Определить начальное решение по методу "северо-западного" угла для транспортной задачи из примера 4.1.
Решение.
Транспортная таблица имеет следующий вид (табл. 4.2):
Таблица 4.2
№ | Предложение | ||||
120 7 | 40 8 | 1 | 2 | ||
4 | 10 5 | 130 9 | 8 | ||
9 | 2 | 60 3 | 110 6 | ||
Спрос |
В первую клетку помещают: х11 = min(160,120) = 120. Спрос первого потребителя полностью удовлетворен, первый столбец вычеркивают. Остаток сырья в первом пункте составляет: 160 – 120=40 усл. ед. Двигаемся по первой строке вправо х 21 =min(160 -120,50) = 40. Предложение поставщика исчерпано, первая строка вычеркивается. Второму потребителю не хватает 50-40=10 усл. ед. Двигаемся по второму столбцу вниз х 22 = min(140,50 – 40) = 10; Второй столбец вычеркивается. Двигаемся по второй строке вправо х 23 = min(140 -10,90) = 130. Вторая строка вычеркивается. Двигаемся по третьему столбцу вниз x33 = min(170,190 -130) = 60. Спрос третьего потребителя удовлетворен. Двигаемся по третьей строке вправо х34 = min(170 -160, 10) = 110. Таблица заполнена. Число ненулевых значений xij, , равно 6. Число базисных переменных задачи 3+4 -1=6. Остальные 3*4-6=6 переменных являются свободными, их значения равны нулю.
|
|
Начальный план перевозок имеет вид
Стоимость перевозок по этому плану составляет
S1 = 120*7+40*8+10*5+130*9+60*3+110*6=3220.
Метод "северо-западного" угла — наиболее простой метод нахождения начального решения. План перевозок, полученный по этому методу, обычно бывает достаточно далек от оптимального.