4.4. Проверка лучшего опорного плана на оптимальность

Для проверки плана на оптимальность можно применить метод потенциалов.

Для этого надо ввести так называемые псевдостоимости . Входящие в псевдостоимости величины _i и _j называют потенциалами. Псевдостоимости обладают следующими свойствами:

при x_ij  0 (базисные клетки); (4.1)

при x_ij = 0 (свободные клетки). (4.2)

Кроме того, псевдостоимости могут быть отрицательными.

Для транспортной задачи 4х6 введем величины ₁, ₂, ₃, ₄, соответствующие первым четырем ограничениям, и ₁, ₂, ₃, ₄, ₅, ₆ – остальным ограничениям.

Запишем условия (4.1) для базисных клеток:

 ₁ + ₂ = 1;

₁ + ₄ = 1;

₂ + ₂ = 1;

₂ + ₅ =7;

₂ + ₆ = 4;

₃ + ₃ = 4;

 ₃ + ₅ =7;



(4.3)

₄ + ₅ =9.

Запишем условия (4.2) для свободных клеток:

 ₁ + ₁  7;

₁ + ₃  8;

₁ + ₅  5;

₁ + ₆  3;

₂ + ₁  7;

₂ + ₃  8;

₂ + ₄  5;

₃ + ₁  3;

₃ + ₂  7;

₃ + ₄  5;

 ₃ + ₆  5;

₄ + ₂  2;



(4.4)

₄ + ₄  9;

₄ + ₆  9.

Система (4.3) состоит из 9 уравнений и содержит 10 переменных: . Поскольку число независимых переменных в данной системе равно 4 + 6  1 = 9, то одна переменная из множества  или  свободная. Пусть это будет ₁. Положив ₁=0, получим: ₁ = 0, ₂ = 0, ₃ =2, ₄ = 4, ₁  = –3, ₂ =1, ₃ = 2, ₄ = 1, ₅ = 5, ₆ = 4. Составим таблицу перевозок, соответствующую данному решению (табл. 4.7).

Полученное решение ₁, ₂, ₃, ₄, ₁, ₂, ₃, ₄, ₅, ₆ подставляем в систему (4.4), т.е. в пустые клетки. Если ограничения системы (4.4) являются верными неравенствами при найденном решении, то проверяемый допустимый план исходной задачи является оптимальным, иначе  план не оптимален, и его надо улучшать.

Из табл. 4.7 видно, что при данном решении не выполняются четвертое, одиннадцатое, двенадцатое и тринадцатое неравенства системы (4.4) – им соответствуют клетки А₁В₆, А₃В₆, А₄В₂, А₄В₃. Это значит, что полученное решение не оптимально, его необходимо улучшить.

Таблица 4.7

Проверка плана ТЗ на оптимальность и первый цикл пересчета