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

• Задача о наибольшей общей подпоследовательности: даны две последовательности, требуется найти самую длинную общую подпоследовательность.
• Задача поиска наибольшей увеличивающейся подпоследовательности: дана последовательность, требуется найти самую длинную возрастающую подпоследовательность.
• Задача о редакционном расстоянии (расстояние Левенштейна): даны две строки, требуется найти минимальное количество стираний, замен и добавлений символов, преобразующих одну строку в другую.
• Задача о вычислении чисел Фибоначчи
• Задача о порядке перемножения матриц: даны матрицы , …, , требуется минимизировать количество скалярных операций для их перемножения.
• Задача о выборе траектории
• Задача последовательного принятия решения
• Задача об использовании рабочей силы
• Задача управления запасами
• Задача о ранце: из неограниченного множества предметов со свойствами «стоимость» и «вес» требуется отобрать некое число предметов таким образом, чтобы получить максимальную суммарную стоимость при ограниченном суммарном весе.
• Алгоритм Флойда-Уоршелла: найти кратчайшие расстояния между всеми вершинами взвешенного ориентированного графа.
• Алгоритм Беллмана — Форда: найти кратчайший путь во взвешенном графе между двумя заданными вершинами.

· Максимальное независимое множество вершин в дереве: дано дерево, найти максимальное множество вершин, никакие две из которых не связаны ребром.

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

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

Проиллюстрируем основную идею. Пусть процесс управления нек-рой системой Xсостоит из тшагов (этапов); на i-м шаге управление y_i переводит систему из состояния x_{i- 1}, достигнутого в результате (i-1)-го шага, в новое состояние ж, -. Этот процесс перехода осуществляет заданная функция f_i (x, у), и новое состояние определяется значениями x_{i- 1}, y_i:

Таким образом, управления у ₁, у ₂,..., у _т переводят систему из начального состояния в конечное - где Х ₀ и Х _т - совокупности допустимых начальных и конечных состояний системы X. Опишем одну из возможных постановок экстремальной задачи. Начальное состояние х ₀ задано. Требуется выбрать управления у ₁, у ₂,..., у _т таким образом, чтобы система Xперешла в допустимое конечное состояние и при этом заданная целевая функция F(x₀, у ₁, x₁, у ₂,..., у _т, х _т)достигла максимального значения F*, т. е.

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

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

Для решения задач Д. п. обычные методы математического анализа либо вообще неприменимы, либо приводят к огромному числу вычислений. В основе метода Д. п. лежит принцип оптимальности, сформулированный Р. Беллманом (R. Bellman): предположим, что осуществляя управление дискретной системой X, мы уже выбрали некоторые управления дискретной системой у ₁, у ₂,..., у _k тем самым траекторию состояний х ₀, х ₁,..., x_k, и хотим завершить процесс, т. е. выбрать y_{k+ 1}, y_k+2,..., у _т (а значит и x_{k+ 1}, x_{k+ 2},..., x_m); тогда, если завершающая часть процесса не будет оптимальной в смысле достижения максимума функции

то и весь процесс не будет оптимальным.

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

k=1, 2,..., т. Здесь максимум берется по всем управлениям, допустимым на шаге к. Соотношение, определяющее зависимость w_k-1 от w_k, принято называть Беллмана уравнением. Смысл функций w_k-1 (х). нагляден: если система на шаге k-1 оказалась в состоянии х, то w_k-1(x) есть максимально возможное значение функции F. Одновременно с построением функций w_k-1 (х). находятся условные оптимальные управления y_k (х)на каждом шаге (т. е. значения оптимального управления при всевозможных предположениях о состоянии системы на шаге k-1). Окончательно оптимальные управления находятся последовательным вычислением величин

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

Д. п. дало новый подход ко многим задачам вариационного исчисления.

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

В качестве основного литературного источника по данной теме рекомендуется использовать [1, 4], в качестве дополнительного – [5, 8, 13].

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

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

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

• вскрыть резервы сил, средств и времени, скрытые в нерацио­нальной организации управляемого процесса, осуществлять контроль за ходом процесса сразу по нескольким направлениям;

• упростить внесение изменений, уточнений и дополнений в планы, обеспечивая гибкость и требуемую периодичность плани­рования, упростить систему отчетности

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

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

Элементы сетевой модели:

· работа - процесс, приводящий к достижению определенного результата, требующий затрат каких-либо ресурсов и имеющий протяженность во времени;

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

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

Рис.1. Сетевой график

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

