>
НЕ що має обмеження в знаку, можна представити як різниця двох невід'ємних змінних: Y i = Y i '-Y < b> i '', де Y i ', Y i '' => 0.
Таку підстановку варто використовувати у всіх обмеженнях, які містять вихідну змінну Y i , а також у вираженні для цільової функції.
Зазвичай знаходять рішення задачі ЛП, в якому фігурують змінні Y i ' і Y i '' , а потім за допомогою зворотного підстановки визначають величину Y i . Важлива особливість змінних Y i ' і Y i '' полягає в тому, що при будь-якому допустимому рішенні тільки одне з цих змінних може приймати позитивне значення, тобто якщо Y i '> 0 , те Y < b> i '' = 0 , і навпаки. Це дозволяє розглядати Y i ' як залишкову зміну, а Y i '' - як надлишкову зміну, причому лише одна з цих змінних може приймати позитивне значення. Зазначена закономірність широко використовується в цільовому програмуванні і фактично є передумовою для використання соответсвующих перетворень в задачі 2.30
Цільова функція
В
Цільова функція лінійної оптимізаційної моделі , Представлена ​​в стандартній формі, може підлягати як максимізації, так і мінімізації. У деяких випадках виявляється корисним змінити вихідну цільову функцію.
Максимізація деякою функції еквівалентна мінімізації тієї ж функції, взятої з протилежним знаком, і навпаки. Наприклад максимізація функції
Z = X 1 + 25X 2
еквівалентна мінімізації функції
( - Z) =-X 1 - 25X 2
Еквівалентність означає, що при одній і тій же сукупності обмежень оптимальні значення X 1 , X 2 , < b> в обох випадках будуть однакові. Відмінність полягає тільки в тому, що при однакових числових значеннях цільових функцій їх знаки будуть протилежні.
Симплекс-метод.
У обчислювальної схемою симплекс-методу реалізується упорядкований процес, при якому, починаючи з деякої вихідної допустимої кутової точки (зазвичай початок координат), здійснюються послідовні переходи від однієї допустимої екстремальної точки до іншої до тих пір, поки не буде знайдена точка, відповідна оптимального рішення.
Загальну ідею симплекс-методу можна проілюструвати на прикладі моделі, посроенной для нашої задачі. Простір рішень цього завдання представимо на рис. 1. Вихідною точкою алгоритму є початок координат (точка А на рис. 1). Рішення, відповідне цій точці, зазвичай називають початковим рішенням. Від вихідної точки здійснюється перехід до деякої суміжної кутовий точці.
Вибір кожної наступної екстремальній точки при використанні симплекс-методу визначається наступними двома правилами .
1. Кожна наступна кутова точка повинна бути суміжній з попередньою. Цей перехід здійснюється за межам (ребрах) простору рішень.
2. Зворотний перехід до попередньої екстремальній точці не може проводитися.
Таким чином, відшукання оптимального рішення починається з деякою допустимої кутової точки, і всі переходи здійснюються тільки до суміжних точкам, причому перед новим переходом кожна з отриманих точок перевіряється на оптимальність.
Визначимо простір рішень і кутові точки агебраіческі. Необхідні соотнощшенія встановлюються із зазначеного в таблиці відповідності геометричних і алгебраїчних визначень.
Геометричне визначення
Алгебраїчне визначення (симплекс метод)
Простір рішень
Обмеження моделі стандартної форми
Кутові точки
Базисне рішення задачі в стандартній формі
Представлення простору рішень стандартної задачі лінійного програмування.
Лінійна модель, побудована для нашої задачі і наведена до ...
