Метод двойного предпочтения

Теперь построим опорный план методом двойного предпочтения. При этом сначала в каждом столбце отметим галочкой клетку с наименьшей стоимостью, затем то же самое делаем с каждой строкой. Далее максимально возможные объемы перевозок помещаем в клетки, отмеченные двойной галочкой. Затем распределяем перевозки по клеткам, отмеченным одной галочкой. В оставшейся части таблицы перевозки распределяем по методу минимальной стоимости.

Как видим, данный метод фактически является модифицированным методом минимальной стоимости.

Очевидно, что по крайней мере одна клетка таблицы будет иметь двойную галочку (этой клеткой обязательно будет клетка с минимальным тарифом). В нашем случае таких клеток будет две: (А ₁, В ₁) и (А ₃, В ₂). Их и заполним в первую очередь:

х ₁₁ = 70; х ₃₂ =80.

Клетками с одной галочкой будут: (А ₁, В ₄); (А ₂, В ₅); (А ₂, В ₂) и (А ₁, В ₃) (проверьте это). Клетка (А ₂, В ₂) не будет заполнена, в этом нет необходимости, поскольку во втором столбце занята одна клетка: (А ₃, В ₂) с двойной галочкой. Остальные клетки используем:

х ₁₄ = 110; х ₁₃ = 20; х ₂₅ = 90.

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

х ₂₃ = 110; х ₃₃ =20.

Получаем новый опорный план транспортной задачи:

ПН ПО	В 1	В 2	В 3	В 4	В 5	а i
А 1	4	¾	6	5	¾
А 2	¾	7 ¾		¾	10
А 3	¾	5		¾	¾
b j

Этому опорному плану соответствует стоимость перевозок:

F (X ₃) =4 × 70 + 6 × 20 + 5 × 110 + 10 × 90 + 5 × 80 + 12 × 20 = 3480.

Отметим, что и этот план имеет семь ненулевых перевозок, поэтому является невырожденным.

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

Метод потенциалов получения оптимального плана ТЗ