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

Общей задачей линейного программирования (ОЗЛП) называют задачу

(2.10)

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

, (2.11)

, (2.12)

, (2.13)

, (2.14)

x_j — произвольные , (2.15)

где c_j , A_ij , b_i — заданные действительные числа; (2.10) — целевая функция; (2.11)—(2.15) — ограничения; x = ( x₁ , ..., x_n ) — план задачи.

Задачу линейного программирования можно представить в 3-х различных видах: развернутом, матричном и векторном.

Приведенная выше ОЗЛП записана в развернутой или индексной форме. В этой же форме задачу можно представить и несколько иначе:

(2.16)

при линейных ограничениях:

(2.17)

, (2.18)

x_j — произвольные ,

здесь c_j , A_ij , b_i  — заданные действительные числа; (2.16)  целевая функция; (2.17) — ограничения; (2.18) — условие неотрицательности части переменных; x = ( x₁, ... , x_n ) — план задачи.

Рассмотрим теперь матричную форму записи ЗЛП. Введем следующие обозначения:

; ,

, ,

где C — матрица-строка; A — матрица системы уравнений; X — матрица-столбец переменных; A₀ — матрица-столбец свободных членов.

Тогда наша задача примет вид:

; (2.19)

, X  0 , (2.20)

или

mаx (min) Z = C X , A X {, =,  }A₀ , X  0 . (2.21)

Полезной является также векторная форма ЗЛП. Для столбцов матрицы A введем обозначения:

, , ..., , ..., .

Тогда задача (2.10)—(2.15) в векторной форме записи примет вид:

mаx (min) Z = CX ; (2.22)

A₁x₁ + ... + A_jx_j + A_nx_n = A₀ , X  0 , (2.23)

где CX  скалярное произведение векторов C = ( c₁; ...;c_n ) и X = (x₁ , ... , x_n).

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

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

Канонической формой записи ЗЛП называют задачу

; (2.24)

, (2.25)

. (2.26)

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

1) минимизация целевой функции (2.24);

2) запись системы ограничений в виде строгих равенств (2.25);

3) условие неотрицательности на все переменные (2.26);

4) наличие в системе ограничений исходного базиса;

5) неотрицательность всех свободных членов в системе ограничений. 

Переход к канонической форме.

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

При необходимости задачу максимизации можно заменить задачей минимизации, и наоборот. Для функции одной переменной это утверждение очевидно. В самом деле, если x* — точка минимума функции y = f ( x ), то для функции y = – f ( x ) она является точкой максимума, так как графики функций f ( x ) и – f ( x ) симметричны относительно оси абсцисс (рис. 2.1).

рис. 2.1

Итак,

min f ( x* ) = – mаx ( – f ( x* )).

То же самое имеет место и в случае функции n переменных:

min f ( x₁* , ..., x_n* ) = – mаx ( – f ( x₁* , ..., x_n* )).

Таким образом, если в исходной ЗЛП целевая функция максимизируется,

т. е. , (2.27)

то выполнив замену Z₁=–Z, получаем новое выражение

(2.28)

и эквивалентную ЗЛП.

Как следует из примеров задач линейного программирования, в них большинство ограничений задается неравенствами. Для перехода к канонической форме необходимо заменить все неравенства на строгие равенства.

Пусть исходная ЗЛП имеет вид

, (2.29)

, (2.30)

, (2.31)

. (2.32)

Преобразуем ее к каноническому виду. Введем m дополнительных (балансовых) неотрицательных переменных x_n+i  0 ( i = ). Для того чтобы неравенства типа  (2.30) преобразовать в равенства, к их левым частям прибавим дополнительные переменные x_n+i  (i = ), после чего система неравенств (2.30) примет вид

. (2.33)

Для того чтобы неравенства типа   (2.31) преобразовать в равенства, из их левых частей вычтем дополнительные переменные x_n+i  ( i = ) . Получим

. (2.34)

Систему уравнений (2.33), (2.34) с условием неотрицательности дополнительных переменных называют эквивалентной системе неравенств (2.30), (2.31).

Дополнительные переменные x_n+i  ( i = ) в целевую функцию вводятся с коэффициентами, равными нулю. Получим задачу:

; (2.35)

