Реферат: Динамическое программирование 2

СОДЕРЖАНИЕ

С.

Введение 3

1 Теоретическая часть. Модели динамического программирования 4

1.1 Предмет динамического программирования 4

1.2 Постановка задачи динамического программирования 6

1.3 Принцип оптимальности и математическое описание динамического процесса управления 8 1.4Оптимальное распределение инвестиций 10

1.5 Выбор оптимальной стратегии обновления оборудования 13

2 Расчетная часть 16

Заключение 30

Список использованных источников 31

ВВЕДЕНИЕ

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

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

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

1 ТЕОРЕТИЧЕСКАЯ ЧАСТЬ. МОДЕЛИ ДИНАМИЧЕСКОГО ПРОГРАММИРОВАНИЯ 1.1 ПРЕДМЕТ ДИНАМИЧЕСКОГО ПРОГРАММИРОВАНИЯ Динамическое программирование представляет собой математический аппарат, который подходит к решению некоторого класса задач путем их разложения на части, небольшие и менее сложные задачи. При этом отличительной особенностью является решение задач по этапам, через фиксированные интервалы, промежутки времени, что и определило появление термина динамическое программирование. Следует заметить, что методы динамического программирования успешно применяются и при решении задач, в которых фактор времени не учитывается. В целом математический аппарат можно представить как пошаговое или поэтапное программирование. Решение задач методами динамического программирования проводится на основе сформулированного Р. Э. Беллманом принципа оптимальности: оптимальное поведение обладает тем свойством, что каким бы ни было первоначальное состояние системы и первоначальное решение, последующее решение должно определять оптимальное поведение относительно состояния, полученного в результате первоначального решения.Из этого следует, что планирование каждого шага должно проводиться с учетом общей выгоды, получаемой по завершении всего процесса, что и позволяет оптимизировать конечный результат по выбранному критерию.Таким образом, динамическое программирование в широком смысле представляет собой оптимальное управление процессом, посредством изменения управляемых параметров на каждом шаге, и, следовательно, воздействуя на ход процесса, изменяя на каждом шаге состояние системы.В целом динамическое программирование представляет собой стройную теорию для восприятия и достаточно простую для применения в коммерческой деятельности при решении как линейных, так и нелинейных задач.Динамическое программирование является одним из разделов оптимального программирования. Для него характерны специфические методы и приемы, применительные к операциям, в которых процесс принятия решения разбит на этапы (шаги). Методами динамического программирования решаются вариантные оптимизационные задачи с заданными критериями оптимальности, с определенными связями между переменными и целевой функцией, выраженными системой уравнений или неравенств. При этом, как и в задачах, решаемых методами линейного программирования, ограничения могут быть даны в виде равенств или неравенств. Однако если в задачах линейного программирования зависимости между критериальной функцией и переменными обязательно линейны, то в задачах динамического программирования эти зависимости могут иметь еще и нелинейный характер. Динамическое программирование можно использовать как для решения задач, связанных с динамикой процесса или системы, так и для статических задач, связанных, например, с распределением ресурсов. Это значительно расширяет область применения динамического программирования для решения задач управления. А возможность упрощения процесса решения, которая достигается за счет ограничения области и количества, исследуемых при переходе к очередному этапу вариантов, увеличивает достоинства этого комплекса методов.Вместе с тем динамическому программированию свойственны и недостатки. Прежде всего, в нем нет единого универсального метода решения. Практически каждая задача, решаемая этим методом, характеризуется своими особенностями и требует проведения поиска наиболее приемлемой совокупности методов для ее решения. Кроме того, большие объемы и трудоемкость решения многошаговых задач, имеющих множество состояний, приводят к необходимости отбора задач малой размерности либо использования сжатой информации. Последнее достигается с помощью методов анализа вариантов и переработки списка состояний.Для процессов с непрерывным временем динамическое программирование рассматривается как предельный вариант дискретной схемы решения. Получаемые при этом результаты практически совпадают с теми, которые получаются методами максимума Л. С. Понтрягина или Гамильтона-Якоби-Беллмана.Динамическое программирование применяется для решения задач, в которых поиск оптимума возможен при поэтапном подходе, например, распределение дефицитных капитальных вложений между новыми направлениями их использования; разработка правил управления спросом или запасами, устанавливающими момент пополнения запаса и размер пополняющего заказа; разработка принципов календарного планирования производства и выравнивания занятости в условиях колеблющегося спроса на продукцию; составление календарных планов текущего и капитального ремонтов оборудования и его замены; поиск кратчайших расстояний на транспортной сети; формирование последовательности развития коммерческой операции и т. д. 1.2 ПОСТАНОВКА ЗАДАЧИ ДИНАМИЧЕСКОГО ПРОГРАММИРОВАНИЯ Постановку задачи динамического программирования рассмотрим на примере инвестирования, связанного с распределением средств между предприятиями. В результате управления инвестициями система последовательно переводится из начального состояния S₀ в конечное S_n . Предположим, что управление можно разбить на n шагов и решение принимается последовательно на каждом шаге, а управление представляет собой совокупность n пошаговых управлений. На каждом шаге необходимо определить два типа переменных: переменную состояния системы S_k и переменную управления x_k . Переменная S_k определяет, в каких состояниях может оказаться система на рассматриваемом k-м шаге. В зависимости от состояния S на этом шаге можно применить некоторые управления, которые характеризуются переменной x_k , которые удовлетворяют определенным ограничениям и называются допустимыми.Допустим, X = (x₁ , x₂ , …, x_k , …, x_n ) – управление, переводящее систему из состояния S₀ в состояние S_n , a S_k – есть состояние системы на k-м шаге управления. Тогда последовательность состояний системы можно представить в виде графа, изображенного на рис. 1.x₁ x₂ x_k-1 x_k x_k+1 x_n S₀ → S₁ → ... → S_k-1 →S_k → ... → S_n Рисунок 1 – График состояний системы

