br />
1.2 Симплекс метод рішення завдань лінійного програмування
Симплекс-метод був розроблений і вперше застосований для вирішення завдань в 1947 р. американським математиком Дж. Данцигом.
Двовимірні задачі лінійного програмування вирішуються графічно. Для випадку N=3 можна розглянути тривимірний простір і цільова функція буде досягати своє оптимальне значення в одній з вершин багатогранника.
Припустимим рішенням (допустимим планом) задачі ЛП, даної в стандартній формі, називається упорядкований безліч чисел (х1, х2, ..., хn), які відповідають обмеженням; це точка в n-вимірному просторі.
Безліч допустимих рішень утворює область допустимих рішень (ОДР) задачі ЛП. ОДР являє собою опуклий багатогранник (багатокутник).
У загальному вигляді, коли в задачі беруть участь N-невідомих, можна сказати, що область допустимих рішень, що задається системою обмежують умов, представляється опуклим многогранником в n-вимірному просторі і оптимальне значення цільової функції досягається в одній або декількох вершинах.
Базисним називається рішення, при якому всі вільні змінні дорівнюють нулю.
Опорна рішення - це базисне невід'ємне рішення. Опорне рішення може бути невиродженим і виродженим. Опорне рішення називається невиродженим, якщо число його ненульових координат одно рангу системи, в іншому випадку воно є виродженим.
Допустиме рішення, при якому цільова функція досягає свого екстремального значення, називається оптимальним і позначається.
Вирішити дані завдання графічно, коли кількість змінних більше 3 вельми скрутно. Існує універсальний спосіб вирішення завдань лінійного програмування, званий симплекс-методом.
Симплекс-метод - це універсальний метод вирішення завдань ЛЗ, що представляє собою ітераційний процес, який починається з одного рішення і в пошуках кращого варіанту рухається по кутовим точкам області допустимих рішень доти, поки не досягне оптимального значення.
З його допомогою можна вирішити будь-яке завдання лінійного програмування.
В основу симплексного методу покладена ідея послідовного поліпшення одержуваного рішення.
Геометричний сенс симплексного методу полягає в послідовному переході від однієї вершини багатогранника обмежень до сусідньої, в якій цільова функція приймає найкраще (або, по крайней мере, не найгірше) значення до тих пір, поки не буде знайдено оптимальне рішення - вершина, де досягається оптимальне значення функції мети (якщо завдання має кінцевий оптимум).
Таким чином, маючи систему обмежень, приведену до канонічної формі (всі функціональні обмеження мають вигляд рівностей), знаходять будь базисне рішення цієї системи, піклуючись тільки про те, щоб знайти його якомога простіше. Якщо перше ж знайдене базисне рішення виявилося допустимим, то перевіряють його на оптимальність. Якщо воно не оптимально, то здійснюється перехід до іншого, обов'язково допустимому базисного рішенням. Симплексний метод гарантує, що при цьому новому рішенні цільова функція, якщо і не досягне оптимуму, то наблизиться до нього (або, по крайней мере, не віддалиться від нього). З новим допустимим базисним рішенням чинять ж, поки не відшукається рішення, яке є оптимальним.
Процес застосування симплексного методу передбачає реалізацію трьох йог...
