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

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

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

Определить xi , i  1, n , максимизирующееa x ,(2.2)c x  R ,(2.3)b x(2.4)i iiпри ограниченияхi iii i W1 ,iгде bi - степень влияния i -го проекта.Если проект i  Qk , k  1,9 , тоbi  iWk xi ,98где  i ci xi; Wk - степень влияния проекта k -го типа (на единицу стоимоcx j jсти программы), т.

е. k  Н , или С, или B.Неравенство (2.4) принимает видc w x  W c xik i1ii iiили c  x  0,kiQkik i(2.5)где k  Wk  W1 .Задача (2.2), (2.3), (2.5) является задачей целочисленного линейногопрограммирования. Опишем приближенный алгоритм и решения на основеметода множителей Лагранжа.Вычислим лангранжиан: ( , x)   (ai   ci  k ) xi ,(2.6)k iQkгде  - множитель Лагранжа.Заметим, что при фиксированном  задача максимизации (2.6) приограничении (2.3) является задачей о ранце.

Будем ее решать приближеннона основе метода «затраты – эффект». Эффективность проекта i  Qk при заданном  определяется выражениемqi ( x) ai  ci  k ai   k .ciciЗадача свелась к определению  , при котором достигается минимумвеличины:N ( )  max L( , x) .xЭту задачу можно решить простым перебором (например, делением отрезка возможных значений  пополам), учитывая, что N ( ) - выпуклаяфункция λ.99Пример 10. Возьмем проекты из примера 9. Данные о величинах ai , ci , k и q1 (0) приведены ниже (величины ci  k умножены на 100).i123456ai1221610149cici  k5101510559060-7,50-22,5-22,5qi (0)43,532,521,5Возьмем R  30 .1 шаг.

  0 .В программу включаются проекты 1, 2, 3. Вычисляем:1   2  3   4  342,5  0 .2 шаг.   0,05 .Значения qi (0,05) приведены ниже.iqi (0,05)1-9,52-4,533,3754053,12562,625В программу включаются проекты 3, 5 и 6 с затратами 25.3 шаг. Берем   0,02 .Значения qi (0,02) приведены ниже.iqi (0,02)10,220,333,1542,552,4562,45В программу входят проекты 3, 4 и 5 с затратами 30 и эффектом 20.Это решение является оптимальным. Действительно, ни один из первых двухпроектов не может входить в программу.Если ректорат и руководитель программы решили пойти на среднийуровень риска, то значения Δk меняются, то есть уменьшаются на W2 –W1 = = 0,48-0,06 = 0,42 (на единицу стоимости). В этом случае, как легко про-100верить, все проекты будут иметь отрицательные Δk и в программу войдутпервые три проекта с эффектом 39, что значительно больше, чем 20.2.5.

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

В качестве критерия оптимальности примем величинуупущенной выгоды, которую определим как   aiti ,iгде ti – момент завершения мероприятия i.Сначала необходимо проверить финансовую реализуемость программы. Для этого построим правосдвинутый план реализации (все мероприятиязавершаются в момент T завершения всей программы) и интегральный график его финансирования (ИПГ).Условие финансовой реализуемости программы: интегральный правосдвинутый график финансирования должен быть не выше ИГФ в любоймомент времени.Задача является сложной задачей оптимизации, не имеющей эффективных точных методов решения. Поэтому предложим эвристический алгоритм,в основе которого лежат правила приоритета мероприятий.Чтобы обосновать предлагаемые далее правила приоритета мероприятий рассмотрим две частных ситуации.1 ситуация.

Интегральный график финансирования такой, что мероприятия могут выполняться только последовательно. Получаем известнуюзадачу определения последовательности выполнения мероприятий, миними-101зирующую упущенную выгоду. Доказано, что в этом случае оптимальнымявляется выполнение мероприятий в очередности убывания приоритетов:i aii,где  i - продолжительность мероприятия i .2 ситуация. Финансирование ведется по периодам, причем каждое мероприятие может быть полностью выполнено в одном периоде (τi ≤ Ѳ, гдеѲ – длительность одного периода). В этом случае решение, близкое к оптимальному, получается на основе метода «затраты - эффект», то есть выполнения мероприятий в очередности приоритетов:qi ai, i  1, n .ciИтак, мы имеем два правила приоритета мероприятий. В работе [17]предложен эвристический алгоритм, в котором предлагается линейная комбинация этих правил:pi      ri  1   )qi ,где 0    1.Величина α выбирается произвольно, что может привести к потере рядавариантов.

