Лабораторна робота № 2. Обчислювальні методи лінійного програмування

При кількості змінних більш трьох задача не може бути вирішена геометрично. Однак ідея одержання рішення зберігає зміст і для випадку багатьох змінних.

2.1. Загальна ідея симплекс-метода.

Нагадаємо, при аналізі графічного методу рішення задач ЛП було відзначено, що оптимальному рішенню завжди відповідає одна з кутових (екстремальних) точок простору припустимих рішень (для п - мірного простору - це вершина багатокутника області допустимих розв’язків, який називається симплексом). Саме цей результат покладений в основу симплекс-метода.

В обчислювальній схемі симплекс-методу реалізується упорядкований процес, при якому, починаючи з деякої вихідної припустимої кутової точки (звичайно початку координат), здійснюються послідовні переходи від однієї припустимої екстремальної точки до іншої до тих пір, поки не буде знайдена точка, що відповідає оптимальному рішенню. Усі переходи здійснюються тільки до суміжних точок, причому перед новим переходом кожна з отриманих точок перевіряється на оптимальність.

Алгоритм симплекс-методу вимагає привести задачу ЛП до канонічного вигляду, тобто:

1) всі обмеження записуються у вигляді рівностей з невід’ємною правою частиною;

2) значення всіх змінних мають бути невід’ємними.

Будь-яку лінійну модель можна привести до канонічного вигляду, використовуючи такий спосіб:

ü Обмеження у вигляді нерівностей типу £ (³) можна представити у вигляді рівності, додаючи залишкову (віднімаючи надлишкову) додаткову змінну до лівої частини обмеження.

ü Праву частину рівності завжди можна зробити невід’ємною, якщо помножити обидві частини на (-1), причому, знак нерівності змінюється на протилежний.

ü Будь-яку змінну, що не має обмеження в знаку, можна представити як різницю двох невід’ємних змінних , де .

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

.

Здійснивши зазначені операції приведемо вихідну модель до канонічного вигляду:

Поиск по сайту: