Лабораторне заняття №16

Тема заняття: Розв’язання цілочислових задач математичного програмування.

Мета: сформувати вміння та навички розв’язання цілочислових задач лінійного програмування методом Гоморі.

Методичні рекомендації: Вивчити лекцію №5 та ознайомиться з наступною літературою [1 с. 242-256], [2 с. 158-165], [3 с. 170-195], [4 с. 175-192].

Постановка завдання:

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

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

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

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

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

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

, (1)

за умов

, (2)

, (3)

— цілі . (4)

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

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

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

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

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

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

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

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

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

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

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

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

Метод Гоморі

Нехай маємо задачу цілочислового програмування (1)—(4). Для її розв’язування можна скористатися ітеративним методом Гоморі. Суть його полягає ось у чому:

1. Знаходять розв’язок послабленої, тобто задачі без вимог цілочисловості змінних — (1)—(3).

Якщо серед елементів умовно-оптимального плану немає дробових чисел, то цей план є оптимальним планом задачі цілочислового програмування (1)—(4).

2. Коли в умовно-оптимальному плані є дробові значення, то вибирається змінна, яка має найбільшу дробову частину. На базі цієї змінної (елементів відповідного рядка останньої симплексної таблиці, в якому вона міститься) будується додаткове обмеження Гоморі:

де символ {} позначає дробову частину числа.

Для визначення дробової частини будь-якого числа від цього числа віднімають цілу його частину — найбільше ціле число, що не перевищує даного. Цілу частину числа позначають символом [ ]. Наприклад,

[1,3] = 1; [–1,3] = –2;

{1,3} = 1,3 – 1 = 0,3; {–1,3} = –1,3 – (–2) =2 – 1,3 = 0,7.

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

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

Приклад1.

Сільськогосподарське підприємство задумало створити сушильний цех на виробничій площі 190 м², маючи для цього 100 тис. грн. і можливість придбати устаткування двох типів А і В. Техніко-економічну інформацію про ці два види устаткування подано в таблиці:

Техніко-економічний показник	Устаткування	Ресурс
А	В
Вартість, тис. грн.
Необхідна виробнича площа, м²
Потужність, тис. грн./рік			—

Розв’язування. Нехай х ₁ і х ₂ — кількість комплектів устаткування відповідно типу А і В.

Запишемо економіко-математичну модель:

і — цілі.

Розв’язуємо задачу, нехтуючи умовою цілочисловості. Остання симплексна таблиця набере вигляду:

Х _баз	С _баз	План
х ₁	х ₂	х ₃	х ₄
х ₁
х ₂

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