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

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

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

Реализацию проекта удобно представлять в виде графа, который задается множеством вершин или узлов и множеством дуг или ребер. Каждая дуга задается парой вершин. Сетью называется граф, каждой дуге которого поставлено в соответствие некоторое неотрицательное число. Сетевым графиком проекта называют наглядное представление проекта в виде сети. Дуги этой сети являются ориентированными, т.е. для каждой указаны начало и конец, и представляют работы; вершины (их называют событиями) представляют последовательность выполнения работ. Ни одна работа, представленная дугой, выходящей из некоторой вершины, не может начинаться прежде завершения всех работ, представленных дугами, входящими в данную вершину. Каждую пару событий должна соединять не более чем одна работа. В сетевом графике должно быть одно начальное и одно конечное событие. Для выполнения перечисленных требований допустимо введение фиктивных работ (работ нулевой продолжительности, не требующих затраты каких-либо ресурсов). Начальному событию присваивается номер 1. Чтобы пронумеровать остальные события, нужно для каждого события найти величину максимального числа дуг в путях, соединяющих данное событие с начальным. События нумеруются по возрастанию этой величины. Если для некоторого числа событий указанная величина одинакова, то эти события нумеруются в произвольном порядке. После построения графа можно вычислить необходимые затраты времени (или ресурсов) на реализацию проекта. При этом удобно использовать метод динамического программирования, начиная с начального состояния и последовательно вычисляя наиболее ранние сроки наступления событий вплоть до конечного. Цепочка событий, т.е. последовательность работ (дуг), сдвиг начала которых приводит к увеличению общего времени выполнения проекта, называется критическим путем.

Пример 7.5. Перечень работ по строительству коттеджа и их продолжительности приведены в табл. 7.10. Построить сетевой график выполнения комплекса работ и определить время реализации проекта.

Приступая к построению сетевого графика (рис. 7.1), замечаем, что работа а не опирается ни на какую работу, поэтому она изобразится дугой, выходящей из события 1, означающего исходный момент, с которого начинается выполнение рассматриваемого комплекса работ. На работу а опираются работы аг, аз, ал поэтому дуги, соответствующие этим работам на сетевом графике, будут следовать непосредственно за дугой а от события 2, означающего момент окончания работы а и начало работ аг, аз, ал. На работу ал опирается работа а$, а на аз и as — работа ав, что и отражено на сетевом графике следующими друг за другом соответствующими дугами. Работа ап опирается на работы агнйь, поэтому дуга ап исходит из события номер 5, означающего момент, к которому завершены обе эти работы. Дуга ап соответствует последней работе, а конечное ее событие номер 6 означает момент завершения работ всего рассматриваемого комплекса.

по строительству коттеджа и их продолжительности

Источник

5.3. Динамическое программирование при моделировании в сетях.

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

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

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

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

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

Характеризуя динамическое программирование, как набор математических процедур для оптимального управления дискретной системой, в общем виде задачу оптимального управления можно сформулировать следующим образом. В дискретные моменты времени t = 1, 2. N система находится в одном из множеств s_i состояний, характеризуемых вектором состояния x ( t ) . Переход между последовательными состояниями осуществляется с помощью вектора управления u ( t ) по закону:

x ( t ) = g ( t ) (x ( t ) , u ( t ) ) ; t = 1, 2. N

Управления u ( t ) выбираются из множества допустимых управлений и образуют последовательность допустимых управлений u (0) ,u (1) ,…,u ( N ) . Последовательность допустимых управлений при заданном начальном состоянии х (0) определяет траекторию системы х (0) ,х (1) ,х (2) ,…,х ( N ) .

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

.

Задачa оптимального управления заключается в нахождении среди множества последовательностей управления такой, которая достигает минимального значения F. Такая последовательность называется оптимальной последовательностью управлений и определяет оптимальную траекторию.

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

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

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

Источник

3 Пример построения сетевого графика и расчета резервов времени

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

