Формы представления задач линейного программирования

Задача линейного программирования может быть сформулирована в одной из нескольких форм - канонической, стандартной или общей. Для анализа особенностей каждой из форм представления задачи линейного программирования (ЛП) их удобно свести в таблицу.

Общая	Стандартная	Каноническая
1. Ограничения
Уравнения и неравенства	Неравенства	Уравнения
2. Условия неотрицательности переменных
Часть переменных	Все переменные	Все переменные
3. Целевая функция

Анализируя можно видеть, что наиболее строгие требования к форме записи предъявляет каноническая форма представления задачи, наименее строгие - общая. Видно, что в общей форме представления ЗЛП ограничения могут быть представлены как в виде неравенств, так и в виде уравнений. Знак части переменных может быть не определен, а целевая функция может максимизироваться или минимизироваться. Все это не позволяет напрямую применять разработанный математический аппарат для решения задачи ЛП. Для решения задачи линейного программирования ее необходимо привести к канонической форме. Каноническая форма характеризуется тем, что ограничения имеют вид линейных уравнений. Переход от ограничений - неравенств к ограничениям уравнениям можно осуществить по определенным правилам:

1. Пусть имеется неравенство вида ax ³ c. Очевидно, что для того, чтобы левая часть стала равной правой части из нее необходимо вычесть некоторое неотрицательное число. Введя новую переменную x ₂, получим

ax ₁ - x ₂ = c при x ₂.0 (x ₁ и x ₂ ³ 0)

если ax ₁£ c, то при x ₂³0 ax ₁ + x ₂ = c.

Видно, что ценой перехода от неравенства к уравнению является новая переменная.

2. Если знак переменных не определен, поступаем следующим образом. Пусть

a ₁ x ₁ + a ₂ x ₂ = c

и при этом известно, что x ₁³0, тогда x ₂ может быть как отрицательной, так и положительной величиной. Введем две новых переменных x ₃ и x ₄. Причем

x ₂ = x ₃ - x ₄. Видно, что если x ₃³0 и x ₄³0 переменная x ₂ может иметь любой знак. Таким образом, получим

a ₁ x ₁ + a ₂ x ₃ - a ₂ x ₄ = c

при этом x ₁³0, x ₃³0, x ₄³0

Введя одну дополнительную переменную, мы получили необходимое условие неотрицательности переменных.

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

a 11 x 1 + a 12 x 2 +... + a 1 j xj +... + a1 n xn = b 1 a 21 x 1 + a 22 x 2 +... + a 2 j xj +... + a2 n xn = b 2 ............................................. ai 1 x 1 + ai 2 x 2 +... + aijxj +... + ainxn = bi .............................................. am1x1 + am 2 x 2 +... + amjxj +... + amnxn = bm

(3.6)

и обращают в минимум целевую функцию

_ L () = c 1 x 1 + c 2 x 2 +... + cjxj +... + cnxn

(3.7)

В такой постановке задача называется основной задачей линейного программирования (ОЗЛП).

Очевидно, что при m=n задача имеет единственное решение и с точки зрения выбора оптимального решения на нескольких альтернативных интереса не представляет. Нас будет интересовать случай, когда m < n. В этом случае задача имеет множество решений, а следовательно, существует возможность выбора наилучшего решения.

Всякую совокупность неотрицательных значений переменных x ₁, x ₂, x ₃,..., x_n, удовлетворяющих ограничениям (3.5), назовем допустимым или опорным решением ОЗЛП. Множество допустимых решений представляет собой подмножество множества неотрицательных значений x ₁, x ₂, x ₃,..., x_n, и образует область допустимых решений (ОДР).

Совокупность значений x ₁ ^*, x ₂ ^*,..., x_n^*, переменных, доставляющих минимальное значение целевой функции L (x), называется оптимальным решением ОЗЛП.

ОЗЛП может не иметь решения по следующим причинам:

1. Система ограничений (3.5) несовместна, то есть, вообще не имеет решений (уравнения противоречат друг другу).

2. Система (3.5) не имеет ни одного неотрицательного решения.

3. На множестве неотрицательных решений системы (3.5) целевая функция может принимать сколь угодно больше по абсолютной величине отрицательные значения, то есть .

Перейдем к рассмотрению графической интерпретации основной задачи линейного программирования.