Аналіз коефіцієнтів цільової функції (стр. 3 )

М

1

С

О 1 х1

рис.5.2.

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

5.3. Загальна характеристика методів розв’язування цілочислових задач лінійного програмування

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

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

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

· наближені методи.

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

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

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

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

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

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

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

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

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

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

До наближених методів відносяться: метод локальної оптимізації (метод вектора спаду); модифікації точних методів; методи випадкового пошуку та інш.

5.4. Методи відтинання. Метод Гоморі

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

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

x2

x1

Рис.5.3.

Слід відмітити, що визначення правила для реалізації ідеї Данціга щодо формування додаткового обмеження виявилось досить складним завданням і першим кому вдалось успішно реалізувати цю ідею був Гоморі.

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

Нехай маємо задачу цілочислового програмування:

(5.5)

за умов

, (5.6)

, (5.7)

— цілі . (5.8)

Припустимо, що параметри – цілі числа.

Не враховуючи умови цілочисловості знаходимо розв’язок задачі (5.5)-(5.7) симплексним методом. Нехай розв’язок існує і міститься в наступній симплексній таблиці.

Базис	Сб	План	c1	c1	...	cm	cm+1	...	cn
			х1	х2	...	хm	хm+1	...	хn
х1	c1	b1	1	0	...	0	a1m+1	...	a1n
х2	c1	b2	0	1	...	0	a2m+1	...	a2n
...	...	...	...	...	...	...	...	...	...
хm	cm	bm	0	0	...	1	amm+1	...	amn

Змінні – базисні, а – вільні. Оптимальний розв’язок задачі: . Якщо – цілі числа, то отриманий розв’язок є цілочисловим оптимальним розв’язком задачі (5.5)-(5.8). Інакше існує хоча б одне з чисел, наприклад, – дробове, отже необхідно побудувати правильне відтинання, що виключає неціле значення .

Розглянемо довільний оптимальний план задачі (5.5)-(5.7). Виразимо в даному плані базисну змінну через вільні: