Диссертация (1172887), страница 12

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 12)

Однако метод «затраты – эффект» дает приближенное решение задачи включения мероприятий в программу. При большом числе мероприятий ошибка не значительна, но при малом может быть существенной.В этом случае целесообразно применять точный алгоритм дихотомическогопрограммирования [18].13х5=113х5=02015Рис. 2.3Пример 3. Рассмотрим простой пример, иллюстрирующий сказанное.Имеются три мероприятия, данные о которых приведены ниже.Мероприятие123Затраты4128Эффект12188Затраты н/и41624Эффект н/и123038Пусть   20 . Согласно методу «затраты – эффект» в программу включаются проекты 1 и 2 с затратами 16. Оптимальное решение состоит в том,что в программу включаются проекты 1 и 3 с затратами 12.Взаимозависимые мероприятияЕще один фактор, который следует учитывать, связан с так называемыми взаимозависимыми мероприятиями.

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

2.4 приведен пример графа взаимозависимостей из пяти вершин, который является паросочетаемым.1425463Рис. 2.4Для решения задачи возьмем структуру дихотомического представления задачи, такую что вершины, соединенные ребром, рассматриваются нанижних уровнях дерева дихотомического представления (рис. 2.5).79IVIIIIII21543Рис. 2.5Пример 4. Имеются пять мероприятий, данные о которых приведены ниже.iaici1582773964845123Граф взаимозависимостей имеет вид (рис. 2.4). Примем   30 .1 шаг. Рассматриваем мероприятия 1 и 2. Решение приведено ниже.17;716;15005;80121Результаты сведены в таблицу.Объединенное мероприятие012Вариант0716Эффект0715Затраты2 шаг.

Рассматриваем мероприятия 3 и 4. Решение приведено ниже.18;423;10009;6014380Результаты сведены в таблицу.Объединенное мероприятие IIвариантэффектзатраты000184296323103 шаг. Рассматриваем объединенные мероприятия II и мероприятие 5.Решение приведено ниже.112;3 20;7 21;9 35;13008;49,623;1001235IIРезультаты сведены в таблицу.Объединенное мероприятие IIIВариантЭффектЗатраты00011232207321942310535134 шаг.

Рассматриваем объединенное мероприятие III и объединенноемероприятие I. Решение приведено ниже.216;1528;1836;22---17;719;1027;1428;1630;17-0012;320;721;923;1035;13012345IIIIОптимальное решение определяется клеткой (35;13). Ей соответствуетвключение в программу проектов 3, 4 и 5 с затратами 13.Рассмотрим общий случай.81Парграфом называется подграф графа, который является паросочетаемым. Парграф с максимальным числом вершин называется максимальнымпарграфом.Идея алгоритма состоит в следующем. Удалим из графа взаимозависимостей некоторое число вершин так, чтобы получить парграф.

Далее, как и вслучае многоцелевых мероприятий, рассматриваем все варианты включенияв программу удаленных вершин. Для каждого варианта решаем задачу дляслучая парграфа. Из всех вариантов выбираем лучший.Естественно, желательно получить парграф с максимальным числомвершин, то есть максимальный парграф.Задача. Задан граф 6. Определить максимальный парграф.Обозначим xi = 1, если вершина i принадлежит максимальному парграфу, xi = 0 в противном случае. Задача заключается в максимизацииxiприiограничениях xixjQij 1 , i  1, n , где Qi - множество вершин, смежных с вер-шиной i . Задача является сложной задачей дискретной оптимизации, которая не имеет эффективных точных методов решения.Опишем простой эвристический алгоритм.1 шаг. Для каждого ребра графа определяем число вершин rij , смежныхс граничными вершинами ребра.2 шаг.

Определяем ребро (i, j ) с минимальным rij и включаем его впарграф.3 шаг. Удаляем все вершины, смежные с ребром (i, j), и повторяем шаги 1, 2, 3.Пример 5. Рассмотрим граф (рис. 2.6).821422535641346Рис. 2.6Легко убедиться, что ребра (1,2) и (3,4) имеют минимальные r12  r34  1.Включаем, например, ребро (1,2) в парграф, удаляя вершину 6. Получаем парграф (см. рис.

2.4). Поскольку удалена одна вершина, то необходиморассмотреть два варианта (берем данные примера 4).1 вариант. Мероприятие 6 не входит в программу. Этот случай былрассмотрен в примере 4. Минимальные затраты равны 13.2 вариант. Мероприятие 6 входит в программу. Примем a6  4 , c6  2 .Значения di 6 , i  1,5 , указаны на рис. 2.6. Добавляем к эффектам вершин дополнительные эффекты di 6 , i  1,5 .Корректируем целевую установку   30  a6  26 .1 шаг.

