WWW.DISSERS.RU

БЕСПЛАТНАЯ ЭЛЕКТРОННАЯ БИБЛИОТЕКА

   Добро пожаловать!


Pages:     || 2 |
ООО «Резольвента», www.resolventa.ru, resolventa@list.ru, (495) 509-28-10 Учебный центр «Резольвента» Доктор физико-математических наук, профессор К. Л. САМАРОВ МАТЕМАТИКА Учебно-методическое пособие по разделу ЭЛЕМЕНТЫ ТЕОРИИ ГРАФОВ.

ДИНАМИЧЕСКОЕ ПРОГРАММИРОВАНИЕ.

СЕТЕВОЕ ПЛАНИРОВАНИЕ © К. Л. Самаров, 2009 © ООО «Резольвента», 2009 ООО «Резольвента», www.resolventa.ru, resolventa@list.ru, (495) 509-28-10 ООО «Резольвента», www.resolventa.ru, resolventa@list.ru, (495) 509-28-10 СОДЕРЖАНИЕ 1. ЭЛЕМЕНТЫ ТЕОРИИ ГРАФОВ....….. …………………………………..4 1.1. Основные понятия, определения и термины...……………………….4 1.2. Задача о построении минимального остовного дерева..…………….8 2. ДИНАМИЧЕСКОЕ ПРОГРАММИРОВАНИЕ....…….………………….10 2.1. Общая схема метода динамического программирования.…………10 2.2. Задача о распределении средств...……………………………………12 3. СЕТЕВОЕ ПЛАНИРОВАНИЕ. ПРИМЕНЕНИЕ АЛГОРИТМОВ ДИНАМИЧЕСКОГО ПРОГРАММИРОВАНИЯ...………………………15 3.1. Понятие сети…………………………………………………………....15 3.2. Построение сетевого графика технологического комплекса………..16 3.3. Постановка задачи о нахождении наименьшего времени выполнения технологического комплекса..…………...……………. 18 3.4. Описание алгоритма динамического программирования для решения задачи о наименьшем времени выполнения технологического комплекса ……………………………………....….18 3.4.1. Построение сетевого графика, упорядоченного по этапам...…18 3.4.2. Расчет времени завершения узлов.…………………………….19 3.4.3. Построение критического пути и нахождение критического времени завершения комплекса работ ………………...………19 3.4.4. Нахождение свободных резервов времени на некритических операциях………………………………………… ……………..20 3.4.5. Применение алгоритма динамического программирования для решения задачи о наименьшем времени выполнения технологического комплекса..………………………………….20 3.5. Постановка задачи о поиске в сети кратчайшего пути..……………22 3.6. Применение алгоритма динамического программирования для решения задачи о поиске в сети кратчайшего пути…………………ВОПРОСЫ ДЛЯ САМОКОНТРОЛЯ..…………………………………………ЗАДАНИЯ ДЛЯ САМОСТОЯТЕЛЬНОЙ РАБОТЫ.…………………………ООО «Резольвента», www.resolventa.ru, resolventa@list.ru, (495) 509-28-10 ООО «Резольвента», www.resolventa.ru, resolventa@list.ru, (495) 509-28-ЛИТЕРАТУРА...…………………………………………………………………ООО «Резольвента», www.resolventa.ru, resolventa@list.ru, (495) 509-28-10 ООО «Резольвента», www.resolventa.ru, resolventa@list.ru, (495) 509-28-1. ЭЛЕМЕНТЫ ТЕОРИИ ГРАФОВ 1.1. Основные понятия, определения и термины Теория графов изучает математические объекты, которые можно изображать в виде рисунков, содержащих кружки и соединяющие их линии.

• Кружки называют вершинами (узлами) графа, а соединяющие линии - ребрами графа.

В качестве примера рассмотрим граф, изображенный на рис. 1. Этот граф состоит из 7 вершин V1,...,V7 и 8 ребер V1, V2, …, V6, V7.

V1 V2 VV5 VV6 VРис.1.

• Две вершины графа, соединенные ребром, называют смежными вершинами.

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

0 1 0 0 1 0 1 0 1 0 0 0 0 1 0 1 0 0 C = 0 1 0 1 0 1 (1.1) 1 0 0 1 0 1 0 0 0 1 0 0 0 0 0 1 0 1 ООО «Резольвента», www.resolventa.ru, resolventa@list.ru, (495) 509-28-10 ООО «Резольвента», www.resolventa.ru, resolventa@list.ru, (495) 509-28-Если граф имеет n вершин V1,V2,...,Vn, то его матрица смежности C = {c } ij является симметричной квадратной матрицей n - го порядка, состоящей из нулей и единиц. Элемент матрицы cij =1, если вершины Vi и Vj являются смежными, в противном случае cij = 0.

