Файл: Васильев Ф.П. Лекции по методам решения экстремальных задач.pdf
ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 11.04.2024
Просмотров: 242
Скачиваний: 1
140 |
МИНИМИЗАЦИЯ ФУНКЦИИ МНОГИХ ПЕРЕМЕННЫХ |
|||
Покажем, что векторы \Alt А2, . . . |
, |
Ак линейно независимы. |
||
Пусть |
вопреки утверждению существует |
|
|
|
|
k |
|
|
|
кой, |
что V z£At= Az — 0. |
Возьмем |
|
|
|
i=l |
|
|
|
|
€ Ет. Так |
как и^> 0, |
то |
при достаточно малых |
е > 0 |
будем иметь Mi^O, ы2^ 0 , кроме того, Ащ = Ь, Au2 — b, т. е. |
ределению угловой точки и множества U. Следовательно, векторы А\,. . . Ах линейно независимы, и_ранг матрицы А раврн к. Тогда
р ^ к , и, вычеркнув из матрицы А |
р—к строк, линейно выражаю- |
щиеся через остальные строки А, |
получим искомую квадратную |
невырожденную матрицу порядка |
к Х к и соответствующий век |
тор Ь, для которых Ви — Ь. Попутно мы доказали, что матрицу В можно выбрать так, что ее порядок будет совпадать с числом не нулевых координат угловой точки.
Д о с т а т о ч н о с т ь . |
Пусть |
точка |
u £ U |
и |
удовлетворяет |
усло |
||||||||
вию (15). |
Пусть и = |
аых + (1 — а)ы 2 |
при |
некоторых их, |
u ^ U и |
|||||||||
0 < а < < 1 . Покажем, |
что |
такое |
представление |
и |
возможно |
только |
||||||||
при ы = ы1 = ы2. В |
самом |
деле, |
если ]'ф]'г, |
r = |
|
1, |
2, . . . |
, |
k, |
то из |
||||
0 < а < 1 , |
ы{ > 0 , |
и'2 > 0 |
имеем |
0 = и' = |
аи[ + (1 — а) |
> |
0, |
что |
||||||
возможно только при и[ — и!2== 0 |
(/Ф j r, |
г — 1, |
2 .......... |
k). |
Тогда |
|||||||||
из Aui = b |
следует, |
что Вщ = Ь , |
где и, |
|
|
. |
| ( t = l , |
2). |
Однако |
|||||
|
|
|
|
|
|
|
|
u’k / |
|
|
|
|
|
|
|В |=/=0, |
поэтому их = |
«а = и> а |
тогда |
и1 = |
ий — и. |
Следовательно, |
||||||||
и — угловая точка U. А |
|
|
|
|
|
|
|
|
|
|
|
Таким образом, для решения задачи (10) достаточно пере брать угловые точки множества U. В силу теоремы 7 число угло вых точек U конечно, так как число невырожденных миноров матрицы А конечно. Однако даже в задачах не очень большой размерности число угловых точек.может быть столь большим, что простой перебор угловых точек U может оказаться невозможным за разумный промежуток времени даже при использовании самых
§ 11] |
Элементы линейного программирования |
141 |
|
быстродействующих ЭВМ. Идея многих |
методов решения задач |
||
линейного программирования заключается в построении |
такого |
||
упорядоченного |
перебора угловых точек, при котором |
значение |
|
-функции (с, и) |
убывает при переходе от |
одной угловой |
точки к |
другой. На этой идее основан и симплекс-метод, к изложению ко торого мы сейчас переходим.
4. Напоминаем, что в задаче (10) матрица А имеет поряд
.рХпг, поэтому ранг матрицы А удовлетворяет неравенству:
rang/4<;m in (р ; т ). Если бы rang А = т, то это означало |
бы, |
что |
||||||
множество |
U состоит не более чем из одной точки, и задача |
ми |
||||||
нимизации |
(с, и) в этом случае становится тривиальной. |
|
Поэтому |
|||||
•будем считать, что |
U = 0 , rang |
А = р < т — этого всегда |
можно |
|||||
добиться, |
исключив |
из равенств |
(Ли)г= & г-, i= 1 , 2, . . . , р, |
линейно- |
||||
.зависимые. Кроме того, симплекс-метод |
будем |
излагать |
в предпо- |
|||||
.ложении невырожденности задачи |
(10). |
и ф 0 |
|
|
U назы |
|||
О п р е д е л е н и е 2. Угловая |
точка |
множества |
|
вается невырожденной, если соответствующая матрица В из тео
ремы 7 имеет порядок p = rangЛ </n |
и число |
положительных |
координат точки и в точности равно р. |
Задача |
(10) называется |
невырожденной, если невырождена каждая угловая точка множе
ства |
Ц. |
|
|
|
|
Пусть известна некоторая угловая точка и множества U. |
В |
||
силу |
невырожденности задачи и теоремы 7 |
можем |
считать, |
что |
|
( |
ап , |
, а1в |
|
> 0 , В =
аръ ••• I &рр
Рассмотрим вектор
и — aB~l Ак
О
О |
k = p + 1, . . . , т, а > 0 , |
а |
|
О |
|
О
142 МИНИМИЗАЦИЯ ФУНКЦИИ МНОГИХ ПЕРЕМЕННЫХ [Гл. г
где а — £-тая компонента |
вектора |
ua,k ( £ > р ) . |
Так |
как |
|
ц > 0 , |
то |
||||||||||||||
найдется |
а о> 0 , такое, |
что «a,ft > 0 |
при всех |
а, 0 < |
а < |
а 0. |
Кроме |
||||||||||||||
того, |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
р |
_ |
|
|
|
|
|
|
|
|
_ |
|
|
|
|
|
|
_ |
|
|
|
Aua,k = ^ |
|
Л; (и — аБ-1 Ak)i + |
Akа = |
В(и-^- аБ -1 ЛА) + |
Ака |
= Ви = |
Ь- |
||||||||||||||
|
i= 1 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||
при всех |
а , поэтому ыа>й £ U при 0 •< а < а 0. |
Далее; |
|
|
|
|
|
|
|
||||||||||||
(с, иа>к) = (с, и |
а Б - 1 Ак) + а ск = (с, и) — а [(с, Б“ >Л*) — c j . |
|
|||||||||||||||||||
Обозначим |
ДА= (с, Б-1 Лй) — ск\ тогда (с, wa.fc) = (с, |
|
и) — аДй (k — |
||||||||||||||||||
= р + |
1, |
. . . , /п). |
Величины Дй имеют смысл и при £ = 1 , 2 , . . . , |
р,. |
|||||||||||||||||
при этом |
согласно определению |
обратной матрицы В-1 ЛА= |
ек, и по |
||||||||||||||||||
этому |
Дй = |
(с, Б-> Л*) — ск = |
(с, |
ёА) — ск = 0 (£ = 1, 2, . . . |
|
, р). В за |
|||||||||||||||
висимости от знаков величин ДА, (Б-1 Ak)t возникают три |
возможно |
||||||||||||||||||||
сти. |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
I. |
Все |
величины Д^^О |
(к —1, 2, . .. ,т ). В этом |
случае, |
|
ока |
|||||||||||||||
зывается, |
|
и* —и является |
решением задачи (10). В |
самом |
деле,, |
||||||||||||||||
возьмем К * = — (В~1)*с. Тогда |
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||||
0 > |
Д* = (с, Б - 1Ak) — ск = ((Б -1)' с, Ак) — ок = — (Г , |
Ак) — |
|
||||||||||||||||||
|
|
|
|
|
— ck( k = |
1, ... , т), |
|
|
|
|
|
|
|
|
|
||||||
что равносильно неравенству c - f |
Л 1 * > 0. Далее, |
|
|
|
|
|
|
|
|
||||||||||||
( С , U a ,k ) 1«=о = |
(С, И) |
= |
(С, |
А - 1 £ ) = |
( ( Б - ' ) * с , |
6 ) = |
- |
( b , |
Г ) . |
|
|
||||||||||
Таким |
образом, Я*— решение двойственной задачи |
(13), |
и в- силу |
тео |
|||||||||||||||||
ремы 4 |
тогда и" = и — решение задачи |
(10). |
|
|
|
|
|
|
|
|
|
||||||||||
II. |
Найдется такой |
номер £ > р , |
что Д * > 0 , |
В - 1 ЛА< |
0 |
(напо |
|||||||||||||||
минаем, что Ак = 0 при£ = |
|
1 . . . . , |
р). Тогда задача (10) не имеет решения. |
||||||||||||||||||
В самом деле, в этом случае «со-> |
0, |
Аиа,к = |
Ь, |
т. е. |
ua,k(:U |
при |
|||||||||||||||
всех а > 0 , |
А тогда (с, |
иа й) = ( с , |
и) — аДй-> — оо при |
a -» -j-o o , |
и- |
||||||||||||||||
inf (с, и) = |
— оо. |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||
иес/ |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
III. Найдутся |
такие |
£ > р |
и |
i^ p , что |
Дй> 0 , |
|
(В~1Ак) ,->0.. |
||||||||||||||
В этом случае делается |
итерационный шаг — переходят к следую |
||||||||||||||||||||
щей угловой точке |
ыао, |
а, |
где |
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||
a = |
a0 = |
min JE L Q l |
, |
4 |
= |
{ i : l < i < p , |
(Б~' Л*)£> 0 }^ = |
0 ^ |
|||||||||||||
|
|
|
£6/ft(B-1^ )I. |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||
Так как B~l b = u^> 0, |
то a 0)> 0 . |
Покажем, что «<*„,;•. 6 |
|
|
Посколь |
||||||||||||||||
ку Aua,k = |
b при |
всех |
а,, |
то |
достаточно установить, |
|
что |
|
|
|
|
О» |
§ Щ |
|
|
|
Элементы |
линейного |
программирования |
|
|
|
143 |
||||||
или (и — а 0В-1 Аа)£ > 0 , |
|
|
р. Это очевидно для тех |
i, |
для |
|||||||||||
которых |
|
|
< |
0. |
Пусть |
(B~l Аа)£ > 0, т. |
е. |
i 6 I k- Тогда |
|
|
||||||
|
Q < a 0 < |
{В , |
Ь)‘ |
= -----r -----. |
или и‘ — а 0(В-1 Aft)£ > |
0 |
|
|
||||||||
|
|
|
|
(Br'Afr |
(B~l А& |
|
|
|
|
|
|
|
||||
при всех |
i 6 /й. Таким образом, |
uaoik 6 U, |
|
|
|
|
|
|
||||||||
Покажем, |
что иа„,к— угловая точка U. Пусть минимум |
в опре |
||||||||||||||
делении |
а 0 |
достигается при некотором t = s 6 Д : |
|
|
|
|
|
|||||||||
|
|
|
|
|
|
|
(В-16)£ |
(В -1 6), |
^ |
а |
|
|
|
( 16) |
||
|
|
|
|
|
|
|
|
|
|
(В-1 |
' |
‘ |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||
Тогда |
Ua0, k = us— а 0 (.В |
Ak)s = |
(В-1 6), — а 0 (В~' Ak)s = 0. |
В |
матри |
|||||||||||
це В = |
( А х , |
А2, |
, |
Ар) |
выбросим столбец A s |
и дополним |
столбцом |
|||||||||
АЙ;Тновую матрицу обозначим через С = (Ах, . . . , |
As_ ь |
А*+1, . . . |
, Ар, |
|||||||||||||
Afe), |
кроме |
того, |
вектор-столбец с |
координатами |
ц„,, . . . |
, |
, |
|||||||||
ц ^ 1, . . . |
, ы£0, гД, = |
а 0 |
обозначим через иа„,к. Будем иметь |
|
|
|
||||||||||
~ |
|
р |
|
|
«оAft — |
A;«a0 + ®oA* — В (u — a 0B |
|
|
||||||||
,CUa0,k= |
|
A; |
+ |
1 Aa) |
||||||||||||
|
|
i= I, |
i=/-s |
|
|
|
|
L=1 |
|
|
|
|
|
|
|
+ a 0Aft = Bu = b.
Далее, убедимся в том, что -|С |=/= 0. Пусть
|
|
|
|
Cz = |
|
^ |
ZjAj + |
z* Ak = 0. |
|
|
||||
Так как |
|
|
•i=l, |
|
|
|
|
|
|
|
|
|||
|
|
|
|
|
|
|
|
|
|
|
|
|||
|
|
|
|
Ak = B(B~'A k) = £ |
|
Д ( В - ‘ Аа)£, |
|
|||||||
Cz — |
^ |
|
z£A£- f 2fc ^ |
А£ (В |
1Aft)£ — |
|
|
[z£ -(- (В 1 Ak)t zk] A£ + |
||||||
|
|
t = l , l ^ b s |
t = 1 |
|
|
|
|
|
£ = 1 , i * r S |
|
|
|||
|
|
|
|
+ |
zftAs (B~1Aft)s = 0, |
|
|
|||||||
Из |
линейной независимости |
Ax, |
A2, . . . |
, Ap тогда следует, что |
||||||||||
|
zc + |
(B—1 Ak)i Zk — 0 (i = |
1, |
2, |
. . . |
, |
p, |
i |
s), |
zk (B—1 Aft)s = 0. |
||||
По |
(B_1Aa)s> 0 по определению |
s 6 / fe, |
поэтому |
zk = 0, а тогда все |
||||||||||
z£ = 0 |
(t = |
1, |
. . . , p, i=^=s), |
t . |
e. |
z = |
0. |
Следовательно, |
|C|=^0, |
|||||
>Cua0,fe = й. |
В |
силу теоремы |
7 |
точка |
ыа„,ь |
является угловой |
для 17. |
144 |
МИНИМИЗАЦИЯ ФУНКЦИИ МНОГИХ ПЕРЕМЕННЫХ |
[Гл. I |
||||||||
При этом |
(с, Ua0ife) = |
(с, |
и) — а 0ДА< |
(с, и) = (с, |
и), т. |
е. значение |
||||
функции (с, и) строго уменьшилось. |
Тем самым |
описан |
один итера* |
|||||||
ционный шаг симплекс-метода. |
|
|
|
|
|
|||||
По условию задача |
(10) невырожденная, поэтому число поло |
|||||||||
жительных компонент у вектора иаа,к равно |
р. Поскольку т — р ну |
|||||||||
левых координат у вектора |
ua„ife |
известны: |
= иРс£1= . . . = и*~1= |
|||||||
= Ua^"1 = |
•••= |
Ua„ = |
о, |
ТО |
Все |
ОСТЭЛЬНЫе |
координаты |
иа‘ 0= (и — |
||
— aQB~l Ak){ (i = |
1, . . . |
, р, |
i=/=s), |
Uas = a0 |
будут |
положительными. |
Это, кстати, означает, что в невырожденных задачах номер s, на ко тором достигается минимум в (16), определяется однозначно.
В вырожденной задаче такой номер s, вообще говоря, опреде ляется неединственным образом, и, более того, величина ао и& (16) в этом случае может оказаться равной нулю, поскольку мо
жет быть равной нулю координата (B~lb )s= u s. Таким |
образом, в |
|
вырожденных задачах возможно зацикливание, |
когда |
значение |
функции (с, и) при переходе от одной угловой |
точки |
к другой |
не убывает и через некоторое число итераций происходит возвра щение к прежней угловой точке (см. упражнение 7). Для преодо ления явления зацикливания симплекс-метод следует несколько' модифицировать; за подробностями отсылаем читателя к работам, [114, 116, 133, 134, 257] и др.
При использовании симплекс-метода производится перебор только тех угловых точек, в которых значение функции (с, и) не возрастает, поэтому симплекс-метод дает значительный выигрыш по сравнению с простым перебором и позволяет решать задачи линейного программирования довольно больших размеров. Разу меется, при больших размерах задачи и при неудачном выбореначальной угловой точки объем работы может оказаться значи тельным и при использовании симплекс-метода или его модифика ций.
5. Приведем формулы, связывающие последовательные итер ции симплекс-метода в случае невырожденной угловой точки Обозначим
Л = b, |
uik = |
(В - 1 Ak)h |
i = |
1, 2, |
, |
р, k = 0, |
1, . . . |
, |
т\. |
||
|
_ |
|
Р |
|
|
|
|
|
|
|
|
“о/ = Л/ = (с , В ~1А,) — с,- = |
£ |
Cjiii, |
Cj, |
/ = |
1, |
2, |
. . . , |
т\ |
|||
|
|
|
£ = 1 |
|
|
|
|
|
|
|
|
|
|
«00 = |
(С. «)• |
|
|
|
|
|
|
|
|
Параметры |
щ, |
назовем параметрами |
итерации |
для |
угловой |
точ |
ки и; через Оц обозначим параметры итерации для новой угловой точки v = Uo^.k, получаемой описанным выше симплекс-мето дом.