3.4.2. Метод декомпозиції Данцига-Вульфа

Розглянемо КЗЛП:

(3.4.1)

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

, ,

, .

Задача (3.4.1) набуває вигляду

(3.4.2)

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

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

, (3.4.3)

де - вершини многогранника, , - направляючі вектори необмежених ребер, ,

Якщо многогранник обмежений, тоді .

Нехай множина діагонального блоку – непорожній, замкнений та опуклий многогранник. Тоді

,

де - вершини многогранника ,

Точка , якщо задовольняє також умовам блока-зв’язці, тобто якщо

, (3.4.4)

, .

Розв’язок задачі (3.4.2) повинен максимізувати цільову функцію. Таким чином задача (3.4.2) зводиться до знаходження таких , при яких функція

досягає максимального значення за умови (3.4.4).

Щоб підкреслити, що є змінними задачі, введемо наступні позначення:

, (3.4.5)

,

. (3.4.6)

Задача (3.4.2) еквівалентна наступній КЗЛП:

(3.4.7)

Якщо оптимальний розв’язок задачі (3.4.7), тоді - оптимальний розв’язок задачі (3.4.2).

Нехай

, , (3.4.8)

тоді задачу (3.4.7) перепишемо так:

(3.4.9)

Задачу (3.4.9) будемо називати головною.

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

Кількість змінних головної задачі дорівнює кількості вершин многогранника .

Приклад 3.6. Побудувати головну задачу до наступної:

,

,

,

,

.

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

Знайдемо геометрично вершини многокутника діагонального блоку (рис. 3.2): та .

Рис.3.2.

За формулою (3.4.5) вектор . За формулою (3.4.6) .

Згідно до (3.4.8): .

Таким чином головна задача наступна:

,

,

,

.

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

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

Розглянемо два випадки:

1. головна задача має канонічну форму

2. головна задача має вид

і для приведення її до канонічної форми вводяться додаткові змінні .

Тоді крім векторів

,

в задачі з’являються вектори

, , ..., .

Тепер головна задача у канонічній формі має вид

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

З модифікованого симплекс-методу оцінки визначаються за формулою (1.7.5), яка для головної задачі (3.4.6) набуває виду:

,

де

,

- обернена матриця до базисної.

Нехай . Так як остання координата векторів дорівнює одиниці, тоді для всіх оцінок справедливі формули

, . (3.4.10)

Так як небазисні вектори невідомі, тоді скористатися формулою (3.4.10) ми не зможемо. Автори методу запропонували знайти мінімальну з оцінок і якщо вона буде невід’ємною, тоді даний базис є оптимальним.

Кожна оцінка згідно (3.4.10) зв’язана з вершиною многогранника , тобто , , тоді

, . (3.4.11)

Щоб підібрати вершину многогранника , для якої оцінка досягатиме найменшого значення необхідно розв’язати наступну допоміжну задачу:

(3.4.12)

Нехай - оптимальний розв’язок задачі (3.4.12). Як відомо з теорії лінійного програмування буде однією з вершин многогранника . Якщо

, (3.4.13)

тоді базис, що перевіряється, оптимальний і відповідний йому опорний план оптимальний.

Якщо

,

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

Якщо перейти в задачі (3.4.12) до цільової функції на максимум, тоді

, (3.4.14)

умову (3.4.13) переписати як

, (3.4.15)

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

Задачу (3.4.14) будемо називати підзадачею діагонального блоку.

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

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

- - те місце,

коефіцієнти цільової функції при додаткових змінних дорівнюють нулю, тому

, .

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

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

,

де - оптимальний розв’язок задачі (3.4.14), а якщо , тоді вводиться додатковий вектор

- -те місце.

Розглянемо загальний випадок, коли многогранник необмежений, тоді в (3.4.3) не всі . Підставляючи вираз (3.4.3) у цільову функцію та блок-зв’язку, отримаємо задачу

,

,

,

.

Нехай ,

,

тоді приходимо до головної задачі

,

,

,

.

Якщо позначимо

,

де відповідає вершині , , відповідає необмеженому ребру , , то головна задача приймає остаточний вид

(3.4.16)

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

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

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

Якщо серед компонент вектора є додатні, тоді вводимо до базису вектор замість одного з базисних векторів за правилами симплекс-методу. Новий базис знов перевіряємо на оптимальність.

Розглянемо КЗЛП, в якій буде два діагональних блоки. Випадок більшого числа блоків принципово не відрізняється від цього випадку.

Нехай КЗЛП має вид

,

,

................................................................................

, (3.4.17)

,

.................................................................................

,

,

.................................................................................

,

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

Коефіцієнти цільової функції при змінних та розіб’ємо на два вектори , .

