Москвин Б.В. Теория принятия решений

Подождите немного. Документ загружается.

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

Наиболее изученными и широко применяемыми на практи-

ке при принятии различных решений являются модели линейного

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

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

программы, которая была решена в 1939 г. в работе известного

российского математика академика Л.В.Канторовича [44], однако

наиболее интенсивное развитие линейное программирование

получило

в период 1955-1965 г.г. в связи с работами Данцига Дж.

[26], Гольштейна Е.Г., Юдина Д.Б. [87]. В настоящее время име-

ются значительные успехи в части создания эффективных алго-

ритмов решения этих задач, кроме того, ряд более сложных про-

цедур оптимизации строится на основе использования методов

линейного программирования. В связи с

этим овладение методи-

кой построения моделей, глубокое понимание сущности алгорит-

мов линейного программирования является первым шагом на пу-

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

тия решений во всем ее многообразии.

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

Задача математического программирования называется

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

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

Таким образом, задача линейного программирования (ЛП)

имеет вид

x* = arg

max

x Δ∈

∑

xc , ∆ = {x∈

│

∑

jij

xa ≤ b

, i = 1,…,m }

или

∑

xc → max (c,x) = c

x → max (3.1)

∑

jij

xa ≤ b

, i = 1,…, m или A x ≤ b (3.2)

≥ 0, j = 1,…, n x ≥ 0 (3.3)

Это с т а н д а р т н а я форма записи задачи линейного

программирования.

Терминология задач линейного программирования

Рассмотрим задачу линейного программирования в стан-

дартной постановке

L = c

x → max

A x ≤ b,

x ≥ 0

Здесь

L - значение целевой функции (линейной формы);

A - матрица условий (ограничений);

b - вектор ограничений;

x - допустимое решение (план), если оно удовлетворяет ог-

раничениям (3.2), (3.3);

c - вектор коэффициентов целевой функции (линейной

формы).

Матрицу A можно представить в виде совокупности векто-

ров условий

A = ║ a

,….,a

║,

тогда a

– j-ый вектор условий; или в виде совокупности векторов

ограничений

…

A = a

…

здесь a

= ║ a

,….,a

║ - i-ый вектор ограничений задачи

линейного программирования; i = 1,..., m.

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

Для задачи линейного программирования (3.1)-(3.3) функ-

ция Лагранжа имеет вид

L(x, μ) = c

x + μ

(b - Ax)= c

x + μ

b - μ

Ax = μ

b + (c

- μ

A)x =…

т.к. L(x,μ) - число, то последнее выражение можно транспониро-

вать, тогда

…= b

μ + x

(c - A

μ)

Итак, с одной стороны

L(x, μ) = c

x + μ

(b - Ax) (3.4)

с другой стороны L(x, μ) = b

μ + x

(c - A

μ) (3.5)

Из теоремы Куна-Таккера (см. 2.4) следует, что

max min L(x, μ) = min max L(x, μ)

x μ μ x

или с учетом (3.4),(3.5)

max min (c

x + μ

(b - Ax)) = min max (b

μ + x

(c - A

μ))

x μ μ x

Ф(x) Ψ(μ)

Последнее выражение описывает связь двойственных задач, его

можно переписать в виде

max (c

x + min μ

(b - Ax)) = min (b

μ + max x

(c - A

μ))

x μ μ x

Здесь min μ

(b - Ax), при любом μ ≥ 0 не существует, если (b - Ax)

≤ 0. Следовательно, должно выполняться условие (b - Ax) ≥ 0.

Аналогично, max x

(c - A

μ), при любом x ≥ 0 не существует,

если (c - A

μ) ≥ 0. Следовательно, должно выполняться условие

(c - A

μ)) ≤ 0.

Отсюда получаем пару д в о й с т в е н н ы х (сопряженных)

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

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

L = c

x → max M = b

μ → min

A x ≤ b, A

μ ≥ c

x ≥ 0 μ ≥ 0

Можно показать, что если рассматривать двойственную за-

дачу, как прямую, то прямая задача будет по отношению к ней

двойственной.

Вектор ограничений b часто интерпретируется как вектор

ресурсов, необходимых для реализации решения x. Тогда двой-

ственные переменные μ можно интерпретировать, как стоимость

(ценность) использования ресурсов в единицах критерия L.

Рассмотрим свойства двойственных задач линейного про-

граммирования.

1). Значение целевой функции прямой задачи, вычисленное

для некоторого решения x, не превышает значения целевой

функции двойственной задачи.

x ≤ b

2). Если x* и μ* - оптимальные решения прямой и двойствен-

ной задач, то c

x* = b

μ* (то есть L = M).

3). Если в прямой задаче

0 = μ<

∗

∑

