Лекція 23

СИМПЛЕКС МЕТОД ВИРІШЕННЯ ЗАДАЧІ ЛІНІЙНОГО ПРОГРАМУВАННЯ

Геометрична інтерпретація, якою ми користувалися для вирішення задач ЛП перестає бути придатною при числі вільних змінних (nm) > 3. Для знаходження рішення задачі в загальному вигляді застосовуються обчислювальні методи. З них найбільш універсальним є так званий симплекс - метод.

Ідея симплекс-методу відносно проста. Нехай у задачі ЛП є n - змінних і m - незалежних лінійних обмежень, заданих у формі рівнянь. Ми знаємо, що оптимальне рішення досягається в одній з опорних точок (вершин ОДР), де принаймні k = n - m з змінних дорівнюють нулю. Виберемо якісь k змінних в якості вільних і висловимо через них інші m базисних змінних:

(23.1)

Подивимося, що буде, якщо покласти всі вільні змінні x₁, x₂,..., x_K рівними нулю: х₁ = 0, х₂ = 0,..., х_К = 0. При цьому ми отримаємо: X_K+1=b_K+1, X_K+2=b_K+2, …, X_n=b_n.Це рішення може бути допустимим і недопустимим. Воно допустимо, якщо всі вільні члени b_К+1, b_К+2, …, b_К+1 ненегативні. Припустимо, що ця умова виконана. Тоді ми отримали опорне рішення. Але чи є воно оптимальним? Щоб перевірити це, висловимо цільову функцію L через вільні змінні x₁, x₂,..., x_K

(23.2)

Очевидно, що при x₁ = x₂ = … = x_K = 0, L=g₀. Подивимося, чи не можемо ми поліпшити рішення, тобто зменшити функцію L, збільшуючи які-небудь із змінних x₁, x₂,..., x_K (зменшити їх ми не можемо, тому що вони рівні нулю, а негативні значення змінних неприпустимі). Якщо всі коефіцієнти c₁, g₂, …, g_K у формулі (23.1) є позитивними, то, збільшуючи якісь з змінних x₁, x₂,..., x_K понад нуля, ми не можемо зменшити L. Отже, знайдене нами рішення є оптимальним. Якщо ж серед коефіцієнтів g_К До є негативні, то збільшуючи деякі з змінних x₁, x₂,..., x_K, а саме - ті, коефіцієнти при яких негативні, ми можемо покращити рішення.

Нехай, наприклад g₁ у формулі (23.1) від'ємний. Значить, є сенс збільшити х₁, тобто перейти від даного опорного рішення до іншого, де мінлива х₁¹0, а замість неї дорівнює нулю якась інша. Збільшення х₁ «корисно» для цільової функції, робить її менше. Однак збільшувати х₁ треба обережно, так, щоб не стали негативними інші змінні x_{к +1}, x_{к +2},..., x_n, виражені через вільні змінні, зокрема через х₁ формулами (23.1).

Подивимося, чи небезпечно для змінних x_{к +1}, x_{к +2},..., x_n, збільшення х₁, тобто чи може воно зробити їх негативними? Так, небезпечно, якщо коефіцієнт при х₁ у відповідному рівнянні від'ємний. Якщо серед рівнянь (23.1) немає рівняння з негативним коефіцієнтом, при х₁, то величину х₁ можна збільшувати безмежно, а значить функція L не обмежена знизу і оптимального рішення не існує. Припустимо, що це не так і що серед рівнянь (23.1) є такі, в яких коефіцієнт при х₁ від'ємний. Для змінних, що стоять в лівих частинах цих рівнянь, збільшення х₁ небезпечно - воно може зробити їх негативними. Візьмемо одну з цих змінних Х_L і подивимося, до якої міри можна все ж збільшити х₁, поки мінлива Х_L не стане негативною? Випишемо l - ше рівняння з системи (23.1).

, при (23.3)

Тут вільний член b_l ³ 0, а коефіцієнт a_l1 - негативний (припустимо). Легко зрозуміти, що якщо ми залишимо х₂ =... = х_К = 0, то х₁ ми можемо збільшувати тільки да значення, рівного х₁ = b_l/a_l1, а при подальшому збільшенні х₁ мінлива Х_L стане негативною.

Виберемо ту з змінних х_{К +1} ... х_n, яка раніше за всіх звернутися в нуль при збільшенні х₁, тобто ту, для якої величина = х₁ = b_l/a_l1 найменше. Нехай така найбільш загрозлива змінна буде хr. Тоді має сенс «перевирішити» систему рівнянь щодо інших базисних змінних, вивівши з числа вільних змінних х₁ і перевівши замість неї в групу вільних змінних х_r. Дійсно, ми хочемо перейти від опорного рішення, що задається рівностями до опорного рішенням х₁ = х₂ =... = х_к = 0, в якому вже х₁¹0, а х₂ =... = х_к = х_r = 0. Перше опорне рішення ми отримали, поклавши рівним нулю всі колишні вільні змінні х₁, х₂,..., х_к, друге ми отримаємо, якщо звернемо в нуль все нові вільні змінні х₂, х_к, х_r. Базисними змінними при цьому будуть х₁, х_{к +1},..., х_r-1, х_{r +1},..., х_n. Припустимо, що рівняння для нового набору базисних і вільних змінних складені. Тоді можна висловити через нові вільні змінні і лінійну функцію L. Якщо всі коефіцієнти при змінних в цій формулі позитивні, то ми знайшли оптимальне рішення (воно вийде якщо всі вільні змінні = 0).

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

