03. Симплекс-метод

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

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

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

1. Каждая последующая угловая точка должна быть смежной с предыдущей. Этот переход осуществляется по границам (ребрам) пространства решений.

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

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

Определим пространство решений и угловые точки алгебраически. Требуемые соотношения устанавливаются из указанного в таблице соответствия геометрических и алгебраических определений.

Геометрическое определение	Алгебраическое определение (симплекс метод)
Пространство решений	Ограничения модели стандартной формы
Угловые точки	Базисное решение задачи в стандартной форме

< Предыдущая		Следующая >