Идея симплекс-метода

Симплекс в - мерном пространстве – простейший многогранник.

гранник

–треугольник

– тетраэдр

Так как оптимальное решение достигается в угловой точке области допустимых решений, то искать оптимальное решение нужно среди опорных решений. Сначала найти произвольное опорное решение. Это вершина многогранника решений. Вместе с соседними с ней вершинами она образует симплекс в пространстве свободных переменных. Перейти к соседней вершине симплекса с лучшим значением критерия, двигаясь по одному из ребер симплекса (лучше по ребру, более близкому к вектору градиента функции).

Этапы симплекс-метода:

1. Построение начального опорного плана .

2. Проверяется признак оптимальности решения.

3. Построение нового опорного решения – переход от одной вершины симплекса к другой .

4. l=l+1, повторять со второго пункта до тех пор, пока не выполнятся условия оптимальности.