На головну

Двоетапний симплекс-метод

  1. Стандартний алгоритм симплекс-методу
  2. Алгоритм симплекс-методу
  3. Алгоритм симплекс-методу
  4. Опис симплекс-методу
  5. Ознака оптимальності. Основні етапи симплекс-методу
  6. Приклад рішення задачі лінійного програмування симплекс-методом

Метод штучного базису

Як було розглянуто в розділі 3, для застосування алгоритму симплекс-методу необхідно почати рішення задачі лінійного програмування з деякого опорного плану. Щоб цей план можна було побудувати, завдання повинна бути записана в канонічній формі з невід'ємними вільними членами і мати повний набір базисних змінних.

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

Розглянемо одну з модифікацій методу штучного базису - двоетапний симплекс-метод.

Двоетапний симплекс-метод

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

У цьому випадку, для того щоб застосувати до неї симплекс-метод, використовується метод штучного базису. Вводять m невід'ємних змінних у1, у2,. . . . уm, По одній в кожне рівняння. Ці змінні називають штучними, І складають розширену задачу, Що має такий вигляд *:

У цьому завданні є m одиничних стовпців при штучних змінних, з яких і складається штучний базис.

Лемма.Завдання (19) завжди можна вирішити.

Доведення. Очевидно, що область допустимих планів (ОДП) цього завдання не може бути порожня: в наявності хоча б один допустимий план - той опорний план, який відповідає початковому базису. Справді, план Х = (х1, x2, ..., Xn, y1, y2, ..., Ym) = (0, 0, ..., 0, b1, b2, ..., Bm) I ОДП завдання (19).

Цільова функція не може бути не обмежена, тому що не може бути менше нуля (вона являє собою суму невід'ємних змінних).

Лема доведена.

нехай U *  = (X1 * ,. . . xn * , y1 * ,. . . ym * ) - Оптимальний план задачі (19).

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

1).

Тобто якщо оптимум розширеної задачі позитивний (що еквівалентно твердженням про те, що хоча б одна штучна змінна в плані U *  позитивна), то ОДП вихідної задачі порожня.

2).

Іншими словами, якщо в U *  всі штучні змінні рівні 0, то план Х(0), Складений з компонент xj *  плану U * , Є допустимим для вихідної завдання.

Доведення першій частині теореми здійснюється від противного. Припустимо, що існує уi * > 0, і ОДП завдання (18) при цьому не порожня, тобто існує план X '= (x1',. . . . xn') I ОДП завдання (18). Розглянемо план U '= (x1',. . . xn',  ) (В ньому перші n компонент взяті з плану X ', а всі штучні змінні дорівнюють нулю). U'I ОДП завдання (19), що легко перевірити підстановкою його в систему обмежень цієї задачі:

Остання система істинна, так як X'I ОДП завдання (18).

На плані U 'цільова функція завдання (19) Z' = 0 (сума нульових штучних змінних). Однак за умовою теореми, оптимум завдання (19) позитивний, тобто більше Z '. Так як завдання (19) на мінімум, план U * не може бути оптимальним, якщо є допустимий план, на якому значення цільової функції менше. Ми прийшли до протиріччя, перша частина теореми доведена.

Друга частина теореми доводиться безпосередньо підстановкою U * U *  = (X1 * ,. . . xn * , 0,. . . 0) в обмеження завдання (19). Так як цей план допустимий для завдання (19), рівняння системи звертаються в справжні рівності. Вони в точності збігаються з рівняннями системи (18) при підстановці в неї плану Х(0) = (X1 * ,. . . xn * ) (І обмеження невід'ємності також виконуються):

З виконання обмежень завдання (19) слід виконання обмежень завдання (18): отже, план Х(0)- Допустимий для завдання (18).

Теорема доведена.

Сенс доведеної теореми в тому, що вирішити задачу лінійного програмування буде можливо лише в тому випадку, якщо вдасться позбутися від усіх штучних змінних *. Справді, ці штучні змінні при побудові розширеної задачі були «втиснуті» між лівою і правою частинами рівнянь. Насправді ліві частини обмежень були РІВНІ правим, ніякої різниці між ними бути не повинно. І завдання буде розв'язано лише в тому випадку, якщо цей «зазор» - штучну змінну - вдасться звести до нуля у всіх обмеженнях.

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

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

1-й етап. Будується розширена задача, яку вирішують звичайним симплекс-методом.

2-й етап. Якщо оптимум розширеної задачі позитивний, робиться висновок про нерозв'язності вихідної задачі, так як її ОДП = ?. Якщо він дорівнює нулю, то переходять до вирішення симплекс-методом початкового завдання, починаючи з опорного плану, відповідного значенням змінних xj * .

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

При вирішенні завдань доцільно дотримуватися наступних рекомендацій:

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

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

в) Після виходу штучних змінних з базису перерахунок відповідних цим змінним стовпців симплексной таблиці не є обов'язковим.




ОСНОВНІ ПРИЧИНИ ЗАБРУДНЕННЯ ВОДНИХ ОБ'ЄКТІВ | Приклад рішення задачі методом штучного базису
© um.co.ua - учбові матеріали та реферати