нійного програмування необхідно кожному фахівцю в області прикладної математики.
Лінійне програмування являє собою найбільш часто використовуваний метод оптимізації. До числа завдань лінійного програмування можна віднести завдання:
В· раціонального використання сировини і матеріалів; задачі оптимального розкрою;
В· оптимізації виробничої програми підприємств;
В· оптимального розміщення і концентрації виробництва;
В· складання оптимального плану перевезень, роботи транспорту;
В· управління виробничими запасами;
В· і багато інших, належать сфері оптимального планування.
1.1 Транспортна завдання
Транспортна задача відноситься до класу задач лінійного програмування. Транспортна задача вирішує проблему знаходження оптимального (мінімального за вартістю) плану розподілу і переміщення ресурсів від виробників до споживачів. Проблема оптимізації вартості перевезень актуальна і на сьогоднішній день, тому що дозволяє фірмам і підприємствам істотно скоротити витрати на транспорт. Правильна організація перевезень дозволяє усунути зустрічні та дублюючі перевезення, скоротити кількість дальніх перевезень і т. д. При вирішенні транспортної задачі необхідно:
В· забезпечити всіх споживачів ресурсами;
В· розподілити всі вироблені ресурси;
В· перемістити ресурси від виробників до споживачів з найменшими витратами.
Від кожного виробника ресурс може переміщатися до будь-якого споживача і вимірюватися в одних одиницях вимірювання.
1.2 Методи складання опорного плану транспортної задачі
1.2.1 Метод північно-західного кута
На кожному етапі максимально можливим числом заповнюють ліву верхню клітину частини, що залишилася таблиці. Заповнення таким чином, що повністю виноситься вантаж з або повністю задовольняється потреба.
1.2.2 Метод найменшої вартості
Суть методу полягає в тому, що з усієї таблиці вартостей вибирають найменшу. І в клітку, яка їй відповідає, поміщають менше з чисел a i або b j . Потім, з розгляду виключають або рядок, відповідну постачальнику, запаси якого повністю витрачені, або стовпець, відповідний споживачеві, потреби якого повністю задоволені. Або і рядок і стовпець, якщо витрачені запаси постачальника і задоволені потреби споживача. З решти таблиці вартостей знову вибирають найменшу вартість, і процес розподілу запасів продовжують, поки всі запасів не будуть розподілені, а потреби задоволені.
Алгоритм:
В· З таблиці тарифів вибирають найменшу вартість. І в клітку, яка їй відповідає, вписують менше з чисел.
В· Перевіряються рядка постачальників на наявності рядки з витраченими запасами і стовпці споживачів на наявність стовпця, потреби якого повністю задоволені. Такі ст...
