Формирование начального плана методом наименьшей стоимости

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

Рассмотрим метод на исходных данных примера 1. Укажем в знаменателе клеток – порядковый номер в упорядоченной по возрастанию последовательности c_ij. При одинаковых значениях c_ij приоритет устанавливаем по убыванию max(a_i, b_j) (значение приведено в скобках в числителе):

Таблица 4.

ai \ bj	b1=25	b2=10	b3=35	B4=5	B5=35
a1 =20	5(25) / 9	6(20) / 12	2(35) / 3	3(20) / 6	1(35) / 2
a2 =30	3(30) / 5	7(30) / 14	8(35) / 16	6(30) / 11	8(35) / 17
a3 =45	9(45) / 18	8(45) / 15	1(45) / 1	4(45) / 8	3(45) / 4
a4 =15	9(25) / 19	3(15) / 7	6(35) / 10	10(15) / 20	7(35) / 13

Начинаем распределение с элемента х₃₃ =35 (т.к. В₃ может принять только такое количество груза), затем x₁₅ = 20 и заносим в табл. 5. Так как запасы пункта A₁ исчерпаны, то 1-я строка исключа­ется из дальнейшего рассмотрения, так же как в 3-й столбец, поскольку потребности В₃ также удовлетворены. В табл. 5 они для дальнейшего удобства отмечены крестиками в самом правом столбце и самой нижней строке.

Таблица 5.

ai \ bj	b1=25	b2=10	b3=35	B4=5	B5=35
a1 =20	5 / 0	6 / 0	2 / 0	3 / 0	1 / 20	Х
a2 =30	3 / 0	7 / 0	8 / 0	6 / 0	8 / 0	30
a3 =45	9 / 0	8 / 0	1 / 35	4 / 0	3 / 0	10
a4 =15	9 / 0	3 / 0	6 / 0	10 / 0	7 / 0	15
	25	10	Х	5	15

В оставшихся клетках табл. 4 наименьший порядковый номер в знаменателе равен 4 в клетке (3,5). Для пункта В₅ остаток составляет 15 ед. груза, а в A₃ – 10. Присваиваем х₃₅ =10 и закрываем для распределения пункт A₃. Из оставшихся клеток табл. 4 наименьший порядковый номер в знаменателе равен 5 в клетке (2,1). Присваиваем х₂₁ =25 и закрываем для распределения пункт В₁. Полученный план представлен в табл. 6.

Таблица 5.

ai \ bj	b1=25	b2=10	b3=35	B4=5	B5=35
a1 =20	5 / 0	6 / 0	2 / 0	3 / 0	1 / 20	Х
a2 =30	3 / 25	7 / 0	8 / 0	6 / 0	8 / 0	5
a3 =45	9 / 0	8 / 0	1 / 35	4 / 0	3 / 10	Х
a4 =15	9 / 0	3 / 0	6 / 0	10 / 0	7 / 0	15
	Х	10	Х	5	5

В оставшихся клетках табл. 4 наименьший порядковый номер в знаменателе равен 7 в клетке (4,2). Для пункта В₂ остаток составляет 10 ед. груза. Присваиваем х₄₂ =10 и закрываем для распределения пункт В₂. Далее присваиваем х₂₄ =5 и закрываем для распределения пункт В₄ и A₂.

Таблица 6.

ai \ bj	b1=25	b2=10	b3=35	B4=5	B5=35
a1 =20	5 / 0	6 / 0	2 / 0	3 / 0	1 / 20	Х
a2 =30	3 / 25	7 / 0	8 / 0	6 / 5	8 / 0	Х
a3 =45	9 / 0	8 / 0	1 / 35	4 / 0	3 / 10	Х
a4 =15	9 / 0	3 / 10	6 / 0	10 / 0	7 / 0	5
	Х	Х	Х	Х	5

Единственная незакрытая клетка (4,5). Присваиваем ей х₄₅ =5. Окончательный план приведен в табл. 7.

Таблица 7.

ai \ bj	b1=25	b2=10	b3=35	B4=5	B5=35
a1 =20	5 / 0	6 / 0	2 / 0	3 / 0	1 / 20	Х
a2 =30	3 / 25	7 / 0	8 / 0	6 / 5	8 / 0	Х
a3 =45	9 / 0	8 / 0	1 / 35	4 / 0	3 / 10	Х
a4 =15	9 / 0	3 / 10	6 / 0	10 / 0	7 / 5	Х
	Х	Х	Х	Х	Х

Распределение груза закончено. Подученное в табл. 7 решение оказалось вырожден­ным, так как содержит 7 ненулевых значений неизвестных вместо нужных 8 = m+n–1=4+5-1. Дня того чтобы иметь 8 базисных клеток, нужно в одну из незаполненных клеток (но не любую), например, в клетку с индексами (3, 4), поместить нуль. Получим табл. 8. В ней.8 базисных клеток для наглядности отмечены цветом. Значения базисных неизвестных в базисном решении равны x₁₅ = 20, x₂₁ = 25, x₂₄=5, x₃₃ = 35, x₃₄ = 0, x₃₅ = 10, x₄₂ = 10, x₄₅ = 5.

Таблица 8.

ai \ bj	b1=25	b2=10	b3=35	b4=5	B5=35
a1 =20	5 / 0	6 / 0	2 / 0	3 / 0	1 / 20
a2 =30	3 / 25	7 / 0	8 / 0	6 / 5	8 / 0
a3 =45	9 / 0	8 / 0	1 / 35	4 / 0	3 / 10
a4 =15	9 / 0	3 / 10	6 / 0	10 / 0	7 / 5

Стоимость перевозок

Z = 1*20+3*25+6*5+1*35+4*0+3*10+3*10+7*5 = 20+75+30+35+30+30+35 = 255,

Что в два раза меньше, чем для плана, полученного методом северо-западного угла.