- Предмет дискретного програмування
- Постановка завдання лінійного програмування
- Геометрична інтерпретація задачі лінійного програмування
- приклад
Анотація: Предмет дискретного програмування. Постановка завдання лінійного програмування. Геометрична інтерпретація задачі лінійного програмування. Загальний шлях знаходження оптимального плану. Обчислювальні методи лінійного програмування. Приклад математичної моделі дискретного програмування (транспортна задача). Метод північно-західного кута.
Предмет дискретного програмування
Справжня лекція присвячена дискретним завданням математичного програмування. Найбільш вивченими завданнями цього класу є цілочисельні задачі лінійного програмування, тобто завдання лінійного програмування, в яких на всі змінні (або на їх частину) накладено додаткову вимогу целочисленности. У першому з цих випадків зазвичай говорять про повністю цілочисельних, а в другому - про частково цілочисельних завданнях. Зрозуміло, аналогічним чином можна визначити цілочисельні (частково цілочисельні) варіанти і для більш загальних задач оптимального програмування - можна говорити, наприклад, про завдання опуклого цілочисельного програмування тощо.
Від цілочисельних задач прийнято відрізняти так звані дискретні задачі математичного програмування, в яких областю допустимого зміни кожної змінної є не безліч цілих невід'ємних чисел, а деякий заданий кінцевий безліч. Такі завдання (на кінцевих множинах) можуть бути формально зведені до цілочисельним.
Дослідження в цьому напрямку, розпочаті ще в шістдесяті роки минулого століття, до теперішнього часу просунулися настільки далеко, що зараз ми вже маємо право говорити про самостійне розділі математичного програмування - дискретно програмуванні. У літературі вживається також термін "целочисленное програмування" і рідше - "комбинаторное програмування". Однак нам представляється, що термін "дискретне програмування" найбільш повно відображає специфіку питання, хоча при його використанні і виникає деяка небезпека змішання дискретного програмування і, скажімо, дискретного аналізу.
Постановка завдання лінійного програмування
Лінійне програмування є складовою частиною більш загального методу - математичного програмування. Математичне програмування дозволяє знаходити найкращі плани розподілу обмежених ресурсів для досягнення необхідної мети - вирішення задачі. Лінійне програмування може бути використано як один з методів оптимізації рішення. Найкращий результат тут досягається не за рахунок виділення додаткових сил і засобів або інших ресурсів, а за рахунок їх раціонального розподілу.
Рішення, найкращим чином відповідає цільовій настанові і задовольняє умовам задачі, називається оптимальним планом.
Лінійне програмування від інших видів математичного програмування відрізняється тим, що математична модель, відповідна цільової установці завдання, може бути записана за допомогою лінійних співвідношень виду:
,
де 
- 
- 
- відомі коефіцієнти;
- - - невідомі змінні 
.
У загальному вигляді постановка задачі лінійного програмування має такий вигляд.
Умови завдання задаються у вигляді системи лінійних рівнянь або нерівностей, які представляють обмеження, що накладаються на використання наявних ресурсів:
де
.
шукані величини 
не можуть бути негативними; 
- відомі постійні величини, що характеризують умови задачі.
Цільова функція задається у вигляді такої лінійної форми:
де - постійні коефіцієнти, які зазвичай називають коефіцієнтами вартості .
Цільову функцію за умовами задачі потрібно звернути в мінімум або максимум. У деяких завданнях вираження (6.2.) Задаються у вигляді нерівностей. У цих випадках, вводячи в кожне лінійне обмеження додаткові невід'ємні невідомі
,
можна привести систему лінійних обмежень до виду (6.2.).
Геометрична інтерпретація задачі лінійного програмування
Геометричну інтерпретацію задачі лінійного програмування розглянемо на прикладі.
приклад
Чотири види овочів 
необхідно розподілити по шести транспортних засобів 
.
Розподіл овочів за транспортними засобами пов'язане з необхідністю врахування низки обмежень, які можуть бути описані системою чотирьох рівнянь з шістьма невідомими, аналогічними системі 6.2.
Сенс першого рівняння в нашому прикладі означає, що овоч типу 1, загальний ресурс якого становить 16 одиниць, може розміщуватися в кількості чотирьох одиниць на транспортному засобі першого типу і однієї одиниці на транспортному засобі четвертого типу. Аналогічно і друге рівняння і так далі.
Остання умова говорить про те, що число типів транспортного засобу не може бути негативним.
Необхідно визначити, яка кількість транспортного засобу кожного типу слід мати, щоб загальні втрати в них були мінімальними.
Оплата за конкретний транспортний засіб (в тисячах рублів) задана наступною таблицею.
Згідно з наведеними даними, цільова функція, що підлягає оптимізації, набуде вигляду:
.
Рішення завдання зводиться до виконання обмежень, заданих рівнянням (6.4.)
У цьому прикладі, коли 
, Кожне з обмежувальних лінійних рівнянь (6.4.), А також лінійна функція (6.5.), Можуть бути представлені геометрично в двомірному просторі (на площині), що дає можливість досить наочно інтерпретувати основні ідеї методу лінійного програмування.
Геометрична інтерпретація задачі лінійного програмування. Щоб мати можливість наочно уявити обмеження і цільову функцію на графіку, необхідно висловити все невідомі через дві незалежні величини, наприклад, 
і 
, Відповідні координатним осях, щодо яких буде проводитися побудова ( Мал. 6.1 ). З рівняння (6.4.) Слід:
А цільова функція прийме такий вигляд:
.
З зіставлення рівнянь (6.6.) І останнього з обмежень (6.2.) 
слід:
Кожному з нерівностей (6.8.) На графіку Мал. 6.1 відповідає напівплощина, в межах якої знаходяться всі допустимі даними нерівністю значення змінної величини 
.
Так, наприклад, нерівності 
відповідає напівплощина вправо від осі (Межа її заштрихована).
нерівності
відповідає напівплощина вправо і вгору від лінії, що відповідає значенню даного нерівності (при 
).
Рівняння цієї лінії
.
Таким же чином можна побудувати кордону, що визначаються іншими рівняннями.
Нерівностей (6.8.) Відповідає деяка область - шестикутник 
, Утворений межами згаданих вище напівплощин. Ця область може бути названа областю допустимих планів, оскільки будь-яка точка в її межах відповідає вимогам накладених обмежень (6.4.).
З усіх доступних планів нас цікавить оптимальний план, при якому функція мети досягає мінімуму.
Цільової функції відповідає сімейство паралельних прямих. Розглянемо одну з них, що проходить через початок координат, що буде мати місце при 
.
При цьому
.
Цікавить нас пряма , Як видно з малюнка 6.1 , Має нахил вправо від осі . Переймаючись різними значеннями 
, Отримаємо сімейство прямих ліній, паралельних прямій , Яка проходить через точку 0. При цьому чим менше буде , Тим, очевидно, правіше розташовується відповідна пряма.
Оскільки ми добиваємося мінімального значення , Нас буде цікавити пряма, розташована в найбільшому видаленні вправо від прямої і проходить через багатокутник , - пряма 
.
Як видно з малюнка 6.1 , Єдиною точкою, відповідної оптимальному плану, буде та вершина багатокутника , Яка одночасно належить області допустимих планів і відповідає вимозі мінімізації цільової функції - вершина 
.
Отже мінімум цільової функції досягається в вершині многогранника. Існує теорема про те, що для будь-якого завдання лінійного програмування знайдеться вершина багатогранника допустимих рішень, в якій цільова функція досягає свого мінімального (максимального) значення.
