Сутність і методи лінійного програмування

Лінійне програмування використовує математичний інструментарій, який базується на теорії і методах вирішення задач про екстремуми лінійних функцій, що задаються системами лінійних рівнянь. В цілому, термін «програмування» визначається як «планування».

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

Сутність методу лінійного програмування базується на принципі аналізу і послідовного поліпшення деякого початкового плану розподілу і використання ресурсів. Зокрема, план поліпшують до тих пір, поки не буде знайдений найкращий (оптимальний) варіант. Алгоритм використання методів лінійного програмування наступний:

- спочатку складають початковий план, який аналізується за конкретними строго розробленими правилами;

- використовуючи результати аналізу визначають можливість і напрямок поліпшення початкового варіанта плану;

- обчислюють новий план, який аналізується і здійснюються процедури щодо поліпшення з метою наближення до оптимального результату;

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

В процесі розв’язання задач лінійного програмування використовується симплекс-метод, який полягає в тому, що, відправляючись з деякої довільної вершини багатокутника обмежень, переходять до обчислення тільки такої вершини, в якій значення лінійної форми буде більше, ніж у попередній. Решту варіантів не обчислюють. Тоді при кінцевому порівняно малому числі кроків може бути знайдений оптимальний план. Таким чином, проводиться впорядкований перебір вершин, при якому відбувається постійне збільшення лінійної форми. У цьому аспекті симплексний метод називається також методом послідовного поліпшення плану.

Вирішення задач лінійного програмування симплекс-методом полягає:

- по-перше, в розробці базового рішення на оптимальність. Якщо воно оптимальне, то задача вирішена, в іншому випадку виконують другий етап;

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

(3.1)

де a_ij - проекції вектора на вектор. Запишемо систему обмежень у векторній формі в наступному вигляді:

Оскільки то

(3.2)

Співвідношення (3.2) дає рішення тільки у тому випадку, коли коефіцієнти при векторах і нового базису будуть ненегативними, тобто

і (3.3)

Відповідне нове значення лінійної форми набуває вигляду

Позначимо

(3.4)

(3.5)

Тоді значення лінійної форми в новій вершині багатокутника рішення можна знайти з рівняння

(3.6)

Величину d_j називають оцінкою плану. В симплексному методі параметри d_j відіграють важливу роль: їх знаки дозволяють визначити, чи є опорний план оптимальним. Якщо dj 0 для всіх j, то даний опорний план є оптимальним, оскільки на підставі (3.6) і зважаючи на q ³ 0 перехід до будь-якої нової вершини веде до убування лінійної форми. Якщо опорний план неоптимальний, то можливі два випадки:

1. Є хоча б один індекс j = k для якого d_k < 0 і всі відповідні компоненти У цьому випадку лінійна форма не обмежена зверху і задача нерозв'язна.

2. Для деяких j d_j < 0 і для кожного такого j, принаймні, одна з проекцій a_ij >0. Тоді при переході до наступної вершини лінійна форма зростає і план поліпшується. Для найшвидшого зростання L необхідно в базис включити той вектор , для якого оцінка d_k < 0 і максимальна за модулєм, а вектор , для якого значення позитивно і мінімально, виключити.

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