Симплекс-метод розв’язування задач ЛП. Початковий опорний план

Симплекс-метод

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

Нехай невироджену задачу лінійного програмування представлено в канонічному вигляді:

Неможливо розібрати вираз (невідома помилка): \sum_{j=1}^nc_jx_j\to\max ,

Неможливо розібрати вираз (невідома помилка): \sum_{j=1}^nA_jx_j=B, x_j\geq0, j=1,2,\ldots,n ,

де Неможливо розібрати вираз (невідома помилка): X=(x_1,\ldots,x_n)

- вектор змінних, Неможливо розібрати вираз (невідома помилка): C=(c_1,\ldots,c_n),B=(b_1,\ldots,b_m)^T,A_j=(a_{1j},\ldots,a_{mj})^T,j=1,\ldots,n
- задані вектори, Т - знак транспонування, та

Неможливо розібрати вираз (невідома помилка): \bar{X}=\bar{x_1},\ldots,\bar{x_m}

відмінні від нуля компоненти опорного плану, для полегшення пояснення розташовані на перших m місцях вектору Х. Базис цього плану:

Неможливо розібрати вираз (невідома помилка): \bar{A}=(A_1,\ldots,A_m) . Тоді

Неможливо розібрати вираз (невідома помилка): \sum_{i=1}^mA_i\bar{x_i}=B,(1)

Неможливо розібрати вираз (невідома помилка): \sum_{i=1}^mc_ix_i=\bar{z_0},(2) ,

де Неможливо розібрати вираз (невідома помилка): \bar{z_0}

значення лінійної форми на даному плані. Так як вектор-стовпці матриці A лінійно незалежні, будь який із векторів умов Неможливо розібрати вираз (невідома помилка): A_j
розкладається по них єдиним чином:

Неможливо розібрати вираз (невідома помилка): \sum_{i=1}^mA_ix_{ji}=A_j,j=1,\ldots,n,(3)

Неможливо розібрати вираз (невідома помилка): \sum_{i=1}^mc_ix_{ij},j=1,\ldots,n,(4) ,

де Неможливо розібрати вираз (невідома помилка): x_{ij}

коефіцієнт розкладання. Система умов:

Неможливо розібрати вираз (невідома помилка): \sum_{i=1}^mA_ix_i+A_kx_k=B,k\geq m+1,(5)

Неможливо розібрати вираз (невідома помилка): z_k\geq 0,x_j=0,j=m+1,\ldots,n,j\ne k(6)

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

при русі по цьому променю дорівнює Неможливо розібрати вираз (невідома помилка): \theta

, тоді значення базисних змінних дорівнюють Неможливо розібрати вираз (невідома помилка): x_i(\theta) . В цих позначеннях рівняння (5) можна представити у вигляді

Неможливо розібрати вираз (невідома помилка): \sum_{i=1}^mx_i(\theta)A_i+\theta A_k=B.(7)

помноживши рівняння (3) на Неможливо розібрати вираз (невідома помилка): \theta

при j = k та віднявши від рівняння (1), отримаємо

Неможливо розібрати вираз (невідома помилка): \sum_{i=1}^m(\bar{x_i}-\theta x_{ik})A_i+\theta A_k=B, (8)

із рівнянь (7-8) отримаємо

Неможливо розібрати вираз (невідома помилка): x_i(\theta)=\bar{x_i}-\theta x_{ik}, i=1,\ldots,m. (9)

ОскількиНеможливо розібрати вираз (невідома помилка): x_i(\theta), \theta = 0

визначають план задачі, то найбільше Неможливо розібрати вираз (невідома помилка): \theta

, яка не порушує обмеження Неможливо розібрати вираз (невідома помилка): x_i(\theta)\geq 0 , визначається із умови

Неможливо розібрати вираз (невідома помилка): \theta_0=\min_{i \in I}\frac{\bar{x_i}}{x_{ik}}. (10) ,

де Неможливо розібрати вираз (невідома помилка): I = ({{i|x_{ik}>0}}) .

В силу невиродженості задачі мінімум досягається не більш ніж для одного i = J, та Неможливо розібрати вираз (невідома помилка): \theta > 0 . Значення лінійної форми при Неможливо розібрати вираз (невідома помилка): \theta = \theta_0

визначається із рівнянь (9), (4), (2).

Неможливо розібрати вираз (невідома помилка): z_0(\theta_0)=\sum_{i=1}^mc_ix_i(\theta_0)+c_k\theta_0=\bar{z_0}-\theta_0\bigtriangleup_k ,

де Неможливо розібрати вираз (невідома помилка): \bigtriangleup_k = z_k - c_k . Очевидно, що Неможливо розібрати вираз (невідома помилка): \bigtriangleup_j = 0

для Неможливо розібрати вираз (невідома помилка): j=1,\ldots,m

.

