6 Оглавление

Исходные данные 5

Задание №1. Графоаналитическое решение ОЗЛП 6

Задание № 2. Задача о коммивояжере. Метод ветвей и границ 12

Задание №3. Оптимизация дискретных управлений дискретными динамическими объектами методом динамического программирования Р. Беллмана 20

Задание №4. Синтез непрерывного оптимального управления с помощью уравнения Эйлера 23

Задание №5. Синтез непрерывных оптимальных уравнений с помощью уравнения Эйлера-Пуассона 28

Исходные данные

К заданию №1.

№	C1	C2	B1	B2	B3	B4	A11	A12	A21	A22	A31	A32	A41	A42
213	2,5	1,5	12	2	2	0,5	-1	8	4	-7	-2	2	2	-4

К заданию №2.

		1	2	3	4	5	6
С =	1	∞	1	5	4	1	3
	2	5	∞	1	6	7	2
	3	6	2	∞	3	4	1
	4	1	5	4	∞	6	7
	5	3	6	1	1	∞	4
	6	7	3	6	5	1	∞

К заданию №3.

№	A	B	α	β	γ
113	1,1	0,6	1,8	1,2	4

К заданию №4.

№	A	B	α2
113	0,6	0,3	12

К заданию №5.

№	k	γ
113	26	13

Задание №1. Графоаналитическое решение озлп

1. Математическая постановка ОЗЛП:

φ=2,5x₁+1,5x₂→max, (0)

-x₁+8x₂≤12, (1)

4x₁-7x₂≤2, (2)

-2x₁+2x₂≤2 , (3)

2x₁-4x₂≤0,5, (4)

x₁≥0, (5)

x₂≥0, (6)

DF: -x₁+8x₂=12, (1’)

EF: 4x₁-7x₂=2, (2’)

BD: -2x₁+2x₂=2, (3’)

CE: 2x₁-4x₂=0,5, (4’)

AC: x₁=0, (5’)

AB:x₂=0, (6’)

2. Записываем уравнение граничных линий допустимого многоугольника (1’) -(6’).

Построим область допустимых решений, т.е. решим графически систему неравенств. Для этого построим каждую прямую и определим полуплоскости, заданные неравенствами (полуплоскости обозначены штрихом).

Построим уравнение -x₁+8x₂= 12 по двум точкам. Для нахождения первой точки приравниваем x₁= 0. Находим x₂= 1.5. Для нахождения второй точки приравниваем x₂= 0. Находим x₁= -12. Соединяем точку (0;1.5) с (-12;0) прямой линией.

Построим уравнение 4x₁-7x₂= 2 по двум точкам. Для нахождения первой точки приравниваем x₁= 0. Находим x₂= -0.29. Для нахождения второй точки приравниваем x₂= 0. Находим x₁= 0.5. Соединяем точку (0;-0.29) с (0.5;0) прямой линией.

Построим уравнение -2x₁+2x₂= 2 по двум точкам. Для нахождения первой точки приравниваем x₁= 0. Находим x₂= 1. Для нахождения второй точки приравниваем x₂= 0. Находим x₁= -1. Соединяем точку (0;1) с (-1;0) прямой линией.

Построим уравнение 2x₁-4x₂= 0.5 по двум точкам. Для нахождения первой точки приравниваем x₁= 0. Находим x₂= -0.13. Для нахождения второй точки приравниваем x₂= 0. Находим x₁= 0.25. Соединяем точку (0;-0.13) с (0.25;0) прямой линией.

3. Строим линию, пересекающую область φ.

, (7)

, (8)

4. Находим градиент целевой функции:

, (9)

, (10)

Пересечением полуплоскостей будет являться область, координаты точек которого удовлетворяют условию неравенствам системы ограничений задачи.

Обозначим границы области многоугольника решений.

Рассмотрим целевую функцию задачи φ=2,5x₁+1,5x₂→max. Построим прямую, отвечающую значению функции φ=0: F=2,5x₁+1,5x₂=0. Вектор-градиент, составленный из коэффициентов целевой функции, указывает направление максимизации F(X). Начало вектора – точка (0; 0), конец – точка (2.5; 1.5). Будем двигать эту прямую параллельным образом. Поскольку нас интересует максимальное решение, поэтому двигаем прямую до последнего касания обозначенной области. На графике эта прямая обозначена пунктирной линией.

Из рисунка видно, что оптимальная точка F* равная, Прямая F(x) = const пересекает область в точке F. Так как точка F получена в результате пересечения прямых (1) и (2), то ее координаты удовлетворяют уравнениям этих прямых:

-x1+8x2≤12, (1)

4x1-7x2≤2, (2)

Решив систему уравнений, получим: x₁= 4, x₂= 2, откуда найдем максимальное значение целевой функции:

, , (11)

, (12)

Ответ: ,;