Продолжительность, дни

Определение объема работы

Выбор проекта реконструкции

Утверждение сметы вышестоящей организацией

Составление договора с подрядчиком

Сообщение заказчику об открытии счета в банке

Экономическое обоснование проекта

Привязка проекта к площади предприятия

Рассчитываем ранние и поздние сроки наступления событий:

(1) = 0

(2) = 0+5 = 5

(3) = 5+10 = 15

(4) = 15+3 = 18

(5) = 15+2 = 17

(6) = 5+5 = 10

(7) = 10+4 = 14

(8) =(14+5;18+3;15+5;17+1)=(19;21;20;18)=21

(9) = 21+60 = 81

2) Поздние допустимые сроки:

(9) =(9) = 81

(8) = 81-60 = 21

(7) = 21-5 = 16

(6) = 16-4 = 12

(5) = 21-1 = 20

(4) = 21-3 = 18

(3) = (18-3; 21-5; 20-2) = (15; 16;18) = 15

(2) =(12-5; 15-10) = (7;5) = 5

(1) = 5-5 = 0

Критический путь содержит 5 работ: (1,2); (2,3); (3,4); (4,8); (8,9).

Минимальный срок: 5+10+3+3+60 = 81 день.

Таблица резервов времени

Длительность работы

Лекция 5. Динамическое программирование

1. Задача о распределении средств между предприятиями

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

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

Пусть – количество ресурсов, выделенных— му предприятию ();– функция полезности, величина дохода от использования ресурсаx_i, полученного— м предприятием;– наибольший доход, который можно получить при использовании ресурсовот первыхkразличных предприятий.

Сформулированную задачу можно записать в математической форме:

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

Обозначим через количество ресурса, используемогоk-м способом (), тогда для (k-1) способов остается величина ресурсов, равная (). Наибольший доход, который получается при использовании ресурса () от первых (k-1) способов, составит. Для максимизации суммарного дохода отk-го и первых (k-1) способов необходимо выбрать таким образом, чтобы выполнялись соотношения

Эти соотношения называются функциональными уравнениями Беллмана:

Источник

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

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

Реализацию проекта удобно представлять в виде графа, который задается множеством вершин или узлов и множеством дуг или ребер. Каждая дуга задается парой вершин. Сетью называется граф, каждой дуге которого поставлено в соответствие некоторое неотрицательное число. Сетевым графиком проекта называют наглядное представление проекта в виде сети. Дуги этой сети являются ориентированными, т. е. для каждой указаны начало и конец, и представляют работы’, вершины (их называют событиями) представляют последовательность выполнения работ. Ни одна работа, представленная дугой, выходящей из некоторой вершины, нс может начинаться прежде завершения всех работ, представленных дугами, входящими в данную вершину. Каждую пару событий должна соединять не более чем одна работа. В сетевом графике должно быть одно начальное и одно конечное событие. Для выполнения перечисленных требований допустимо введение фиктивных работ (работ нулевой продолжительности, не требующих затраты каких-либо ресурсов). Начальному событию присваивается номер 1. Чтобы пронумеровать остальные события нужно для каждого события найти величину максимального числа дуг в путях, соединяющих данное событие с начальным. События нумеруются по возрастанию этой величины. Если для некоторого числа событий указанная величина одинакова, то эти события нумеруются в произвольном порядке. После построения графа можно вычислить необходимые затраты времени (или ресурсов) на реализацию проекта. При этом удобно использовать метод динамического программирования, начиная с начального состояния и последовательно вычисляя наиболее ранние сроки наступления событий, вплоть до конечного. Цепочка событий, т. е. последовательность работ (дуг), сдвиг начала которых приводит к увеличению общего времени выполнения проекта, называется критическим путем.

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

Приступая к построению сетевого 1рафика (рис. 6.1). замечаем, что работа Перечень работ по строительству коттеджа и их продолжительности

Источник