Составители:
Рубрика:
49 50
5. СВОЙСТВА ДОПУСТИМЫХ ПЛАНОВ ЗАДАЧИ
ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ.
ОПОРНЫЙ ПЛАН
Не ограничивая общности, рассмотрим свойства допустимых
планов на примере канонической формы модели ЗЛП:
,bAx =
(5.1)
,0≥x (5.2)
.СX max→=
Ζ
(5.3)
Основные свойства этой задачи формулируются в следую-
щих теоремах, которые, по сути, обобщают свойства ЗЛП с двумя
переменными на случай любого числа переменных.
Теорема 5.1. Множество планов ЗЛП выпукло.
Необходимо показать, что если X
1
и X
2
– допустимые планы
ЗЛП (5.1)–(5.3), то их выпуклая линейная комбинация:
,
2
2
1
1
ΧλΧλΧ
+=
где
100
2121
=
+≥≥ λλ,λ,λ ,
также является ее допустимым планом, т.е. удовлетворяет систе-
ме (5.1)–(5.3).
Итак, пусть X
1
и X
2
– допустимые планы задачи (5.1)–(5.3),
т.е. справедливы соотношения:
,,b 0
11
≥=
ΧΑΧ
.,b 0
22
≥=
ΧΑΧ
Возьмем два любых числа
0
1
≥
λ
и
,0
2
≥
λ
таких, что
,1
21
=+
λ
λ
и умножим первое равенство на
1
λ
, второе – на
2
λ
.
Складывая результаты, получим:
)(b
21
2
2
1
1
λλΑΧλΑΧλ
+=+
или
,b)( =+
2
2
1
1
ΧλΧλΑ
т.е.
2
2
1
1
ΧλΧλΧ
+=
удовлетворяет системе (5.1).
А так как
,,,, 0000
21
21
≥≥≥≥
λλΧΧ
то 0≥
Χ
также
удовлетворяет условию (5.2).
Таким образом, доказано, что выпуклая линейная комбина-
ция векторов X
1
и X
2
также является допустимым планом задачи
(5.1)–(5.3) и, следовательно, согласно определению, множество
планов ЗЛП выпукло.
Множество допустимых планов ЗЛП может быть ограничен-
ным и тогда оно называется
выпуклым многогранником, а его
крайние точки –
вершинами.
Если же оно неограниченное, то его называют
выпуклым
многогранным множеством.
Теорема 5.2.
Если целевая функция
Χ
Ζ
С
=
имеет
максимум на выпуклом многограннике допустимых реше-
ний, то он достигается по крайней мере в одной из вер-
шин этого многогранника.
Выпуклый многогранник имеет конечное число вершин,
обозначим их через
,,,,
к
ΧΧΧ
K
21
а точку, где функция Z имеет
максимум, через X
*
. Очевидно, ).к,i(СXС
i*
1=≥
Χ
Если среди вершин найдется хотя бы одна вершина, например,
),кр(
р
≤≤1
Χ
для которой
,СС
р*
ΧΧ
=
то теорема доказана.
Предположим противное, т.е. что Х
*
не является вершиной. То-
гда для каждой вершины
i
X
должно выполняться соотношение:
.к,i(СС
*i
)1=<
ΧΧ
Но, согласно свойству ограниченных выпуклых множеств
(см. теорему 3.2), точку
*
Χ
можно представить в виде выпуклой
линейной комбинации крайних точек (вершин):
)к,i(,,
i
k
i
i
i
k
i
i
*
101
11
=≥==
∑∑
==
λλΧλΧ
.
Подставляя Х
*
в целевую функцию и принимая во внимание
ее линейность, получим:
,CXCX)CX()С(СС
*
k
i
i
**
i
k
i
i
k
i
i
i
k
i
i
*
==<=⋅=
∑∑∑∑
==== 1111
λλΧλΧλΧ
что является противоречием. Полученное противоречие возникло
в силу предположения о том, что
*
Χ
не является вершиной.
5. СВОЙСТВА ДОПУСТИМЫХ ПЛАНОВ ЗАДАЧИ Таким образом, доказано, что выпуклая линейная комбина-
ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ. ция векторов X1 и X2 также является допустимым планом задачи
ОПОРНЫЙ ПЛАН (5.1)–(5.3) и, следовательно, согласно определению, множество
планов ЗЛП выпукло.
Не ограничивая общности, рассмотрим свойства допустимых Множество допустимых планов ЗЛП может быть ограничен-
планов на примере канонической формы модели ЗЛП: ным и тогда оно называется выпуклым многогранником, а его
Ax = b , (5.1) крайние точки – вершинами.
x ≥ 0, (5.2) Если же оно неограниченное, то его называют выпуклым
многогранным множеством.
Ζ = СX → max . (5.3)
Теорема 5.2. Если целевая функция Ζ = СΧ имеет
Основные свойства этой задачи формулируются в следую-
щих теоремах, которые, по сути, обобщают свойства ЗЛП с двумя максимум на выпуклом многограннике допустимых реше-
переменными на случай любого числа переменных. ний, то он достигается по крайней мере в одной из вер-
Теорема 5.1. Множество планов ЗЛП выпукло. шин этого многогранника.
Необходимо показать, что если X1 и X2 – допустимые планы Выпуклый многогранник имеет конечное число вершин,
ЗЛП (5.1)–(5.3), то их выпуклая линейная комбинация: обозначим их через Χ 1 , Χ 2 ,K , Χ к , а точку, где функция Z имеет
Χ = λ1Χ 1 + λ2 Χ 2 , максимум, через X*. Очевидно, СΧ * ≥ СX i ( i = 1, к ).
где λ1 ≥ 0 , λ2 ≥ 0 , λ1 + λ2 = 1 , Если среди вершин найдется хотя бы одна вершина, например,
также является ее допустимым планом, т.е. удовлетворяет систе- Χ ( 1 ≤ р ≤ к ), для которой СΧ * = СΧ р , то теорема доказана.
р
ме (5.1)–(5.3). Предположим противное, т.е. что Х* не является вершиной. То-
Итак, пусть X1 и X2 – допустимые планы задачи (5.1)–(5.3), гда для каждой вершины X i должно выполняться соотношение:
т.е. справедливы соотношения:
СΧ i < СΧ * ( i = 1,к ).
ΑΧ 1 = b , Χ 1 ≥ 0,
Но, согласно свойству ограниченных выпуклых множеств
ΑΧ= b , Χ 2 ≥ 0.
2
(см. теорему 3.2), точку Χ * можно представить в виде выпуклой
Возьмем два любых числа λ1 ≥ 0 и λ2 ≥ 0 , таких, что линейной комбинации крайних точек (вершин):
λ1 + λ2 = 1, и умножим первое равенство на λ1 , второе – на λ2 . k k
Χ * = ∑ λi Χ i , ∑ λi = 1 , λi ≥ 0 ( i = 1,к ) .
Складывая результаты, получим: i =1 i =1
λ1ΑΧ 1 + λ2ΑΧ 2 = b( λ1 + λ2 ) Подставляя Х* в целевую функцию и принимая во внимание
или ее линейность, получим:
k k k k
Α ( λ1Χ 1 + λ 2 Χ 2 ) = b ,
СΧ * = С ⋅ ∑λi Χ i = ∑λi ( СΧ i ) < ∑ λi ( CX* ) = CX* ∑λi = CX* ,
т.е. Χ = λ1Χ 1 + λ 2 Χ 2 i=1 i=1 i=1 i=1
удовлетворяет системе (5.1). что является противоречием. Полученное противоречие возникло
А так как Χ 1 ≥ 0 , Χ 2 ≥ 0 , λ1 ≥ 0 , λ2 ≥ 0 , то Χ ≥ 0 также в силу предположения о том, что Χ * не является вершиной.
удовлетворяет условию (5.2).
49 50
Страницы
- « первая
- ‹ предыдущая
- …
- 22
- 23
- 24
- 25
- 26
- …
- следующая ›
- последняя »
