85767 (Математичне програмування в економіці), страница 4

Визначальний елемент симплекс-таблиці – це коефіцієнт у рівнянні (3), якій дорівнює (5/7), та відіграє роль нового центру, або ключового елементу.

Як буде виготовлено 70 жіночих костюмів, так х₁ = 70 з рівняння (3) отримаємо у₃ = 0 (нова базова змінна);

Третій опорний план задачі складає:

Х (3) = (70; 80; 0; 60; 0;); Z (3) = 2300 грн.;

Z (3) Z (1);

де: у₁ = 0; у₃ = 0 - вільні змінні, відповідає розв’язку задачі, якщо виробляється 70 жіночих та 80 чоловічих костюмів. Надамо цю інформацію у вигляді симплекс-таблиці.

Таблиця

Збільшити прибуток неможливо у зв’язку з тим, що вільні змінні (у_і 0), що наявні у цільовій функції мають від’ємні коефіцієнти у той же час, як самі вони додатні. Опорний план Х (3) є оптимальним.

Х* = ( х₁* = 70? х₂* = 80; у₁ = 0; у₂* = 60; у₃ = 0);

залишки шовкової тканини складають 60 метрів, прибуток складає 2300 грн., як буде виготовлено 70 жіночих та 80 чоловічих костюмів.

Надамо звичайний вигляд симплекс-таблиці розв’язку задачі.

Таблиця 1 ітерація

Z (х) = ( -Z); Z (х) – С₀ – С₁Х₁ – С₂Х₂ – С₃Х₃ – С₄Х₄ – С₅Х₅ = 0;

Z = С₀ + С₁Х₁ + С₂Х₂ + С₃Х₃ + С₄Х₄ + С₅Х₅ = 0 + 10Х₁ + 10Х₂ + 0 Х₃ + 0 Х₄+ 0 Х₅ = 0 Х₁ + 2 Х₂ ;

( -Z) = - 10 Х₁ – 20 х₂; min

Таблиця 2 ітерація

х₂ = 100 – (2/7) х₁ – (2/7)х₃; Z (x) + (30/7) х₁ – (40/7)х₃ = -2000 ;

Z = 10х₁ + 20 (100 – (2/7)х₁ – (2/7)х₃ ) = 2000 + (30/7)х₁ – (40/7)х₃;

• Z = - 2000 + (40/7)х₃ - (30/7)х₁ = - 2000;

Таблиця 3 ітерація

х₁ = 70 + (2/5) х₃ – (7/5)х₅; Z (x) - (28/7) х₃ – 6 х₅ = -2300 ;

Z = 2000 + (30/7) (70 + (2/5)х₃ – (7/5)х₅ ) – (40/7) х₃= 2300 - 6х₅ – (28/7)х₃;

• Z = - 2300 + 6х₅ + (28/7)х₃ = - 2300; х₃ = х₅ = 0.

У цільовій функції усі вільні змінні від’ємні – опорний план Х* = (70; 80; 0; 60; 0) є оптимальним. Задача розв’язана.

Z*_max = (-Z*)_min = +2300.

Стереометрично ідея методу полягає у тому, що:

• знаходять будь-яку вершину багатогранника розв’язків;

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

• як потрапляють у вершину, з якої у всі боки функція зростає (спадає), так знаходять мінімум (максимум).

Нагадаємо ще раз:

• якщо вектор розв’язків задовольняє усім обмеженням, так він має назву плану;

• якщо план відповідає вершині багатогранника розв’язків (усі вільні змінні дорівнюють нулеві), так він має назву опорного плану;

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

Критерій оптимальності за симплекс-таблицею.

Якщо форма мінімізується (максимізується) і у рідку цільової функції відсутні додатні числа (від’ємні числа), за винятком стовпчика опорний розв’язок (b₁), так опорний план є оптимальним.

Коефіцієнти рядка цільової функції інтерпретують як приріст цільової функції при збільшенні вільної невідомої на одиницю. Приріст додатній, якщо коефіцієнт від’ємний, і навпаки від’ємний, якщо коефіцієнт додатній.

Стовпець “j” є вирішальним, як у цьому стовпцю, оцінка коефіцієнта при невідомій у цільовій функції найбільша за модулем, тобто

С_j = max.

Змінну “x_j” у вирішальному стовпцю знаходять за співвідношенням

b_i

min = , (f_ij 0; b_i 0);

a_ij

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

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

Елементи симплексної строки нової таблиці дорівнюють елементам старої таблиці, поділеним на “ a_ij” – ключовий елемент (центр). Усі інші елементи вирішального стовпця прирівнюють до “0” (за виключенням ключового, якій дорівнює одиниці) шляхом жорданового перетворення; це стосується також цільової функції.

Можливі випадки розв’язку задачі лінійного програмування симплексним методом.

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

Необмеженість задачі лінійного програмування виникає, як у якомусь стовпчику змінних у випадку мінімізації “с_j” 0 , а усі елементи таблиці “а_ij” 0; у випадку максимізації “с_j” 0, а усі “а_ij” 0. Це позначає, що область припустимих розв’язків задачі не обмежена знизу (мінімізація) або зверхне (максимізація).

Послідовність використання симплекс-методу:

• звести задачу лінійного програмування до задачі мінімізації у канонічній формі (обмеження-рівняння; b_і 0);

• поділити змінні на базисні та вільні і отримати базисне припустиме рішення (базисні змінні невід’ємні; вільні змінні дорівнюють нулеві);

• знайти вираз базисних змінних та цільової функції через вільні змінні;

• за знаком коефіцієнтів при невідомих (с_j 0) у цільовій функції з’ясувати, чи є рішення оптимальне

Z = с₀ + с₁х₁ + с₂х₂ + . . . + с_nх_n ; (c_j 0 – мінімізація); або яку вільну змінну можливо підвищити від нуля та перевести у базис і відповідно, яку базисну змінну перевести у вільні змінні;

• знайти мінімальне додатне співвідношення “b_i” вільних членів рівнянь-обмежень до коефіцієнтів “a_ij” при новій вільній змінній, тобто з’ясувати, яку базисну змінну необхідно перевести у вільні змінні;

• перетворити умови-обмеження та цільову функцію у вираз в залежності від нових вільних змінних.

Приклад.