SEMINAR4 (Семинары)

МОСКОВСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ им М.В. ЛОМОНОСОВА

ФАКУЛЬТЕТ ВОЕННОЙ ПОДГОТОВКИ

Кафедра войск ПВО

«УТВЕРЖДАЮ»

Начальник военной кафедры Войск ПВО

полковник О. Калашников

«_____» _______________ 199___г.

Методическая разработка

для проведения занятий по разделу:

«Математические методы моделирования исследований боевых действий войск и анализа сложных систем (моделей операций)»

профиль ВУС 530700

ТЕМА: 17 Методы динамического программирования и их применение к задачам планирования боевых действий

ЗАНЯТИЕ: 36 Решение задач по определению оптимальной стратегии при исследовании боевых действий

Обсуждена на заседании цикла 24

«__» __________ 1997 г.

ПРОТОКОЛ ___________________

Москва 1993 г.

Учебная и воспитательная цели:

Привить студентам практические навыки в применении метода динамического программирования при исследовании боевых действий. Привить навыки работы с личным составом при решении задач исследования операций с АСУ.

Организационно-методические указания:

Материал данной темы изучается на лекциях и групповых занятиях. В ходе лекций изучаются следующие вопросы:

1. Модели боевых операций ПВО, исследуемые методы динамического программирования;

2. Понятие дискретного многошагового процесса;

3. принцип оптимальности Беллмана;

4. Функциональные уравнения процесса;

5. Составление основных рекуррентных соотношений;

6. Общая вычислительная схема метода динамического программирования;

7. Решение задач об оптимальном распределении ресурсов и оптимальном управлении.

На групповых занятиях студенты должны закрепить теоретические знания, полученные на лекциях и получить практические навыки в решении военных задач методом динамического программирования.

Занятия 3,4. Решение задач по выбору оптимальной стратегии при исследовании боевых действий.

Время: 4 часа.

Учебная и воспитательная цели:

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

Методика проведения занятия:

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

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

Основной целью группового занятия является получение практических навыков студентами: в алгоритмизации поставленной задачи и в построении вычислительной схемы задачи.

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

В качестве задач рассматриваются: выбор оптимального маршрута и оптимальное распределение снарядов при стрельбе по групповой цели

В качестве задания на самостоятельную работу необходимо дать студентам следующую задачу об оптимальном распределении средств по объектам удара.

Постановка задачи об оптимальном распределении средств по объектам удара.

Для нанесения удара по объектам выделяется однотипных средств. Каждое средство может воздействовать только по одному объекту. Ущерб, наносимый -му объекту -м количеством в условных единицах составляет . Распределить средств между объектами так, чтобы суммарный ущерб, нанесенный всем объектам, был максимальным.

Пример. ; ; заданы таблицей

Краткое содержание занятий 3,4.

Учебный вопрос № 1.

Математическая формулировка задач динамического программирования.

1. Принцип оптимальности Беллмана

Найти числа

максимизирующие функцию

при ограничениях

Из выражения следует вывод функционального уравнения

где

Доказательство:

Имеем

Следовательно

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

Часто процесс оптимизации строится с конца, тогда функциональные уравнения представляются в виде:

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

В общем случае процесс пошаговой оптимизации представляется так:

Рассматривается система, которая на каждом -м шаге под влиянием переходит из состояния в состояние .

Если - показатель эффективности на -ом шаге, то , при этом предполагается отсутствие последействия . Показателем эффективности процесса шагов является целевая функция, которая должна удовлетворять условию аддитивности.

Задачу динамического программирования можно сформулировать следующим образом: определить совокупность допустимых (удовлетворяющих некоторым ограничениям) управлений переводящих систему из начального состояния в конечное и оптимизирующих целевую функцию.

2. Постановка задачи о выборе оптимального маршрута.

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

3. Формализация задачи.

Для каждой точки задано число . Необходимо найти такую последовательность точек

чтобы

4. Последовательность вычислений.

1-й этап - обратных ход:

2-й этап - прямой ход:

После узла выбирается один из узлов или , для которого найдется

или

Числовой пример.

а) Обратных ход

б) Прямой ход