Постановка задачі

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

Існує доволі широкий клас задач математичного програмування, в економіко-математичних моделях яких одна або кілька змінних мають набувати цілих значень, наприклад, коли йдеться про кількість верстатів у цеху, корів у сільськогосподарських підприємствах тощо, тобто коли така вимога випливає з особливостей технології виробництва. До цілочислового програмування належать також задачі оптимізації, в яких змінні набувають лише двох значень — 0 або 1 (бульові, або бінарні, змінні).

Розглянемо приклад. Інвестиційна компанія може вкласти кошти у три різні підприємства. Ефективність кожного проекту оцінено згідно з тим, що його реалізація можлива за чотирьох умов. Дані про ці проекти наведено в таблиці:

Проект	Змінна	Умови реалізації проектів
y 1	y 2	y 3	y 4
	х 1
	х 2
	х 3
Імовірнісні оцінки реалізації проектів	0,2	0,1	0,4	0,3

Кожна змінна , , може набувати лише двох значень –1 або 0, тобто інвестиційна компанія вкладає або не вкладає кошти у відповідне підприємство.

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

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

, (1)

за умов

, (2)

, (3)

— цілі . (4)

Для знаходження оптимального розв’язку цілочислових задач застосовують спеціальні методи. Найпростішим методом розв’язування цілочислової задачі є знаходження її оптимального роз­в’язку як задачі, що має лише неперервні змінні, з подальшим округленням останніх. Такий підхід часто є виправданим. Нехай, наприклад, у результаті розв’язування задачі про поєднання галузей у сільськогосподарському підприємстві дістали, що воно потребує 1235,6 корів. Округливши це значення корів до 1236, не припустимося значної похибки. Проте в деяких випадках такі спрощення призводять до істотних неточностей. Якщо, скажімо, у разі розв’язування як неперервної задачі про сушильний цех, що може бути обладнаний агрегатами трьох типів, дістали х ₁ = 2,6, х ₂ = 4,3 і х ₃ = 0,7, будь-які округлення недопустимі.

Для знаходження оптимальних планів задач цілочислового програмування застосовують дві основні групи методів:

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

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

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

До цієї групи належать:

а) методи розв’язування повністю цілочислових задач (дробовий алгоритм Гоморі);

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

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

Найпоширенішим у цій групі методів є метод віток і меж.

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

Для розв’язування задач із бульовими змінними застосовують комбіновані методи, причому оскільки змінні є бульовими, то методи пошуку оптимуму значно спрощуються.

Дата добавления: 2014-10-31