Математическое программирование (линейное программирование). Киселева Э.В - 25 стр.

UptoLike

ВУЗ: 

НГАСУ «Сибстрин» | Новосибирск

Составители: 

Рубрика: 

51 52
Следовательно, в ограниченной выпуклой многогранной об-
ласти всегда существует вершина, в которой целевая функция
принимает максимальное значение.
Теорема 5.3. Если целевая функция имеет максимум
более чем в одной вершине выпуклого многогранника до-
пустимых решений, то этот максимум достигается в
любой точке, являющейся выпуклой линейной комбина-
цией этих вершин.
Предположим, целевая функция
Χ
Ζ
С
=
достигает макси-
мума в нескольких вершинах:
r
,,,
ΧΧΧ
K
21
многогранника, т.е.
).r,i(CX
i
max
1==
Ζ
Пусть .dCX
i
=
Рассмотрим произвольную выпуклую линейную комбина-
цию этих вершин:
)r,i(,,
i
r
i
i
i
r
i
i
'
101
11
=≥==
∑∑
==
λλΧλΧ
и покажем, что значение целевой функции
)X(
'
Ζ
также равно d.
Действительно, имеем:
.dd)С(CСX)(
r
i
i
i
r
i
i
i
r
i
i
''
===⋅==
∑∑∑
=== 111
λΧλΧλΧΖ
Опорный план. Теорема о соответствии опорного плана
вершине многогранника допустимых планов
Рассмотрим ЗЛП в канонической форме:
⎪
⎩
⎪
⎨
⎧
=++
=++
,
,
1
11111
mnmnmn
nn
bxaxa
bxaxa
L
LLLLLL
L
),,1(0 njx
j
=≥
.XCXСΖ
nn
max
11
→++
=
L
Предположим, что число линейно независимых уравнений
системы ограничений равно m (m<n). Методом Жордана–Гаусса
приведем систему к базисному виду:
⎪
⎪
⎩
⎪
⎪
⎨
⎧
=+++
=++++
=++++
++
++
++
.xxx
,xxx
,xxx
mnn,mmm,mm
nn,mm,
nn,mm,
βαα
βαα
βαα
L
LLLLLLLLLL
LL
LL
11
221122
111111
(Не ограничивая общности, можно считать, что базисными
переменными являются
m
xxx ,,,
21
K .)
Очевидно, базисное решение системы имеет вид:
).,....,,,,(
mn
,тбаз
321
K
−
=
00
21
β
β
β
Χ
Определение 5.1. Неотрицательное базисное решение
системы ограничений ЗЛП называется опорным решени-
ем (опорным планом) ЗЛП.
Из определения следует, что:
1)
если ,0,,0
1
≥≥
т
β
β
K то соответствующее базисное ре-
шение является опорным решением ЗЛП;
2)
число положительных координат опорного плана не мо-
жет превышать m.
Определение 5.2. Опорный план называется невырож-
денным, если число его положительных компонентов
равно m, и вырожденным в противном случае.
Теорема 5.4.
Вектор Х является опорным планом ЗЛП
тогда и только тогда, когда Х
– вершина многогранника
допустимых планов
.
Итак, для нахождения оптимального решения ЗЛП достаточ-
но исследовать вершины выпуклого многогранника допустимых
решений. В этом и состоит основная идея симплекс-метода ре-
шения ЗЛП. 
    Следовательно, в ограниченной выпуклой многогранной об-                          Предположим, что число линейно независимых уравнений
ласти всегда существует вершина, в которой целевая функция                       системы ограничений равно m (m

Страницы