Рассматриваем мероприятия 1 и 2. Решение приведено ниже.112;719;15007;80121Результаты сведены в таблицу.Объединенное мероприятие IВариантЭффектЗатраты000112721915832 шаг. Рассматриваем мероприятия 3 и 4. Решение приведено ниже.19;422;100013;60143Результаты сведены в таблицу.Объединенное мероприятие II0123Вариант0913 22Эффект04610Затраты3 шаг. Рассматриваем объединенное мероприятие II и мероприятие 5.Решение приведено ниже.Объединенное мероприятие III115;3 24;7 28;9 37;13009;40113;6 22;105II234 шаг.

Рассматриваем объединенные мероприятия I и III. Решение приведено ниже.219;15 34;18112;700-27;10 36;1415;324;7----28;9 37;13IIIIОптимальное решение определяется клеткой (37;13) с затратами13+2 = 15. Выбираем первый вариант.842.4. Учет рисковКаждое мероприятие программы имеет определенный риск его невыполнения. То есть неполучение планируемого эффекта. На практике рискиоценивают в качественных шкалах. Наиболее распространены двухбалльная(низкий риск и высокий риск) и трехбалльная (низкий, средний и высокийриск) шкалы.

Ограничимся рассмотрением двухбалльной шкалы. Одним изспособов уменьшения риска программы является ограничение на финансирование высокорисковых мероприятий. Рассмотрим постановку соответствующей задачи.Обозначим Q – множество высокорисковых мероприятий института(номер института опускаем), Rв – ограничение на финансирование высокорисковых мероприятий.Описание алгоритма. Применяя метод «затраты - эффект», строимграфик (таблицу потенциала) отдельно для низкорисковых и высокорисковых мероприятий.На основе полученных графиков (таблиц) определяем зависимость минимального объема финансирования низкорисковых мероприятий от получаемого от них эффекта и минимального объема финансирования высокорисковых мероприятий от получаемого от них эффекта.Решаем задачу с двумя переменными (эффект, получаемый от низкорисковых мероприятий, и эффект, получаемый от высокорисковых мероприятий) по критерию минимизации затрат на получение того или иного суммарного эффекта.Пример 6.

Имеются 7 мероприятий, данные о которых приведеныниже.iaici1310272636234936541765227125585Первые три проекта являются высокорисковыми. Поставим задачу увеличить уровень компетентности на 20. При этом финансирование высокорисковых проектов не должно превышать Rв = 50.1 шаг. Решаем задачу определения минимальных затрат в зависимостиот эффекта для высокорисковых мероприятий. Решение приведено ниже.ВариантЭффектЗатраты0001310210362 шаг. Решаем задачу определения минимальных затрат для низкорисковых мероприятий.

Решение приведено ниже.ВариантЭффектЗатраты000193621353318754301303 шаг. Решаем задачу определения минимальных суммарных затрат нафинансирование увеличения эффекта на 20. Решение приведено ниже.210;36 19;72 23;8913;10009;3601-12;46 16;63 21;85-13;53 18;75 30;130RвRн234Оптимальное решение определяется клеткой (21;85). Ей соответствуетвключение в программу высокорискового проекта 1 и низкорисковых проектов 4, 5 и 6.Описанный алгоритм нетрудно обобщить на качественные шкалы с тремя и более градациями.

Рассмотрим трехбалльную шкалу риска: малый (1),средний (2) и высокий (3). Обозначим Qk – множество проектов с уровнемриска k , Rk – ограничение на финансирование проектов Qk , k  2,3 .86Описание алгоритма совпадает с приведенным выше для двухоценочных шкал. Отличие в том, что решаются три независимые задачи отдельнодля каждого множества Qk , k  1, 2,3. Далее на этапе 3 решаем задачу с тремяпеременными Yk , k  1, 2,3 , где Yk – величина финансирования проектовмножества Qk . Задачу решаем методом дихотомического программирования.Пример 7.

Возьмем данные примера 6. Пусть Q1  (5,6,7) , Q2  (3,4) ,Q3  (1,2) . Примем R2 = 40, R3 = 30 .I этап. Строим графики (таблицы) потенциала отдельно для множествQk, k=1, 2, 3.Таблицы потенциала приведены ниже.Низкий рискВариантY1A10001174239939421Средний рискВариантY2A20001236Высокий рискВариантY3A30001104II этап. Решаем задачу минимизацииY1 ( A1 )  Y2 ( A2 )  Y3 ( A3 )при ограниченииA1  A2  A3  20.Задачу решаем методом дихотомического программирования.87329; 436; 2313; 6010; 4018; 8215; 62-13; 107; 2712; 4924;104004; 179; 3921; 940123(2,3)1Оптимальное решение определяется клеткой (24;104).

Ей соответствуетвключение в программу всех проектов с низким уровнем риска и проекта 1 свысоким уровнем риска.Выше уже отмечалось, что метод «затраты - эффект», применяемыйпри построении таблицы потенциала, при малом числе проектов может давать большую погрешность. В этих случаях целесообразно применить точный метод дихотомического программирования. Рассмотрим его на предыдущем примере.I этап1 шаг. Решаем задачу минимизации17 x5  22 x6  55x7при ограничении4x5  5x6  12x7  20.Решение приведено ниже.ВариантY1A1000117422253399455122 шаг.

Характеристики

Список файлов диссертации