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

 

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

Для реализации симплексного метода – последовательного улучшения решения – необходимо освоить три основных элемента:

· способ определения какого – либо первоначального допустимого базисного решения задачи;

· правило перехода к лучшему (точнее, не худшему) решению;

· критерий проверки оптимальности найденного решения.

III   Задание:    Решить задачу симплексным методом.

 

   

 

 Z(x)=x₁-x₂+x₃ → max

 

 

При ограничениях:

 

        4x₁+2x₂+x₃ ≥ 6

         -x₁+x₂+x₃ = 1

          x₁-x₂+4x₃ ≤ 24

 

Учитывая условия неотрицательности:

             x_j ≥ 0, j=1,2,3

 

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

 

I шаг:

 

 

    Основные переменные: х₂, х₄, х₅

    Свободные переменные: х₁, х₃

 

С помощью дополнительных неотрицательных переменных перейдём к системе уравнений:

 

x₂=1+x₁-x₃

x₄=-4+6x₁-3x₃

x₅=25+3x₃

 

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

 

X1=(0,1,0,-4,25) – недопустимое базисное решение.

 

х₃=min{1,∞, }=1

II Шаг

 

 

Основные переменные: х₁, х₂, х₅

Свободные переменные: х₃, х₄

     Выразим новые основные переменные через неосновные:

         

     х₁=2/3+х₃/2+х₄/6

     x₂=5/3+x₃/2+x₄/6

     x₅=25+x₃

 

   

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

  

 X2=(, ,0,0,25) – допустимое базисное решение.

 

 

Выражаем линейную функцию через неосновные переменные:

  

  Z(x)=2/3+x₃/2+x₄/6-5/3-x₃/2-x₄/6+25+x₃=24+x₃=24.

 

  

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