Практикум по дискретной математике в среде виртуальной лаборатории системы ДО ИТМО (стр. 9 )

220	110				0
	60	210			0
			150	200	0
0	0	0	0	0	b\a

Стоимость перевозок при таком распределении будет определяться:

С = 220*10 + 110*12 + 60*22 + 210*49 + 150*67 +200*63 =ед.

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

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

1.  Выбираем незаполненную клетку с минимальной стоимостью сij.

2.  Сравниваем количество груза в ai и потребности bj.

3.  Если ai > bj, то в выбранную клетку заносим величину bj, что означает, что пункт потребления bj мы насытили, а в пункте поставки осталось груза (ai - bj), j-й столбец вычеркиваем из рассмотрения. Начинаем просматривать i-ю строку в поисках незаполненной клетки с минимальной стоимостью. Это клетка со стоимостью cik (пусть j=k). Переходим к п.2.

4.  Если ai = bj, то вычеркиваем i-ю строку и j-й столбец. Это означает, что пункт потребления bj насыщен, а в пункте потребления ai нет больше груза. Переходим к п.6.

5.  Если ai < bj, то в выбранную клетку заносим ai, т. е. весь груз из пункта поставки ai распределили в пункт потребления bj. В пункт потребления bj осталось доставить груз в количестве (bj - ai). Вычеркиваем из рассмотрения i-ю строку. Начинаем просматривать j-й столбец в поисках незаполненной клетки с минимальной стоимостью. Это клетка со стоимостью ckj (пусть i=k). Переходим к п.2.

6.  Проверяем, есть ли еще ненасыщенные пункты потребления bj. Если есть, то переходим к п.1, иначе - заканчиваем процесс построения опорного плана.

Пример: Рассмотрим данный метод на том же примере, что и в методе «северо-западного угла» [15].

10	12	24	50	12	330
13	22	49	66	320	270
26	27	35	67	63	350
220	170	210	150	200	b\a

Выбираем самую дешевую перевозку среди возможных, это – С11 = 10. Выполняем п. 3 алгоритма:

220					110
					270
					350
0	170	210	150	200	b\a

Далее опять выбираем самую дешевую перевозку из возможных (на пересечении строк и столбцов с ненулевыми значениями массивов a и b), это - С12 = 12. Далее выполняем п. 5 алгоритма и получаем следующий результат:

220	110				0
					270
					350
0	60	210	150	200	b\a

Теперь самая дешевая перевозка соответствует С22 = 22. Далее по п.3 получим:

220	110				0
	60				210
					350
0	0	210	150	200	b\a

Теперь самая дешевая перевозка соответствует С33 = 35. Далее по п. 4 получим:

220	110				0
	60				210
		210			140
0	0	0	150	200	b\a

Теперь самая дешевая перевозка соответствует С35 = 63. Далее по п. 5 получим:

220	110				0
	60				210
		210		140	0
0	0	0	150	60	b\a

Теперь самая дешевая перевозка соответствует С24 = 66. Далее по п. 3 получим:

220	110				0
	60		150		60
		210		140	0
0	0	0	0	60	b\a

В итоге получим следующий опорный план перевозок: