значень лінійної функції, на невідомі якої накладено лінійні обмеження. Таким чином, завдання лінійного програмування відносяться до завдань на умовний екстремум функції. p align="justify"> Розглянемо коротко два методи розв'язання задач лінійного програмування: графічний і симплекс-метод; також розглянемо транспортну задачу, яка теж є задачею лінійного програмування і може бути вирішена симплекс-методом, але оскільки вона має своєрідну матрицю обмежень, то для неї розроблені спеціальні методи рішення.
Графічний метод досить простий і наочний для вирішення завдань лінійного програмування з двома змінними. Він заснований на геометричному поданні допустимих рішень і цільової функції задачі. p align="justify"> Кожне з нерівностей задачі лінійного програмування визначає на координатній площині деяку напівплощина, а система нерівностей в цілому - перетин відповідних площин. Безліч точок перетину даних півплощин називається областю допустимих рішень (ОДР). ОДР завжди являє собою опуклу фігуру. p align="justify"> Вектор C = (c 1 , c 2 ) з координатами з коефіцієнтів цільової функції при x 1 і x 2 перпендикулярний до кожної з ліній рівня. Напрямок вектора C збігається з напрямком зростання цільової функції, що є важливим моментом для вирішення завдання. Напрямок убування цільової функції протилежно напрямку вектора C.
Суть графічного методу полягає в наступному. У напрямку (проти напрямку) вектора C в ОДР проводиться пошук оптимальної точки x * = (x 1 *, x 2 *). Оптимальною вважається точка, через яку проходить лінія рівня L max (L min ), відповідна найбільшому (найменшому) значенню функції L (x). Оптимальне рішення завжди знаходиться на кордоні ОДР, наприклад, в останній вершині багатокутника ОДР, через яку пройде цільова пряма, або на всій його боці.
Симплекс-метод - алгоритм рішення оптимізаційної задачі лінійного програмування шляхом перебору вершин опуклого багатогранника в багатовимірному просторі.
Суть симплекс-методу полягає в наступному:
. Знаходять-яке допустиме базисне рішення. Його можна знайти, прийнявши будь-які mn змінні за вільні, прирівнявши їх до нуля і вирішивши вийшла систему рівнянь. Якщо при цьому деякі з базисних змінних виявляться негативними, то потрібно вибрати інші вільні змінні, тобто перейти до нового базису.
. Перевіряють, чи не чи досягнуто вже максимум цільової функції ...
