lign="justify">) , яка носить назву
цільової функції. Ставиться завдання: знайти екстремум (максимум чи мінімум) цільової функції f (x) за умови, що змінні x належать деякій області G :
1.2 Симплекс-0метод
Симплекс-метод є основним у лінійному програмуванні . Рішення завдання починається з розглядів однієї з вершин багатогранника умов. Якщо досліджувана вершина не відповідає максимуму (мінімуму), то переходять до сусідньої, збільшуючи значення функції мети при вирішенні задачі на максимум і зменшуючи при вирішенні завдання на мінімум. Таким чином, перехід від однієї вершини до іншої покращує значення функції мети. Так як число вершин багатогранника обмежена, то за кінцеве число кроків гарантується знаходження оптимального значення або встановлення того факту, що завдання нерозв'язна.
Цей метод є універсальним, застосовним до будь-якій задачі лінійного програмування у канонічної формі . Система обмежень тут - система лінійних рівнянь, в якій кількість невідомих більше кількості рівнянь. Якщо ранг системи дорівнює r , то ми можемо вибрати r невідомих, які висловимо через інші невідомі. Для визначеності припустимо, що обрані перші, що йдуть підряд, невідомі X 1 , X 2 , ..., X r . Тоді наша система рівнянь може бути записана як
В
До такого виду можна навести будь-яку спільну систему , наприклад, методом Гаусса. Правда, не завжди можна виражати через інші перші r невідомих (ми це зробили для визначеності запису). Однак такі r невідомих обов'язково знайдуться. Ці невідомі (змінні) називаються базисними, решта вільними.
Надаючи певні значення вільним змінним і обчислюючи значення базисних (виражених через вільні), ми будемо отримувати різні рішення нашої системи обмежень. Таким чином, можна отримати будь-яке її рішення. Нас будуть цікавити особливі рішення, одержувані у випадку, коли вільні змінні дорівнюють нулю. Такі рішення називаються базисними , їх стільки ж, скільки різних базисних видів у даної системи обмежен...