jij

то ,b xa

. Действительно,

если i-го ресурса в избытке, то стоимость его использования рав-

на 0 .

4). Если в двойственной задаче

0 = >μ

∗

∑

jij

xто ,c a

. Дейст-

вительно, если затраты при использовании j-го ресурса превы-

шают прибыль, то такой ресурс нет смысла использовать.

Отметим, что свойства 1, 2 вытекают непосредственно из

теоремы Куна-Таккера; свойства 3, 4 являются интерпретацией

условий дополняющей нежесткости для задач линейного про-

граммирования (см. 2.4).

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

Наряду со стандартной формой записи задач линейного

программирования (3.1)-(3.3) широко используется запись задач в

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

L = c

x → max

A x = b, (3.6)

x ≥ 0

при этом b ≥ 0.

Каноническая форма записи является более общей, чем

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

рования может быть сведена к канонической форме. Действи-

тельно, пусть имеется s-е ограничение вида

b xa ≤

∑

тогда в канонической форме оно будет иметь следующий вид

s1nj

bx xa =+

∑

Значение переменной x

n+1

характеризует величину, на кото-

рую левая часть меньше правой. В целевой функции переменной

n+1

соответствует 0, т.е. она имеет вид (c

,...,c

,0) x → max. Соот-

ветственно, если k-е ограничение имеет вид

b xa ≥

∑

, тогда в канонической форме

k1nj

bx- xa =

∑

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

мирования в канонической форме, имеет вид

L = b

μ → min

μ ≥ c

Т.е. компоненты вектора μ могут принимать и отрицательные

значения. Действительно, стандартная задача линейного про-

граммирования (3.1)-(3.3) в канонической форме будет иметь вид

x + 0

→ max

A x + E x

= b,

x≥0, x

≥ 0.

Здесь x

- дополнительные переменные;

E - единичная матрица;

– транспонированный вектор, все компоненты которого

равны 0.

Задача двойственная к последней будет иметь вид

μ → min

μ .≥ c,

E μ ≥. 0, откуда μ ≥ 0

т.е. будет иметь вид задачи, двойственной к задаче линейного

программирования в стандартной форме.

3.2. Свойства выпуклых многогранников в задаче

линейного программирования

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

стандартной форме (3.1)-(3.3)

L = c

x → max

A x ≤ b .

x ≥ 0

или

L = c

+ ….+ c

→ max

+ …. + a

≤ b

. . . . . . . . . . . . . . . . . .

+ …. + a

≤ b

≥ 0, j = 1,…, n

Каждое i-е ограничение задачи линейного программирова-

ния задает некоторое замкнутое полупространство.

Сформулируем ряд определений и утверждений, которые

будут использоваться в дальнейшем.

Выпуклые многогранники

♦ В ы п у к л о е м н о г о г р а н н о е м н о ж е с т в о - непус-

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

♦ В ы п у к л ы й м н о г о

г р а н н и к - ограниченное много-

гранное множество.

♦ Г р а н ь ю многогранного множества размерности h в R

называется пересечение n-h линейно независимых гиперплоско-

стей.

♦ В е р ш и н о й многогранника называется грань нулевой

размерности (пересечение n линейно независимых гиперплоско-

стей).

♦ Вершина многогранника М - крайняя точка М.

Линейная независимость

♦ Система векторов

R D x,...,x

⊆∈

называется л и н е й н о

з а в и с и м о й, если в линейной комбинации векторов

=α

∑

существует k ∈ {1,…,r}, такое, что α

≠ 0

В противном случае система векторов называется л и н е й н о

н е з а в и с и м о й. Т.е., если

=α

∑

, то ∀α

= 0 .

♦ Если система векторов {x

,..., x

} линейно зависима, то хотя

бы один из векторов является линейной комбинацией остальных,

т.е.

ki,1i

ikk

x x x

∑

≠=

α=∃

♦ Линейно независимая система векторов называется м а к -

с и м а л ь н о й линейно независимой системой в D, если добав-

ление к ней любого вектора из D делает ее линейно зависимой.

♦ Любая максимальная линейно независимая система векто-

ров называется б а з и с о м (

базой) в R

♦ Р а н г о м системы векторов D = {x

,..., x

} называется ко-

личество векторов в максимальной линейно независимой систе-

ме; rang D = r.

♦ Ранг матрицы А (множество векторов) равен максимальному

порядку отличных от нуля миноров А.

♦ Максимальное число линейно независимых строк А равно

максимальному числу линейно независимых столбцов и равно

рангу А.

Утверждение.

Пусть задан многогранник М(А, b) ограничениями Аx ≤ b,

x ≥ 0, где А - матрица размерности m×n. Тогда, если решение x

