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

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

(6)

или

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

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

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

(7)

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

(8)

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

(9)

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

1.4.3 Матричная форма записи

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

С = (с₁, с₂, . . ., с_j, . . . , с_n) – вектор-строка коэффициентов целевой функции,

B = - вектор-столбец свободных членов (правых частей ограничений),

X = - вектор-столбец переменных,

A = - матрица коэффициентов в левых частях ограничений (каждая ее строка соответствует ограничению, а каждый столбец – переменной).

Тогда задача линейного программирования в канонической форме запишется следующим образом:

(10)

Задача в стандартной форме будет иметь вид:

(11)

или .

В самом деле, по правилам перемножения векторов СХ = с₁х₁+ с₂х₂+ … + с_nх_n=. Это и есть линейное выражение в целевой функции.

Умножая матрицу А размерности (mxn) на вектор Х (nx1), получают столбец изmвыражений, т.е. матрицу (mx1). Каждое их этих выражений получают умножением строки матрицы А на столбец Х, т.е. а_i1х₁ + а_i2х₂+ … + а_i1х_n=. Тогда АХ представляет собой столбец выражений в левых частях ограничений: АХ =. Благодаря тому, что во всех ограничениях стоит один и тот же знак, этот столбец можно сравнить со столбцом В. Тогда запись АХ = В представляет собой систему уравнений в ограничениях задачи в канонической форме (АХВ или АХВ – соответственно системы неравенств в задачах в стандартной форме).

Отметим, что О в формулах (10) и (11) представляет собой не одно число, а нулевой вектор (столбец из nнулей), поскольку каждая изnпеременных сравнивается с нулем.