рограмування так звана В«основне завданняВ» полягає в знаходженні ненегативного рішення системи лінійних рівнянь або нерівностей (обмежень), яке мінімізує або максимізує лінійну форму (цільову функцію). Математична задача лінійного програмування записується у скороченому вигляді наступним чином:
В
Геометрична інтерпретація задачі ЛП
Задача лінійного програмування геометрично може бути проілюстрована наступним чином.
Нехай необхідно знайти мінімум цільової функції:
В
Змінні x 1 і x 2 повинні бути невід'ємними.
Тому безліч точок, які є можливими (допустимими) рішеннями, може перебувати у першому квадраті (див. рис. 4.6.1.). Нерівності-обмеження зображені у вигляді півплощин, межами яких є прямі (графіки функцій), отримані з нерівностей шляхом відкидання знаків > , < . Напівплощини утворюють опуклий багатокутник (багатокутник рішень - симплекс).
Лінійна форма (лінія рівня) для деякого набору фіксованих значень змінної z являє собою сімейство паралельних прямих. Одна з них, яка пройде через вершину багатокутника В«МВ», найближчу до початку координат і дасть мінімум z (для координат вершини) .
Визначивши координати точки М (8/7; 4/7) отримаємо: z = 2 серпня/7 + 4 березня/7 = 4.
Основна ідея методів вирішення завдань ЛЗ
Графічний спосіб вирішення (переміщення графіка цільової функції з симплекс) прийнятний тільки для двомірних завдань (завдань на площині). Але геометричне тлумачення задачі лінійного програмування справедливо і для загального випадку (m обмежень і n змінних). Кожне з відповідних нерівності рівнянь системи визначає деяку гіперплощина в n - вимірному просторі. Безліч невід'ємних рішень утворює опуклий багатогранник в n - вимірному просторі. Лінійна форма z -гіперплощина, переміщаючи яку паралельно самій собі, будемо отримувати безліч точок перетину її з опуклим багатогранником. Максимальне або мінімальне значення лінійної форми z досягається в точках, які є вершинами опуклого багатогранника.
У силу труднощі вирішення завдання графічним способом у випадку m обмежень і n> 2 змінних застосовують інші методи розв'язання задачі ЛП. Найбільш поширеним і зручним є симплекс метод рішення задачі ЛП.
Для вирішення завдання лінійного програмування симплекс-методом застосовується спеціальний апарат формальних перетворень математичної моделі. Розглянемо деякі його положення. Нехай задана основна задача лінійного програмування (див. (4.6.1.) І (4.6.2)). Ввівши в ліву частину кожного нерівності додаткову змінну, перетворимо його в рівняння і перейдемо до іншої, стандартній формі запису:
В
При цьому значення b i повинні бути невід'ємними. У разі b i < 0 обидві частини рівняння множать на В»- 1В». Зауважимо, що при максимізації z завдання зводиться до стандартної шляхом заміни: max z = - min (- z ).
Систему (4.6.3) після нескладних перетворень можна привести до вигляду:
В
Тут b i ? 0. Коефіцієнти при змінних рівні одиниці (+1). Дана система представлена ​​в канонічній формі запису. Якщо кількість змінних перевищує кількість рівнянь, то існує незліченна безліч рішень системи .
Нехай m
а) основні змінні, кількість яких має дорівнювати кількості лінійно-незалежних змінних (m);
б) неосновні змінні, кількість яких дорівнюватиме n - m.
Визначимо перші m змінних ( x 1 , x 2 , ..., x m ) в якості основних. Тоді систему (4.6.4) можна вирішити відносно x 1 , x 2 , ..., x m , ...
