Оглавление
Исходные данные5
Задание №1. Графоаналитическое решение ОЗЛП6
Задание № 2. Задача о коммивояжере. Метод ветвей и границ9
Задание №3. Оптимизация дискретных управлений дискретными динамическими объектами методом динамического программирования Р. Беллмана15
Задание №4. Синтез непрерывного оптимального управления с помощью уравнения Эйлера18
Задание №5. Синтез непрерывных оптимальных уравнений с помощью уравнения Эйлера-Пуассона22
Исходные данные
К заданию №1. №C1C2B1B2A11A12A21A2222251442-226К заданию №2.
123456С =1∞2453121∞1276365∞1434176∞5156523∞4613561∞К заданию №3.
№ABαβγ12210,2521,58К заданию №4.
№ABα21220,513/4К заданию №5.
№kγ1224422
Задание №1. Графоаналитическое решение ОЗЛП
1. Математическая постановка ОЗЛП:
φ=5x1+x2→max, (0)
2x1-2x2≤4, (1)
2x1+6x2≤4, (2)
x1≥0, (3)
x2≥0, (4)
BD: 2x1-2x2=4, (1')
CD: 2x1+6x2=4, (2')
AC: x1=0, (3')
AB: x2=0, (4')
2. Записываем уравнение граничных линий допустимого многоугольника (1') - (4').
На плоскости (x1, x2) строим граничные линии.
3. Строим линию, пересекающую область φ.
φ=5*2+1*0=10 (X1=2, X2=0), (5)
X1+X2=2, (6)
4. Находим градиент целевой функции:
∂φ/∂X=(∂φ/(∂X_1 ))/(∂φ/(∂X_2 ))=(5/1)=(C_1/C_2 ), (7)
φ=C_1 X_1+C_2 X_2, (8)
Пересечением полуплоскостей будет являться область, координаты точек которого удовлетворяют условию неравенствам системы ограничений задачи.
Обозначим границы области многоугольника решений.
Рассмотрим целевую функцию задачи φ=5x1+x2→max. Построим прямую, отвечающую значению функции φ=0: F=5x1+x2=0. Будем двигать эту прямую параллельным образом до последнего касания обозначенной области. На графике эта прямая обозначена пунктирной линией.
Из рисунка видно, что оптимальная точка D* равная D^*={■(D_1^*@D_2^* )}, находится на пересечении линий BD и CD и ее координаты определяются путем решения одноименных уравнений (1') и (2').
D_1^*=2, D_2^*=0, (9)
φ^*=5*2+1*0 = 10, (10)
Ответ: D_2^*=0; φ^*=10. Задание № 2. Задача о коммивояжере. Метод ветвей и границ
Расстояния между пунктами заданы матрицей:
123456С =1∞2453121∞1276365∞1434176∞5156523∞4613561∞Решение задачи о коммивояжере методом ветвей и границ начинается с приведения матрицы (вычитания из каждой строки (столбца) матрицы C минимального элемента этой строки (столбца).
Произведем приведение матрицы C по строкам: hν= min(i) hνi
123456hνС' =1∞41321122∞41561371∞46514467∞13153216∞12605324∞1Произведем приведение матрицы C по столбцам: gi = min(υ) gνi
123456С' =1∞3021022∞3045370∞3654466∞0253105∞0604213∞gi010000
В итоге получаем полностью приведенную (редуцированную) матрицу:
123456hνС0 =1∞30210122∞30451370∞36514466∞02153105∞02604213∞1gi010000Величины hν и gi называются константами приведения.
Нижняя граница цикла: d0=8 (d_0=∑_(ν=1)^n▒〖h_ν+∑_(i=1)^n▒g_i 〗).
Шаг №1. Определяем ребро ветвления и разобьем все множество допустимых значений Q0 относительно этого ребра на два непересекающихся подмножества (P,q) и ((P,q) ̅), т.е. Q^0=Q_1^0∪Q_2^0, где Q_1^0=(P,q), Q_2^0=((P,q) ̅ ). В приведенной матрице исследуем все нулевые переходы.
123456ανC0 =1∞0(1)3420(0)020(0)∞0(0)1650353∞0(3)32240(0)55∞40(0)05420(1)1∞2160(0)1450(2)∞0βi010120Наибольшая сумма констант приведения равна υ34= α3 + β4 =2+1=3, следовательно, множество разбивается на два подмножества Q_1^0=(3,4) и Q_2^0=((3,4) ̅ ).
Оценка длины цикла: η(Q_2^0 )=d_0+υ_34=8+3=11.
В результате получим другую сокращенную матрицу (5x5), которая подлежит операции приведения.
После операции приведения сокращенная матрица будет иметь вид:
12356hν1∞0320020∞0650C1=405∞4005420∞2060140∞0gi00000d1=0
Шаг №2.
Определяем ребро ветвления и разобьем все множество допустимых значений Q1 относительно этого ребра на два непересекающихся подмножества Q^1=Q_1^1∪Q_2^1.
В приведенной матрице исследуем все нулевые переходы.
12356αν1∞0(1)320(0)020(0)∞0(0)650C1=40(0)5∞40(0)05420(2)∞2260(0)140(2)∞0βi01020Наибольшая сумма констант приведения равна υ53=2+0=2, следовательно, множество разбивается на два подмножества Q_1^1=(5,3) и Q_2^1=((5,3) ̅ ).
Оценка длины цикла: η(Q_2^1 )=d_0+υ_53=8+2=10.
Оценка на перспективном множестве: η(Q_1^1 )=d_0+d_1=8+0=8
В результате получим другую сокращенную матрицу (4x4), которая подлежит операции приведения.
После операции приведения сокращенная матрица будет иметь вид:
1256hνC2 =1∞020020∞6504054006010∞0gi0000d2=0
Шаг №3.
Определяем ребро ветвления и разобьем все множество допустимых значений Q2 относительно этого ребра на два непересекающихся подмножества Q^2=Q_1^2∪Q_2^2.
В приведенной матрице исследуем все нулевые переходы.
1256ανC2 =1∞0(1)20(0)020(5)∞65540(0)5∞0(0)060(0)10(2)∞0βi0120Наибольшая сумма констант приведения равна υ21=5+0=5, следовательно, множество разбивается на два подмножества Q_1^2=(2,1) и Q_2^2=((2,1) ̅ ).
Оценка длины цикла: η(Q_2^2 )=d_0+υ_21=8+5=13.
Оценка на перспективном множестве: η(Q_1^2 )=d_0+d_2=8
В результате получим другую сокращенную матрицу (3x3), которая подлежит операции приведения.
После операции приведения сокращенная матрица будет иметь вид:
256hν1∞200C3 =45∞00610∞0gi100d3=1
Шаг №4.
Определяем ребро ветвления и разобьем все множество допустимых значений Q3 относительно этого ребра на два непересекающихся подмножества Q^3=Q_1^3∪Q_2^3.
В приведенной матрице исследуем все нулевые переходы.
256αν1∞20(2)2C3 =44∞0(4)460(4)0(2)∞0βi420Наибольшая сумма констант приведения равна υ46=4+0=4, следовательно, множество разбивается на два подмножества Q_1^3=(4,6) и Q_2^3=((4,6) ̅ ).
Оценка длины цикла: η(Q_2^3 )=d_0+υ_46=8+4=12.
Оценка на перспективном множестве: η(Q_1^3 )=d_0+d_3=8+1=9
В результате получим другую сокращенную матрицу (2x2), которая подлежит операции приведения.
После операции приведения сокращенная матрица будет иметь вид:
25hνC4 =1∞226000gi00d4=2
В соответствии с этой матрицей включаем в маршрут Q_1^4=(1,5) и Q_1^5=(6,2).
Ответ: l* =C34+C46+C62+C21+C15+C53=1+1+3+1+3+2=11.
Дерево решения имеет следующий вид:
Задание №3. Оптимизация дискретных управлений дискретными динамическими объектами методом динамического программирования Р. Беллмана
Дано:
X_(k+1)=X_k+0,25〖 U〗_(k, ) (1)k=0,1,2,3
X_0=X(0), (2)
X_((U))=X_(4 )-н.з., (3)n=4
U - н.у. (неограниченное управление), (4)
I=∑_(k=0)^3▒[[(X_k^2)/2+1,5 (〖 U〗_k^2)/2]+8 (X_4^2)/2] →min, (5)
Найти: 〖 U〗_(k^* )=〖 U〗_(k^* ) (X_k ), (6).
Решение
1. S_3=min{0,5X_3^2+0,75〖 U〗_3^2+(X_3+0,25〖 U〗_(3 ) )^2 }=0,25X_3+0,5625〖 U〗_3+X_3+0,5X_3 〖 U〗_3+0,0625〖 U〗_3=1,25X_3+0,625〖 U〗_3+0,5X_3 〖 U〗_3.
Минимизируем φ_3 по 〖 U〗_3:
(∂φ_3)/(∂〖 U〗_3 )=0(∂^2 φ_3)/(∂〖 U〗_3^2 )>0
(∂φ_3)/(∂〖 U〗_3 )=0,5X_3+0,5〖 U〗_3=0,⟹〖 U〗_3^*=-X_3, (∂^2 φ_3)/(∂〖 U〗_3^2 )=0,5>0 Вычислим S3 от x3:
X_4=X_3+0,25(-X_3 )=0,75X_3 S_3 (X_3 )=〖0,25X〗_3^2+0,25〖(-X_3)〗^2+〖(0,75X_3)〗^2=X_3^2 2. S_2=min{0,5X_2^2+0,75〖 U〗_2^2+(X_2+0,25〖 U〗_(2 ) )^2 }=0,25X_2+0,5625〖 U〗_2+X_2+0,5X_2 〖 U〗_2+0,0625〖 U〗_2=1,25X_2+0,625〖 U〗_2+0,5X_2 〖 U〗_2.
Минимизируем φ_2 по〖 U〗_2:
(∂φ_2)/(∂〖 U〗_2 )=0(∂^2 φ_2)/(∂〖 U〗_2^2 )>0
(∂φ_2)/(∂〖 U〗_2 )=0,5X_2+0,5〖 U〗_2=0,⟹〖 U〗_2^*=-X_2, (∂^2 φ_2)/(∂〖 U〗_2^2 )=0,5>0 Вычислим S2 от U2:
X_3=X_2+0,25(-X_2 )=0,75X_2 S_2 (X_2 )=0,25X_2^2+0,25〖(-X_2)〗^2+〖(0,75X_2)〗^2=X_2^2 3. S_1=min{0,5X_1^2+0,75〖 U〗_1^2+(X_1+0,25〖 U〗_(1 ) )^2 }=0,25X_1+0,5625〖 U〗_1+X_1+0,5X_1 〖 U〗_1+0,0625〖 U〗_1=1,25X_1+0,625〖 U〗_1+0,5X_1 〖 U〗_1.
Минимизируем φ_1 по〖 U〗_1:
(∂φ_1)/(∂〖 U〗_1 )=0(∂^2 φ_1)/(∂〖 U〗_1^2 )>0
(∂φ_1)/(∂〖 U〗_1 )=0,5X_1+0,5〖 U〗_1=0,⟹〖 U〗_1^*=-X_1, (∂^2 φ_1)/(∂〖 U〗_1^2 )=0,5>0 Вычислим S1 от U2:
X_3=X_2+0,25(-X_2 )=0,75X_2 S_1 (X_1 )=0,25X_1^2+0,25〖(-X_1)〗^2+〖(0,75X_1)〗^2=X_1^2 4. S_0=min{0,5X_0^2+0,75〖 U〗_0^2+(X_0+0,25〖 U〗_(0 ) )^2 }=0,25X_0+0,5625〖 U〗_0+X_0+0,5X_0 〖 U〗_0+0,0625〖 U〗_0=1,25X_0+0,625〖 U〗_0+0,5X_0 〖 U〗_0.
Минимизируем φ_0 по〖 U〗_0:
(∂φ_0)/(∂〖 U〗_0 )=0(∂^2 φ_0)/(∂〖 U〗_0^2 )>0
(∂φ_0)/(∂〖 U〗_0 )=0,5X_0+05〖 U〗_0=0,⟹〖 U〗_0^*=-X_0, (∂^2 φ_0)/(∂〖 U〗_0^2 )=0,5>0 Вычислим S0 от U0:
X_1=X_0+0,25(-X_0 )=0,75X_0 S_0 (X_0 )=0,25X_0^2+0,25〖(-X_0)〗^2+〖(0,75X_0)〗^2=X_0^2 Рассчитаем оптимальный процесс:
X_0^*=X(0)=X_0 X_1^*=X_0+0,25U_0=X_0-0,25U_0=0,75X_0 X_2^*=X_1+0,25U_1=(0,75X_0 )+0,25(-X_1 )=0,75X_0+0,25(-X_0 )=0,5X_0 X_3^*=X_2+0,725=(0,5X_0 )+(-X_2 )=0,5X_0+(-0,25X_0 )=0,25X_0 Рассчитаем оптимальное программное управление:
U_0^* (0)=-X_0, U_1^* (0)=-〖0,75X〗_0, U_2^* (0)=-〖0,5X〗_0, U_3^* (0)=-〖0,25X〗_0
Задание №4. Синтез непрерывного оптимального управления с помощью уравнения Эйлера
Дано:
I=∫_0^∞▒〖(0,75x^2+U^2)dt→min〗 x(t)∈C_1 [0,∞) x(0)=x_0 x(∞)=0 x ̇=-0,5x+U Найти: U^*=U^* (x).
1. Выразим входное управляющее воздействие
x ̇=-0,5x+U U=x ̇+0,5x Приведем задачу к варианту задачи на безусловный экстремум:
f_0=0,75+U^2=0,75x^2+(〖x ̇+0,5x )〗^2=0,75x^2+x ̇^2+x ̇x+〖0,25x〗^2==x ̇^2+x ̇x+x^2
2. J=∫_0^∞▒( x ̇^2+x ̇x+x^2)dt
x(t)∈C_1 [0;∞) x(0)=x_0 x(∞)=0 3. Решим задачу с помощью уравнения Эйлера:
(∂f_0)/∂x∙d/dt (∂f_0)/∂x=0
(∂f_0)/∂x=2x+x ̇
(∂f_0)/(∂x ̇ )=2x ̈+x ̇
2x+x ̇-(2x ̈+x ̇ )=2x+x ̇-2x ̈-x ̇=2x-2x ̈=0 -2x ̈+2x=0 4. Решим ДУ Эйлера методом характеристического уравнения
-2p^2+2=0 -2p^2=-2 p^2=1 p1=-1,p2=1
x=C_1 e^(-t)+C_2 e^t 5. Т.к. x→∞, то C_2=0
x=C_1 e^(-t) Учитывая, что x0=C1
x=x_0 e^(-t)
Найдем оптимальную программу управления:
x ̇=-0,5x+U
U=x ̇+0,5x =(x_0 e^(-t))'+〖0,5(x〗_0 e^(-t))=(-x_0 e^(-t))+〖0,5x〗_0 e^(-t)=-x_0 e^(-t)+0,5x_0 e^(-t)=-0,5x_0 e^(-t)
〖 U〗^* (t)=-0,5x_0 e^t
6. Найдем оптимальный регулятор (оптимальный закон управления):
U^* (x)=-0,5x 7. Закон управления можно получить и другим способом:
x ̇=-x_0 e^(-t) x ̇=-x x ̇=-0,5x+U -x=-0,5x+U -0,5x=U U^*=-0,5x 8.{█(x ̇+0,[email protected]^*=-0,5x)┤
9. Структурная схема: Задание №5. Синтез непрерывных оптимальных уравнений с помощью уравнения Эйлера-Пуассона
x ̈=44U x(0)=x_0 x ̇(0)=x ̇_0 x ̇(0)=0 x(t)∈C_2 [0,∞) x(∞)=0 U-н.н. (неограниченное непрерывное) I=∫_0^∞▒〖(484x^2+U^2)dt→min〗 Найти: U^*=U^* (x,x ̇).
1. Преобразуем эту задачу в вариационную задачу на безусловный экстремум:
x ̈=44U U=1/44 x ̈ I=∫_0^∞▒〖(484x^2+x ̈/1936)dt→min〗 x(t)∈C_2 [0,∞) x(0)=x_0 x ̇(0)=x ̇_0 x ̇(0)=0 x(∞)=0 2. (∂f_0)/∂x-d/dt∙(∂f_0)/(∂x ̇ )+d^2/(dt^2 ) (∂f_0)/(∂x ̈ )
f_0=484x^2+x ̈/1936 (∂f_0)/∂x=968x; (∂f_0)/(∂x ̇ )=0; (∂f_0)/(∂x ̈ )=1/968 x ̈ 968x+1/968 x^((4) )=0 1/968 x^((4) )+968x=0 3. 1/968 p^4+968=0 1/968 p^4=-968 p^4=-937024 p_(1-4)=±√(±√(-937024)) =±√968j=±√(e^(±968j φ/2) )=±√(e^(±484jφ) )=±22±22j
x=C_1 e^(p_1 t)+C_2 e^(p_2 t)+C_3 e^(p_3 t)+C_4 e^(p_4 t)
C_3=C_4=0 p_1=-22+22j; p_1=-22-22j x=C_1 e^(p_1 t)+C_2 e^(p_2 t) 4. (p+p_1 )(p-p_2 )=0
p^2-(p_1+p_2 )p+p_1-p_2=0 p_1 p_2=(-22+22j)(-22-22j)=484+484j-484j+484=968
p_1+p_2=-22+22j-22-22j=-44 p^2+44p+484=0 5. x ̈+44x ̇+484=0
x ̈=44U; 44U+44x ̇+484x=0 U=-x-22x 6. Составим оптимальную синтезированную систему управления:
{█(x ̈[email protected]^*=-x ̇-22x)┤ 7. Структурная схема:
4
Автор
1/--страниц