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

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

ОГЛАВЛЕНИЕ

Следующая >>

t1 t2
0


-G0

-C0


Рис.10. Пример динамики финансового баланса и резервов центра

Цель центра заключается в том, чтобы выполнить при-
быльные работы с минимальными резервами за минимальное
42
время. Однако, цели минимизации резервов и минимизации
времени вступают в противоречие друг с другом. Поэтому для
выявления множества рациональных вариантов (последова-
тельностей выполнения прибыльных работ) целесообразно
исследовать возможные комбинации времен и резервов. Экс-
тремальные их оценки могут быть получены в результате
решения следующих задач.
Задача 1. Найти множество последовательностей выпол-
нения работ (вариантов), на которых достигает минимума
величина резервов центра, и из этого множества выбрать вари-
ант, которому соответствует минимальная продолжительность
проекта.
Задача 2. Найти множество последовательностей выпол-
нения работ (вариантов), на которых достигает минимума
продолжительность проекта, и из этого множества выбрать
вариант, которому соответствует минимальная величина ре-
зервов центра.
Обозначим (C1, T1) – решение (значения максимальных ре-
зервов и продолжительности проекта) задачи 1, (C2, T2) – ре-
шение задачи 2. Очевидно, что C1 ? C2, T1 ? T2. Полученные
две оценки являются границами множества Парето-
эффективных (по критериям максимального резерва и продол-
жительности) вариантов – см. рисунок 12, на котором изобра-
жено это множество для рассматриваемого ниже примера 4.
Процесс решения каждой из сформулированных выше за-
дач может быть разбит на два этапа. На первом этапе опреде-
ляется множество вариантов, на которых достигается минимум
величины, минимизируемой в первую очередь. На втором
этапе величина, минимизируемая во вторую очередь, оптими-
зируется на множестве вариантов, полученных на первом
этапе.
Первые этапы решения и задачи 1, и задачи 2, реализуются
достаточно просто.
Рассмотрим задачу поиска последовательности выполне-
ния работ (вариантов), на которых достигает минимума вели-
чина резервов центра. Эта задача является частным случаем
43
задачи о лекторе [3]. Понятно, что в оптимальном варианте все
работы будут выполняться последовательно (то есть никакие
две работы не должны выполняться параллельно) и без пере-
рывов. Следовательно, остается найти оптимальный порядок
выполнения работ. Для этого воспользуемся результатами,
полученными в [3, 5], в соответствии с которыми минимуму
максимального резерва будет соответствовать выполнение
прибыльных работ (убыточные работы, то есть работы из
множества I \ Q0, в дальнейшем рассматривать не будем) в
порядке возрастания их затрат.
Упорядочим работы в порядке возрастания затрат:
c1 ? c2 ? … cm, где m = |Q0|. Положив
(6) t1 = 0, ti = ti-1 + ?i-1, i = 2 , m ,
и подставив времена начала работ (6) в (1), получим значение
С1.
Отметим, что, если значения затрат, необходимых для вы-
полнения соответствующих работ, неизвестны центру и сооб-
щаются ему АЭ, то АЭ не заинтересованы в искажении затрат,
так как затраты несут сами АЭ (именно они рассчитываются
по взятому кредиту), а завышение затрат приведет к тому, что
в результате первого этапа решения задачи 1 срок начала реа-
лизации соответствующей работы увеличится, что невыгодно
для АЭ. Для исключения выгодности манипулирования ин-
формацией о затратах со стороны АЭ, центру следует, сообщая
АЭ «правила игры», не детализировать правила принятия
решений на втором этапе.
Второй этап решения задачи 1 (в дальнейшем будем назы-
вать эту задачу задачей 1.2) заключается в нахождении времен
начала выполнения работ, минимизирующих время заверше-
ния проекта, при условии, что величина максимального резер-
ва не превышает известного значения C1. Эта задача будет
рассмотрена ниже.
Рассмотрим задачу поиска последовательности выполне-
ния работ (вариантов), на которых достигает минимума про-
должительность проекта (первый этап задачи 2). Понятно, что
в оптимальном варианте все работы будут выполняться парал-
44
лельно и без перерывов. При этом продолжительность проекта
будет равна T2 = max {?i}, то есть будет определяться макси-
i?Q0
мальной из длительностей прибыльных работ. Следовательно,
остается найти оптимальный порядок выполнения работ (в
дальнейшем будем называть эту задачу задачей 2.2), то есть
времена начала работ, при которых минимизируется макси-
мальный резерв центра при условии, что продолжительность
проекта не превышает известного значения T2. Эта задача
будет рассмотрена ниже.
Рассмотрим следующий пример, иллюстрирующий реше-
ния задач оптимизации последовательности выполнения работ.
Пример 4. Пусть имеются пять работ, данные о которых
представлены в таблице 6, ?0 = 20%, ? = 40%. Видно, что
пятая работа является убыточной по критерию приведенной
рентабельности (хотя без учета платежей по процентам креди-
та она является прибыльной), поэтому из дальнейшего рас-
смотрения ее можно исключить.
Таблица 6
? i0
?i ?i
№ ci di
1 10 20 1 1,0 0,8
2 10 25 4 1,5 0,7
3 20 30 2 0,5 0,1
4 40 90 5 1,25 0,25
5 30 40 3 0,33 -0,27

Решение первого этапа задачи 1 дает следующую последо-
вательность выполнения работ (без одновременного выполне-
ния и перерывов): 1-2-3-4. При этом максимальный резерв
равен C0 = 33,2, а продолжительность проекта составляет
T10 = 12 единиц времени (см. рисунок 2). На втором этапе
решения задачи 1 найдем последовательность выполнения
операций (операции в круглых скобках выполняются парал-
лельно): (2; 1)-(2; 3) - 2 - 4, при которой величина максималь-
ного резерва не изменится, а продолжительность проекта
45
сократится до T1 = 9 единиц времени (см. жирную линию на
рисунке 11 – цифры у дуг соответствуют номерам работ). При
этом после оптимизации времени график резервов стал более
«равномерным».

с(t) T1 T10
C0 4 4
3;2
26,8
2
26
1;2
20
3
14
10 1
2
t
6,8
0 12
1 5
3 9
4 7

Рис. 11. Оптимальная последовательность работ в задаче 1


Решение первого шага задачи 2 заключается в одновре-
менном начале выполнения всех работ, что требует макси-
мального резерва C20 = 80 и времени T2 = 5 единиц времени.
На втором шаге решения задачи 2 можно, не увеличивая вре-
мени выполнения проекта, сократить величину максимального
резерва до C2 = 70.
Нанося результаты решения первой и второй задач (точки
(С1, T1) и (С2, T2)) на плоскость C0 0 T, получим заштрихован-
ную на рисунке 12 оценку (понятно, что в дискретной задаче
возможно конечное множество вариантов) множества возмож-
ных комбинаций максимальных резервов и сроков. •




46
T

T1 = 9



T2 = 5


C0
0 C1 = 33,2 C2 = 70

Рис. 12. Множество допустимых комбинаций
максимальных резервов и сроков


Выше мы описали методы решения задач минимизации
максимальных резервов центра (времени завершения проекта),
которым соответствуют две точки на рисунке 12. Более общей
является задача перечисления всех вариантов, которые имеют
Парето-эффективные оценки продолжительности и резервов. В
еще более общем случае динамика финансового баланса цен-
тра может оцениваться не только величиной максимального
резерва, а некоторым функционалом, отражающим приорите-
ты центра.
Рассмотрим методы решения задачи минимизации резерва
при условии, что определен директивный срок Т реализации
всех работ (проектов реформирования). Примем сначала, что
продолжительности ?i всех работ одинаковы (без ограничения
общности примем их равными 1).
Пусть определено число работ nk, выполняемых в каждом
периоде k = 1?T (очевидно, что 1? nk ? n-T, где n – число работ
региональной программы). В этом случае остается справедли-
вым правило приоритета работ, согласно которому работы
назначаются в очередности возрастания ci (доказательство
аналогично доказательству для последовательной цепочки
работ). Таким образом, задача сведена к определению числа
47
работ nk, выполняемых в k-ом периоде. Для ее решения приме-
ним метод динамического программирования.
Построим сеть на плоскости. По оси ординат отложим пе-
риоды k = 1, T . По оси абсцисс отложим числа Nk – число
работ, выполненных за первые k периодов, k ? Nk ? N. Точкам с
координатами (k, Nk) соответствуют вершины сети. Из вершин
(k-1, Nk-1), k = 1?T, идут дуги ко всем вершинам (k, Nk) таким,
что Nk > Nk-1. Заметим, что каждой дуге (Nk-1, Nk) соответствует
вполне определенное множество Q(Nk-1, Nk) работ, которые
выполняются в k-ом периоде, а именно, это работы с номерами
от Nk-1,+1 до Nk включительно. Обозначим
N k ?1
? ? ? q cq
D(Nk-1) =
q =1
средства, поступившие в Центр к периоду (k-1) включительно
в результате выполнения первых Nk-1 работ,
Nk
C (N k ?1 , N k ) = ? cq
N k ?1 + 1
средства, которые необходимо зарезервировать Центру для
того, чтобы выполнить работы с номерами от (Nk-1,+1) до Nk
включительно в периоде k. Примем разность
L(Nk-1, Nk) = C(Nk-1, Nk) - D(Nk-1)
за длину дуги (Nk-1, Nk).
Заметим, что любому пути в сети, соединяющему вход с
выходом однозначно соответствует некоторый план реализа-
ции проекта, и наоборот.
Построенная модель позволяет решить ряд задач оптими-
зации плана реализации проекта. Так, поставленная выше
задача определения минимального резерва, при условии вы-
полнения всех работ за время Т сводится к определению пути в
сети, соединяющем начальную вершину с конечной, у которо-
го максимальная длина дуги минимальна.
Пример 5. Пусть имеются четыре работы, данные о кото-
рых представлены в таблице 7.
48
Таблица 7
№ 1 2 3 4
10 10 20 40
Ci
20 25 30 90
Pi

Примем Т = 4. Сеть возможных вариантов выполнения работ
представлена на рисунке 13. Заметим, что мы получаем опти-
мальные планы выполнения работ для любого Т. Так при Т = 3 в
оптимальном плане в первом периоде выполняется первая рабо-
та, во втором – вторая и третья, а в третьем – четвертая (мини-
мальная величина резерва равна 10). При Т = 2 в первом периоде
выполняется первая и вторая работы, а во втором – третья и
четвертая. Пути, соответствующие оптимальным планам, выде-
лены на рисунке 13 толстыми линиями.

4.1 4.2 4.3 4.4
(-35) (-35) (-35)
(50)
(80)
(15) (15)
3.1 3.2 3.3

(-25)
(40)

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

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

ОГЛАВЛЕНИЕ

Следующая >>