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

Симплекс-метод — метод розв'язання задачі лінійного програмування, в якому здійснюється скерований рух по опорних планах до знаходження оптимального розв'язку; симплекс-метод також називають методом поступового покращення плану. Метод був розроблений американським математиком Джорджем Данцігом у 1947 році.

Опис методу

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

$\sum _{j=1}^{n}c_{j}x_{j}\to \max$,

$\sum _{j=1}^{n}A_{j}x_{j}=B,\quad x_{j}\geq 0,\quad j=1,2,\ldots ,n,$

де X = (x₁, …, x_n) — вектор змінних, C = (c₁, …., c_n), B = (b₁, …, b_m)^T, A_j = (a_1j, …, a_mj)^T, j = 1, …, n — задані вектори, T — знак транспонування, та

${\bar {X}}=({\bar {x}}_{1},\ldots ,{\bar {x}}_{m})$

відмінні від нуля компоненти опорного плану, для полегшення пояснення розташовані на перших m місцях вектора X. Базис цього плану — ${\bar {A}}=(A_{1},\ldots ,A_{m})$. Тоді

$\sum _{i=1}^{m}A_{i}{\bar {x}}_{i}=B$, (1)

$\sum _{i=1}^{m}c_{i}x_{i}={\bar {z}}_{0}$, (2)

де ${\bar {z}}_{0}$ значення лінійної форми на даному плані. Так як вектор-стовпці матриці A лінійно незалежні, будь-який із векторів умов A_j розкладається по них єдиним чином:

$\sum _{i=1}^{m}A_{i}x_{ji}=A_{j},\qquad j=1,\ldots ,n$, (3)

$\sum _{i=1}^{m}c_{i}x_{ij},\qquad j=1,\ldots ,n$, (4)

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

$\sum _{i=1}^{m}A_{i}x_{i}+A_{k}x_{k}=B,\qquad k\geq m+1$, (5)

z_k ≥ 0, x_j = 0, j = m + 1, …, n, j ≠ k (6)
при заданому k визначає в просторі змінних задачі промінь, який виходить із точки, яка відповідає опорному плану, що розглядається. Нехай значення змінної x_k при русі по цьому променю дорівнює θ, тоді значення базисних змінних дорівнюють x_i(θ). В цих позначеннях рівняння (5) можна представити у вигляді

$\sum _{i=1}^{m}x_{i}(\theta )A_{i}+\theta A_{k}=B$. (7)

помноживши рівняння (3) на θ при 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},\qquad i=1,\ldots ,m$. (9)

Оскільки x_i(θ) при θ = 0 визначають план задачі, то найбільше θ, яке не порушує обмеження x_i (θ) ≥ 0, визначається із умови

$\theta _{0}=\min _{i\in I}{\frac {{\bar {x}}_{i}}{x_{ik}}}$. (10)

де I = {i | x_ik > 0}.

В силу невиродженості задачі мінімум досягається не більш ніж для одного i = J та θ > 0. Значення лінійної форми при θ = θ₀ визначається із рівнянь (9), (4), (2)

$z_{0}(\theta _{0})=\sum _{i=1}^{m}c_{i}x_{i}(\theta _{0})+c_{k}\theta _{0}={\bar {z}}_{0}-\theta _{0}\Delta _{k}$,

де Δ_k = z_k — c_k. Очевидно, Δ_j = 0 для j = 1, …, m.

Нехай ${\bar {A}}=E$ — початковий базис із m одиничних векторів. Всі дані задачі записуються у вигляді симплекс-таблиці (першої ітерації обчислювального процесу). Симплекс-алгоритм розв'язання задачі лінійного програмування складається із наступних операцій:

1. знайти $\Delta _{k}=\min _{j}\Delta _{j}$. Якщо Δ_k = 0, тоді план, який розглядається оптимізовано; якщо Δ_k < 0, вектор A_k вводиться в базис;
2. знайти θ₀ та l, для якого $\theta _{0}={\bar {x}}_{l}/x_{l}k$, із формули (10). Якщо I = Λ — порожня множина, лінійна форма необмежена зверху; якщо I ≠ Λ вектор A_l виводиться із базису;
3. за знайденими l, k обчислити нові значення елементів таблиці за формулами

$x_{ij}'={\begin{cases}x_{ij}-{\frac {x_{lj}}{x_{lk}}}x_{i}k,&{\mbox{if }}i\neq l;\\{\frac {x_{lj}}{x_{lk}}},&{\mbox{if }}i=l;\end{cases}}$ (12)

$i=1,\dots ,m+1,\quad j=0,1,\dots ,n$,

де $x_{i0}={\bar {x}}_{i},\;x_{m+1\,0}={\bar {z}}_{0},\;x_{m+1\,j}=\Delta _{j}$ та перейти до виконання операції (1) з новими значеннями всіх x_ij = x'_ij.

Перетворення (12) замінює вектор коефіцієнтів X_k = (x_1k, …, x_mk) на одиничний вектор X_k з x_lk = 1. В силу монотонного збільшення x₀ повернення до вже пройденого плану неможливе, а із скінченності кількості опорних планів випливає скінченність алгоритму.

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

$\sum _{i=1}^{m}(-y_{n+i})\to \max$,

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

$\sum _{j=1}^{n}a_{ij}x_{j}+y_{n+i}=b_{i},\quad i=1,\dots ,$

$y_{n+1}\geq 0,i=1,\dots ,m$;

$x_{j}\geq 0,j=1,\dots ,n$,

яка містить одиничний базис, який складається із векторів A_n+1, …, A_n+m. Цим векторам відповідають штучні змінні із значеннями ${\bar {y}}_{n+i}=b_{i}$, i = 1, …, m. Якщо в оптимальному розв'язку цієї задачі $\sum _{i=1}^{m}y_{n+i}>0$, вихідна задача не має розв'язку. Якщо ж $\sum _{i=1}^{m}y_{n+i}=0$ та задача невироджена, оптимальний базис складається лише тільки із векторів вихідної задачі, які за формулами (12) перетворені в одиничну матрицю. Якщо задача має невироджені плани, значення z₀ може не збільшуватись на ряді ітерацій. Це відбувається через те, що значення відповідних ${\bar {x}}_{l}$ дорівнює нулю та визначається неоднозначно. В таких випадках монотонність методу порушується і може трапитись зациклювання, тобто, повернення до вже пройденого базису. Невелика зміна вектора обмежень задачі, яка полягає в заміні величин b_i на b_i + ε_i, де ε_i достатньо малі, при вдалому виборі ε_i не змінюють множину векторів оптимального опорного плану вихідної задачі і робить її невиродженою.

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