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

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

Постановка задач линейного программирования - student2.ru f(X) = Постановка задач линейного программирования - student2.ru cj xj Постановка задач линейного программирования - student2.ru max(min)

a11x1+a12x2+…+a1nxn Постановка задач линейного программирования - student2.ru b1

a21x1+a22x2+…+a2nxn Постановка задач линейного программирования - student2.ru b2

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

am1x1+am2x2+…+amnxn=bm

x1 Постановка задач линейного программирования - student2.ru 0, x2 Постановка задач линейного программирования - student2.ru 0, …, xl Постановка задач линейного программирования - student2.ru 0 (l Постановка задач линейного программирования - student2.ru n).

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

f(X)= CX Постановка задач линейного программирования - student2.ru min

AX=B (2)

X Постановка задач линейного программирования - student2.ru O.

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

· матрица C = (c1,c2,…,cn) – матрица цен,

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

· матрица X = (x1,x2,…,xn)т – вектор неизвестных,

· матрица B = (b1,b2,…,bm)т – вектор свободных членов.

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

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

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

f(X) = c0 - Постановка задач линейного программирования - student2.ru cjxj Постановка задач линейного программирования - student2.ru min

a11x1+a12x2+ … +a1kxk+xk+1=b1

a21x1+a22x2+ … +a2kxk+xk+2=b2

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

ar1x1+ar2x2+ … +arkxk+xk+r=br

x1 Постановка задач линейного программирования - student2.ru 0, x2 Постановка задач линейного программирования - student2.ru 0, … , xn Постановка задач линейного программирования - student2.ru 0

(k+r=n, bj Постановка задач линейного программирования - student2.ru 0, j=1,2,…,r)

Здесь все свободные члены b1, b2, …, br неотрицательны.

Переменные x1,x2, … ,xk называются свободными переменными, а переменные xk+1,xk+2, … ,xn называются базисными переменными.

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

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

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

f(X) = 2x1 + 3x2 Постановка задач линейного программирования - student2.ru max

x1 – x2 Постановка задач линейного программирования - student2.ru -3

- 4x1 + 6x2 Постановка задач линейного программирования - student2.ru -5 (*)

x1 Постановка задач линейного программирования - student2.ru 0

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

f (X) введем функцию f*(X) = - f (X) = - 2x1 – 3x2 Постановка задач линейного программирования - student2.ru min; 2) для преобразования неравенств (*) в равенства введем две новых неотрицательных переменных x3 и x4 так, чтобы они удовлетворяли уравнениям

x1 – x2 + x3 = -3

4x1 – 6x2 + x4 = 5

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

f*(X) = -2x1 – 3x5 + 3x6 Постановка задач линейного программирования - student2.ru min

x1 – x5 +x6 + x3 = -3

4x1 – 6x5 + 6x6 + x4 = 5 (**)

x1 Постановка задач линейного программирования - student2.ru 0, x3 Постановка задач линейного программирования - student2.ru 0,x4 Постановка задач линейного программирования - student2.ru 0,x5 Постановка задач линейного программирования - student2.ru 0, x6 Постановка задач линейного программирования - student2.ru 0.

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

f*(X) = -2x1 – 3x5 + 3x6 Постановка задач линейного программирования - student2.ru min

-x1 + x5 – x6 – x3 + x7 = 3

4x1 – 6x5 + 6x6 +x4 = 5

x1 Постановка задач линейного программирования - student2.ru 0, x3 Постановка задач линейного программирования - student2.ru 0, x4 Постановка задач линейного программирования - student2.ru 0, x5 Постановка задач линейного программирования - student2.ru 0, x6 Постановка задач линейного программирования - student2.ru 0, x7 Постановка задач линейного программирования - student2.ru 0.

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

Наши рекомендации