Реферат: Оптимизация структуры стохастического графа c переменной интенсивностью выполнения работ

50. Произвести перекодирование условий работ множества .

51. Проверить выполняется ли условие .Если условие выполняется, то принять и перейти к п. 2;

если нетк п. 52.

52. Конец.

4. Пример.

На разработку, состоящую из 2-х параллельно выполняемых проектов, выделено два различных вида ресурсов по 2 единицы каждого. Исходные данные решения задачи приведены в табл. 1, где код работы состоит из кода проекта и кода работы в проекте. Первый проект содержит решающий результат с двумя альтернативами: 14,15.

Каждой альтернативе приписана aприорная вероятность: 0,7, 0,3. Требуется в области определить экстремальный граф, включающий альтернативу 14, вероятность которой равна 0,7. В табл. 2, где код работы с учетом разбивки работ на части, представлен экстремальный ресурсный граф, полученный алгоритмом, основные идеи которого были изложены выше. Более подробно пример рассматривается в [20, 21].

Таблица 1. Исходные данные.

j		Xj	cj			Dj
1	11	0	1	1	2	6
2	12	0	1	2	2	12
3	13	11	1	1	2	8
4	14	13, 12	1	2	2	4
5	15	13, 12	1	1	2	10
6	21	0	1	1	1	4
7	22	0	1	2	1	2
8	23	21	1	1	2	10
9	24	22	1	2	2	4

Таблица 2. Экстремальный ресурсный граф.

				nj
21	21	0	1	1	0	4	4
11	11	0	1	1	0	4	4
11	12	21, 11	1	2	4	1	5
12	13	0	2	1	0	2	2
12	14	13	2	0	2	2	4
12	15	14, 23	2	2	4	5	9
22	22	0	2	1	0	2	2
13	16	12	1	2	5	4	9
24	23	22, 13	2	2	2	2	4
14	17	16, 15	2	2	9	2	11
23	24	16, 21	1	2	9	5	14

Обоснованность задания критерия оптимальности (1) в виде графа следует из теоремы 1.

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

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

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

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

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

Теорема 2. Если все функции , n₂ , . . . , ), вогнуты и аддитивны, то математическое построение сетевой модели многопроектной разработки обеспечивает получение экстремального графа.

Cостояние системы меняется в моменты времени 2, . . . , что соответствует времени обеспечения работ ресурсами. Причем при распределении участвуют все ресурсы, выделенные на выполнение многопроектной разработки, и все работы, свободные в данный момент времени от технологических условий. Для всех значений к, состояние системыпостоянно. Распределение ресурсов среди работ множества 2, . . . , осуществляется по одной и той же схеме, включающей пункты алгоритма 1 для всех и для всех 2, . . . , В свете сказанного необходимо доказать, что переменные n_{i ,} Z_j обеспечивают максимальное значение функции (1) при фиксированных значениях i, . Зафиксируем значения i, , приняв i=1, . Не теряя общности рассуждений, доказательство теоремы проведем для случая, когда число работ множества A₂ , выполняемых 1-м видом ресурсов, равно 2. Для общего случая теорема доказана в работе [19] .

Пронумеруем работы множества А₂ . функция (1) примет вид (52)

(52)

Пусть в соответствии с условием теоремы

(53) .

(54)

Рассмотрим матрицу (55).

(55)

Физически означает приращение функции (52) за счет того, что на выполнение работы множества А₁ дополнительно назначается одна единица ресурса при условии, что на эту же самую работу уже было назначено единиц ресурсов.

В силу вогнутости функций справедливы соотношения (56).

(56)

С вводом элементов матрицы (55) функция (52) примет вид (57).

(57)

Это следует из (53), если представить

(58)