Понятие о симплекс-методе. Алгоритм симплекс-метода

Общую идею симплекс-метода можно проиллюстрировать на примере модели, построенной для задачи №1. Пространство решений этой задачи представлено на рисунке 2.1.

Исходной точкой алгоритма является начало координат (точка А). Решение, соответствующее этой точке, обычно называют начальным решением. От исходной точки осуществляется переход к некоторой смежной угловой точке.

В рассматриваемом случае это может быть либо точка В, либо точка F. Выбор точки зависит от коэффициентов целевой функции. Так как коэффициент целевой функции при x ₁, больше коэффициента при х ₂, а целевая функция подлежит максимизации, требуемое направление перехода будет от точки А к точке F.

После этого указанный процесс повторяется, чтобы выяснить, существует ли другая экстремальная точка, соответствующая лучшему допустимому решению (в данном случае большему значению целевой функции). Используя, как и ранее, информацию о целевой функции, можно определить, имеется ли на данном шаге алгоритма такая точка. В результате такой итеративный процесс позволяет найти оптимальную угловую точку Е.

Выбор каждой последующей экстремальной точки при использовании симплекс-метода определяется следующими двумя правилами.

1. Каждая последующая угловая точка должна быть смежной с предыдущей. Например, в пространстве решений, изображенном (на рис. 2.1, невозможен прямой переход от точки А к точке Е. Этот переход осуществляется по границам (ребрам) пространства решений: от точки А к точке F и лишь затем от точки F к точке E.

2. Обратный переход к предшествующей экстремальной точке не может производиться.

Подводя итог изложению идей симплекс-метода, еще раз обратим внимание на то, что отыскание оптимального решения начинается с некоторой допустимой угловой точки, и все переходы осуществляются только к смежным точкам, причем перед новым переходом каждая из полученных точек проверяется на оптимальность. При решении задачи №1 начальным решением является точка А, из которой осуществляется переход в точку F и затем в точку E, соответствующую оптимуму. Таким образом, в данном случае для нахождения оптимального решения требуются три итерации (получаемые решения изображаются точками А, F и E).