3.1. Оптимальний план злп

Визначення оптимального плану типу min проілюструємо на прикладі рішення наступної задачі:

(26)

(27)

(28)

Аналіз задачі.

1) задача представлена в першій канонічній формі;

2) система обмежень (27) включає п'ять змінних, n = 5, r = 3;

3) тому що r = 3, у системі будуть три базисні змінні й n – r =2 – вільні;

4) х₁, х₂, х₃ – базисні змінні системи (27)

(х₁ – тільки в першому рівнянні, х₂ – тільки в другому, х₃ – тільки в третьому);

х₄, х₅ – вільні змінні.

Виразимо лінійну форму (26) і базисні змінні через вільні

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

Далі необхідно зменшувати значення лінійної форми F. Зменшення лінійної форми F можна здійснити за рахунок збільшення вільних змінних. Однак збільшення вільних змінних, у цьому випадку х₄, стримується базисними змінними, які повинні залишатися невід’ємними. Тому варто визначити ту базисну змінну, котра першою обернеться в нуль і перейде в розряд вільних. У розглянутій задачі першою обернеться в нуль базисна змінна х₁. Це видно з жорданової таблиці, в якій складено первісний план задачі. Після одного кроку модифікованих жорданових виключень одержимо нову жорданову таблицю, з якої одержимо нове значення цільової функції При цьому це значення буде мінімальним, тому що в рядку лінійної форми всі елементи (за винятком значення функції F) від’ємні, і подальше зменшення значення цільової функції неможливо. Остаточно, маємо

	1	-х4	-х5			1	-х1	-х5
х1	2	1	1		х4	2	1	1
х2	7	2	3		х2	3	–2	1
х3	2	–1	–3		х3	4	+1	–2
F	3	1	–1		F	1	–1	–2

3. 2. Алгебра симплексного процесу при визначенні opt типу min

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

2. Розв'язувальний рядок вибирається по мінімальному симплексному відношенню, тобто по мінімальному відношенню елемента стовпця вільних членів до відповідного невід’ємного елемента розв'язувального стовпця. У розглянутій задачі , тобто розв'язувальний рядок – перший.

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

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

Розв'язок прямо припустимий, якщо серед базисних змінних немає невід’ємних.

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

Визначення оптимального плану типу max проілюструємо на прикладі розв'язування наступної задачі:

Первісне значення лінійної форми F₀ = 3, .

На основі останньої форми запису ЗЛП складемо первісну жорданову таблицю

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

Нове значення лінійної форми , новий план Цей план є оптимальним, тому що в рядку лінійної форми F всі елементи невід’ємні й подальше збільшення значення функції цілі неможливо. Таким чином,