Симплексный метод решения задачи линейного программирования

Симплексний-метод вирішення задачі лінійного програмування

Геометрична інтерпретація, якою ми користувалися при вирішенні завдань лінійного програмування, перестає бути придатною для цієї мети при числі вільних змінних n - m > 3, а скрутна вже при n - m = 3. Для знаходження рішення задачі лінійного програмування в загальному випадку (при довільному числі вільних змінних) застосовуються не геометричні, а обчислювальні методи. З них найбільш універсальним є так званий симплекс-метод.

Ідея симплекс-методу відносно проста. Хай в завданні лінійного програмування є п змінних і т незалежних лінійних обмежень, заданих у формі рівнянь. Ми знаємо, що оптимальне рішення (якщо воно існує) досягається в одній з опорних точок (вершин ОДР), де принаймні до = n - m із змінних дорівнюють нулю. Виберемо якісь до змінних як вільні і виразимо через них останні т базисних змінних. Хай, наприклад, як вільні вибрані перші до = n - m змінних  а

останні m виражені через них:

  (2. 22)

Передбачимо, що всі вільні змінні  дорівнюють нулю.

При цьому ми отримаємо:

 

Це рішення може бути допустимим або недопустимим. Воно допустиме, якщо всі вільні члени ненегативні. Передбачимо, що ця умова виконана. Тоді ми отримали опорне рішення. Але чи є воно оптимальним? Аби перевірити це, виразимо цільову функцію Z через вільні змінні

  (2. 23)

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

Хай, наприклад, коефіцієнт в (2. 23) негативний. Значить, є сенс збільшити, тобто перейти від даного опорного рішення до іншого, де змінна не дорівнює нулю, а замість неї дорівнює нулю якась інша. Проте збільшувати слід з обережністю, так аби не стали негативними інші змінні виражені через вільні змінні, зокрема через формулами (2. 22).

Наприклад, якщо коефіцієнт при у відповідному  рівнянні (2. 22) негативний, то збільшення може зробити  негативним. Навпаки, якщо серед рівнянь (2. 22) немає рівняння з негативним коефіцієнтом при те величину   можна збільшувати безмежно, а, означає, лінійна функція Z не обмежена знизу і оптимального рішення ОЗ не існує.

Допустимо, що це не так і що серед рівнянь (2. 22) є такі, в яких коефіцієнт при негативний. Для змінних, що стоять в лівих частинах цих рівнянь, збільшення  небезпечне — воно може зробити їх негативними.

Візьмемо одну з таких змінних і поглянемо, до якої міри можна збільшити, поки змінна не стане негативною. Випишемо рівняння з системи (2. 22):

 

Тут вільний член, а коефіцієнт негативний.

Легко зрозуміти, що якщо ми залишимо, то можна збільшувати лише до значення, рівного а при подальшому збільшенні змінна стане негативною.

Виберемо ту із змінних яка раніше всіх перетвориться на нуль при збільшенні тобто ту, для якої величина найменша. Хай це буде Тоді має сенс вирішити систему рівнянь (2. 22) відносно інших базисних змінних, виключаючи з числа вільних змінних і переводячи замість неї в групу вільних змінних Дійсно, ми хочемо перейти від опорного рішення, що задається рівністю до опорного рішення, в якому вже а   Перше опорне рішення

1 2

Похожие работы

Рефераты

Курсовые

Дипломные