• Две смежные вершины называют граничными вершинами соединяющего их ребра.

• Ребро графа называют дугой, если на нем при помощи стрелки указано направление.

На рис. 1 дугами являются ребра V2, V3 и V5, V4.

• Граничную вершину дуги, из которой стрелка выходит, называют началом дуги, а вершина, в которую стрелка входит, - концом дуги.

• Граф, в котором каждое ребро имеет направление (т.е. является дугой), называют ориентированным графом. В противном случае граф называют неориентированным.

• Ребро, соединяющее две смежные вершины, называют ребром, инцидентным этим вершинам.

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

V1,V2 V1,V5 V2,V3 V3,V4 V4,V5 V4,V7 V5,V6 V6,V V1 1 1 0 0 0 0 0 V2 1 0 1 0 0 0 0 V3 0 0 1 1 0 0 0 B =.

V4 0 0 0 1 1 1 0 V5 0 1 0 0 1 0 1 V6 0 0 0 0 0 0 1 V7 0 0 0 0 0 1 0 В первом столбце таблицы инцидентности записаны все вершины графа, а первой строке - все ребра графа. Если вершина инцидентна ребру, то соотООО «Резольвента», www.resolventa.ru, resolventa@list.ru, (495) 509-28-10 ООО «Резольвента», www.resolventa.ru, resolventa@list.ru, (495) 509-28-ветствующий элемент таблицы равен 1, в противном случае элемент таблицы равен 0.

• Число ребер, инцидентных вершине Vi графа, называют степенью вершины Vi и обозначают символом deg Vi.

У графа, изображенного на рис.1, deg Vi = 2 i =1,2,3,6,7, deg V4 = deg V5 = 3.

( ) • Граф, содержащий n вершин и m ребер, называют графом типа n, m.

( ) Теорема Эйлера. Сумма степеней всех вершин графа типа n, m равна ( ) удвоенному числу его ребер, т.е.

n deg Vi = 2m.

i=Следствие. В любом графе число вершин нечетной степени четно.

Замечание. Теорему Эйлера и следствие из нее легко проиллюстрировать на примере графа, изображенного на рис.1.



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

Каждая цепь состоит из звеньев.

• Звеном называют две последовательные вершины цепи и связывающее их ребро.

Если Vi и Vj две последовательные вершины цепи, то соответствующее им звено обозначают символом Vi Vj.

• Простой цепью называют цепь, все вершины которой различны.

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

• Замкнутую цепь называют циклом.

• Простую замкнутую цепь называют простым циклом.

ООО «Резольвента», www.resolventa.ru, resolventa@list.ru, (495) 509-28-10 ООО «Резольвента», www.resolventa.ru, resolventa@list.ru, (495) 509-28-В графе, изображенном на рис. 1, циклом является, в частности, замкнутая цепь, состоящая из следующих звеньев:

V6 V5 V4 V7 V6.

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

Теорема Эйлера. Связный неориентированный граф является эйлеровым графом тогда и только тогда, когда степени всех его вершин четны.

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

Пример эйлерова графа можно получить, нарисовав на плоскости произвольный выпуклый многоугольник (рис. 2):

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

Теорема Оре. Если в графе не менее трех вершин, и для любых двух его несмежных вершин Vi и Vj выполнено неравенство deg Vi + deg Vj n, то граф является гамильтоновым графом.

Замечание. Граф, изображенный на рис. 2, является как эйлеровым, так и гамильтоновым графом.

• Связный неориентированный граф без циклов называют деревом.

Утверждение 1. Граф является деревом тогда и только тогда, когда две его любые вершины связаны единственной цепью.

ООО «Резольвента», www.resolventa.ru, resolventa@list.ru, (495) 509-28-10 ООО «Резольвента», www.resolventa.ru, resolventa@list.ru, (495) 509-28-Утверждение 2. Граф является деревом тогда и только тогда, когда, вопервых, он является связным, а, во-вторых, число его ребер на 1 меньше числа его вершин.

Примером дерева служит граф, изображенный на рис. 3.

VVVVVVVVVРис. • Остовным деревом графа называют дерево, все вершины которого совпадают с вершинами графа, а ребра являются ребрами графа.

У связного графа остовное дерево всегда существует.

• Минимальным остовным деревом связного графа с заданными длинами ребер называют остовное дерево, сумма длин ребер которого минимальна.

1.2. Задача о построении минимального остовного дерева Следующая задача решается с помощью построения остовного дерева, имеющего наименьшую сумму длин ребер.

Задача 1.2. На рис. 4 изображены населенные пункты (вершины графа) и связывающие их грунтовые дороги (ребра графа):

ООО «Резольвента», www.resolventa.ru, resolventa@list.ru, (495) 509-28-10 ООО «Резольвента», www.resolventa.ru, resolventa@list.ru, (495) 509-28-2 Рис. 4.

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