Матрицю , яка відповідає блоку-зв’язці, розіб’ємо на дві матриці та :

, ,

вільні члени блоку-зв’язки визначимо .

Для матриць діагональних блоків та векторів їх вільних членів приймемо позначення:

, ,

, .

Тоді задача (3.4.17) має вид:

,

,

.

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

через - другого блоку

,

.

Представимо , як

, (3.4.18)

де вершини многогранника , , .

Аналогічно :

, (3.4.19)

де , вершина многогранника , , .

Підставимо вирази для та у блок-зв’язку цільову функцію задачі (3.4.14) та отримаємо головну задачу:

,

,

, ,

де ,

,

,

.

Якщо позначити , , ,

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

,

(3.4.20)

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

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

.

Нехай оптимальний розв’язок підзадачі, що відповідає першому діагональному блоку

(3.4.21)

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

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

(3.4.22)

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

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

Приклад 3.7. Розглянемо задачу планування двох підприємств концерна. На першому виробляється по два види продукції А та В, прибуток з кожної одиниці якої дорівнює 3 грн. та 1 грн. На другому підприємстві виробляються продукція видів С та Д, яка приносить прибуток відповідно 2 грн. та 1 грн. з кожної одиниці. Обсяг виробництва на кожному з підприємств не перевищує 4 ум.од. продукції, а попит на продукцію всіх видів не перевищує 6 ум.од. Знайти оптимальний план виробництва продукції на кожному з підприємств концерну.

Для побудови моделі введемо змінні - обсяг виробництва продукції виду . Цільовою функцією задачі буде максимізація прибутку концерну:

, (3.4.23)

за умови загального попиту

(3.4.24)

та можливостей підприємств

, (3.4.25)

, (3.4.26)

а також

. (3.4.27)

Задачу (3.4.23)-(3.4.27) можна розглядати як задачу з блочно-діагональною структурою, де перше обмеження (3.4.24) – блок-зв’язка, а (3.4.25) та (3.4.26) – два діагональні блоки. До першого блоку входять змінні та , до другого - та .

Побудуємо головну задачу до задачі (3.4.23)-(3.4.27): , матриця блоку-зв’язки , відповідно та , матриця першого блоку , відповідно та матриця другого блоку . - множина невід’ємних розв’язків, які задовольняють умовам першого блоку:

,

- другого блоку:

.

Визначимо тепер базис головної задачі. Так як блок-зв’язка є нерівністю виду „ ”, то такий же вид буде мати перше обмеження головної задачі. При приведенні головної задачі до канонічного виду з’явиться додаткова змінна, якій буде відповідати вектор .

Очевидно, що однією з вершин множини є , множини - . Цим вершинам відповідають вектори

та .

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

.

Обчислимо вектор для цього базису

.

Тоді . Складаємо та розв’язуємо під задачу першого діагонального блоку виду (3.4.2.1):

,

,

.

Оптимальний розв’язок: . Тому початковий базис, який складається з векторів та не є оптимальний.

Перша ітерація. Так як різниця є мінімальною, то в базис вводимо вектор

.

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

.

Знайдемо

та обчислимо

.

Тоді .

Складаємо та розв’язуємо наступну під задачу першого діагонального блоку виду (3.4.21):

,

,

,

оптимальним розв’язком якої є . Базис оптимальний.

Складаємо та розв’язуємо під задачу другого діагонального блоку виду (3.4.22):

,

,

.

Її оптимальним розв’язком є вектор , . Тому попередній базис, який складався з векторів та не є оптимальним.

Друга ітерація. Вводимо до базису вектор

.

Відповідно .

Щоб знайти вектор, який треба вивести з базису, розкладемо вектори та за базисом:

,

,

, тому виводимо з базису вектор, який стоїть на першому місці у базисі, тобто . Новий базис утворюють вектори

та .

Матриця, складена з базисних векторів, наступна:

,

обернена до неї має вид:

.

Знаходимо вектори

,

.

Складаємо та розв’язуємо наступну під задачу другого діагонального блоку:

.

Оптимальним розв’язком цієї задачі , де

.

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

.

Значить в оптимальному плані головної задачі ненульові компоненти наступні:

.

Використовуючи формули (3.4.18) та (3.4.19), знаходимо оптимальний план початкової задачі (3.4.23)-(3.4.27):

,

.

Так, оптимальний розв’язок задачі (3.4.23)-(3.4.27): , тобто максимальний прибуток 16 грн. буде оптимальний, якщо на першому підприємстві буде вироблятися тільки продукція виду А в кількості 4 ум.од., на другому – тільки 2 ум.од. продукції виду С.