ТЕМА 8. ЦІЛОЧИСЛОВЕ ПРОГРАМУВАННЯ.

1.   Цілочислові задачі математичного програмування.

2.   Постановка задачі цілочислового лінійного програмування, її інтерпретація та основні підходи до розв’язування.

3.   Метод повного (суцільного) перебору можливих варіантів рішень).

4.   Розв’язування лінійних задач змішаного програмування методом відтинання площинами (методом Ґоморі).

5.   Комбінаторні методи.

1.   Цілочислові задачі математичного програмування.

При розв’язуванні задач, змінні у яких позначають кількість одиниць неподільної продукції (літаків, машин, комп’ютерів), очевидною є вимога цілочисельності.

Задачі цілочислового програмування – це задачі оптимізації, розв’язком яких є цілі числа. Такі задачі відносяться до більш складних задач оптимізації і роз’язуються більш складними методами.

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

2.   Постановка задачі цілочислового лінійного програмування, її інтерпретація та основні підходи до розв’язування.

Задача цілочислового програмування формулюється так само, як задача лінійного програмування, але вона містить додаткову вимогу, яка полягає в тому, що значення змінних, які становлять оптимальний розв’язок, мають бути цілими невід’ємними числами:

;

; (8.1)

.

Як показує практика, розв’язання цілочислових оптимізаційних задач є досить трудомістким. Для знаходження їх оптимального розв’язку використовують спеціальні методи з врахуванням скінченності числа можливих розв’язків будь-якої цілочислової задачі.

3.   Метод повного (суцільного) перебору можливих варіантів рішень).

Одним із методів розв’язання цілочислових оптимізаційних задач є метод повного (суцільного) перебору можливих варіантів рішень.

Однак зазначений метод є достатньо трудомісткістким, особливо при зростанні кількості змінних і розширенні області граничних умов.

4.   Розв’язування лінійних задач змішаного програмування методом відтинання площинами (методом Ґоморі).

Тому розроблені спеціальні методи розв’язання цілочислових задач, серед яких можна виділити два напрямки:

·               метод відтинання площинами;

·               комбінаторні методи.

Метод відтинання площинами полягає в побудові додаткових обмежень і застосуванні симплексного методу.

Відповідно до одного з методів відтинання площинами, відомого як метод Ґоморі, перший етап розв’язання цілочислових задач не відрізняється від звичайного розрахунку за симплексним алгоритмом. Якщо серед значень змінних в оптимальному плані є дробові, складається додаткове обмеження, яке відтинає дробову частину розв’язку, але враховує всі інші умови, яким має задовольняти оптимальний план. Це додаткове обмеження приєднується до початкових обмежень задачі, після чого знову застосовується процедура симплексного методу. Процес приєднання додаткових обмежень повторюють до тих пір, поки або буде знайдено цілочисловий оптимальний план, або доведено, що задача не має цілочислового розв’язку. Це може бути у випадку, коли для дробового всі в цьому рядку виявляться цілими.

Алгоритм Ґоморі дозволяє визначити оптимальний цілочисловий розв’язок за скінченну кількість кроків. Недоліком методу Ґоморі є вимога цілочисельності для всіх змінних: як основних (що позначають одиниці продукції), так і додаткових (що позначають обсяг невикористаних ресурсів), які можуть набувати й дробових значень.

5.   Комбінаторні методи.

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

При застосуванні методу розгалужень і границь для кожної конкретної задачі перш за все мають бути визначені дві важливі процедури:

1)         розгалуження множини можливих розв’язків;

2)         обчислення нижніх і верхніх оцінок цільової функції.

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

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

Перевагою методу розгалужень і границь є те, що він дозволяє накладати вимогу цілочисельності на будь-яку кількість змінних:

·               при накладанні її на всі змінні, які входять в модель, отримують повністю цілочисловий розв’язок;

·               при накладанні її на частину змінних – частково цілочислову задачу, яку також слід розв’язувати за допомогою методу розгалужень і границь.

Схему розв’язання задач на основі методу розгалужень і границь часто називають прийняттям рішення на дереві можливих варіантів.

В багатьох практичних задачах шукані змінні набувають не будь-яких цілих значень, а лише одне з двох: нуль або одиницю. Такі змінні називають булевими і позначають на відміну від звичайних цілочислових змінних замість . За допомогою булевих змінних розв’язуються різні за змістом задачі, пов’язані з процесом вибору різних варіантів і дискретного програмування.

В загальному вигляді задача вибору варіантів записується так:

;

; (8.2)

.

За допомогою булевих змінних можна накладати додаткові логічні умови зв’язку між варіантами.

В задачах дискретного програмування результатом розв’язання задачі виступають тільки цілі, причому лише певні числа.

Модель задачі розподілу ресурсів з врахуванням вимоги дискретного значення змінних в загальному вигляді записується так:

;

;

; (8.3)

,

де – дискретні значення, яких може набувати змінна .

Система (8.3) відрізняється від звичайної задачі розподілу ресурсів тим, що містить булеві змінні і більшу кількість обмежень.

На практиці до задач з булевими змінними можна звести багато різноманітних задач. Особливо у тих випадках, коли виникає проблема вибору найкращого з набору варіантів.

В цілому задачі з булевими змінними можна розв’язувати:

·          як звичайні задачі цілочислового програмування методом розгалужень і границь (при цьому на кожну змінну накладаються вимоги, що вона має бути в межах і набувати цілих значень: 0 або 1);

·          методом повного (суцільного) перебору.

В загальному випадку кількість обчислювальних операцій при повному переборі варіантів розраховується за формулою:

, (8.4)

де – кількість обмежень;

– кількість змінних.

Рекомендована література: [1; 2; 4; 5; 9; 10; 11].