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

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

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

повышение компетентности персонала четвертого института доуровня 2.Для повышения компетентности персонала вуза до уровня 3 оптимальное решение определяется клеткой (3;39), которой соответствует вариант (3,2, 1, 2), т. е. повышение компетентности ППС института 1 до уровня 3, институтов 2 и 4 до уровня 2 и сохранение компетентности института 3 науровне 1.Описанный выше алгоритм не учитывает ряда возможных ситуаций.Выше предполагалось, что для каждого института имеется свое множество70мероприятий по повышению уровня компетентности ППС и эти множестване пересекаются (одноцелевые мероприятия).

В действительности могут существовать так называемые многоцелевые мероприятия, реализация которыхдает эффект сразу для нескольких институтов. К таким мероприятиям относятся, например, организация конференций, приглашение ведущих ученых слекциями и др. Рассмотрим два подхода к решению задачи при наличии многоцелевых мероприятий.1 подход. Если число многоцелевых мероприятий не велико, то можнорассмотреть все варианты вхождения в программу многоцелевых мероприятий (таких вариантов 2q , где q – число многоцелевых мероприятий). Прификсированном варианте вхождения в программу многоцелевых мероприятий получаем рассмотренную выше задачу с одноцелевыми мероприятиями.Из всех вариантов затем выбирается лучший.Пример 1. Дадим иллюстрацию подхода на примере двух институтов.Данные об одноцелевых мероприятиях по повышению уровня компетентности приведены ниже.Институт I1263Затратын/и223358102,725101424Эффектн/и61525Мероприятие Затраты Эффект ЭффективностьЭффектн/и6Институт II1362Затратын/и323689101,51,2917Мероприятие Затраты Эффект Эффективность71Имеются также два многоцелевых мероприятия, данные о которых приведены ниже.Мероприятие45ПримемЗатраты65Эффект (институт I)97Эффект (институт II)710A1  50 , A2  70 , Y0  40 , 1  10 , 2  30 для обоих институ-тов.Поскольку имеются два многоцелевых мероприятия, то необходиморассмотреть четыре варианта их включения в программу.Вариант 1.

Ни одно из многоцелевых мероприятий не входит в программу. Определяем минимальные затраты S1 j , j=1,2,3 для первого института. Имеем S11  3 (экспертная оценка), S12  5 . Оценка 3 не достижима.Определяем минимальные затраты для второго института. Имеем S21  2(экспертная оценка), S22  9 . Оценка 3 не достижима. Для получения комплексной оценки возьмем матрицу (см. рис. 2.2).2;91;2211;121;52;142;71;32;5Получаем, что для сохранения оценки 1 требуется 5 единиц затрат, а длядостижения оценки 2 требуется 7 единиц затрат.Вариант 2.

Многоцелевое мероприятие 4 входит в программу, а мероприятие 5 не входит.Корректируем целевые установки для одноцелевых мероприятий с учетом эффекта от мероприятий 1:- для первого института: 1  10  9  1, 2  30  9  21;- для второго института: 1  10  7  3 , 2  30  10  20 .72Определяем минимальные затраты для первого института: S11  0 , S12  2 ,S13  10 .Определяем минимальные затраты для второго института:,S21  0 , S22  3S23  17 .Подставляя в матрицу комплексного оценивания, получаем:3;17 2;17 3;192;3 1;3 2;51;0 1;0 2;221 1;0 2;23;273;132;103;10Получаем, что для достижения оценки 2 требуется 2+6 = 8 единиц затрат, а для достижения оценки 3 требуется 19 единиц затрат.Вариант 3.

Многоцелевое мероприятие 5 входит в программу, а мероприятие 4 не входит.Корректируем целевые установки для одноцелевых мероприятий с учетом эффекта от мероприятия 5.Для первого института: 1  10  7  3 , 2  30  7  23 .Для второго института: 1  10  10  0 , 2  30  10  20 .Определяем минимальные затраты для первого института: S11  0 ,S 12  2 ,S13  10 . Определяем минимальные затраты для второго института:S21  0 , S22  0 , S23  17 .Подставляем в матрицу комплексного оценивания:3;172;173;193;272;01;02;23;101;01;02;22;101;02;23;102173Для достижения оценки 2 требуется 2+5 = 7 единиц затрат, а для достижения оценки 3 требуется 10+5 = 15 единиц затрат.Вариант 4. Оба многоцелевых мероприятия входят в программу.

Корректируем целевые установки.Для первого института: 1  0 , 2  30  16  14 .Для второго института: 1  0 , 2  30  17  13 .Определяем минимальные затраты для первого института: S11  0 ,S12  0 , S13  5 . Определяем минимальные затраты для второго института:S21  0 , S22  0 , S23  9 .Подставляем в матрицу комплексного оценивания:3;92;93;93;142;01;02;03;51;01;02;02;51;02;03;521Для достижения оценки 2 требуется 11 единиц затрат, а для достижения оценки 3 требуется 5+11 = 16 единиц затрат.Сравнивая все четыре варианта, получаем, что для оценки 2 оптимальными являются первый и третий варианты с затратами 7, а для оценки 3 оптимальным является третий вариант с затратами 15.При большом числе многоцелевых мероприятий метод перебора всехвариантов их вхождения в программу становится трудоемким.2 подход.

