Ректорська контрольна робота

З дисципліни: «Економіко-математичне моделювання»

Варіант 2

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 перехід до будь-якої нової вершини веде до убування лінійної форми. Якщо опорний план неоптимальний, то можливі два випадки:

1. Є хоча б одйн індекс j = k для якого dk < 0 і всі відповідні компоненти

aik <0(i=1,m). У цьому випадку лінійна форма не обмежена зверху і задача нерозв'язна.

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

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

Особливості задач лінійного програмуванння та практичні аспекти іх вирішення.