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

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

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

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

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

a₂₁x₁+a₂₂x₂+…+a_2nx_n=b_2,

… ……………………….

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

x_j³0 (j=1,…, n), b_i³0 (i=1,…, m).

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

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

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_1,

………………………..

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

x_j³0 (j=1,…, n+m),

bi³0 (i=1,…, m).

Переменные x_n+1, x_n+2,…, x_n+m называются дополнительными. Экономический смысл, например, для задачи использования ресурсов заключается в том, что дополнительные переменные будут интерпретироваться как количество неиспользованных ресурсов.

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

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

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_1,

_{…………………………………….}

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

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

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

Контрольные вопросы и упражнения

1. Решить графическим методом следующие задачи:

2. Какую область образуют допустимые решения задачи линейного программирования, и что собой она представляет?

3. Какое множество называется выпуклым?

4. Какое множество называется замкнутым?

5. Что такое угловая точка?

6. Где целевая функция задачи линейного программирования достигает своего экстремального значения?

7. Какая зависимость существует между областью определения задачи и ее решением?