і на максимум шляхом множення цільової функції f (x) на - 1.
Поділ обмежень на (1) і (2) також не носить принципового характеру, оскільки кожне з них може бути записано в одному з цих двох видів, але іноді виявляється корисним.
Окремим випадком задачі (4) є завдання лінійного програмування, для якої функції f (x), gi (x) є лінійними, а безліч R - ненегативним ортантом. Таким чином, задача лінійного програмування полягає в знаходженні максимуму лінійної функції f (x) на багатогранному безлічі Х. При цьому для знаходження максимуму достатньо перебрати вершини множини Х, число яких звичайно. Методи лінійної алгебри дозволяють досить ефективно описувати ці вершини, що і використовується в загальному методі вирішення завдань лінійного програмування - симплекс-методі, реализующем спрямований перебір вершин [1].
Другий важливий окремий випадок задачі (4) - завдання опуклого програмування, для якої безліч Х є опуклим, а функція f (x) - увігнутою (для задачі на мінімум опуклою). Для опуклості Х досить опуклості множини R і угнутості функцій gi (x).
Істотною властивістю завдання опуклого програмування є те, що будь-який локальний максимум увігнутої функції f (x) є і глобальним максимумом (для опуклої функції це справедливо для мінімумів). Це та інші властивості завдання опуклого програмування істотно полегшують її рішення, так як більшість чисельних методів забезпечує знаходження тільки локальних екстремумів. Зауважимо, що завдання лінійного програмування є окремим випадком опуклого програмування, але властивість лінійності настільки специфічно, що дозволяє застосовувати спеціальні методи.
Лінійне і опукле програмування є найбільш розробленими розділами математичного програмування. Існують і інші розділи зі своїми спеціальними методами (цілочисельне, геометричне, динамічне програмування і т.д.).
Що стосується загальної задачі математичного програмування, то її рішення пов'язане з великими складнощами, так як універсальні методи, як правило, малоефективні. Тому розвиток математичного програмування йде в основному по шляху виділення спеціальних класів задач і розробки відповідних їм методів.
(x, y0) # F (x0, y0) # F (x0, y)" xk R, yk Y.
Теорема подвійності. Якщо функція Лагранжа F (x, у) для задачі (4) має седловую точку (x0, у0) на прямому творі множин R i Y, то справедливо співвідношення подвійності (7), причому х0 є рішенням задачі (4), а у0 -рішенням двоїстої задачі.
Співвідношення подвійності дозволяє звести рішення задачі (4) до вирішення двоїстої задачі, яка іноді виявляється простіше. Наприклад, двоїста задача до задачі лінійного програмування теж є лінійною, причому вона може мати меншу розмірність, що дозволяє будувати більш ефективні методи рішення (на цій ідеї заснований двоїстий симплекс-метод, см. [1]). Крім того, співвідношення подвійності дозволяє встановити сам факт існування рішення (наприклад, наявність хоча б по одному допустимому планом у двоїстих задач лінійного програмування гарантує існування оптимальних планів), проаналізувати чутливість рішення до малих змін параметрів задачі.
На жаль, співвідношення подвійності справедливо далеко не завжди. Серед широких класів задач математичного програмування в цьому плані можна виділити лінійне програмування (з...
