1. Сутність і методи лінійного програмування
Лінійне програмування використовує математичний інструментарій, який базується на теорії і методах вирішення задач про екстремуми лінійних функцій, що задаються системами лінійних рівнянь. В цілому, термін «програмування» визначається як «планування».
Найбільш універсальним методом лінійного програмування є диференціальний алгоритм, який дозволяє вирішувати будь-які задачі лінійного програмування. Поряд з цим, може для вирішення цих задач можуть використовуваться і графічний метод, який відзначається простотою і наочністю, але потребує графічних побудов. Для вирішення задач лінійного програмування, які визначаються транспортними, може бути використаний метод потенціалів.
Сутність методу лінійного програмування базується на принципі аналізу і послідовного поліпшення деякого початкового плану розподілу і використання ресурсів. Зокрема, план поліпшують до тих пір, поки не буде знайдений найкращий (оптимальний) варіант. Алгоритм використання методів лінійного програмування наступний:
спочатку складають початковий план, який аналізується за конкретними строго розробленими правилами;
використовуючи результати аналізу визначають можливість і напрямок поліпшення початкового варіанта плану;
обчислюють новий план, який аналізується і здійснюються процедури щодо поліпшення з метою наближення до оптимального результату;
процес визначення оптимального результату здійснюється до отримання найбільш оптимального результату.
В процесі розв’язання задач лінійного програмування використовується симплекс-метод, який полягає в тому, що, відправляючись з деякої довільної вершини багатокутника обмежень, переходять до обчислення тільки такої вершини, в якій значення лінійної форми буде більше, ніж у попередній. Решту варіантів не обчислюють. Тоді при кінцевому порівняно малому числі кроків може бути знайдений оптимальний план. Таким чином, проводиться впорядкований перебір вершин, при якому відбувається постійне збільшення лінійної форми. У цьому аспекті симплексний метод називається також методом послідовного поліпшення плану.
Вирішення задач лінійного програмування симплекс-методом полягає:
по-перше, в розробці базового рішення на оптимальність. Якщо воно оптимальне, то задача вирішена, в іншому випадку виконують другий етап;
по-друге, визначають вектор Ак , який повинен бути введений в базис, і вектор Аr , який повинен бути виключений з нього, тобто виходить новий базисний план з великим значенням лінійної форми. Щоб знайти вектори Ак і Аr заміна яких забезпечує найбільше зростання лінійної форми, виразимо всі вектори, що не входять в базис, через базисні вектори.
(3.1)
Де aij - проекції вектора Aj на вектор Аi Запишемо систему обмежень у векторній формі в наступному вигляді:
Оскільки
(3.2)
Співвідношення (3.2) дає рішення тільки у тому випадку, коли коефіцієнти при векторах Аi і Aк нового базису будуть ненегативними, тобто
(3.3)
Відповідне нове значення лінійної форми набуває вигляду .
Позначимо (3.4)
(3.5)
Тоді значення лінійної форми в новій вершині багатокутника рішення можна знайти з рівняння
(3.6)
Величину dj називають оцінкою плану. В симплексному методі параметри dj відіграють важливу роль: їх знаки дозволяють визначити, чи є опорний план оптимальним. Якщо dj >0 для всіх j то даний опорний план є оптимальним, оскільки на підставі (3.6) і зважаючи на 0 > 0 перехід до будь-якої нової вершини веде до убування лінійної форми. Якщо опорний план неоптимальний, то можливі два випадки:
Є хоча б одйн індекс j = k для якого dk < 0 і всі відповідні компоненти
aik <0(i=1,m). У цьому випадку лінійна форма не обмежена зверху і задача нерозв'язна.
Для деяких j dj < 0 і для кожного такого j, принаймні, одна з проекцій aij >0. Тоді при переході до наступної вершини лінійна форма зростає і план поліпшується. Для найшвидшого зростання L необхідно в базис включити той вектор Aк, для якого оцінка dк < 0 і максимальна за модулєм, а вектор Ar для якого значення позитивно і мінімально, виключити.
При лінійному програмуванні також використовують методи еліпсоїдів, метод внутрішніх точок, методи логарифмічних бар'єрних функцій нелінійного програмування. У цих методах вирішення задач лінійного програмування здійснюють шляхом пошуку уздовж траєкторій у просторі змінних задачі, що не проходять через вершини багатокутника.
Особливості задач лінійного програмуванння та практичні аспекти іх вирішення.