СИМПЛЕКС-МЕТОД

из "Математические исследования операций в экономике "

В дальнейшем для удобства нумерации элементов будем считать, что добавляемый коэффициент целевой функции с. является нулевым элементом /-го расширенного столбца условий, т. е. o,/ = /. При изображении расширенных векторов нулевая координата откладывается вдоль вертикальной оси — оси аппликат. [c.34]
Из геометрической иллюстрации следует, что для решения задачи мы должны среди векторов а1 выбрать такой набору a/l,a/2 , чтобы прямая, проведенная через конец вектора b параллельно оси аппликат, пересекала конус, натянутый на систему соответствующих расширенных столбцов а 1, 2 , в наивысшей точке. [c.34]
С вычислительной точки зрения критерий оптимальности в симплекс-методе реализуется через нахождение специальных оценок для небазисных векторов-столбцов, относительно текущего базиса. [c.35]
Значения Яоу(Р( 7)) также называют оценками столбцов матрицы А относительно текущего базиса, или симплекс-разностями. [c.37]
Можно доказать, что допустимость базиса, к которому осуществляется переход, обеспечивается следующим правилом вывода столбца из текущего базиса. [c.38]
Вообще говоря, после перехода от базиса р( г) к базису р( 7+0 мы можем заново сформировать матрицы Д(р( 7+1)), Д Чр 4 0) и, вычислив Жр( 7+1)) = А 1 (р( 7+1) )А, делать выводы о его оптимальности. Однако, учитывая, что р( 7+1) отличается от р( ) всего лишь одним столбцом, с точки зрения техники вычислений представляется рациональным непосредственно переходить от Л(р( ) и (р ) к А(р( + )) и 6(р( +1)). Дело в том, что у матриц типа Л(р( /)) столбцы, соответствующие базисным векторам, состоят из нулей, за исключением одного элемента, равного единице. Позиция этого ненулевого элемента определяется порядковым номером базисного столбца в Мр( 7)). Поэтому для получения матрицы Жр( 7+1 ) достаточно с помощью линейных операций над строками матрицы Л(р( 7 ) привести ее столбец, соответствующий вводимому в базис вектору, к базисному виду. [c.39]
Название метода произошло от понятия симплекса. Напомним, что т-симплексом называют выпуклый многогранник, аффинная оболочка 1 которого есть аффинное множество размерности т. В данном случае можно считать, что система расширенных базисных столбцов ал,а/2. а/т , рассматриваемых как точки в / m+1, порождает (т- 0-мерный симплекс в пространстве / от+1. [c.40]
В заключение настоящего пункта обобщим изложенные вопросы и приведем схему алгоритма симплекс-метода для решения задачи максимизации. Она включает однократно выполняемый 0-этап и повторяемый конечное число раз 1-этап (стандартную итерацию). [c.40]
a0(p(q)) Q — план, соответствующий текущему базису задачи, оптимален. Вычислительный процесс закончен. Согласно формулам (1.33) и (1.32) выписываются оптимальный план задачи х =х( (ч)) и значение целевой функции f(x ) = f(x(p (q))). [c.41]
Он называется ведущим и должен быть введен в очередной базис. Переходим к пункту 2° алгоритма. [c.41]
Задача ЛП, имеющая вырожденные планы, называется вырожденной. При выходе на вырожденный план мы фактически получаем разложение столбца b по системе из меньшего, чем т, количества столбцов а1 и, следовательно, лишаемся возможности корректно определить, ввод какого столбца в базис приведет к росту значения целевой функции. Подобные ситуации, в конечном счете, могут привести к зацикливанию вычислительного процесса, т. е. бесконечному перебору одних и тех же базисов. [c.46]
С точки зрения первой геометрической интерпретации ЗЛП ситуация вырожденности означает, что через некоторую угловую точку многогранного множества допустимых планов задачи, соответствующую текущему базисному плану, проходит более чем т гиперплоскостей ограничений задачи. Иными словами, одно или несколько ограничений в данной точке являются избыточными. Последнее предоставляет повод для размышлений об экономической стороне проблемы вырожденности как проблемы наличия избыточных ограничений и в некоторых случаях определяет пути ее решения. [c.46]
Из данной интерпретации вытекает и идея метода решения вырожденных задач ЛП, получившего названия метода возмущений при выходе на вырожденный план осуществляется незначительный сдвиг вектора b и вырожденность (как это видно из иллюстрации) устраняется. [c.47]
Необходимо, однако, сказать, что рассмотренная здесь проблема зацикливания для большинства практически значимых задач является достаточно редкой и маловероятной. Более того, она очень часто разрешается за счет ошибок округлений при выполнении расчетов на ЭВМ. [c.47]
Идея метода минимизации невязок состоит в построении соответствующей вспомогательной задачи, для которой можно в явном виде указать исходный базисный план, и решении ее с помощью процедуры симплекс-метода. [c.48]

Вернуться к основной статье