Решение транспортной задачи методом потенциалов (стр. 2 из 2)
Полагают vn = 0. Если значения k неизвестных
определены, то в системе всегда имеется уравнение, одно из неизвестных в котором уже найдено, а другое ещё нет.Переменные ui и vj симплекс - множителями. Иногда они называются также потенциалами, а этот метод решения называют методом потенциалов.
Пример 2.
| 5 | u1 | |||
| 6 | 4 | 7 | u2 | |
| 3 | 1 | 8 | u3 | |
| v1 | v2 | v3 | v4 | v5 |
v5= 0 ®u3 = 8, так как u3 + u5= p35= 8, ®v4 = -7, так как u3+ v4= p34= 1, ®v3 = -5, так как u3+ v3= 3, ®u2 = 12 ®v2 = -8, ®v1 = -6 ®u1 = 11.
Симплекс – множители нужны для того, чтобы найти свободную ячейку (i, j), которая при замене базиса переходит в базисную (это соответствует отысканию разрешающего столбца в симплекс – методе).
Для определения симплекс – множителей мы вносим на свободные места в таблице значения
p¢ij= pij – ui – vj
(коэффициенты целевой функции, пересчитанные для свободных переменных). Если все p¢ij 
0, то базисное решение оптимально. В противном случае мы выбираем произвольное p¢ab< 0, чаще всего наименьшее. Индексом abпомечено свободное переменное хab, которое должно войти в базис. Соответствующую ячейку транспортной таблицы мы отметим знаком +.
Пример 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+ neи все 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 + 2e | ||
| 5 - e | 5 + e | 5 - 2e |
| 10 + e | 10 + e | 3e |
Если полученный таким образом элемент
окажется отрицательным, то в этой же строке должен найтись положительный (ещё до изменения) элемент 
и в этом же столбце – положительный элемент 
. Тогда ячейка (s, r) свободна, отмечаем её знаком + и проводим замену базиса. Так можно избавиться от всех отрицательных значений*[1].Затем при помощи метода потенциалов расчеты продолжают дальше (вырождение уже никогда больше не встретится). Устремляя e® 0, приходим к оптимальному решению исходной задачи.
Список использованной литературы:
1. Еремин И.И., Астафьев Н.Н. Введение в теорию линейного и выпуклого программирования М.; Наука, 1976г.
2. Карманов В.Г. Математическое программирование. – М.; Наука, 1986г.
3. Моисеев Н.Н., Иванов Ю.П., Столярова Е.М. Методы оптимизации. – М.; Наука, 1978г.
4. Иванов Ю.П., Лотов А.В. Математические модели в экономике. – М.; Наука, 1979г.
5. Бронштейн И.Н., Семендяев К.А. Справочник по математике. – М.; Наука, 1986г.
[1] Часто бывает достаточно везде заменить e на -e.