Основы симплес метода

     ^{Запишем задачу в канонической форме (в виде системы  уравнений, что требует  симплекс-метод), для  этого введем две  переменные х₃ ≥ 0 и х₄ ≥ 0 получим:} 
 
 

     ^{Система ограничений предлагает только одну допустимую базисную переменную x₄, только она входит только в одно уравнение в третье с коэффициентом 1, поэтому в первое и второе уравнения добавляем искусственные переменные R₁ ≥ 0 и R₂ ≥ 0 Чтобы можно было применить симплекс-метод система уравнений-ограничений должна быть системой с базисом, т.е. в каждом уравнении должна быть переменная с коэффициентом 1, которая входит только в одно уравнение системы, в нашем случае это R₁, R₂ и x₄. Получили, так называемую, М-задачу:} 
 
 

     ^{Данная  система является системой с базисом, в которой R₁, R₂ и x₄ базисные переменные, а x₁, x₂ и x₃ свободные переменные, свободные члены всех уравнений неотрицательны. Следовательно, для решения задачи можно применить симплекс-метод. Запишем начальную симплекс-таблицу:}

^{Таблица 1.8}

     ^{В таблицу для задач  с искусственным  базисом добавлена  строка «Оценка». Она получается суммированием соответствующих коэффициентов строк с искусственными переменными (R) с обратным знаком. Она будет присутствовать в таблице до тех пор, пока хотя бы одна из искусственных переменных есть в базисе. По наибольшему по модулю отрицательному коэффициенту строки " Оценка " определяется разрешающий столбец пока она есть в таблице. Когда строка "Оценка" выйдет из таблицы (в базисе нет искусственных переменных) разрешающий столбец будет определяться по f(x)-строке, как и в задаче с начальным базисом. В данной таблице разрешающий столбец х₂, он выбран по наибольшей по модулю отрицательной оценке (-7). Разрешающая строка R₂ выбрана по наименьшему отношению столбца "Решение" к соответствующим положительным элементам разрешающего столбца, как и в задаче без искусственных переменных. Это значит, что на следующей итерации симплекс-метода переменная х₂ из свободной перейдет в базисную, а переменная R₂ из базисной – в свободную. Запишем следующую симплекс-таблицу:} 
 

^{Таблица 1.9} 

     Разрешающий столбец х₁, разрешающая строка R₁, R₁ выходит из базиса, x₁ входит в базис. После этого в базисе не остается искусственных переменных, поэтому строки «Оценка» в следующей таблице нет: 
 

^{Таблица 2.0} 
 

     Далее разрешающий столбец выбирается поf(x)-строке. В f(x)-строке все коэффициенты неотрицательны кроме коэффициента при искусственной переменной R₁, который не влияет на оптимальность, когда искусственные переменные вышли из базиса. Следовательно, симплекс-методом получено оптимальное решение x₁ = 6/5; x₂ = 3/5; f()_max = 72/5. 
 
 
 

     

4. ^{Модифицированный  симплекс – метод}

 

     Одним из модификаций симплекс-метода является улучшенный симплекс-метод.

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

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

     В улучшенном симплекс-методе реализуется  та же основная идея, что и в обычном  симплекс-методе, но здесь на каждой итерации пересчитывается не вся  матрица A^-1, обратная матрице ограничений A, а лишь та часть, которая относится к текущему базису A_x.

     Рассмотрим  поэтапно шаги решения задачи линейного  программирования улучшенным симплекс-методом:

     1.В  начале первого цикла нам известны обратная матрица (единичная матрица), базисное решение x_b = b.

     2.Образуем  для каждой небазисной переменной  характеристическую разность D_j, используя уравнение: 

     D_j = c_j — p= c_j — pP_j , 

     Где p - двойственные переменные, которые можно найти следующим образом: 

     p = c_{x *} , 

     Где c_x - вектор коэффициентов целевой функции при базисных переменных.

     3.Предполагая,  что используется стандартное  правило выбора вводимого столбца,  находим: 

     DD . 

     4.Если D_s ³ 0 - процедура останавливается. Текущее базисное решение является оптимальным.

     5.Если D_s £ 0, вычисляем преобразованный столбец: 

      = P_s 

     6.Пусть 

     = (, , ..., ) .

     Если  все £ 0 - процедура останавливается: оптимум неограничен.

     7.В  противном случае находим выводимую  из базиса переменную: 

     _³ = q . 

     8.Строим  увеличенную матрицу: 
 
 

     и трансформируем ее с ведущим элементом  . Первые m столбцов результат дают матрицу, обратную новому базису. Преобразуем базисное решение: 

     x_{b i} Ü x_{b i} — q _* , i ¹ r,

     x_{b r} Ü q 

     и переходим к этапу 2.

     Этот  вариант называют также модифицированным симплекс-методом, поскольку он уменьшает  объем вычислений на каждом шаге. Идея заключается в том, что на каждом шаге конаническую форму задачи для текущего базиса можно получить независимо от других таких форм непосредственно из исходной записи стандартной задачи ЛП. Для этого нужно: (1) сохранять исходную запись задачи на протяжении всей работы метода, это та цена, которую приходится платить за больше быстродействие;

     (2) использовать так называемые  симплекс – множители π – коэффициенты для непосредственного перехода от исходной записи задачи к ее текущей канонической форме базиса; и (3) использовать обращенный базис В־¹ - матрицу размера m x m, позволяющую вычислять на каждом шаге ведущий столбец a΄s и обновлять симплекс – множители π.

     Преимущества метода

     Улучшенный  симплекс-метод, обладает значительными  преимуществами по сравнению со стандартной  формой. Это относится к точности, скорости и требованиям к памяти. Большая часть этих преимуществ  определяется тем фактором, что, как  правило, матрицы больших линейных задач (то есть с n>m>100) являются слабозаполненными, содержат малый процент ненулевых элементов.

     Обычной является плотность 5% или менее. Улучшенная форма симплекс-метода в большей  степени способна использовать преимущества, вытекающие из этого факта. В этой форме характеристические разности и ведущий вектор вычисляются  непосредственно по исходным данным. Поскольку исходная матрица слабозаполнена, а перемножение следует производить только тогда, когда оба сомножителя отличны от нуля, то время вычислений значительно сокращается.

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