Файл: Цирлин, А. М. Основы оптимального управления конспект лекций.pdf
ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 23.10.2024
Просмотров: 100
Скачиваний: 0
т
§ 12. Условия оптимальности для дискретных задач оо связями разного типа. Задача на максимум минимумов
Изученная нами задача далеко не исчерпывает возможные ва рианты дискретных задач оптимизации. Жизнь выдвигает разно
образные |
условия |
и целевые функции, такие их сочетания, ко |
||||||||
торые |
невозможно |
предусмотреть заранее. Например, |
в рассмот |
|||||||
ренной выше задаче начальное состояние Уе |
очиталось |
задан |
||||||||
ным, а конечное У^свободныы. Спрашивается, |
как |
изменятся |
||||||||
условия оптимальности, если одно из этих предположений не |
||||||||||
выполнено? |
|
|
|
|
|
|
|
|
||
Связи между переменными также могут иметь различный, не |
||||||||||
обязательно марковский характер. Наконец? целеван функция |
||||||||||
далеко |
не |
всегда |
имеет |
форму |
( I I . 1 ) . Ниже мы изложин |
подход, |
||||
позволяющий для различных сочетаний и форм связей, |
ограни |
|||||||||
чений |
и различных |
функций цели записать функционал |
Лагранжа |
|||||||
и услсвия |
оптимальности. |
|
|
|
|
|
||||
1 2 . I . |
Аддитивность |
функционала |
Лагранжа. |
Каноническая |
||||||
|
|
|
форма |
связи |
|
|
|
|
|
|
Первым этапом |
при |
составлении |
как.условий |
оптимальности, |
||||||
так и |
основанных |
на |
них численных |
алгоритмов |
является |
состав |
||||
ление |
функционала |
Лагранжа |
8 . |
|
|
|
|
|||
Для |
решения дискретных задач |
со связями разного типа нужно |
|
научиться |
составлять функционал $ при произвольном наборе |
||
сгязей. |
|
|
|
Также |
как в общей задаче нелинейного программирования, |
||
каждой |
связи соответствует одно слагаемое в функционале/^. |
||
Однако |
в зависимости от структуры связи вид этого слагаемого |
||
окакется |
различным. Чтобы найти |
слагаемые, соответствующие |
|
щ
разный формам оьязай, мы наметим |
такую последовательность дей |
|||||||||||
ствий: |
|
|
|
|
|
|
|
|
|
|
|
|
1. Выбераи вспомогательную каноническую форму связи между |
||||||||||||
дискретными переменными. |
|
|
|
|
|
|
|
|
||||
2. Найдем вид функционала Лагранжа и условий оптимальнооти для |
||||||||||||
такой |
связи. |
|
|
|
|
|
|
|
|
|
|
|
3. Разнообразные формы связи приведем |
к |
кановичеокому |
виду. |
|||||||||
Тогда |
условия |
|
оптимальности, полученные в п . 2, окажутся |
примени |
||||||||
мы для |
любого |
|
сочетания |
"приводимых" |
форм |
связей. |
|
|
||||
В качестве |
канонической |
формы |
связи выберем выражение |
|
||||||||
|
|
|
|
п. |
|
V • Ь |
J |
i 1 - |
|
п |
|
|
|
|
|
|
I |
/ |
|
|
( I 2 . I ) |
||||
|
|
|
' = ° |
|
|
|
|
^ |
0 , 1 , 2 , . . „ П . |
|||
|
|
|
|
|
|
|
|
|||||
Эта |
свя'зь |
завионт |
от |
параметра |
j |
и |
справедлива |
для |
любого |
|||
его значения |
от нуля |
до |
ft |
. Так что,по |
сути дела, |
она |
эквива |
|||||
лентна |
|
|
связи. |
|
|
|
|
|
|
|
|
|
Пусть целевая функция |
имеет вид |
|
|
|
|
|
||||||
|
|
1 |
=i2-' а |
(*1№> |
О |
|
|
|
|
(12.2) |
||
Составим Функционал Лагранжа для задачи (12.2), (12.1), считая
пока, |
что |
ограничения |
на переменные |
отсутствуют. Заметим, |
что в |
||
ату задачу |
<У{ и. |
U L |
входят |
совершенно симметрично. Однако,имея |
|||
в виду |
дальнейшее |
изложение, |
удобно |
разбить переменные на |
две |
||
группы. |
|
— |
|
|
|
|
|
Итан^ функционал Лагранжа |
|
|
|
||||
j - °
|
|
|
|
|
|
|
|
i09 |
|
|
|
|
|
|
|
|
|
|
|
Необходимые уоповия оптимальности (ou. п.5.2) |
утверждают: |
||||||||||||||||
если для |
всех |
J |
|
выполнены уоловия общности полокенип. т . е . |
||||||||||||||
ни |
при одной |
J |
|
решение |
^УЫ, |
U*\ |
не являотоп |
зкстреивлыо |
||||||||||
<Р* ( J |
) |
и функции |
J |
и |
J-e |
удовлетворяют |
уоловияи |
дисМд- |
||||||||||
ренцируеиооти, то найдется такая последовательность |
\<^j^ |
% |
||||||||||||||||
что |
щункциоиад |
«3^ |
на \ У* . U* { |
достигает |
локального |
иакоицуиа |
||||||||||||
на |
множестве |
|
|
сравнения |
Ь |
. |
|
|
|
|
|
|
|
|
||||
|
Если |
свяаей |
(12.1) несколько, |
£f, |
(j |
) |
= 0, |
|
$i.Q) |
* О , . . . |
||||||||
|
o / m ( j |
) |
= 0, |
то |
в ч/ункщюнале |
(12.3) |
появится |
не |
одно, а гп |
|||||||||
олагаемых |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||
|
|
|
|
|
|
|
т . |
|
|
|
|
|
|
|
|
|
|
|
|
Но нам удобнее |
поставить в |
соответствие |
|
оьпзи |
(12.1) |
слагаемое |
|||||||||||
не |
в 1рунк:ЛОнале |
j3 , а л выражении, стоящим под знаком суммы |
||||||||||||||||
этого |
1Ду>.кционала. |
Перепишем (12.3) в |
форио |
|
|
|
|
|
|
|||||||||
или, меняя порядок суммирования во втором слагаемом, как
|
1-0 |
|
|
i'o |
|
Выражении, стоящее |
в квадратных скобках, полностью опреде |
||||
ляет |
^ |
« Обозначим |
его через /2 |
, а слагаемое, соответствую |
|
щее |
ci-яви г через Qtg |
|
. Тип ГП |
связей |
|
/У)
& = ^ |
* < ^ , ^ с ^ , |
|
/12.6/ |
х / < Если L открыто,условие максимума |
на нем приводит |
в условию |
|
стационарности. |
|
|
|
|
HO |
|
где |
n , / |
, / 1 |
Р |
^'ZJjMXiWJ) |
(12.?) |
Условия оптимальности при отсутствии ограничений имеют обычный
вид |
|
|
vS |
|
|
|
|
|
|
|
|
|
|
|
|
= 0 . |
|
|
|
|
|
^ |
|
Но так как в функционале |
(12.5) |
от |
У,- и |
зависит |
лишь |
||||||
I - е слагаемое, то последнее условие перепишется в форме систе |
|||||||||||
мы ураввений. |
|
|
|
|
|
|
|
|
|
|
|
|
_ |
р . |
^3 |
= |
О |
|
|
|
(12,8) |
||
|
|
|
|
|
|
|
|
1= |
0,1,2 |
|
|
Наряду |
со связью |
(12.1) |
в аналогичной |
форме запишем и |
|
||||||
ограничение |
|
|
|
|
|
|
|
|
|
|
|
М |
) ~ |
|
|
|
|
|
0 |
|
|
|
|
|
|
|
|
|
|
|
J= |
0 , 1 , . . . , Л |
|
|
|
Введя дополнительную переменную 2,- |
^ 0 |
, |
условие (12.8) |
можно |
|||||||
записать в форме |
связи |
(12.1): ^п' P ^ U - |
i \)+2j~QИЛИ |
|
|
||||||
ОД-'if^u^.i) |
|
|
|
+ |
|
^,'J)] |
= 0 |
. |
(12.Ю |
||
|
{«•о |
|
|
|
|
|
|
|
|
|
|
Здесь