интересно
Предыдущая | Содержание | Следующая

Задача минимизации упущенной выгоды

После того, как сформирована программа развития отрасли, то есть выбрано множество проектов, реализация которых обеспечивает достижение поставленных целей, возникает задача построения календарного плана реализации программы. Дело в том, что в условиях дефицита финансовых ресурсов нет возможности вести одновременно реализацию всех проектов программы. Необходимо выбрать первоочередные , реализация которых обеспечивает наибольший эффект. Реализация остальных проектов отодвигается на более поздние сроки. Очевидно, что сдвиг проектов на более поздние сроки приводит к уменьшению эффекта или, как говорят, к упущенной выгоде. Желательно разработать такой план реализации программы, при котором упущенная выгода минимальна. Рассмотрим формальную постановку задачи. Пусть программа состоит из п проектов. Каждый проект будем описывать требуемым объемом финансирования Wi и продолжительностью реализации ii . Величина ii определяется максимальным объемом средств ai , который можно освоить в единицу времени, то есть ii = Wi /a .[. Примем, что задержка срока реализации проекта на единицу времени (например, на месяц) приводит к упущенной выгоде, которая равна Ci . Известны возможные объемы финансирования программы в зависимости от времени, то есть известно, что в k-ом периоде объем финансирования составит Nk , к = 1, р. Задача заключается в определении графиков финансирования проектов так, чтобы упущенная выгода

(ti - момент завершения i-го проекта) была минимальной. Эта задача была поставлена в работе [18], где предложен эвристический алгоритм ее решения. В основе алгоритма лежит упорядочение проектов по убыванию приоритетов qi = ci /wi . Там же приведен пример, показывающий, что это правило не всегда дает оптимальное решение. Рассмотрим приближенный алгоритм решения задачи.

Обозначим xik - объем финансирования i-го проекта в k-ом периоде. Выпишем ограничения на допустимые значения {xik }. Ограничения на заданные объемы финансирования по периодам

Ограничения на допустимый объем финансирования i-го проекта в k-ом периоде

Напомним требование выполнения полного объема работ по проектам:

Ограничения (3.1) - (3.3) это классические ограничения транспортной задачи. Условия ее разрешимости очевидны:

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

Специфику задачи определяет вид целевой функции. Действительно, момент завершения проекта ti равен периоду ki такому, что

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

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

и, соответственно, критерий оптимальности примет вид

Эффективных точных методов решения задачи (3.1) - (3.4) не известно. Ниже дается описание приближенного алгоритма. Предварительно для каждого проекта i определим последовательность чисел

где [x ] - целая часть x . Другими словами, мы разбиваем ось времени на отрезки длинны ti . При этом dik определяет номер отрезка, которому принадлежит период k . Так, если ti = 3, то первые три периода имеют

Лемма.

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

Значения dik приведены в таблице

3.2, а значения cik транспортной задачи приведены в таблице 3.3.

Транспортная сеть, в которой показаны только дуги с ненулевыми финансовыми потоками приведена на рис. 3.1.

Величина критерия С оценочной задачи (3.6) - (3.8) равна 253/5. Мы видим, что в полученном решении проект 1 завершается в четвертом периоде, проект 2 - в третьем, а проект 3 - во втором. Это допустимое решение для задачи минимизации упущенной выгоды с величиной упущенной выгоды

Таким образом отклонение полученного решения от оптимального не превышает 2 единицы, поскольку оценку снизу 253/5 можно заменить на 26 в силу целочисленности значений упущенной выгоды. Для того, чтобы получить оптимальное решение применим метод ветвей и границ. Для этого разобьем множество всех решений на два подмножества. В первом подмножестве проект 1 завершается в четвертом периоде, а во втором - раньше четвертого периода. Для первого подмножества мы уже имеем оптимальное решение со значением F = 28, поскольку второй проект не может завершаться раньше третьего периода, а третий - раньше второго.

Оценим второе подмножество. Для этого нужно решить транспортную задачу, исключив дугу (1, 4), соответствующую выполнению проекта 1 в четвертом периоде. Оптимальное решение этой задачи приведено на рис. 3.2.

Величина критерия оценочной задачи равна 271/5 или 28 с учетом целочисленности . Следовательно, полученное выше решение не хуже, чем оптимальное решение во втором подмножестве, а значит является оптимальным.

В рамках рассмотренного подхода можно учесть и ограничения на моменты начала и завершения проектов а также запрещения на выполнение проекта в определенных периодах. Для этого достаточно оставить в транспортной сети только допустимые дуги (i , j ) (проект i может выполняться в периоде j ).

Пример 3.2. Пусть в задаче, рассмотренной в примере 3.1 имеются дополнительные ограничения. А именно, проект 3 может начинаться только со второго периода, а проект 1 должен завершаться не позже третьего периода. График финансирования имеет вид: N1 = 6, N2 = 9, N3 = 10, N4 = 3. Так как матрица затрат (таблица 3.3) не изменилась, то решаем транспортную задачу исключив из сети дугу (3, 1), так как проект 3 не может выполняться в первом периоде, и дугу (1, 4), так как проект 1 должен завершиться не позже третьего периода. Оптимальное решение задачи приведено на рис.3.3.

Имеем величину оценки снизу C = 9 + 12 + 62/3 = 272/3, или 28. Так как первый проект завершается в третьем периоде, второй также в третьем, а третий - в четвертом, то величина упущенной выгоды F = 3Ч3 + 4×3 + 2×4 = 29. Погрешность полученного решения составляет 29 - 28 = 1. Покажем, что полученное решение является оптимальным. Для этого заметим, что первый проект не может быть завершен во втором периоде, поскольку в этом случае в третьем периоде образуется избыток финансовых ресурсов. Третий проект может завершиться в третьем периоде, но тогда второй проект завершится в четвертом периоде, что приведет к росту упущенной выгоды на две единицы.

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

где Di - желательный срок завершения i-го проекта, 1[x ] = 1, если ti > Di и 0 в противном случае. Для того, чтобы сформулировать оценочную задачу для этого случая определяем числа dik по аналогии с вышеописанным случаем, принимая за начальный период (Di + 1), то есть dik=0 если k Ј Di и

Доказательство этого факта проводится по аналогии с доказательством леммы 3.1.

Таким образом мы получаем оценочную задачу (3.6) - (3.8), решение которой дает приближенное решение исходной задачи с оцениваемой погрешностью.

Пример 3.3. Примем, что все ai = 1. В этом случае объем финансирования проекта wi совпадает с минимальной продолжительностью его реализации ti . Пусть имеются четыре проекта, данные о которых приведены в таблице 3.4.

Оптимальное решение оценочной задачи выделено жирным шрифтом с подчеркиванием. Имеем C = 12, а величина упущенной выгоды для соответствующего допустимого решения F = 24. Действительно, t1 = 5,

Разобьем множество всех решений на два подмножества. В первом проект 2 завершается не раньше 7-го периода, а во втором - не позже 6-го периода. Рассмотрим первое подмножество. Так как проект 2 завершается не раньше 7-го периода, то в оптимальном решении транспортной задачи мы можем все работы по проекту, выполняемые во втором и четвертом периодах передвинуть на более поздние периоды, освобождая место для других проектов. Получим решение, приведенное в таблице 3.6.

Для этого решения C = 17, F = 20.

Для второго подмножества клетки (2, 7) и (2, 8) запрещены. Оптимальное решение транспортной задачи приведено ниже.

Имеем C = 13, F = 20.

Выбираем второе подмножество с меньшей оценкой. Это подмножество также разбиваем на два. В первом проект 2 завершается точно в 6-ом периоде, а во втором - не позже 5-го периода. Оптимальное решение оценочной задачи для первого подмножества приведено в таблице 3.8, а для второго - в таблице 3.9.

Имеем C = 16 и F = 16, то есть полученное решение является оптимальным в данном подмножестве.

Имеем C = 15 и F = 15, то есть полученное решение является оптимальным в этом подмножестве.

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

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

что соответствует минимизации максимальной упущенной выгоды. Эта задача легко сводится к параметрической транспортной задаче. В качестве параметра выступает величина критерия F. Дадим описание алгоритма.

Из условия Оставляем в транспортной сети только дуги (i , j ), такие что j Ј bi и определяем максимальный поток в сети при ограничении

для всех i ,

то получено оптимальное решение задачи. В противном случае увеличиваем F до такой величины, при которой в сети появляется хотя бы одна новая дуга. Очевидно, что за конечное число шагов будет получено оптимальное решение задачи.

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

Берем F = 6. В таблице 3.10 знаком (¥) указаны запрещенные клетки. Определяем поток максимальной величины в соответствующей транспортной сети. Единичные потоки по дугам отмечены в таблице 3.10.

Максимальный поток равен 8, то есть все проекты выполняются.

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

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

сроки завершения проектов t ip , применяя известные алгоритмы расчета

сетевых графиков [16]. Очевидно, что величина упущенной выгоды

На основе оценки (3.13) можно предложить метод ветвей и границ для решения задачи. Примем, что проекты имеют номера такие, что

характеризует в определенной степени

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

Пример3.5. Пусть сетевой график из четырех проектов имеет вид, показанный на рис. 3.4. В вершинах указаны номера проектов (верхнее число) и минимальные продолжительности (нижнее число) Данные о проектах приведены в таблице 3.11.

Пусть уровень финансирования программы N = 6 в каждый период. Определим оценку снизу величины упущенной выгоды. Для этого определим ранние времена завершения проектов:

В озникла конфликтная ситуация. Рассматриваем два варианта.

Вариант 1. Проект 1 финансируется при максимальном уровне финансирования. и меем финансирование первого проекта на уровне u1 = 4, а второго - на остаточном уровне u2 = 2. Через 5 дней проект 1 завершается. К этому моменту остается невыполненным проект 2 в объеме

Имеем для первого варианта

Оценка величины упущенной выгоды составит

Вариант 2. Проект 2 финансируется на максимальном уровне, то есть u2 = 6, u1 = 0. Через 3 дня проект 2 завершится. Имеем для второго варианта

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

2 шаг. Поскольку проект 1 выполнен, то можно выполнять два проекта - второй и третий. В данном случае также возникает конфликтная ситуация. Рассматриваем два варианта.

Проект завершается в момент

Вариант 2. Проект 3 выполняется на максимальном уровне финансирования, то есть u3(5) = 5, u2(5) = 1. Первым завершается проект 3 (через два дня). За это время проект 2 выполнен в объеме 2, и остался невыполненным объем 6, требующий одного дня для завершения. Имеем

Выберем вариант 1 с минимальной оценкой F(1; 2) = 169.

3 шаг. Можно выполнять третий и четвертый проекты. Так как a3 + a4 > 6, то возникает конфликтная ситуация. Рассматриваем два варианта.

Проект 3 завершается в

К этому моменту остался невыполненным проект 4 в

объеме 12 - 2 = 10, что требует 2,5 дня. Имеем:

t1p = 5, t p2 = 61/3, t p3 = 81/3, t p4 = 105/6,

F(1; 2; 3) = 60 + 57 + 331/3 + 212/3 = 172. Вариант 2. Проект 4 выполняется при максимальном уровне финансирования, то есть u4(61/3) = 4, u3(61/3) = 2. Проект 4 завершается через 3 дня. К этому моменту остался невыполненным проект 3 в объеме 10 - 2 × 3 = 4, что требует еще 0,8 дня. Имеем

Сравнивая получаем, что лучшим является вариант 1.

Таким образом мы получили оптимальный вариант, согласно которому проекты завершаются в порядке их приоритетов с величиной упущенной выгоды F = 172.

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

Однако, это не является оптимальным решением, поскольку величина упущенной выгоды в этом случае составит