Заглавная страница Избранные статьи Случайная статья Познавательные статьи Новые добавления Обратная связь КАТЕГОРИИ: АрхеологияБиология Генетика География Информатика История Логика Маркетинг Математика Менеджмент Механика Педагогика Религия Социология Технологии Физика Философия Финансы Химия Экология ТОП 10 на сайте Приготовление дезинфицирующих растворов различной концентрацииТехника нижней прямой подачи мяча. Франко-прусская война (причины и последствия) Организация работы процедурного кабинета Смысловое и механическое запоминание, их место и роль в усвоении знаний Коммуникативные барьеры и пути их преодоления Обработка изделий медицинского назначения многократного применения Образцы текста публицистического стиля Четыре типа изменения баланса Задачи с ответами для Всероссийской олимпиады по праву Мы поможем в написании ваших работ! ЗНАЕТЕ ЛИ ВЫ?
Влияние общества на человека
Приготовление дезинфицирующих растворов различной концентрации Практические работы по географии для 6 класса Организация работы процедурного кабинета Изменения в неживой природе осенью Уборка процедурного кабинета Сольфеджио. Все правила по сольфеджио Балочные системы. Определение реакций опор и моментов защемления |
Принцип оптимальности Беллмана
Основным методом динамического программирования является метод рекуррентных соотношений; который основывается на использовании принципа оптимальности, разработанного американским математиком Р.Беллманом. Суть принципа: Каковы бы ни были начальное состояние на любом шаге и управление, выбранное на этом шаге, последующие управления должны выбираться ОПТИМАЛЬНЫМИ относительно состояния, к которому придет система в конце каждого шага. Использование данного принципа гарантирует, что управление, выбранное на любом шаге, не локально лучше, а лучше с точки зрения процесса в целом. Условная оптимизация
Безусловная оптимизация Si – состояние системы на i-м шаге. Основная рекуррентная формула динамического программирования в случае решения задачи максимизации имеет вид: , где максимум в данной формуле берется по всем возможным решениям в ситуации, когда система на шаге m находится в состоянии i. Величина fm(i) – есть максимальная прибыль завершения задачи из состояния i, если предположить, что на шаге m, система находится в состоянии i. Максимальная прибыль может быть получена максимизацией суммы прибылей самого шага m и максимальной прибыли шага (m+1) и далее, чтобы дойти до конца задачи. Планируя многошаговую операцию надо выбирать управление на каждом шаге с учетом всех его будущих последствий на ещё предстоящих шагах. Управление на i-м шаге выбирается не так, чтобы выигрыш именно на данном шаге был максимальным, а так, чтобы была максимальна сумма выигрышей на всех оставшихся шагах плюс данный шаг. Среди всех шагов последний шаг планируется без оглядки на будущее, т.е. чтобы он сам, как таковой принес наибольшую выгоду.
Задача динамического программирования решается в два этапа: 1 этап (от конца к началу по шагам): Проводится условная оптимизация, в результате чего находится условные оптимальные управления и условные оптимальные выигрыши по всем шагам процесса. 2 этап (от начала к концу по шагам): Выбираются (просчитываются) уже готовые рекомендации от 1-го шага до последнего и находится безусловное оптимальное управление х*, равный х*1, х*2, …, х*m.
Пример. Имеется запас средств, который нужно распределить между предприятиями, чтобы получить наибольшую прибыль. Пусть начальный капитал S0 =100 д.ед. Функции дохода предприятий даны в матрице прибылей по каждому предприятию.
Используем принцип Беллмана. Каковы бы ни были начальное состояние на любом шаге и управление, выбранное на этом шаге, последующие управления должны выбираться оптимальными относительно состояния, к которому придет система в конце каждого шага. Использование данного принципа гарантирует, что управление, выбранное на любом шаге, не локально лучше, а лучше с точки зрения процесса в целом. Схема решения:
Математическая модель задачи: Экономический смысл переменных: xi – количество денег, вкладываемых в i предприятие. Si – количество денег, оставшихся после вложения в i-предприятие (состояние системы на i-шаге); F(xi) – прибыль от вложенной суммы денег; S0 – начальный капитал. Рассмотрим 4-й шаг: На 4-ом предприятии может остаться либо 0, либо 20, либо 40, либо 60, либо 80, либо 100 ден. ед. Тогда прибыль от вложения денег можно получить следующую.
Рассмотрим 3-й шаг: На 3-ем и 4-ем предприятии может остаться либо 0, либо 20, либо 40, либо 60, либо 80, либо 100 ден. ед. Рассмотрим первую возможность. Если 3-му предприятию мы выдаем 20 ден. ед. то 4-му предприятию ничего не остается, и наоборот. Соответственно 40 ден. ед. можно поделить так (0;40), (20;20); 60 ден. ед. – (0;60), (20;40), (40;20), (60;0). Прибыль от вложения денег в 3-е предприятие берется в исходной матрице прибылей, а прибыль от вложений, денег в 4-е предприятие берется из таблицы предыдущего шага Прибыль на 3-м шаге берется максимальной по каждому вложению.
Рассмотрим 2 -й шаг:
Рассмотрим 1-й шаг:
Анализ результатов: Максимальная прибыль равна 15 д.ед. Расположить денежные средства между проектами можно несколькими способами: 1) 1 предприятие – 0 ден. ед., 2 предприятие – 0 ден. ед., 3 предприятие – 60 ден. ед., 4 предприятие т – 40 ден. ед. 2) 1 предприятие – 0 ден. ед., 2 предприятие – 100 ден. ед., 3 предприятие – 0 ден. ед., 4 предприятие – 0 ден. ед. 3) 1 предприятие – 20 ден. ед., 2 предприятие – 0 ден. ед., 3 предприятие – 60 ден. ед.., 4 предприятие – 20 ден. ед. 4) 1 предприятие – 60 ден. ед., 2 предприятие – 0 ден. ед., 3 предприятие – 20 ден. ед., 4 предприятие – 20 ден. ед. 5) 1 предприятие – 60 ден. ед., 2 предприятие – 0 ден. ед., 3 предприятие – 0 ден. ед., 4 предприятие т – 40 ден. ед.
|
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
Последнее изменение этой страницы: 2021-02-07; просмотров: 146; Нарушение авторского права страницы; Мы поможем в написании вашей работы! infopedia.su Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. Обратная связь - 3.17.79.59 (0.019 с.) |