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

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

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

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

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

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

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

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

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

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

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

Мал. 11

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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