Стандартная форма задачи линейного программирования

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

или

Любая задача в смешанной форме может быть приведена к любой из стандартных форм. Рассмотрим приведение к стандартной форме на max (на min приводится аналогично).

Если какая-то из переменных задачи не ограничена по своему знаку, то ее заменяют на разность двух неотрицательных переменных точно так же, как это делается при приведении задачи к канонической форме (см. раздел 1.4.1).

Необходимо добиться, чтобы во всех остальных ограничениях стоял знак £. Предположим, что в некотором ограничении стоит знак ³. Тогда обе его части умножаются на -1, при этом знак неравенства меняется на противоположный.

Предположим, что некоторое ограничение является уравнением. Тогда его заменяют на два неравенства следующим образом (в самом деле, ведь «равно» означает «не больше и не меньше»):

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

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