lign="justify"> Найчастіше потрібно неотрицательность змінних (необов'язково наявність саме таких умов для параметрів), в такому випадку з'являється додатково n умов:
. (3)
Можна показати, що канонічна задача має рішення, якщо визначник матриці коефіцієнтів буде ненульовим. При тому буде єдине рішення, якщо m=n . Цей факт очевидно випливає з теореми Крамера. Якщо ж m < n , то залишиться n - m незалежних змінних, інші виражаються через них зважаючи лінійної залежності. Таким чином, при перетворенні цільової функції f (x) , виходить нова функція f 1 (k) , де - незалежні змінні. Притому завдання оптимізації зводиться до пошуку оптимального набору, при якому функція f 1 (k 0 ) буде максимальною або мінімальною без будь-яких обмежень. Таким чином, при m < n , основну канонічну задачу лінійного програмування з n змінними можна привести до загальної задачі з n - m незалежними змінними і обмеженнями (3).
Якщо ж умови g j (x) є нерівностями, то можна за допомогою введення додаткових змінних (2) перетворити в (2 *):
прі.
Дане перетворення «канонізує» задачу, однак збільшується її розмірність.
Покажемо, що у загальної задачі з обмеженнями (3) або одне рішення, або жодного. Обчислимо першу похідну по кожній змінної - зважаючи лінійності (1) похідними будуть коефіцієнти при x i ; якщо всі коефіцієнти будуть негативними, то буде існувати лише максимум функції, якщо позитивні - тільки мінімум (рис 1).
Притому максимум або мінімум буде спостерігатися на початку координат. Якщо коефіцієнти будуть мати різні знаки, то екстремуму не існує.
Покажемо тепер, що екстремум цільової функції (1), якщо він існує, знаходиться на перетині гіперплоскостей (перетин n гіперплоскостей в n-вимірному просторі дає точку, звану вузлом).
Дане твердження вірно зважаючи монотонності цільової функції: достатньо взяти два вузла, з'єднані ребром. При русі від одного вузла до іншого монотонно змінюється значення функції. Якщо є такий вузол, що значення функції більш не збільшується або не зменшується, то в цій точці спостерігається максимум або мінімум.
Основним методом лінійної оптимізації є симплекс-метод, розроблений американським математиком Джорджем Данцигом. Він полягає в переборі вершин n-мірного багатогранника для пошуку оптимального набору параметрів.
Для початку зауважимо, що рівняння (1) породжує гіперплоскость L (F (x)) . Для зручного запису позначимо F (x)=S . Залежність від S породжує сімейство паралельних гіперплоскостей. Тоді екстремальна завдання набуває наступне формулювання - потрібно знайти таке найбільше ...
