/i> справедливо f (Х В°) ≥ f (X) (локальний максимум) або f (Х В°) ≤ f (X) (локальний мінімум).
Обгрунтоване застосування кількісних методів для прийняття рішень - оптимізацію поведінки структур систем називають дослідженням операцій (ІСО). Тут операція - комплекс цілеспрямованих дій.
Завдання, розглянута вище, вирішується із застосуванням математичної моделі системи, об'єднуючою згадані обмеження на ресурси і цільову функцію. Знаходження величин згаданих параметрів системи (вони входять в математичну модель як невідомі) шляхом рішення математичної задачі називають математичним програмуванням . Математичне програмування - найважливіша область математики, орієнтована на широке застосування комп'ютерів.
У Залежно від характеру цільової функції, а також обмежень можуть використовуватися різні методи оптимізації (математичного програмування): лінійне програмування, нелінійне програмування (хоча б одна з функцій нелінійна по X), цілочисельне лінійне програмування, динамічне програмування та ін
5.6 Завдання лінійного програмування
В
Одним з розділів математичного програмування є лінійне програмування. У моделях лінійного програмування так звана В«основна завдання В»полягає в знаходженні ненегативного рішення системи лінійних рівнянь або нерівностей (обмежень), яке мінімізує або максимізує лінійну форму (цільову функцію). Математична задача лінійного програмування записується у скороченому вигляді наступним чином:
В В
Геометрична інтерпретація задачі ЛП
Задача лінійного програмування геометрично може бути проілюстрована наступним чином.
Нехай необхідно знайти мінімум цільової функції:
В
Змінні x 1 і x 2 повинні бути невід'ємними.
Тому безліч точок, які є можливими (допустимими) рішеннями, може знаходитися у першому квадраті (див. рис. 4.6.1.). Нерівності-обмеження зображені у вигляді півплощин, межами яких є прямі (графіки функцій), отримані з нерівностей шляхом відкидання знаків > , <. Напівплощини утворюють опуклий багатокутник (багатокутник рішень - симплекс).
Лінійна форма (лінія рівня) для деякого набору фіксованих значень змінної z являє собою сімейство паралельних прямих. Одна з них, яка пройде через вершину багатокутника В«МВ», найближчу до початку координат і дасть мінімум z (Для координат вершини). p> Графічний спосіб вирішення (переміщення графіка цільової функції з симплекс) прийнятний тільки для двомірних завдань (завдань на площині). Але геометричне тлумачення задачі лінійного програмування справедливо і для загального випадку (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 ...