Применение управляющего воздействия x_k на каждом шаге переводит систему в новое состояние S¹ (S, x_k ) и приносит некоторый результат W_k (S, x_k ). Для каждого возможного состояния на каждом шаге среди всех возможных управлений выбирается оптимальное управление х*_k , такое, чтобы результат, который достигается за шаги с k-го по последний n-й, оказался бы оптимальным. Числовая характеристика этого результата называется функцией Беллмана F_k (S) и зависит от номера шага k и состояния системы S.

Задача динамического программирования формулируется следующим образом: требуется определить такое управление Х*, переводящее систему из начального состояния S₀ в конечное состояние S_n , при котором целевая функция принимает наибольшее (наименьшее) значение F(S₀ , X*) → extr.Особенности математической модели динамического программирования заключаются в следующем:1) задача оптимизации формулируется как конечный многошаговый процесс управления;2) целевая функция (выигрыш) является аддитивной и равна сумме целевых функций каждого шага: F = ∑ F_k (S_k ₋₁ , x _k ) → extremum ;k =13) выбор управления х_k на каждом шаге зависит только от состояния системы к этому шагу S_k ₋₁ , и не влияет на предшествующие шаги (нет обратной связи);4) состояние системы S_k после каждого шага управления зависит только от предшествующего состояния системы S_k _-1 и этого управляющего воздействия х_k (отсутствие последействия) и может быть записано в виде уравнения состояния: S_k = f_k (S_k -1, х_k ), k = 1, n;5) на каждом шаге управление х_k зависит от конечного числа управляющих переменных, а состояние системы S_k зависит от конечного числа параметров;6) оптимальное управление представляет собой вектор X*, определяемый последовательностью оптимальных пошаговых управлений: X = (х*₁ , х*₂ , …, х*_k , …, х*_n ), число которых и определяет количество шагов задачи. 1.3 ПРИНЦИП ОПТИМАЛЬНОСТИ И МАТЕМАТИЧЕСКОЕ ОПИСАНИЕ ДИНАМИЧЕСКОГО ПРОЦЕССА УПРАВЛЕНИЯ В основе метода динамического программирования лежит принцип оптимальности, впервые сформулированный в 1953 г. американским математиком Р. Э. Беллманом: каково бы ни было состояние системы в результате какого-либо числа шагов, на ближайшем шаге нужно выбирать управление так, чтобы оно в совокупности с оптимальным управлением на всех последующих шагах приводило к оптимальному выигрышу на всех оставшихся шагах, включая выигрыш на данном шаге. При решении задачи на каждом шаге выбирается управление, которое должно привести к оптимальному выигрышу. Если считать все шаги независимыми, тогда оптимальным управлением будет то управление, которое обеспечит максимальный выигрыш именно на данном шаге. Однако, например, при покупке новой техники взамен устаревшей на ее приобретение затрачиваются определенные средства, поэтому доход от ее эксплуатации в начале может быть небольшой, а в следующие годы новая техника будет приносить больший доход. И наоборот, если принято решение оставить старую технику для получения дохода в текущем году, то в дальнейшем это приведет к значительным убыткам. Этот пример демонстрирует следующий факт: в многошаговых процессах управление на каждом конкретном шаге надо выбирать с учетом его будущих воздействий на весь процесс.Кроме того, при выборе управления на данном шаге следует учитывать возможные варианты состояния предыдущего шага. Например, при определении количества средств, вкладываемых в предприятие в i-м году, необходимо знать, сколько средств осталось в наличии к этому году и какой доход получен в предыдущем (i-1)-м году. Таким образом, при выборе шагового управления необходимо учитывать следующие требования: 1) возможные исходы предыдущего шага S_k _-1 ;2) влияние управления х_k на все оставшиеся до конца процесса шаги (n - k).В задачах динамического программирования первое требование учитывают, делая на каждом шаге условные предположения о возможных вариантах окончания предыдущего шага и проводя для каждого из вариантов условную оптимизацию. Выполнение второго требования обеспечивается тем, что в этих задачах условная оптимизация проводится от конца процесса к началу.Условная оптимизация. На первом этапе решения задачи, называемом условной оптимизацией, определяются функция Беллмана и оптимальные управления для всех возможных состояний на каждом шаге, начиная с последнего в соответствии с алгоритмом обратной прогонки. На последнем, n-м шаге, оптимальное управление – х*_n определяется функцией Беллмана: F(S) = max {W_n (S, x_n )}, в соответствии с которой максимум выбирается из всех возможных значений х_n , причем х_n ∈Х.Дальнейшие вычисления производятся согласно рекуррентному соотношению, связывающему функцию Беллмана на каждом шаге с этой же функцией, но вычисленной на предыдущем шаге. В общем виде это уравнение имеет вид: F_n (S) = max {W_n (S, x_n ) + F_k+1 (S¹ (S, x_k ))}, x_k ∈Х.Этот максимум (или минимум) определяется по всем возможным для k и S значениям переменной управления X.Безусловная оптимизация. После того, как функция Беллмана и соответствующие оптимальные управления найдены для всех шагов с n-го по первый, осуществляется второй этап решения задачи, называемый безусловной оптимизацией. Пользуясь тем, что на первом шаге (k = 1) состояние системы известно – это ее начальное состояние S_o , можно найти оптимальный результат за все n шагов и оптимальное управление на первом шаге x₁ , которое этот результат доставляет. После применения этого управления система перейдет в другое состояние S¹ (S,х*₁ ), зная которое, можно, пользуясь результатами условной оптимизации, найти оптимальное управление на втором шаге х*₂ , и так далее до последнего n-го шага. Вычислительную схему динамического программирования можно строить на сетевых моделях, а также по алгоритмам прямой прогонки (от начала) и обратной прогонки (от конца к началу). Рассмотрим примеры решения различных по своей природе задач, содержание которых требует выбора переменных состояния и управления.1.4 ОПТИМАЛЬНОЕ РАСПРЕДЕЛЕНИЕ ИНВЕСТИЦИЙ Требуется распределить имеющиеся В единиц средств среди n предприятий, доход g_i (x_i ) от которых, в зависимости от количества вложенных средств х_i , определяется матрицей (n*n), приведенной в табл. 1, так, чтобы суммарный доход со всех предприятий был бы максимальным. Таблица 1

