Приведение ЗЛП к канонической форме

Алгоритмы решения ЗЛП (например, симплекс-метод) разработаны для канонической формы. Приведем стандартную ЗЛП (5.2) к канонической форме. Для этого обратим ограничения-неравенства в равенства, введя дополнительные неотрицательные переменные y_i, (m - количество ограничений), которые входят в целевую функцию f(x) с нулевыми коэффициентами. В этом случае исходная задача будет эквивалентна исходной, так как оптимальное значение целевой функции не изменится:

max (+0• y_i)

при ограничениях- равенствах

,

Пример1. Привести ЗЛП к каноническому виду:

f(x)=2x₁ +x₂ – х₃ → max

при ограничениях

2x₂ – x₃ ≤5

x₁ +x₂ – x₃ ≥ -1

2x₁ – x₂ ≤-3

х₁≤ 0, x₃ ≥ 0

Решение. Введем в каждое ограничение дополнительные неотрицательные переменные х₄, х₅, х₆, причем в первое и третье ограничение переменные х₄, х₆ войдут со знаком «+», а во второе ограничение х₅ войдет со знаком «-»:

2x₂ – x₃ + х₄ =5

x₁ +x₂ – x₃ - х₅ = -1

2x₁ – x₂ +х₆=-3

x₄ ≥ 0, x₅ ≥ 0, x₆ ≥ 0

Свободные члены (правые части ограничений) в канонической форме должны быть положительными, поэтому два последних ограничения умножим на -1:

2x₂ – x₃ + х₄ =5

-x₁ -x₂ + x₃ + х₅ = 1

-2x₁ + x₂ -х₆=3.

В канонической форме все переменные должны быть неотрицательными. Поэтому проведем замену: х_j = х_j⁺ - х_j^-, j=1,2, причем х_j⁺·х_j^-=0. При этом количество оптимизируемых переменных увеличивается:

f(x)=2x₁⁺ - 2x₁^-+ x₂⁺ - x₂^- - x₃→ max

2x₂⁺ - 2x₂^-- х₃ +х₄ =5

-x₁⁺ + x₁^-- x₂⁺ + x₂^-+ х₃ + х₅ =1

-2x₁⁺ + 2x₁^-+ x₂⁺ - x₂^-- х₆ =3

х_j⁺ ≥ 0, х_j^-≥ 0, j=1,2

Переобозначим переменные:

x₁⁺ → х₁; x₁^-→ х₇; x₂⁺ → х₂; x₂^-→ х₈.

Получим следующую задачу оптимизации:

f(x)= 2x₁ + x₂– x₃ -2x₇ – х₈ → max

2x₂ - х₃ +х₄ - 2x₈=5

-x₁ - x₂ + х₃ + х₅ + x₇ +x₈ =1

-2x₁ + x₂ - х₆ + 2x₇ - x₈=3

х_j ≥ 0,

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