Нехай Неможливо розібрати вираз (невідома помилка): \bar{A}=E

- початковий базис із m одиничних векторів. Всі дані задачі записуються у вигляді симплекс-таблиці (першої ітерації обчислювального процесу). Симплекс-алгоритм розв'язання задачі лінійного програмування складається із наступних операцій:

1. Знайти Неможливо розібрати вираз (невідома помилка): \bigtriangleup_k=\min_{j}\bigtriangleup_j

. Якщо Неможливо розібрати вираз (невідома помилка): \bigtriangleup_k = 0 , тоді план, який розглядається, оптимізовано, якщо Неможливо розібрати вираз (невідома помилка): \bigtriangleup_k < 0 , вектор Неможливо розібрати вираз (невідома помилка): A_k

вводиться в базис.

1. Знайти Неможливо розібрати вираз (невідома помилка): \theta_0

та Неможливо розібрати вираз (невідома помилка): l

, для якого Неможливо розібрати вираз (невідома помилка): \theta_0=\frac{\bar{x_l}}{x_{l}k} , із формули (10). Якщо Неможливо розібрати вираз (невідома помилка): l = \wedge

- порожня множина, лінійна форма необмежена зверху, якщо Неможливо розібрати вираз (невідома помилка): l \ne \wedge

, вектор Неможливо розібрати вираз (невідома помилка): A_l

виводиться із базису.

1. За знайденими Неможливо розібрати вираз (невідома помилка): I,k

обчислити нові значення елементів таблиці за формулами:

Неможливо розібрати вираз (невідома помилка): x'_{ij}=\begin{cases} x_{ij}-\frac{x_{lj}}{x_{lk}}x_{ik}, & i \ne l; \\ \frac{x_{lj}}{x_{lk}}, & i = l; \end{cases}

Неможливо розібрати вираз (невідома помилка): i = 1,\ldots,m+1, j = 0,1,\ldots,n ,

де Неможливо розібрати вираз (невідома помилка): x_{i0}=\bar{x_i},x_{m+1_0}=\bar{z_0},x_{m+1j}=\bigtriangleup_j

та перейти до виконання операції (1) з новими значеннями всіх Неможливо розібрати вираз (невідома помилка): x_{ij}=x'_{ij}

.

Перетворення (12) замінює вектор коефіцієнтів Неможливо розібрати вираз (невідома помилка): X_k=(x_{1k},\ldots,x_{mk})

на одиничний вектор. В силу монотонного збільшення Неможливо розібрати вираз (невідома помилка): x_0
повернення до вже пройденого плану неможливе, а із скінченності кількості опорних планів випливає скінченність алгоритму.

Зауважимо, що кожне з лінійних нерівностей на змінні обмежує півпростір у відповідному лінійному просторі. В результаті всі нерівності обмежують деякий багатогранник (можливо, нескінченний), називаний також поліедральних конусом. Рівняння Неможливо розібрати вираз (невідома помилка): W(x) = c , де Неможливо розібрати вираз (невідома помилка): W(x)

- максімізіруемий (або мінімізіруемий) лінійний функціонал, породжує гіперплоскость Неможливо розібрати вираз (невідома помилка): L(c)

. Залежність від Неможливо розібрати вираз (невідома помилка): c

породжує сімейство паралельних гіперплоскостей. Тоді екстремальна задача набуває наступне формулювання - потрібно знайти таке найбільше Неможливо розібрати вираз (невідома помилка): c

, що гіперплоскость Неможливо розібрати вираз (невідома помилка): L(c)

перетинає багатогранник хоча б в одній точці. Зауважимо, що перетин оптимальної гіперплоскості і багатогранника буде містити хоча б одну вершину, причому, їх буде більше однієї, якщо перетин містить ребро або k-мірну грань. Тому максимум функціоналу можна шукати в вершинах багатогранника. Принцип симплекс-методу полягає в тому, що вибирається одна з вершин багатогранника, після чого починається рух по його ребрах від вершини до вершини в бік збільшення значення функціоналу. Коли перехід по ребру з поточної вершини в іншу вершину з більш високим значенням функціоналу неможливий, вважається, що оптимальне значення c знайдено.

Послідовність обчислень симплекс-методом можна розділити на дві основні фази:

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

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

Основна ідея симплекс-метода

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

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

Двохетапний симплекс-метод

Двохетапний симплекс-метод. Завдання за допомогою цього методу вирішується в два етапи: спочатку відшукується початкове допустиме рішення, що не містить штучних змінних, а потім на основі знайденого рішення шукається оптимальне рішення початкової задачі. Основні кроки, реалізації методу наступні.