Применим метод ветвей и границ с получением нижних оценок на основе метода сетевого программирования И. В. Бурковой [18] Для этого разделим затраты каждого многоцелевого мероприятия произвольным образом на несколько частей по числу институтов, в которых это мероприятиедает эффект. После этого получим задачу с одноцелевыми мероприятиями.74Теорема 1. Решение задачи с одноцелевыми мероприятиями дает оценку снизу для исходной задачи.Задача определения деления затрат многоцелевых мероприятий, прикотором нижняя оценка затрат максимальна, называется обобщенной двойственной задачей.Полученную оценку используем в методе ветвей и границ. При этомпосле каждого ветвления можно попытаться улучшить оценку, корректируяразбиение затрат.

Этот прием в ряде случаев позволяет уменьшить числоветвлений.Пример 2. Возьмем данные предыдущего примера. Поскольку каждоемногоцелевое мероприятие дает эффект для двух институтов, то положимсi  di  hi , где d i - доля затрат для первого института, hi - доля затрат длявторого института. Возьмем d4  d5  3 , h4  3 , h5 = 2.1 шаг.

Решаем задачу для первого института. Таблица потенциала приведена ниже.1263Затратын/и243935152382,78235372,31130Мероприятие Затраты Эффект ЭффективностьЭффектн/и6351021640Для достижения оценки 2 требуется 5 единиц затрат с мероприятиями 1и 4, а для достижения оценки 3 требуется 11 единиц затрат с мероприятиями1, 4, 2, 5.Решаем задачу для второго института. Таблица потенциала приведенаниже.52105Затратын/и24372,35Мероприятие Затраты Эффект ЭффективностьЭффектн/и101775136282691,51438101,222Для достижения оценки 2 требуется 2 единицы затрат (проект2332425), а длядостижения оценки 3 требуется 14 единиц затрат (проекты 5, 4, 1,2).Подставляем в матрицу комплексного оценивания.3;142;173;193;252;21;52;73;131;21;52;72;131;32;53;1121Для достижения комплексной оценки 2 требуется 7 единиц затрат, адля достижения комплексной оценки 3 требуется 13 единиц затрат.

Дляоценки 2 в программу включаются проекты 1 и 2 первого института и проекты (5, 4) или (5, 1) второго института. Это решение не является допустимым,поскольку проект 5 и проект 4 входят в программу второго института, но невходят в программу первого института.Для оценки 3 в программу включаются проекты 1, 4, 2, 5 для первогоинститута и проект 5 для второго института.

Это решение также не являетсядопустимым для исходной задачи. Применяем метод ветвей и границ. Дляветвления выберем проект 5.Делим множество всех решений на два подмножества. В первом подмножестве x5  1, а во втором x5  0 . Оценка первого подмножества ( x5  1) .Корректируем целевые установки с учетом эффектов от проекта 5.Имеем для первого института: 1  10  7  3 , 2  30  7  23 . Для второго института: 1  10  10  0 , 2  30  10  20 .Определяем минимальные затраты для первого института: S12  2 ,S13  8 .Для второго института: S22  0 , S23  12 .76Подставим в матрицу комплексного оценивания.3;122;123;143;202;01;02;23;81;01;02;23;81;02;22;821Для достижения комплексной оценки требуется 2+5 = 7 единиц (проект 1 для первого института и проект 5 для обеих).

Это решение является допустимым для исходной задачи и, следовательно, оптимальным.Для достижения комплексной оценки 3 требуется 8+5 = 13 единиц(проекты 1, 4, 2) для первого института и проект 5. Это решение не являетсядопустимым. Применим операцию корректировки разбиения эффектов на двечасти. Возьмем d4  4,5 , h4  1,5 .

В этом случае для первого института появляется еще одно решение с затратами 15 (проекты 1, 2, 3), для первого института и проект 5 для обеих. Это решение является допустимым, и, следовательно, оптимальным в своем подмножестве. Оценка второго подмножества:( x5  0) .Определяем минимальные затраты для первого института: S11  3 ,S12  6 , S13  14 . Для второго института: S21  2 , S22  6 , S23  20 .Подставляем в матрицу комплексного оценивания:3;202;233;263;342;61;92;123;201;21;52;83;161;32;63;1421Для достижения оценки 2 требуется 8 единиц, а для достижения оценки 3 требуется 20 единиц.

В обоих случаях выбираем первое подмножество.77Дерево ветвлений для оценки 3 приведено на рис. 2.3 (операция корректировки разбиения эффекта четвертого проекта показана пунктиром). Заметим,что применение операции корректировки позволило ограничиться всего одним ветвлением.

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

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