Процедура «перевирішення» системи рівнянь - обмежень ОЗЛП щодо нових базисних змінних може бути істотно спрощена, якщо її формалізувати і звести до заповнення стандартних таблиць по певній системі правил (коротше алгоритму). Цей алгоритм продемонструємо на конкретному прикладі. Розглянемо систему п'яти рівнянь обмежень:

y₁=a₁₁x₁+a₁₂x₂+a₁₃x₃+a₁₄x₄+b₁

y₂=a₂₁x₁+a₂₂x₂+a₂₃x₃+a₂₄x₄+b₂

y₃=a₃₁x₁+a₃₂x₂+a₃₃x₃+a₃₄x₄+b₃

y₄=a₄₁x₁+a₄₂x₂+a₄₃x₃+a₄₄x₄+b₄ (23.4)

y₅=a₅₁x₁+a₅₂x₂+a₅₃x₃+a₅₄x₄+b₅

З чотирма вільними змінними х₁, х₂, х₃, х₄. Нехай нам потрібно вивести з числа вільних змінних якусь змінну, наприклад х₂ і перевести її в базисні, а натомість її ввести в число вільних якусь базисну змінну, скажімо у₃, коротше кажучи, ми хочемо обміняти місцями змінні х₂ і у₃. Цю заміну символічно позначають х2 Û у3. Для полегшення цього завдання скористаємося табличним алгоритмом. Попередньо, доцільно кілька перетворити систему рівнянь (23.4), представивши їх праві частини як різниці між вільними членами та сумою інших:

y₁= b₁ – (–a₁₁x₁ – a₁₂x₂ – a₁₃x₃ – a₁₄x₄)

y₂= b₂ – (–a₂₁x₁ – a₂₂x₂ – a₂₃x₃ – a₂₄x₄)

y₃= b₃ – (–a₃₁x₁ – a₃₂x₂ – a₃₃x₃ – a₃₄x₄)

y₄= b₄ – (–a₄₁x₁ – a₄₂x₂ – a₄₃x₃ – a₄₄x₄)

y₅= b₅ – (–a₅₁x₁ – a₅₂x₂ – a₅₃x₃ – a₅₄x₄) (23.5)

Позначаючи –a₁₁ = a₁₁, –a₁₂ = a₁₂…–a₅₄ = a₅₄ одержимо:

y₁= b₁ – (a₁₁x₁ + a₁₂x₂ + a₁₃x₃ + a₁₄x₄)

y₂= b₂ – (a₂₁x₁ + a₂₂x₂ + a₂₃x₃ + a₂₄x₄)

y₃= b₃ – (a₃₁x₁ + a₃₂x₂ + a₃₃x₃ + a₃₄x₄) (23.6)

y₄= b₄ – (a₄₁x₁ + a₄₂x₂ + a₄₃x₃ + a₄₄x₄)

y₅= b₅ – (a₅₁x₁ + a₅₂x₂ + a₅₃x₃ + a₅₄x₄)

Форму запису рівнянь (23.6) будемо називати стандартної.

Очевидно, замість того, щоб повністю записувати рівняння (23.6) можна обмежитися заповненням стандартної таблиці, де вказані тільки вільні члени і коефіцієнти. Перший стовпець таблиці ми відведемо під вільні члени, другий, третій, четвертий і п'ятий - під коефіцієнти при змінних х₁, х₂, х₃, х₄. Стандартна таблиця для системи (23.6) має вигляд:

	свободный член	X 1	X 2	X 3	X 4
y1	b1	a 11	a 11	a 11	a 11
y2	b2	a 11	a 11	a 11	a 11
y3	b3	a 11	a11	a11	a11
y4	b4	a 11	a11	a11	a11
y5	b5	a 11	a11	a11	a11
L	g0	g 1	g2	g3	g4

Тепер уявімо собі, що ми хочемо зробити заміну х₂ Û у₃, тобто перевести х₂ в число базисних, а у₃ - в число вільних. Виділимо в стандартній таблиці дозволяючий коефіцієнт a₃₂. Виділимо, також, рядок і стовпець, в якому стоїть дозволяючий елемент. Цей рядок і стовпець назвемо вирішуючим рядком і стовпцем. Виконуючи операцію х₂ Û у₃ ми хочемо в роздільною рядку помістити змінну у₃, а в дозвільному стовпці - х₂. Знайдемо коефіцієнти, які потрібно буде поставити в таблиці після обміну х₂ Û у₃. Почнемо з перетворення роздільного рядка. Вирішуючи третє рівняння (23.6) щодо х₂

