 |
 |
 |
 |
|
 |
 |
64
базисных клеток, и по нему можно так определить потенциалы u
i
и v
j
, чтобы для каждой базисной клет-
ки (т. е. для той, в которой х
i,j
> 0) выполнялось условие
Поскольку система (3.10) содержит m+n-1 уравнение и m+n неизвестных, то один из потенциалов
можно задать произвольно (например, приравнять v
j
или u
i
к нулю). После этого остальные неизвестные
u
i
и v
j
определяются однозначно.
Рассмотрим процесс определения потенциалов текущего плана транспортной задачи на примере. В
табл. 3.3 переписаны условия задачи из табл. 3.1 и ее допустимый базисный план, построенный
методом северо-западного угла (см. табл. 3.2).
Потенциал первого пункта потребления принимаем равным нулю (v1=0). Теперь, зная его, мы можем
определить потенциалы для всех пунктов производства, связанных с первым пунктом ненулевыми
перевозками. В данном случае их два (это первый и второй пункты), получаем:
Имея u2 и учитывая, что во второй строке таблицы существуют еще ненулевые компоненты х
2,2
и х
2,3
,
можно определить v2 = u2 + c
2,2
= -10+17=7 и v3 = u2 +c
2,3
= -10+15=5, после чего появляется возможность
рассчитать u3 = v3 – c
3,3
=5 - 25 = - 20 и, наконец, v
4
= u3+ c
3,4
= -20 +21=1. В результате получаем полную
систему потенциалов, показанную в табл. 3.3.
Для свободных клеток транспортной таблицы вычисляются величины ?
i,j
= v
j
-
u
i
, называемые
разностями потенциалов. В табл. 3.4 они выписаны для всех небазисных клеток под ценами.
Разность потенциалов ?
i,j
можно трактовать как увеличение цены продукта при его перевозке из
пункта i в пункт j. Согласно критерию оптимальности (3.8)-(3.9), если все ?
i,j
?
с
i,j
, то план оптимален, в
противном случае, если существует хотя бы одна разность потенциалов ?
i,j
> с
i,j
, то он может быть
улучшен. Процесс «улучшения» плана состоит в определении вводимой и выводимой клеток, в чем
прослеживается содержательная аналогия с соответствующими пунктами симплекс-процедур.
Кандидатом на ввод, очевидно, может быть любая клетка, в которой ?
i,j
> с
i,j
, поскольку после ввода в
базис будет обеспечено равенство ?
i,j
= с
i,j
. Для определенности обычно рекомендуется брать ту клетку,
в которой оценка ?
i,j
- с
i,j
максимальна. В рассматриваемом нами примере это будет клетка (3, 1).
Выводимая клетка определяется с помощью так называемой цепочки преобразования плана,
описывающей характер перераспределения грузовых потоков. В соответствии со свойствами
транспортной задачи для невырожденного базисного плана в текущей таблице можно образовать