__2014_DvojstvennSM+Gomory_ukr_rus_new

Крок 1. Вибір змінної, що виводиться з базису.

Розв’язок ще не допустимий ( s1 = -2). За умовою допустимості за змінну, що виводиться з базису, вибираємо змінну s1 .

Крок 2. Вибір змінної, що вводиться до базису. (табл. 5).

Розв’язок, що є оптимальним і допустимим, відповідає точці С(4/3,4/3).

x2

10

B C

Рис. 1. Графічна ілюстрація процесу розв’язання задачі (8)-(12) (стрілками показано порядок проходження базисних розв’язків)

11

x1 12 .

2.Приведемо його до канонічної форми :

x1 s5 12 .

3.Виразимо всі базисні змінні, що входять до складу обмеження, через небазисні (за оптимальною симплекс-таблиці) :

x1 34 32 s1 13 s2 .

4. Підставимо ці значення в обмеження і після скорочення отримаємо :

задача не має розв’язку.

14

Приклад 4. Нехай до задачі (8)-(12) добавлене додаткове обмеження:

3x1 + 2x2 6.

Розв’язок (4/3,4/3) не задовольняє це обмеження. Для його урахування потрібно

виконати наступні дії.

1. Приведемо обмеження до канонічної форми :

3x1 + 2x2 + s5 = 6.

2. Виразимо всі базисні змінні, що входять до складу обмеження, через небазисні (по оптимальній симплекс-таблиці) :

3. Підставимо ці значення в обмеження і після скорочення отримаємо :

4/3 s1 + 1/3 s2 + s5 = - 2/3 .

4.Не додаючи це обмеження до оптимальної симплекс-таблиці, бачимо, що всі коефіцієнти у лівій частині рівняння додатні, а в правій – від’ємне число. Це означає, що введене обмеження суперечить початковій системі обмежень.

1.5. Завдання до самостійної роботи

Додати до оптимальної симплекс-таблиці додаткове обмеження, згідно зі своїм варіантом (див. табл. 10).

15

Розв’язати ЗЛП. Додати (незалежно одне від іншого) до неї додаткові обмеження та розв’язати розширені задачі. Дати графічну ілюстрацію розв’язання задач.

16

17

является оптимальным (пример Б1).

Рис. 4.

Как видно из рис. 4, оптимальным решением непрерывной задачи (задачи без условий целочисленности) является точка x1 2.5, x2 0 . После округления вниз получаем допустимое решение x1 2, x2 0, z 121. Оптимальным же решением исходной ЗЦЛП является решение x1 0, x2 3, z 150.

(б2) Все возможные комбинации округлений вверх или вниз могут не дать допустимого целочисленного решения (рис. 5).

Рис. 5

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

2.1. Загальна характеристика методів відсікання

Розглянемо задачу цілочислового лінійного програмування (ЗЦЛП):

19

де Z n — множина всіх n-вимірних векторів з цілочисловими компонентами.

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

Рис. 6. Множина допустимих розв’язків ЗЦЛП

Однак, якщо б ми могли додати нові граничні лінії, що з'єднують "зовнішні" цілі точки системи, а після цього взяли за допустиму область всю опуклу множину, обмежену осями і новим контуром (рис. 7), то отримали б нову ЗЛП з наступними властивостями:

1)нова допустима область містить всі цілі точки, які замкнені в первісній допустимій області;

2)кожна вершина нової допустимої області є цілою.

Оскільки оптимальні розв’язки ЗЛП знаходяться серед вершин, то при використанні симплекс-методу нам забезпечена цілочисельність розв’язків цієї задачі і досяжність розв’язку за кінцеву кількість кроків.

В основу методу відсікань покладено заміну розв’язку задачі (13) - (16) деякою

20