Перегляд вихідного коду сторінки Симплекс-метод

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

== Опис методу ==
Нехай невироджену [[Задача лінійного програмування|задачу лінійного програмування]] представлено в канонічному вигляді:<br />
:<math>\sum_{j=1}^n c_jx_j \to \max </math>,
: <math>\sum_{j=1}^n A_jx_j = B,\quad x_j \ge 0,\quad j = 1, 2, \ldots, n, </math> <br />
де ''X'' = (''x''<sub>1</sub>, …, ''x''<sub>n</sub>)&nbsp;— вектор змінних, ''C'' = (''c''<sub>1</sub>, …., ''c''<sub>n</sub>), ''B'' = (''b''<sub>1</sub>, …, ''b''<sub>m</sub>)<sup>T</sup>, ''A''<sub>j</sub> = (''a''<sub>1j</sub>, …, ''a''<sub>mj</sub>)<sup>T</sup>, ''j'' = 1, …, ''n''&nbsp;— задані вектори, T&nbsp;— знак транспонування, та
: <math>\bar{X} = (\bar{x}_1, \ldots, \bar{x}_m)</math><br />
відмінні від нуля компоненти [[опорний план|опорного плану]], для полегшення пояснення розташовані на перших ''m'' місцях вектора ''X''. Базис цього плану&nbsp;— <math>\bar{A} = (A_1, \ldots, A_m) </math>. Тоді
: <math> \sum_{i=1}^m A_i \bar{x}_i = B </math>, (1)
: <math> \sum_{i=1}^m c_i x_i = \bar{z}_0 </math>, (2)
де <math> \bar{z}_0 </math> значення лінійної форми на даному плані. Так як вектор-стовпці [[Матриця (математика)|матриці]] ''A'' [[Лінійно незалежні вектори|лінійно незалежні]], будь-який із векторів умов ''A''<sub>j</sub> розкладається по них єдиним чином:
: <math> \sum_{i=1}^m A_i x_{ji} = A_j, \qquad j = 1, \ldots, n</math>, (3)
: <math> \sum_{i=1}^m c_i x_{ij}, \qquad j = 1, \ldots, n </math>, (4)
де ''x''<sub>ij</sub> коефіцієнт розкладання. Система умов
: <math>\sum_{i=1}^m A_i x_i + A_k x_k = B, \qquad k \ge m + 1</math>, (5)
''z''<sub>k</sub> ≥ 0, ''x''<sub>j</sub> = 0, ''j'' = ''m'' + 1, …, n, ''j'' ≠ ''k'' (6)<br />
при заданому ''k'' визначає в просторі змінних задачі [[промінь (геометрія)|промінь]], який виходить із точки, яка відповідає опорному плану, що розглядається. Нехай значення змінної ''x''<sub>k</sub> при русі по цьому променю дорівнює θ, тоді значення базисних змінних дорівнюють ''x''<sub>i</sub>(θ). В цих позначеннях рівняння (5) можна представити у вигляді
: <math> \sum_{i=1}^m x_i (\theta) A_i + \theta A_k = B </math>. (7)
помноживши рівняння (3) на θ при ''j'' = ''k'' та віднявши від рівняння (1), отримаємо
: <math> \sum_{i=1}^m (\bar{x}_i - \theta x_{ik}) A_i + \theta A_k = B </math>.(8)
Із рівнянь (7-8) отримаємо
: <math> x_i (\theta) = \bar{x}_i - \theta x_{ik}, \qquad i = 1, \ldots, m </math>. (9)
Оскільки ''x''<sub>i</sub>(θ) при θ = 0 визначають план задачі, то найбільше θ, яке не порушує [[Обмеження (математика)|обмеження]] ''x''<sub>i</sub> (θ) ≥ 0, визначається із умови
: <math> \theta_0 = \min_{i \in I} \frac{\bar{x}_i}{x_{ik}} </math>. (10)
де ''I'' = {''i'' | ''x''<sub>ik</sub> &gt; 0}.

В силу невиродженості задачі мінімум досягається не більш ніж для одного ''i'' = ''J'' та θ &gt; 0. Значення лінійної форми при θ = θ<sub>0</sub> визначається із рівнянь (9), (4), (2)
: <math>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</math>,
де Δ<sub>k</sub> = ''z''<sub>k</sub>&nbsp;— ''c''<sub>k</sub>. Очевидно, Δ<sub>j</sub> = 0 для ''j'' = 1, …, ''m''.

