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

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

f (X) = c _j x _j max(min)

a₁₁x₁ + a₁₂x₂ +…+ a_1nx_n b₁

a₂₁x₁ + a₂₂x₂ +…+ a_2nx_n b₂

………………………… (1)

a_m1x₁ + a_m2x₂ +…+ a_mnx_n = b_m

x ₁ 0, x ₂ 0, …, x _l 0 (l n).

Основная задача ЛП имеет вид:

f (X)= CX min

AX=B (2)

X O.

Задача (2) записана в матричной форме:

· матрица C = (c ₁ ,c _2, …,c _n) – матрица цен,

· матрица A – матрица из коэффициентов, стоящих перед неизвестными,

· матрица X = (x₁,x_2,…,x_n)^т – вектор неизвестных,

· матрица B = (b₁,b₂,…, b_m)^т – вектор свободных членов.

Отличительные особенности основной задачи – это всегда задача на минимизацию целевой функции, в этой задаче все ограничения имеют вид равенств и все неизвестные – неотрицательны.

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

Каноническая задача ЛП имеет вид:

f(X) = c₀ - c_jx_j min

a₁₁x₁+a₁₂x₂+ … +a_1kx_k+x_k+1=b₁

a₂₁x₁+a₂₂x₂+ … +a_2kx_k+x_k+2=b₂

…………………………. (3)

a_r1x₁+a_r2x₂+ … +a_rkx_k+x_k+r=b_r

x₁ 0, x₂ 0, …, x_n 0

(k+r=n, b_j 0, j=1,2,…,r)

Здесь все свободные члены b₁, b₂, …, b_r неотрицательны.

Переменные x₁,x₂, …,x_k называются свободными переменными, а переменные x_k+1,x_k+2, …,x_n называются базисными переменными.

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

Основная задача (2) не всегда может быть приведена к каноническому виду (3). Пример приведения основной задачи к каноническому виду также приведен ниже.

Пример. Нижеследующую общую задачу ЛП привести к основной задаче, а затем, получившуюся основную задачу ЛП привести к канонической задаче:

f(X) = 2x₁ + 3x₂ max

x₁ – x₂ -3

- 4x₁ + 6x₂ -5 (*)

x₁ 0

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

f (X) введем функцию f^*(X) = - f (X) = - 2x₁ – 3x₂ min; 2) для преобразования неравенств (*) в равенства введем две новых неотрицательных переменных x₃ и x₄ так, чтобы они удовлетворяли уравнениям

x₁ – x₂ + x₃ = -3

4x₁ – 6x₂ + x₄ = 5

(здесь, во втором из неравенств (*) мы предварительно поменяли знак неравенства на противоположный); 3) наконец, вместо переменной x₂ введем две новых неотрицательных переменных x₅ и x₆: x₂ = x₅ – x₆. В результате, задача (*) приводится к виду:

f*(X) = -2x₁ – 3x₅ + 3x₆ min

x₁ – x₅ +x₆ + x₃ = -3

4x₁ – 6x₅ + 6x₆ + x₄ = 5 (**)

x₁ 0, x₃ 0,x₄ 0,x₅ 0, x₆ 0.

Задача (**) является основной задачей ЛП. Преобразуем теперь задачу (**) к каноническому виду. Для этого поменяем знак в первом из уравнений на противоположный и добавим в получившемся уравнении в левую часть новую переменную x₇ 0. Тогда получим задачу:

f*(X) = -2x₁ – 3x₅ + 3x₆ min

-x₁ + x₅ – x₆ – x₃ + x₇ = 3

4x₁ – 6x₅ + 6x₆ +x₄ = 5

x₁ 0, x₃ 0, x₄ 0, x₅ 0, x₆ 0, x₇ 0.

Здесь переменные x₄, x₇ являются базисными, а остальные переменные – свободными. Задача является канонической.