Решение транспортной задачи методом потенциалов
3. Метод потенциалов.
Пусть имеется
транспортная
таблица, соответствующая
начальному
решению, хil
=
для базисного
решения переменных,
хil
= 0 для свободных
переменных
(ячейки, соответствующие
свободным
переменным,
остаются пустыми).
Далее, нам требуется
таблица расходов
с заданными
pij.
Отыскание симплекс множителей. Заполним таблицу расходов, оставив ячейки, соответствующие свободным переменным, пустыми. В крайний правый столбец внесем значения неизвестных u1,…,um, в нижнюю строку – значения неизвестных v1,…,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 |
||
|
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.