Page 166 - 5637

4. Опуклі, увігнуті задачі цілочислового програмування, завдання стохастичного

цілочисельного програмування, визначаються відповідною структурою критерію (∙).

і обмежень ( = 1, … , ).

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

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

відноситься лише до частини компонентів оптимізується вектора = { , … , } . Для

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

підмножини – цілочисельних параметрів , … , і безперервних , … , :

, … , ∪ , … , ∶=∶ { , … , }, + = .

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

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

дискретизації параметрів , … , з деяким інтервалом , … , ( > 0,

= 1, … , ). При досить широких припущеннях про структуру функції вирішення

цієї нової задачі сходиться до вирішення вихідної за умови

max → 0. Таким чином, другий підхід полягає в зведенні задач частково

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

зручний для реалізації на ЕОМ і широко застосовується при проведенні практичних

розрахунків.

В даний час в теорії целочисленной оптимізації можна виділити наступні три

основні групи методів: метод відсікань, комбінаторні і наближені (евристичні).

Метод відсікань призначений для вирішення завдань лінійного цілочисельного

програмування. Загальна схема методу відсікань наступна. Спочатку задача (8.1) –

(8.3) вирішується без урахування цілочисельності змінних. Якщо отримане рішення

цілочисельний, то воно є рішенням задачі (8.1) – (8.3). В іншому випадку

(нецілочисельне рішення) до обмежень (8.3) додається нове обмеження, що володіє

тим властивістю, що безліч допустимих рішень нового завдання містить будь

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

попередньої задачі без обмежень цілочисельності. Потім зазначений процес