Постановка завдання лінійного програмування і двоїста завдання лінійного программирования

Постановка завдання лінійного програмування і двоїста завдання лінійного программирования.

Лінійне програмування є складовою розділу математики, який вивчає методи перебування умовного экстремума функції багатьох змінних і називається математичним програмуванням. У класичному математичному аналізі розглядається завдання відшукання умовного экстремума функції. Проте, час показало, що завдань, виникаючих під впливом запитів практики, класичні методи недостатні. У зв’язку з розвитком техніки, зростанням промислового виробництва та з приходом ЕОМ усі великій ролі почали грати завдання відшукання оптимальних рішень на різні сфери людської діяльності. Основним інструментом під час вирішення з завдань стало математичне моделювання — формальне опис досліджуваного явища як дослідження з допомогою математичного аппарата.

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

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

Основні форми завдання ЛП.

Розрізняють три основні форми завдань лінійного програмування в залежність від наявності обмежень різного типа.

Стандартна завдання ЛП.

[pic] чи, в матричної записи,.

[pic] де [pic]— матриця коефіцієнтів. Вектор [pic]называется вектором коефіцієнтів лінійної форми, [pic]— вектором ограничений.

Стандартна завдання важлива через наявність значної частини прикладних моделей, зводяться якомога природнішим чином цього класу завдань ЛП.

Канонічна завдання ЛП.

[pic] чи, в матричної записи,.

[pic].

Основні обчислювальні схеми вирішення завдань ЛЗ розроблено саме з канонічної задачи.

Загальна завдання ЛП.

У цьому завдання частина обмежень більшою мірою кримінальна нерівностей, а частина є рівняннями. З іншого боку, не так на все перемінні накладено умова неотрицательности:

[pic].

Тут [pic]. Зрозуміло, що стандартна завдання виходить як приватний випадок загальної при [pic]; канонічна — при [pic].

Усі три перелічені завдання еквівалентні тому, що кожну з на них можна простими перетвореннями призвести до кожній із двох остальных.

Під час вивчення завдань ЛЗ склалася терминалогия. Лінійна форма [pic], підлягаючий максимізації (чи мінімізації), називається цільової функцією. Вектор [pic], зрозумілу всім обмеженням завдання ЛЗ, називається допустимим вектором, чи планом. Завдання ЛЗ, на яку існують допустимі вектори, називається припустимою завданням. Допустимий вектор [pic], котрий завдавав найбільше значення цільової функції порівнянню з іншою допустимим вектором [pic], тобто. [pic], називається рішенням завдання, чи оптимальним планом. Максимальне значення [pic]целевой функції називається значенням задачи.

Двоїста завдання лінійного программирования.

Розглянемо завдання ЛП.

[pic](1) чи, в матричної записи,.

[pic](2).

Завданням, двоїстої до (1) (двоїстої завданням), називається завдання ЛЗ від [pic] змінних [pic] вида.

[pic](3) чи, в матричної записи,.

[pic](4) де [pic].

Правила побудови завдання (3) формою записи завдання (1) такі: в завданню (3) змінних [pic] стільки ж, скільки рядків матриці [pic] завдання (1). Матриця обмежень у (3) — транспортированная матриця [pic]. Вектор правій частині обмежень у (3) служить вектором коефіцієнтів максимизируемой лінійної формі в (1), у своїй знаки нерівностей змінюються на рівність. Навпаки, як цільової функції в (3) виступає лінійна форма, коефіцієнтами якої задаються вектором правій частині обмежень завдання (1), у своїй максимізація змінюється на мінімізацію. На двоїсті перемінні [pic] накладається умова неотрицательности. Завдання (1), в відмінність від двоїстої завдання (3) називається прямой.

Теорему двоїстості. Якщо взаимодвойственные завдання (2), (4) припустимі, всі вони обидві мають рішення і однакове значение.

Теорему рівноваги. Нехай [pic]— оптимальні плани прямий (1) і двоїстої (3) завдань відповідно. Тоді якщо [pic] то.

[pic].