Оптимальний план ЗЛП

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

(26)

(28)

(27)

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

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

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

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

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

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

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

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

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

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

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

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