Решение. Рассмотрим какую-нибудь из вершин графа, изображенного на рис. 4, например, вершину № 3. Из всех ребер, соединяющих вершину № с остальными вершинами графа, самым коротким является ребро, соединяющее вершины № 3 и № 1.

Теперь рассмотрим множество всех ребер, соединяющих вершины № 3 и № 1 с остальными вершинами графа. Самым коротким из них является ребро, соединяющее вершины № 3 и № 5.

Действуя по аналогии, рассмотрим множество всех ребер, соединяющих вершины № 3, № 1 и № 5 с остальными вершинами графа. Самым коротким из них является ребро, соединяющее вершины № 5 и № 2.

Наконец, рассмотрим множество всех ребер, соединяющих вершины № 3, № 1, № 5 и № 2 с остальными вершинами графа. Самым коротким из них является ребро, соединяющее вершины № 5 и № 4.

В результате мы получаем граф, изображенный на рис. 5:

ООО «Резольвента», www.resolventa.ru, resolventa@list.ru, (495) 509-28-10 ООО «Резольвента», www.resolventa.ru, resolventa@list.ru, (495) 509-28-2 Рис. Этот граф является остовным деревом для графа, изображенного на рис. 4, причем таким остовным деревом, которое обладает наименьшей суммой длин ребер, а дорожная сеть, изображенная на рис. 5, является решением рассматриваемой задачи. Длина этой дорожной сети равна 13 условным единицам.

Замечание. Если в качестве первого шага расчетного алгоритма, использованного при решении данной задачи, избрать не вершину с № 3, а любую другую вершину графа, то полученное в результате работы алгоритма минимальное остовное дерево будет тем же самым.

Решение задачи 1.2. завершено.

2. ДИНАМИЧЕСКОЕ ПРОГРАММИРОВАНИЕ 2.1. Общая схема метода динамического программирования Метод динамического программирования дает возможность находить последовательные оптимальные решения в задачах, разделенных на этапы.

Изложим схему применения этого метода на следующей модели. Рассмотрим некоторую управляемую систему, которая может находиться в одном из нескольких состояний. На каждом этапе в результате применения управляющего воздействия (управления) система может изменить свое состояние или остаться в прежнем состоянии. Эффективность процесса управООО «Резольвента», www.resolventa.ru, resolventa@list.ru, (495) 509-28-10 ООО «Резольвента», www.resolventa.ru, resolventa@list.ru, (495) 509-28-ления характеризуется целевой функцией прибыли, зависящей от состояния системы и применяемого управления.





0 этап. В начальный момент времени система находится в исходном состоянии x0.

1 этап. В результате применения управления y1 система переходит из состояния x0 в состояние x1 = g1 x0, y1, ( ) при этом получается прибыль h1 x0, y1.

( ) 2 этап. В результате применения управления y2 система переходит из состояния x1 в состояние x2 = g2 x1, y2, ( ) при этом получается прибыль h2 x1, y2, ( ) и так далее.

За N этапов получается последовательность состояний x0, x1, x2,KxN и последовательность управлений y1, y2,K yN, где xn+1 = gn(xn, yn+1), n = 0,1,K,N, а общая прибыль на каждом этапе вычисляется по формуле Jn(x0, y1,K yn) = h1(x0, y1) + h2(x1, y2) +K+ hn(xn-1, yn), n =1,2,K, N, Нашей целью является отыскание такой последовательности оптималь ных управлений, y,K, y чтобы функция прибыли JN достигала {y }, 1 2 N максимума JN (x0, y1,Ky ) = max JN (x0, y1,KyN ).

N {y1,KyN} ООО «Резольвента», www.resolventa.ru, resolventa@list.ru, (495) 509-28-10 ООО «Резольвента», www.resolventa.ru, resolventa@list.ru, (495) 509-28-Принцип оптимальности Беллмана утверждает, что на последовательно сти оптимальных управлений, y,K, y должна достигать максимума {y } 1 2 N каждая из функций fn(xn-1, yn, yn+1,K yN ) = hn(xn-1, yn) + hn+1(xn, yn+1) +K+ hN (xN-1, yN ), n =1,2,K,N.

Если ввести обозначения n(xn-1) = max fn(xn-1, yn,KyN ), n =1,2,K,N, {y,KyN} n то из принципа оптимальности Беллмана вытекает, что функции n(xn-1) должны удовлетворять следующим функциональным уравнениям Беллмана:

n(xn-1) = max n+1(gn(xn-1, yn))+ hn(xn-1, yn), n =1,2,K, N. (2.1) yn Решение уравнений Беллмана позволяет найти последовательность оптимальных управлений и оптимальное значение функции прибыли.

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

2.2. Задача о распределении средств Используем метод динамического программирования для решения следующей задачи.

