Общая ЗЛП. Канонический вид ЗЛП

2.1. Общая ЗЛПформулируется в виде (1.2). Другими словами, ЗЛП в общем виде ставится как (1.2).

Таким образом, имея дело с ЗЛП, мы будем иметь дело с линейной системой. В теории линейных систем x₁, x₂, …, x_n мы называли неизвестными. В оптимизации функции f(x₁, x₂, …, x_n) они выступают в качестве переменных. Поэтому к ним мы будем применять этот термин. От этого их суть не меняется: необходимо найти (неизвестные) переменные x₁, x₂, …, x_n, при которых целевая функция f(x₁, x₂, …, x_n) достигает экстремума. Также, мы сохраняем терминологию линейных систем: основная и расширенная матрица, совместные системы, ранг системы, базисное решение и т.д. Так же, будем считать, что ранг r системы совпадает с числом m уравнений и неравенств: r=m.

Канонический вид ЗЛП

Если в системе ограничений задачи (1.2) присутствуют только уравнения, а свободные члены в системе ограничений задачи являются неотрицательными, то говорят, что задача имеет канонический вид. Согласно 1.2.2 первой части, любая смешанная система приводится к системе уравнений добавлением дополнительных неотрицательных переменных со знаком «+» в неравенства типа «≤» и со знаком «-» в неравенства типа «≥». Поэтому для приведения к каноническому виду задачи линейного программирования поступаем следующим образом:

1) Если в системе ограничений задачи имеется ограничение с отрицательной правой частью, то умножаем его на -1.

2) Добавляем в каждое неравенство дополнительные неотрицательные переменные: со знаком «+» в неравенства типа «≤» и со знаком «-» в неравенства типа «≥».

Таким образом,

2.2.1. ОЗЛП (1.2) приводится к каноническому виду

c₁x₁+c₂x₂+…+c_nx_n®max(min)

2.2.2. ЗЛП (1.4) приводится к каноническому виду

c₁x₁+c₂x₂+…+c_nx_n®max

А также

2.2.1. ЗЛП (1.5) приводится к каноническому виду

c₁x₁+c₂x₂+…+c_nx_n®min

В любом случае можно считать, что ЗЛП имеет канонический вид

c₁x₁+c₂x₂+…+c_nx_n®max(min)

(2.1)

Если A=(a_ij) - матрица системы ограничений задачи, X=(x₁, x₂, …, x_n)^T - столбец переменных, B=(b₁, b₂, …, b_n)^T - столбец свободных членов системы ограничений и C=(c₁, c₂, …, c_n) - вектор коэффициентов целевой функции, то задачу (2.1) можно записать в матричной форме:

CX®max(min)

AX=B, X≥O.

Обозначим через A₁, A₂, …, A_n соответственно 1-й, 2-й, …, n-й столбцы матрицы A. Тогда задачу (1.6) можно записать в векторной форме:

CX®max(min)

A₁x₁+A₂x₂+…+A_nx_n=B,

X≥O.

2.3. Упражнение. Привести к каноническому виду задачи линейного программирования из предыдущих заданий 1) - 3), выписать их матрицы ограничений, столбцы свободных членов, векторы условий, векторы коэффициентов целевых функций, и записать задачи в матричной и векторной формах.

Решение. 1г) 4x₁+x₂®min(max)

Правая часть первого неравенства - отрицательная. Поэтому первое неравенство умножаем на -1:

Теперь все неравенства ограничений имеют тип «£». Поэтому во все эти неравенства вводим дополнительные неотрицательные переменные, соответственно x₃, x₄, x₅:

Таким образом, канонический вид задачи - следующий:

4x₁+x₂ ® max

Матрица ограничений (выписываем для канонического вида): , - столбец свободных членов, A₁= , A₂ = , A₃= , A₄= , A₅= - векторы условий, (4, 1, 0, 0, 0) - вектор коэффициентов целевой функции, × = , ³O - матричная форма записи задачи, x₁+ x₂+ x₃+ x₄+ x₅= -

- векторная форма записи задачи.