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

 

     Столбец p симплекс-таблицы, соответствующий выбранному коэффициенту A_0,p < 0, называется ведущим столбцом. Свободная переменная ведущего столбца должна быть введена в базис вместо одной из текущих базисных переменных. Очевидно, из базиса следует исключить такую переменную X_q, которая раньше других обращается в нуль при увеличении переменной X_p ведущего столбца.

     Её  индекс легко определить, если среди положительных элементов ведущего столбца p найти элемент, минимизирующий отношение (A_i,0 / A_i,p):

     Элемент A_q,p называется ведущим элементом, cтрока q симплекс-таблицы, содержащая ведущий элемент, называется, соответственно, ведущей строкой. Переменная ведущей строки X_q заменяется в базисе переменной ведущего столбца X_p и становится свободной переменной с значением 0, в то время как новая базисная переменная X_p достигнет максимально возможного значения, равного:

     После указанного взаимообразного обмена переменными X_p и X_q между наборами свободных и базисных переменных нужно модифицировать исходную каноническую модель задачи путем приведения ее к диагональной форме относительно нового множества базисных переменных. Для указанного преобразования можно формально использовать процедуру исключения Гаусса, которая, как известно, состоит из двух элементарных операций, применяемых к системе алгебраических уравнений ( в данном случае ограничений - равенств):

• умножение уравнения E₁(X) = 0 на константу K₁ и замена уравнения E₁(X) = 0 уравнением K₁*E₁(X) = 0;
• сложение уравнений E₁(X) = 0 и E₂(X) = 0 c последующей заменой уравнения E₂(X) = 0 уравнением E₁(X) + E₂(X) = 0.

     Исключения  Гаусса позволяют привести систему  уравнений к диагональной форме  относительно желаемого множества переменных. В данном случае исключение Гаусса применяется так, чтобы все элементы симплекс-таблицы в ведущем столбце, кроме ведущего элемента A_q,p, стали нулевыми, а ведущий элемент стал равным единице: A_i,p = 0, если i не равно q и A_i,p = 1, если i = q.

     Указанные шаги симплекс-метода повторяются, пока не будет получена симплекс-таблица, которая одновременно является прямо и двойственно допустимой. Если положит в такой симплекс-таблице текущие базисные переменные равными A_i,0, а свободные - нулю, то будет получено оптимальное решение.

     Практика  применения симплекс метода показала, что число итераций, требуемых  для решения задачи линейного программирования обычно колеблется от 2m до 3m, хотя для некоторых специально построенных задач вычисления по правилам симплекс метода превращаются в прямой перебор базисных допустимых решений. Однако, трудные для симплекс метода задачи на практике встречаются крайне редко, что объясняет широкое распространение и большую популярность данного метода линейного программирования по сравнению с другими подходами.

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

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

      Любые m переменных системы m линейных уравнений с n переменными называются базисными (основными), если определитель матрицы размерности m×m коэффициентов при них отличен от нуля. Остальные переменных называются свободными (неосновными).

      Симплексный метод позволяет улучшать план задачи наиболее рациональным способом, опираясь на критерии оптимальности решения.

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

      Критерий  оптимальности решения при отыскании  минимума линейной функции: если в выражении линейной функции через свободные переменные отсутствуют отрицательные коэффициенты при свободных переменных, то решение оптимально.

      На  практике удобнее для выяснения  вопроса: является ли найденный план оптимальным, пользоваться оценками переменных , которые вычисляются по формулам:

                                                                                 (1.3)

      Тогда критерии оптимальности решения  формулируются иначе, а именно:

• при отыскании максимума функции: если оценки всех переменных неотрицательны, то значение целевой функции максимально и решение оптимально;
• при отыскании минимума функции: если оценки всех переменных не положительны, то значение целевой функции минимально и решение оптимально.

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

      Практические  расчеты при решении реальных задач, если не используется ЭВМ, проводят в так называемых симплексных  таблицах.

      Рассмотрим одну из часто решаемых симплексным методом оптимизационных задач − задачу о распределении ресурсов.

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

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

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

      Решение задачи начнём с допущения, что неизвестная  x₁ обозначает количество телевизоров, x₃ − количество магнитофонов, а x₃ − количество моноблоков, выпускаемых предприятием. Тогда получаем, что затраты по ресурсу "Пластиковые формы" на данном предприятии, согласно заданным табл. 1.1 технологическим коэффициентам определяются зависимостью . При этом затраты по ресурсу «Пластиковые формы» не должны превышать 150 единиц, заданных в качестве имеющегося на предприятии запаса.

      Технологические коэффициенты, прибыль и запасы ресурсов Таблица 1.1.

        
 
 
 

      Таким образом, получаем первое ограничение на количество выпускаемой продукции:                                            (1.4)

      Аналогично  составляются ограничения по другим ресурсам, и в результате получаются еще три ограничения по ресурсам:

      

                            (1.5)

      

                                      (1.6)

      

                                      (1.7)

      Кроме того, поскольку количество выпущенной продукции не может быть отрицательной величиной, естественно потребовать, чтобы выполнялись неравенства

                                                    (1.8)

      При выпуске выбранного количества продукции  согласно данным табл.1.1 предприятие получит прибыль, определяемую функцией

                                              (1.9)

   Решение задачи оптимизации заключается в нахождении таких количеств выпускаемой продукции, которые обеспечивают функции прибыли максимальное значение при заданных ограничениях по количеству имеющихся на предприятии ресурсов. Каждое из решений системы неравенств (1.5) − (1.7),будет допустимым

решением (планом) для данной задачи. Оптимальным решением называется то из

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

       Таким образом, объединяя составленные по данным табл.1.1 зависимости (1.5) − (1.8), получаем математическую модель задачи о распределении ресурсов: 
 
 
 

                                    (1.10)

      Естественное  ограничение о не отрицательности количеств выпускаемой продукции вытекает из смысла производственной задачи.

      Решение сформулированной задачи может быть найдено, например, симплексным методом.

       Поскольку ограничения  задачи являются неравенствами "с  недостатком", введём дополнительные вспомогательные переменные которые называют "выравнивающими", и с помощью них превратим неравенства в равенства: 
 
 
 

            (1.11)

      Теперь  система (1.11) является системой четырёх  линейных алгебраических уравнений  относительно семи неизвестных. Решения  системы (1.11) находим симплексным методом в табл. 1.2, с использованием метода Жордана − Гаусса для решения систем линейных алгебраических уравнений.

      Метод Жордана − Гаусса − это метод нахождения базисных решений систем m линейных алгебраических уравнений относительно n неизвестных, если n≥ m, в специальных таблицах, позволяющих в ходе решения замещать базисный элемент одним из свободных переменных. Количество N различных базисных решений определяется формулой:   

                                                   (1.12)                                        

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

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

      При решении системы (1.11) и нахождении того её базисного решения, которое  обеспечивает максимум рассматриваемой  функции прибыли (целевой функции) F , использованы критерии симплексного метода для задач линейного программирования. Стрелки в табл. 1.2 указывают разрешающий столбец и разрешающую строку, на их пересечении находится разрешающий элемент.

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