__2014_DvojstvennSM+Gomory_ukr_rus_new

Оскільки ми говоримо про повністю цілочислову задачу, то перед її

зведенням до канонічної форми ми повинні перетворити задачу таким чином,

щоб усі її коефіцієнти aij, bi, cj були цілими.

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

Розглянемо довільне лінійне обмеження, яке можна отримати за допомогою елементарних перетворень над лінійними обмеженнями (18). Тоді, якщо деякий розв’язок задовольняє (18) - (19), то він повинен також задовольнити і це рівняння. Нехай вираз

визначає саме таке обмеження.

Позначимо символом [ ] цілу частину дійсного числа - найбільше ціле,

що менше або дорівює . За визначенням [ ] . Наприклад:

Далі, оскільки сума в лівій частині (21) повинна бути цілочисельною, (21) можна посилити таким чином:

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

Визначимо fij та fi - дробові частини чисел ij і i - тотожностями:

За визначенням дробові частини є не від’ємним. Наприклад:

дробова частина числа 12/5 дорівнює 2/5;

дробова частина числа –12/5 складає 3/5;

дробова частина числа 1/3 дорівнює 1/3;

дробова частина числа –1/3 дорівнює 2/3;

дробова частина числа 3 дорівнює 0;

дробова частина числа -3 дорівнює 0.

Віднімаючи почленно з рівняння (23) рівняння (20), отримаємо обмеження, що складається лише з дробових частин:

Це перетворення є елементарним, а це означає, що множина допустимих розв’язків системи (18), (19), (23) збігається з множиною допустимих розв’язків системи (18), (19), (24).

Рівняння (24) називається рівнянням відсікання, а рівняння (20), за яким побудували рівняння відсікання, зветься породжуючим рівнянням. Задача (17) – (19), (24) з додатковим обмеженням-відсіканням називається розширеною.

2.3. Схема алгоритму Гоморі

23

Крок 1. Знайти оптимальний розв’язок послабленої задачі.

Крок 2. Припинити обчислення, якщо поточний розв’язок ЗЛП є цілочисловим. В

іншому випадку вибрати дробову базисну змінну xk . Скласти рівняння відсікання за рівнянням, що містить цю базисну змінну в поточному оптимальному розв’язку ЗЛП. Тобто, якщо i -й рядок симплекс-таблиці має вигляд:

змінної xk ), то додаткове обмеження має вигляд:

Крок 3. Додати до вхідної задачі це рівняння-відсікання; знайти за допомогою двоїстого симплекс-методу3 оптимальний розв’язок розширеної задачі та повернутися на крок 2.

Алгоритм Гоморі має наступні особливості:

1. Загальна кількість обмежень розширеної задачі не може перевищувати кількість n змінних вхідної задачі у канонічній формі. Якщо розширена задача містить більш ніж n обмежень, то одна або декілька вільних змінних s, зазначених відсіканням Гоморі, повинні стати базисними. У цьому разі відповідні рівності стають надлишковими і можуть бути виключені з таблиці (приклад 5).

Отже, якщо остаточна змінна s рівняння-відсікання на кроці 3 деякої ітераціі знову увійшла у базис, то перед кроком 2 (до того, як виконується оптимізація) потрібно викреслити рядок і стовпець, що містять цю змінну.

2. Якщо у стовпці β вільних членів (стовпці "Розв’язок") є від’ємний коефіцієнт, і при цьому всі коефіцієнти відповідного рядка є невід’ємними, то ЗЦЛП буде нерозв’язною (не має допустимих розв’язків) (приклад 6).

2.4. Эффективность отсечения Гомори

[4] Вид неравенства, определяющего некоторое отсечение, зависит от

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

24

выбора производящей строки. Одна и та же таблица порождает различные отсечения. Возникает естественный вопрос: какое из них является наиболее эффективным? Эффективность отсечения характеризуется размерами области, отсекаемой от многогранника допустимых решений (рис. 8). Математически это выражается следующим образом.

(*)

(**)

Рис. 8.

Пусть по некоторой строке построено такое ограничение-отсечение:

( fij )x j s fi

причем, по крайней мере, в одном случае выполняется строгое неравенство.

Например,

25

выбрать более эффективное. Графическая иллюстрация этой ситуации дана на рис. 9.

Рис. 9 Использование данного определения эффективности отсечения связано с

существенными трудностями вычислительного характера. Поэтому были разработаны следующие правила, отражающие смысл этого определения.

–Правило 2. В качестве производящей выбирается та строка, которой соответствует

– Правило 2. В качестве производящей выбирается та строка, которой соответствует

max fi .

i

Второе правило теснее связано с определением эффективности. Использование этих двух правил не всегда обеспечивает введение наиболее эффективного отсечения.

26

Розглянемо початкову симплекс-таблицю послабленної задачі (25а) - (28а) :

Після двох ітерацій симплекс-методу отримаємо оптимальну симплекс-таблицю послабленої задачі :

Через те, що отриманий розв’язок не є цілочисловим, слід поширити дану задачу шляхом введення відсікання. У даному випадку z -рядкок співпадає з x2 -

рядком, значить, відсікання, побудуване за x2 -рядком співпаде з відсіканням за z -

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

27

x2 14 x3 14 x4 32 .

Виділимо цілі і дробові частини коефіцієнтів:

Сформуємо за цим обмеженням рівняння-відсікання Гоморі:

І введемо його в оптимальну симплекс-таблицю послабленої задачі (табл. 13). Таблиця 13

Застосувавши двоїстий симплекс-метод, отримуємо оптимальне розв’язок задачі

(25а) - (28а), (30) (табл. 14)

Розв’язок знову не задовольняє обмеження цілочисельності (29). Тому продовжимо процес побудови відсікань за допомогою алгоритму Гоморі. У

поточному розв’язку тільки змінна x1 не ціла. За таблицею 14 x1 - рядок має вигляд:

28

x1 13 x4 23 s1 23 .

Виділимо цілі і дробові частини коефіцієнтів:

Відсікання, побудоване за цим обмеженням, має вигляд:

23 x4 23 s1 s2 23 .

Додамо його до останньої симплекс-таблиці та знову застосуємо двоїстий симплексметод (табл. 15).

Отримали оптимальний розв’язок початкової задачі: z=1, x1=1, x2=1.

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

29

1.Перше рівняння-відсікання має вигляд: 14 x3 14 x4 s1 12 .

14 (6 3x1 2x2 ) 14 (3x1 2x2 ) s1 12 .

Після зведення подібних отримаємо:

Рис.10. Графічна ілюстрація процесу розв’язання ЗЦЛП з прикладу 5

2.Друге рівняння-відсікання має вигляд:

23 x4 23 s1 s2 23 .

Зпершого рівняння-відсікання виразимо змінну s1 через x3 та x4 :

30