Файл: Васильев Ф.П. Лекции по методам решения экстремальных задач.pdf
ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 11.04.2024
Просмотров: 241
Скачиваний: 1
S щ |
Элементы линейного |
программирования |
145- |
Заметим, |
что параметры иц, i = l , 2 , . . . ,р, /= 0 , 1 , . . . , т, |
одно |
|
значно определяются из соотношений |
|
|
|
|
Л/ = 5 ( Л - М /) = |
£ Л <и(/. |
|
|
|
i=-i |
|
Аналогично параметры vtj могут быть определены соотношениями
Л/ = £ ' ^ ‘7 + Akvhh / = 0, 1, . . . , т,
РР
ГДе £ ' = |
Е ’ |
3 Л . • • • . Д - 1 , |
Д + 1 .............. |
Л - А к — СТОЛбДЫ |
£=1 |
i= 1 |
|
|
|
матрицы С. С учетом этого замечания нетрудно получить простые связи между параметрами utj и vtj
vU = uci — Uih |
i — 0, |
1, . . . , р, |
i =?^ s; |
usi |
||
“si ’ |
||||||
|
usk |
|
|
|
||
|
|
7 = 0 , 1 , . . . , |
|
(17) |
||
В самом деле, по |
условию usft = |
(В- 1 Aa)s > |
0 (см. |
п. 4). Из равен |
||
ства |
|
|
|
|
|
|
|
А* = В ( В - М а) = £ д ^ , |
|
||||
|
|
|
1=1 |
|
|
|
тогда имеем |
|
|
|
|
|
|
|
Д = |
— Д - У ' А , - ^ - . |
(18) |
|||
|
|
usk |
i=l |
|
|
|
|
|
|
|
|
||
Так как 1 < s < р |
и |
|
|
|
|
|
|
Л = £ |
Дыгз = |
В ( В - ‘ Д )= В е “ , |
|
||
|
£=1 |
|
|
|
||
где е, — s-тый столбец единичной матрицы порядка |
р х р, то uls= О |
|
при |
и ы „ = 1. Поэтому равенство (18) можно |
переписать в виде: |
146 |
|
МИНИМИЗАЦИЯ ФУНКЦИИ МНОГИХ ПЕРЕМЕННЫХ |
|
[Гл. 2 |
||||||||
Далее, при / = О, |
1, . . . |
, |
т, 'j= £s |
с учетом |
(18) получим |
|
||||||
|
|
|
|
|
|
Р |
|
и |
|
|
|
|
|
А, = В ( S - 1 Aft |
= ^ |
V |
( 7 = ^ Ч '« £ / + A«s/ = |
|
|||||||
|
|
|
|
|
|
t=l |
|
t=l |
|
|
|
|
|
|
= У Ч - ( «I/— |
|
|
— |
4k. |
|
|
||||
|
|
|
1=11 |
V |
|
|
"sfe / |
«sfc |
|
|
||
Сравнивая |
полученные |
представления |
Ajt j = 0, 1, . . . |
, in |
с соотно |
|||||||
шениями |
|
|
|
|
|
p |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||
|
|
|
|
|
Aj — ]£] A(vij + Akvki< |
|
|
|||||
|
|
|
|
|
|
£=l |
|
|
|
|
|
|
определяющими vif, получим формулы ' (17) |
при всех i Ф 0. |
Остается |
||||||||||
рассмотреть |
случай |
i — 0. |
Так |
как |
|
|
|
|
|
|||
|
|
|
р |
'с flu + ckvkj — сh |
/ = 1 , 2 .......... in, |
|
||||||
|
|
% = |
£ |
|
||||||||
|
|
i =1 |
|
|
|
|
|
|
|
|
||
по определению, то с учетом уже доказанных формул (17) |
при i Ф 0 |
|||||||||||
имеем |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
^ ) |
+ ск usj |
|
р |
|
|
|
|
|
|
|
|
|
— Cj = (' |
|
|
||||
|
i=i |
|
|
|
Usk J |
|
- usk |
|
Vi£=1 |
|
|
|
usi |
|
|
|
|
) = “о/ — “oft |
usj |
/ = |
|
|
|||
Usk |
£=1 |
|
|
|
Usk У |
|
|
|||||
|
|
|
|
|
|
|
v) = |
(c, uaa,k) = (с, |
и) — а 0ДА, до |
|||
Наконец, |
из (16) |
и равенства |
(с, |
|||||||||
казанного |
в |
п. 4, |
следует, что |
|
|
|
|
|
|
|||
« 00 — « 00 |
a 0« 0ft — « 0 0 ■ |
«so
“sft «oft-
-Формулы (17) полностью доказаны.
Полученные формулы (17), связывающие параметры угловых точек на одном шаге симплекс-метода, весьма просты и могут быть использованы для численного решения на ЭВМ невырожден ных задач линейного программирования симплекс-методом.
6. Как выбрать начальную угловую точку? Оказывает ■отыскание угловой точки множества U—{u :u ^ .O , Au==b} в свою очередь весьма трудоемкая задача, сравнимая с исходной зада чей (10). Мы здесь опишем один из наиболее распространенных лриемов отыскания угловых точек, использующий тот же сим плекс-метод.
§ Щ |
|
|
|
Элементы линейного |
|
программирования |
|
|
|
14Т |
|||||||||
|
Рассмотрим |
такую |
вспомогательную |
задачу |
линейного |
|
про |
||||||||||||
граммирования: найти |
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||
т ш |
y/) ’ 117 = |
|® = |
^ ^ € £ т +р, |
|
« > 0 , |
п > |
0, |
Au + v = b ^ . |
|||||||||||
jrn ( E |
|
||||||||||||||||||
w |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Ь ^ .О, |
|
|
(19) |
||
Без ограничения общности можем считать, что |
ибо |
в |
про |
||||||||||||||||
тивном случае соответствующую строчку ограничений |
(Au)i = bi |
||||||||||||||||||
мы бы умножили на |
(— 1). Для задачи (19) |
можно сразу указать |
|||||||||||||||||
угловую |
точку. |
Это |
будет точка |
( |
|
) (см. теорему 7) |
и, следова- |
||||||||||||
тельно, для решения задачи |
(19) |
\°/ |
|
|
|
|
симплекс-ме |
||||||||||||
можно применять |
|||||||||||||||||||
тод |
(или его модификации в случае вырожденной задачи) и найти |
||||||||||||||||||
ее решение. |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||
|
Т е о р е м а |
8. |
Пусть |
|
— решение задачи |
(19), |
пусть |
|
|
||||||||||
|
|
|
|
|
|
2 |
|
- “ |
(5 |
: 4 |
|
|
|
|
|
|
|
||
|
|
|
|
|
|
t=i |
|
|
|
|
i=i |
|
|
|
|
|
|
|
|
Тогда если ф* = |
0, |
то и* — угловая точка множества U\ если |
ф*]> 0„ |
||||||||||||||||
о U = 0 |
и задача |
(10) |
становится тривиальной. |
|
|
|
|
|
|
||||||||||
|
Д о к а з а т е л ь с т в о . |
Прежде |
всего ясно, |
что задача |
(19) |
|
имеет |
||||||||||||
|
|
|
|
W Ф 0 |
|
|
|
|
|
|
р |
г/ > 0 |
|
на W. Да- |
|||||
решение, |
так как |
и линейная функция |
^ |
|
|||||||||||||||
лее, |
поскольку |
|
эта |
задача |
решается |
|
i=l |
|
|
|
|
|
то |
||||||
|
симплекс-методом, |
||||||||||||||||||
Ц 9 |
\ |
|
точка множества |
W. В частности, |
если ф* = |
0, то |
|||||||||||||
ф 1— угловая |
|||||||||||||||||||
и' = 0 и ( о ) — Угловая |
точка |
|
Очевидно, тогда |
и* — угловая |
|||||||||||||||
точка U. Если же |
ф *> 0 , то [U — пустое множество. В |
самом |
|
деле, |
|||||||||||||||
если бы |
существовала точка и 6 U, то |
^ q j 6 W. Но тогда | |
^ |
||||||||||||||||
решение задачи |
(19) |
и ф* = 0 — противоречие. |
|
|
|
|
|
|
|
||||||||||
|
Упражнения. 1. Выяснить геометрический смысл задач линей |
||||||||||||||||||
ного программирования, |
взяв в задачах (10) и |
(12) т = 2, |
т = 3. |
||||||||||||||||
|
2. |
На |
велосипедном |
заводе |
|
выпускают |
гоночные и дорожн |
||||||||||||
велосипеды. Производство устроено так, что вместо двух дорож ных велосипедов завод может выпустить один гоночный, причем гоночный велосипед приносит в 1,5 раза больше прибыли. Завод, может произвести 700 дорожных велосипедов в день, однако склад, может принять не более 500 велосипедов в день. Сколько нужно'
148 МИНИМИЗАЦИЯ ФУНКЦИЙ МНОГИХ ПЕРЕМЕННЫХ [Гл. 2
выпускать в день гоночных и сколько дорожных велосипедов для того, чтобы завод получал максимальную прибыль? («Квант», 1971, № 3). Для решения этой задачи применить симплекс-метод.
3. В |
пунктах |
А и В расположены |
кирпичные |
заводы, а в |
|||
пунктах |
С и Д — карьеры, снабжающие |
их |
песком. Ежесуточно |
||||
заводу А нужно 40 т песка, заводу В — 50 т, |
а карьер С ежесуточ |
||||||
но добывает |
70 |
т песка, карьер Д — 30 |
т. |
Стоимость перевозки |
|||
тонны песка |
с карьера |
С на завод А равна 2 руб., на завод. В — |
|||||
6 руб., с |
карьера |
Д на |
завод А — 5 руб., |
на завод |
В — 5 руб. |
||
Нужно организовать ежесуточное снабжение заводов песком так, чтобы полная стоимость перевозок была наименьшей («Квант», 1971, № 3). Для решения этой задачи применить симплекс-метод.
4. По аналогии с теоремой 4 для задачи (12) сформулиро вать условия разрешимости и оптимальности, пользуясь теорема
ми |
1— 3. |
|
|
|
|
|
|
|
|
5. |
Для |
того |
чтобы задача |
(1) |
(и, следовательно, двойствен |
||
ная |
задача |
(7)) |
имела решение, необходимо и достаточно, чтобы |
|||||
1 ! ф 0 |
и (с, и) ограничена снизу на |
U. Доказать. |
|
|||||
|
6. |
Для |
того |
чтобы задача |
(1) |
(и, следовательно, задача (7)) |
||
имела |
решение, |
необходимо и |
достаточно, чтобы |
11ф ф , А ф ф . |
||||
Доказать. |
|
|
(с, |
и) = |
и3— u4+ u 5— ы6 |
|
||
|
7. |
Решить задачу min |
при условиях |
|||||
и1ф и 3— 2u4— 3w5+ 4 u 6 = 0, |
и2+ 4 и 3— За4— 2u5+ u 6 = 0, |
и3+ и4 + и5+ |
||||||
+ и6 + и7 = 1, |
|
0, /=1, 2 . . . , 7 . |
Показать, что в этой задаче мож |
|||||
но получить зацикливание, если с помощью симплекс-метода ор
ганизовать перебор угловых точек, |
соответствующий |
перебору |
|||
базисных столбцов в следующем порядке: |
|
|
|||
(А3, Л2, Л7) —>(Л3, |
Л4, Л7) |
(Л5, |
At , |
Л7) —»-(ЛБ, А0, |
Л7) —>• |
Ав, |
Л7) —^(Лх, |
Аг, |
Л7) |
(Л3, Л2, Л7). |
|
Любопытно отметить, что длина циклов в задачах линейного про граммирования меньше шести не бывает ([257], стр. 389).
§ 12. О МЕТОДЕ СЛУЧАЙНОГО ПОИСКА И НЕКОТОРЫХ ДРУГИХ МЕТОДАХ
Наряду с описанными выше методами минимизации функ ций m переменных существует большая группа методов поиска минимума, объединенных под названием метода случайного поис ка [79], [204]. Метод случайного поиска в отличие от ^анее рас смотренных методов характеризуется намеренным введением эле мента случайности в алгоритм поиска. Многие варианты метода случайного поиска сводятся к построению последовательности {и п} по правилу
s Щ |
О методе случайного поиска и некоторых других методах |
149 |
|
|
U-n-\-\— U>n“Ь |
^ — 0> 1 >■■•> |
(1) |
где а п — |
некоторая положительная величина, £ = (g1, . . . ,£m) |
— |
|
жакая-либо реализация m-мерной случайной величины | с извест ным законом распределения. Например, компоненты случайного вектора | могут представлять независимые случайные величины, распределенные равномерно на отрезке [— 1,1]. Как видим, орга низация случайного поиска минимума функции пг переменных свя зана с наличием датчика (или генератора) случайных чисел, об ращаясь к которому в любой момент можно получить какую-либо реализацию /n-мерного случайного вектора | с заданным законом распределения. Такие датчики могут быть получены на основе
•стандартных программ, обычно имеющимися в библиотеках под
программ на ЭВМ. |
|
|
|
|
|
|
|
|
|
|
|
|
|||
1. |
|
Приведем |
несколько вариантов |
метода |
случайного пои |
||||||||||
минимума |
функции J (и) на |
множестве и<=Ет, предполагая, что |
|||||||||||||
и-е приближение un^ U (п ^ .0) уже известно. |
|
|
|
|
|
|
|||||||||
а) Алгоритм с возвратом |
при неудачном |
шаге |
[204]. |
Смысл |
|||||||||||
этого алгоритма заключается |
в следующем. С помощью датчика |
||||||||||||||
•случайного вектора получают некоторую |
его |
реализацию |
| |
и в |
|||||||||||
пространстве Ет определяют точку ип= ип+ а|, |
a = c o n st> 0 . |
Если- |
|||||||||||||
vn<=U и /(vn) < / (ип) , |
то сделанный |
шаг считается |
удачным, |
и в |
|||||||||||
этом случае полагается |
un+i = vn. Если |
vn^.U, |
но |
J (v n) ^ J ( u n), |
|||||||||||
или же |
vn0. U, то сделанный шаг считается |
неудачным |
и пола |
||||||||||||
гается |
un+i = |
un. Если окажется, что |
un= |
un+l = |
... = un+N |
для |
|||||||||
достаточно больших N, то точка ип может быть принята в каче |
|||||||||||||||
стве приближения искомой точки минимума. |
|
|
|
|
|
|
|
||||||||
б) |
Алгоритм наилучшей |
пробы |
[204]. |
Берутся |
какие-либо s |
||||||||||
-реализаций |
..., |<s>случайного вектора | и вычисляются значения |
||||||||||||||
функции J (и) |
в тех точках u = u n+ a%(i), i —1, 2, . . . , s, которые при |
||||||||||||||
надлежат |
множеству U. Затем полагается ип+\= ип+ а ^ 1°),гд,е |
ин |
|||||||||||||
декс г'о определяется условием |
|
|
|
|
|
|
|
|
|
|
|||||
|
|
|
J (ип + |
а^°>) = |
min |
J (ип + |
|
|
|
|
|
|
|||
|
|
|
|
|
|
un+a&)£U |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
l< i< s |
|
|
|
|
|
|
|
|
|
Величины s > l |
и a = con st> 0 |
являются параметрами алгоритма. |
|||||||||||||
в) |
|
Алгоритм статистического градиента [204]. Берутся как |
|||||||||||||
либо s реализаций £0), ... , |
|(s) |
случайного вектора | и вычисляются |
|||||||||||||
разности |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
A/ft° = |
J ( Un + Y£<0) - J ( u |
n) |
|
|
|
|
|
|
||||
.для всех |
un+ y ^ ^ U . |
Затем |
полагают |
рп — — У ]£ (г) AJn\ |
где |
||||||||||
сумма берется по всем тем i, l ^ i ^ s , для которых un+yQ l)^ U .
