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

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

ОГЛАВЛЕНИЕ

Следующая >>

1;1 1;4 2;2 3;1 2;4 3;2




2 7 20 3 10 35 50 1 8 50
1 2 3 1 2 3 4 1 2 3


УЖ УБ УЭ


Рис.2.8.


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

экономической эффективности заданы затраты (sЖj) и (sБj), требуемые для
достижения оценки j, соответственно по критериям (Б) и (Ж). В этом
случае, метод определения программы минимальной стоимости основан
на переборе возможных оценок уровня экономической эффективности.
При каждом значении уровня экономической эффективности решается
задача построения программы минимальной стоимости по остальным
критериям. Из четырех вариантов, соответствующих четырем возможным
значениям уровня экономической эффективности, выбирается наилучший.
Пример. Пусть затраты (sЖj) и (sБj) для различных уровней
экономической эффективности имеют значения, приведенные в таблице
2.3.
Таблица 2.3.
j
Э 1 2 3 4
i
Ж 2 7 20 60
1
Б 3 10 35 50
Ж 1 3 10 30
2
Б 5 15 45 70
Ж 0 1 5 15
3
Б 8 30 60 100
Ж 0 0 2 5
4
Б 18 40 70 120

Для каждого уровня экономической эффективности мы получаем
некоторую сеть напряженных вариантов, которая является подграфом сети
2.7. Заметим, однако, что эти подграфы пересекаются только в начальной
вершине и некоторых конечных вершинах. Разделим конечные вершины, в
которых пересекаются подграфы, на несколько вершин, так чтобы все
подграфы имели только одну общую вершину, а именно начальную, рис
2.9. Теперь для получения сети применяем описанный выше алгоритм
определения варианта минимальной стоимости. Оптимальный вариант
41


23
2


52 23 31
1;3 2;2 3;1


1 8 50
2 15 30
1 2 3
1 2 3



30
2 71 18 15 57
1;1 1;4 2;2 3;1 2;4 3;2




01 3 7 10 20 8 5 15 10 70 50 1 8 50
1 2 3 1 2 3 1 2 3


УБ
УЖ УЭ


Рис.2.9.


показан на рис. 2.9 толстыми линиями. Это вариант (3; 1; 2) с затратами
s = 23. Таким образом можно определять оптимальные варианты
программы развития отрасли и для случая, когда одно из направлений
влияет на другие.
42


ГЛАВА III. Задача минимизации
упущенной выгоды


После того, как сформирована программа развития отрасли, то есть
выбрано множество проектов, реализация которых обеспечивает
достижение поставленных целей, возникает задача построения
календарного плана реализации программы. Дело в том, что в условиях
дефицита финансовых ресурсов нет возможности вести одновременно
реализацию всех проектов программы. Необходимо выбрать
первоочередные, реализация которых обеспечивает наибольший эффект.
Реализация остальных проектов отодвигается на более поздние сроки.
Очевидно, что сдвиг проектов на более поздние сроки приводит к
уменьшению эффекта или, как говорят, к упущенной выгоде. Желательно
разработать такой план реализации программы, при котором упущенная
выгода минимальна. Рассмотрим формальную постановку задачи. Пусть
программа состоит из n проектов. Каждый проект будем описывать
требуемым объемом финансирования и продолжительностью
wi
реализации ?i. Величина ?i определяется максимальным объемом средств
ai, который можно освоить в единицу времени, то есть ?i = wi /ai. Примем,
что задержка срока реализации проекта на единицу времени (например, на
месяц) приводит к упущенной выгоде, которая равна ci. Известны
возможные объемы финансирования программы в зависимости от
времени, то есть известно, что в k-ом периоде объем финансирования
составит Nk, k = 1, p . Задача заключается в определении графиков
финансирования проектов так, чтобы упущенная выгода
n
F = ? citi
i =1
43