, (2.36)

, (2.37)

. (2.38)

Задача (2.35)—(2.38) имеет каноническую форму. Задачи (2.29)—(2.32) и (2.35)—(2.38) тесно связаны между собой.

Т е о р е м а 1. Каждому допустимому решению задачи (2.29)—(2.32) соответствует вполне определенное допустимое решение задачи (2.35)—(2.38), где x_n+i  0 (i = ), и наоборот, каждому допустимому решению задачи (2.35)—(2.38) соответствует допустимое решение решению задачи (2.29)—(2.32).

Д о к а з а т е л ь с т в о. Пусть — допустимое решение задачи (2.29)—(2.32). Для условий (2.30) обозначим

, (2.39)

для условий (2.31) —

. (2.40)

Из условий (2.39) и (2.40) следуют условия (2.36)—(2.38). Отсюда x⁰ =  есть определенное допустимое решение задачи (2.35)—(2.38).

Аналогично доказывается обратное утверждение. Теорема доказана.

Так как дополнительные переменные входят в целевую функцию (2.35) с коэффициентами, равными нулю, то значения целевых функций (2.29) и (2.35) при соответствующих допустимых решениях и одинаковы. Отсюда следует, что целевые функции (2.29) и (2.35) на множестве соответствующих допустимых решений достигают экстремального значения одновременно. Оптимальному решению задачи (2.29)— (2.32) соответствует оптимальное решение задачи (2.35)—(2.38), т. е. исходная задача и ее каноническая форма эквивалентны.

Отметим экономический смысл дополнительных переменных. Они в каждой задаче прямо связаны с ее экономическим содержанием.

Например, для задачи о наилучшем использовании ресурсов

, (2.41)

т. е. дополнительная переменная показывает величину неиспользованного ресурса. Для задачи о смесях

, (2.42)

т. е. дополнительная переменная показывает потребление соответствующего питательного вещества в оптимальном плане сверх нормы.

В ряде производственно-экономических ситуаций не на все переменные налагаются условия неотрицательности. В подобных ситуациях, даже если ограничения представлены в виде равенств, задача не будет канонической. Для представления такой задачи в каноническом виде каждую из переменных x_k , на которые не наложено условие неотрицательности, заменим разностью двух неотрицательных переменных и , т. е. , где . Очевидно, что при этом мы получим эквивалентную задачу.

И, наконец, рассмотрим два последних признака того, что ЗЛП представлена в каноническом виде. Это наличие в системе ограничений исходного базиса при неотрицательности всех свободных элементов данной системы; другими словами, наличие в системе ограничений выделенного исходного опорного решения.

Ï ð è ì å ð  1.  Привести к канонической форме следующую задачу линейного программирования:

Р е ш е н и е . 

1) Минимизируем целевую функцию задачи путем введения новой функции Z₁ : .

2) В системе ограничений ЗЛП перейдем к строгим равенствам, для чего введем неотрицательные «балансовые» переменные x₄ и x₅ в левые части неравенств со знаками минус и плюс (в зависимости от знака неравенства). В результате ЗЛП запишется в следующем виде:

3) Перейдем к преобразованию условий неотрицательности. Данное условие не наложено только на одну переменную x₁ (назовем ее произвольной). Исключим эту переменную из задачи, выполнив следующую замену переменных:

где .

При этом получаем следующее:

4) Выделяем в системе ограничений базис при неотрицательных свободных членах.

A'1	A"1	A2	A3	A4	A5	A0
1	-1	-1	0	-1	0	-2	*( -1 )
5	-5	2	0	0	1	15
3	-3	-1	-1	0	0	3
A'1	A"1	A2	A3	A4	A5	A0
-1	1	1	0	1	0	2
5	-5	2	0	0	1	15
3	-3	-1	-1	0	0	3
A'1	A"1	A2	A3	A4	A5	A0	A0/A'1
-1	1	1	0	1	0	2
5	-5	2	0	0	1	15	3
3	-3	-1	-1	0	0	3	1
						min	1
A'1	A"1	A2	A3	A4	A5	A0
0	0	0,666667	-0,33333	1	0	3
0	0	3,666667	1,666667	0	1	10
1	-1	-0,33333	-0,33333	0	0	1

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