Нехай <math>\bar{A} = E</math>&nbsp;— початковий базис із ''m'' одиничних векторів. Всі дані задачі записуються у вигляді симплекс-таблиці (першої ітерації обчислювального процесу). Симплекс-алгоритм розв'язання задачі лінійного програмування складається із наступних операцій:
# знайти <math>\Delta_k = \min_j\Delta_j</math>. Якщо Δ<sub>k</sub> = 0, тоді план, який розглядається оптимізовано; якщо Δ<sub>k</sub> &lt; 0, вектор ''A''<sub>k</sub> вводиться в базис;
# знайти θ<sub>0</sub> та ''l'', для якого <math>\theta_0 = \bar{x}_l / x_lk</math>, із формули (10). Якщо ''I'' = Λ&nbsp;— [[порожня множина]], [[лінійна форма]] необмежена зверху; якщо ''I'' ≠ Λ вектор ''A''<sub>l</sub> виводиться із базису;
# за знайденими ''l'', ''k'' обчислити нові значення елементів таблиці за формулами
: <math>x_{ij}' = \begin{cases}
x_{ij} - \frac{x_{lj}}{x_{lk}} x_ik, & \mbox{if } i \neq l; \\
\frac{x_{lj}}{x_{lk}}, & \mbox{if } i = l;
\end{cases}</math> (12)
: <math> i = 1, \dots, m + 1,\quad j = 0, 1, \dots, n</math>,
де <math>x_{i0} = \bar{x}_i,\; x_{m+1\, 0} = \bar{z}_0,\; x_{m+1\, j} = \Delta_j</math> та перейти до виконання операції (1) з новими значеннями всіх ''x''<sub>ij</sub> = x'<sub>ij</sub>.

Перетворення (12) замінює вектор коефіцієнтів ''X''<sub>k</sub> = (''x''<sub>1k</sub>, …, ''x''<sub>mk</sub>) на одиничний вектор ''X'''<sub>k</sub> з ''x'''<sub>lk</sub> = 1. В силу монотонного збільшення ''x''<sub>0</sub> повернення до вже пройденого плану неможливе, а із скінченності кількості опорних планів випливає скінченність алгоритму.

Початковий опорний план з одиничним базисом можна отримати, розв'язавши описаним алгоритмом допоміжну задачу
: <math> \sum_{i=1}^m (- y_{n+i}) \to \max </math>,
при [[Обмеження (математика)|обмеженнях]]
: <math> \sum_{j=1}^n a_{ij}x_{j} + y_{n+i} = b_i,\quad i = 1, \dots, </math>
: <math>y_{n+1} \geq 0, i = 1, \dots, m </math>;
: <math>x_j \geq 0, j = 1, \dots, n </math>,
яка містить одиничний базис, який складається із векторів ''A''<sub>n+1</sub>, …, ''A''<sub>n+m</sub>. Цим векторам відповідають штучні змінні із значеннями <math>\bar{y}_{n+i} = b_i</math>, ''i'' = 1, …, ''m''. Якщо в оптимальному розв'язку цієї задачі <math> \sum_{i=1}^m y_{n+i} > 0 </math>, вихідна задача не має розв'язку. Якщо ж <math> \sum_{i=1}^m y_{n+i} = 0 </math> та задача невироджена, оптимальний базис складається лише тільки із векторів вихідної задачі, які за формулами (12) перетворені в одиничну матрицю. Якщо задача має невироджені плани, значення ''z''<sub>0</sub> може не збільшуватись на ряді ітерацій. Це відбувається через те, що значення відповідних <math>\bar{x}_l</math> дорівнює нулю та визначається неоднозначно. В таких випадках монотонність методу порушується і може трапитись зациклювання, тобто, повернення до вже пройденого базису. Невелика зміна вектора обмежень задачі, яка полягає в заміні величин ''b''<sub>i</sub> на ''b''<sub>i</sub> + ε<sub>i</sub>, де ε<sub>i</sub> достатньо малі, при вдалому виборі ε<sub>i</sub> не змінюють множину векторів оптимального опорного плану вихідної задачі і робить її невиродженою.

Описаний вище алгоритм називається першим (або прямим) алгоритмом симплекс-методу. Також відомий другий алгоритм (алгоритм із оберненою матрицею). В ньому перетворюється лише матриця ''A''<sup>-1</sup>, обернена до базисної матриці.
{{Методи оптимізації}}
{{Портал|математика}}
{{Math-stub}}
[[Категорія:Дослідження операцій]]
[[Категорія:Алгоритми оптимізації]]