__2014_DvojstvennSM+Gomory_ukr_rus_new

МІНІСТЕРСТВО ОСВІТИ І НАУКИ УКРАЇНИ НАЦІОНАЛЬНИЙ ТЕХНІЧНИЙ УНІВЕРСИТЕТ УКРАЇНИ «КИЇВСЬКИЙ ПОЛIТЕХНIЧНИЙ ІНСТИТУТ»

ДВОЇСТИЙ СИМПЛЕКС-МЕТОД. АЛГОРИТМ ГОМОРІ

МЕТОДИЧНI ВКАЗIВКИ

до самостійної роботи

з дисциплiни «Математичні методи дослідження операцій»

Київ 2010

Двоїстий симплекс-метод. Алгоритм Гоморі. Методичні вказівки до самостійної роботи з дисциплiни «Математичні методи дослідження операцій» для студентiв спецiальності «Iнформацiйнi управляючi системи та технологiї» / Укл.: О.Г. Жданова. – К.: НТУУ “КПІ”, 2006. – 48 с.

Навчальне видання

МЕТОДИЧНI ВКАЗIВКИ

до самостійної роботи

з дисциплiни «Математичні методи дослідження операцій»

для студентiв спецiальності «Iнформацiйнi управляючi системи та технологiї»

2

називати двоїстим симплекс - методом.

Двоїстий симплекс-метод - це по суті симплекс-метод, що пристосований до двоїстої задачі, але працюючий з перетворюваною прямою задачею.

Нехай пряма перетворювана задача записана в наступному вигляді:

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

1.1. Схема двоїстого симплекс-методу для задачі максимізації ЦФ

Наступна схема містить теоретичне обгрунтування методу [1].

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

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

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

Спочатку розглянемо наступне: коли j–й небазисний стовпчик замінює q–

4

й базисний, тоді після застосування перетворень Гауса відносна оцінка q–го

вектора d N , як і раніше, були невід’ємні ( 0) (виконувалась умова оптимальності),

знаменник повинен бути від’ємним .

Визначимо коефіцієнт за формулою:

і нехай мінімум досягається при j = p.

Якщо взяти більше значення параметра , ніж те, яке дає (7), наприклад значення, яке відповідає j = r , і якщо ( xN )r ввести у базис, то в новому розв’язку одержимо

Якщо у рядку, що відповідає змінній, яка виводиться, нема жодного qj 0

для j, які відповідають небазисним змінним (ознака відсутності допустимих розв’язків), то СТОП, пряма задача не має допустимих розв’язків.

У протилежному випадку перейти на крок 3.

Крок 3. Перехід до нового ДБР

За допомогою елементарних перетворень Гауcа виконується операція заміщення (xB )q на (xN ) p . Перехід на крок 1.

Схема двоїстого симплекс-методу для задачі мінімізації ЦФ

5

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

Коефіцієнт визначається за формулою:

(як і раніше розглядаються тільки відношення з від’ємним знаменником)

Ознака відсутності допустимих розв’язків та ж: у рядку, що відповідає змінній, яка виводиться, немає жодного qj 0 для j, які відповідають небазисним змінним.

З урахуванням (7) и (7а) можна записати єдине (для задач максимізації та мінімізації) правило вибору ведучого стовпчика:

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

У табл. 1 наведена порівняльна характеристика прямого і двоїстого симплекс-методів. Відзначимо, що між цими методами спостерігається симетрія.

6

1.2.Сфера застосування двоїстого симплекс-методу

1.Розв’язок ЗЛП безпосередньо. Двоїстий симплекс-метод може безпосередньо застосовуватись для розв’язання тільки певного класу задач. В цих задачах знаки коефіцієнтів цільової функції та знаки обмежень не можуть бути довільними.

7

1.1.Значення коефіцієнтів цільової функції:

a)якщо цільова функція мінімізується, то усі коефіцієнти цільової функції

повинні бути невід’ємними1: cj 0;

б) якщо цільова функція максимізується, то усі коефіцієнти цільової функції повинні бути недодатними2: cj 0.

1.2.Знаки обмежень. Обмеження початкової ЗЛП з невід’ємними компонен-

тами вектора b мають лише знаки " " і " " (але не всі одночасно типу " ").

2.Розв’язок ЗЛП у випадках, коли після отримання оптимального розв’язку

взадачу вводиться нове (додаткове) обмеження (найбільш важлива сфера застосування).

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

Параметричне програмування – це метод знаходження того, як зміниться розв’язок задачі зміною або вектора коефіцієнтів ЦФ, або вектора обмежень [1].

1.3. Приклад застосування двоїстого симплекс-методу

1У випадку, коли не усі коефіцієнти цільової функції невід’ємні можна застосовувати метод штучних обмежень (аналог М-методу, що використовує штучні змінні) [4].

2У випадку, коли не усі коефіцієнти цільової функції недодатні можна застосовувати метод штучних обмежень [4].

8

змінну s2 .

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

За умовою оптимальності змінна, що вводиться у базис, вибирається з небазисних таким чином: обчислюються відношення коефіцієнтів лівої частини z-рівняння до відповідних коефіцієнтів рівняння, відповідної змінної, що виводиться. Відношення з додатними або нульовими значеннями знаменника не враховуються. У задачі на min змінній, що вводиться, повинне відповідати найменше з вказанних співвідношень. У задачі на max вибираємо відношення, найменше за абсолютною величиною (табл. 3).

= min{1,1/2}=1/2, тобто вводити до базису будемо змінну x2 .

Крок 3. Виконаємо операцію заміщення, використовуючи перетворення Жордана-Гауса (тобто звичайні симплекс-перетворення) (табл. 4).

Таблиця 4

Новий базисний розв’язок відповідає точці В(2,0) (див. рис. 1).

Ітерація 2.

10