Презентация - Семенкин Е.С. Методы оптимизации
Подождите немного. Документ загружается.
Теория линейного программирования
Данылинейнаяфункция: Z=C
1
x
1
+C
2
x
2
+…+C
n
x
n
(1)
и система линейных ограничений:
=+++++
=+++++
=+++++
=
+
+
+
+
+
,
bxa...xa...xaxa
........................................................
,bxa...xa...xaxa
.......................................................
,bxa...xa...xaxa
,bxa...xa...xaxa
mnmnjmj2m21m1
ininjij2i21i1
2n2nj2j222121
1n1nj1j212111
(2)
x
j
≥0,(j=1,2,…,n), (3)
где а
ij
, b
i
и C
j
– заданныепостоянныевеличины.
Найтитакиенеотрицательныезначения x
1
,x
2
,…,x
n
,которыеудовлетворяют
системеограничений (2) идоставляютцелевойфункции (1) минимальное
значение.
Всистемеограничений (2) все b
i
, i=1,2,…,m,безпотериобщностиможно
считатьнеотрицательными.
Ввекторнойформе: Z=C
T
X → min
приограничениях: A
1
x
1
+A
2
x
2
+…+A
n
x
n
=A
0
, X≥0, (4)
A
1
= , A
2
= , …, A
n
= , A
0
= .
m1
21
11
a
a
a
M
m2
22
12
a
a
a
M
mn
2n
1n
a
a
a
M
m
2
1
b
b
b
M
Определение1. Планом или допустимымрешением задачилинейного
программированияназываетсявектор X=(x
1
,x
2
,…,x
n
), удовлетворяющий
условиям (2) и (3).
Определение2. План X=(x
1
,x
2
,…,x
n
)называется опорным, если
векторы A
i
(i=1,2,…,m),входящиевразложение (4) сположительными
коэффициентами x
i
, являютсялинейнонезависимыми.
Замечание. Так как векторы A
i
являются m-мерными, то из
определенияопорногопланаследует, чточислоегоположительных
компонентнепревышает m.
Определение 3. Опорныйпланназывается невырожденным, еслион
содержит m положительныхкомпонент, впротивномслучаеопорныйплан
называется вырожденным.
Определение 4. Оптимальнымпланом или оптимальнымрешением
задачилинейногопрограммированияназываетсяплан, доставляющий
наименьшее (наибольшее) значениецелевойфункции.
Пустьнаплоскости x
1
Ox
2
заданыдветочки: A
1
(x
1
(1)
; x
2
(1)
) и A
2
(x
1
(2)
; x
2
(2)
),
определяющиепрямолинейныйнаправленныйотрезок .
Координатыпроизвольнойвнутреннейточки A (x
1
;x
2
):
, λ
1
≥0, λ
2
≥0, λ
1
+λ
2
=1. (5)
или:
А=λ
1
А
1
+λ
2
А
2
, λ
1
≥0, λ
2
≥0, λ
1
+λ
2
=1.
Точка А, длякоторойвыполняютсяэтиусловия, называется выпуклой
линейнойкомбинациейточек А
1
и А
2
.
При λ
1
=1 и λ
2
=0 точка А совпадаетсА
1
,при λ
1
=0 и λ
2
=1–сА
2
.
Точки А
1
и А
2
называются угловыми или крайнимиточками отрезка .
Замечание. Изопределениявыпуклойлинейнойкомбинацииточек
очевидно, что угловаяточканеможетбытьпредставленакаквыпуклая
линейнаякомбинациядвухдругихточекотрезка.
2
1
AA
+=
+=
,xxx
xxx
(2)
2
2
(1)
2
12
(2)
1
2
(1)
1
11
,
λλ
λλ
2
1
AA
∑
=
n
1j
j
λ
Определение6. Множествоточекназывается выпуклым, еслионовместес
любымидвумяточкамисодержитиихпроизвольнуювыпуклуюлинейную
комбинацию.
Геометрическийсмысл: множествувместесегодвумяпроизвольными
точкамиполностьюпринадлежитипрямолинейныйотрезок, ихсоединяющий.
Определение7. Точкамножестваназывается граничной, еслилюбойшарс
центромвэтойточкесодержиткакточки, принадлежащиемножеству, такиточки,
непринадлежащиеему. Граничныеточкимножестваобразуютего границу.
Определение8. Замкнутым называетсямножество, содержащиевсесвои
граничныеточки.
Замечание. Замкнутое множество может быть ограниченным и
неограниченным.
Определение9. Множествоназывается ограниченным, еслисуществуетшар
радиусаконечнойдлинысцентромвлюбойточкемножества, которыйполностью
содержитвсебеданноемножество; впротивномслучаемножествоназывается
неограниченным.
Теорема 1. Пересечение выпуклых множеств является выпуклым
множеством.
Доказательство
.
Пусть
F
=
F
1
∩
F
2
,
F
1
и
F
2
-
выпуклые
множества
.
А
1
,
А
2
-
две
2
1
AA
2
1
AA
2
1
AA
Определение10. Угловымиточками выпуклогомножестваназываются
точки, неявляющиесявыпуклойкомбинациейдвухпроизвольныхточек
множества.
Выпуклоемножествоможетиметьконечноеибесконечноечисло
угловыхточек.
Определение11. Выпуклым многоугольником называется выпуклое
замкнутоеограниченноемножествонаплоскости, имеющееконечноечисло
угловыхточек. Угловыеточкимногоугольниканазываютсяего вершинами, а
отрезки, соединяющие две вершины и образующие его границу, -
сторонами многоугольника.
Определение12. Опорной прямой выпуклого многоугольника
называетсяпрямая, имеющаясмногоугольником, расположеннымпоодну
сторонуотнее, хотябыоднуобщуюточку.
Определение13. Выпуклым многогранником называется замкнутое
ограниченноевыпуклоемножествотрехмерногопространства, имеющее
конечноечислоугловыхточек. Угловыеточкимногогранниканазываются
его вершинами; многоугольники, ограничивающиемногогранник,-гранями,
отрезки, покоторымонипересекаются,-ребрами.
Определение14. Опорной плоскостью многогранника называется
плоскость,
имеющая
с
многогранником,
расположенным
по
одну
сторону
от
Теорема 2. Замкнутый, ограниченный, выпуклыймногогранникявляется
выпуклойлинейнойкомбинациейсвоихугловыхточек.
Доказательство. Докажемтеоремудлямногоугольника, имеющего n вершин.
Сначала докажем, что любая точка треугольника удовлетворяет теореме. А -
произвольная точка треугольника А
1
А
2
А
3
.
А∈ ⇒
А=t
1
А
1
+t
4
А
4
, t
1
≥0, t
4
≥0, t
1
+t
4
=1 (*)
А
4
∈ ⇒
А
4
=t
2
А
2
+t
3
А
3
, t
2
≥0, t
3
≥0, t
2
+t
3
=1. (**)
Подставляя (**) в (*): A=t
1
A
1
+t
4
(t
2
A
2
+t
3
A
3
)=t
1
A
1
+t
2
t
4
A
2
+t
3
t
4
A
3
.
Полагая
t
1
=
λ
1
,
t
2
t
4
=
λ
2
,
t
3
t
4
=
λ
3
:
А
=
λ
1
А
1
+
λ
2
А
2
+
λ
3
А
3
,
4
1
AA
3
2
AA
причем λ
1
≥0, λ
2
≥0, λ
3
≥0, λ
1
+λ
2
+λ
3
=1,
т. е. точка А является выпуклой линейной комбинацией А
1
, А
2
, А
3
.
Выпуклый многоугольник, имеющий n вершин (n>3) разобьем на n–2
треугольника, произвольнаяточка А попадетводинизних. Безограничения
общностиможноположить, чтоонапопалавтреугольник А
1
А
2
А
3
. Тогда, какуже
доказано, точка А являетсявыпуклойлинейнойкомбинациейтрехвершин:
А=λ
1
А
1
+λ
2
А
2
+λ
3
А
3
. Поэтому
А=λ
1
А
1
+λ
2
А
2
+λ
3
А
3
+0⋅А
4
+…+0⋅А
n
,
λ
j
≥0 (j=1, 2, …, n), =1,
т. е. точка А являетсявыпуклойлинейнойкомбинациейугловыхточек
многоугольника.
Доказательстводлямногогранникапроводитсяаналогично. <
Теорема 3. Множествовсехплановзадачилинейногопрограммирования
выпукло.
Доказательство. ПустьХ
1
иХ
2
–планызадачиЛП, т.е.
AX
1
=A
0
, X
1
≥0;AX
2
=A
0
, X
2
≥0,
Х=λ
1
Х
1
+λ
2
Х
2
, λ
1
≥0, λ
2
≥0, λ
1
+λ
2
=1,
- ихпроизвольнаявыпуклаялинейнаякомбинация.
Тогда
∑
=
n
1j
j
λ
Теорема 4. Целеваяфункциязадачилинейногопрограммированиядостигает
своегоминимальногозначениявугловойточкемногогранникарешений.
Еслицелеваяфункцияпринимаетминимальноезначениеболеечемводной
угловойточке, тоонадостигаеттогожезначениявлюбойточке, являющейся
выпуклойлинейнойкомбинациейэтихточек.
Доказательство. Предположим, что многогранник решений К является
ограниченным, имеющимконечноечислоугловыхточек.
Пусть X
1
, Х
2
,..., Х
р
,- угловыеточки К, Х
0
- оптимальныйпланзадачиЛП.
Тогда Z(Х
0
) ≤ Z(X) ∀Х∈К. Если Х
0
– угловаяточка, топерваячастьтеоремы
доказана.
Предположим, что Х
0
неявляетсяугловойточкой; тогдапотеореме 2
Х
0
=λ
1
Х
1
+λ
2
Х
2
+...+λ
p
Х
p
, λ
i
≥0(i=1,2,…, p), =1.
Таккак Z(X)–линейнаяфункция
Z(Х
0
)=Z(λ
1
Х
1
+λ
2
Х
2
+...+λ
p
Х
p
)=λ
1
Z(X
1
)+λ
2
Z(X
2
)+...+λ
p
Z(X
p
) (*)
Пусть т = Z(Х
k
)–наименьшееиз Z(Х
i
)(i=1,2, ..., р) вразложении (*), X
k
–
одна
из
угловых
точек
.
∑
=
p
1i
i
λ
∑
=
p
1i
i
λ
∑
=
p
1i
i
λ
так как ∀λ
i
≥0, =1.
Т.е. Z(X
0
) ≥ т, нопопредположениюХ
0
–оптимальныйплан, т.е.
Z(X
0
) ≤ т, следовательно Z(X
0
)=т=Z(X
k
), где X
k
– угловаяточка.
Для доказательства второй части теоремы допустим, что Z(X)
принимаетминимальноезначениеболеечемводнойугловойточке,
напримервX
1
,Х
2
,..., Х
q
,1<q≤р; тогда Z(X
1
)=Z(Х
2
)=...=Z(X
q
)=т.
Пусть
Х = λ
1
Х
1
+λ
2
Х
2
+...+λ
q
Х
q
, λ
i
≥0(i=1,2,…,q), =1,
тогда
Z(Х) = Z(λ
1
Х
1
+λ
2
Х
2
+...+λ
q
Х
q
) =
= λ
1
Z(X
1
) + λ
2
Z(X
2
) +...+ λ
q
Z(X
q
) =
= λ
1
m + λ
2
m +...+ λ
q
m = т = m,
т. е. целевая функция Z принимает минимальное значение в
произвольнойточке X, являющейсявыпуклойлинейнойкомбинацией
угловыхточек X
1
, Х
2
,..., Х
q
. <
Замечание. Еслимногогранникрешенийявляетсянеограниченной
областью, тонекаждуюточкуобластиможнопредставитьвыпуклой
линейной комбинацией угловых точек области. Задачу ЛП с
многогранником
решений,
представляющим
собой
неограниченную
∑
=
q
1
i
i
λ
∑
=
q
1
i
i
λ
Теорема 5. Еслиизвестно, чтосистемавекторов A
1
,А
2
,..., A
k
(k≤п) в
разложении (4) линейнонезависимаитакова, что
A
1
x
1
+ А
2
x
2
+...+A
k
x
k
=А
0
,
гдевсе x
j
≥0, тоточка Х=(x
1
, x
2
,..., x
k
,0,…,0) являетсяугловойточкой
многогранникарешений.
Здесь Х – n-мерныйвектор, последние п-k компоненткоторогоравнынулю.
Доказательство. Предположим, чтоточка Х неявляетсяугловой. Тогда
Х=λ
1
Х
1
+λ
2
Х
2
, λ
1
≥0, λ
2
≥0, λ
1
+λ
2
=1,
где X
1
и Х
2
– некоторыеточкимногогранникарешений.
Очевидно, что
Х
1
=(x
1
(1)
, x
2
(1)
, …, x
k
(1)
, 0, …, 0),
Х
2
=(x
1
(2)
, x
2
(2)
, …, x
k
(2)
, 0, …, 0).
Поскольку X
1
и Х
2
– планы, то
A
1
x
1
(1)
+ A
2
x
2
(1)
+…+ A
k
x
k
(1)
=A
0
,
A
1
x
1
(2)
+ A
2
x
2
(2)
+…+ A
k
x
k
(2)
=A
0
Вычитаяизпервогосоотношениявторое:
(
x
(1)
-
x
(2)
)
A
+ (
x
(1)
-
x
(2)
)
A
+ … + (
x
(1)
–
x
(2)
)
A
= 0.