Просмотр кода страницы Симплекс-метод. Простое объяснение

{{wikipedia|Симплекс-метод}}

== Причины создания этого учебника ==
В интернете опубликовано множество объяснений алгоритма симплекс-метода, про которые можно смело сказать «лучше ничего, чем это». Они написаны крайне заумным языком и доставляют множество страданий всем, кто пытается с их помощью изучить этот метод линейного программирования.

Целью данного учебника является создание простого и доступного описания алгоритма симплекс-метода, которое можно понять, что называется, «с ходу».

== Задача линейного программирования ==
Задача линейного программирования в стандартной форме заключается в том, чтобы найти экстремум функции

<math>c_1  x_1+c_2 x_2+ \cdots + c_n x_n \rightarrow \text{max}</math>

при заданных ограничениях:

<math>
a_{11} x_1+a_{12} x_2+\cdots+a_{1n} x_n \le b_1
</math>

<math>
a_{21} x_1+a_{22} x_2+\cdots+a_{2n} x_n \le b_2
</math>

<math>
\cdots
</math>

<math>
a_{m1} x_1+a_{m2} x_2+\cdots+a_{mn} x_n \le b_m
</math>

== Симплекс-таблица ==
Запишем симплекс-таблицу:

{|border
|-
|  || <math>x_1</math> ||   <math>x_2</math> ||  … ||  <math>x_n</math> ||
|-
|<math>y_1</math> || <math>a_{11}</math> || <math>a_{12}</math> || … ||  <math>a_{1n}</math> || <math>b_1</math>
|-
|<math>y_2</math> || <math>a_{21}</math> || <math>a_{22}</math> ||  … || <math>a_{2n}</math> || <math>b_2</math>
|-
| … || … || … ||  … || … || …
|-
| … || … || … ||  … || … || …
|-
|<math>y_m</math> || <math>a_{m1}</math> || <math>a_{m2}</math> ||   … ||  <math>a_{mn}</math> ||  <math>b_m</math>
|-
|  || <math>-c_1</math> || <math>-c_2</math> ||  … || <math>-c_n</math> || <math>0</math>

|}

== Алгоритм ==
Первый шаг алгоритма состоит в том, чтобы найти минимальный элемент в последней строке (<math>-c_{i}</math>). Номер этого элемента определит разрешающий столбец.

На втором шаге определяется разрешающая строка. Для этого нужно найти симплекс отношение: в каждой строке элемент последнего столбца делится на соответствующий элемент разрешающего столбца. Так получается столбец симплекс-отношений. Минимальный элемент в этом столбце и определяет разрешающую строку.

Приступаем к построению новой симплекс-таблицы.
Метки <math>y</math> и <math>x</math> для разрешающей строки и столбца соответственно меняются местами: <math>y_i</math> обозначает теперь столбец, а <math>x_j</math> — строку.
Элемент на пересечении разрешающего столбца и разрешающей строки возводим в степень <math>-1</math>.
Все элементы разрешающей строки, кроме того, что на пересечении, делим на этот элемент на пересечении.
Все элементы разрешающего столбца, кроме того, что на пересечении, делим на этот элемент на пересечении и умножаем на <math>-1</math>.

Остальные элементы новой симплекс таблицы высчитываются по правилу прямоугольника:

<math>a_{iL}</math> ……………………………………. <пересч. элемент <math>a_{ij}</math>>

…

<элемент на пересечении <math>a_{s_l}</math> > … <math>a_{sj}</math>


<math>a_{ij}</math> новый = <math>a_{ij} - (a_{il}*a_{sj})/(a_{sl})</math>

Вышеуказанные операции выполняются для всех элементов, включая <math>a</math>, <math>b</math> и <math>c</math> и повторяются до тех пор, пока в строке <math>c</math> будут отрицательные элементы.

Если же отрицательных элементов в строке больше нет, значит, оптимальное решение достигнуто. Оно будет находиться в последнем столбце <math>b</math>, его будут обозначать соответствующие метки «<math>x</math>» строк.

Подставив найденные <math>x</math> в целевую функцию, находим оптимальное решение.

[[Категория:Алгоритмы]]