Зведення загальної ЗЛП до канонічної форми

План

Лінійних економічних задач

Аналітичні методи дослідження

1. Зведення загальної задачі ЛП до канонічної форми.

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

3. Розв’язування прикладних задач лінійної оптимізації симплексним методом.

1. Зведення загальної ЗЛП до канонічної форми

Симплекс-метод – це поетапна обчислювальна процедура, в основу якої покладено принцип послідовного поліпшення значень цільової функції переходом від одного опорного плану ЗЛП до іншого.

- для розв’язування задач ЛП – у канонічній формі:

1) задача ЛП записана в першій стандартній формі (обмеження-рівності);

2) праві частини рівнянь-обмежень (вільні члени) невід’ємні;

3) система рівнянь-обмежень має чітко виділений базис, тобто в кожному рівнянні є невідома з коефіцієнтом 1 і ця невідома відсутня в усіх інших рівняннях системи обмежень. Ці невідомі називаються базисними, а всі інші – вільними;

4) цільова функція залежить тільки від вільних невідомих.

Якщо -те обмеження – рівність в правій частині має значення , то помноживши -те обмеження на (-1), в правій частині утвориться додатне значення.

Якщо -те обмеження має вигляд нерівності

,

то ввівши допоміжну (балансову) змінну , обмеження – нерівність можна представити у вигляді рівності .

Аналогічно, якщо -те обмеження має вигляд нерівності , то ввівши допоміжну (балансову) змінну , обмеження – нерівність можна представити у вигляді рівності .

Примітка. ЗЛП на відшукання оптимального плану, при якому досягається максимум цільової функції, може бути зведено до ЗЛП на мінімум, якщо цільову функцію помножити на (-1).

Тобто задачі: знайти

і знайти

мають однакові оптимальні розв’язки.

Приклад. Записати в канонічній формі наступну ЗЛП.

Знайти: ,

за умов

Розв’язання:

1. Введемо балансову змінну у першу нерівність, помножимо на (-1) друге і трете обмеження та введемо балансову змінну в другу нерівність.

- , не змінюють значення цільової функції.

Отже, задана ЗЛП може бути представлена в наступній канонічній формі.

Знайти:

за умов

Особливості симплекс-методу:

- є достатньо ефективним алгоритмом, але - є алгоритмом з експоненціальною складністю;

- використовують для вирішення будь-якої задачі лінійного програмування;

- забезпечує більш раціональне вирішення задачі.

Сутність: відправляючись з деякої довільної вершини багатокутника обмежень, переходять до обчислення тільки такої вершини, в якій значення лінійної форми буде більше, ніж в попередній. Решту варіантів не обчислюють. Тоді при кінцевому порівняно малому числі кроків може бути знайдений оптимальний план. Таким чином, проводиться впорядкований перебір вершин, при якому відбувається постійне збільшення лінійної форми. Тому симплексний метод називають ще методом послідовного поліпшення плану.

Дата добавления: 2014-01-07