Алгоритм симплекс-методу.

Записуємо робочу модель.

З’ясовуємо умови задачі і записуємо їх у вигляді обмежень.

Будуємо цільову функцію, що відображує мету розв’язання задачі і обов’язково включає до свого складу змінні.

Цільова функція нашої задачі має вигляд:

L = 10 х₁ + 18 х₂ → max,

де кожний окремий доданок означає прибуток від випуску продукції відповідного виду, а символ → max відображає вимогу максимізації функції.

Згідно з умовами прикладу запаси сировини S₁, S₂, S₃ обмежені і відповідно дорівнюють 60, 65, 135, отже, кількість ресурсів кожного типу, які використовуються для виробництва всіх видів продукції, не повинна перевищувати наявної їх кількості в розпорядженні підприємства:

2 х₁ + 2 х₂ ≤ 60,

3 х₁ + х₂ ≤ 65,

2 х₁ + 9 х₂ ≤ 135,

i, очевидно, випуск продукції повинен бути невід’ємним:

х₁ ≥ 0, х₂ ≥ 0.

L = 10 х₁ + 18 х₂ → max,

2 х₁ + 2 х₂ ≤ 60,

3 х₁ + х₂ ≤ 65,

2 х₁ + 9 х₂ ≤ 135,

х₁ ≥ 0, х₂ ≥ 0.

6. Зводимо дану задачу лінійного програмування до канонічної форми. (Детально дана задача розглянуто у прикладі 1).

Вводимо в ліві частини нерівностей виду “≤” додаткові невід’ємні змінні х₃, х₄, х₅ (балансові змінні) зі знаком “+” та отримуємо канонічну форму для заданої задачі лінійного програмування:

L = 10 х₁ + 18 х₂ → max,

2 х₁ + 2 х₂ + х₃ = 60,

3 х₁ + х₂ + х₄ = 65, (*)

2 х₁ + 9 х₂ + х₅ = 135,

х₁ ≥ 0, х₂ ≥ 0, х₃ ≥ 0, х₄ ≥ 0, х₅ ≥ 0.

1).

5). Обчислюємо елементи всіх інших рядків (при k≠p) за формулою:

a­’_іk = a­_іk - a­’_qk­∙ a­_іp­, (і = 0, 1, 2, …, q-1,q+1,…,r).

Перед тим як виконувати вищевказані дії, перевіряємо чи виконується теорема симплексного методу:

1) якщо в стовпчику, де γ­_і­ < 0 існує хоча б один елемент а­_ір­ > 0, то опорний план можна покращити;

2) якщо в усіх стовпчиках, де γ­_і­ < 0 немає жодного додатного елемента а­_ір­, (всі а­_ір­< 0), то функція цілі не обмежена в області допустимих розв’язків (L→max).

3) якщо γ­_і­ ≥ 0 для всіх і, то отриманий опорний план є оптимальним.

Повертаємося до прикладу. Отримана система рівнянь-обмежень сумісна, так як ранги матриці системи А та розширеної матриці Ā співпадають і рівні 3.

2 2 1 0 0 2 2 1 0 0 60

rang А = rang 3 1 0 1 0 = rang Ā = rang 3 1 0 1 0 65 = 3.

2 9 0 0 1 2 9 0 0 1 135

З того, що система сумісна і має ранг 3 випливає, що три базисні змінні можна лінійно виразити через дві вільні змінні. Виразимо, наприклад, змінні х₃, х₄, х₅ та функцію цілі через змінні х₁ та х₂, тобто приведемо систему до одиничного базису:

х₃ = 60 – 2х₁ – 2х­₂,

х₄ = 60 – 2х­₁ – 2х­₂,

х₅ = 60 – 2х­₁ – 2х­₂.

Функція цілі L = 10 х₁ + 18 х₂ виражена через змінні х­₁ та х­₂, перепишемо її для зручності у вигляді: L - 10 х₁ - 18 х_2­ = 0.

Покладемо х₁ = 0 та х₂ = 0 і дістаємо значення решти змінних: х₃ = 60, х₄ = 65, х₅ = 135. Всі значення змінних є невід’ємними і задовольняють системі (*), а тому є допустимими. Таким чином, отримали початковий розв’язок системи (*) – початковий план: (0; 0; 60; 65; 135). При цьому L = 0.

Таблиця 2.

Отриманий початковий план можна вдосконалити, так як в останньому рядку табл.2 є два від’ємні числа: -10, -18. Вибираємо за направляючий стовпчик - стовпчик, що містить х_2­, так як min {-18; -10} = -18. Визначаємо ведучий рядок, для цього з’ясовуємо, чи є в першому стовпці додатні числа. Їх три: 2, 1, 9. Складаємо відношення відповідних вільних членів до цих чисел, які заносимо в останній стовпчик і вибираємо серед цих відношень найменше (15), тоді ведучим рядком буде рядок, що містить х­_5­. На перетині направляючого стовпця та ведучого рядка буде число 9, цей елемент є розрахунковим. Таким чином, змінна х­_5­ виводиться з базису, тепер її значення дорівнює 0. Змінна х­₂ вводиться в базис. Виконуємо цю операцію за вищенаведеними правилами та отримуємо табл.3.

Таблиця 3.

З цієї таблиці знаходимо новий опорний план: (0; 15; 30; 50; 0) для якого L=270.

В табл. 3 в рядку для L є одне від’ємне число –6, яке відповідає стовпцю для змінної х­₁. Отже, виконуємо наступну ітерацію – крок симплекс-метода. У визначеному стовпці є три додатні чиста: 14/9, 25/9, 2/9. З останнього стовпчика за відношенням вільних членів до цих чисел визначаємо, що ведучим рядком буде рядок, що містить змінну х­₄. Розрахунковий елемент 25/9, що означає вивід з базису змінної х­₄ (тепер х­₄ = 0) та включення до базису змінної х­₁ . Провівши відповідні розрахунки, отримуємо табл. 4.

Таблиця 4.

Оскільки в останньому рядку немає від’ємних чисел, то отриманий опорний план (18; 11; 2; 0; 0), L = 378 є оптимальний.

Згідно з отриманим розв’язком, щоб отримати максимальний прибуток L­_max­ = 378, необхідно випускати 18 одиниць продукції Р­_1­ та 11 одиниць продукції Р­_1­.

Змінна х­_3­ = 2, це означає, що перший ресурс використовується не повністю. Є його залишок кількістю 2 одиниці. Оскільки х­_4­ та х­_5­ дорівнюють 0, то це означає, що другий і третій ресурси використовуються повністю.