Добро пожаловать на наш портал !

Методы компьютерного моделирования экономических процессов

Преобразование Жордана—Гаусса

Для это применяется преобразование Жордана—Гаусса (так называемый метод полного исключения). В данном случае оно состоит в том, что мы должны «заработать» единицу на месте элемента ar,l(q)) (он обычно называется ведущим)* и нули на месте остальных элементов столбца al(q)). Первое достигается посредством деления r-й строки на ведущий элемент, второе — путем прибавления вновь полученной r-й строки, умноженной на подходящий коэффициент, к остальным строкам матрицы A(q)).

* Напомним, что l — номер столбца, вводимого в базис, а r — номер строки в симплекс-таблице, определяющей номер столбца, выводимого из базиса.


Формально результат выполнения данного преобразования над элементами A(q)) и b(q)) может быть выражен в следующем виде


Следует особо отметить смысл элементов вектора b(q)). Его нулевой компонент b0(q)) в соответствии с построением содержит значение целевой функции, достигаемое ею на текущем плане

а остальные элементы — ненулевые компоненты этого плана:

Название метода произошло от понятия симплекса. Напомним, что m-симплексом называют выпуклый многогранник, аффинная оболочка* которого есть аффинное множество размерности m. В данном случае можно считать, что система расширенных базисных столбцов {аj1 ,аj2,..., аjm}, рассматриваемых как точки в Rm+1, порождает (m -1)-мерный симплекс в пространстве Rm+1.

* Аффинной оболочкой множества называют наименьшее аффинное множество, в котором содержится данное множество.

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