(ti - момент завершения i-го проекта) была минимальной. Эта задача была
поставлена в работе [18], где предложен эвристический алгоритм ее
решения. В основе алгоритма лежит упорядочение проектов по убыванию
приоритетов qi = ci/wi. Там же приведен пример, показывающий, что это
правило не всегда дает оптимальное решение. Рассмотрим приближенный
алгоритм решения задачи.
Обозначим xik - объем финансирования i-го проекта в k-ом периоде.
Выпишем ограничения на допустимые значения {xik}. Ограничения на
заданные объемы финансирования по периодам
n
? x ik ? N k , k = 1, p . (3.1)
i =1

Ограничения на допустимый объем финансирования i-го проекта в k-ом
периоде
xik ? ai, k = 1, p , i = 1, n . (3.2)

Напомним требование выполнения полного объема работ по проектам:
p
? x ik = w i , i = 1, n . (3.3)
k =1

Ограничения (3.1) - (3.3) это классические ограничения транспортной
задачи. Условия ее разрешимости очевидны:
p n
? Nk ? ? wi ,
k =1 i =1

то есть общий объем финансовых ресурсов должен быть не меньше
суммарного объема требуемых ресурсов для реализации всех проектов.
Специфику задачи определяет вид целевой функции. Действительно,
момент завершения проекта ti равен периоду ki такому, что
ki
? x iq = wi ,
q =1

то есть за периоды от 1 до ki выполнен весь объем работы по i-му проекту.
44

Аналитически ti можно записать как функцию {xik}следующим
образом:

( )
t i = max k ? x ik ,
k

и, соответственно, критерий оптимальности примет вид
n
? c i t i = ? c i max( k ? x ik ) . (3.4)
k
i =1 i

Эффективных точных методов решения задачи (3.1) - (3.4) не известно.
Ниже дается описание приближенного алгоритма. Предварительно для
каждого проекта i определим последовательность чисел
? k + ? i ? 1?
d ik = ? ?,
?i
? ?
где [x] - целая часть x. Другими словами, мы разбиваем ось времени на
отрезки длинны ?i. При этом dik определяет номер отрезка, которому
принадлежит период k. Так, если ?i = 3, то первые три периода имеют
dik = 1, следующая тройка - dik = 2 и т.д.
Лемма.
p
x ik
? a ? d ik .
ti ? (3.5)
k =1 i

Доказательство. Пусть проект i завершается в периоде q, то есть
ti = q, причем выполняется непрерывно в периодах с (q - ?i + 1) до q с
максимально допустимым уровнем финансирования ai, то есть
xij = ai, j = ( q ? ? i + 1), q .

В этом случае
x ik
p q
? ? d ik .
d ik =
ai
k =1 k = q ? ? i +1

q
? d ik =q.
Покажем, что
k = q ? ? i +1
45

Действительно, пусть q = (m - 1)?i, тогда все периоды от (q - ?i + 1) до
q
? d ik = ( m ? 1)? i = q . Если q = (m - 1)?i + l
q имеют dik = (m - 1) и значит
k = q ? ? i +1


(l < ?i), то l периодов имеют dik = m, а ?i - l периодов имеют dik = (m - 1). В
этом случае
q
? d ik = ( m ? 1)(? i ? l) + ml = ( m ? 1)? i + l = q .
k = q ? ? i +1


Пусть теперь xik > 0 для k ? Qi, причем проект i завершается в периоде q. В
этом случае в силу неубывания dik с ростом k
x ik
p q
? ? d ik
d ik ? = q.
ai
k =1 k = q ? ? i +1

Лемма доказана.
Заменим величину ti на ее нижнюю оценку (3.5). В этом случае

(c ):
d ijc i
=
получаем классическую транспортную задачу определить
ij ai


xij ? 0, i = 1, n , j = 1, p такие, что

C = ? x ij c ij > min , (3.6)
i, j


? x ij ? N j , j = 1, p , (3.7)
i


? x ij = wi j , i = 1, n . (3.8)
j

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

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

ОГЛАВЛЕНИЕ

Следующая >>