3.3 Алгебра симплексного процесу при визначенні оптимального розв’язку типу max

1. Розв'язувальний стовпець вибирається по від’ємному елементу в рядку лінійної форми F (за винятком вільного члена).

2. Розв'язувальний рядок вибирається по мінімальному симплексному відношенню.

3. Розв'язувальний елемент завжди позитивний.

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

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

3.4. Умови збіжності симплексного процесу

Визначення. ЗЛП називається невиродженою, якщо в жодному з її опорних планів серед базисних змінних немає нульових значень.

С точки зору геометрії виродженість ЗЛП можна трактувати як стягування двох вершин багатогранника ( в одну (мал. 10). Виродженість, як правило, приводить до зациклення ітераційного процесу.

Мал. 10

Теорема (про збіжність симплексного процесу)

Нехай:

1. ЗЛП невироджена.

2. Система обмежень ЗЛП має, принаймні, одне опорне рішення.

3. Лінійна форма F обмежена знизу при визначенні opt min і зверху при визначенні opt max.

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

Як правило, при рішенні ЗЛП симплексним методом кількість ітерацій R < 2 r (r – ранг системи обмежень ЗЛП).

Коментарі до теореми про збіжність симплексного процесу

1. Ознака необмеженості цільової функції.

Нехай при розгляді функції F на экстремум типу максимум на деякому кроці симплексна таблиця придбала вид:

	1	-х4	-х5
х1	2	–1	2
х2	3	0	–1
х3	1	–3	4
F	4	–1	5

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

Ознака наявності незліченної множини оптимальних планів

Нехай при дослідженні функції F на экстремум типу максимум на деякому кроці симплексна таблиця придбала вид:

	1	-х4	-х5
х1	1	1	0
х2	2	2	–1
х3	4	3	4
F	3	0	2

З аналізу таблиці виходить

Приклад. Наступну задачу лінійного програмування розв’язати прямим симплексним методом. Розв’язок проілюструвати графічно.

Система обмежень даної задачі сумісна, Ω - область припустимих планів представлена на мал. 11.

Мал. 11

Перетворимо обмеження-нерівності вихідної ЗЛП в обмеження-рівності шляхом введення балансових змінних х₃, х₄ ≥ 0:

Виділимо базис невідомих (х₃, х₄ – базисні, х₁, х₂ – вільні) і виразимо базисні невідомі через вільні:

Складемо первісну симплексну таблицю:

	1	-х1	-х2
х3	6	1	1
х4	8	1	2
F	0	–2	–3

У даній таблиці записаний первісний опорний план:

Геометрично цей план відповідає вершині багатокутника Ω..

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

Будемо збільшувати вільну змінну х₁ (тим самим визначаємо розв'язувальний стовпець). Тому що в розв'язувальному стовпці є невід’ємні елементи, то ріст змінної х₁ буде стримуватися базисними змінними, у вираз для яких х₁ входить зі знаком «мінус» .

По мінімальному симплексному відношенню (відношенню вільного члена до невід’ємного елемента розв'язувального стовпця) визначимо, яка з базисних змінних першою обернеться в нуль:

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

Н ова симплексна таблиця має вигляд:

	1	-х3	-х2
х1	6	1	1
х4	2	–1	1
F	12	2	–1

В останній таблиці записаний поліпшений план:

Геометрично цей план відповідає вершині багатокутника Ω.

Наявність у рядку лінійної форми невід’ємного елемента свідчить про те, що значення цільової функції F₁ не є оптимальним і його можна далі збільшити за рахунок збільшення вільної змінної х₂. Розв'язувальний рядок визначаємо по мінімальному симплексному відношенню:

Після одного кроку жорданових виключень одержимо нову симплексну таблицю

	1	-х3	-х4
х1	4	2	–1
х2	2	–1	1
F	14	1	1

і новий опорний план: Цей план геометрично відповідає вершині багатокутника Ω.

Останній опорний план є оптимальним, тому що в рядку лінійної форми немає від’ємних елементів і подальше збільшення значення цільової функції неможливо: