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

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

Любая задача в смешанной форме может быть приведена к канонической. Рассмотрим, каким образом это делается.

Пусть ограничение задачи в смешанной форме имеет вид неравенства со знаком £. Преобразуем его в уравнение. Можно доказать, что

Здесь новая переменная y_i называется дополнительной, и представляет собой разность между правой и левой частями ограничений: (именно на y_i левая часть неравенства может быть меньше правой). Иногда ее еще называют балансовой. Эта переменная всегда вводится, как неотрицательная.

Чтобы понять смысл введения новой переменной, представим себе, что две части неравенства представляют собой груз на чашах весов, и правая часть может быть тяжелее (рисунок 1). Чтобы сравнять, сбалансировать обе части, добавим на левую чашу весов дополнительный груз (впрочем, если «весы» и без того были уравновешены, то вес этого нового груза может быть и нулевым).

Аналогично можно преобразовать ограничения, имеющие вид неравенств со знаком ³, только здесь дополнительная переменная вводится со знаком (-):

Здесь переменная y_i также называется дополнительной и представляет собой разность между левой и правой частями ограничений: (на столько правая часть может быть меньше левой).

Переменные х_j, , иногда называют основными переменными задачи, чтобы отличать их от дополнительных.

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

Предположим, что переменная x_j – именно такая. Введем две новые неотрицательные переменные x_j`³ 0 и x<sub>j</sub>``³ 0. Затем заменим переменную x<sub>j</sub> на разность этих двух переменных: x<sub>j</sub> = x<sub>j</sub>` - x_j``. Разность неотрицательных чисел по знаку может быть любой (положительной, отрицательной, нулевой). Таким образом, осуществив такую замену, можно избавится от неотрицательной по знаку переменной, не изменив при этом смысл задачи.

Приведем к канонической форме задачу производственного планирования из раздела 1.1. В этой задаче обе переменные неотрицательны, но остальные три ограничения представляют собой неравенства. Следовательно, необходимо ввести три дополнительные переменные. Обозначим их соответственно х₃, х₄ и х₅. Тогда задача примет вид:

max 108х₁ + 112х₂

0,8х₁ + 0,5х₂+ х₃ = 800

0,2х₁ + 0,4х₂+ х₄ = 600

0,01х₁ + 0,1х₂ + х₅ = 120

х_1-5 ³ 0

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

х₃ – неизрасходованный остаток сахарного песка, т;

х₄ - неизрасходованный остаток патоки, т;

х₅ - неизрасходованный остаток фруктового пюре, т.

Далее в разделе 4.2 будет рассмотрено приведение к канонической форме задачи о диете из раздела 1.3.1 и интерпретирован экономический смысл дополнительных переменных.