Пример 4.2. Определить начальное решение по методу "северо-западного" угла для транспортной задачи из примера 4.1
Определить начальное решение по методу "северо-западного" угла для транспортной задачи из примера 4.1. Решение. Транспортная таблица имеет следующий вид (табл. 4.2): Таблица 4.2
В первую клетку помещают: х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, Начальный план перевозок имеет вид Стоимость перевозок по этому плану составляет S1 = 120*7+40*8+10*5+130*9+60*3+110*6=3220. Метод "северо-западного" угла — наиболее простой метод нахождения начального решения. План перевозок, полученный по этому методу, обычно бывает достаточно далек от оптимального.
|
, равно 6. Число базисных переменных задачи 3+4 -1=6. Остальные 3*4-6=6 переменных являются свободными, их значения равны нулю.
