Общие понятия динамического программирования

↑

▷ Содержание

⇐ ПредыдущаяСтр 7 из 10Следующая ⇒

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

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

Обозначим через х _k, управление на k -м шаге . Переменные х _k, удовлетворяют некоторым ограничениям и в этом смысле называются допустимыми (х _k может быть числом, точкой в n -мерном пространстве, качественным признаком).

Пусть  - управление, переводящее систему s из состояния s₀ в состояние . Обозначим через s_k состояние системы после k -го шага управления. Получаем последовательность состояний  которую изобразим кружками (рис. 5).

Рис. 5

Показатель эффективности рассматриваемой управляемой операции - целевая функция - зависит от начального состояния и управления:

                                                  (26)

Сделаем несколько предположений.

1. Состояние s_k системы в конце k -го шага зависит только от предшествующего состояния s_k-1 и управления на k -м шаге х _k, (и не зависит от предшествующих состояний и управлений). Это требование называется “отсутствием последействия”. Сформулированное положение записывается в виде уравнений

которые называются уравнениями состояний.

2. Целевая функция (26) является аддитивной от показателя эффективности каждого шага. Обозначим показатель эффективности k -го шага через тогда

                                          (27)

Задача пошаговой оптимизации (задача ДП) формулируется так: определить такое допустимое управление х, переводящее систему s из состояния в s₀ в состояние , при котором целевая функция (27) принимает наибольшее (наименьшее) значение.

Выделим особенности модели ДП:

1. Задача оптимизации интерпретируется как n -шаговый процесс управления.

2. Целевая функция равна сумме целевых функций каждого шага.

3. Выбор управления на k -м шаге зависит только от состояния системы к этому шагу, не влияет на предшествующие шаги (нет обратной связи).

4. Состояние s_k после k -го шага управления зависит только от предшествующего состояния s_{k - 1} и управления х _k (отсутствие последействия).

5. На каждом шаге управление х _k, зависит от конечного числа управляющих переменных, а состояние s_k - от конечного числа параметров.

Пример решения задачи

Планируется деятельность четырех промышленных предприятий (системы) на очередной год. Начальные средства: s₀ = 5 усл. ед. размеры вложения в каждое предприятие кратны 1 усл. ед. средства х, выделенные k -му предприятию (k =1, 2, 3, 4), приносят в конце года прибыль . Функции  заданы таблично (табл. 8). Принято считать, что:

а) прибыль  не зависит от вложения средств в другие предприятия;

б) прибыль от каждого предприятия выражается в одних условных единицах;

в) суммарная прибыль равна сумме прибылей, полученных от каждого предприятия.

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

Таблица 8

Решение. Обозначим через х _k количество средств, выделенных k -му предприятию (нумерацию предприятий 1, 2, 3, 4 сохраняем в процессе решения неизменной.)

Суммарная прибыль равна

Переменные х удовлетворяют ограничениям:

Требуется найти переменные х₁, х₂, х₃, х₄, удовлетворяющие системе ограничений и обращающие в максимум функцию.

Особенности модели. Ограничения линейные, но переменные целочисленные, а функции  заданы таблично, поэтому нельзя применить методы целочисленного линейного программирования.

Схема решения задачи методом ДП имеет следующий вид: процесс решения распределения средств s₀=5 можно рассматривать как 4-шаговый, номер шага совпадет с номером предприятия; выбор переменных  - управление соответственно на i, ii, iii, iv шагах. - конечное состояние процесса распределения - равно нулю, так как все средства должны быть вложены в производство, =0. схема распределения показана на рис. 6.

Уравнения состояний в данной задаче имеют вид:

где s_k - параметр состояния - количество средств, оставшихся после k -го шага, т.е. средства, которые остается распределить между оставшимися 4 - k предприятиями.

Рис. 6

