Метод минимальной стоимости

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

В данном случае сама дешёвая клетка ( А₁ , В₁ ). С неё и начинаем распределение грузов:

х₁₁ = min { 200 ; 70 } = 70.

Вычеркиваем оставшиеся клетки первого столбца и повторяем процесс в оставшейся части таблицы. Запишем последовательность заполнения клеток:

х₁₄ = min { 200 - 70 ; 110 } = 110;

х₃₂ = min { 100 ; 80 } = 80;

х₁₃ = min { 200 – 70 – 110 ; 150 } = 20;

х₂₃ = min { 200 ; 150 - 20 } = 130;

х₂₅ = min { 200 - 130 ; 90 } = 70;

х₃₅ = 20.

Получаем следующий опорный план:

ПН ПО	В1	В2	В3	В4	В5	bj
А1	4 70	11 	6 20	5 110	15 	200
А2	8 	7 	9 130	13 	10 70	200
А3	10 	5 80	12 	7 	20 20	100
аi	70	80	150	110	90

Здесь получены семь ненулевых перевозок, поэтому план невырожденный. Подсчитаем его стоимость:

F ( X₂ ) = 4  70 + 6  20 + 5  110 + 9  130 + 10  70 + 5  80 + 20  20 = 3620.

Как видим, этот опорный план дешевле первого.

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

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

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

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

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

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

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

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

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

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

ПН ПО	В1	В2	В3	В4	В5	аi
А1	4 70	11 	6 20	5 110	15 	200
А2	8 	7 	9 110	13 	10 90	200
А3	10 	5 80	12 20	7 	20 	100
bj	70	80	150	110	90

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

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

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

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