Предлагаем рассмотреть все варианты приоритетов (их число непревышает 1  cn2 ( cn2 - число сочетаний из n по 2).Для определения этих приоритетов для каждой пары мероприятийопределим граничное значение i из уравнения ri  (1   )qi   ri  (1   )qi .Получаем (если qi > qj): ij qi  q j(rj  ri )  (qi  q j ).Если qi = q j , то приоритет больше у мероприятия с большим r, независимо от величины α. При переходе α граничных точек  ij происходит сменаприоритетов.102Пример 11. В программу входят четыре проекта, данные о которыхприведены ниже.iaiciiqiri1124831,5215672,52,23105422,543331,03Примем продолжительность программы T = 12 месяцев, причем ИГФтакой, что вначале поступает половина средств, т.

е. 9 единиц, а вторая половина поступает через 3 месяца. Проверяем финансовую реализуемость программы. Правосдвинутый интегральный график приведен ниже в виде таблицы. Там же приведен ИГФ (интегральный график финансирования).123456ИГФ99918 18 18ИПГ0000410Программа финансово реализуема.t718108181091815101818111818121818Определяем приоритеты мероприятий, вычисляя граничные значения  ij :12 3 2q1  q20,50,5 0,5 ; 0,42 ; 13 11(r2  r1)  (q1  q2 ) 0,7  0,5 1,214  23 22 0,57 ,1,5  2 3,50,50,51,51,5 0,63 ,  24  0,65 ,0,3  0,5 0,80,8  1,5 0,8 3411 0,67 .0,5  1 1,5Имеем:0    0,42 : 1  2  3  4 ; 0, 42    0,5 : 2 1  3  4 ;0,5    0,57 : 2  3 1  4 ; 0,57    0,63 : 2  3  4 1 ;0,63    0,65 : 3  2  4 1 ; 0,65    0,67 : 3  4  2 1 ;1030,67    1 : 4  3  2 1 .Вариант 1.

Приоритеты мероприятий 1  2  3  4 .1 шаг. Строим ИПГ без мероприятия 1.1904tИГФИПГ 1ГФ 1290439044180451804618647186481864918114101814411181441218144Имеем t1  8 , t1  a1  96 .2 шаг. Строим ИПГ без мероприятия 2 с учетом финансирования мероприятия 1.tИГФ 1ИПГ 3,4ГФ 2150025003500414065140661466714668146691456101486111486121486Имеем t2  10 , t2  a2  150 .3 шаг. Строит ИПГ без мероприятия 3 с учетом финансирования мероприятий 1 и 2.1505tИГФ 3,4ИПГ 3ГФ 325053505414055140561405714058140591405101438111438121438101812611181261218126Имеем t3  4 , t3  a3  40 , t4  6 , t4  a4  18 .Упущенная выгода равна 1  304 .Вариант 2.

Приоритеты мероприятий 2  1  3  4 .1 шаг. Строим ИПГ без мероприятия 2.tИГФИПГ 2ГФ 2190629063906418065184661846718468184691896104Имеем t2  7 , t2  a2  105 .2 шаг. Строим ИПГ без мероприятия 1 с учетом финансирования мероприятия 2.tИГФ 2ИПГ 3,4ГФ 3130023003300Имеем t1  11,4120451204612047120481204912541012841112841212184101812611181261218126t1  a1  132 .3 шаг. Вычисляем t3  7 , t3  a3  70 .

t4  3 , t4  a4  9 .Упущенная выгода равна 316.Вариант 3. Приоритеты мероприятий 2  3  1  4 .1 шаг. Строим ИПГ без мероприятия 2.19064ИГФ18ИПГ 20ГФ 26Имеем t2  7 , t2  a2  105 .t2906390651846618467184681846918962 шаг. Строим ИПГ для мероприятий 1 и 4 с учетом финансированиямероприятия 2.tИГФ 2ИПГ 1,4ГФ 3130023003300412055124561245712458124591245Имеем t3  7 , t3  a3  70 .Вычисляем t 1  11, t1  a1  132t4  3 , t4  a  9 .4Упрощенная выгода равна 3  316 .Вариант 4. Приоритеты мероприятий 2  3  4  1.101275111275121275105Первые два типа совпадают с вариантом 3, то есть t2  t3  7 . Далеетакже имеем t1  11, t4  3 .

Упущенная выгода также равна 316.Вариант 5. Приоритеты мероприятий 3  2  4  1.1 шаг. Строим ИПГ без мероприятия 3.1400tИГФ 3ИПГ 1,4ГФ 224003400413065134661346713468134691346101376111376121376Имеем t2  10 , t2  a2  150 ; t4  3 , t4  a  150 ; t1  11, t1  a1  132 .4Упрощенная выгода равна 5  331 .Вариант 6. Приоритеты мероприятий 3  4  2  1.1 шаг. Строим ИПГ без учета мероприятия 3.110tИГФ 3,4ИПГ 1ГФ 2210310410065104661046710468104691046101046111046121046Имеем t2  10 , t2  a2  150 ; t1  11, t1  a1  132 .Упущенная выгода равна 6  331.Вариант 7.

Приоритеты мероприятий 4  3  2  1.1 шаг. Строим ИПГ без мероприятия 4.tИГФ 3,4ИПГ 1ГФ 21903290339034180351843618103718103818103918153101815311181531218153Имеем t4  3 , t4  a4  9 .Далее вычисляем t3  4 , t3  a3  40 , t2  10 , t2  a2  150 , t1  11,t1  a1  132 .106Упущенная выгода 7  331, что совпадает с вариантами 5 и 6.

Сравнивая, получаем лучший вариант 1 с величиной упущенной выгоды 304.Выше предполагалось, что мероприятие не начинается до тех пор, покане получены все средства, необходимые для его реализации. Это оправдано вусловиях нестабильного финансирования. Однако если есть гарантии поступления средств, то можно начинать мероприятие на имеющиеся средства.Это позволяет улучшить решение. В этих условиях хорошие результаты даетприменение метода «затраты - эффект» при дополнительном условии началамероприятий не позже моментов позднего начала ( T   i ).Описание алгоритмаВыделяем множество мероприятий М, у которых продолжительностьбольше интервала между поступлениями средств. Для этих мероприятийстроится интегральный правосдвинутый график финансирования.Применяем метод «затраты - эффект», начиная с первого периода.

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

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