Метод Гоморі, целочисленное програмування
Економічна і геометрична інтерпретація задачі цілочислового програмування. Екстремальна задача, змінні якої приймають лише цілочисельні значення, називається завданням цілочисельного програмування.
У математичної моделі задачі цілочислового програмування як цільова функція, так і функції в системі обмежень можуть бути лінійними, нелінійними і змішаними. Обмежимося випадком, коли цільова функція і система обмежень задачі є лінійними.
У цеху підприємства вирішено встановити додаткове обладнання, для розміщення якого виділено площі. На придбання обладнання підприємство може витратити 10 тис. Руб. при цьому воно може купити обладнання двох видів. Комплект обладнання I виду коштує 1000 руб. а II виду - 3000 руб. Придбання одного комплекту обладнання I виду дозволяє збільшити випуск продукції в зміну на 2 од. а одного комплекту обладнання II виду - на 4 од. Знаючи що для установки одного комплекту обладнання I виду потрібно 2 м 2 площі, а обладнання II виду - 1 м 2 площі визначити такий набір додаткового обладнання, яких дає можливість максимально збільшити випуск продукції
Рішення. Складемо математичну модель задачі. Припустимо, що підприємство придбає x1 комплектів обладнання I виду і комплектів обладнання II виду. Тоді змінні x1 і повинні відповідати таким нерівності:
Якщо підприємство придбає зазначену кількість устаткування, то загальне збільшення випуску продукції складе
За своїм економічним змістом змінні x1 і можу приймати лише цілі невід'ємні значення, т. Е.
Таким чином, приходимо до наступної математичної задачі: знайти максимальне значення лінійної функції (71) при ви виконанні умов (70), (72) і (73). Так як невідомі можуть приймати тільки цілі значення, то задача (70) - (73) є завданням цілочисельного програмування. Оскільки число невідомих задачі дорівнює двом, рішення даного завдання можна знайти, використовуючи її геометричну інтерпретацію. Для цього перш за все побудуємо багатокутник рішень завдання, що складається у визначенні максимального значення лінійної функції (71) при виконанні умов (70) і (72) (рис. 11). Координати всіх точок побудованого багатокутника рішень ОАЕВС задовольняють системі лінійних нерівностей (70) і умові незаперечності змінних (72). Разом з тим умові (73), т. Е. Умові целочисленности змінних, задовольняють координати лише 12 точок, позначених на рис. 11. Щоб знайти точку, координати якої визначають рішення вихідної задачі, замінимо багатокутник ОАВС многоугольником OKEMNF. що містить всі допустимі точки з цілочисельними координатами і таким, що координати кожної з вершин є цілими числами. Значить, якщо знайти точку максимуму функції (71) на багатокутнику OKEMNF. то координати цієї точки і визначать оптимальний план завдання.
Для цього побудуємо вектор і пряму проходить через багатокутник рішень OKEMNF (число 12 взято довільно). Побудовану пряму пересуваємо в напрямку вектора доти, поки вона не пройде через останню загальну точку її з даними многоугольником. Координати цієї точки і визначають оптимальний план, а значення цільової функції в ній є максимальним.
В даному випадку шуканої є точка E (1; 3), в якій цільова функція приймає максимальне значення С ледовательно, координати точки Е визначають оптимальний план задачі (70) - (73). Відповідно до цього плану підприємству слід придбати один комплект обладнання 1 виду і три комплекти обладнання II виду. Це забезпечить підприємству при наявних у нього обмеження на виробничі площі та грошові кошти максимальне збільшення випуск продукції, що дорівнює 14 од. в зміну.
Для виконання робіт можуть бути використані п механізмів. Продуктивність i -го механізму при виконанні j- й роботи дорівнює. Припускаючи, що кожен механізм може бути використаний тільки на одній роботі і кожна робота може виконуватися тільки одним механізмом, визначити закріплення механізмів за роботами, що забезпечує максимальну продуктивність. Побудувати математичну модель задачі.
Рішення. Введемо змінну xij. значення якої дорівнює 1, якщо при виконанні i- й роботи використовується j- й механізм, і дорівнює 0 в іншому випадку. Тоді умови використання кожного механізму тільки на одній роботі виражаються рівностями
а умови виконання роботи тільки одним механізмом - равенствами
Таким чином, завдання полягає у визначенні таких значень невідомих, які відповідають системам рівнянь (74) і (75) і умові (76), при яких досягається максимальне значення функції
Сформульована задача є задачею цілочислового програмування.
Визначення оптимального плану задачі цілочислового програмування. Розглянемо задачі цілочислового програмування, в яких як цільова функція, так і функції в системі обмежень є лінійними. У зв'язку з цим сформулюємо основну задачу лінійного програмування, в якій змінні можуть приймати тільки цілі значення. У загальному вигляді це завдання можна записати так: знайти максимум функції
Якщо знайти рішення задачі (78) - (81) симплексним методом, то воно може виявитися як цілочисельним, так і немає (прикладом задачі лінійного програмування. Рішення якої завжди є цілочисельним, служить транспортна задача). У загальному ж випадку для визначення оптимального плану задачі (78) - (81) потрібні спеціальні методи. В даний час існує декілька таких методів, з яких найбільш відомим є метод Гоморі. в основі якого лежить описаний вище симплексний метод.
Метод Гоморі. Знаходження рішення задачі цілочислового програмування методом Гоморі починають з визначення симплексним методом оптимального плану задачі (78) - (80) без урахування целочисленности змінних. Після того як цей план знайдений, переглядають його компоненти. Якщо серед компонент немає дробових чисел, то знайдений план є оптимальним планом задачі цілочислового програмування (78) - (81). Якщо ж в оптимальному плані задачі (78) - (80) змінна приймає дробове значення, то до системи рівнянь (79) додають нерівність
і знаходять рішення задачі (78) - (80), (82).
У нерівності (82) і - перетворені вихідні величини і значення яких взяті з останньої симплекс-таблиці, а й - дробові частини чисел (під дробовою частиною деякого числа а розуміється найменше невід'ємне число b таке, що різниця між а і b є ціле). Якщо в оптимальному плані задачі (78) - (80) дробові значення приймають декілька змінних, то додаткове нерівність (82) визначається найбільшою дробовою частиною.
Якщо в знайденому плані задачі (78) - (80), (82) змінні приймають дробові значення, то знову додають одне додаткове обмеження і процес обчислень повторюють. Проводячи кінцеве число ітерацій, або отримують оптимальний план задачі цілочислового програмування (78) - (81), або встановлюють її нерозв'язність.
Якщо вимога целочисленности (81) відноситься лише до деяких змінним, то такі завдання називаються частково цілочисельними. Їх рішення також знаходять послідовним вирішенням завдань, кожна з яких виходить з попередньої за допомогою введення додаткового обмеження. У цьому випадку таке обмеження має вигляд
де визначаються з наступних співвідношень:
1) у випадку, які можуть приймати нецілочисельне значення,
2) у випадку, які можуть приймати тільки цілочисельні значення,
З викладеного вище випливає, що процес визначення оптимального плану задачі цілочислового програмування методом Гоморі включає наступні основні етапи.
1. Використовуючи симплексний метод, знаходять рішення задачі (78) - (80) без урахування вимоги целочисленности змінних.
2. Складають додаткове обмеження для змінної, яка в оптимальному плані задачі (78) - (80) має максимальне дробове значення, а в оптимальному плані задачі (78) - (81) має бути целочисленной.
3. Використовуючи двоїстий симплекс-метод. знаходять рішення задачі, що виходить з завдання (78) - (80) в результаті приєднання додаткового обмеження.
4. У разі необхідності складають ще одне додаткове обмеження і продовжують ітераційний процес до отримання оптимального плану задачі (78) - (81) або встановлення її нерозв'язності.
Методом Гоморі знайти максимальне значення функції
Дати геометричну інтерпретацію рішення задачі.
Рішення. Для визначення оптимального плану задачі (86) - (89) спочатку знаходимо оптимальний план завдання (86) - (88) (табл. 22).
Знаходимо тепер максимальне значення функції (86) при виконанні умов (87), (88) і (90) (табл. 23).
З таблиці 23 видно, що вихідна задача цілочисельного програмування має оптимальний план П ри цьому плані значення цільової функції дорівнює. Дамо геометричну інтерпретацію рішення задачі. Областю допустимих рішень задачі (86) - (88) є багатокутник OABCD (рис. 12). З рис. 12 видно, що максимальне значення цільова функція приймає в точці С (19/2; 7/2), т. E. що Х = (19/2; 7/2; 0; 0; 34) є оптимальним планом. Це безпосередньо видно і з таблиці 22. Так як Х = (19/2; 7/2; 0; 0; 34) не є оптимальним планом задачі (86) - (89) (числа і - дробові), то вводиться додаткове обмеження . Виключаючи з нього і підстановкою замість них відповідних значень з рівнянь системи обмежень (87), отримаємо відтинає від багатокутника OABCD трикутник EFC.
Як видно з рис. 12, областю допустимих рішень отриманої завдання є багатокутник OABEFD. У точці Е (9; 4) цього багатокутника цільова функція даного завдання набуває максимального значення. Так як координати точки Е - цілі числа і невідомі, і приймають цілочисельні значення при підстановці в рівняння (87) значень і, то є оптимальним планом задачі (86) - (89). Це випливає і з таблиці 23.
Методом Гоморі знайти рішення задачі, що складається у визначенні максимального значення функції
Дати геометричну інтерпретацію рішення задачі.
Рішення. Сформульовану задачу перепишемо так: знайти максимальне значення функції
Завдання (95) - (98) є частково целочисленной, так як змінні і можуть приймати нецілочисельне значення.
Знаходимо симплексним методом рішення Задаянна (95) - (97) (таблиця 24).