<< Предыдущая

стр. 8
(из 9 стр.)

ОГЛАВЛЕНИЕ

Следующая >>


периода. Рассмотрим первое подмножество. Так как проект 2 завершается
не раньше 7-го периода, то в оптимальном решении транспортной задачи
мы можем все работы по проекту, выполняемые во втором и четвертом
периодах передвинуть на более поздние периоды, освобождая место для
других проектов. Получим решение, приведенное в таблице 3.6.
Таблица 3.6.
k
1 2 3 4 5 6 7 8
i
0 3 3 6 6 9
1 0 0

0 0 0 0 8
2 4 4 4

0 0 0 4 6 8 10
3 2

0 1 1 2 2 3
4 0 3


Для этого решения C = 17, F = 20.
Для второго подмножества клетки (2, 7) и (2, 8) запрещены.
Оптимальное решение транспортной задачи приведено ниже.
Таблица 3.7.
k
1 2 3 4 5 6 7 8
i
0 0 3 6 6 9
1 0 3

? ?
0 0 4
2 0 0 4

0 0 2 4 6 8 10
3 0

0 0 1 1 2 2
4 3 3


Имеем C = 13, F = 20.
Выбираем второе подмножество с меньшей оценкой. Это
подмножество также разбиваем на два. В первом проект 2 завершается
53

точно в 6-ом периоде, а во втором - не позже 5-го периода. Оптимальное
решение оценочной задачи для первого подмножества приведено в
таблице 3.8, а для второго - в таблице 3.9.
Таблица 3.8.
k
1 2 3 4 5 6 7 8
i
0 3 3 6 6 9
1 0 0

? ?
0 0 0
2 0 4 4

0 0 0 4 6 8 10
3 2

0 0 1 1 2 2
4 3 3


Имеем C = 16 и F = 16, то есть полученное решение является оптимальным
в данном подмножестве.
Таблица 3.9.
k
1 2 3 4 5 6 7 8
i
0 0 0 3 6 9
1 3 6

? ? ?
0 4
2 0 0 0

0 0 2 4 6 8 10
3 0

0 0 1 1 2 2
4 3 3


Имеем C = 15 и F = 15, то есть полученное решение является оптимальным
в этом подмножестве.
Окончательно получаем оптимальное решение, соответствующее
решению транспортной задачи, приведенному в таблице 3.9 со значением
упущенной выгоды F = 15. Таким образом в данном случае нам пришлось
решить пять задач транспортного типа. Заметим, сто число возможных
54

вариантов, определяемое числом перестановок четырех проектов равно 24.
С ростом числа проектов число возможных вариантов растет как n! и
преимущества описанного метода проявляются в бoльшей степени.
В тех случаях, когда проекты направлены на достижение различных
целей в качестве критерия оптимальности распределения финансовых
ресурсов целесообразно взять
F = max c i ( t i ? D i ) , (3.10)
i

что соответствует минимизации максимальной упущенной выгоды. Эта
задача легко сводится к параметрической транспортной задаче. В качестве
параметра выступает величина критерия F. Дадим описание алгоритма.
Пусть задана величина F (на первом шаге берем F = 0). В этом случае
из условия
ci(ti - Di) ? F
получаем
F + c i Di
t i ? bi = , i = 1, n . (3.11)
ci

Оставляем в транспортной сети только дуги (i, j), такие что j ? bi и
определяем максимальный поток в сети при ограничении
bi
? x ik ? w i , i = 1, n . (3.12)
k =1

bi
? x ik = w i для всех i,
Если этот поток насыщает все входные дуги, то есть
k =1

то получено оптимальное решение задачи. В противном случае
увеличиваем F до такой величины, при которой в сети появляется хотя бы
одна новая дуга. Очевидно, что за конечное число шагов будет получено
оптимальное решение задачи.
Пример 3.4. Решим задачу, рассмотренную в примере 3.3 для
критерия (3.10). Заметим, что величина F должна быть по крайней мере
55

такой, при которой в любую вершину j идет хотя бы одна дуга. Для
вершины 8 имеем
min ci(8 - Di) ? F
или
min (15, 16, 10, 6) ? F.
Берем F = 6. В таблице 3.10 знаком (?) указаны запрещенные клетки.
Определяем поток максимальной величины в соответствующей
транспортной сети. Единичные потоки по дугам отмечены в таблице 3.10.
Таблица 3.10.
k
1 2 3 4 5 6 7 8
i
? ? ?
1 1
1

