2018-01-21
499
Алгоритм розв’язування задач ЛП симплекс – методом:
1. Будуємо першу симплекс – таблицю. Для цього:
1.1. Запишемо задачу у канонічній формі. Для цього введемо додаткові змінні із знаком
«+», якщо нерівність виду «
»
«-», якщо нерівність виду «
»
1.2. Якщо додаткові змінні було введено із знаком «-», помножимо ліву і праву частини рівняння на (-1), щоб отримати базисні невідомі.
Будуємо симплекс – таблицю.
1.3. В стовпчик Базис записуємо базисні вектори
1.4. В стовпчик Сб заносимо відповідні базисним невідомим коефіцієнти з цільової функції.
1.5. Стовпчик 
заповнюємо вільними членами ві із рівнянь, відповідних базисним невідомим.
1.6. В рядок 
та 
записуємо всі вектори, що входять в систему обмежень та відповідні їм коефіцієнти з цільової функції (ЦФ)
1.7. В стовпчики заносимо коефіцієнти перед змінними хj із системи обмежень.
1.8. Визначаємо значення цільової функції для даного опорного плану:
F0 = 
;
1.9. Обчислюємо оцінки для кожного вектора :
1.10. Перевіряємо, чи має дана задача лінійного програмування (ЛП) розв’язки і, якщо так, точи є отриманий опорний план-оптимальним. Якщо задача не має розв’язків, або отриманий план – оптимальний – задачу розв’язано.
|
|
|
2. Якщо задана задача ЛП має розв’язки, але отриманий план не є оптимальним, будуємо другу симплекс – таблицю.
Для цього:
2.1. Визначаємо найбільшу за абсолютною величиною від’ємну оцінку (якщо F 
max) або додатню оцінку (якщо F min).
Вектор, якому належить дана оцінка, будемо вводити в базис і називати розв’язувальним стовпчиком (РС).
2.2. Для визначення вектора, який виводимо з базису, із розв’язувального стовпчика для всіх додатних елементів знаходимо співвідношення:
(1)
Рядок, який відповідає (1), називається також розв’язувальним і вектор, що належить цьому рядку, виводиться із базису.
2.3. На перетині розв’язувального стовпчика і розв’язувального рядка визначаємо розв’язувальний елемент (РЕ)
2.4. В стовпчик Базис записуємо вектори, що утворили новий базис, а в стовпчик 
, відповідні їм коефіцієнти із ЦФ
2.5. Всі інші елементи базисного рядка отримуємо діленням елементів, що знаходились в попередній симплекс - таблиці, на РЕ. Всі інші елементи базисного стовпчика дорівнюють 0.
2.6. Елементи інших рядків обчислюємо за правилом Жордана- Гауса:
, де
- елементи з першої симплекс - таблиці
CI – розрахунковий елемент;
BII – елемент, що необхідно обчислити для II симплекс - таблиці, який стоїть на місці bI з І симплекс - таблиці.
2.7. Перевіряємо отриманий опорний план на можливість розв’язку та оптимальність (1.9, 1.10) та обчислюємо значення ЦФ для даного плану.
|
|
|
1.8. Якщо отриманий план не оптимальний – будуємо наступну симплекс – таблицю.
