Тема 3. Задача лінійного програмування та методи її розв’язування

ЛАБОРАТОРНЕ ЗАНЯТТЯ №8.

 

Тема заняття: Побудова вихідних опорних планів транспортної задачі.

Мета: сформувати вміння та навички побудови вихідних опорних планів транспортної задачі методами північно-західного кута, найменшої вартості та подвійного перевантаження.

Методичні рекомендації: Вивчити лекцію №4 та ознайомиться з наступною літературою [1 с. 159-189], [2 с.134-158], [3 с.129-168], [4 с.134-175]

Побудова початкового опорного плану транспортної задачі.

Для побудови початкового опорного плану транспортної задачі існує кілька методів: північно-західного кута; мінімальної вартості; подвійної переваги; апроксимації Фогеля. Побудову опорного плану зручно подавати у вигляді таблиці, в якій постачальники продукції є рядками, а споживачі — стовпчиками.

Побудову першого плану за методом північно-західного кута починають із заповнення лівої верхньої клітинки таблиці (х ₁₁), в яку записують менше з двох чисел а ₁ та b ₁. Далі переходять до наступної клітинки в рядку або у стовпчику і заповнюють її, і т. д. Закінчують заповнювати таблицю у правій нижній клітинці.

Ідея методу мінімальної вартості полягає в тому, що на кожному кроці заповнюють клітинку таблиці, яка має найменшу вартість перевезення одиниці продукції. Такі дії повторюють доти, доки не буде розподілено всю продукцію між постачальниками та споживачами.

 

Задача 1.

Скласти вихідний план транспортної задачі методами північно-західного кута, найменшої вартості та подвійного перевантаження і оцінити його вартість, якщо відомі:

– запаси однотипної продукції торгівельних баз;

– величини попиту магазинів роздрібної торгівлі;

– вартість перевезення одиниці однотипної продукції від -ї торгівельної бази до -го магазину роздрібної торгівлі.

 

1. ; 2. ;

 

3. ; 4. ;

5. ; 6. ;

 

 

ДОДАТКОВІ ЗАВДАННЯ:

7. ; 8. ;

9. ; 10. ;