Практичне заняття №3
Тема: |
Симплекс-метод розв’язку ЗЛП |
Мета: |
|
Час: |
2 год. |
Теоретичні відомості
Симплекс-метод використовується для визначення максимального значення цільової функції
(3.1)
при заданій системі обмежень
(3.2)
Симплекс-метод базується на переході від одного опорного плану до іншого, при якому значення цільової функції зростає.
Розв’язок задачі лінійного програмування симплекс-методом включає наступні етапи:
Приводимо ЗЛП (3.1) – (3.2) до канонічного виду.
ЗЛП полягає у визначенні максимального значення цільової функції
(3.3)
при умовах
(3.4)
Змінні
є базисними, тому що кожна з них входить
до складу тільки одного рівняння системи
обмежень (3.4) з коефіцієнтом 1. Змінні
є вільними.
Заповнюємо першу симплекс-таблицю.
Таблиця 3.1 – Симплекс-таблиця
|
|
Базис
|
|
|
|
… |
|
|
|
… |
|
|
|
|
|
… |
|
|
|
… |
|
|
|||||
|
|
|
|
|
|
… |
|
|
|
… |
|
|
|
|
|
|
|
|
|
… |
|
|
|
… |
|
|
|
… |
… |
… |
… |
… |
… |
… |
… |
… |
… |
… |
… |
|
|
|
|
|
|
|
|
… |
|
|
|
… |
|
|
|
|
|
|
|
|
|
… |
|
|
|
… |
|
|
|
Перша симплекс-таблиця заповнюється за наступними правилами:
а) у стовпець записують коефіцієнти при базисних змінних в цільовій функції (3), у стовпець – базисні змінні;
б) у
стовпець
записують праві частини системи обмежень
(3.4);
в)
у стовпцях
записують коефіцієнти
при змінних в системі обмежень (4);
г)
у
-ому
рядку записують значення
,
(
), (
для базисних змінних дорівнюють 0),
.
Опорний план задачі має вигляд
.
Базисні
змінні
дорівнюють до відповідних елементів
стовпця
,
вільні змінні
дорівнюють
.
Таким чином маємо опорний план задачі
лінійного програмування
.
Перевіряємо опорний план
на оптимальність.
Якщо
в
-ому
рядку (будемо називати його рядком
)
усі значення
,
то
є оптимальним планом задачі (3.3) – (3.4).
Якщо хоча б одне значення
,
то опорний план
не є оптимальним.
Вибираємо напрямний стовпець і напрямний рядок.
Для
визначення напрямного стовпця
серед
вибираємо максимальне за модулем
значення
,
.
Заповнюємо
стовпець
.
Для
знаходимо
.
Для
не обчислюємо.
Напрямний
рядок
вибираємо за мінімальним значенням
:
.
На
перетинанні напрямного рядка і напрямного
стовпця знаходиться дозвільний елемент
.
Будуємо наступну симплекс-таблицю.
Перехід до неї здійснюється за такими правилами:
а)
замість змінної
,
що відповідає напрямному рядку, у базис
вводимо змінну
,
що відповідає напрямному стовпцеві;
б)
елементи напрямного рядка поділяємо
на напрямний елемент
;
в) елементи напрямного стовпця замінюємо нулями, крім дозвільного елемента, що дорівнює 1;
г) всі інші елементи перераховуємо за правилом прямокутника:
Переходимо до п. 3) і 4). Якщо всі
,
то отриманий план
є оптимальним. У противному випадку
проводимо нові обчислення і будуємо
наступну таблицю за відомими правилами.