4. ЛИНЕЙНОЕ ПРОГРАММИРОВАНИЕ

4.1.Постановка задачи

Постановка задачи имеет вид

Q x cT x max ,

(4.1)

x X

X x : x En , x , Ax b ,

(4.2)

или в развернутом виде

Q x cT x c x

c

x

c

x

... c

n

x

n

,

a x a x ... a n xn b

a x

... a n xn b

a x

Ax b ..........................................

,

a

x

a

m

x

... a

mn

x

n

b

m

m

a	a	...	a n
где A a	a	...	a n	– матрица коэффициентов ограничений задачи;
	...	...
...			...
am	am	...	amn

cТ c c ...cn T – вектор-строка коэффициентов целевой функции.

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

Условие x представляет собой неотрицательный ортант n-мерного евклидова пространства E n . Каждое из ограничений – неравенств (4.2)

n
aij x j bi , i , ,...,m	(4.3)

j

также определяет замкнутое пространство в E n , либо принадлежащих гиперплоскости Ax b , либо расположенных по одну сторону от этой гиперплоскости.

В общем случае пересечение замкнутых полупространств представляет собой выпуклое многомерное множество или выпуклый многогранник.

Поскольку Q x cT x – гиперплоскость, то даже из геометрических

представлений ясно, что решение задачи, если оно существует, не может быть внутренней точкой множества Х, а должно принадлежать границе допустимого множества. Следовательно, решением может быть одна вершина или несколько вершин и все точки, лежащие между этими вершинами. В трехмерном пространстве соответственно - вершина, ребро или плоскость

(рис. 4.1).

89

x
	X	gradQ x
		линии равного
			уровня Q(x)
		с	с
	с		x
	а)
x2
с	с
	gradQ x

А

Х

В x1

в)

x		h x	граничная линия
			равного уровня	Q (x)
			грани
		А
Q		X	вершины
	1
			h x
		gradQ x	x
		б)
	x

x

г)

x	gradQ x
	x

д)

x 3

грани

вершины

x 1

ребра

x 2

е)

Рис. 4.1. Геометрия задач линейного программирования:

а) неограниченность множества Х; б) решение в вершине А множества Х; в) решение на грани АВ; г) решение отсутствует (множество Х пусто);

д) множество не замкнуто; е) допустимое множество в трехмерном пространстве

90

Возможны два случая, когда задача не может иметь решения:

1)ограничения являются несовместными, так что допустимое множество пусто (рис. 4.1, г);

2)неограниченность допустимого множества (рис. 4.1, а, д).

Итак, задача линейного программирования (ЛП) имеет единственное решение (в вершине), либо бесконечное множество решений (ребро, грань), либо не имеет решений (если допустимое множество пусто или не ограничено).

4.2.Двойственные задачи ЛП

Втеории ЛП чрезвычайно важную роль играет то обстоятельство, что каждой задаче ЛП соответствует некоторая двойственная задача. Если исходная задача ЛП, называемая прямой задачей, является задачей на максимум типа (4.1) при условии (4.2), то двойственная задача представляет собой задачу на минимум

		G λ bT λ min ,	(4.4)
		λ
		λ : λ E m , λ , AT λ c ,	(4.5)
где λ ,...,	m	– вектор-столбец размерности m .

Если к задаче (4.4) (4.5) применить двойственные преобразования, то мы придем к исходной задаче (4.1).

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

- если прямая задача-задача максимизации, то двойственная минимиза-

ции;

-коэффициенты целевой функции в прямой являются свободными членами в ограничениях двойственной;

-свободные члены из ограничений прямой задачи становятся коэффициентами целевой функции в двойственной задаче;

-знаки неравенств в ограничениях меняются на противоположные. Если система неравенств задачи на max, кроме неравенств содержит

неравенства , то перед построением двойственной задачи эти неравенства умножением левой и правой части на -1 «переводят» в неравенства . Если равенства, то заменяют двумя неравенствами и одно из них умножают на -1. В задаче на min все наоборот.

Справедливы следующие соотношения для прямой и двойственной задач в матричной форме (табл. 4.1).

Для анализа основных свойств двойственных задач используют метод множителей Лагранжа. Для постановки задачи (4.1) при условиях (4.2) функция Лагранжа имеет вид

L x, λ cT x λT b Ax .	(4.6)
91

92

maxQ x min G λ* ;

Тогда согласно теореме Куна-Таккера решение задачи (4.1) x

при су-

ществовании λ удовлетворяют условиям Куна-Таккера

L cT λТ A ,

x

x cT λТ

L

A x ,

x

L

b Ax ,

.

(4.7)

λ

L

λТ b

λТ

λ

Ax ,

х ,

λ .

Таблица 4.1

Взаимосвязь прямой и двойственной задачи

Прямая задача

Двойственная задача

сT x max

bT λ min

Ax b,x

T

A λ c, λ

сT x min

bT λ max

Ax b,x

T

A λ c, λ

сT x max

bT λ min

Ax b, x

T

A λ c, λ

сT x min

bT λ max

Ax b,x

T

A λ c, λ

К этим же условиям придем, если составим функцию Лагранжа для двойственной задачи (4.4) при условии (4.5). Эти условия позволяют сформулировать и доказать следующие основные теоремы ЛП [2]:

- теорема существования: для того чтобы задача ЛП имела решение, необходимо и достаточно, чтобы допустимые множества Х как прямой так и двойственной задачи были непусты;

- теорема двойственности: некоторый допустимый вектор тогда, и только тогда, является решением задачи ЛП, когда существует такой допустимый вектор двойственной задачи, что значения целевых функций обеих задач в этих векторах равны

(4.8)

- теорема о дополняющей нежесткости: для того чтобы допустимые

векторы x и λ являлись решением двойственных задач, необходимо и достаточно, чтобы они удовлетворили условиям дополняющей нежесткости

с			Т	A x
	Т	λ
								(4.9)
Т							.
λ		b Ax

Результат (4.9) непосредственно следует из условий Куна-Таккера (4.7). Для интерпретации двойственных переменных, можно воспользоваться тем обстоятельством, что они являются множителями Лагранжа и поэтому их можно считать показателями чувствительности оптимального значения целевой функции к изменениям констант ограничений (см. раздел 2). Для прямой

	задачи имеем	Q x
	λ			(4.10)
		b
	и для двойственной	G λ
	x		.	(4.11)
		c

	,
Из (4.10) следует, что если некоторая двойственная переменная i

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

Пример 4.1. Исходная задача
							Q x x			x	x x x min ,
											x X
x : x E , x				i	, i ,...,
	x x x
где X										.
x x		x x x
x x			x				x		x

Необходимо сформулировать двойственную задачу.

Решение. В соответствии с табл. 4.1 ограничения задачи должны быть типа .

Для этого преобразуем равенство в два неравенства типа и , и одно из них домножим на -1. Тогда задача примет вид

Q x x x x x x min ,

X

93