Метод потенциалов

Для формулировки критерия оптимальности используем теоремы двойственности. Выпишем транспортную задачу вместе с двойственной к ней в таблицу 2.9.

Для удобства первые m уравнений исходной задачи умножим на –1; неизвестные двойственной задачи, соответствующие первым m уравнениям исходной задачи, обозначены через u ₁, u ₂, ..., u_m, а неизвестные, соответствующие последним n уравнениям – через v ₁, v₂,..., v_n. Систему неравенств двойственной задачи кратко можно записать в виде

(i= ; j = ).

Неизвестные u ₁, u₂ ,..., u_m будем рассматривать как оценки единицы груза, находящегося в распоряжении соответствующего поставщика, или потенциалыпоставщиков, а неизвестные v ₁ , v₂,..., v_m – как оценки единицы груза, доставленного соответствующему потребителю, или потенциалы потребителей. Потенциалы можно интерпретировать соответственно как цены в пункте поставщика или в пункте потребителя.

Применяя теорему 2.8 о дополняющей нежесткости, приходим к следующему критерию оптимальности.

Таблица 2.9

 

Задача 1	Задача 2
Минимизировать где	Максимизировать где
при условиях ...... ......	при условиях ........... ...........
....... ......	........... ...........

 

Окончание таблицы 2.9

 

.................... ....................

... , ...

любого знака

 

Теорема 2.11. (критерий оптимальности плана транспортной задачи). Для того чтобы план перевозок Х* = () был оптимальным, необходимо и достаточно, чтобы существовали числа () и (), удовлетворяющие следующим условиям:

а) для всех базисных клеток плана ( > 0) ;

б) для всех свободных клеток ( =0) .

Замечание. В оба условия критерия потенциалы u _i и v_j входят только в виде разностей v_j – u_i, и поэтому потенциалы определяются с точностью до постоянного слагаемого, т. е. если числа и удовлетворяютусловиям критерия, то им будут удовлетворять и числа и , где с – произвольное число.

Проверим исходное опорное решение Х₀, полученное ранее, на оптимальность. С этой целью составим систему уравнений, соответствующих положительным перевозкам (занятым клеткам) плана Х_0, т. е.

v ₁ – u ₁ = 2, v ₂ – u ₂ = 3, v ₃ – u ₃ = 4,

v ₂ – u ₁ = 4, v ₃ – u ₂ = 6, v ₄– u ₃ = 5,

где u ₁, u ₂, u ₃ –потенциалы поставщиков, а v ₁, v ₂, v ₃, v ₄ – потенциалы потребителей (для удобства эти потенциалы записаны справа и снизу от плана Х₀). Решим данную систему, положив, например, u ₁ = 0.Получим следующие значения:

v ₁ = 2, v ₂ = 4, u ₂ = 1, v ₃ = 7, u ₃ = 3, v ₄ = 8.

Для свободных клеток плана Х₀ составим систему неравенств:

Подставляя полученные значения потенциалов в данную систему неравенств, имеем:

Неравенства не выполняются для двух перевозок x ₁₃ = 0 и x ₁₄ = 0 плана Х₀ (для двух свободных клеток). Значит план Х₀ не оптимален и требуется построить новый (улучшенный) план перевозок, для которого транспортные затраты меньше или, по крайней мере, равны затратам для предыдущего плана.

Обозначим разность (v_j – u_i) – c_ij= . Эта величина называется оценкой свободной клетки. Для двух клеток (1, 3) и (1, 4) эти оценки положительны. Выбираем максимальную из них .

В новом, улучшенном, плане клетка (1, 4) (соответствующая максимуму ) должна быть занятой. Введем в план перевозку x ₁₄ = e ( значение e будет определено ниже). Для того чтобы новый план удовлетворял условиям (2.10)–(2.11), внесем в план Х₀ следующие поправки. Перевозку х ₁₂ = 50, стоящую в той же строке матрицы Х₀, что и х ₁₄ = e, уменьшим на e; перевозку х ₂₂ = 250, стоящую в том же столбце, что и х ₁₂, увеличим на e; аналогично х ₂₃ = 100 уменьшим на e, х ₃₃ = 250 увеличим на e и, наконец, х₃₄ = 200 уменьшим на e.
В результате новый план перевозок Х _{1 e} будет иметь вид, представленный на рис. 2.12.

 

50- e

e

u 1

250+ e

100- e

u 2

250+ e

200- e

u 3

v 1

v 2

v 3

v 4

 

Рис. 2.12

 

Здесь e должно удовлетворять неравенствам , т. е. (чтобы все значения 50 – e, 100 – e, 200 – e были неотрицательными). Для плана Х _{1 e} стоимость перевозок составит

