Симплексний метод вирішення завдань лп

У стовпці Сб записуються коефіцієнти цільової функції з тими ж індексами, що і вектори базису.

У стовпці Р0 записуються позитивні компоненти вихідного опорного плану, в ньому ж в результаті обчислень отримують позитивні компоненти оптимального плану. У стовпчиках Р1 ... Рn записані коефіцієнти обмежень при невідомих.

В (m + 1) -му рядку: F0 - поточне значення цільової функції; в шпальтах Pj записані числа.

1. Завдання ЛП призводять до канонічного вигляду і знаходять вихідний опорний план.

2. Складають вихідну симплекс-таблицю.

3. Визначають, чи є хоча б одне негативне число # 916; j в (m + 1) -му рядку. Якщо немає, то знайдений опорний план оптимальний.

4. Знаходять найменший негативний # 916; j і відповідний стовпець позначають як дозволяє. Якщо в дозвільному стовпці серед чисел aij немає позитивних, то цільова функція не обмежена зверху, а завдання ЛП не має рішення.

5. Знаходять відносини bi до позитивних aij дозволяє стовпця. Мінімальна з цих відносин визначає роздільну рядок.

6. На перетині дозволяють рядки і стовпці визначають дозволяє елемент.

7. Всі елементи роздільної рядка ділять на дозволяючий елемент.

8. Всі елементи дозволяє стовпця (крім дозволяє елемента) замінюють нулями.

9. Інші елементи таблиці розраховуються за правилом прямокутника і фіксується введення в базис нової змінної. При цьому роздільна рядок визначає змінну, яка виключається з базису, а дозволяє стовпець - змінну, яка вводиться в базис.

10. Переходять до пункту 3.

Цей опорний план X * = (0; 8; 20; 0; 0; 96) оптимальний, тому що Усе # 916; j невід'ємні.

Максимальне значення функції на оптимальному рішенні одно:

Fmax = 0 · 9 + 8 · 10 + 20 · 16 + 0 · 0 + 0 · 0 + 0 · 96 = 400

Індивідуальні завдання. Вирішити задачу ЛП симплексним методом. Варіанти завдань взяти з індивідуальних завдань пункту 1.1.

1.3. Метод штучного базису.

У загальному випадку після приведення завдання ЛП до канонічного вигляду безпосередньо записати опорний план не вдається, тому що серед векторів Pj. немає m одиничних. У цьому випадку завдання ЛП вирішується методом штучного базису.

Постановка задачі. Потрібно знайти максимум функції

але серед векторів Pj немає m одиничних.

Визначення. Завдання, що складається у визначенні максимуму функції

називається розширеною по відношенню до вихідної задачі (1.10), (1.11).

Тут M деякі великі позитивні числа, значення яких не задаються.

Розширена задача (1.12), (1.13) має опорний план:

Змінні xn + 1. xn + 2 ... xn + m називаються штучними, а система одиничних векторів Pn + 1. Pn + 2 ... Pn + m утворює штучний базис.

Якщо в оптимальному плані розширеної задачі (1.12), (1.13) значення штучних змінних дорівнюють нулю, то - є оптимальний план вихідної завдання (1.10), (1.11).

Тому процес вирішення завдання ЛП (1.10), (1.11) включає наступні етапи:

1. Для початкового завдання складають розширену задачу виду (1.12), (1.13).

2. Знаходять опорний план розширеної задачі.

3. За допомогою обчислень симплекс-методу виключають штучні вектора з базису. В результаті знаходять опорний план вихідної задачі. Якщо штучні змінні виключити з базису не вдається, то задача ЛП нерозв'язна.

4. Використовуючи знайдений опорний план вихідної завдання (1.10), (1.11), або знаходять симплекс-методом її оптимальний план, або встановлюють її нерозв'язність

Приклад. Знайти мінімум функції

Уявімо цю задачу в канонічному вигляді: