Принцип оптимальности и математическое описание динамического процесса управления

ФГОУ СПО «Волгоградский государственный экономико-технический колледж»

Кафедра информационных технологий

КУРСОВОЙ ПРОЕКТ

по дисциплине: Математические методы

 

на тему:

 

Построение оптимальной последовательности операций в коммерческой деятельности

Пояснительная записка

ВГЭТК. 401-П. 13. КП.13. ПЗ

 

Студента: Кролькова Ильи Владимировича

Шифр К-1205

Группа 401-П

Руководитель: Еловенко Н. А.

 

 

Волгоград, 2011

 

Содержание

Введение. 3

1 Теоретическая часть. 3

1.1 Принцип оптимальности и математическое описание динамического процесса управления. 3

1.2 Построение сетевой модели последовательности операций в коммерческой деятельности и ее решение. 3

2 Практическая часть. 3

2.1 Решение задачи с помощью математического аппарата. 3

2.2 Решение задачи средствами прикладных программ. 3

2.3 Автоматизация решения задачи. 3

Заключение. 3

Библиографический список. 3

Приложение А Блок-схема алгоритма. 3

Приложение Б Листинг расчета в VBA.. 3

Введение

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

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

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

Для достижения поставленной цели необходимо решить следующие задачи:

− изучить предметную область решаемой проблемы;

− разработать этапы решения задачи;

− рассмотреть принципы использования прикладных программ для расчета основных характеристик по теме задачи;

− разработать приложение, позволяющее автоматизировать процесс решения задачи.

Объект исследования – построение сетевой модели последовательности операций .

Предмет исследования – построение оптимальной последовательности операций в коммерческой деятельности.

 

Теоретическая часть

Принцип оптимальности и математическое описание динамического процесса управления

В основе метода ДП лежит принцип оптимальности, впервые сформулированный в 1953 г. американским математиком Р.Э. Беллманом: каково бы ни было состояние системы в результате какого-либо числа шагов, на ближайшем шаге нужно выбирать управление так, чтобы оно в совокупности с оптимальным управлением на всех последующих шагах приводило к оптимальному выигрышу на всех оставшихся шагах, включая выигрыш на данном шаге. При решении задачи на каждом шаге выбирается управление, которое приводит к оптимальному выигрышу. Если считать все шаги независимыми, тогда оптимальным управлением будет то управление, которое обеспечит максимальный выигрыш на каждом шаге. Однако, например, при покупке новой техники взамен устаревшей на ее приобретение затрачиваются определенные средства, поэтому доход от ее эксплуатации в начале может быть небольшой, а в следующие годы новая техника будет приносить больший доход. И наоборот, если принято решение оставить старую технику для получения дохода в текущем году, то в дальнейшем это приведет к значительным убыткам. Этот пример демонстрирует следующий факт: в многошаговых процессах управление на каждом конкретном шаге надо выбирать с учетом его будущих воздействий на весь процесс.

Кроме того, при выборе управления на данном шаге следует учитывать возможные варианты состояния предыдущего шага. Например, при определении количества средств, вкладываемых в предприятие в i-м году, необходимо знать, сколько средств осталось в наличии к этому году и какой доход получен в предыдущем -м году. Таким образом, при выборе шагового управления необходимо учитывать следующие требования:

1) возможные исходы предыдущего шага ;

2) влияние управления на все оставшиеся до конца процесса шаги (п — к).

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

Условная оптимизация. На первом этапе решения задачи, называемом условной оптимизацией, определяются функция Беллмана и оптимальные управления для всех возможных состояний на каждом шаге, начиная с последнего в соответствии с алгоритмом обратной прогонки. На последнем, n-м, шаге оптимальное управление определяется функцией Беллмана: в соответствии с которой максимум выбирается из всех возможных значений причем .

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

Этот максимум (или минимум) определяется по всем возможным для k и S значениям переменной управлениях

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

Пользуясь тем, что на первом шаге (k = 1) состояние системы известно - это ее начальное состояние можно найти оптимальный результат за все п шагов и оптимальное управление на первом шаге , которое этот результат доставляет. После применения этого управления система перейдет в другое состояние   зная которое, можно, пользуясь результатами условной оптимизации, найти оптимальное управление на втором шаге и так далее до последнего п-го шага.

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