Презентация - Семенкин Е.С. Методы оптимизации
Подождите немного. Документ загружается.
Теорема 6. Если Х=(x
1
,x
2
,..., x
n
) - угловаяточкамногогранникарешений, то
векторывразложении (4), соответствующиеположительным x
i
являются
линейнонезависимыми.
Доказательство. Безограниченияобщностиможноположитьнеравными
нулюпервые k компонентвектора X, такчто
= A
0
.
Допустим, чтосистемавекторов A
1
, А
2
,..., A
k
линейнозависима. Тогда
существуюттакиечисла l
1
,l
2
,...,l
k
,невсеравныенулю, прикоторыхвыполняется
соотношение
l
1
A
1
+ l
2
А
2
+ ... + l
k
A
k
= 0. (*)
Поусловию,
x
1
A
1
+ x
2
А
2
+ ... + x
k
A
k
= A
0
. (**)
Зададимнекотороечисло ε>0, умножимнанегоравенство (*); прибавляяи
вычитаярезультатиз (**), получим:
(x
1
+εl
1
)A
1
+ (x
2
+εl
2
)A
2
+ … + (x
k
+εl
k
)A
k
= A
0
,
(x
1
- εl
1
)A
1
+ (x
2
- εl
2
)A
2
+ … + (x
k
- εl
k
)A
k
= A
0
.
Т
.
е
.
система
уравнений
(
4
)
имеет
два
решения,
которые
могут
и
не
быть
∑
=
k
1i
ii
xA
Приэтом 0.5⋅Х
1
+0.5⋅Х
2
= X,
т. е. Х - выпуклая линейная комбинация точек Х
1
и Х
2
, что
противоречитусловиютеоремыотом, что Х - угловаяточка.
Итак, допущение, чтосистемавекторов A
1
, А
2
,..., A
k
линейнозависима,
привелокпротиворечию. Следовательно, сделанноедопущениеневернои
системавекторовлинейнонезависимая. <
Следствие1. Таккаквекторы A
1
, А
2
,..., A
n
имеютразмерностьт,то
угловая точка многогранника решений имеет не более чем т
положительныхкомпонент.
Следствие2. Каждой угловой точке многогранника решений
соответствует k≤тлинейнонезависимыхвекторовсистемы A
1
, А
2
,..., A
n
.
Нетеряяобщности, можнопредположить, чтосистемавекторов
A
1
, А
2
,..., A
n
задачилинейногопрограммирования (1)-(3) всегдасодержит
т линейнонезависимыхвекторов. Еслиприрешениичастнойзадачиэто
свойство
не
очевидно,
то
первоначальную
систему
векторов
дополняют
т
Итак, еслицелеваяфункциязадачилинейногопрограммирования
ограниченанамногогранникерешений, то:
1) существуеттакаяугловаяточкамногогранникарешений, вкоторой
целеваяфункциязадачилинейногопрограммированиядостигаетсвоего
оптимума;
2) каждыйопорныйплансоответствуетугловойточкемногогранника
решений.
Поэтомудлярешениязадачилинейногопрограммированиянеобходимо
исследоватьтолькоугловыеточкимногогранникарешений, т. е. только
опорныепланы.
Симплекс-методпредложенДж. Данцигомв1947 г. непосредственноприменяетсяк
общейзадачеЛПвканоническойформе:
Z=C
T
X→min,
приограничениях
X ≥ 0, AX = B, B > 0,
Любоенеотрицательноерешениесистемы AX=B называется допустимым решением
Система AX=B можетбытьрешена, если n-m неизвестныхприравнятькнулюи
разрешитьееотносительнооставшихся
Еслиполученное решениеединственно, тоононазывается базисным решением
Если базисноерешение допустимо, тоононазывается базиснымдопустимым решением
Переменные, равныенулювбазисномрешении, называются небазиснымипеременными.
Остальныеназываются базисными иобразуют базис.
Утверждение 2.1. Еслиограниченияимеютдопустимоерешение, тоониимеюти
базисноерешение.
Утверждение 2.2. Допустимаяобластьявляетсявыпуклыммножеством.
Утверждение 2.3. Базисные допустимые решения соответствуютвершинам
допустимогомножества.
Утверждение
2
.
4
.
Если
целевая
функция
имеет
конечный
минимум,
то
по
крайней
мере
Симплекс-метод решения задач ЛП
Общая схема симплекс-метода
Z=C
T
X→min,
X ≥ 0, AX = B, B > 0,
А =ER
E - единичнаяматрица, размерности m,
R - матрица-остаток
c
1
,c
2
,...,c
n
, x
1
,x
2
,..., x
m
,...
............................................................................
, ...
, ...
2211
222221122
112211111
mnmnmmmmmmm
nnmmmm
nnmmmm
bxaxaxax
bxaxaxax
bxaxaxax
′
=
′
++
′
+
′
+
′
=
′
++
′
+
′
+
′
=
′
+
+
′
+
′
+
++++
++++
++++
∑
=
++++
=
′
++
′
+
′
=−
m
i
iinnmmmm
bcZxcxcxcZZ
1
022110
, ,...
0,,0,0,,,,
21
''
22
'
11
=
=
=
=
=
=
++ nmmmm
xxxbxbxbx KK
)0,,0,0,,,,(
''
2
'
1
KK
m
bbb
'
i
b
, >0
x
1
,x
2
,..., x
m
- базисныепеременные
x
m+1
, x
m+2
,..., x
n
- небазисные
Симплекс-методобеспечиваетсистематическуюпроцедурутакойзаменыодного
допустимогобазисногорешениянадругое, прикоторойзначениецелевойфункции
уменьшается.
1. Найтипеременнуюдлявключениявбазис.
x
m+1
, x
m+2
,..., x
n
- небазисные
<0(x
s
↑⇒ Z↓)
≥0 ⇒ ≥0∀i ⇒Zнеможетбытьуменьшено ⇒ решениенайдено
2. Найтипеременнуюдляисключенияизбазиса.
Пусть >0.
Пока x
s
=0⇒ограничениеимеетвид: x
i
=b.
x
s
>0 ⇒ ограничениепринимаетвид: x
i
+ a
'
is
x
s
=b.
x
i
≥0⇒maxx
s
=b/a
'
is
(или x
i
, станетотрицательным)
Если a
'
is
<0, то x
s
↑⇒x
i
↑,т.е.x
i
≥0всегда.
Рассматриваявсе i =1,..., m, имеем
x
s
= min(b/a
'
is
).
{
}
''
2
'
1
'
,...,,min
nmms
cccc
++
=
'
s
c
'
s
c
'
i
c
s
i
a
'
'
i
'
i
'
i
max
,0
,
,...,2,1
>
=
is
a
mi
'
i
max
,0
,
,...,2,1
>
=
is
a
mi
'
r
3. Записатьзадачувновойформе.
Переменная x
s
сталабазисной.
Новыйбазисимеетвид: x
1
, x
2
,..., x
r-1
, x
s
, x
r+1
,..., x
m
а. Коэффициентпри x
s
введущейстрокенадосделатьравнымединице
(ведущуюстрокуразделитьна a'
rs
).
б. Необходимо исключить x
s
из других ограничений (из i-й строки,
имеющей коэффициент a
'
is
при x
s
вычесть ведущую строку (с коэффициентом
1 при x
s
) умноженную на a'
is
, i=1, ..., m, i≠r).
в. Преобразоватьцелевуюфункцию (коэффициент c'
s
<0 при x
s
), вычитаяиз
нееновуюведущуюстроку, умноженнуюна c'
s
.
Построив новую задачу (эквивалентную исходной), необходимо
вернутьсякшагу 1.
Есливсекоэффициентыцелевойфункциинеотрицательны, тозадача
решена.
Еслиприэтомнекоторыекоэффициентыравнынулю, тоимеетсяболее,
чем
одно,
оптимальное
решение
.
Порождение начального допустимого базиса
Пустьисходнаязадачаимеетвид:
z=c
1
x
1
+c
2
x
2
+...+c
n
x
n
→min
приограничениях:
x
i
≥ 0, i =1,...,n,
.. . . . . . . .
. . . . . . . . . . . . . . . . . . . . .
...
...........................
. . .
. . . . . . . . . . . . . . . . . . . . .
,+. . . . .
,. . . . . . .
. . . . . . . . . . . . . . . . . . . .
,. . . . . . . .
,11,
,1,111,1
,,11,
1,111,1
,11,
1,111,1
212121
212121
111
111
mnnmm
mmnnmmmm
mmnnmmmm
mnnmm
mnnmm
nn
bxaxa
bxaxa
bxaxa
bxaxa
bxaxa
bxaxa
≤⋅++⋅
≤⋅++⋅
=⋅++⋅
=⋅+⋅
≥⋅++⋅
≥
⋅
+
+
⋅
++++++
+++
+++
Впервые m
1
ограниченийввести дополнительные переменные x
n+1
,..., с
коэффициентом -1.
Впоследние m
3
ограниченийввести дополнительные переменные
скоэффициентом +1.
Впервые m
1
+m
2
ограниченийввести искусственные переменные
скоэффициентом +1.
Искусственныепеременныеипоследние m
3
дополнительныепеременныеобразуют
начальноедопустимоебазисноерешение, координатыкоторогосовпадаютсправыми
частямиограничений.
В
целевую
функцию
Z
дополнительные
переменные
входят
с
нулевым
1
mn
x
+
311
,...,
1 mmnmn
xx
++++
313131
,...,
1 mmmmnmmn
xx
+++++++
Транспортная задача ЛП
Имеется m пунктовпроизводствасобъемамипроизводства a
i
,i=1,..., m и n
пунктовпотреблениясобъемамипотребления b
j
,j=1,..., n,c
ij
- стоимость
транспортировкиодногоизделия (единицыпродукции) изпунктапроизводства
i впунктпотребления j. Задачазаключаетсявпланированииперевозокот
поставщиковкпотребителям, минимизирующихстоимостьтранспортировки.
x
ij
- объем планируемой перевозки продукции от поставщика i к
потребителю j
z=c
11
x
11
+c
12
x
12
+...+c
mn
x
1
→ min,
x
11
+x
12
+...+x
1n
=a
1
,
x
21
+x
22
+...+x
2
n
=a
2
,
. . . . . . . . .
x
m
1
+x
m
2
+...+x
mn
=a
m
,
x
11
+x
21
+x
m
1
=b
1
,
x
12
+x
22
+x
m
2
=b
2
,
.
.
.
.
.
.
.
.
.
x
ij
≥ 0,i=1,...,m,j=1,...,n,
Есливтранспортнойзадачевыполняетсяусловие
тоонаназывается задачейзакрытоготипа. Транспортнаязадачазакрытоготипа
всегдаимеетрешение.
Есливтранспортнойзадачесуммарныезапасынесовпадаютссуммарными
потребностями, тоесть
тоонаназывается задачейоткрытоготипа.
Транспортнаязадачаоткрытоготипарешаетсяприведениемкзадачезакрытого
типа, длячеговводится фиктивныйпоставщик или фиктивныйпотребитель. Если
суммарныепотребностипревышаютсуммарныезапасы, товводятсяфиктивный
поставщиксобъемомпроизводства (запасов)
n1,j ,bx
m1,i ,ax
minxcz
j
m
1i
ij
i
n
1j
ij
m
1i
n
1j
ijij
==
==
→=
∑
∑
∑∑
=
=
= =
a b
i j
j
n
i
m
=
==
∑∑
,
11
a b
i j
j
n
i
m
≠
==
∑∑
,
11
.
11
1
∑∑
==
+
−=
m
i
i
n
j
jm
aba