Метод северо-западного угла
Сущность этого метода становится понятной при рассмотрении следующеего примера. Пусть условия транспортной задачи заданы табл. 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; просмотров: 428;