Сетевой график (стрелочная диаграмма, сетевая модель или просто сеть) состоит из стрелок и кружков, обозначающих два основных элемента любой сети – работы и события. Работа – это реальный процесс или действие, требующее затрат труда, материалов или времени. Продолжительность выполнения работ измеряется в единицах времени: часах, днях, неделях, месяцах и т.д. Работы могут иметь также и количественные показатели, которые характеризуют трудоемкость, стоимость, материальные ресурсы и т.д. Работы обозначаются стрелками, которые соединяются между собой с помощью кружков (событий). Временные и количественные оценки проставляются обычно над стрелками. Событием называется результат, получаемый после выполнения работ, стрелки которых сходятся к данному кружку. Событие имеет двойственное значение. Для всех предшествующих работ оно является законченным свершением, а для последующих работ – начальным пунктом их выполнения. Всем событиям присваивается определенный цифровой шифр, который проставляется обычно внутри кружка. В общем смысле начальное (предшествующее) событие обозначается буквой i, а конечное (последующее) буквой j, работа в этом случае обозначается как i, j.

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

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

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

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

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

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

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

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

6. Длина стрелки не зависит от времени выполнения работы.

7. Каждая операция должна быть представлена только одной стрелкой.

8. Следует избегать пересечения стрелок.

9. Не должно быть стрелок, направленных справа налево.

10. Номер начального события должен быть меньше номера конечного события.

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

12. Для любой работы предшествующее ей событие расположено левее и имеет меньший номер по сравнению с завершающим эту работу событием.

Расчет параметров сетевого графика. Начало и окончание любой работы описываются парой событий, которые называются начальным и конечным событиями. Поэтому для указания конкретной работы используют код работы Р_{i, j}, состоящий из номеров начального (i-го) и конечного (j-го) событий (рис.2а).

На рис.2б изображен пример кодирования работ и событий в принятых обозначениях: t_ij – продолжительность работы Р_{i, j}, t – ранний срок (ожидаемый момент) осуществления события, t^* – поздний срок (предельный момент) осуществления события, n – номер события, n_см – номер предшествующего (смежного) события.

Рис. 2. Обозначение элементов сетевого графика: а – код работы; б – пример кодирования событий в при­нятых обозначениях; в – пример изо­бражения события в принятых вы­ше обозначениях

На рис. 2 в приведён пример изображения события в принятых выше обозначениях.

Обозначим через множество работ, входящих в j-е событие, а через – множество работ, выходящих из i-го события.

Ранний срок (ожидаемый момент) осуществления j-го события представляет собой момент времени, раньше которого событие произойти не может и рассчитывается по формуле

.

Поздний срок (предельный момент) осуществления i-го собы­тия показывает максимальную задержку во времени наступления данного события:

.

Одно из важнейших понятий сетевого графика – понятие пути L.

Критический путь – последовательность работ между начальными и конечными событиями сети, имеющих наибольшую продолжительность во времени. Минимальное время, необходимое для выполнения проекта, запланированного сетевым графиком, равно длине критического пути. Сетевой график может содержать не один, а несколько критических путей. Критическими называются также работы и события, расположенные на этом пути. Резервный интервал от t до t* для событий, лежащих на критическом пути, равен 0. Для завершающего события сетевого графика поздний срок свершения события должен равняться его раннему сроку, т. е. t_п = t*_п.

Длина критического пути равна раннему сроку свершения завершающего события, т. е. t_кр = t_п = t*_п.

Любая из работ пути L на его участке, не совпадающем с критическим путем (замкнутым между двумя событиями критического пути), обладает резервом времени.

Среди резервов времени работ наиболее часто используют полный и свободный резервы времени работ.

Полный резерв времени работы P_{i, j} показывает, на сколько можно увеличить время выполнения данной работы при условии, что срок выполнения комплекса работ не изменится. Полный резерв определяется по формуле

.

Свободный резерв времени работы P_{i, j} представляет часть полного резерва времени, на которую можно увеличить продолжительность работы, не изменив при этом раннего срока ее конечного события. находится по формуле

.

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

Анализ и оптимизация сетевого графика.Чаще всего продолжительность работы по сетевому графику заранее не известна и может принимать лишь одно из ряда возможных значений, т. е. продолжительность работы t_ijявляется случайной величиной, характеризующейся своим законом распределения, а значит, своими числовыми ха­рактеристиками – средним значением, или математическим ожиданием, и дисперсией σ ² _{i, j}.