? ? ?
1 1 1
2

? ?
1
3

1 1
4


Максимальный поток равен 8, то есть все проекты выполняются.
Таким образом мы получили оптимальное решение со значением
F = 6. Интересно отметить, что полученное решение имеет суммарную
величину упущенной выгоды, равную 16, что весьма близко к
оптимальной величине F = 15 (для оптимального решения по критерию
суммы упущенной выгоды максимум упущенной выгоды имеет проект 2, и
этот максимум равен 8, что больше, чем в полученном выше решении.
Во многих случаях проекты, входящие в программу развития
отрасли, зависимы между собой в том смысле, что для начала проекта
необходимо, чтобы были завершены другие проекты. Такие зависимости
удобно задавать в виде сетевого графика (графа), вершины которого
56

соответствуют проектам, а дуги отражают зависимости между проектами.
Наличие дуги (i, j) в сетевом графике означает, что проект j нельзя
начинать, пока не завершен проект i. Рассмотрим задачу минимизации
упущенной выгоды с учетом зависимостей между проектами. Дадим
оценку снизу величины упущенной выгоды. Для этого определим ранние
сроки завершения проектов t p , применяя известные алгоритмы расчета
i

сетевых графиков [16]. Очевидно, что величина упущенной выгоды
n
F ? ? citp . (3.13)
i
i =1

На основе оценки (3.13) можно предложить метод ветвей и границ для
решения задачи. Примем, что проекты имеют номера такие, что
c1 c c
? 2?L? n.
w1 w 2 wn
ci
Напомним, что отношение характеризует в определенной степени
wi
приоритетность проектов по критерию упущенной выгоды. Далее
рассматриваем проекты, которые можно начинать, и финансируем их в
порядке приоритетности. В силу ограниченности финансов может
возникнуть ситуация, когда очередной проект не может быть обеспечен
финансированием. Такую ситуацию назовем конфликтной. При
возникновении конфликтной ситуации рассматриваем возможные
варианты разрешения конфликта. Для каждого такого варианта
определяем оценку снизу по формуле (3.13). Согласно методу ветвей и
границ, для дальнейшего развития выбирается вариант с минимальной
оценкой. Дадим иллюстрацию алгоритма на примере.
Пример3.5. Пусть сетевой график из четырех проектов имеет вид,
показанный на рис. 3.4. В вершинах указаны номера проектов (верхнее
57

число) и минимальные продолжительности (нижнее число) Данные о
проектах приведены в таблице 3.11.


1 3
5 2




2 4
3 3

Рис. 3.4.


Таблица 3.11.

i 1 2 3 4

20 18 10 12
wi

4 6 5 4
ai

?i 5 3 2 3

12 9 4 2
ci


Пусть уровень финансирования программы N = 6 в каждый период.
Определим оценку снизу величины упущенной выгоды. Для этого
определим ранние времена завершения проектов:
t 1 = 5, t p = 3, t p = 7, t p = 8.
p
2 3 4

Имеем
F = 12 ? 5 +9 ? 3 + 4 ? 7 + 2 ? 8 = 131.
58

1 шаг. Проекты 1 и 2 не могут финансироваться с максимальным
уровнем, так как а1 + а2 = 10 > 6. Возникла конфликтная ситуация.
Рассматриваем два варианта.
Вариант 1. Проект 1 финансируется при максимальном уровне
финансирования. имеем финансирование первого проекта на уровне u1 = 4,
а второго - на остаточном уровне u2 = 2. Через 5 дней проект 1
завершается. К этому моменту остается невыполненным проект 2 в объеме
w2(5) = 18 - 2? 5 = 8 с минимальной продолжительностью ?2(5) = 8/6 = 11/3.
Имеем для первого варианта
t 1 = 5, t p = 5 + 11/3 = 61/3, t p = 5 + 2 = 7, t p = 91/3.
p
2 3 4

<< Предыдущая

стр. 8
(из 9 стр.)

ОГЛАВЛЕНИЕ

Следующая >>