Симплекс-метод
Решение задачи ЛП (2.1.1), согласно теоремам 2, 3, 4, достигается в вершине многогранного множества. Теорема 2 дает простое описание вершин и способ их определения при известном базисе. Число вершин конечно. Минимум задачи может быть найден за конечное число шагов посредством перебора вершин.
В симплекс-методе осуществляется идея перебора вершин соседних текущей вершине и выбора среди них в качестве следующего приближения вершины с наименьшим значением целевой функции. Симплекс-метод применяют для задач, записанных в форме:
. (2.4.1)
Пусть на 
-ом шаге получена точка 
, являющаяся вершиной множества 
, и пусть 
.
Назовем 
невырожденной вершиной множества , если число положительных компонент в ней равно 
.
Предположим, что все вершины множества невырождены. В силу невырожденности множество 
содержит элементов. Разобьем вектор 
на две группы 
, где 
отвечает компонентам из , 
- компонентам, не принадлежащим . Тогда система 
может быть записана в виде:
, (2.4.2)
где 
, столбцы которой являются столбцами 
с индексами из , 
-матрица, составленная из оставшихся столбцов. Отсюда, в силу невырожденности матрицы 
,
(2.4.3)
Целевая функция приобретает вид:
, (2.4.4)
где 
- вектор с компонентами 
, 
, 
-вектор с компонентами 
, 
. С учетом (2.4.3) целевая функция может быть выражена только через 
.
Следовательно, исходная задача эквивалентна следующей:
, 
(2.4.5)
При этом точке соответствует вектор 
, где 
, 
. Точка является допустимой для задачи (2.4.5) при ограничении 
, которое удовлетворяется как строгое неравенство 
. Поэтому оно может быть отброшено (как неактивное) при анализе точки 
на оптимальность.
В задаче
, 
(2.4.6)
минимум достигается в 0 тогда и только тогда, когда 
.
Итак, если
(2.4.7)
то точка 
является решением (2.1.1) и одновременно (2.4.5), а тем самым является решением (2.4.1). Если же среди компонент 
есть отрицательные (например, 
), то не является решением (2.4.6), и, увеличивая 
, можно уменьшить значение целевой функции в (2.4.6).
Итак, сделаем шаг
- 
-й орт. (2.4.8)
Выбор 
производится из следующих соображений. С увеличением целевая функция уменьшается, однако может нарушиться ограничение 
, которое в точке , было неактивным. Итак, нужно выбрать из условия
. (2.4.9)
Если при этом 
, то задача не имеет решения в силу бесконечного убывания функции. Если же 
, то получаем новую точку 
,
где 
. Эта точка вновь является вершиной (она допустима и имеет m положительных компонент, так как -я компонента стала положительной, а одна из компонент 
обратилась в 0).
Поэтому в ней можно повторить всю процедуру заново. При этом значение целевой функции уменьшилось. Следовательно, возврат в одну из точек невозможен. В силу конечности общего числа вершин метод конечен.
Условия (2.4.7) являются условием оптимальности в симплекс-методе.