Студопедия

КАТЕГОРИИ:

Авто Автоматизация Архитектура Астрономия Аудит Биология Бухгалтерия Военное дело Генетика География Геология Государство Дом Журналистика и СМИ Изобретательство Иностранные языки Информатика Искусство История Компьютеры Кулинария Культура Лексикология Литература Логика Маркетинг Математика Машиностроение Медицина Менеджмент Металлы и Сварка Механика Музыка Население Образование Охрана безопасности жизни Охрана Труда Педагогика Политика Право Приборостроение Программирование Производство Промышленность Психология Радио Регилия Связь Социология Спорт Стандартизация Строительство Технологии Торговля Туризм Физика Физиология Философия Финансы Химия Хозяйство Ценнообразование Черчение Экология Эконометрика Экономика Электроника Юриспунденкция

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

Стр 1 из 2Следующая ⇒

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

Кзаданию №1.

№	C1	C2	B1	B2	B3	B4	A11	A12	A21	A22	A31	A32	A41	A42
220	3	4	1	4	0,5	0,5	1	-1,5	-2	6	1	-2	-2	2

Кзаданию №2.

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

К заданию №3.

№	A	B	α	β	γ
120	1	0,25	1	0,75	4

К заданию №4.

№	A	B	α²
120	0,3	0,6	3/4

К заданию №5.

№	k	γ
120	40	20

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

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

φ=3x₁+4x₂→max, (0)

x₁-1,5x₂≤1, (1)

-2x₁+6x₂≤4, (2)

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

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

x₁≥0, (5)

x₂≥0, (6)

EF: x₁-1,5x₂=1, (1’)

DF: -2x₁+6x₂=4, (2’)

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

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

AC: x₁=0, (5’)

AB: x₂=0, (6’)

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

На плоскости (x1, x2) строим граничные линии.

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

, (7)

, (8)

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

, (9)

, (10)

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

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

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

Из рисунка видно, что оптимальная точка F* равная , находится на пересечении линий DFи EFи ее координаты определяются путем решения одноименных уравнений (1’) и (2’).

, , (11)

, (12)

Ответ: , ;

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

Расстояния между пунктами заданы матрицей:

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

