1. Постановка основного завдання лінійного програмування
1.1 Лінійне програмування
Лінійне програмування - це напрямок математичного програмування, що вивчає методи вирішення екстремальних задач, які характеризуються лінійною залежністю між змінними і лінійним критерієм. Такі завдання знаходять великі додатки в різних сферах людської діяльності. Систематичне вивчення задач такого типу почалося в 1939-1940 рр.. в роботах Л.В. Канторовича.
До математичним завданням лінійного програмування відносять дослідження конкретних виробничо-господарських ситуацій, які в тому чи іншому вигляді інтерпретуються як завдання про оптимальне використання обмежених ресурсів.
Коло завдань, що вирішуються за допомогою методів лінійного програмування досить широкий. Це, наприклад:
· задача про оптимальне використання ресурсів при виробничому плануванні;
· задача про сумішах (планування складу продукції);
· задача про знаходження оптимальної комбінації різних видів продукції для зберігання на складах (управління товарно-матеріальними запасами або);
· транспортні завдання (аналіз розміщення підприємства, переміщення вантажів).
Лінійне програмування - найбільш розроблений і широко застосовуваний розділ математичного програмування (крім того, сюди відносять: целочисленное, динамічне, нелінійне, параметричне програмування). Це пояснюється наступним:
· математичні моделі великого числа економічних завдань лінійни щодо шуканих змінних;
· даний тип завдань в даний час найбільш вивчений. Для нього розроблені спеціальні методи, за допомогою яких ці завдання вирішуються, і відповідні програми для ЕОМ;
· багато завдань лінійного програмування, будучи вирішеними, знайшли широке застосування;
· деякі завдання, які в первісної формулюванні не є лінійними, після ряду додаткових обмежень і припущень можуть стати лінійними або можуть бути приведені до такої форми, що їх можна вирішувати методами лінійного програмування.
Економіко-математична модель будь-якої задачі лінійного програмування включає: цільову функцію, оптимальне значення якої (максимум або мінімум) потрібна відшукати; обмеження у вигляді системи лінійних рівнянь або нерівностей; вимога невід'ємності змінних.
У загальному вигляді модель записується таким чином:
цільова функція
(1.1)
при обмеженнях
(1.2)
вимоги невід'ємності
(1.3)
де xj - змінні (невідомі);
- коефіцієнти задачі лінійного програмування.
Завдання полягає в знаходженні оптимального значення функції (1.1) при дотриманні обмежень (1.2) і (1.3).
Систему обмежень (1.2) називають функціональними обмеженнями задачі, а обмеження (1.3) - прямими.
Вектор, що задовольняє обмеженням (1.2) і (1.3), називається допустимим рішенням (планом) задачі лінійного програмування. План, при якому функція (1.1) досягає свого максимального (мінімального) значення, називається оптимальним.
<...
