2. Основні теореми лінійного програмування

Для обґрунтування методів рішення задач лінійного програмування сформулюємо ряд найважливіших теорем, опускаючи їхні аналітичні докази. Усвідомити зміст кожної з теорем допоможе поняття про геометричну інтерпретацію рішення ЗЛП, дане в попередньому підрозділі.

Однак спочатку нагадаємо про деякі поняття, важливі з погляду подальшої розмови:

1. Будь-які m змінних системи m лінійних рівнянь із n змінними (m < n) називаються основними, якщо визначник матриці коефіцієнтів при них відмінний від нуля. Тоді інші m-n змінних називаються неосновними (або вільними).

2. Базисним рішенням системи m лінійних рівнянь c n змінними (m < n) називається всяке її рішення, у якому всі неосновні змінні мають нульові значення.

Теорема 1. Множина всіх припустимих рішень системи обмежень задачі лінійного програмування є опуклою.

В окремому випадку, коли в систему обмежень входять тільки дві змінні x₁ і x₂, цю множину можна зобразити на площині. Оскільки мова йде про припустимі рішення (x₁, x₂  0), то відповідна множина буде розташовуватися в першій чверті декартової системи координат. Ця множина може бути замкнутою (багатокутник), незамкнутою (необмежена багатогранна область), складатися з єдиної точки й, нарешті, система обмежень-нерівностей може бути несумісною.

Теорема 2. Якщо задача лінійного програмування має оптимальне рішення, то воно співпадає з однією (двома) із кутових точок множини припустимих рішень.

З теореми 2 можна зробити висновок про те, що одиничність оптимального рішення може порушуватися, причому, якщо рішення не єдине, то таких оптимальних рішень буде незліченна множина (всі точки відрізка, що з'єднує відповідні кутові точки).

Теорема 3. Кожному припустимому базисному рішенню задачі лінійного програмування відповідає кутова точка області припустимих рішень, і навпаки.

Наслідком з теорем 2 і 3 є твердження про те, що оптимальне рішення (оптимальні рішення) задачі лінійного програмування, заданої (або приведеної) обмеженнями-рівняннями, збігається із припустимим базисним рішенням (припустимими базисними рішеннями) системи обмежень.

Таким чином, оптимальне рішення ЗЛП варто шукати серед кінцевого числа припустимих базисних рішень.

3. Симплексний метод рішення злп

Симплекс-Метод був розроблений і вперше застосований для рішення задач в 1947 р. американським математиком Дж. Данцигом.

Симплексний метод на відміну від геометричного універсальний. З його допомогою можна вирішити будь-яку задачу лінійного програмування.

В основу симплексного методу покладена ідея послідовного поліпшення одержуваного рішення.

Геометричний зміст симплексного методу складається в послідовному переході від однієї вершини багатогранника обмежень до сусіднього, у якій цільова функція приймає краще (або, принаймні, не гірше) значення доти, поки не буде знайдене оптимальне рішення - вершина, де досягається оптимальне значення функції мети (якщо задача має кінцевий оптимум).

Таким чином, маючи систему обмежень, приведену до канонічної форми (всі функціональні обмеження мають вигляд рівностей), знаходять будь-яке базисне рішення цієї системи, піклуючись тільки про те, щоб знайти його як можна простіше. Якщо перше ж знайдене базисне рішення виявилося припустимим, то перевіряють його на оптимальність. Якщо воно не є оптимальним, то здійснюється перехід до іншого, обов'язково припустимого базисного рішення. Симплексний метод гарантує, що при цьому новому рішенні цільова функція, якщо й не досягне оптимуму, то наблизиться до нього (або, принаймні, не вийде від нього). З новим припустимим базисним рішенням роблять так само, поки не відшукається рішення, що є оптимальним.

Процес застосування симплексного методу припускає реалізацію трьох його основних елементів:

1) приведення обмежень до канонічної форми;

2) спосіб визначення якого-небудь початкового припустимого базисного рішення задачі;

3) правило переходу до кращого (точніше, не гіршого) рішення;

4) критерій перевірки оптимальності знайденого рішення.

Симплексний метод містить у собі ряд етапів і може бути сформульований у вигляді чіткого алгоритму (чіткого припису про виконання послідовних операцій). Це дозволяє успішно програмувати й реалізовувати його на ЕОМ. Задачі з невеликим числом змінних і обмежень можуть бути вирішені симплексним методом вручну.

Далі розглянемо симплексний алгоритм, не заглиблюючись у його обґрунтування.