Задача 2.2. Составить план распределения суммы в 4 миллиона долларов между тремя предприятиями П1, П2, П3, приносящий наибольшую прибыль, если в каждое из предприятий может быть вложено 1, 2, 3 или 4 миллиона долларов, а прибыль каждого из предприятий задана в Таблице 2.2.1:

Т а б л и ц а 2.2.Размер вложенных Прибыль предприятий (%) средств (млн. долл.) П1 П2 П0 0 0 1 20 ООО «Резольвента», www.resolventa.ru, resolventa@list.ru, (495) 509-28-10 ООО «Резольвента», www.resolventa.ru, resolventa@list.ru, (495) 509-28-2 20 18 3 20 17 4 18 16 Решение. Пусть h1, h2, h3 - прибыли (млн. долл.) предприятий П1, П2, П3, соответственно. Тогда, пересчитывая данные из Таблицы 2.2.1, получим следующую Таблицу 2.2.2:

Т а б л и ц а 2.2.Размер вложенных Прибыль предприятий (млн. долл.) средств (млн. долл.) h1 h2 h0 0 0 0,2 0,22 0,0,4 0,36 0,0,6 0,51 0,0,72 0,64 0,Разобьем процесс выделения средств предприятиям на 3 этапа: на первом этапе выделяется y1 средств предприятию П1, на втором – y2 средств предприятию П2, на третьем – y3 средств предприятию П3.

Будем считать состоянием системы xi i = 0,1,2,3 ту сумму средств, ко( ) торая осталась нераспределенной после i -го этапа. Поскольку необходимо распределить все 4 миллиона долларов, то x0 = 4. Тогда xn = xn-1 - yn, n =1,2,3.

Заметим, что на третьем этапе выделения средств весь остаток x2 вкладывается в предприятие П3, поэтому y3 = x2.

Воспользуемся уравнениями Беллмана для N = 3. Тогда уравнения (2.1) примут следующий вид:

3(x2) = max h3( y3), x2 = 0,1,2,3,4, (2.2) {y3=0,1,2,3,4} 2(x1) = max h2( y2) +3(x1 - y2), x1 = 0,1,2,3,4, (2.3) {y2=0,1,2,3,4} ООО «Резольвента», www.resolventa.ru, resolventa@list.ru, (495) 509-28-10 ООО «Резольвента», www.resolventa.ru, resolventa@list.ru, (495) 509-28- 1(x0) = max h1( y1) +2(x0 - y1), x0 = 4. (2.4) {y1=0,1,2,3,4} Обозначим значения управлений y1, y2, y3, на которых достигается максимум в соотношениях (2.2), (2.3) и (2.4), символами y1, y2, y3, соответственно, и, воспользовавшись Таблицей 2.2.2, заполним по формулам (2.2) Таблицу 2.2.3:

Таблица 2.2.y x2 3(x2) y0 1 2 3 0 0 0 - - - - 0,25 - - - 0,25 1 - 0,46 - - 0,46 2 - - 0,45 - 0,45 3 - - - 0,76 0,76 4 - - - - Воспользовавшись Таблицей 2.2.2 и формулами (2.3), заполним Таблицу 2.2.4:

Таблица 2.2.y x1 2(x1) y0 1 2 3 0 0 0+0 - - - - 0,25 1 0+0,25 0,22+0 - - - 0,47 2 0+0,46 0,22+0,25 0,36+0 - - 0,68 3 0+0,45 0,22+0,46 0,36+0,25 0,51+0 - 4 0+0,76 0,22+0,45 0,36+0,46 0,51+0,25 0,64+0 0,82 Воспользовавшись Таблицей 2.2.2 и формулой (2.4), заполним Таблицу 2.2.5:

Таблица 2.2.y x0 1(x0) y0 1 2 3 4 0+0,82 0,2+0,68 0,4+0,47 0,6+0,25 0,72+0 0,88 Из Таблицы 2.2.5 вытекает, что оптимальным управлением будет y1 =1, при этом оптимальная прибыль равна 0,88. Далее получаем ООО «Резольвента», www.resolventa.ru, resolventa@list.ru, (495) 509-28-10 ООО «Резольвента», www.resolventa.ru, resolventa@list.ru, (495) 509-28- x1 = x0 - y1 = 4-1= 3, 2(x1) =2(3) = 0,68, y2 =1;

x2 = x1 - y2 = 3-1= 2, 3(x2) =3(2) = 0,46, y3 = 2.

Pages:     || 2 |










© 2011 www.dissers.ru - «Бесплатная электронная библиотека»

Материалы этого сайта размещены для ознакомления, все права принадлежат их авторам.
Если Вы не согласны с тем, что Ваш материал размещён на этом сайте, пожалуйста, напишите нам, мы в течении 1-2 рабочих дней удалим его.