(23.7)

Таким образом, преобразованные элементы разрешающей строки найдены. Составим правило преобразования остальных строк. Для этого подставим в уравнение (23.6)(например в первое) вместо х₂ его выражение (23.7). после приведения подобных членов, получим:

(23.8)

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

х₂ Û у₃ вже здійснена.

	Вільний член	x1	y3	x3	x4
Y1
Y2
X2
Y4
Y5

Розглянувши цю таблицю, ми можемо сформулювати алгоритм перетворення коефіцієнт стандартної таблиці.

1. Дозволяючий елемент замінюється на зворотню йому величину.

2. Всі інші елементи роздільного рядка діляться на вирішуючий елемент.

3. Всі елементи дозволяючого стовпця (крім самого дозволяючого елемента) змінюють знак і ділять на дозволяючий елемент.

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

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

Перетворення стандартної таблиці при заміні х_j Û у_i зручно робити, виконуючи всі допоміжні розрахунки тут же, у таблиці, для чого виділяється нижня частина кожної клітинки. Алгоритм перетворення х_j Û у_i зводиться при цьому до наступних операцій:

1. Виділити в таблиці дозволяючий елемент a_ij. Обчислити його зворотню величину l = 1/a_ij і записати в нижній частині тієї ж комірки (у правому нижньому куті)

2. Всі елементи роздільного рядка (крім самого a_ij) помножити на +l, результат записати в нижній частині тієї ж осередки.

3. Всі елементи дозволяючого стовпця (крім самого a_ij) помножити на -l, результат записати в нижній частині тієї ж осередки.

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

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

6. Переписати таблицю, замінивши: x_j на y_i і назад, елементи дозволяючого стовпця і рядка - числами, що стоять в нижніх частинах тих же осередків, кожен з окремих елементів - сумою чисел, що стоять у верхній і нижній частині тієї ж осередки.

Таким чином, за допомогою табличного алгоритму ми можемо здійснювати будь-яку заміну х_j Û у_i. Згадаймо, що в задачі лінійного програмування, крім рівнянь - обмежень існує ще й цільова функція:

(23.9)

яку потрібно мінімізувати. Якщо ця функція виражена через колишні вільні змінні х₁, х₂,..., х_n, то, очевидно, після заміни х_j Û у_i її потрібно висловити через нові вільні змінні х₁, х₂,..., х_{j +1}, y_i, x_i +... + x_n. Неважко переконатися, що для цього може бути застосований той же алгоритм, що і для перетворення будь-якого рядка стандартної таблиці. Наводячи L до стандартної форми, ми отримаємо ще один рядок, яка відрізняється від інших лише тим, що в ній ніколи не вибирається дозволяючий елемент.

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

1. Пошук опорного рішення.

2. Пошук оптимального рішення.

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

Розглянемо відшукання опорного рішення ОЗЛП за допомогою розглянутого алгоритму. Нехай є ОЗЛП з обмеженнями - рівностями, записаними в стандартній формі, дозволеними щодо базисних змінних

х₁, х₂,..., х_n, які виражені через вільні змінні х1, х₂,..., х_n. У кожній вершині ОДР (опорному рішенні) принаймні n змінних повинні бути звернені в нуль. Отже, якщо х₁ = х₂ =... = х_n = 0, то y₁ = b₁, y₂ = b₂,..., y_m = b_m. Якщо всі вільні члени b₁, b₂,..., b_m в рівняннях ненегативні, це означає, що опорне рішення уже отримано. Розглянемо випадок, коли серед вільних членів є негативні. Належить знайти опорне рішення. Для цього ми крок за кроком будемо обмінювати місцями базисні та вільні змінні, до тих пір, поки не прийдемо до опорного рішенням або не переконаємося, що його не існує.

Останнє буває, коли система несумісна з нерівностями x_j> 0, y_i> 0, тобто у неї немає невід'ємних рішень. Очевидно, потрібно так обмінювати місцями базисні та вільні змінні, щоб ця процедура наближала нас до кордону ОДР, а не видаляла від неї, тобто щоб число негативних вільних членів з кожним кроком зменшувалося, або принаймні, убували їх абсолютні величини. Існує ряд способів вибору дозволяючого елемента для наближення до опорного рішення. Зупинимося на одному з них. Нехай є одне з рівнянь, з негативним вільним членом. Шукаємо в цьому рядку негативний елемент a_ij. Якщо такого елемента немає, то це ознака того, що система рівнянь несумісна з нерівностями

x_j> 0, y_i> 0. Припустимо, що негативний елемент є.

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

Далі сформулюємо правила перебування оптимального рішення ОЗЛП симплекс-методом.

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

2. Якщо в рядку L є позитивний елемент, а в стовпці відповідному йому немає жодного позитивного елементу, то лінійна функція L не обмежена знизу і оптимального рішення не існує.

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

Розглянутий алгоритм найбільш доцільно реалізовувати на ЕОМ (особливо при великому числі змінних).

Дата добавления: 2014-01-07