Содержание к диссертации
Введение
Глава 1. Задачи информационно-аналитической поддержки управления развитием социальной инфраструктуры территориальных образований РФ 5
1.1. Управление развитием социальной инфраструктуры территориальных образований РФ как объект диссертационного исследования 5
1.2. Математические постановки задач поддержки развития социальной инфраструктуры территориального образования и методы их решения . 27
1.3. Постановка задачи диссертационного исследования 37
Глава 2. Генетический алгоритм оптимизации системы обеспечения муниципального образования сезонной продукцией 42
2.1. Теоретические основы генетических алгоритмов 42
2.2 Математическая постановка исходной задачи 52
2.3. Математическая постановка задачи оптимизации структуры системы обеспечения муниципального образования сезонной продукцией для применения генетического алгоритма 60
2.4. Исследование вычислительной эффективности генетического алгоритма решения задачи развития системы обеспечения муниципального образования сезонной продукцией 64
Выводы 72
Глава 3. Гибридный метод поддержки развития системы обеспечения сезонной продукцией населения муниципального образования 74
3.1 Концепция гибридного метода 74
3.2. Алгоритм расчета суточных лотов-поставок из баз хранения сезонной продукции 88
3.3. Оценка вычислительной эффективности гибридного метода 95
3.4. Альтернативный алгоритм расчета суточных лотов 100
Выводы 109
Глава 4. Математические методы поддержки развития социальный инфраструктуры территориального образования РФ 111
4.1. Концепция математической поддержки решения задач развития социальной инфраструктуры территориального образования РФ 111
4.2. Метод математической поддержки решения задачи развития социальной инфраструктуры муниципального образования 121
4.3. Задача внешнего контура 2 и подходы к ее решению 130
4.4. Стратегический план развития социальной инфраструктуры территориального образования 134
4.5. Особенности интеграции программных продуктов для реализации математической поддержки развития социальной инфраструктуры... 137 Выводы 142
Заключение 144
Список литературы 148
- Математические постановки задач поддержки развития социальной инфраструктуры территориального образования и методы их решения
- Математическая постановка задачи оптимизации структуры системы обеспечения муниципального образования сезонной продукцией для применения генетического алгоритма
- Алгоритм расчета суточных лотов-поставок из баз хранения сезонной продукции
- Метод математической поддержки решения задачи развития социальной инфраструктуры муниципального образования
Введение к работе
Динамичные изменения экономических условий, характеризующие российскую действительность в течение последних лет, привели к существенному усложнению задач по развитию социальной инфраструктуры территориальных образований РФ (под территориальным образованием понимается муниципальное образовании или Субъект РФ), стоящих перед администрацией разного уровня. При этом все более существенной становится задача информационно-аналитической поддержки управляющих решений в данной сфере. Задачи сходного рода являются предметом исследования двух направлений -конфигурационного организационного управления и реинжиниринга бизнеса. Методы решения задач конфигурационного управления исследуются в работах А.А. Федулова, Ю.Г. Федулова, В.Н. Цигичко [42, 43] и др. Имеется несколько работ по методам решения задач конфигурационного управления в абстрактной постановке как задач оптимизации структур сложных иерархических систем. Чаще всего задачи оптимизации структуры решаются с помощью методов исследования операций. Теория исследования операций развивается в большом числе трудов зарубежных и отечественных ученых, таких как Е.С. Ветнцель [10], академика Л.С.Понтрягина [24], В.Г.Болтянского [24], [7], нобелевского лауреата Л.В. Канторовича [20], В.М. Гаврилова [32] и др. (см. [3], [4], [5], [27], [41]). Среди зарубежных авторов следует отметить работы С.Гасса [11], Р. Беллмана [6], Дж. Хедли [48], Л.С. Лэсдона [25].
Реинжиниринг бизнеса имеет те же цели, что и данная работа, но применительно к бизнесу. Отличительной чертой является решение задачи на основе интуиции и опыта экспертов без применения методов оптимизации, но с мощной информационно-справочной поддержкой. Исследования по этой теме проводятся в работах М. Хаммера, Дж. Чампи [51], Е.Г. Ойхмана, Э.В. Попова [29] и др.
В целом имеется прочный теоретический фундамент для выполнения исследований по выбранной теме. Однако в конфигурационном управлении математическая поддержка ограничивалась суженной постановкой задачи, не адекватной потребностям развития социальной инфраструктуры территориальных образований, а реинжиниринг бизнеса по своей сути не учитывает в должной мере удовлетворение социальных потребностей населения. Отсутствие методов, отвечающих требованиям поддержки развития социальной инфраструктуры, делает актуальным исследование и разработку методов оптимизации социальной инфраструктуры территориальных образований РФ.
В первой главе диссертации излагается анализ состояния исследований по теме диссертации, формулируются постановки задач диссертационного исследования, даются основные понятия, используемые в исследовании, анализируются существующие исследования по теме. Также формулируются требования к постановке полномасштабной задачи развития социальной инфраструктуры, и формируется классификация постановок частных задач.
Во второй главе описываются теоретические основы построения генетических алгоритмов (ГА), формулируется математическая постановка исходной задачи оптимизации параметров системы обеспечения муниципального образования сезонной продукцией, представляющей собой систему баз хранения сезонной продукции и доставки ее населению. Базы располагаются на окружности заданного радиуса от центра муниципального образования. Задача состоит в создании системы обеспечения населения сезонной продукцией, повышающей до желаемого средний по районам уровень удовлетворения потребностей населения, ориентируясь на критерии наименьшей стоимости наращивания возможностей и наивысшего разумного удовлетворения населения в продукции. Также формулируется постановка исходной задачи для решения ее с помощью ГА, описывается вид и параметры ГА для решения данной задачи и проводится исследование его вычислительной эффективности.
В третьей главе изложен гибридный метод поддержки развития системы обеспечения сезонной продукцией населения муниципального образования и оценена его вычислительная эффективность.
В четвертой главе изложены математические методы поддержки развития социальный инфраструктуры территориального образования РФ, формулируется постановка задачи более общего вида, чем рассмотренной в предыдущих главах - задачи оптимизации покомпонентного оказания социальных услуг населению. Особенность состоит в том, что услуги не доставляются базами, а оказываются учреждениями, размещенными на территории муниципального образования, население вынуждено добираться до учреждений самостоятельно. Предлагается метод решения данной задачи, также описаны особенности интеграции программных продуктов для реализации математической поддержки развития социальной инфраструктуры.
Математические постановки задач поддержки развития социальной инфраструктуры территориального образования и методы их решения
Ниже формулируются математические постановки задач поддержки развития социальной инфраструктуры территориальных образований РФ.
Введем следующие обозначения: A{i) - состояние системы в момент времени t (многомерный массив или кортеж);
S(t) - структура системы в момент времени / (многомерный массив или кортеж);
Q(f) - пространственное положение элементов системы и подсистем в момент времени t (многомерный массив или кортеж); // - номер подсистемы; І2 - номер элемента; /; - множество подсистем; І2 — набор типов элементов; V— многомерное множество функций элементов и подсистем, их связей и отношений; W{t) - состояние внешней среды в момент времени U а - номер индивидуальной задачи; - вербальное или формализованное описание функциональной задачи /-го элемента или подсистемы; /. - множество действий (с обозначенной последовательностью) и правилами поведения /-го элемента (подсистемы), как функция состояния оставшейся части системы, внешней среды и цели элемента (подсистемы); hp - значение ju-й функциональной характеристики /-го типа элемента, JUEM, М- множество номеров-признаков функциональных характеристик элементов социальной инфраструктуры; НІ = {hfM, jueM, v,} - описание /-го типа элементов социальной инфраструктуры; а,2 -количество элементов типа іі в системе; a.t, - количество элементов типа в подсистеме системе с номером /;; 0(/,) - множество элементов в подсистеме с номером І\\ v, - вербальное или формализованное описание функций /-го элемента (подсистемы), его связи и отношения с другими элементами или подсистемами; j - номер ресурса, необходимого для создания и поддержания функционирования системы; hi - функциональные характеристики элементов /-го типа. U{t) - управляющие воздействия в процессе работы системы; to- начальный момент исследования системы или момент ее создания; ti - начальный момент функционирования системы для достижения желаемого результата tj to;
Xj{t) - объем ресурса с номером./, израсходованного к моменту времени t;
Предположим также, что в рассматриваемой задаче перед моментом времени tj система либо еще не существует, либо не способна функционировать.
Также, в дальнейшем будем отмечать символом « » наибольшее возможное или предварительно заданное значение переменной в ряду целых чисел от 1 доу .
В общем случае состояние системы в любой момент времени t является полностью определенным, если структура, пространственное расположение элементов и подсистем, а также внутреннее состояние системы известны для данного момента времени V. A(t) = (S(t),Q(t),B(t)), (/)«&,(/)}, /e/,u/2
Символом {...} обозначается, в общем случае, многомерное множество либо любая упорядоченная последовательность значений внутри скобок. Рядом со скобками указываются границы изменения заданного набора значений.
Описание структуры системы S(f) включает:
а) векторы // = {//}, h = {i2}, {0(/,)}, /, є /,
б)множество V = {v/}, fe/,u/2, где V,- совокупность описаний всех возможных функциональных задач, а также возможных действий и правил поведения элементов (подсистемы) в различных ситуациях; в)матрица a = {ajh) как число и распределение элементов по подсистемам. Другими словами, структура системы полностью определена, если известны: состав элементов в каждой подсистеме, описание функций элементов и подсистем, матрица их распределения по подсистемам; г) {НІ, і є І2} - множество функциональных характеристик элементов всех типов в социальной инфраструктуре. Примеры h - стоимость, геометрические характеристики объекта /-го типа. Совокупность множеств A(i) и W(t) определяет ситуацию в момент времени t. Обычно принимается следующее допущение для данного ряда допустимых действий элементов и подсистем {/,( ,/4(/), (/))} » существует некоторый класс математических операторов G = {gv}, каждый элемент которого gv позволяет, в пределах принятых правил поведения, {/,( ,,4(/), (/))), в течение любого момента времени t и с незначительными отклонениями от t, равными Д/, определять состояние системы в момент / + А/, зная состояние системы A(t),{W(r)},t т t + At и предысторию функционирования системы по некоторому интервалу[/- Дг„,/], гдеДгу зависит от оператора : A(v\t + At) = gvi_{A(v\T)},{W{v\z)},u{t)),t-Avv r t (1) при условии ({A(V)(T)},{W(V)(T)})CZ[AXW]{V) (2) где [А х W]iv) совокупность допустимых возможных состояний системы А и состояний внешней среды Wz данным оператором gv. В общем случае форма оператора gv ,подходящая для описания зо процесса функционирования, зависит от состояния системы и внешней среды, то есть при переходе от одного класса ситуации к другому может требоваться изменение в форме оператора gv. Пусть Ф({Л(О},{0ЧО}» і t T - некоторый критерий работы системы в интервале [t\,T\, где Т - некоторый момент в будущем, и Xj подходящий математический оператор, определяющий количество различных израсходованных ресурсов к моменту времени t.
Математическая постановка задачи оптимизации структуры системы обеспечения муниципального образования сезонной продукцией для применения генетического алгоритма
При решении функционал М минимизируется. Значения v,y рассчитываются по формулам (7) п.2.2, значения dy - по формуле расстояния от точки - местоположения базы с номером j до z-ro центра потребления, является функцией величины Sj и координат /-го центра. До начала оптимизации во внутреннем контуре величины dy - известны, т.к. по технологии решения сначала формируются хромосомы внешнего контура - С, Cj и Sj. Символом t обозначен номер итерации внешнего контура оптимизации.
Алгоритм решения задачи в целом представлен на рис.2.3. В свою очередь оптимизация фитнес-функции М осуществляется с помощью алгоритма, обобщенная блок-схема которого дана на рис.2.4.
Если из каждой базы вывезен ровно суточный лот wf, (условия (7)), это значит, что ни один центр потребления не получил продукции меньше или больше другого, следовательно, поставки в любой центр потребления не могут быть более увеличены, и p(t) достигает в этих условиях своего условного максимума. Тем самым обеспечивается эквивалентность требований тах (/)и глобального минимума M{i). Если же M(t) О, то такой эквивалентности может и не быть, так как в этом случае при выполнении условий (6) могут не выполняться условия (7) и/или (8). В этом варианте максимум p (t) при данных С,- и S, может и не т достигаться. Например, может оказаться, что для некоторых у, ау 1. i-i Это значит, что из соответствующих баз вывезена продукция в меньшем, чем wf объеме. Значит, имеется возможность увеличения поставок в какие-то центры потребления и, следовательно, для них может быть то pi(t) p(t). А это уже нарушение принципа социальной справедливости. Итак, в пределе при М(/)=0 оптимальный план поставок {щ} во внутреннем контуре обеспечивает возможный при данных N, С, Cj и 8/ максимум p(t). Требования к формулировке задачи оптимизации пакетом типа GeneHunter выполнены. Однако адекватность исходной задачи и задачи в форме (1)-(5) в общем случае не достигается: все компоненты фитнес функций обоих контуров, имеющие перед собой штрафные коэффициенты в случаях, когда они отличны от нуля, могут давать формальные решения, не отвечающие смыслу исходной формулировки. Так одинаковый ненулевой штраф в функции (t) будет и в случае, когда p(t) М, и в случае когда p(t) hf при одинаковой абсолютной величине разности p(t) - А/ . Аналогичная картина будет при невыполнении условий ау=1,
v,y=l и др. Увеличение степени адекватности исходной и преобразованной постановок задач за счет учета знака разностей величин, стоящих в штрафных компонентах, вполне возможно, но для этого потребуется существенное усложнение алгоритмов формирования штрафных коэффициентов. Такой шаг был бы целесообразным, если бы в целом применение генетического алгоритма в чистом виде обеспечивало бы выполнение требований по необходимому быстродействию. Однако автору данного исследования не удалось полностью исключить механизмы штрафных функций. Как оказалось при последующих исследованиях этот механизм не обеспечивает желаемого быстродействия и в связи с этим дальнейший материал исследования приведен для постановок в форме (1) - (5).
Алгоритм расчета суточных лотов-поставок из баз хранения сезонной продукции
Вопрос о том, какой центр потребления (/) должен стать предметом перепланирования зон обслуживания и объемов поставок, желательно связывать с возможностью выполнения подобной операции без возможных ошибок в расчетах wf по многим критериям при условии однократного перепланирования поставок без решения системы неравенств. Последнее требование является желанием увеличить вычислительную эффективность расчетов wf за счет использования простейших математических средств.
Данному требованию отвечает следующий принцип: в первую очередь перепланирование зон обслуживания, а с ними и объемов S/vy как компонентов лотов wf должно осуществляться за счет тех центров потребления, которые входят в наименьшее число зон обслуживания баз из данной группы.
Обозначим символом Г, множество
TrU\jeG,{i}eI/0),jeG} (14) Тогда при наличии в группе G двух баз с разным wj, в первую очередь наименьший лот Щ увеличивается за счет объема S/v,j переменной, имеющей наименьшую мощность Щ. Чем меньше возможностей для маневра - перезакрепления центра потребления за какой-либо базой, тем больше шансов, что при отсутствии системного решения, последовательное без возвратов изменение зон обслуживания, приведет к исходу, когда в силу методической погрешности метода не удается выровнять wf. Большое значение Щ - признак широкого маневра для выравнивания wf, входящих в одну группу G баз. Сама корректировка wj сводится к увеличению aIJx для базы с наименьшим wj и уменьшению aihc наибольшим wj, при условии, Ij(O)nIh(O) 0. При этом wjдолжна как можно больше приближаться к w(группы), a wj уменьшаться, но не ниже w (группы). Эти условия и определяют алгоритм выравнивания wj и wj : из базы, с номером j2 передается объем услуг А,-, а в базе, с номером j\, он наращивается на ту же величину А,- так, чтобы (w0j(группы)-(wj + Д,))- min, и 0, w (группы) wj -Ап (15) Wf arg min Wf, (16) wj arg max wj, (17) /є/Л(О)п/А(О) 0 Д, = min [Ahi, w (группы) - wj, wj - w (группы)], (18) 4,.= -. (19) если Д; = Ahi, то это означает, что і-й центр потребления полностью выходит из зоны обслуживания чтоу-й базы. В этом случае необходимо откорректировать Ih (0): I h = Ih (0) \ {/}. В результате может оказаться, что
l h n I j = 0. В этом случае необходимо корректировать состав группы G.
В случае, когда изменяется группа G баз, с пересекающимися зонами обслуживания, необходимо заново пересчитывать w(zpynnbi).
Данная процедура является реализацией разновидности балансового метода с последовательно-необратимыми операциями назначения суточных лотов wf в соответствии с требованиями (11).
Конечность процедуры очевидна, если предусмотреть специальные меры от формального зацикливания алгоритма выравнивания суточных лотов wf баз с пересекающимися зонами обслуживания.
Формальное доказательство сходимости решения к оптимуму в виде (1) не проводилось. Однако, вычислительный эксперимент подтвердил справедливость гипотезы о быстрой сходимости к решению, отвечающему условиям (1) - (4) для широкого диапазона исходных данных. Теоретически искомый оптимум может не достигаться, если в процессе изменений зон обслуживания Ij, будет выбрана последовательность изменений, при которой по отношению к исходным множествам 7,(0), будет пропущен вариант, когда maxwj-vtd может достигать наименьшего возможного значения. Процедура попарного выравниваниям и wch с возможным необратимым для данного алгоритма исключения некоторого / из /,2не гарантирует глобального экстремума. Для общего случая алгоритма значения wf должны искаться как решение системы (1) - (4). В соответствии с рекомендациями главы 2, такое решение целесообразно осуществлять одним из методом нелинейного программирования, например, методом отображающей точки. Программная реализация такого метода потребовала бы определенных усилий и времени. В связи с этим автор и предложил упрощенную процедуру расчета wf. Поскольку групп баз G с пересекающимися зонами обслуживания может быть несколько и в ходе расчетов состав групп может меняться, то в алгоритме вводится цикл с номером к, контролирующий полноту и корректность операций с w] и 1 г Каждый такой цикл заканчивается формированием wf для jeG(k), новых зон обслуживания и объемов поставок из каждой базы в центры потребления, входящие в зоны обслуживания I j,jeG(k). Последние нужны лишь для контроля. На блок-схеме ВМеСТО СИМВОЛОВ А у ИСПОЛЬЗУЮТСЯ СИМВОЛЫ OLy.
Метод математической поддержки решения задачи развития социальной инфраструктуры муниципального образования
Внешний контур 2 предназначен для выработки окончательного решения по развитию социальной инфраструктуры территориального образования. В целом поиск решения является интерактивной процедурой выработки группового решения нескольких суверенных лиц [39] или кооперативного решения субъектов управления [28]. Однако существующие программные реализации методов поддержки групповых решений (см. например [39]) рассчитаны на дискретное множество альтернатив. В рассматриваемой задаче данное требование порождает определенные трудности, так как теоретически множество возможных решений задачи внешнего контура 2 имеет мощность континуума. Методы поиска кооперативных решений предполагают наличие функций полезности альтернатив у каждого участника [28]. Построение функций полезности достаточно сложная процедура для лиц, не имеющих математической подготовки. В силу этого в данном исследовании сделан выбор в пользу процедур групповых решений лиц, рассматриваемых как суверенные.
Автор данного исследования предлагает следующую последовательность трех этапов человеко-машинных операций.
Первый этап: сбор данных о множестве альтернатив Г необходимых для осуществления операции индивидуального ранжирования. Второй этап - индивидуальное ранжирование субъектами управления процессом развития социальной инфраструктуры. Третий этап - рекомендации по выбору группового решения с использованием метода Скринской Т.П. [39] Четвертый этап - неформальное обсуждение субъектами управления полученного группового
В случае неудовлетворительной оценки любым из участников имеющегося группового решения неформальным путем задаются новые данные, ввод которых может привести к очередной альтернативе в Г. Автору принадлежат рекомендуемые действия на 1-м, 2-м и 4-м этапах.
В число данных, собираемых на 1-м этапе, входят значения показателей оценки выгоды и издержек субъектов управления. Пример показателей представлен ранее в п.3.1. Элементами - альтернативами у множества выбора Г могут быть парето-оптимальные оценки имеющихся показателей. В качестве показателей оценки решения по развитию социальной инфраструктуры предлагаются. К\ - полные затраты на создание и развитие инфраструктуры; К2 - удельные издержки вхождения в бизнес - оказания социальных услуг на коммерческой основе; Къ - уровень конкуренции собственников бизнеса; Ку — доходность бизнеса - оказания услугу-го типа; Кб/ - нижняя граница уровня качества услугу-го типа; Ку - превышение фактической стоимости услуг в коммерческом секторе Pj над желаемым уровнем pj в каждом типе услуг; К$ — желаемый уровень качества услуг в целом по территориальному образованию; Kg - фактический уровень качества услуг в целом; К\о - оценка возможных доходов бюджета от функционирования социальной инфраструктуры. і . -SIX +cl +CDN; -С ;К2=М ;К9 = М(І) От искомых переменных задач внешнего контура 1 и внутреннего контура непосредственно зависят показатели К\, K2, К , Kg. Значение показателя К2 является предметом договора инвесторов - собственников с администрацией. Объективная и явная часть договора определяется значениями средней цены pj на услугиу -го типа в коммерческом секторе, уровня Kg. Последняя зависимость затрудняет априори установление 132 объективно-обусловленных компонентов издержки вхождения в бизнес -оказания на коммерческой основе социальных услуг [26] Фактически значение показателя К2 определяется в ходе переговоров инвесторов с администрацией, осуществляемой в рамках 4-го этапа операций внешнего контура 2. Доходность бизнеса - Ку является монотонно возрастающей функцией цены pj и числа учреждений ]Г N h в социальной к инфраструктуре. С позиции инвесторов и администрации территориального образования К\ определяет издержки развития социальной инфраструктуры и относится к минорируемому показателю: чем меньше значение К\, тем лучше и для инвестора и для администрации. Однако компоненты C3h + С" одновременно выступают источниками доходов соответствующего бюджета в виде отчислений по статье подоходного налога. Кроме того, расходы на персонал -C"t повышая семейные бюджеты увеличивают и совокупный показатель уровня развития территориального образования, не представленного в данной задаче. С этой точки зрения помимо показателя К\ как образа совокупных издержек в ряде случаев надо отдельно рассматривать и показатель ]Г C"t , который не может однозначно рассматриваться только к как минорируемый. С позиции инвестора все три составляющие К\ являются минорируемыми. С позиции администрации Cnh с некоторого уровня становится мажорируемой величиной. Эта неоднозначность классификации имеет своим следствием неоднозначное априорное отношение администрации к значениям показателя К\. Значение показателя К\о= С"к. С позиции администрации в определенных пределах чем больше ] С" сможет обеспечить развиваемая инфраструктура, тем больше высокооплачиваемых рабочих мест и отчисления в бюджет по статье подоходного налога. Значение К\ и K\Q- предмет компромиссного решения, зависящего еще и от уровней К% 133 Признаком не оптимальности по Парето решений задач внутреннего и внешнего контура 1 является не убывание с номером t итераций внешнего контура 1 совокупности зависящих от решений в этих контурах показателей К\, Къ, К4, К9, K\Q. Как только выполняются условия: Ut-2) Ut-\), V/; (З/) Kli) K(t-\), то решение внешнего контура 1 на шаг t-\ с точностью до разницы компонентов решения на итерациях с номерами t-\ и t является парето оптимальным.