соответствует вершине многогранника М(А, b), то оно называет-

ся о п o р н ы м решением и представимо в виде

x = ( x

, x

)

где x

- базисные переменные x

- небазисные (свободные) пере-

менные. Причем,

≥ 0, │x

│= m; x

= 0, │x

│= n-m,

т.е. опорное решение представимо в виде x = (x

, 0)

Тогда A = ║ S ¦ Q ║,

где S = ║ a

, a

, … ,a

║ - матрица базиса и множество векторов

, a

, … ,a

} - базис матрицы А.

= {s1,s2,…,sm} - номера векторов условий, образующих

базис.

Если x - опорное решение, то ограничения задачи линейно-

го программирования могут быть представлены в виде

A x = b ⇒ S x

+ Q x

= b,

откуда следует, что x

= S

-1

b, т.к. x

= 0.

Действительно, в любой вершине многогранника М(А,b) пе-

ресекаются n гиперплоскостей. Причем m гиперплоскостей зада-

ются ограничениями вида A x = b, a (n-m) гиперплоскостей зада-

ются ограничениями вида x

= 0

Утверждение.

Оптимальное решение задачи линейного программирова-

ния соответствует хотя бы одной вершине (крайней точке) выпук-

лого многогранника М(А,b).

Действительно, пусть известно множество крайних точек

M(A,b), а именно {x

,…,x

}. Тогда ∀x∈M(A,b) представимо в

виде

* x x

∑

α=

. Тогда

x = c

* x

∑

*xc

∑

→ max

L max L

= , т.е. оптимум достигается в к-ой крайней точке (вер-

шине многогранника).

Очевидно, что число вершин выпуклого многогранника, за-

даваемого ограничениями задачи линейного программирования,

конечно. Тогда, на основе организации направленного перебора

решений x, соответствующих вершинам многогранника (опорных

решений), и, сравнения значений целевой функции, вычисленных

при этих решениях, можно найти оптимальное решение

x*, соот-

ветствующее максимальному значению целевой функции.

3.3. Геометрическое представление задач линейного

программирования

Задача линейного программирования в стандартной форме

имеет вид:

L = c

x → max

A x ≤ b .

x ≥ 0

Здесь x ∈ R

, пусть n = 2. Тогда задача будет иметь вид

+ c

→ max (3.7)

+ a

≤ b

. . . . . . . . . . . . . . (3.8)

+ a

≤ b

, x

≥ 0 (3.9)

Структура области допустимых решений

♦ Ограничения (3.9) задают положительный ортант (2 полу-

пространства).

♦ Ограничения (3.8) задают пересечение m полупространств в

♦ {x

,…,x

} - вершины выпуклого многогранника (0-мерные

грани), в вершинах пересекаются n (n=2) гиперплоскостей.

♦ ∀x ∈ M(A,b) - линейная комбинация крайних точек x*

. При-

чем для представления любого x таких точек должно быть не бо-

лее 3.

♦ В зависимости от структуры ограничений (3.8), (3.9) можно

различать 3 случая:

А).

Δ = ∅ - ограничения

противоречивы

в совокупности.

Б).

Δ ≠ ∅ и Δ - ограниченное

множество

(т.е. Δ- многогранник).

В).

Δ ≠ ∅ и Δ - неограниченное

множество

(Δ - многогранное множество).

Целевая функция.

Целевая функция в задаче линейного программирования

имеет вид

L = c

+ c

Тогда L

= c

+ c

- линия уровня L

(гиперплоскость). Гради-

ент целевой функции

∇L =

∂

= (c

)

Линия уровня перпендикулярна градиенту ∇L .

В зависимости от направленности градиента можно разли-

чать ситуации:

- в случае А) - нет ни одного решения (не зависимо от направлен

ности градиента).

- в случае Б): а - решение существует и оно единственно (реше-

ние соответствует некоторой вершине много-

гранника) ;

б - решение существует и оно не

единственно, су-

ществует множество эквивалентных решений

(решение соответствует некоторой грани много-

гранника) ;

- в случае В): а - решение существует и оно единственно;

б - решение существует и оно не единственно;

в - решения не существует - целевая функция неог-

раниченно возрастает на множестве допустимых

решений;

Таким образом, можно сформулировать следующие свой-

ства решений

задачи линейного программирования.

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

♦ Оптимальное решение, если оно существует, находится на

границе допустимой области.

♦ Оптимальное решение всегда достигается в некоторой край-

ней точке (вершине) многогранника М(А,b).

♦ Оптимальное решение может быть не единственным, тогда

оно достигается как минимум в 2-х крайних точках.

♦ Задача может не иметь решения, хотя допустимые решения

существуют (целевая функция не ограничена на множестве до-

пустимых решений).