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

Певну групу задач математичного програмування складають задачі дискретного програмування, в яких необхідно знайти максимум цільової функції Z, визначений на деякій дискретній множині P = {p₁, p₂, … p_n}. Для розв’язання такої задачі треба визначити елемент р* Р такий, щоб

. (1.5.1)

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

х_j – цілі, j  J. (1.5.2)

Якщо множина індексів J містить всі j = 1…n, то ми будемо мати справу з повністю цілочисловою задачею. В ній елементи множини Р є цілочислові точки многогранника допустимих розв’язків Х задачі лінійного програмування. Якщо вимога цілочисельності поширюється не на всі j = 1…n, то матимемо частково цілочислову задачу лінійного програмування.

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

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

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

Відомі методи такого пошуку поділяють на дві групи:

1. всі розв’язки (1.5.2) є цілочисловими;

2. лише частина розв’язків задачі цілочислова, а решта – довільні.

Метод Гоморрі. Розглянемо детальніше шлях пошуку розв’язку задачі цілочислового програмування з усіма цілочисловими змінними методом відтинання площин. Для цього попередньо введемо такі означення.

Означення 1.

Цілою частиною числа а називають найбільше ціле число, яке менше або дорівнює йому (позначення – [a]):

Рис.1.4.

Означення 2.

Дробовою частиною числа а називають різницю між числом а та його цілою частиною (позначення – f(a)):

. (1.5.3)

Очевидно, що f(a)  0, причому f(a) = 0 лише тоді, коли а – ціле число. В теорії чисел для дробової частини числа виведені такі властивості:

, (1.5.4)

якщо n  0 – ціле, то . (1.5.5)

Для обмежень задачі (1.5.2) наведені властивості дають змогу записати нерівність

, (1.5.6)

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

Алгоритм Гоморрі можна записати за допомогою кількох кроків.

Крок 1. Знаходимо розв’язок задачі (1.5.2) без умови цілочисельності.

Крок 2. Якщо оптимальний план цілочисловий, то задача розв’язана. У протилежному випадку вибираємо базисну змінну з найбільшою дробовою частиною і за обмеженням цієї базисної невідомої складаємо нерівність Гоморрі.

Крок 3. До обмежень задачі додаємо обмеження з кроку 2, тобто нерівність Гоморрі. Розв’язуємо розширену задачу і повертаємось до кроку 1. Процес повторюємо доти, доки розв’язок не буде цілочисловим або симплекс-таблиці не покажуть, що задача не має розв’язку.

Рис.1.5.

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

Якщо спробувати побудувати блок-схему методу Гоморрі, то вона матиме такий вигляд:

Рис.1.6.

Без умови цілочисельності значення цільової функції Z_max міститься у т. А. При виконанні умови цілочисельності Z_max зміщується у точку В.

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

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

Нехай ми маємо m постачальників однорідної продукції з об’ємом виробництва a_i у кожного (i = 1…m), а також n споживачів з потребами b_j кожного (j = 1…n). Через x_ij позначимо об’єм поставок від постачальника і до споживача j, через C_ij – вартість перевезення одиниці продукції від і до j. Однак, на відміну від звичайної транспортної задачі, ми беремо до уваги, що розглядаються не існуючі підприємства, а такі, що проектуються до будівництва. В результаті розв’язування задачі необхідно визначити, які з цих підприємств мають бути збудовані, щоб сумарні витрати на будівництво і транспортування були мінімальними.

Позначимо також через f_i приведені витрати на будівництво і-того підприємства потужністю a_i, y_i – цілочислову змінну, яка дорівнює одиниці, якщо і-те підприємство будується, і нулю – в протилежному випадку.

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

. (1.5.7)

Умова задоволення потреб споживачів залишається такою ж, як і у транспортній задачі, оскільки їх підбір і попит b_j вважаємо заданими:

. (1.5.8)

Для того, щоб існував розв’язок задачі, зрозуміло, має бути виконана умова

. (1.5.9)

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

, (1.5.10)

, (1.5.11)

, (1.5.12)

; у_і = 0 або 1. (5.13)

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

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

, (1.5.14)

, (1.5.15)

, (1.5.16)

або 1. (1.5.17)

Тут N – кількість підприємств; k – номер підприємства; j – номер варіанту будівництва чи реконструкції підприємства; m_k – кількість варіантів будівництва чи реконструкції підприємства; i – вид продукції; L – кількість видів продукції; – об’єм випуску і-тої продукції на k–тому підприємстві при j–тому варіанті; bⁱ – потреба в і-тому виді продукції; C_jk – приведені витрати (поточні й капітальні), що відповідають j–тому варіанту розвитку k–того підприємства; x_jk = 1, якщо для k–того підприємства вибирають j–тий варіант, x_jk = 0 в протилежному випадку.

