Тема 3 «Лінійне програмування»
План лекції
1. Загальна постановка задачі лінійного програмування (ЗЛП).
2. Форми запису ЗЛП (загальна, стандартна, канонічна форми).
3. Приклади практичних задач лінійного програмування:
3.1 Задача оптимального використання ресурсів виробництва.
3.2 Задача оптимального вибору технологій
3.3 Задача про суміші.
3.4 Задача про розкрій.
3.5 Транспортна задача.
3.6 Задача про призначення.
3.7 Задача оптимізації міжгалузевих зв’язків.
1. Загальна постановка задачі лінійного програмування (злп)
Джерела лінійного програмування зв'язані з II Світовою війною. Джеймс Данциг (1947 р.) - розробив симплекс метод. Теодост Купманс - запропонував термін лінійного програмування. Самі джерела лінійного програмування (методи рішення, геометрична інтерпретація та ін..) були введені в 30-х роках у Ленінградському університеті Л.В. Конторовичем. Поштовх у розвитку лінійного програмування дав засновник теорії ігор Нейман, що розвив концепцію двоїстості. Всі 50-роки інтенсивно вивчалися методи лінійного програмування, які лежать в основі алгоритмів рішення задач цілочисельного, стохастичного й нелінійного програмування. В останні роки поштовх у розвитку цієї дисципліни дав розвиток обчислювальної техніки.
Лінійне програмування – розділ математичного програмування, який використовується при розробці методів відшукання екстремуму лінійних функцій декількох змінних при лінійних додаткових обмеженнях, що накладаються на змінні.
Кілька слів про самий термін лінійне програмування. Він вимагає правильного розуміння. У цьому випадку програмування - це, звичайно, не складання програм для ЕОМ. Програмування тут повинне інтерпретуватися як планування, формування планів, розробка програми дій.
До математичних задач лінійного програмування відносять дослідження конкретних виробничо-господарських ситуацій, які в тому або іншому виді інтерпретуються як задачі про оптимальне використання обмежених ресурсів.
Коло задач, розв'язуваних за допомогою методів лінійного програмування, досить широкий. Це, наприклад:
задача про оптимальне використання ресурсів при виробничому плануванні;
задача про суміші (планування складу продукції);
задача про знаходження оптимальної комбінації різних видів продукції для зберігання на складах (керування товарно-матеріальними запасами або "задача про рюкзак");
транспортні задачі (аналіз розміщення підприємства, переміщення вантажів).
Лінійне програмування - найбільш розроблений і широко застосовуваний розділ математичного програмування.
Це пояснюється наступним:
математичні моделі великої кількості економічних задач лінійні щодо шуканих змінних;
даний тип задач у цей час найбільш вивчений. Для нього розроблені спеціальні методи, за допомогою яких ці задачі вирішуються, і відповідні програми для ЕОМ;
багато задач лінійного програмування, будучи вирішеними, знайшли широке застосування;
деякі задачі, які в первісному формулюванні не є лінійними, після ряду додаткових обмежень і допущень можуть стати лінійними або можуть бути наведені до такої форми, що їх можна вирішувати методами лінійного програмування.
Економіко-математична модель будь-якої задачі лінійного програмування включає:
цільову функцію, оптимальне значення якої (максимум або мінімум) потрібно відшукати;
обмеження у вигляді системи лінійних рівнянь або нерівностей;
вимога невід’ємності змінних.
У загальному виді модель записується в таким чином:
цільова функція:
=
c1x1 + c2x2 + ... + cnxn
→ max(min); (1)
обмеження:
(2)
|
a11x1 + a12x2 + ... + a1nxn {≤ = ≥} b1, a21x1 + a22x2 + ... + a2nxn {≤ = ≥} b2, ... am1x1 + am2x2 + ... + amnxn {≤ = ≥} bm; |
вимога невід’ємності: xj ≥ 0,
(3)
При цьому aij, bi, cj (
)
- задані сталі величини.
Завдання полягає в знаходженні оптимального значення функції (1) при дотриманні обмежень (2) і (3).
Систему обмежень (2) називають функціональними обмеженнями задачі, (умовами задачі), а обмеження (3) - прямими.
Вектор
,
що задовольняє обмеженням (2) і (3),
називається припустимим рішенням
(планом) задачі лінійного програмування.
План
,
при якому функція (1) досягає свого
максимального (мінімального) значення,
називається оптимальним.
Далі введемо основні визначення, пов'язані з вирішенням ЗЛП.
Усяке невід’ємне рішення системи обмежень задачі линійного програмування називається планом.
Будемо називати будь-який план задачі лінійного програмування припустимим, якщо він задовольняє умовам обмежень задачі.
Припустимий план будемо називати опорним, якщо в ньому відмінні від нуля не більше m+n–1 компонент, а інші - дорівнюють нулю.
Якщо в опорному плані число відмінних від нуля компонентів дорівнює в точності n-m–1, то план є невироджений, інакше - вироджений.
Припустимий план, при якому цільова функція задачі лінійного програмування приймає своє мінімальне значення, називається оптимальним планом.
За типом вирішуваних завдань його методи поділяються на:
універсальні;
спеціальні.
За допомогою універсальних методів можуть вирішуватися будь-які задачі лінійного програмування.
Спеціальні методи враховують особливості моделі завдання, її цільової функції і системи обмежень.
Особливістю ЗЛП є те, що екстремуму цільова функція досягає на кордоні області припустимих рішень.