Симплекс-метод розв’язування задач ЛП. Початковий опорний план
Зміст
Вступ
Симплекс-метод
Симплекс-метод - алгоритм рішення оптимізаційної задачі лінійного програмування шляхом перебору вершин опуклого багатогранника в багатовимірному просторі. Метод був розроблений американським математиком Джорджем Данцигом (George Dantzig) в 1947 році. Задача лінійного програмування полягає в тому, що необхідно максимізувати або мінімізувати деякий лінійний функціонал на багатовимірному просторі при заданих лінійних обмеженнях.
Зауважимо, що кожне з лінійних нерівностей на змінні обмежує півпростір у відповідному лінійному просторі. В результаті всі нерівності обмежують деякий багатогранник (можливо, нескінченний), називаний також поліедральних конусом. Рівняння Неможливо розібрати вираз (невідома помилка): W(x) = c , де Неможливо розібрати вираз (невідома помилка): W(x)
- максімізіруемий (або мінімізіруемий) лінійний функціонал, породжує гіперплоскость Неможливо розібрати вираз (невідома помилка): L(c)
. Залежність від Неможливо розібрати вираз (невідома помилка): c
породжує сімейство паралельних гіперплоскостей. Тоді екстремальна задача набуває наступне формулювання - потрібно знайти таке найбільше Неможливо розібрати вираз (невідома помилка): c
, що гіперплоскость Неможливо розібрати вираз (невідома помилка): L(c)
перетинає багатогранник хоча б в одній точці. Зауважимо, що перетин оптимальної гіперплоскості і багатогранника буде містити хоча б одну вершину, причому, їх буде більше однієї, якщо перетин містить ребро або k-мірну грань. Тому максимум функціоналу можна шукати в вершинах багатогранника. Принцип симплекс-методу полягає в тому, що вибирається одна з вершин багатогранника, після чого починається рух по його ребрах від вершини до вершини в бік збільшення значення функціоналу. Коли перехід по ребру з поточної вершини в іншу вершину з більш високим значенням функціоналу неможливий, вважається, що оптимальне значення c знайдено.
Послідовність обчислень симплекс-методом можна розділити на дві основні фази:
- знаходження вихідної вершини безлічі припустимих рішень,
- послідовний перехід від однієї вершини до іншої, що веде до оптимізації значення цільової функції.
При цьому в деяких випадках оригінал рішення очевидно або його визначення не вимагає складних обчислень, наприклад, коли всі обмеження представлені нерівностями виду "менше або дорівнює" (тоді нульовий вектор абсолютно точно є припустимим рішенням, хоча і, швидше за все, далеко не найбільш оптимальним) . У таких завданнях першу фазу симплекс-методу можна взагалі не проводити. Симплекс-метод, відповідно, ділиться на однофазний і двофазний.
Основна ідея симплекс-метода
Основна ідея симплекс-метода полягає в тому, що екстремум цільової функції завжди досягається в кутових точках області допустимих рішень. Симплекс-метод, званий також методом послідовного поліпшення плану, реалізує перебір кутових точок області допустимих рішень у напрямі поліпшення значення цільової функції. Основна ідея цього методу наступна. Перш за все, знаходиться яке-небудь допустиме початкове (опорное) рішення, тобто яка-небудь кутова точка області допустимих рішень. Процедура методу дозволяє відповісти на питання, чи є це рішення оптимальним. Якщо "так", то завдання вирішене. Якщо "ні", то виконується перехід до суміжної кутової точки області допустимих рішень, де значення цільової функції поліпшується, тобто до негіршого допустимого рішення. Якщо деяка кутова крапка має декілька суміжних, то обчислювальна процедура методу забезпечує перехід до тієї з них, для якої поліпшення цільової функції буде найбільшим. Процес перебору кутових точок області допустимих рішень повторюється, поки не буде знайдена крапка, якою відповідає екстремум цільової функції Е.
При побудові початкового базису в заданому завданні використовувався метод штучного базису, тому знайдене рішення не є допустимим. В цьому випадку для вирішення завдання необхідно використовувати двохетапний симплекс-метод.
Двохетапний симплекс-метод
Двохетапний симплекс-метод. Завдання за допомогою цього методу вирішується в два етапи: спочатку відшукується початкове допустиме рішення, що не містить штучних змінних, а потім на основі знайденого рішення шукається оптимальне рішення початкової задачі. Основні кроки, реалізації методу наступні.
- Завдання лінійного програмування зводиться до стандартної форми.
- Будується штучний базис.
- Складається штучна цільова функція: сума всіх штучних змінних.
- Реалізується перший етап двохетапного методу: за допомогою звичайних процедур симплекс-метода виконується мінімізація штучної цільової функції. Якщо її мінімальне значення рівне 0, то відповідне рішення є допустимим рішенням початкової задачі. Очевидно, що при нульовому значенні штучної цільової функції всі штучні змінні також нульові (оскільки штучна цільова функція - їх сума, і всі вони ненегативні). Якщо мінімальне значення штучної цільової функції виявляється відмінним від нуля, це означає, що завдання не має допустимих рішень.
- Реалізується другий етап двохетапного методу: знайдене на кроці 4 допустиме рішення використовується як початкове рішення початкової задачі для пошуку її оптимального рішення.
Опорний план
Опорний план — розв'язок системи лінійних обмежень в задачі лінійного програмування, який неможливо представити у вигляді лінійної комбінації будь яких інших розв'язків.
Система обмежень задачі лінійного програмування в канонічній формі має вигляд:
Неможливо розібрати вираз (невідома помилка): \sum_{j=1}^nA_ix_i = B; x_j\geq0,j=1,\ldots,n
де Неможливо розібрати вираз (невідома помилка): B=(b_1,\ldots,b_m)^T, A_j=(A_1j,\ldots,A_mj)^T, (j=1,\ldots,n)
- відомі вектори, Т - знак транспонування, а Неможливо розібрати вираз (невідома помилка): X = (x_1,\ldots,x_n) - вектор змінних.
