Каноническая форма задачи ЛП

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

Задача линейного программирования в канонической форме имеет вид:

f = c₁x₁ + c₂x₂ +…+ c_nx_n → max;

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

a₂₁x₁ + a₂₂x₂ +…+ a_2nx_n = b₂, (4)

……………………………..

a_m1x₁ + a_m2x₂ +…+ a_mnx_n = b_m,

x_j >= 0 (j= 1, n); b_i >= 0 (i= 1, m).

Так как общая задача линейного программирования имеет ограничения не только вида «=», но и «<=», «>=», а целевая функция может либо максимизироваться, либо минимизироваться, то необходимо уметь приводить любые задачи линейного программирования к канонической форме. С этой целью рассмотрим два частных вида задач линейного программирования и покажем, как эти задачи привести к канонической форме.

Одна из частных задач линейного программирования может быть представлена моделью:

f = c₁x₁ + c₂x₂ +…+ c_nx_n → max;

a₁₁x₁ + a₁₂x₂ +…+ a_1nx_n <= b₁,

a₂₁x₁ + a₂₂x₂ +…+ a_2nx_n <= b₁, (5)

……………………………..

a_m1x₁ + a_m2x₂ +…+ a_mnx_n <= b_m,

x_j >= 0 (j= 1, n), где b_i >= 0 (i= 1, m).

Левая часть каждого ограничения данной задачи меньше либо равна правой. Для того, чтобы левая часть ограничения была равна правой, необходимо к левой части каждого ограничения прибавить соответственно неотрицательные переменные x_n+1, x_n+2,…, x_n+m. Эти переменные вводятся в целевую функцию с нулевыми коэффициентами, чтобы не изменить ее значение.

После приведения к канонической форме задача (5) будет иметь вид:

f = c₁x₁ +…+ c_nx_n + 0*x_n+1 + 0*x_n+2 +…+ 0*x_n+m → max;

a₁₁x₁ +…+ a_1nx_n + x_n+1 = b₁,

a₂₁x₁ +…+ a_2nx_n + x_n+2 = b₂, (6)

…………………………….

a_m1x₁ +…+ a_mnx_n + x_n+m = b_m,

x_j >= 0 (j= 1, n+m).

Рассмотрим другой частный вид задачи линейного программирования:

f = c₁x₁ + c₂x₂ +…+ c_nx_n → min;

a₁₁x₁ + a₁₂x₂ +…+ a_1nx_n >= b₁,

a₂₁x₁ + a₂₂x₂ +…+ a_2nx_n >= b₂, (7)

……………………………..

a_m1x₁ + a_m2x₂ +…+ a_mnx_n >= b_m,

x_j >= 0 (j= 1, n),

где b_i >= 0 (i= 1, m).

Определение минимального значения целевой функции f можно свести к определению максимального значения функции (- f), так как min f = - max (- f).

Для приведения ограничений вида «>=» к ограничениям-равенствам необходимо из левой части каждого ограничения вычесть соответственно неотрицательные переменные x_n+1, x_n+2,…, x_n+m. Эти переменные вводятся в целевую функцию с нулевыми коэффициентами, чтобы не изменить ее значение.

После приведения к канонической форме задача (7) будет иметь вид:

f = - c₁x₁ -…- c_nx_n + 0*x_n+1 + 0*x_n+2 +…+ 0*x_n+m → max;

a₁₁x₁ +…+ a_1nx_n - x_n+1 = b₁,

a₂₁x₁ +…+ a_2nx_n - x_n+2 = b₂, (8)

…………………………….

a_m1x₁ +…+ a_mnx_n - x_n+m = b_m,

x_j >= 0 (j= 1, n+m).

Таким образом, если в задаче линейного программирования определяется минимум целевой функции, то такую задачу необходимо свести к определению максимума целевой функции, а все имеющиеся ограничения вида «<=» и «>=» привести к ограничениям-равенствам.

Замечание. Требование максимизации целевой функции при приведении задачи к канонической форме не обязательно и выдвигается с целью простоты изложения материала, связанного с решением задач линейного программирования симплекс-методом. Методика решения задач на минимум несколько отличается от методики решения задач на максимум. Поэтому требование максимизации целевой функции дает возможность решать задачу по единому алгоритму.