Преобразование неограниченных по знаку переменных

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

Значение может быть как положительным так и отрицательным в зависимости от соотношения величин и .

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

при ограничениях

(2.4)

(2.5)

(2.6)

где - неограниченная по знаку переменная.

Преобразуем эту задачу к стандартной форме.

1. Заменим на , где .

2. Умножим обе части уравнения (2.6) на –1.

3. Введем дополнительные переменные в ограничения (2.4) и (2.5) соответственно.

4. Припишем нулевые коэффициенты переменным в целевой функции. Целевая функция при этом не меняется.

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

при ограничениях

Используя стандартную форму задачи линейного программирования в матричных обозначениях

при ограничениях

сформулируем основные определения.

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

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

Определение 2.6. Оптимальным решением называется такой допустимый вектор , для которого соответствующее ему значение целевой функции больше, чем для любого другого допустимого решения. Или, другими словами, вектор называется оптимальным, если и для всех . Оптимальным значением задачи линейного программирования называется значение целевой функции, соответствующее оптимальному решению. Если - оптимальное значение, то .