Каноническая форма задачи ЛП
Будем считать, что задача линейного программирования записана в канонической форме, если ее целевая функция максимизируется, ограничения имеют вид равенств с неотрицательной правой частью и все переменные неотрицательны.
Задача линейного программирования в канонической форме имеет вид:
f = c1x1 + c2x2 +…+ cnxn → max;
a11x1 + a12x2 +…+ a1nxn = b1,
a21x1 + a22x2 +…+ a2nxn = b2, (4)
……………………………..
am1x1 + am2x2 +…+ amnxn = bm,
xj >= 0 (j= 1, n); bi >= 0 (i= 1, m).
Так как общая задача линейного программирования имеет ограничения не только вида «=», но и «<=», «>=», а целевая функция может либо максимизироваться, либо минимизироваться, то необходимо уметь приводить любые задачи линейного программирования к канонической форме. С этой целью рассмотрим два частных вида задач линейного программирования и покажем, как эти задачи привести к канонической форме.
Одна из частных задач линейного программирования может быть представлена моделью:
f = c1x1 + c2x2 +…+ cnxn → max;
 |
a11x1 + a12x2 +…+ a1nxn <= b1,
a21x1 + a22x2 +…+ a2nxn <= b1, (5)
……………………………..
am1x1 + am2x2 +…+ amnxn <= bm,
xj >= 0 (j= 1, n), где bi >= 0 (i= 1, m).
Левая часть каждого ограничения данной задачи меньше либо равна правой. Для того, чтобы левая часть ограничения была равна правой, необходимо к левой части каждого ограничения прибавить соответственно неотрицательные переменные xn+1, xn+2,…, xn+m. Эти переменные вводятся в целевую функцию с нулевыми коэффициентами, чтобы не изменить ее значение.
После приведения к канонической форме задача (5) будет иметь вид:
f = c1x1 +…+ cnxn + 0*xn+1 + 0*xn+2 +…+ 0*xn+m → max;
a11x1 +…+ a1nxn + xn+1 = b1,
a21x1 +…+ a2nxn + xn+2 = b2, (6)
…………………………….
am1x1 +…+ amnxn + xn+m = bm,
xj >= 0 (j= 1, n+m).
Рассмотрим другой частный вид задачи линейного программирования:
f = c1x1 + c2x2 +…+ cnxn → min;
a11x1 + a12x2 +…+ a1nxn >= b1,
a21x1 + a22x2 +…+ a2nxn >= b2, (7)
……………………………..
am1x1 + am2x2 +…+ amnxn >= bm,
xj >= 0 (j= 1, n),
где bi >= 0 (i= 1, m).
Определение минимального значения целевой функции f можно свести к определению максимального значения функции (- f), так как min f = - max (- f).
Для приведения ограничений вида «>=» к ограничениям-равенствам необходимо из левой части каждого ограничения вычесть соответственно неотрицательные переменные xn+1, xn+2,…, xn+m. Эти переменные вводятся в целевую функцию с нулевыми коэффициентами, чтобы не изменить ее значение.
После приведения к канонической форме задача (7) будет иметь вид:
f = - c1x1 -…- cnxn + 0*xn+1 + 0*xn+2 +…+ 0*xn+m → max;
a11x1 +…+ a1nxn - xn+1 = b1,
a21x1 +…+ a2nxn - xn+2 = b2, (8)
…………………………….
am1x1 +…+ amnxn - xn+m = bm,
xj >= 0 (j= 1, n+m).
Таким образом, если в задаче линейного программирования определяется минимум целевой функции, то такую задачу необходимо свести к определению максимума целевой функции, а все имеющиеся ограничения вида «<=» и «>=» привести к ограничениям-равенствам.
Замечание. Требование максимизации целевой функции при приведении задачи к канонической форме не обязательно и выдвигается с целью простоты изложения материала, связанного с решением задач линейного программирования симплекс-методом. Методика решения задач на минимум несколько отличается от методики решения задач на максимум. Поэтому требование максимизации целевой функции дает возможность решать задачу по единому алгоритму.