Для того чтобы проверить является ли данный опорный план оптимальным, необходимо применить метод потенциалов. Предварительно сделаем необходимые обозначения:
Vj - потенциалы столбцов;
Ui - потенциалы строк,
Сij - стоимость перевозки единицы груза от каждого поставщика каждому потребителю;
Хij – количество груза, которое будет перевезено от i –ого поставщика к j – ому потребителю,
где i =1,…,m (m – число строк), а j = 1, …, n (n – число столбцов).
Опорный план транспортной задачи может иметь (m + n –1) отличных от нуля неизвестных. В этом случае план является невырожденным.
Если отличных от нуля неизвестных меньше, чем (m + n –1), то такой план – вырожденный. И для нахождения оптимального плана одна из пустых клеток таблицы, в этом случае, считается заполненной нулевым грузом.
Опорный план является оптимальным, если выполняются следующие условия:
1. Для заполненных клеток (Хij > 0 )
Vj – Ui = Сij
2. Для пустых клеток (Хij = 0 )
Vj – Ui £ Сij
для всех i =1,…,m и j = 1, …, n
Опорный план, представленный в таблице 4.6., прежде всего проверим на вырожденность:
- число заполненных клеток в опорном плане (табл. 4.6.) равно 6;
- m + n –1 = 4 + 4 –1 =7.
Следовательно, данный план является вырожденным. Заполним клетку, расположенную на пересечении третьей строки и третьего столбца, нулевым грузом.
Найдем систему потенциалов, исходя из первого условия оптимальности. Но предварительно одному из неизвестных придадим нулевое значение. Обычно приравнивают к нулю неизвестную величину, обозначающую потенциал строки, которая чаще всего встречается в системе или, другими словами, потенциал той строки, в которой больше всего заполненных клеток. В нашем случае это – потенциал третьей строки (U3 =0).
V1 –U3 = 2
V1 = 0 + 2
V1 = 2
V2 –U3 = 3
V2 = 0 +3
V2 = 3
V3 –U3 =6
V3= 0+6
V3 = 6
V4 –U3 =5
V4 = 0+5
V4 = 5
V3 –U1=6
6 - U1 = 6
U1= 0
V4 –U2 =3
5 –U2 =3
U2 = 2
V2 –U4 = 4
3–U4 = 4
U4 = -1
Заполняем потенциалы строк и столбцов (табл. 4.7.)
Таблица 4.7.
V1 = 2 V2 = 3 V3 = 6 V4 =5
U1 =0
6 200
U2 =2
3 180
U3 =0
3 50
6 0
U4 =-1
4 100
Проверяем второе условие оптимальности (для пустых клеток).
Для всех пустых клеток, где нарушено второе условие оптимальности, находим характеристику по следующей формуле:
aij =vj-ui-cij
Из характеристик выбираем наибольшую (в данном случае единственная: a24= 4 –1-2 = 1) и начиная с клетки с данной характеристикой строим цепь (цикл)– ломаная линия, вершины которой расположены в занятых клетках таблицы, кроме первой. Повороты цепи делают под прямым углом. В строке или столбце, где проходит цепь, содержится только две клетки цепи, цепь должна быть замкнута. Клетки цепи отмечаем чередующимися знаками (+) и (-), начиная со знака (+) в первой клетке цепи.
Таблица 4.10.
V1 = 2 V2 = 5 V3 = 7 V4 = 4
U1 =0
5 120
7 10
U2 = 1
- 1 30
6 70
+ 2
U3 = -3
5 120 +
50 -
Из всех объемов поставок, стоящих в клетках со знаком (-), выбираем минимальный, он обозначается буквой Q. Вычитаем Q из поставок отрицательной полу цепи и прибавляем к поставкам положительной полу цепи.
Q = min(30, 50) = 30
Пересчитанные грузы записываем в таблицу 4.11. и пересчитываем потенциалы.
Потенциалы исправляем, начиная с потенциала столбца той клетки, с которой начиналась цепь в предыдущей таблице, т.е. V4=4-1=3 (табл. 4.9.). Уменьшаем его на величину характеристики этой клетки a24 = 1.В столбце, где исправлен потенциал, есть еще заполненные клетки в третьей строке, следовательно, исправляем потенциал третьей строки (U3 = -3-1 = -4). Затем “пройдем” по этой строке и для заполненных клеток исправим потенциал столбцов (V1 = 2-1=1).
Таблица 4.11.
V1 = 2 1 V2 = 5 V3 = 7 V4 = 4 3
U1 =0
5 120
7 10
U2 = 1
6 70
2 30
U3 =-3 -4
5 150
Проверяем исправленную систему на выполнение условий оптимальности:
U3 = -3
V1 = 2 1 V2 = 5 V3 = 7 V4 = 4 3
U3 =-3 -4