Двоїстий симплексний метод. Можна переконатись, що при розв’язуванні цілочислових задач при використанні звичайного симплекс-методу виникають певні проблеми. Симплексний метод застосовують для розв’язання задач з не-від’ємними правими частинами b_i системи обмежень і довільними за знаком _j. Іноді буває легше знайти базис, що задовольняє критерій оптимальності (всі _j  0), але не задовольняє критерій допустимості, оскільки не всі b_i  0. При розв’язуванні таких задач використовують так званий двоїстий симплекс-метод. За його допомогою розв’язують задачі лінійного програмування вигляду

, (1.5.18)

, (1.5.19)

, (1.5.20)

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

1. Усі b_i  0. Тоді ми маємо не лише допустимий, але й оптимальний план задачі, оскільки за припущенням усі _j  0.

2. У стовпчику вільних членів є елемент b_i  0, а усі коефіцієнти і-того рядка a_ij  0. Тоді задача не має розв’язку, оскільки система несумісна.

3. Існує рядок r такий, що b_r < 0 i a_rj < 0 принаймні для одного j. Нехай s  1…n – такий номер стовпчика, що a_rs < 0 і

.

Тоді жорданове перетворення з ключовим елементом a_rs приводить до еквівалентної задачі, в якій, по-перше, _j  0, а, по-друге, значення цільової функції не збільшується.

Алгоритм застосування двоїстого симплекс-методу розглянемо на прикладі розв’язування задачі у двоїстій базисній формі.

Приклад. Розв’язати задачу

,

.

За умови, що система обмежень містить одиничний базис, перевіряємо знаки елементів стовпчика вільних членів. Якщо усі b_i  0, і при цьому усі _j  0, то базисний розв’язок і значення цільової функції є оптимальними.

Запишемо нульовий (оціночний) рядок задачі

.

Всі оцінки _j  0, але права частина системи обмежень містить від’ємні числа –8 і –4. Тому переходимо до наступного кроку.

Будуємо початкову симплекс-таблицю.

Базисні змінні	Вільні члени	х1	х2	х3	х4	х5	х6	х7
х5	–8	–3	–2	1	–5	1	0	0
х6	–4	0	1	3	–6	0	1	0
х7	0	–2	0	–1	1	0	0	1
Z1	0	4	3	10	5	0	0	0

Серед від’ємних чисел b_i вибираємо найбільше за абсолютною величиною b_r, а відповідний рядок називаємо ключовим. В нашому випадку це рядок х₅.

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

Складаємо від’ємні відношення додатних оцінок _j до відповідних від’ємних елементів a_rj ключового рядка і вибираємо серед них найбільше відношення

Стовпчик s буде ключовим, відповідно, a_rs буде ключовим елементом.

Для нашого прикладу складемо від’ємні відношення:

.

Виконуємо жорданове перетворення з ключовим елементом –5. Одержуємо першу симплексну таблицю.

Симплекс-таблиця 1.

Базисні змінні	Вільні члени	х1	х2	х3	х4	х5	х6	х7
х4	8/5	3/5	2/5	–1/5	1	–1/5	0	0
х6	25/5	18/5	17/5	9/5	0	–6/5	1	0
х7	–8/5	-13/5	–2/5	–4/5	0	1/5	0	1
Z1	–8	1	1	11	0	1	0	0

Оскільки в симплекс-таблиці 1 умова оптимальності не виконується, застосовуємо до неї знову жорданове перетворення, вибравши за ключовий елемент –13/5, і отримуємо другу симплекс-таблицю.

Симплекс-таблиця 2.

Базисні змінні	Вільні члени	х1	х2	х3	х4	х5	х6	х7
х4	16/13	0	4/13	-5/13	1	-2/13	0	3/13
х6	44/13	0	37/13	9/35	0	-12/13	1	18/13
х1	8/13	1	2/13	2/13	0	-1/13	0	-5/13
Z1	–112/13	0	11/13	139/13	0	14/13	0	5/13

Симплекс-таблиця 2 задає оптимальний розв’язок задачі , і значення цільової функції в максимумі .

Двоїстий симплекс-метод зручно використовувати і при розв’язуванні задач, що мають одиничний базис, але не належать до задач у базисній чи двоїстій базисній формі, оскільки мають від’ємні елементи як серед b_i, так і серед _j одночасно. Розв’язання такої задачі складається з двох етапів. Спочатку за допомогою двоїстого симплекс-методу виключаються всі b_i < 0, а потім оптимальний план знаходять звичайним симплексним методом. Потрібно лише при складанні симплексних відношень використати відношення

.