Выбрав наибольшее возможное значение e, т. е. e = 50, получим новый план Х₁, представленный на рис. 2.13. Перераспределение перевозок при переходе от плана Х₀ к плану Х₁ было произведено по замкнутой ломаной линии, называемой обычно циклом (этот цикл отмечен пунктиром на рис. 2.12). Вычислим транспортные затраты для плана Х₁

 

.

 

Они оказались меньше транспортных затрат для плана Х₀. Следовательно, план Х₁ лучше плана Х₀. Таким образом, включение в план Х₁ перевозки x ₁₄ = 50, оказалось оправданным и транспортные затраты уменьшились на величину .

 

u 1

u 2

u 3

v 1

v 2

v 3

v 4

 

Рис. 2.13

 

Далее найдем новые значения потенциалов поставщиков и потребителей из уравнений

v ₁ – u ₁ = 2, v ₂ – u ₂ = 3 v ₃ – u ₃ = 4,

v ₄ – u ₁ = 3, v ₃ – u ₂ = 6, v ₄ – u ₃ = 5,

соответствующих занятым клеткам плана Х₁.

При u ₁ = 0 получим v ₁ = 2, v ₄ = 3, u ₃ = –2, v ₃ = 2, u ₂ = –4, v ₂ = –1.

Подставив найденные значения потенциалов в неравенства

соответствующие свободным клеткам плана Х₁, получим

v ₂ – u ₁ = – 1 < 4, v ₁ – u ₂ = 6 > 4, v ₁ – u ₃ = 4 < 6,

v ₃ – u ₁ = 2 < 5, v ₄ – u ₂ = 7 = 7, v ₂ – u ₃ = 1 < 5.

Не выполняется только третье неравенство, соответствующее перевозке х ₂₁ = 0. В плане Х₁ только одна положительная оценка . Включая в план Х₁ перевозку , и, перераспределяя другие перевозки по циклу , получим новый план Х₂ (см. рис. 2.14)

 

u1

u2

u3

v1

v2

v3

v4

 

Рис. 2.14

 

План Х₂ лучше плана Х₁, т. к. для него стоимость транспортных затрат оказалась меньше, чем для плана Х₁. Применительно к плану Х₂ вновь составим систему уравнений

v ₁– u ₁ = 2, v ₁ – u ₂ = 4, v ₃– u ₃ = 4,

v ₄ – u ₁ = 3, v ₂ – u ₂ = 3, v ₄ – u ₃ = 5

и неравенств

Положив u ₁ = 0, из последней системы уравнений получим v ₁ = 2, v ₄ = 3, u ₃ = –2, v ₃ = 2, u ₂ = –2, v ₂ = 1. Найденные значения потенциалов удовлетворяют последней системе неравенств. Действительно,

Так как потенциалы u ₁ = 0, v ₄ = 3, u ₃ = –2, v ₁ = 2, v ₃ = 2, u ₂ = –2, v ₂ = 1 удовлетворяют обоим условиям критерия оптимальности, то план Х₂ будет оптимальным, а стоимость перевозок f (Х₂) = 3600 является минимальной.

Оптимальное решение формулируется следующим образом. Первый поставщик должен доставить 150 ед. груза первому потребителю и 100 ед. четвертому, второй поставщик доставит 50 ед. груза первому потребителю и 300 ед. второму и третий поставщик – 350 ед. третьему потребителю и 100 ед. – четвертому. Суммарные транспортные расходы составляют 3600 (денежных единиц). Оптимальный план Х₂ выпишем в виде матрицы

 

.

 

Описанный выше метод решения транспортной задачи называется методом потенциалов. Подводя итоги предыдущих рассмотрений, сформулируем последовательность шагов, необходимых для решения транспортной задачи методом потенциалов.

Шаг 1. Проверить, является ли данная транспортная задача закрытой. Если да, то перейти ко второму шагу. Если нет, то свести ее к закрытой задаче путем введения либо фиктивного поставщика, либо фиктивного потребителя.

Шаг 2. Найти исходное опорное решение (исходный опорный план) закрытой транспортной задачи.

Шаг 3. Проверить полученное опорное решение на оптимальность:

а) вычислить для него потенциалы поставщиков u _iи потребителей v _j ;

б) для всех свободных клеток (i, j) вычислить оценки ;

в) если все оценки неположительны (), то решение задачи окончено: исходный опорный план оптимален. Если среди оценок есть хотя бы одна положительная, то переходим к четвертому шагу.

Шаг 4. Выбрать клетку (i^*, j^*) с наибольшей положительной оценкой и для нее построить замкнутый цикл перераспределения груза. Цикл начинается и заканчивается в выбранной клетке. Получим новое опорное решение, в котором клетка (i^*, j^*) окажется занятой. Возвращаемся к третьему шагу.

Через конечное число шагов будет получено оптимальное решение, т. е. оптимальный план перевозок продукции от поставщиков к потребителям.