Пример. Максимизировать линейную форму L= – x4+x5 при ограничениях: x1+x4–2x5=1, x2–2x4+x5=2, x3+3x4+x5=3

Максимизировать линейную форму L = – x₄ + x₅ при ограничениях: x₁ + x₄ –2 x₅ =1, x₂ –2 x₄ + x₅ =2, x₃ +3 x₄ + x₅ =3.

Решение. Данная система уравнений-ограничений совместна, так как ранги матрицы системы и расширенной матрицы совпадают и равны 3. Следовательно, система уравнений совместна и три переменные (базисные) можно линейно выразить через две свободные переменные. Выразим, например x₁, x₂ и x₃ через x₄ и x₅, т.е. приведем систему к единичному базису:

(*)

Линейную форму L = – x₄ + x₅ выразим через свободные переменные x₄ и x₅ (в данном примере L уже выражена через x₄ и x₅). Теперь, при x₄ =0 и x₅ =0, найдем значения базисных переменных: x₁ =1, x₂ =2, x₃ =3, x₄ =0, x₅ =0 или (1,2,3,0,0). При найденном допустимом решении линейная форма L имеет значение 0, т.е. L₁ =0.

Теперь попытаемся увеличить значение L₁; увеличение x₄ уменьшит L₁, так как перед x₄ стоит отрицательный коэффициент, а увеличение x₅ дает увеличение и L₁. Увеличим поэтому x₅ так, чтобы x₁, x₂ и x₃ не стали отрицательными, оставив x₄ =0. Из второго уравнения системы (*) следует, что x₅ можно увеличить до 2. Таким образом, получаем следующие значения переменных: x₁ =5, x₂ =0, x₃ =1, x₄ =0, x₅ =2 или (5,0,1,0,2).

Значение линейной формы L при этом допустимом решении равно L₂ =2, т.е. при втором шаге оно увеличилось.

Далее, примем за свободные переменные x₂ и x₄, т.е. именно те переменные, которые в новом решении имеют нулевые значения. С этой целью из второго уравнения системы (*) выразим x₅ через x₂ и x₄ и получим

x₅ =2– x₂ +2 x₄. Тогда

(**)

Для увеличения значения L будем увеличивать x₄. Из второго уравнения системы (**) видно, что при условии неотрицательности x₃ значение x₄ можно довести до x₄ =1/5. При этом условии новое допустимое решение есть x₁ =28/5, x₂ =0, x₃ =0, x₄ =1/5, x₅ =12/5 или (28/5,0,0,1/5,12/5). Значение линейной формы при этом L₃ =11/5.

Выразим теперь x₁, x₄, x₅ через свободные переменные x₂ и x₃:

(***)

Так как в последней линейной форме обе свободные переменные входят с отрицательными коэффициентами, то наибольшее значение L достигается при x₂ =0 и x₃ =0. Это означает, что решение (28/5,0,0,1/5,12/5) является оптимальным и L_max =11/5.

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

Дата добавления: 2014-01-20