Для определения числовых характеристик и σ ²_{i, j} работы P_{i, j} на основании опроса ответственных исполнителей проекта и экспертов определяют три временные оценки:

а) оптимистическую оценку а_ij;

б) пессимистическую оценку b_ij;

в) наиболее вероятную оценку m_ij.

Указанные три оценки являются основой для расчета средней ожидаемой продолжительности работы ( ) и ее дисперсии ( ). При этом используется гипотеза об определенном законе распределения длительностей работ (так называемое β -распределение).

Предположение о β -распределении продолжительности работы Р_{i, j} позволяет получить следующие оценки ее числовых характеристик:

;

.

Общая продолжительность пути L имеет нормальный закон распределения со средним значением (L), равным сумме средних значений продолжительности составляющих его работ и дисперсией σ ² (L), равной сумме соответствующих дисперсий σ ²_{i, j}:

;

.

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

Полагая t_кp случайной величиной, имеющей нормальный закон распределения, получим

,

где Ф(z) – значение интеграла вероятностей Лапласа, где

,

где σ _кр – среднее квадратическое отклонение длины критического пути:

.

Если P(t_кp ≤ Т) мала (например, меньше 0, 3), то опасность срыва заданного срока выполнения комплекса велика, необходимо принятие дополнительных мер (перераспределение ресурсов по сети, пересмотр состава работ и событий и т. п.). Если P(t_кp ≤ Т) значительна (например, более 0, 8), то, очевидно, с достаточной степенью надежности можно прогнозировать выполнение проекта в установленный срок.

Значения функции Лапласа определяются с помощью значений таблицы функций Лапласа или с помощью функции «НОРМРАСП» в среде MS Excel (см. подразд. 3.4).

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

,

где Kсл – коэффициент сложности сетевого графика; nраб – количество работ, ед.; nсоб – количество событий, ед.

Сетевые графики, имеющие коэффициент сложности от 1, 0 до 1, 5, являются простыми, от 1, 51 до 2, 0 – средней сложности, более 2, 1 – сложными.

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

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

где t(Lmax) – продолжительность максимального пути, проходящего через работу Pi, j, от начала до конца сетевого графика; tкр – продолжительность (длина) критического пути; t'кр – продолжительность отрезка рассматриваемого максимального пути, совпадающего с критическим путем.

Коэффициент напряженности Кн работы Pi, j может изменяться в пределах от 0 (для работ, у которых отрезки максимального из путей, не совпадающие с критическим путем, состоят из фиктивных работ нулевой продолжительности) до 1 (для работ критического пути). Чем ближе к 1 коэффициент напряженности Кн работы Pi, j, тем сложнее выполнить данную работу в установленные сроки. Чем ближе Кн работы Pi, j к нулю, тем большим относительным резервом обладает максимальный путь, проходящий через данную работу.

Вычисленные коэффициенты напряженности позволяют дополнительно классифицировать работы по зонам. В зависимости от величины Кн выделяют три зоны: критическую (Кн > 0, 8); подкритическую (0, 6 < Кн < 0, 8); резервную (Кн < 0, 6).

Оптимизация сетевого графика методом «время-стоимость»

При использовании метода «время-стоимость» предполагают, что уменьшение продолжительности работы пропорционально возрастанию ее стоимости. Каждая работа Pi, j характеризуется продолжительностью ti, j, которая может находиться в пределах

где аij – минимально возможная (экстренная) продолжительность работы Pi, j, которую только можно осуществить в условиях разработки; bij – нормальная продолжительность выполнения работы Pi, j.

При этом стоимость сi, j работы Pi, j заключена в границах от cmin (при нормальной продолжительности работы) до сmах (при экстренной продолжительности работы).

Затраты на ускорение работы Pi, j (по сравнению с нормальной продолжительностью) на единицу времени рассчитываются по формуле

где hi, j – коэффициент затрат на ускорение работы Pi, j.

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

.

Стоимость выполнения проекта после оптимизации уменьшится на величину

.

Для проведения частной оптимизации сетевого графика, кроме продолжительности работ ti, j, необходимо знать их граничные значения аij и bij, а также показатели затрат на ускорение работ hi, j, вычисляемые по формуле. Продолжительность каждой работы ti, j целесообразно увеличить в таком размере, чтобы не изменить ранние (ожидаемые) сроки наступления всех событий сети, т. е. на величину свободного резерва времени .

В качестве основного литературного источника по данной теме рекомендуется использовать [1, 4], в качестве дополнительного – [5, 6, 10, 13].