Симплекс-метод, его сущность

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

     2X1 – X2 + 6X4 – 3X5 + Х9 = 0;

     2X1 – 2X3 + 6X4 – 2X6 + Х10 =0. 

     где Х9 и Х10 – искусственные переменные, не имеющие никакого физического смысла, причем Х9, Х10 ≥0.

     После построения искусственного базиса, придав нулевые значения всем переменным, кроме базисных, получим начальный базис: Х7, Х8, Х9, Х10 . Всего в базисе имеется четыре переменные и их значения равны правым частям ограничений, т.е.: 

     Х7 = 8; Х8 = 8; Х9 = 0; Х10 = 0. 

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

Глава 2. Двухэтапный  метод. 

      2.1 Искусственное начальное решение. 

      В простом симплексе при начальном  допустимом базисном решении гарантировалось, что все последующие базисные решения, получаемые при выполнении симплекс-метода, также будут допустимыми. В задачах линейного программирования, где все ограничения являются неравенствами типа «<=» (с неотрицательной правой частью), дополнительные (остаточные) переменные позволяют сформировать начальное допустимое базисное решение в задачах ЛП, где есть ограничения в виде равенств или неравенств типа «>=» ?

      Наиболее  общим способом построения начального допустимого базисного решения  задачи ЛП является использование искусственных  переменных. Эти переменные в первой итерации играют роль дополнительных остаточных переменных, но на последующих итерациях от них освобождаются. Разработано два тесно связанных между собой метода нахождения начального решения, которые используют искусственные переменные: М-метод и двухэтапный метод.

      Для объяснения двухэтапного метода объясним сначала концепцию М-метода. 

      Пусть задача ЛП записана в стандартной  форме. Для любого равенства I, в котором не содержится дополнительная остаточная переменная, введём искусственную переменную Ri, которая далее войдёт в начальное базисное решение. Но поскольку эта переменная искусственна (другими словами, не имеет никакого «физического смысла» в данной задаче), необходимо сделать так, чтобы на последующих итерациях она обратилась в нуль. Для этого в выражение целевой функции вводят штраф.

      Переменная  Ri, с помощью достаточно большого положительного числа М, штрафуется путём ввода в целевую функцию выражения – MRi в случае максимизации целевой функции и выражения +MRi – в случае минимизации. Вследствие этого штрафа естественно предположить, что процесс оптимизации симплекс-метода приведёт к нулевому значению переменной Ri. Следующий пример проясняет детали этого метода. 

      Пример 3.4-1 

      Минимизировать  z = 4x1 + x2 

      при выполнении условий 

        3x1 + x2 = 3,

            4x1 + 3x2 >= 6,

          x1 + 2x2 <= 4,

      x1, x2 >= 0. 

      Стандартная форма этой задачи получается в результате добавления дополнительной (избыточной) переменной x3 во второе неравенство и дополнительной (остаточной) переменной x4 в третье неравенство. Эта задача в стандартной форме будет записана следующим образом. 

      Минимизировать  z = 4x1 + x2 

      при выполнении условий 

      3x1 + x2 = 3,

                4x1 + 3x2 – x3 = 6,

              x1 + 2x2 + x4 = 4,

                x1, x2, x3, x4 >= 0.

       

      В полученной задаче первое и второе уравнения не имеют дополнительных (остаточных) переменных, которые можно ввести в базисное решение. Поэтому введём в эти уравнения искусственные переменные R1 и R2, а в целевую функцию добавим штраф MR1 + MR2. В результате получим следующую задачу ЛП. 

      Минимизировать z = 4x1 + x2 + MR1 + MR2 

      при выполнении условий 

        3x1 + x2 + R1 = 3,

                 4x1 + 3x2 – x3 + R2 = 6,

      x1 + 2x2 + x4 = 4,

                      x1, x2, x3, x4, R1, R2 >= 0. 

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

      При использовании М-метода следует  обратить внимание на следующие два  обстоятельства. 

      1. Использование штрафа М может  и не привести к исключению  искусственной переменной в конечной  симплекс-итерации. Если исходная задача линейного программирования не имеет допустимого решения (например, система ограничений несовместна), тогда в конечной симплекс-итерации, по крайней мере, одна искусственная переменная будет иметь положительное значение. Это «индикатор» того, что задача не имеет допустимого решения.

      2. Теоретически применение М-метода  требует, чтобы М → ∞. Однако с точки зрения компьютерных вычислений величина М должна быть конечной и, вместе с тем, достаточно большой. Как понимать термин «достаточно большая» – это открытый вопрос. Величина М должна быть настолько большой, чтобы выполнить роль «штрафа», но не слишком большой, чтобы не уменьшить точность вычислений. На практике вы должны помнить о возможных ошибках машинного округления при выполнении выполнений, в которых совместно участвуют как большие, так и малые числа. 

      Правильный  выбор значения М зависит от данных исходной задачи. Бездумное следование теоретическому требованию, что М  должно быть «очень большим», может  привести к значительным ошибкам  округления. Именно поэтому М-метод никогда не применяется в коммерческих программах, реализующих симплекс-метод. Вместо него используется двухэтапный метод, который будет описан в следующем разделе. 
 
 
 
 
 
 
 
 
 
 

      2.2 Алгоритм двухэтапного метода. 

      Пример  2.2-2 демонстрирует проблемы, которые могут возникнуть при М-методе вследствие ошибок округления. Двухэтапный метод полностью лишён тех недостатков, которые присущи М-методу. Как следует из названия этого метода, процесс решения задачи ЛП разбивается на два этапа. На первом этапе ведётся поиск начального допустимого базисного решения. Если такое решение найдено, то на втором этапе решается исходная задача. 

      Этап 1. Задача ЛП записывается в стандартной форме, а в ограничения добавляются необходимые искусственные переменные (как и в М-методе) для получения начального базисного решения. Решается задача ЛП минимизации суммы искусственных переменных с исходными ограничениями. Если минимальное значение этой новой целевой функции больше нуля, значит, исходная задача не имеет допустимого решения, и процесс вычислений заканчивается. (Напомним, что положительные значения искусственных переменных указывают на то, что исходная система ограничений несовместна.) Если новая целевая функция равна нулю, переходим ко второму этапу.

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

      Пример  2.2-3 

      К задаче из примера 2.2-3 применим двухэтапный метод. 

      Этап 1 

      Минимизировать  r = R1 + R2 

      С ограничениями 

        3x1 + x2 + R1 = 3,

                 4x1 + 3x2 – x3 + R2 = 6,

      x1 + 2x2 + x4 = 4,

                       x1, x2, x3, x4, R1, R2, >= 0. 

      Соответствующая таблица имеет следующий вид.