Пример 4.2. Определить начальное решение по методу "северо-западного" угла для транспортной задачи из примера 4.1

Определить начальное решение по методу "северо-западного" угла для транспортной задачи из примера 4.1.

Решение.

Транспортная таблица имеет следующий вид (табл. 4.2):

Таблица 4.2

В первую клетку помещают: х₁₁ = min(160,120) = 120. Спрос первого потребителя полностью удовлетворен, первый столбец вычеркивают. Остаток сырья в первом пункте составляет: 160 – 120=40 усл. ед. Двигаемся по первой строке вправо х ₂₁ =min(160 -120,50) = 40. Предложение поставщика исчерпано, первая строка вычеркивается. Второму потребителю не хватает 50-40=10 усл. ед. Двигаемся по второму столбцу вниз х ₂₂ = min(140,50 – 40) = 10; Второй столбец вычеркивается. Двигаемся по второй строке вправо х ₂₃ = min(140 -10,90) = 130. Вторая строка вычеркивается. Двигаемся по третьему столбцу вниз x₃₃ = min(170,190 -130) = 60. Спрос третьего потребителя удовлетворен. Двигаемся по третьей строке вправо х₃₄ = min(170 -160, 10) = 110. Таблица заполнена. Число ненулевых значений x_ij, , равно 6. Число базисных переменных задачи 3+4 -1=6. Остальные 3*4-6=6 переменных являются свободными, их значения равны нулю.

Начальный план перевозок имеет вид

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

S₁ = 120*7+40*8+10*5+130*9+60*3+110*6=3220.

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