Транспортная задача. Контрольная работа (стр. 2 )

40	50-			+
	10+	60	10-
			40+	20-
				40

Знак + поставлен в ячейке (1,5). Соответственно в последнем столбце должен быть поставлен знак -, это можно сделать только в ячейке (3,5). В ячейке с числом 40 этого сделать нельзя, так как тогда в соответствующей строке не было бы знака +, и т. д.

Затем мы определяем минимум М из всех элементов, помеченных знаком -, и выбираем ячейку (g, d), где этот минимум достигается.

В нашем примере с М = 10, выберем (g, d) = (2, 4); при этом (g, d) определяет базисное переменное, которое должно стать свободным, т. е. базисное переменное, соответствующее индексу разрешающей строки симплекс – метода.

	40	60	60	50	60
90	40	50-			+
80		10+	60	10-
60				40+	20-
40					40

¯

	40	60	60	50	60
90	40	40			10
80		20	60
60				50	10
40					40

Переход к новой транспортной таблице (замена базиса) происходит следующим образом:

а). В ячейку (a, b) новой таблицы записывается число М.

б). Ячейка (g, d) остается пустой.

в). В других ячейках помеченных знаками – или +, число М вычитается из стоящего в ячейке числа (-) или складывается с ним (+). Результат вносится в соответствующую ячейку новой таблицы.

г). Непомеченные числа переносятся в новую таблицу без изменений. Остальные ячейки новой таблицы остаются пустыми.

Получается новая транспортная таблица, и повторяется ход предыдущих рассуждений. После конечного числа шагов критерий минимальности будет выполнен (если не учитывать теоретически возможного зацикливания в случае вырождения).

Копт = 40*5 + 40*2 + 20*4 + 60*3 + 50*0 + 10*6 + 40*1 + 10*3 = 670

Вторая итерация:

5	2			3	u1
	4	3			u2
			0	6	u3
				1	u4
v1	v2	v3	v4	v5

v5 = 0

u4 + v5 = p45 = 1 ® u4 = 1,

u3 + v5 = p35 = 6® u3 = 6,

u1 + v5 = p15 = 3® u1 = 3,

u3 + v4 = p34 = 0 ® v4 = -6,

u1 + v1 = p11 = 5 ® v1 = 2,

u1 + v2 = p12 = 2 ® v2 = -1,

u2 + v2 = p22 = 4 ® u2 = 5,

u2 + v3 = p23 = 3 ® v3 = -2.

5	2			3	3
	4	3			5
			0	6	6
				1	1
2	-1	-2	-6	0

5	2	8	7	3
-3	4	3	3	2
-3	-1	-1	0	6
0	2	6	12	1

Минимальный элемент -3 ® (a, b) = (3,1).

40	40			10
	20	60
+			50	10
				40

®

40-	40			10+
	20	60
+			50	10-
				40

Затем определили минимум из всех элементов, помеченных знаком – (М = 10), и выбрали ячейку (3, 5), где этот минимум достигается ®