Автоматика и телемеханика, № 3, 2014
Управление в социально-экономических, медико-биологических системах
© 2014 г. В.Н. БУРКОВ, д-р техн. наук, И.В. БУРКОВА, д-р техн. наук (Институт проблем управления им. В.А. Трапезникова РАН, Москва)
МЕТОД СЕТЕВОГО ПРОГРАММИРОВАНИЯ В УПРАВЛЕНИИ ЦЕЛЕВЫМИ ПРОГРАММАМИ
Рассматривается задача оптимизации программ по стоимости. Состояние программы определяется по нескольким целям (критериям) на основе системы комплексного оценивания. Для каждой цели существует множество проектов, дающих вклад в ее достижение. Ряд проектов дают вклад в несколько целей (многоцелевые проекты). Для решения задачи предложены два метода. Первый основан на переборе всех вариантов включения в программу многоцелевых проектов. Второй основан на методе сетевого программирования. Приведены результаты вычислительных экспериментов по сравнению этих методов.
1. Введение
Целевые программы в настоящее время - это основное средство инновационного развития. Одной из важнейших задач является формирование предметной области программы. Эта задача относится к классу задач дискретной оптимизации. Как правило, состояние программы оценивается по нескольким целям (критериям). В региональных программах в качестве таких критериев обычно выступают экономическая эффективность, уровень жизни, экологическая безопасность и др. Методы разработки целевых программ рассматривались в работах В.А. Ирикова, В.Н. Тренева, В.Г. Балашова, С.В. Леонтьева и других авторов [1-3]. В этих работах предполагалось, что для каждой цели существует множество мероприятий, обеспечивающих ее достижение, и эти множества не пересекаются. В этом случае формирование программы декомпозировалась на несколько независимых задач (по числу целей). Для решения каждой задачи применялся метод "Затраты - Эффект" (мероприятия в программу отбирались в порядке убывания эффективностей, т.е. отношения эффекта к затратам).
В действительности существуют так называемые многоцелевые мероприятия (проекты), дающие вклад в несколько целей. Задачи разработки целевых программ с учетом многоцелевых проектов рассматривались в [4]. В этой работе формирование программы сводится к задаче целочисленно-
го линейного программирования (многомерной задаче о ранце). В последние годы большую популярность приобрел метод комплексного оценивания программы на основе матричных сверток [5]. Методы разработки целевых программ на основе систем комплексного оценивания рассматривались в работах Н.Г. Андронниковой, С.А. Баркалова, А.М. Котенко и др. [6, 7]. В этих работах решение задачи заключалось в переборе всех Парето-оптимальных вариантов, обеспечивающих достижение требуемого значения комплексной оценки и решение для каждого варианта многомерной задачи о ранце.
В течение последних десяти лет в Институте проблем управления был разработан новый подход к решению задач дискретной оптимизации - метод сетевого программирования [8, 9]. В статье метод сетевого программирования применяется к решению задачи формирования целевых программ при наличии системы комплексного оценивания и многоцелевых проектов.
2. Постановка задачи
Рассмотрим задачу формирования программы развития региона (либо предприятия, холдинга, корпорации), обеспечивающей требуемое значение комплексной оценки с минимальными затратами. Примем, что задана процедура формирования комплексной оценки программы. Программа оценивается по т критериям. Обозначим через минимальное (граничное) значение г-го критерия, которому соответствует оценка ] (] = 1,4). Таким образом, если значение критерия у7- лежит в полуинтервале ^ уг < ¿¿7+1, то оценка по соответствующему направлению равна 3.
Имеется п проектов - претендентов на участие в программе. Каждый проект характеризуется затратами Ск и показателями эффекта акг вклад к-го проекта в г—й критерий. Примем, что Хк = 1, если к-й проект включен в программу, Хк = 0 в противном случае. Предполагая, что эффекты суммируются, получаем, что увеличение г-го критерия в результате реализации программы составит
Дуг = ^ акгХк, к
а соответствующая оценка по г-му направлению равна
Зг = О (Уг) = в (у° + Дуг) ,
где у0 — начальное значение г-го критерия, в — преобразование численного значения критерия в дискретную шкалу. Суммарные затраты составят
С (х) = ^ Сгхг.
г
Обозначим через К (3) комплексную оценку программы при оценках направлений 3 = (З1, . . . ,Зт).
Задача. Определить множество проектов, обеспечивающих К(3) = Ктреб при минимальных затратах. Задача относится к сложным задачам дискретной оптимизации.
3. Метод решения
Рассмотрим ситуацию, когда для каждого направления г существует свое множество проектов С,)^, г = 1 ,т, причем эти множества не пересекаются. В этом случае алгоритм решения задачи становится существенно проще. 1-й шаг. Решаем т задач о ранце для каждого критерия:
Как известно, решение задачи о ранце при правой части ограничения Лг4 дает оптимальные решения и для всех меньших значений правой части, т.е. для Лгэ, Л^2 и Л^. Обозначим через Б^ минимальные затраты, требуемые для достижения оценки ] по г-му критерию.
2-й шаг. Поскольку структура формирования комплексной оценки является деревом, то решаем задачу, последовательно выполняя для каждой матрицы процедуры комплексного оценивания задачи с двумя переменными.
Для примера рассмотрим задачу формирования целевой программы развития региона. Программа оценивается по трем критериям - экономическая эффективность (Э), уровень жизни (Ж) и экономическая безопасность (Б).
Представляется естественным сначала объединить критерии уровня жизни и экологической безопасности в один агрегированный критерий социального уровня (С). Далее, объединяя социальный уровень с экономической эффективностью, получим комплексную оценку социально-экономического уровня, который обеспечивает анализируемый вариант программы развития. Особенностью иерархической структуры является агрегирование в каждом узле дерева только двух оценок. Это крайне привлекательная особенность. Дело в том, что комплексная оценка должна отражать приоритеты развития региона. Формирование этих приоритетов, а значит, и формирование комплексной оценки должно проводиться первыми лицами (главой администрации, его заместителями, начальниками управлений), т.е. лицами, принимающими решения. Здесь сталкиваемся с чисто психологической проблемой. Человек способен эффективно оценить (соразмерить) только ограниченное число целей и лучше всего, если на каждом шаге оценки приходится сравнивать не более двух критериев. Такое сравнение в случае двух критериев удобно проводить, представляя результаты в виде таблицы (матрицы). Предварительно перейдем к дискретной шкале оценок по каждому критерию, а именно, будем оценивать состояние отрасли по каждому критерию по четырехбалльной шкале: плохо, удовлетворительно, хорошо, отлично, или в числовых оценках - один, два, три, четыре. В таких же шкалах будем оценивать агрегированную и комплексную оценки. В табл. 1 приведен пример свертки критерия "уровень жизни" (Ж) с критерием "экологическая безопасность" (Б).
С (х) = скхк ^ шт
к—^г
при ограничении
к—^г
4 2 со 4 4
3 1 2 3 3
2 1 2 3 3
1 1 1 1 2
Б 1 2 3 4
Как уже отмечалось, эта матрица отражает общественные приоритеты: так, при критическом положении в области экологии и по уровню жизни приоритет отдается обоим критериям. При удовлетворительном положении в области экологической безопасности приоритет имеет показатель "уровень жизни", поскольку состояние с хорошей оценкой по безопасности и удовлетворительной по уровню жизни оценивается как удовлетворительное, а обратная картина (оценка "хорошо" по уровню жизни и "удовлетворительно" по безопасности) оценивается как оценка "хорошо". С ростом уровня жизни приоритет смещается в сторону показателя экологической безопасности, поскольку состояние "отлично" возможно только при оценке "отлично" по показателю безопасности (при этом возможна оценка "хорошо" по уровню жизни). Имея оценку социального уровня, можно построить матрицу свертки для комплексной оценки социально-экономического уровня. Пример такой оценки приведен в табл. 2.
Таблица 2
4 2 со 4 4
3 2 2 3 3
2 1 2 3 3
1 1 1 2 2
^^э 1 2 3 4
Здесь также можно заметить изменение системы приоритетов. При кризисном положении в экономике и обществе приоритет имеют оба показателя -и социальный уровень, и уровень экономической эффективности. При удовлетворительном или хорошем значении этих показателей приоритет смещается в сторону экономической эффективности. Наконец, при высоких оценках (хорошо или отлично) приоритет снова имеет показатель социального уровня. Граничные состояния, отделяющие плохие состояния от удовлетворительных, удовлетворительные от хороших и хорошие от отличных, можно также определять по-разному. Более того, эти границы могут и должны меняться со временем. Так, состояние "плохо" соответствует сегодняшнему состоянию и по экономической эффективности в регионе, и по уровню жизни ее работников, и по уровню экологической безопасности. Состояние "удовлетворительно" может соответствовать средним значениям соответствующих показателей по другим регионам, состояние "хорошо" - лучшим значениям показателей по
регионам, а "отлично" - средним значениям по другим странам в соответствующих направлениях. При росте эффективности экономики и уровня жизни цели могут измениться. Так, состояние "отлично" может соответствовать лучшим значениям показателей в мире.
Описание алгоритма проведем на примере процедуры комплексного оценивания, представленной матрицами (в табл. 1 и 2) и таблицей затрат 5 = {Б^} (табл. 3).
Таблица 3
% \ 1 2 3 4
Б 10 30 40 100
Ж 25 60 90 150
э 40 70 120 200
Рассмотрим матрицу свертки показателей уровня жизни и уровня экологической безопасности (табл. 4). Первое число в каждой клетке соответствует оценке, а второе - затратам, необходимым на получение этой оценки.
Таблица 4
4, 100 2, 125 3, 169 4, 190 4, 250
3, 40 1, 65 2, 100 3, 130 4, 190
2, 30 1, 55 2, 90 3, 120 3, 180
1, 10 1, 35 1, 70 1, 100 2, 160
Б Хж 1, 25 2, 60 3, 90 4, 150
Для каждой оценки выбираем клетку с минимальными з
Для дальнейшего прочтения статьи необходимо приобрести полный текст. Статьи высылаются в формате PDF на указанную при оплате почту. Время доставки составляет менее 10 минут. Стоимость одной статьи — 150 рублей.