Постановка транспортной задачи

 

v₅ = 0 ® u₃ = 8, так как u₃ + u₅ = p₃₅ = 8, ® v₄ = -7, так как u₃ + v₄  = p₃₄ = 1,  ® v₃ = -5, так как u₃ + v₃  = 3, ® u₂ = 12  ® v₂ = -8, ® v₁ = -6  ® u₁ = 11.

Симплекс – множители  нужны для того, чтобы найти свободную ячейку (i, j), которая при замене базиса переходит в базисную (это соответствует отысканию разрешающего столбца в симплекс – методе).

Для определения симплекс – множителей мы вносим на свободные  места в таблице значения

p¢_ij = p_ij – u_i – v_j

(коэффициенты целевой  функции, пересчитанные для свободных  переменных). Если все  p¢_ij 0, то базисное решение оптимально. В противном случае мы выбираем произвольное p¢_ab < 0, чаще всего наименьшее. Индексом ab помечено свободное переменное х_ab , которое должно войти в базис. Соответствующую ячейку транспортной таблицы мы отметим знаком +.

Пример 3.

5	6	3	5	9
6	4	7	3	5
2	5	3	1	8

p_ij: 

5					11
6	4	7			12	®
		3	1	8	8
-6	-8	-5	-7	0

   

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

 

 

Минимальный элемент  –7 ®   (a, b) = (2,5).

Кроме ячейки (a, b) транспортной таблицы, мы пометим значками – и + другие занятые числами ячейки таким образом, чтобы в каждой строке и в каждом столбце транспортной таблицы число знаков + было равно числу знаков -. Это всегда можно сделать единственным образом, причем в каждой строке и в каждом столбце будет содержаться максимум по одному знаку = и по одному  знаку -.

Пример 4.

 

15
5	5	5		+	®
		5	10	5

 

	15
®	5	5	5-		+
			5+	10	5-

 

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

 

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

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

 

 

	20	5	10	10	5
15	15
15	5	5	5-		+
20			5+	10	5-

 

¯

 

15
5-	5			5+
+		10	10	0-

 

¯

 

15-		+
5	5			5
0+		10-	10

 

¯

 

5		10
5-	5		+	5
10+			10-

 

¯

5		10
	5		5	5
15			5

 

К_опт = 150

 

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

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

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

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

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

Пример 5.

15
5	5	5-		+	®
		5+	10	5-

 

	15
®	5	5			5
			10	10	0

 

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

Пример 6. Ниже воспроизведен  ход решения примера 1.

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

 

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

 

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

 

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

 

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

 

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

 

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

Если дана вырожденная  транспортная таблица (её можно узнать   по     имеющемуся 0, то заменив a_m на a_m + ne  и  все  b_j  на b_j + e , где e >  0 подразумевается очень малым, исправим значения базисных переменных так, что бы для новых a_i и b_j получилось базисное решение. Это всегда можно сделать единственным способом (как и при отыскании симплекс – множителей).

 

15
5	5			5
		10	10	0

 

	20 + e	5 + e	10 + e	10 + e	5 + e
15
15
20 + e

 

15 + 2e
5 - e	5 + e			5 - 2e
		10 + e	10 + e	3e