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

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

 
 
 

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

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

      на  тему: 

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

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

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

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

Шифр  К-1205

Группа  401-П

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

      Волгоград, 2011

 

      

Содержание

Введение 4

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

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

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

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

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

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

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

Заключение 22

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

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

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

 

      

Введение

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

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

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

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

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

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

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

 

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

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

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

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

1. возможные исходы предыдущего шага;
2. влияние управления на все оставшиеся до конца процесса шаги (п — к).

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

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

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

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

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

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

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

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

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

     Из  условия следует, что состояние  экономической системы характеризуется двумя параметрами: количеством принятых и оформленных машин по разгрузке товара и количеством машин отправленных с товаром в магазины. Поэтому решение будем искать на плоскости XOY, ограниченной прямоугольником, который является областью допустимых состояний системы. Если по оси X отложить число п разгруженных машин, а по оси Y— число т загруженных товаром машин, то можно построить на плоскости граф состояний процесса, в котором каждая вершина характеризует состояние операции приема и отгрузки товара на оптовой базе. Ребра этого графа означают выполнение работы по приему или отправке товара на очередной машине. Каждому ребру можно сопоставить издержки, связанные с выполнением операции по разгрузке или загрузке машины.

     Пример. Пусть n = 6, m = 4. Известны затраты по выполнению каждой операции, которые показаны на ребрах графа (рис. 5.7.1).

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

Рис 1.2.1 Графическая схема связи операций

     I этап. Условная оптимизация

     1-й  шаг: k = 1. На первом шаге с задаваемым сечением, из состояний и возможен только один вариант перехода в конечное состояние . Поэтому в вершинах  и записываем соответственно издержки 8 и 11. Ребра и обозначаем стрелкой, направленной в вершину -, как показано на рис. 1.2.2.

Рис 1.2.2 Фрагмент связи операции (шаг 1)

     2-й  шаг: k = 2. Второй шаг оптимизации задается сечением по вершинам. Из состояний и , возможен единственный переход в вершины , и соответственно, поэтому в вершинах и записываем суммарные издержки 17 и 22 на первых двух шагах перехода в конечное состояние .

     Из  вершины  возможны два варианта перехода: в вершинy или вершину  . При переходе сумма издержек составляет 10 + 8 = 18, на переходе сумма составляет 13 + 11 = 24. Из двух вариантов суммарных издержек выбираем наименьшую (18) и обозначаем стрелкой условно оптимальный переход, как показано на рис. 1.2.3.

Рис 1.2.3 Сетевая модель операции (шаг 2)

     3-й  шаг: k = 3. На третьем шаге сечение проходит через вершины , , ,. Из вершин и возможен единственный переход в вершины соответственно. Суммарные издержки для состояния   равны 22 + 12 = 34. Из вершины возможны два варианта перехода: в вершину издержки равны 17 + 8 = 25; в вершину 18 + 9 = 27.