Реферат: Решение транспортной задачи методом потенциалов
Составленный нами план перевозок, не является оптимальным по стоимости, так как при его построении мы совсем не учитывали стоимость перевозок С ij .
3. Метод потенциалов.
Пусть имеется транспортная таблица, соответствующая начальному решению, х il = 
для базисного решения переменных, х il = 0 для свободных переменных(ячейки, соответствующие свободным переменным, остаются пустыми). Далее, нам требуется таблица расходов с заданными pij .
Отыскание симплекс множителей. Заполним таблицу расходов, оставив ячейки, соответствующие свободным переменным, пустыми. В крайний правый столбец внесем значения неизвестных u 1 ,…, um , в нижнюю строку – значения неизвестных v 1 ,…, vn ,. Эти m + n неизвестных для всех ( i , j ) , соответствующих базисным переменным, должны удовлетворять линейной системе уравнений ui + vj = pij .
| pll | plj | pln | ul | |
. … . | . … . | . . . | ||
| pil | pij | pin | ui | |
. … . | . … . | . . . | ||
| pml | pmj | pmn | um | |
| vl | … | vj | … | vn |
Для всех базисных решений эта система имеет треугольный вид, ранг её матрицы равен n + m – 1 . Следовательно, систему всегда можно решить следующим способом.
Полагают vn = 0. Если значения k неизвестных 
определены, то в системе всегда имеется уравнение, одно из неизвестных в котором уже найдено, а другое ещё нет.
Переменные ui и vj симплекс - множителями . Иногда они называются также потенциалами , а этот метод решения называют методом потенциалов .
Пример 2.
| 5 | u1 | |||
| 6 | 4 | 7 | u2 | |
| 3 | 1 | 8 | u3 | |
| v 1 | v 2 | v 3 | v 4 | v5 |
v 5 = 0 ®u 3 = 8, так как u 3 + u 5 = p 35 = 8, ®v 4 = -7, так как u 3 + v 4 = p 34 = 1, ®v 3 = -5, так как u 3 + v 3 = 3, ®u 2 = 12 ®v 2 = -8, ®v 1 = -6 ®u 1 = 11.
Симплекс – множители нужны для того, чтобы найти свободную ячейку ( i , j ) , которая при замене базиса переходит в базисную (это соответствует отысканию разрешающего столбца в симплекс – методе).
Для определения симплекс – множителей мы вносим на свободные места в таблице значения
p ¢ ij = pij – ui – vj
(коэффициенты целевой функции, пересчитанные для свободных переменных). Если все p ¢ ij 
0, то базисное решение оптимально. В противном случае мы выбираем произвольное p ¢ a b < 0, чаще всего наименьшее. Индексом a b помечено свободное переменное х a b , которое должно войти в базис. Соответствующую ячейку транспортной таблицы мы отметим знаком +.
Пример 3.
| 5 | 6 | 3 | 5 | 9 |
| 6 | 4 | 7 | 3 | 5 |
| 2 | 5 | 3 | 1 | 8 |
pij :
| 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, то заменив am на am + n e и все bj на bj + e , где e > 0 подразумевается очень малым, исправим значения базисных переменныхтак, что бы для новых ai и bj получилось базисное решение. Это всегда можно сделать единственным способом (как и при отыскании симплекс – множителей).
| 15 | ||
| 5 | 5 | 5 |
| 10 | 10 | 0 |
| 20 + e | 5 + e | 10 + e | 10 + e | 5 + e |
| 15 | ||||
| 15 | ||||
| 20 + e |
| 15 + 2 e | ||
| 5 - e | 5 + e | 5 - 2 e |
| 10 + e | 10 + e | 3 e |
Если полученный таким образом элемент 
окажется отрицательным, то в этой же строке должен найтись положительный (ещё до изменения) элемент 
и в этом же столбце – положительный элемент 
. Тогда ячейка ( s , r ) свободна, отмечаем её знаком + и проводим замену базиса. Так можно избавиться от всех отрицательных значений*[1] .