Решение задачи о коммивояжере методом ветвей и границ начинается с приведения матрицы (вычитания из каждой строки (столбца) матрицы C минимального элемента этой строки (столбца).

Произведем приведение матрицы Cпо строкам:

h_ν=min(i) h_ν_i

		1	2	3	4	5	6	h_ν
С’ =	1	∞	3	4	5	1	6	1
	2	1	∞	5	1	3	2	1
	3	4	2	∞	3	6	1	1
	4	3	4	1	∞	5	7	1
	5	5	1	6	2	∞	3	1
	6	1	6	3	1	4	∞	1

Произведем приведение матрицы Cпо столбцам:

g_i = min(υ) g_ν_i

		1	2	3	4	5	6
С’ =	1	∞	2	3	4	0	5
	2	0	∞	4	0	2	1
	3	3	1	∞	2	5	0
	4	2	3	0	∞	4	6
	5	4	0	5	1	∞	2
	6	0	5	2	0	3	∞
	g_i	0	0	0	0	0	0

В итоге получаем полностью приведенную (редуцированную) матрицу:

		1	2	3	4	5	6	h_ν
С₀ =	1	∞	2	3	4	0	5	1
	2	0	∞	4	0	2	1	1
	3	3	1	∞	2	5	0	1
	4	2	3	0	∞	4	6	1
	5	4	0	5	1	∞	2	1
	6	0	5	2	0	3	∞	1
	g_i	0	0	0	0	0	0

Величины h_ν и g_i называются константами приведения.

Нижняя граница цикла: d₀=6 ( ).

Шаг №1.

Определяем ребро ветвления и разобьем все множество допустимых значений Q⁰ относительно этого ребра на два непересекающихся подмножества ( ) и ( ), т.е. , где

В приведенной матрице исследуем все нулевые переходы.

		1	2	3	4	5	6	α_ν
C₀ =	1	∞	2	3	4	0(4)	5	2
	2	0(0)	∞	4	0(0)	2	1	0
	3	3	1	∞	2	5	0(2)	1
	4	2	3	0(4)	∞	4	6	2
	5	4	0(2)	5	1	∞	2	1
	6	0(0)	5	2	0(0)	3	∞	0
	β_i	0	1	2	0	2	1

Наибольшая сумма констант приведения равна

υ₁₅=α₁+ β₅=2+2=4, следовательно,

множество разбивается на два подмножества и .

Оценка длины цикла: .

В результате получим другую сокращенную матрицу (5x5), которая подлежит операции приведения.

После операции приведения сокращенная матрица будет иметь вид:

		1	2	3	4	6	h_ν
	2	0	∞	4	0	1	0
	3	3	1	∞	2	0	0
C₁=	4	2	3	0	∞	6	0
	5	∞	0	5	1	2	0
	6	0	5	2	0	∞	0
	g_i	0	0	0	0	0

d₁=0

Шаг №2.

Определяем ребро ветвления и разобьем все множество допустимых значений Q¹ относительно этого ребра на два непересекающихся подмножества .

В приведенной матрице исследуем все нулевые переходы.

		1	2	3	4	6	α_ν
	2	0(0)	∞	4	0(0)	1	0
	3	3	1	∞	2	0(2)	1
C₁=	4	2	3	0(4)	∞	6	2
	5	∞	0(2)	5	1	2	1
	6	0(0)	5	2	0(0)	∞	0
	β_i	0	1	2	0	1

Наибольшая сумма констант приведения равна

υ₄₃=2+2=4, следовательно,

множество разбивается на два подмножества и .

Оценка длины цикла: .

Оценка на перспективном множестве:

В результате получим другую сокращенную матрицу (4x4), которая подлежит операции приведения.

После операции приведения сокращенная матрица будет иметь вид:

		1	2	4	6	h_ν
C₂ =	2	0	∞	0	1	0
	3	3	1	∞	0	0
	5	∞	0	1	2	0
	6	0	5	0	∞	0
	g_i	0	0	0	0

d₂=0

Шаг №3.

Определяем ребро ветвления и разобьем все множество допустимых значений Q²относительно этого ребра на два непересекающихся подмножества .

В приведенной матрице исследуем все нулевые переходы.

		1	2	5	6	α_ν
C₂ =	2	0(0)	∞	0(0)	1	0
	3	3	1	∞	0(2)	1
	5	∞	0(2)	1	2	1
	6	0(0)	5	0(0)	∞	0
	β_i	0	1	0	1

Наибольшая сумма констант приведения равна

υ₃₆=1+1=2, следовательно,

множество разбивается на два подмножества и .

Оценка длины цикла: .

Оценка на перспективном множестве:

В результате получим другую сокращенную матрицу (3x3), которая подлежит операции приведения.

После операции приведения сокращенная матрица будет иметь вид:

		1	2	4	h_ν
	2	0	∞	0	0
C₃ =	5	∞	0	1	0
	6	0	5	0	0
	g_i	0	0	0

d₃=0

Шаг №4.

Определяем ребро ветвления и разобьем все множество допустимых значений Q³относительно этого ребра на два непересекающихся подмножества .

В приведенной матрице исследуем все нулевые переходы.

		1	2	4	α_ν
	2	0(0)	∞	0(1)	2
C₃ =	5	∞	0(6)	1	1
	6	0(5)	5	∞	5
	β_i	0	5	1

Наибольшая сумма констант приведения равна

υ₅₂=1+5=6, следовательно,

множество разбивается на два подмножества и .

Оценка длины цикла: .

Оценка на перспективном множестве:

В результате получим другую сокращенную матрицу (2x2), которая подлежит операции приведения.

После операции приведения сокращенная матрица будет иметь вид:

		1	4	h_ν
C₄ =	2	0	0	0
C₄ =	6	0	∞	0
	g_i	0	0

d₄=0

В соответствии с этой матрицей включаем в маршрут и .

Ответ: l* =C₁₅+C₅₂+C₂₄+C₄₃+C₃₆+C₆₁=1+1+1+1+1+1=6.

Дерево решения имеет следующий вид:

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

Дано:

(1) k=0,1,2,3

(2)

, (3) n=4

U – н.у. (неограниченное управление), (4)

, (5)

Найти: (6).

Решение

Минимизируем

Вычислим S₃от x₃:

Минимизируем

Вычислим S₂от U₂:

Минимизируем

Вычислим S₁от U₂:

Минимизируем

Вычислим S₀от U₀:

Рассчитаем оптимальный процесс:

X₀

0,75X₀

0,5X₀

0,25X₀

Рассчитаем оптимальное программное управление:

-0,75

-0,5

-0,25

-1

12 Следующая ⇒

Последнее изменение этой страницы: 2018-06-01; просмотров: 209.

stydopedya.ru не претендует на авторское право материалов, которые вылажены, но предоставляет бесплатный доступ к ним. В случае нарушения авторского права или персональных данных напишите сюда...