Введем в рассмотрение функцию  - условную оптимальную прибыль, полученную от k-го,..., 4-го предприятий, если между ними распределялись оптимальным образом средства . Допустимые управления на k -м шаге удовлетворяют условию:  (либо k -му предприятию ничего не выделяем, х _k =0, либо не больше того, что имеем к k -му шагу, x_k≤ s_k-1 .

Уравнения имеют вид:

                          (a)

                               (б)

                                   (в)

                                                 (г)

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

iv шаг. В таблице 8   прибыли монотонно возрастают, поэтому все средства, оставшиеся к iv шагу, следует вложить в 4-е предприятие. При этом для возможных значений s₃=0, 1,..., 5 получим:

 и

iii шаг. Делаем все предположения относительно остатка средств s₂ к iii шагу (т.е. после выбора х₁ и х₂). s₂ может принимать значения 0, 1, 2, 3, 4, 5. В зависимости от этого выбираем  находим  и сравниваем для разных х₃ при фиксированном s₂ значения суммы . Для каждого s₂ наибольшее из этих значений есть - условная оптимальная прибыль, полученная при оптимальном распределении средств s₂ между 3-м и 4-м предприятиями.

ii шаг. Условная оптимизация, согласно уравнению (в), проведена в таблице 9 при k=2.

i шаг. Условная оптимизация (уравнение (г) проведена в табл. 9 при k=1 для s₀=5. поясним решение подробно: если х=0, то s₁=5, прибыль, полученная от четырех предприятий при условии, что s₁=5 ед. средств между оставшимися тремя предприятиями будут распределены оптимально, равна . Если х₁=1, то s₂=4. Суммарная прибыль при условии, что s₂=4 ед. средств между оставшимися тремя предприятиями будут распределены оптимально, равна . Аналогично при  и ;

при х₁=3, s₂= 2 и ;

при х₁=4, s₂= 1 и ;

при х₁=5, s₂= 0 и .

сравнивая числа, получим усл. ед. =z_max при .

Максимум суммарной прибыли равен 24 усл. ед. средств при условии, что 1-му предприятию выделено 1 усл. ед.; 2-му предприятию - 2 усл. ед.; 3-му предприятию - 1 усл. ед.; 4-му предприятию - 1 усл.ед.

Таблица 9

s k-1	xk	sk	k=3			k=2			k=1
1	2	3	4	5	6	7	8	9	10	11	12
0	0	0	0	0	0	0	0	0	0	0	0
1	0	1	0+1=1			0+4=4			0+6=6	8	1
	1	0	3+1=3	4	0	6+0=6	6	1	8+0=8
2	0	2	0+6=6			0+7=7			0+10=10
	1	1	3+4=4	7	1	6+4=10	10	1	8+6=14	14	1
	2	0	4+0=4			9+0=9			10+0=10
	0	3	0+8=8			0+9=9			0+13=13
3	1	2	3+6=9	9	1	6+7=13	13	1	8+10=18	18	1
	2	1	4+4=8			9+4=13		2	10+6=16

СЕТЕВАЯ МОДЕЛЬ

Сетевая модель – план выполнения некоторого комплекса взаимосвязанных работ, заданного в специфической форме сети, графическое изображение которого называется сетевым графиком.

Событие – момент завершения какого-либо процесса, отражающий отдельный этап выполнения проекта.

Порядок построения сетевого графика.

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

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

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

4. Любые два события должны быть непосредственно связаны не более чем одной работой-стрелкой.

5. В сети рекомендуется иметь одно исходное и одно завершающее событие.

Пут ь – любая последовательность работ, в которой конечное событие каждой работы совпадает с начальным событием следующей за ней работы.

Критический путь – наиболее продолжительный полный путь в сетевом графике.

Временные параметры сетевых графиков

Оптимизация сетевого графика – процесс улучшения организации выполнения комплекса работ с учетом срока его выполнения.

Частная оптимизация – минимизация времени выполнения комплекса работ при заданной стоимости, минимизация стоимости комплекса работ при заданном времени выполнения проекта.

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

Пример решения задачи

Оптимизировать сетевой график, изображенный на рис. 7, на котором указаны максимально возможные продолжительности работ (в сутках). Необходимые для оптимизации исходные данные представлены в таблице.

Таблица 8

Решение. Исходный для оптимизации план (рис.7) имеет максимальную продолжительность работ  и соответственно минимальную стоимость с=300 (усл. руб.). Найдем все полные пути сетевого графика.

Рис. 7

их четыре:

l₁  продолжительностью t(l₁)=89 (суток);

l₂  продолжительностъю t_кр= t(l₂)=99 (суток);

l₃ продолжительностью t(l₃)=50(сугок);

l₄ продолжительностью t(l₄)=50 (сугок).

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

Рис. 8.

i шаг. Уменьшить продолжительность выполнения комплекса можно, как известно, только за счет сокращения продолжительности работ критического пути t_кр=t(l₂). Из работ критического пути l₂ наименьший коэффициент затрат на ускорение h(i,j) имеет работа (3,4): h_min(i,j)= min{h (0, 1); h (1,.3); h (3, 4); h (4, б); h (б, 7); h (7, 8)}= min{6; 8; 2; 4; 5; 9}=2, т.е. h_min(i,j)= h (3, 4)=2. продолжительность работы t(3,4) можно сокращать не более чем на 10 суток. при этом изменится длина только критического пути (с 99 до 89 суток) - l₂ единственного из четырех путей, проходящего через работу (3,4), а стоимость проекта за счет ускорения работы (3,4) возрастет до 320 (усл. руб.). итак, на 1 шаге:

, где 89≤t≤99;

новые длины путей равны  

ii шаг. Теперь мы имеем два критических пути l₁ и l₂ и сократить срок выполнения проекта можно за счет одновременного сокращения их продолжительности. Сократить одновременно t(l₁) и t(l₂) можно, уменьшив продолжительность работ, лежащих на этих путях: либо t(0, 1), либо t(6,7), либо t(7, 6). останавливаемся на t(6, 7), поскольку при этом обеспечивается минимум затрат на ускорение работы:

Продолжительность работы t(6,7), можно уменьшить не более на 5 суток. На эту величину уменьшатся длины критических путей t(l₁) и t(l₂), а следовательно, и срок выполнения проекта  При этом стоимость проекта увеличится с 320 до 345 (усл. руб.). итак, на ii шаге:

где 84≤t≤89;

Продолжая аналогичным образом сокращать продолжительность работ, получим

iii шаг.

Сокращая продолжительностъ работы t(0, 1) до 10 суток, найдем

где 74≤t≤84

iv шаг.

 Сокращая продолжительность работы t(1, 3) до 5 суток, найдем

 где 69≤t≤74

v шаг. сокращая продолжительность работы t(7, 8) до 5 суток, найдем (учитывая, что h (7, 8)=9)

 где 64≤t≤69

vi шаг. Теперь несокращенными остались продолжительности трех критических работ: t(3, 5) и t(5, 6) критического пути l₁, каждую из которых можно сократить до 5 суток, и t(4, 6) критического пути l₂, которую можно сократить до 10 суток. Сокращение какой-либо одной из названных величин не приведет к сокращению продолжительности выполнения проекта, ибо при этом сократится лишь один из двух путей, а длина несокращенного пути, который станет единственным критическим путем, не изменится. Поэтому, последовательно сокращая t(4, 6) и t(5, 6) до 5 суток (с учетом времени сокращения продолжительности работ), найдем (теперь коэффициент затрат на ускорение работ равен

 где 59≤t≤64;

vii шаг. Продолжительность работы t(4, 6) можно сократить еще до 5 суток и на тот же срок можно сократить t (3, 5) (иначе срок выполнения проекта не изменится). Полагая, что , найдем

 где 54≤t≤59

График оптимальной зависимости стоимости проекта с(t) от продолжительности его выполнения показан на рис. 9 с помощью этого графика можно, с одной стороны, оценить минимальную стоимость проекта при любом возможном сроке его выполнения, а с другой стороны - найти предельную продолжительность выполнения проекта при заданной его стоимости. Например, при продолжительности проекта t=79 (суток) минимальная стоимость выполнения рассматриваемого комплекса составит 375 (усл. руб.), а при стоимости выполнения комплекса, например, 540 (усл. руб.) предельная продолжительность проекта составит 55 (суток). С помощью функции с(t) можно оценить дополнительные затраты, связанные с сокращением сроков завершения комплекса. так, сокращение продолжительности проекта с 79 до 55 суток потребует дополнительных затрат 540-375=165 (усл. руб.).

Рис. 9

МНОГОКРИТЕРИАЛЬНЫЕ ЗАДАЧИ

Познавательные статьи:



Алгоритмические операторы Matlab

Конструирование и порядок расчёта дорожной одежды

Исследования учёных: почему помогают молитвы?

Почему терпят неудачу многие предприниматели?