1. Завдання лінійного програмування зводиться до стандартної форми.
2. Будується штучний базис.
3. Складається штучна цільова функція: сума всіх штучних змінних.
4. Реалізується перший етап двохетапного методу: за допомогою звичайних процедур симплекс-метода виконується мінімізація штучної цільової функції. Якщо її мінімальне значення рівне 0, то відповідне рішення є допустимим рішенням початкової задачі. Очевидно, що при нульовому значенні штучної цільової функції всі штучні змінні також нульові (оскільки штучна цільова функція - їх сума, і всі вони ненегативні). Якщо мінімальне значення штучної цільової функції виявляється відмінним від нуля, це означає, що завдання не має допустимих рішень.
5. Реалізується другий етап двохетапного методу: знайдене на кроці 4 допустиме рішення використовується як початкове рішення початкової задачі для пошуку її оптимального рішення.

Опорний план

Опорний план — розв'язок системи лінійних обмежень в задачі лінійного програмування, який неможливо представити у вигляді лінійної комбінації будь яких інших розв'язків.

Система обмежень задачі лінійного програмування в канонічній формі має вигляд:

Неможливо розібрати вираз (невідома помилка): \sum_{j=1}^nA_ix_i = B; x_j\geq0,j=1,\ldots,n,

(1)

де Неможливо розібрати вираз (невідома помилка): 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)
- вектор змінних. Розв'язок Неможливо розібрати вираз (невідома помилка): X^*
є опорним планом тоді і тільки тоді, коли множина векторів Неможливо розібрати вираз (невідома помилка): A_j

, для яких Неможливо розібрати вираз (невідома помилка): x_j^* > 0 , лінійно незалежна.

Кількість додатніх компонент опорного плану не перевищує m. Якщо кількість цих компонент дорівнює m, опорний план називається невиродженим, а множина відповідних векторів Неможливо розібрати вираз (невідома помилка): A_j

утворює базис. Множина Неможливо розібрати вираз (невідома помилка): A_{j_1},\ldots,A_{j_m}
є базисом задачі лінійного програмування з обмеженнями (1) тоді і тільки тоді, коли система

Неможливо розібрати вираз (невідома помилка): \sum_{i=1}^mA_{j_i}x_{j_i}=B

має єдиний розв'язок, та Неможливо розібрати вираз (невідома помилка): x_{j_i}\geq0, i=1,\ldots,m .

Різним опорним планам відповідають різні базиси. Зворотне твердження вірне лише у випадку невиродженості всіх опорних планів системи (1).

Початковий опорний план

Початковий опорний план з одиничним базисом можна отримати, розв'язавши описаним алгоритмом допоміжну задачу

Неможливо розібрати вираз (невідома помилка): \sum_{i=1}^m(-y_{n+i})\to\max ,

при обмеженнях

Неможливо розібрати вираз (невідома помилка): \sum_{j=1}^na_{ij}x_j+y_{n+i}=b_i,i=1,\ldots,n

Неможливо розібрати вираз (невідома помилка): y_{n+1}\geq0,i=1,\ldots,m

Неможливо розібрати вираз (невідома помилка): x_j\geq0,j=1,\ldots,n

яка містить одиничний базис, який складається із векторів Неможливо розібрати вираз (невідома помилка): A_{n+1},\ldots,A_{n+m} . Цим векторам відповідають штучні змінні із значеннями y'_{n+i}=b_i,i=1,\ldots,m. Якщо в оптимальному розв'язку цієї задачі Неможливо розібрати вираз (невідома помилка): \sum_{i=1}^my_{n+i}>0 , вихідна задача не має розв'язку. Якщо ж Неможливо розібрати вираз (невідома помилка): \sum_{i=1}^my_{n+i}=0

та задача невироджена, оптимальний базис складається лише тільки із векторів вихідної задачі, які за формулами (12) перетворені в одиничну матрицю. Якщо задача має невироджені плани, значення Неможливо розібрати вираз (невідома помилка): z_0
може не збільшуватись на ряді ітерацій. Це відбувається через те, що значення відповідних Неможливо розібрати вираз (невідома помилка): \bar{x_l}
дорівнює нулю та визначається неоднозначно. В таких випадках монотонність методу порушується і може трапитись зациклювання, тобто, повернення до вже пройденого базису. Невелика зміна вектора обмежень задачі, яка полягає в заміні величин Неможливо розібрати вираз (невідома помилка): b_i
на Неможливо розібрати вираз (невідома помилка): b_i + \varepsilon_i

, де Неможливо розібрати вираз (невідома помилка): \varepsilon_i

достатньо малі, при вдалому виборі Неможливо розібрати вираз (невідома помилка): \varepsilon_i
не змінюють множину векторів оптимального опорного плану вихідної задачі і робить її невиродженою.

Описаний вище алгоритм називається першим (або прямим) алгоритмом симплекс-методу. Також відомий другий алгоритм (алгоритм із оберненою матрицею). В ньому перетворюється лише матриця Неможливо розібрати вираз (невідома помилка): A^{-1} , обернена до базисної матриці.