Розв’язяння задач цілочисельного програмування за допомогою методу Гоморі

Міністерство освіти і науки України Ужгородський державний інститут інформатики, економіки і права факультет інформатики Реєстраційний № Дата      ІНДИВІДУАЛЬНА РОБОТА на тему: Розв’язяння задач цілочисельного програмування за допомогою методу Гоморі Написав: студент ІІІ курсу факультету інформатики

Мартиненко О. М. Ужгород 2002 Становленню лінійного програмування, його узагальненням і додаткам величезну допомогу зробило створення в середині 40-х років XX століття електронних обчислювальних машин (ЕОМ). Справа в тім, що екстремальні задачі, що включають у свої умови нестрогі нерівності, рідко допускають рішення у формі, що до XX століття була широко поширена в математику

і широко використовується тепер і в шкільній математиці. Мова йде про запис рішень у виді формул, що виражають шукані перемінні через параметри задачі. Найпростіші приклади - формули для площ трикутника, кола, для коренів квадратного рівняння, для крапок мінімуму і максимуму квадратного тричлена і т.п. Такий "формульний тип рішення" математичних задач часто зручний для використання, а в найпростіших ситуаціях його знання для математика обов'язково

як таблиця множення. Його достоїнство складається в глобальности: одержавши формулу один раз, її можна використовувати для одержання чисельної відповіді в будь-якій конкретній ситуації. Формульне рішення володіє й істотним недоліком: надзвичайно вузький клас математичних задач, для рішення яких удається побудувати зручні формули. В останні роки за допомогою ЕОМ вчені істотно просунулися в цій області і стали непотрібними численні таблиці формул.

Тепер ЕОМ сама одержує формулу для рішення математичної задачі, якщо задача допускає формульне рішення. Однак уже давно відомо, що проблема побудови формул для рішення більшості математичних задач принципово нерозв'язна. У зв'язку з цим з появою ЕОМ на перший план став виходити інший тип рішення математичних задач. Цей тип рішення був відомий ще И. Ньютонові, але використовувався в математику не дуже часто.

На відміну від формульного новий тип рішення призначався для одержання чисельної відповіді з кожної наперед заданою точністю для конкретних задач із заданими чисельними значеннями параметрів. У дискретному програмуванні змінні (усі чи частина) задачі можуть приймати лише скінчене число значень, можуть бути, наприклад, лише цілими числами (задача цілочисельного програмування). Одним з прикладів задач цілочисельного програмування може служити так звана “задача про заплічник”:

є m різноманітних предметів, відома вага кожного предмета та його вартість. Потрібно визначити, які предмети потрібно покласти в заплічник, щоб загальна маса не перевищувала заданої границі, а загальна вартість була максимальною. Виділення з теорії екстремальних задач спеціальних частин дозволяє створювати для них ефективні методи, що враховують специфіку цих задач. Розглянемо задачі цілочисельного програмування, в котрих як цільова функція, так

і функції у системі обмежень є лінійними. У зв’язку з цим сформулюємо основну задачу лінійного програмування, в якій змінні можуть приймати тільки цілі значення. У загальному вигляді цю задачу можна записати так: знайти максимум функції (1) при умовах (2) (3) цілі, (4) Якщо знайти розв’язок задачі (1) – (4) за допомогою симплекс-методу, то він може виявитися як цілочисельним, так і ні (прикладом задачі лінійного програмування, розв’язок якої завжди

є цілочисельним, служить транспортна задача). У загальному ж випадку для визначення оптимального плану задачі (1) – (4) потрібні спеціальні методи. На теперішній час існує декілька таких методів, із яких найбільш відомим є метод Гоморі, в основі якого лежить симплекс-метод. МЕТОД ГОМОРІ Знаходження розв’язку задачі цілочисельного програмування методом

Гоморі починають з визначення за допомогою звичайного симплекс-методу оптимального плану задачі (1) – (3) без урахування цілочисельності змінних. Після того, як цей план знайдений, проглядають його компоненти. Якщо серед компонент немає дробових чисел, то знайдений план являється оптимальним планом задачі цілочисельного програмування (1) – (4). Якщо ж у оптимальному плані задачі (1) – (3) змінна xj приймає дробове значення, то до системи рівнянь (1) – (3) додають нерівність (5)

і шукають розв’язок задачі (1) – (3), (5). В нерівності (5) та - перетворені вихідні величини aij та bi, значення котрих узяті з останньої симплекс-таблиці, а та - дробові частини чисел (під дробовою частиною деякого числа а підрозумівається найменше невід’ємне число в таке, що різниця між а і в є цілим). Якщо у оптимальному плані задачі (1) – (3) дробові значення приймають декілька змінних, то додаткова нерівність (5) визначається найбільшою дробовою частиною.

Якщо у знайденому плані задачі (1) – (3) змінні приймають дробові значення, то знову додають одне додаткове обмеження і процес обчислень продовжують. Проводячи скінчене число ітерацій, або отримують оптимальний план задачі (1) – (4), або встановлюють її нерозв’язність. Якщо вимога цілочисельності (4) стосується лише декотрих змінних, то такі задачі називаються частково цілочисельними. Їх розв’язок також знаходять послідовним розв’язанням задач, кожна

наступна з яких отримується із попередньої за допомогою введення додаткового обмеження. У цьому випадку обмеження має наступний вигляд: (6) де визначається зі слідуючих співвідношень: 1) для xj, котрі можуть приймати нецілочисельні значення: при , = при ; (7) 2) для xj, котрі можуть приймати тільки цілочисельні значення: при , = при ; (8) З вищесказаного слідує, що процес визначення оптимального плану задачі цілочисельного програмування

методом Гоморі включає в себе слідуючи основні етапи: 1.Використовуючи симплекс-метод, знаходять розв’язок задачі (1) – (3) без урахування вимог до цілочисельності змінних. 2.Складають додаткове обмеження для змінної, котра в оптимальному плані задачі (1) – (3) має максимальне дробове значення, а в оптимальному плані задачі (1) – (4) має бути цілочисельною. 3.Використовуючи двоїстий симплекс-метод, знаходять розв’язок задачі, котра отримується

із задачі (1) – (3) в результаті додавання ще одного додаткового обмеження. 4. У випадку необхідності складають ще одне додаткове обмеження і продовжують ітераційний процес до отримання оптимального плану задачі (1) – (4) або встановлення її нерозв’язності. СПИСОК ВИКОРИСТАНОЇ ЛІТЕРАТУРИ 1. Абрамов С.А Гнездилов Г. Г. Задачи по программированию.

М.: Наука, 1988. 2. Акулич. И. Л. Математическое программирование в примерах и задачах. М.: Высшая школа, 1986. 3. Данциг Дж. Линейное программирование, его применения и обобщения. М.: Прогресс, 1966.