Математическое программирование
Методическое пособие - Компьютеры, программирование
Другие методички по предмету Компьютеры, программирование
М, и решают задачу обычным способом.
2. Обязательные поставки.
а) Если необходимо из п. Аi перевезти в п. Вj определенное количество продукции dij, соответствующую клетку заполняют сразу числом dij, а в дальнейшем решают задачу, считая заполненную клетку свободной, но с тарифом, сij = М, равным очень большому числу, а запасы и потребности уменьшают на величину dij.
б) Если необходимо из п. Аi в п. Вj перевезти не меньше определенного количества продукции dij, то считают запасы и потребности меньше на величину dij, это количество dij считают перевезенным по маршруту Аi Вj, и решают задачу далее обычным способом.
в) Если необходимо перевезти из п. Аi в п. Вj не более определенного количества продукции dij, вводят дополнительный пункт назначения с потребностью, равной ( - dij), потребность в п. Вj делают равной dij. Тарифы на перевозки в дополнительный пункт назначения равны тарифам п. Вj , кроме i-той строки, тариф в которой будет равен сколь угодно большому числу М. Решают задачу обычным образом, а при записи ответа объединяют основного и дополнительного потребителя (складывают содержимое столбцов).
Лекция 14, 15
Метод динамического программирования
Вопросы:
1. Основные понятия. Общая постановка задачи ДП.
. Принцип оптимальности. Функциональные уравнения Беллмана.
. Задача оптимального распределения ресурсов.
. Задача о замене.
. Задача управления производством и запасами.
1. Основные понятия. Общая постановка задачи динамического программирования
Динамическое программирование - метод оптимизации, приспособленный к операциям, в которых процесс принятия решений может быть разбит на отдельные этапы, шаги.
Такие операции называются многошаговыми. Многие экономические процессы расчленяются на шаги естественным образом. Это процессы планирования и управления, развиваемые во времени. Естественным шагом может быть год, квартал, месяц и т.д. Т.о., если управление сводится к однократному принятию решения, то соответствующая задача называется одноэтапной или одношаговой. Ранее решаемые задачи линейного и нелинейного программирования - примеры подобных задач. Если управление требует некоторой последовательности принятых решений, то такая задача называется многоэтапной или многошаговой.
Рассмотрим некоторую управляемую систему, характеризующуюся определенным набором параметров, задающих ее состояния. Система под влиянием управления переходит из начального состояния в конечное. Введем обозначения.
1. xi - многомерный вектор, компоненты которого определяют состояние системы на i-том шаге. Дальнейшее изменение состояния зависит только от данного состояния и не зависит от того, каким путем система перешла в него (процесс без последствия).
2. На каждом шаге выбирается одно решение, управление ui , под действием которого система переходит из предыдущего состояния xi-1 в новое xi. Это новое состояние является функцией состояния на начало шага xi-1 и принятого в начале решения ui , т.е.
xi = xi ( xi-1 , ui ).
. Действие на каждом шаге связано с определенным выигрышем (доходом, прибылью) или потерей (издержками), которые зависят от состояния на начало шага и принятого решения. Fi - приращение целевой функции задачи в результате i-того шага, аналогично, Fi = Fi ( xi-1 , ui ). Тогда значение целевой функции при переходе системы из начального состояния в конечное за n шагов
.
. На векторы состояния хi и управления ui могут быть наложены ограничения, объединение которых составляет область допустимых решений u U.
5. Требуется найти такое допустимое управление u* = (u1* ,…, un* ) (для каждого шага), чтобы получить экстремальное значение функции цели F* за все n шагов.
Любая последовательность действий для каждого шага, переводящая систему из начального состояния в конечное, называется стратегией управления.
Допустимая стратегия управления, доставляющая функции цели экстремальное значение, называется оптимальной.
2. Принцип оптимальности. Функциональные уравнения Беллмана
Метод динамического программирования состоит в том, что оптимальное управление строится постепенно, шаг за шагом. На каждом шаге оптимизируется управление только этого шага. Вместе с тем на каждом шаге управление выбирается с учетом последствий, т.к. управление, оптимизирующее целевую функцию только для данного шага, может привести к неоптимальному эффекту всего процесса. Управление на каждом шаге должно быть оптимальным с точки зрения процесса в целом. В основе метода динамического программирования лежит принцип оптимальности, сформулированный Беллманом.
Принцип оптимальности: если некоторая последовательность решений оптимальна, то на любом шаге последующие решения образуют оптимальную стратегию по отношению к результату предыдущих решений.
Другими словами, каково бы не было состояние системы перед очередным шагом, надо выбрать управление на этом шаге так, чтобы выигрыш на данном шаге (проигрыш) плюс оптимальный выигрыш (проигрыш) на всех последующих шагах был бы максимальным (минимальным). На основе принципа оптимальности Беллмана строится схема решения монгошаговой задачи, состоящая из 2-х частей:
1) Обратный ход: от последнего шага к первому получают множество возможных оптимальных (условно-оптимальных) управлений.