x \ g_i	g₁	g₂	…	g_i	…	g_n
x₁	g₁ (x₁ )	g₂ (x₁ )	…	g_i (x₁ )	…	g_n (x₁ )
x₂	g₁ (x₂ )	g₂ (x₂ )	…	g_i (x₂ )	…	g_n (x₂ )
x_i	…	…	…	g_i (x_i )	…	…
x_n	g₁ (x_n )	g₂ (x_n )	…	…	…	g_n (x_n )

Запишем математическую модель задачи.Определить

X* = (х^* ₁ , х^* ₂ , …, х^* _i , …, х^* _n ), удовлетворяющий условиям

и обеспечивающий максимум целевой функцииF(X) = ∑x_i g_i ( x_i ) → maxОчевидно, эта задача может быть решена простым перебором всех возможных вариантов распределения В единиц средств по n предприятиям, например на сетевой модели. Однако решим ее более эффективным методом, который заключается в замене сложной многовариантной задачи многократным решением простых задач с малым количеством исследуемых вариантов.С этой целью разобьем процесс оптимизации на n шагов и будем на каждом k-м шаге оптимизировать инвестирование не всех предприятий, а только предприятий с k-го по n-е. При этом естественно считать, что в остальные предприятия (с первого по (k–1)-е тоже вкладываются средства, и поэтому на инвестирование предприятий с k-го по n-е остаются не все средства, а некоторая меньшая сумма С_k ≤ В. Эта величина и будет являться переменной состояния системы. Переменной управления на k-м шаге назовем величину х_k средств, вкладываемых в k-e предприятие. В качестве функции Беллмана F_k (C_k ) на k-м шаге можно выбрать максимально возможный доход, который можно получить с предприятий с k-го по n-е при условии, что на их инвестирование осталось С_k средств. Очевидно, что при вложении в k-e предприятие х_k средств будет получена прибыль g_k (x_k ), а система к (k+1)-му шагу перейдет в состояние S_k+1 и, следовательно, на инвестирование предприятий с (k+1)-го до n-го останется С_k+1 = (С_k – х_k ) средств.Таким образом, на первом шаге условной оптимизации при k = n функция Беллмана представляет собой прибыль только с n-го предприятия. При этом на его инвестирование может остаться количество средств С_n , 0 ≤ С_n ≤ В. Чтобы получить максимум прибыли с этого предприятия, можно вложить в него все эти средства, т. е. F_n (С_n ) = g_n (С_n ) и х_n = С_n .На каждом последующем шаге для вычисления функции Беллмана необходимо использовать результаты предыдущего шага. Пусть на k-м шаге для инвестирования предприятий с k-го по n-е осталось С_k средств (0 ≤ С_k ≤ В). Тогда от вложения в k-e предприятие х_k средств будет получена прибыль g_k (C_k ), а на инвестирование остальных предприятий (с k-го по n-е) останется С_k+1 = (С_k – х_k ) средств. Максимально возможный доход, который может быть получен с предприятий (с k-го по n-е), будет равен:F_k (C_k ) = max {g_k (x_k ) + F_k ₊₁ (с_k - x_k )} , k = 1, …, nМаксимум выражения достигается на некотором значении х^* _k , которое является оптимальным управлением на k-м шаге для состояния системы S_k . Действуя таким образом, можно определить функции Беллмана и оптимальные управления до шага k = 1.Значение функции Беллмана F₁ (c₁ ) представляет собой максимально возможный доход со всех предприятий, а значение х^* ₁ , на котором достигается максимум дохода, является оптимальным количеством средств, вложенных в первое предприятие. Далее на этапе безусловной оптимизации для всех последующих шагов вычисляется величина С_k = (С_k-1 – х_k-1 ) оптимальным управлением на k-м шаге является то значение х_k , которое обеспечивает максимум дохода при соответствующем состоянии системы S_k . 1.5 ВЫБОР ОПТИМАЛЬНОЙ СТРАТЕГИИ ОБНОВЛЕНИЯ ОБОРУДОВАНИЯ Важной экономической проблемой является своевременное обновление оборудования: автомобилей, станков, телевизоров, магнитол и т. п. Старение оборудования включает физический и моральный износ, в результате чего растут затраты на ремонт и обслуживание, снижается производительность труда и ликвидная стоимость. Задача заключается в определении оптимальных сроков замены старого оборудования. Критерием оптимальности являются доход от эксплуатации оборудования (задача максимизации) либо суммарные затраты на эксплуатацию в течение планируемого периода (задача минимизации).Предположим, что планируется эксплуатация оборудования в течение некоторого периода времени продолжительностью n лет. Оборудование имеет тенденцию с течением времени стареть и приносить все меньший доход r(t) (t – возраст оборудования). При этом есть возможность в начале любого года продать устаревшее оборудование за цену S(t), которая также зависит от возраста t, и купить новое оборудование за цену P.Под возрастом оборудования понимается период эксплуатации оборудования после последней замены, определенный в годах. Требуется найти оптимальный план замены оборудования с тем, чтобы суммарный доход за все n лет был бы максимальным, учитывая, что к началу эксплуатации возраст оборудования составлял t₀ лет.Исходными данными в задаче являются доход r(t) от эксплуатации в течение одного года оборудования возраста t лет, остаточная стоимость S(t), цена нового оборудования P и начальный возраст оборудования t₀ .Таблица 2

t	0	1	…	n
r	r(0)	r(1)	…	r(n)
S	S(0)	S(1)	…	S(n)

При составлении динамической модели выбора оптимальной стратегии обновления оборудования процесс замены рассматривается как n-шаговый, т. е. период эксплуатации разбивается на n-шагов.Выберем в качестве шага оптимизацию плана замены оборудования с k-го по n-й годы. Очевидно, что доход от эксплуатации оборудования за эти годы будет зависеть от возраста оборудования к началу рассматриваемого шага, т. е. k-го года.Поскольку процесс оптимизации ведется с последнего шага (k = n), то на k-м шаге неизвестно, в какие годы с первого по (k-1)-й должна осуществляться замена и, соответственно, неизвестен возраст оборудования к началу k-го года. Возраст оборудования, который определяет состояние системы, обозначим t. На величину t накладывается следующее ограничение:1 ≤ t ≤ t₀ + k – 1Это выражение свидетельствует о том, что t не может превышать возраст оборудования за (k–1)-й год его эксплуатации с учетом возраста к началу первого года, который составляет t₀ лет; и не может быть меньше единицы (этот возраст оборудование будет иметь к началу k-го года, если замена его произошла в начале предыдущего (k–1)-го года).Таким образом, переменная t в данной задаче является переменной состояния системы на k-м шаге. Переменной управления на k-м шаге является логическая переменная, которая может принимать одно из двух значений: сохранить (С) или заменить (З) оборудование в начале k-го года: x_k (t) = { С, если оборудование сохраняется { З, если оборудование заменяетсяФункцию Беллмана F_k (t) определяют как максимально возможный доход от эксплуатации оборудования за годы с k-го по n-й, если к началу k-го возраст оборудования составлял t лет. Применяя то или иное управление, система переходит в новое состояние. Так, например, если в начале k-го года оборудование сохраняется, то к началу (k + 1)-го года его возраст увеличится на единицу (состояние системы станет t+1), в случае замены старого оборудования новое достигнет к началу (k + 1)-го года возраста t = 1 год.На этой основе можно записать уравнение, которое позволяет рекуррентно вычислить функции Беллмана, опираясь на результаты предыдущего шага. Для каждого варианта управления доход определяется как сумма двух слагаемых: непосредственного результата управления и его последствий.Если в начале каждого года сохраняется оборудование, возраст которого t лет, то доход за этот год составит r(t). К началу (k+1)-го года возраст оборудования достигнет (t+1) и максимально возможный доход за оставшиеся годы (с (k+1)-го по n-й) составит F_k+1 (t+1). Если в начале k-го года принято решение о замене оборудования, то продается старое оборудование возраста t лет по цене S(t), приобретается новое за P единиц, а эксплуатация его в течение k-го года нового оборудования принесет прибыль r(0). К началу следующего года возраст оборудования составит 1 год и за все оставшиеся годы с (k+1)-го по n-й максимально возможный доход будет F_k+1 (1). Из двух возможных вариантов управления выбирается тот, который приносит максимальный доход. Функция F_k (t) вычисляется на каждом шаге управления для всех 1 ≤ t ≤ t₀ + k – 1. Управление при котором достигается максимум дохода, является оптимальным.Значения функции F_n (t), определяемые F_n-1 (t), F_n-2 (t) вплоть до F₁ (t). F₁ (t₀ ) представляют собой возможные доходы за все годы. Максимум дохода достигается при некотором управлении, применяя которое на первом году, мы определяем возраст оборудования к началу второго года. Для данного возраста оборудования выбирается управление, при котором достигается максимум дохода за годы со второго по n-й и так далее. В результате на этапе безусловной оптимизации определяются годы, в начале которых следует произвести замену оборудования.

2 РАСЧЕТНАЯ ЧАСТЬ

Построение оптимальной последовательности операций в коммерческой деятельности Пример Пусть на оптовую базу «Ларес» прибыло 10 машин с товаром для разгрузки и 8 машин для загрузки товаров, направляемых в магазины. Материально-ответственное лицо оптовой базы осуществляет оформление документов по операциям разгрузки или загрузки для одной машины, а затем переходит к обслуживанию другой машины. Известны затраты по выполнению каждой операции, которые показаны на ребрах графа (рис. 2).Издержки от операций обусловлены простоем транспорта, типом операции (прием или отправка товара) и не зависят от конкретной машины. Необходимо спланировать последовательность операций обоих видов таким образом, чтобы суммарные издержки по приему и отправке товаров для всех машин были минимальными.Решение: Из условия следует, что состояние экономической системы характеризуется двумя параметрами: количеством принятых и оформленных машин по разгрузке товара и количеством машин, отправленных с товаром в магазины. Поэтому решение будем искать на плоскости X0Y, на ограниченном прямыми прямоугольнике, который является областью допустимых состояний системы. Если по оси X отложить число (10) разгруженных машин, а по оси Y – число (8) загруженных товаром машин, то можно построить на плоскости граф состояний процесса, в котором каждая вершина характеризует состояние операции приема и отгрузки товара на оптовой базе. Ребра этого графа означают выполнение работы по приему или отправке товара на очередной машине. Каждому ребру можно сопоставить издержки, связанные с выполнением операции по разгрузке или загрузке машины.Точка S₀ определяет начало процесса, a S₁ – конечное состояние, соответствующее приему и отправке всех машин. Оптимизацию процесса будем производить с конечного состояния S₁ . Весь процесс разобьем на шаги, их количество k = n + m = 10 + 8 = 18. Каждый шаг представляет собой сечение графа состояний, проходящее через вершины (на рис. 2 сечения показаны косыми линиями).

К=18 К=17 К=16 К=15 К=14 К=13 К=12 К=11 К=10 К=9Рисунок 2 – Графическая схема связи операцийI этап. Условная оптимизация. 1-й шаг. k = 1. На первом шаге, с задаваемым сечением А₁ В₁ , из состояний А₁ и B₁ возможен только один вариант перехода в конечное состояние S₁ . Поэтому в вершинах А₁ и B₁ записываем соответственно издержки 13 и 10. Ребра A₁ S₁ и B₁ S_l обозначаем стрелкой, направленной в вершину S₁ , как показано на рис. 3.

Рисунок 3 – Сетевая модель операции, шаг 1 2-й шаг. k = 2. Второй шаг оптимизации задается сечением по вершинам А₂ , В₂ , C₁ . Из состояний А₂ и C₁ возможен единственный переход в вершины А₁ и B₁ соответственно, поэтому в вершинах А₂ и C₁ записываем суммарные издержки 29 и 28 на первых двух шагах перехода в конечное состояние S₁ . Из вершины В₂ возможны два варианта перехода: в вершину А₁ или вершину B₁ . При переходе В₂ → А₁ сумма издержек составляет 11 + 13 = 24, на переходе В₂ → В₁ сумма составляет 15 + 10 = 25. Из двух вариантов суммарных издержек выбираем наименьшую (24) и обозначаем стрелкой условно оптимальный переход В₂ → А₁ , как показано на рис. 4.

Рисунок 4 – Сетевая модель операции, шаг 2 3-й шаг. k = 3. На третьем шаге сечение проходит через вершины А₃ , В₃ , С₂ , D₁ . Из вершин А₃ и D₁ возможен единственный переход в вершины А₂ и С₁ соответственно. Суммарные издержки для состояния D₁ равны 28 + 19 = 47; для состояния А₃ : 29 + 20 = 49. Из вершины В₃ возможны два варианта перехода: в вершину А₂ издержки равны 29 + 9 = 38; в вершину В₂ – 13 + 24 = 37 . Для вершины С₂ возможен переход в вершину В₂ (21 + 24 = 45) и в вершину С₁ (18 + 28 = 46). Выбираем для вершин В₃ и С₂ наименьшие суммарные издержки и обозначаем стрелкой условно оптимальный переход, как показано на рис. 5.

Рисунок 5 – Сетевая модель операции, шаг 3 4-й шаг. k = 4. Четвертый шаг оптимизации задается сечением по вершинам А₄ , В₄ , C₃ , D₂ , Е₁ . Из состояний А₄ и Е₁ возможен единственный переход в вершины А₃ и D₁ соответственно, поэтому в вершинах А₄ и Е₁ записываем суммарные издержки:А₄ А₃ : 18 + 49 = 67 Е₁ D₁ : 18 + 47 = 65. Вершина В₄ : В₄ А₃ : 10 + 49 =59 В₄ В₃ : 13 + 37 = 50. Вершина С₃ : С₃ В₃ : 20 + 37 =57 С₃ С₂ : 21 + 45 = 66.Вершина D₂ : D₂ С₂ : 19 + 45 =64 D₂ D₁ : 11 + 47 = 58.

Рисунок 6 – Сетевая модель операции, шаг 4 5-й шаг. k = 5. На пятом шаге сечение проходит через вершины А₅ , В₅ , С₄ , D₃ , Е₂ , F₁ . Из вершин А₅ и F₁ возможен единственный переход в вершины А₄ и Е₁ соответственно:А₅ А₄ : 15 + 67 = 82 F ₁ Е₁ : 16 + 65 = 81. Вершина В₅ : В₅ А₄ : 13 + 67 =80 В₅ В₄ : 12 + 50 = 62. Вершина С₄ : С₄ В₄ : 18 + 50 = 68 С₄ С₃ : 12 + 57 = 69.Вершина D₃ : D₃ С₃ : 18 + 57 = 75 D₃ D₂ : 11 + 58 = 69. Вершина Е₂ : Е₂ D₂ : 16 + 58 = 74 Е₂ Е₁ : 15 + 65 = 80.

Рисунок 7 – Сетевая модель операции, шаг 5 6-й шаг. k = 6. Шестой шаг оптимизации задается сечением по вершинам А₆ , В₆ , C₅ , D₄ , Е₃ , F₂ , G₁ . Из состояний А₆ и G₁ возможен единственный переход в вершины А₅ и F₁ соответственно, поэтому в вершинах А₆ и G₁ записываем суммарные издержки:А₆ А₅ : 13 + 82 = 95 G ₁ F ₁ : 10 + 81 = 91. Вершина В₆ : В₆ А₅ : 14 + 82 =96 В ₆ В ₅ : 1 5 + 62 = 77 . Вершина С₅ : С₅ В₅ : 10 + 62 = 72 С₅ С₄ : 12 + 68 = 80.Вершина D₄ : D₄ С₄ : 16 + 68 = 84 D₄ D₃ : 12 + 69 = 81. Вершина Е₃ : Е ₃ D ₃ : 1 5 + 69 = 8 4 Е₃ Е₂ : 14 + 74 = 88.Вершина F₂ : F ₂ Е ₂ : 1 5 + 74 = 89 F₂ F₁ : 12 + 81 = 93.

Рисунок 8 – Сетевая модель операции, шаг 6 7-й шаг. k = 7. Сечение А₇ , В₇ , C₆ , D₅ , Е₄ , F₃ , G₂ , Н₁ . Вершина А₇ : А₇ А₆ : 18 + 95 = 113 Вершина Н₁ : Н₁ G ₁ : 11 + 91 = 102 Вершина В₇ : В₇ А₆ : 15 + 95 = 110 В₇ В₆ : 18 + 77 = 95. Вершина С₆ : С₆ В₆ : 9 + 77 = 86 С₆ С₅ : 13 + 72 = 85. Вершина D₅ : D₅ С₅ : 15 + 72 = 87 D₅ D₄ : 10 + 81 = 91.Вершина Е₄ : Е₄ D₄ : 15 + 81 = 96 Е₄ Е₃ : 14 + 84 = 98.Вершина F₃ : F₃ Е₃ : 16 + 84 = 100F ₃ F ₂ : 10 + 8 9 = 9 9. Вершина G₂ : G₂ F₂ : 14 + 89 = 103G ₂ G ₁ : 11 + 91 = 102. 8-й шаг. k = 8. Сечение А₈ , В₈ , C₇ , D₆ , Е₅ , F₄ , G₃ , Н₂ , I₁ . Вершина А₈ : А₈ А₇ : 16 + 113 = 129 Вершина I₁ : I ₁ Н₁ : 12 + 102 = 114 Вершина В₈ : В₈ А₇ : 14 + 113 = 127 В₈ В₇ : 20 + 95 = 115. Вершина С₇ : С₇ В₇ : 15 + 95 = 110 С₇ С₆ : 11 + 85 = 96. Вершина D₆ : D₆ С₆ : 13 + 85 = 98 D₆ D₅ : 13 + 87 = 100.Вершина Е₅ : Е₅ D₅ : 13 + 87 = 100 Е₅ Е₄ : 10 + 96 = 106.Вершина F₄ : F ₄ Е₄ : 14 + 96 = 110 F₄ F₃ : 18 + 99 = 117.Вершина G₃ : G ₃ F ₃ : 12 + 99 = 111 G₃ G₂ : 18 + 102 = 120.Вершина Н₂ : Н₂ G₂ : 17 + 102 = 119Н₂ Н₁ : 12 + 102 = 114. 9-й шаг. k = 9. Сечение А₉ , В₉ , C₈ , D₇ , Е₆ , F₅ , G₄ , Н₃ , I₂ . Вершина А₉ : А₉ А₈ : 10 + 129 = 139 Вершина В₉ : В₉ А₈ : 13 + 129 = 142 В₉ В₈ : 10 + 115 = 125. Вершина С₈ : С₈ В₈ : 16 + 115 = 131 С₈ С₇ : 9 + 96 = 105. Вершина D₇ : D₇ С₇ : 14 + 96 = 110 D₇ D₆ : 14 + 98 = 112.Вершина Е₆ : Е₆ D₆ : 15 + 98 = 113 Е₆ Е₅ : 15 + 100 = 115.Вершина F₅ : F ₅ Е₅ : 12 + 100 = 112 F₅ F₄ : 16 + 110 = 126.Вершина G₄ : G₄ F₄ : 19 + 110 = 129G ₄ G ₃ : 9 + 111 = 120. Вершина Н₃ : Н₃ G₃ : 16 + 111 = 127Н₃ Н₂ : 10 + 114 = 124. Вершина I₂ : I₂ Н₂ : 11 + 114 = 125I ₂ I ₁ : 8 + 114 = 122. 10-й шаг. k = 10. Сечение А₁₀ , В₁₀ , C₉ , D₈ , Е₇ , F₆ , G₅ , Н₄ , I₃ . Вершина А₁₀ : А₁₀ А₉ : 14 + 139 = 153 Вершина В₁₀ : В₁₀ А₉ : 12 + 139 = 151 В₁₀ В₉ : 10 + 125 = 135. Вершина С₉ : С₉ В₉ : 15 + 125 = 140 С₉ С₈ : 18 + 105 = 123. Вершина D₈ : D₈ С₈ : 13 + 105 = 118 D₈ D₇ : 15 + 110 = 125.Вершина Е₇ : Е₇ D₇ : 14 + 110 = 124 Е₇ Е₆ : 13 + 113 = 126.Вершина F₆ : F ₆ Е₆ : 12 + 113 = 125 F₆ F₅ : 19 + 112 = 131.Вершина G₅ : G ₅ F ₅ : 13 + 112 = 125 G₅ G₄ : 11 + 120 = 131.Вершина Н₄ : Н₄ G ₄ : 16 + 120 = 136 Н₄ Н₃ : 15 + 124 = 139.Вершина I₃ : I ₃ Н₃ : 11 + 124 = 135 I₃ I₂ : 15 + 122 = 137. 11-й шаг. k = 11. Сечение В₁₁ , C₁₀ , D₉ , Е₈ , F₇ , G₆ , Н₅ , I₄ . Вершина В₁₁ : В₁₁ А₁₀ : 10 + 153 = 163 В₁₁ В₁₀ : 9 + 135 = 144. Вершина С₁₀ : С₁₀ В₁₀ : 10 + 135 = 145 С₁₀ С₉ : 10 + 123 = 133. Вершина D₉ : D₉ С₉ : 13 + 123 = 136 D₉ D₈ : 14 + 118 = 132. Вершина Е₈ : Е₈ D₈ : 11 + 118 = 129 Е₈ Е₇ : 14 + 124 = 138.Вершина F₇ : F ₇ Е₇ : 10 + 124 = 134 F₇ F₆ : 18 + 125 = 143.Вершина G₆ : G ₆ F ₆ : 11 + 125 = 136 G₆ G₅ : 18 + 125 = 143.Вершина Н₅ : Н₅ G ₅ : 15 + 125 = 140 Н₅ Н₄ : 19 + 136 = 155.Вершина I₄ : I₄ Н₄ : 16 + 136 = 152I ₄ I ₃ : 14 + 135 = 149. 12-й шаг. k = 12. Сечение C₁₁ , D₁₀ , Е₉ , F₈ , G₇ , Н₆ , I₅ . Вершина С₁₁ : С₁₁ В₁₁ : 11 + 144 = 155 С₁₁ С₁₀ : 8 + 133 = 141. Вершина D₁₀ : D₁₀ С₁₀ : 15 + 133 = 148 D₁₀ D₉ : 13 + 132 = 145. Вершина Е₉ : Е₉ D₉ : 15 + 132 = 147 Е₉ Е₈ : 14 + 124 = 138. Вершина F₈ : F ₈ Е₈ : 9 + 129 = 141 F₈ F₇ : 21 + 134 = 155.Вершина G₇ : G ₇ F ₇ : 12 + 134 = 146 G₇ G₆ : 13 + 136 = 149.Вершина Н₆ : Н₆ G ₆ : 15 + 136 = 151 Н₆ Н₅ : 16 + 140 = 156.Вершина I₅ : I ₅ Н₅ : 11 + 140 = 151 I₅ I₄ : 9 + 149 = 158. 13-й шаг. k = 13. Сечение D₁₁ , Е₁₀ , F₉ , G₈ , Н₇ , I₆ . Вершина D₁₁ : D₁₁ С₁₁ : 11 + 141 = 152 D₁₁ D₁₀ : 12 + 145 = 157.Вершина Е₁₀ : Е₁₀ D₁₀ : 16 + 145 = 161 Е₁₀ Е₉ : 13 + 141 = 154. Вершина F₉ : F ₉ Е₉ : 11 + 141 = 152 F₉ F₈ : 20 + 138 = 158.Вершина G₈ : G ₈ F ₈ : 14 + 138 = 152 G₈ G₇ : 12 + 146 = 158.Вершина Н₇ : Н₇ G ₇ : 14 + 146 = 160 Н₇ Н₆ : 13 + 151 = 164.Вершина I₆ : I ₆ Н₆ : 10 + 151 = 161 I₆ I₅ : 17 + 151 = 168. 14-й шаг. k = 14. Сечение Е₁₁ , F₁₀ , G₉ , Н₈ , I₇ . Вершина Е₁₁ : Е₁₁ D₁₁ : 9 + 152 = 161 Е₁₁ Е₁₀ : 11 + 154 = 165.Вершина F₁₀ : F ₁₀ Е₁₀ : 15 + 154 = 169 F₁₀ F₉ : 19 + 152 = 171.Вершина G₉ : G₉ F₉ : 13 + 152 = 165G ₉ G ₈ : 12 + 152 = 164. Вершина Н₈ : Н₈ G ₈ : 13 + 152 = 165 Н₈ Н₇ : 15 + 160 = 175.Вершина I₇ : I ₇ Н₇ : 9 + 160 = 169 I₇ I₆ : 16 + 161 = 177. 15-й шаг. k = 15. Сечение F₁₁ , G₁₀ , Н₉ , I₈ . Вершина F₁₁ : F ₁₁ Е₁₁ : 16 + 161 = 177 F₁₁ F₁₀ : 18 + 169 = 187.Вершина G₁₀ : G₁₀ F₁₀ : 10 + 169 = 179G ₁₀ G ₉ : 10 + 164 = 174. Вершина Н₉ : Н₉ G ₉ : 9 + 164 = 173 Н₉ Н₈ : 12 + 165 = 177.Вершина I₈ : I ₈ Н₈ : 13 + 165 = 178 I₈ I₇ : 14 + 169 = 183. 16-й шаг. k = 16. Сечение G₁₁ , Н₁₀ , I₉ . Вершина G₁₁ : G₁₁ F₁₁ : 9 + 177 = 186G ₁₁ G ₁₀ : 10 + 174 = 184. Вершина Н₁₀ : Н₁₀ G₁₀ : 10 + 174 = 184Н₁₀ Н₉ : 10 + 173 = 183. Вершина I₉ : I ₉ Н₉ : 11 + 173 = 184 I₉ I₈ : 10 + 178 = 188. 17-й шаг. k = 17. Сечение Н₁₁ , I₁₀ . Вершина Н₁₁ : Н₁₁ G₁₁ : 10 + 184 = 194Н₁₁ Н₁₀ : 9 + 183 = 192. Вершина I₁₀ : I ₁₀ Н₁₀ : 9 + 183 = 192 I₁₀ I₉ : 15 + 184 = 199. 18-й шаг. k = 18. Вершина S₀ : S₀ Н₁₁ : 10 + 192 = 202 S₀ I₁₀ : 13 + 192 = 205. Минимально возможные суммарные издержки по обслуживанию всех 18 машин на оптовой базе «Ларес» составляют 202 усл. ед.II этап. Безусловная оптимизация. Определяем оптимальную траекторию на исходном сетевом графе, просматривая результаты всех шагов в обратном порядке, учитывая, что выбор некоторого управления на k-м шаге приводит к тому, что состояние на (k-1)-м шаге становится определенным.

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

Рисунок 9 – Оптимальная последовательность операцийМинимальные издержки F_min соответствуют следующему оптимальному пути на графе:(S₀ → H₁₁ → H₁₀ → H₉ → G₉ → G₈ → F₈ → E₈ → D₈ → C₈ → C₇ → C₆ → → C₅ → B₅ → B₄ → B₃ → B₂ → A₁ → S₁ ) иравны: F_min = 10 + 9 + 10 + 9 + 12 + 14 + 9 + 11 + 13 + 9 + 11 + 13 + 10 + 12 + 13 + + 13 + 11 + 13 = 202 усл. ед. Таким образом, в соответствии с решением оптимальное управление процессом разгрузки и загрузки машин товаром состоит в следующем: на первом шаге следует оформить документы по загрузке одной машины, на втором – по разгрузке двух машин, затем по загрузке одной машины; далее обслуживать одну машину по разгрузке товара, четыре машины по загрузке, три машины по разгрузке, одну машину по загрузке; в последнюю очередь оформить документы по разгрузке трех машин, по загрузке одной машины и разгрузить последнюю машину.

ЗАКЛЮЧЕНИЕ

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

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

СПИСОК ИСПОЛЬЗОВАННЫХ ИСТОЧНИКОВ

1 Фомин Г.П. Математические методы и модели в коммерческой деятельности: Учебник. – М.: Финансы и статистика, 2001.- 544 с.

2 Ломкова Е. Н., Эпов А. А. Экономико-математические модели управления производством (теоретические аспекты): Учеб. пособие. – Волгоград: ВолгГТУ, 2005. – 67 с.3 Холод Н. И., Кузнецов А. В., Жихар Я. Н. и др.; под общ. ред. Кузнецова А. В. Экономико-математические методы и модели: Учеб. пособие. –Мн.: БГЭУ, 2000. – 412 с.4 Шикин Е. В., Чхартищвили А. Г. Математические методы и модели в управлении: Учеб. пособие. – 2-е издание, испр. – М.: Дело, 2002. – 440 с.