Метод северо-западного угла


Сущность этого метода становится понятной при рассмотрении следующеего примера. Пусть условия транспортной задачи заданы табл. 8.4

Таблица 8.4

Постав-щики Потребители Запасы
B1 B2 B3 B4 B5
А1 10 7 4 1 4 a2
100 - - - - 100
А2 2 7 10 6 11 a2
100 150 - - - 250
А3 8 5 3 2 2 a1
- 50 100 50 - 200
А4 11 8 12 16 13 a2
- - - 50 250 300
спрос 200   200   100   100   250   850

 

Не учитывая стоимости перевозки единицы груза, начинаем удовлетворение потребностей первого потребителя B1 за счет запаса поставщика А1 (северо-западный угол). В левый нижний угол клетки А1B1 записываем меньший из располагаемых[ объемов min (a1,b1)=min(100,200)=100 ед. После данной операции запасы первого поставщика полностью израсходованы, поэтому остальные клетки первой строки прочеркиваем. Потребности B1 остались неудовлетворенными на 200-100 = 100 ед. Сравниваем этот остаток с запасами поставщика А2: так как 100 < 250, то 100 ед. записываем в клетку А2B1, чем полностью удовлетворяем потребности потребителя B1, а оставшиеся клетки в первом столбце прочеркиваем.

У поставщика А2 осталось 150 ед.груза. Частично удовлетворяем потребителя B2 за счет оставшегося у поставщика А2 груза. Для этого сравниваем этот остаток с потребностями потребителя В2: 150 < 200, записываем 150 ед. в клетку А2В2, так как запасы А2 полностью израсходованы, прочеркиваем остальные клетки второй строки. Читателю рекомендуется довести данный процесс до конца и получить табл. 8.4.

На этом построение первоначального опорного плана заканчивается.

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

Проверим, является ли план, построенный в табл. 8.4, опорным. Видим, что, начиная движение от занятой клетки A1B1, двигаясь только по занятым клеткам, вернуться в нее, невозможно. Аналогичная ситуация с другими начальными клетками. Следовательно, план является опорным, и в то же время он является невырожденным, поскольку содержит точно m+n-1= 4 + 5-1=8 занятых клеток.

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

Найдем общую стоимость составленного плана как сумму произведений объемов перевозок, стоящих в левом углу занятых клеток, на соответствующие стоимости в этих же клетках:

Z = 100·10+100·2+150·7+50·5+100·3+50·2+50·16+250·13=6950 (ед. стоимости).

Если при составлении опорного плана как-то учитывать стоимость перевозки единицы груза, то, очевидно, план будет значительно ближе к оптимальному.



Дата добавления: 2020-07-18; просмотров: 421;


Поиск по сайту:

Воспользовавшись поиском можно найти нужную информацию на сайте.

Поделитесь с друзьями:

Считаете данную информацию полезной, тогда расскажите друзьям в соц. сетях.
Poznayka.org - Познайка.Орг - 2016-2024 год. Материал предоставляется для ознакомительных и учебных целей.
Генерация страницы за: 0.011 сек.