Содержание к диссертации
Введение
1 Анализ особенностей постановки многоиндексных транспортных задач 17
1.1 Определение транспортной задачи как задачи распределения ресурсов 17
1.2 Этапы решения многоиндексной задачи распределения ресурсов 20
1.3 Анализ методов размещения центров аккумуляции ресурсов 23
1.4 Формализация многоиндексной задачи распределения ресурсов 27
1.5 Анализ методов решения многоиндексных задач распределения ресурсов 33
1.6 Приближенные методы решения задач распределения ресурсов 35
1.7 Анализ способов представления недетерминированных величин 39
1.8 Формализация параметров задачи в виде нечетких интервалов 41
1.9 Задача автоматизации распределения ресурсов 45
1.10 Выводы 47
2 Разработка метода и алгоритма решения задачи рационального размещения центров аккумуляции ресурсов 50
2.1 Методы определения принадлежности объекта к центру аккумуляции ресурсов 50
2.2 Разработка метода решения задачи определения рационального расположения центров аккумуляции ресурсов при задании параметров в виде нечетких интервалов 55
2.3 Определение параметров функции принадлежности областей группирования на основе вычисления потенциалов 61
2.4 Разработка алгоритма решения задачи определения расположения центров аккумуляции ресурсов в условиях неопределенности 64
2.5 Разработка информационного обеспечения для задачи рационального размещения центров аккумуляции ресурсов 69
2.6 Сравнительная оценка полученных результатов при вариации условий построения транспортно-распределительной системы 85
2.7 Вывод 94
3 Разработка метода и алгоритма решения многоиндексных задач распределения ресурсов с нечёткими параметрами 96
3.1 Модель многоиндексной задачи распределения ресурсов с использованием нечетко-интервального подхода 96
3.2 Свойства многоиндексной задачи распределения ресурсов с нечеткими параметрами 98
3.3 Разработка метода индексных элементов для решения многоиндексных задач распределения ресурсов с нечеткими параметрами 102
3.4 Применение метода декомпозиции для решения многоиндексных распределительных задач 106
3.5 Разработка алгоритма решения многоиндексной распределительной задачи с нечеткими параметрами 107
3.6 Области применения метода решения многоиндексных задач распределения ресурсов с нечеткими параметрами 115
3.7 Выводы 117
4 Апробация исследований с применением проблемно ориентированного программного приложения 119
4.1 Структура проблемно-ориентированного программного приложения. 119
4.2 Особенности функционирования разработанного программного комплекса123
4.3 Экспериментальное исследование результатов предлагаемого метода 129
4.4 Оценка эффективности применения метода индексных элементов при решении многоиндексной задачи распределения ресурсов 137
4.5 Выводы .141
Заключение 143
Список источников
- Формализация многоиндексной задачи распределения ресурсов
- Определение параметров функции принадлежности областей группирования на основе вычисления потенциалов
- Применение метода декомпозиции для решения многоиндексных распределительных задач
- Экспериментальное исследование результатов предлагаемого метода
Введение к работе
Актуальность темы исследований. Задача распределения ресурсов
представляет собой специальную задачу линейного программирования
транспортного типа, имеющую многочисленные приложения к задачам
планирования, управления и проектирования. Математический аппарат
данных задач – средство прикладных научных исследований при
проектировании систем на основе системного подхода. Признаком
распределительных задач является распределение ресурсов между их
производителями и потребителями согласно выбранным критериям. Методы
решения распределительных задач относятся к методам системного анализа,
как методологии теории систем, и связаны с исследованием объектов
производства, распределения и потребления ресурсов, которые в
совокупности представляют собой самостоятельную систему, требующую структуризации и анализа, т.е. решения задачи синтеза. При решении распределительных задач имеются такие составляющие, как анализ и обработка информации, моделирование, оптимизация и принятие решений для совершенствования управления техническими объектами, предприятиями и отраслью в целом. В разработку методов системного анализа внесли большой вклад такие ученые как Берталанфи Л., Валуев С.А., Денисов А.А. Волкова В.Н., Емельянов А.А., Квейд Э., Месарович М., Оптнер С., Такахара И., Перегудов Ф.И., Уемов А.И., Черняк Ю.И., Янг С. и многие другие.
Развитие производственных отношений и технологий распределения
привело к необходимости создания центров аккумуляции и распределения
ресурсов. Функции этих распределительных центров могут выполнять, в
зависимости от решаемой задачи, технологическое оборудование
предприятий, банк производственных операций, банк ресурсов технических систем, складские помещения, хранящие информацию серверы сетей передачи дискретной информации и многое другое. Общим признаком распределительных центров является аккумуляция и хранение ресурсов, что связано с потребностью решения задач эффективного управления распределением этих ресурсов на других уровнях.
Целью распределительной задачи является оптимизация процесса распределения ресурсов, имеющихся в запасе и находящихся в центрах аккумуляции ресурсов (ЦАР), т.е. обеспечение потребителя в заданном месте необходимым ресурсом нужного количества с минимальными затратами. Значительная часть действий на пути движения ресурсов от первичного производителя до конечного потребителя осуществляется через центры аккумуляции ресурсов с применением различных передающих элементов (каналов связи, средств перевозки и пр.), т.е. транспортной системы.
Оптимизировать взаимодействие источников ресурсов, потребителей, ЦАР, различных видов транспорта позволяет создание транспортно-распределительной системы, позволяющей ускорить продвижение потоков
4
ресурсов, снизить суммарные затраты отправителей и получателей этих
ресурсов. Системный принцип исследования объектов такой самостоятельной
системы, как транспортно-распределительная система, соответствует
пониманию того, что при их изучении необходимо исходить из внутренних связей и многосторонних взаимозависимостей между элементами системы.
При решении распределительной задачи для управления материальными, информационными и другими потоками должна использоваться комплексная модель единого процесса, учитывающая взаимодействие производителей и потребителей ресурсов, наличие ЦАР, неоднородность распределяемых ресурсов, а также различные типы средств доставки, участвующие в распределении. Увеличение параметров (увеличение индексности) позволяет оптимизировать более сложные задачи распределения ресурсов и учитывать большее число факторов, влияющих на стоимость их распределения. Решение многоиндекных задач связано с именами Юдина Д.Б., Гольштейна Е.Г., Верховского Б.С., Хели К., Таха Х.А., Раскина Л.Г., Кириченко И.О., Моисеева Н.Н., Серой О.В., Прилуцкого М.Х., Афраймовича Л.Г. и многих других.
При решении многоиндексной транспортно-распределительной задачи с применением ЦАР существует неопределенность исходных параметров, которая определена случайными факторами: сбои в работе технологического оборудования, изменение стоимости и условий распределения ресурсов и многое другое, что может существенно влиять на конечный результат. Для формализации неопределенностей в диссертации применены методы теории нечетких множеств.
Хотя нечетко-множественные методы решения задач оптимального
распределения ресурсов уже были ранее рассмотрены в ряде работ, но
проблемы принятия решений в транспортно-распределительной системе,
компоненты которой связаны информационными, материальными,
управленческими потоками, недостаточно исследованы.
Диссертационная работа посвящена разработке методов решения задачи рационального размещения центров аккумуляции ресурсов и решения многоиндексных распределительных задач при задании параметров в виде нечетких интервалов. Необходимость решения распределительных задач большой размерности в условиях неопределенности требует разработки новых методов, информационного и математического обеспечения.
Цель диссертационной работы состоит в развитии методов и
алгоритмов решения задачи рационального размещения ЦАР и решения
многоиндексных транспортных задач, применительно к задачам
распределения ресурсов при задании параметров в виде нечетких интервалов.
Для достижения поставленной цели решаются следующие задачи:
– анализ методов размещения ЦАР и методов распределения ресурсов, обеспечивающих оптимальное решение многоиндексной распределительной задачи, с учетом специфики типа ресурсов, способов транспортировки, особенностей производства, хранения и потребления;
– разработка метода определения области рационального
месторасположения ЦАР с учетом задания параметров задачи в виде нечетких интервалов;
– разработка алгоритма реализации метода рационального размещения центров аккумуляции ресурсов с учетом задания параметром в нечетко-интервальном виде;
– разработка метода решения многоиндексной задачи распределения ресурсов, позволяющего получить оптимальное решение за допустимое время, учитывая неопределенность параметров задачи;
– разработка алгоритма реализации метода решения многоиндексной задачи распределения ресурсов, позволяющего учесть неопределенность исходных данных задачи и обеспечивающего оптимальное решение задачи за меньшее время, за меньшее число итераций и без возникновения случаев вырожденности при построении опорного плана (начального решения) задачи, по сравнению с классическим транспортным методом линейного программирования, применяемым при решении задач распределения ресурсов – методом потенциалов;
– разработка программного обеспечения решения задачи рационального размещения ЦАР и решения многоиндексной задачи распределения ресурсов с нечеткими параметрами.
Методами исследований являются методы системного анализа, методы теории нечетко-интервального анализа, методы кластерного анализа, методы линейного программирования, методы математического моделирования.
Достоверность получаемых в диссертации результатов вытекает из их
математического обоснования, подтверждается результатами
экспериментальных исследований и положительной оценкой внедрения.
Объектами исследования являются многоиндексные задачи
распределения ресурсов (транспортные задачи линейного программирования) в условиях неопределенности.
Тематика работы соответствует п. 1 «Теоретические основы и методы системного анализа, оптимизации, управления, принятия решений и обработки информации», п. 2 «Формализация и постановка задач системного анализа, оптимизации, управления, принятия решений и обработки информации», п. 4 «Разработка методов и алгоритмов решения задач системного анализа, оптимизации, управления, принятия решений и обработки информации» паспорта специальности 05.13.01 – «Системный анализ, управление и обработка информации».
Научная новизна. В диссертации получены следующие новые научные и практические результаты:
1. Метод решения задачи рационального размещения центров
аккумуляции ресурсов (ЦАР) для дальнейшего их распределения, отличие которого заключается в расширении исходных методов группирования. Группирование определяется не только расстоянием между объектами, но и спросом на ресурсы, и пропускной способностью ЦАР с учетом нечеткости
6 исходных параметров. Новизна предлагаемого подхода заключается в возможности не только определения рациональной области размещения, но и позволяет учесть неопределенность параметров задачи. Применение методов теории нечетко-интервального анализа позволит получить решение задачи размещения ЦАР как множество нечетких интервалов – координат размещения, которые определят область для варьирования данными в зоне наилучших решений.
-
Алгоритм предложенного метода рационального размещения центров аккумуляции ресурсов, позволяющий учесть неопределенность исходных данных и сократить стоимость распределения ресурсов в среднем на 25% по сравнению с алгоритмами известных методов;
-
Метод решения многоиндексной задачи распределения ресурсов, позволяющий учесть помимо факторов, определенных в классической транспортной задаче, дополнительные факторы, влияющие на стоимость перевозки ресурсов, такие как: наличие ЦАР, вид ресурса, вид транспорта, осуществляющего перевозку. В основе предлагаемого метода индексных элементов для решения многоиндексной транспортно-распределительной задачи лежит приближенный метод нуль-преобразования для решения трехиндексных задач, расширенный до пяти индексов. Существенное отличие предложенного метода заключается в определении параметров пятииндексной распределительной задачи в виде нечетких интервалов.
-
Алгоритм предложенного метода решения многоиндексной задачи распределения ресурсов, позволяющий учесть неопределенность исходных данных задачи и обеспечивающий оптимальное решение задачи за меньшее время, за меньшее число итераций и без возникновения случаев вырожденности при построении опорного плана (начального решения) задачи, по сравнению с алгортмом классического транспортного метода линейного программирования, применяемым при решении задач распределения ресурсов – метода потенциалов;
5. Программные комплексы, основанные на реализации предложенных
методов и обеспечивающие оптимизацию совокупного материального потока
на всем протяжении – от производителя до конечного потребителя, что
определяет максимальный эффект при распределении ресурсов и позволяет
усовершенствовать систему управления распределением ресурсов путем
организации единой, территориально распределенной системы планирования
и контроля. Разработанные комплексы обеспечивают решение задач учета,
распределения и управления, а также применение возможностей
информационных технологий (картографические службы: Яндекс.Карта,
GoogleMaps и т.д., программные решения для оперативного управления на
платформе 1С) для поддержки решения задач данного класса.
Основные положения, выносимые на защиту:
1. Метод и алгоритм решения задачи рационального размещения ЦАР,
отличающийся расширением исходных методов группирования,
7 учитывающий не только расстояние между объектами, но и спрос на ресурсы, пропускную способностью ЦАР в условиях неопределенности.
2. Метод и алгоритм решения многоиндексной задачи распределения ресурсов, отличающийся применением метода нуль-преобразования для пятииндексных задач, и учитывающий основные факторы, влияющие на стоимость перевозки ресурсов: производительность поставщика, спрос потребителя, наличие ЦАР, вид ресурса и вид транспорта, осуществляющего перевозку при задании параметров в нечетко-интервальном виде.
Теоретическая ценность работы. Ценность научных работ состоит в
том, что предложен, научно обоснован и практически реализован комплекс
математических, информационных и алгоритмических моделей транспортно-
распределительной задачи. Предложен и программно реализован набор
алгоритмов обработки информации при решении транспортно-
распределительной задачи при задании параметров в виде нечетких интервалов.
Практическая ценность работы. Практическая значимость
исследования заключается в том, что на основе разработанных метода рационального расположения ЦАР и метода решения многоиндексных задач распределения ресурсов в нечетко-интервальной постановке созданы программные средства поддержки принятия решений для управления распределением ресурсов. Внедрение данных программ позволяет получить оптимальное решение за допустимое время, при этом учесть факторы, влияющие на стоимость распределения ресурсов.
Реализация результатов работы. Практические и теоретические результаты работы внедрены:
– на предприятии ООО «Юг-Гарант» метод и программное обеспечение (ПО) рационального размещения ЦАР;
– на предприятии ООО «СМиК» метод и ПО для решения многоиндексной задачи распределения ресурсов;
– в учебном процессе на кафедре систем автоматического управления Института радиотехнических систем и управления ЮФУ.
Апробация работы и публикации. Основные положения диссертации и отдельные ее результаты докладывались и получили положительные отзывы на следующих конференциях:
– III Всероссийская научная конференция молодых учёных, аспирантов и студентов «Проблемы автоматизации. Региональное управление. Связь и автоматика. – ПАРУСА–2014» – Геленджик: ЮФУ, 2014 г.;
– XII Всероссийская научная конференция молодых ученых аспирантов и студентов «Информационные технологии, системный анализ и управление (ИТСАиУ-2014)», г. Таганрог, 2014 г.;
– IV Всероссийская научная конференция молодых ученых, аспирантов и студентов «Современные технологии, естествознание, педагогика – СТЕПь– 2015», г. Элиста, 2015 г.;
– VIII Международная научно-практическая конференция «Молодежь и наука: реальность и будущее». Невинномысский институт экономики, управления и права. - Невинномысск, 2015 г.;
– Международная научно-практическая конференция «Молодежный форум: технические и математические науки», «Воронежский гос. лесотехнический ун-тет им. Г.Ф. Морозова». Воронеж, 2015 г.;
– XIX Международная конференция по мягким вычислениям и измерениям IEEE. Санкт-Петербург. СПбГЭТУ (ЛЭТИ), 2016 г.
Структура диссертационной работы. Диссертационная работа
содержит 172 страницы машинописного текста, включая введение, четыре
раздела, заключение, список литературы из 231 наименования,
62 рисунка, 21 таблицу, а также приложение.
Формализация многоиндексной задачи распределения ресурсов
Таким образом, основной целью транспортно-распределительной задачи является минимизация затрат по доведению ресурсопотока от первичного источника ресурсов до конечного потребления. Решение этой задачи возможно лишь при условии способности ТРС интерпретировать исходные параметры задачи в нечетко определенной среде.
Большое количество разных ресурсов и услуг повышает степень неопределенности спроса на них, обуславливает резкие колебания качественных и количественных характеристик материальных потоков, проходящих через транспортно-распределительные системы. Неопределенным может быть не только спрос, но и стоимость перемещения единицы ресурса, которая определяется как разнообразием типов используемых передающих элементов, изменением стоимости энергоресурсов, так и характеристиками транспортных магистралей. В этих условиях адаптация ТРС к внешней среде является существенным фактором устойчивого положения на рынке [15].
На основе проведенных исследований можно сделать вывод, что для эффективного решения проблемы оптимизации функционирования ТРС необходимы [166, 170]: – метод, определяющий рациональное число и область расположения центров аккумуляции ресурсов, учитывающий недетерминированный характер параметров транспортно-распределительной системы; – метод, позволяющий получить оптимальное решение многоиндексной задачи распределения ресурсов с учетом неопределенности параметров задачи; – эффективные алгоритмы принятия решений для многоуровневой модели, основанные на принципах стратегического планирования и управления; – информационная поддержка оптимальных управленческих решений и повышение эффективности деятельности административного персонала на основе использования возможностей автоматизированной системы. Анализ транспортно-распределительной системы позволяет выявить проблемы, требующие рассмотрения [15, 16, 18, 20, 22, 36, 162, 165, 172]. Прежде всего, очевидным является недостаток многих подходов к решению задач транспортно-распределительных систем – отсутствие учета информационных, материальных и качественных связей между элементами общей распределительной системы. Необходимо рассматривать функционирование и оценивать эффективность системы «производство – доставка – потребление» как единый комплекс [32]. Соответствующие постановки задач на содержательном уровне сделаны в работах [17, 18]. В [35, 84] подтверждается необходимость разработки и использования комплексных систем поддержки принятия управленческих решений, в которых каждое подразделение представлено соответствующей информационной подсистемой, осуществляющей свои действия в рамках своих полномочий.
Общий процесс построения оптимизационной транспортно-распределительной модели делится на следующие этапы [15, 17, 23]: – постановка задачи; – определение цели исследования в транспортной системе; – разработка системы в рамках принятых допущений; – планирование имитационного эксперимента на вычислительной станции; испытание модели в соответствии с намеченным планом и получение результатов для последующего формирования решения.
Далее проведем анализ существующих методов решения транспортно-распределительных задачи на каждом этапе.
В современных условиях перемещение ресурса от источника (производителя) к потребителю осуществляется двумя путями: «производитель – потребитель» и «производитель –центр аккумуляции ресурсов – потребитель» [85, 86]. Поставка ресурсов через центр аккумуляции к потребителю требует построения модели многоэтапной транспортно-распределительной задачи, в которой в качестве критерия оптимальности обычно принимается минимальное значение совокупных затрат по распределению ресурсов [23, 24, 31, 36, 68, 71, 72].
Задача оптимального размещения центров аккумуляции ресурсов давно уже стала классической задачей логистики [15, 17, 182, 200]. В ней требуется найти такое расположение ЦАР относительно своих производителей и потребителей, при котором некая целевая функция, обычно выражающая суммарные затраты, достигает своего минимального значения. Оптимальное месторасположение распределительного центра зависит от многих факторов. Помимо расстояний, объемов перевозимых ресурсов и транспортных тарифов, на оптимальное размещение центров аккумуляции оказывают влияние наличие развитой сети подъездных путей (каналов передачи ресурсов), перспективы и стоимость строительства новых путей (каналов) сообщения в регионе, целесообразность и затраты на строительство новых распределительных центров или ЦАР, экологические и правовые ограничения, налоговые нормы и множество других [87].
Задача размещения центров аккумуляции ресурсов может быть формализована, как поиск оптимального решения или же, как поиск субоптимального, то есть эвристического, близкого к оптимальному [76], которое определим, как рациональное решение поставленной задачи. Для рационального месторасположения центров аккумуляции ресурсов существует множество аналитических и экспертных методов, которые имеют ряд, как достоинств, так и недостатков. В качестве центров аккумуляции ресурсов, обеспечивающих распределение ресурсов за закрепленными за ними потребителями, в работах ученых исследуются так называемые центры кластеризации (группирования) или промежуточные распределительные центры.
Определение параметров функции принадлежности областей группирования на основе вычисления потенциалов
Полученные значения позволяют на следующем шаге основного алгоритма определить для i-й итерации значение Fi - как общую стоимость перевозки ресурсов от ЦАР к закрепленными за ними областями спроса ресурса при данном закреплении их положения. Цикл завершается, если результаты группирования (закрепление районов за ЦАР) до корректировки координат и после корректировки координат расположения центров, совпадают. Место размещения ЦАР (рисунок 2.2) с учетом корректировки координат (2.12) расположения примет следующий вид представленный на рисунке 2.3. By +fiy By Ay Ay -ay y Ax -ax Ax Bx Bx + /ix - область соответствующая модальным значениям (ц=1 ) - область соответствующая значениям 1
Результат решения задачи размещения ЦАР будет представлять собой множество нечетких интервалов – координат размещения центров в зависимости от нечеткого спроса каждой подобласти. Место расположения ЦАР определится не конкретными числовыми значениями, а нечетким интервалом, определяющим наилучшее возможное расположение центра аккумуляции. Определение значений в виде нечетких интервалов позволяет определить область для варьирования данными в зоне наилучших решений. Так, например, представление координат нахождения ЦАР в виде нечетких интервалов, позволит осуществить их размещение с учетом вариации выбора размера и конфигурации участка, транспортной доступности местности, наличия коммуникаций, стоимости земельного участка и т.д.
Множество потенциалов, рассчитанных на основе разработанного метода, описанного в разделе 2.2, позволяют определить степень оценки взаимосвязи областей потребления ресурса, характеризующихся величиной спроса с ЦАР, характеризующимися пропускной способностью (емкостью) с учетом расстояния между ними.
Применение нечетко-интервального метода для определения областей группирования, в отличие от детерминированных методов, позволяет одной и той же q-й области потребления ресурса принадлежать одновременно нескольким центрам группирования, но с разной степенью принадлежности.
При задании параметров задачи группирования в виде четких величин матрица принадлежности q-й области потребления ресурса к k-му центру группирования W определится следующим образом: w где r/ - четкое значение (0 или 1), определяющее принадлежность q-й области потребления ресурса к к-му центру группирования. То есть в матрице W содержатся значения rjk согласно которым можно точно сказать принадлежит ли область центру группирования. Причем если определена принадлежность области какому-либо центру (г}кд=1), то данная область не может принадлежать другому центру группирования (г/кд=0). При задании параметров задачи группирования в виде нечетких величин матрица принадлежности q-й области потребления ресурса к к-му центру группирования w определится следующим образом:
В задаче, поставленной в разделе 2.2, при разбиении на области потребления спроса имеет значение не только расстояние между центром и объектом группирования, но и спрос области потребления, а также так называемая, емкость центра аккумуляции ресурсов, которая характеризует пропускную способность центра.
С учетом данных условий, для определения значений принадлежности областей потребления ресурса к центрам аккумуляции ресурсов, предлагается использовать среднее модальное значение потенциалов р,ср, которое определится kq как центр тяжести трапеции [142], построенной по соответствующим значениям Р. . Тогда функция принадлежности g-ой области потребления ресурса к к-му центру группирования определится как: pср Іикд= к q = l,...,m;k = !,...,К. (2.17) ч 1 туср kq к=\ Применение значений потенциалов позволяет избежать сложности нечеткого разбиения, отмеченного в работе [143], относительно областей, удаленных от всех центров группирования.
Результат определения значений принадлежности областей потребления к центрам группирования представлен на рисунке 2.4, где - а) определяет четкое задание параметров, согласно (2.15); - б) - задание параметров в виде нечетких интервалов, согласно (2.16). a) б) Задание параметров задачи в виде нечетких интервалов представляет возможность описания заданных параметров в соответствии с тем, что параметры реальных задач в результате влияния различных факторов не точны и учитывает неопределенности, связанные с неполнотой, неточностью исходных данных.
Результатом применения нечетко-интервального подхода является параметрическая область возможных решений. С точки зрения принятия решений нечетко-интервальная модель определяется как модель с параметрами, принимающими значения из допустимых интервалов.
По результатам разработанного метода определения рационального расположения ЦАР с учетом задания параметров задачи в виде нечетких интервалов представлена графическая интерпретация алгоритма (рисунок 2.5).
Для описания исходных данных на основе нечетких интервалов используется структурное представление вида: NI { Aa - нижние граничные значения нечеткого интервала; mn – нижние модальные значения нечеткого интервала; mv – верхние модальные значения нечеткого интервала; (2.17) Bb – верхние граничные значения нечеткого интервала. } В качестве исходных данных, необходимых для реализации данной итерационной последовательности шагов используются: – (a,b) – исходные значения, задающие размер области S; – l – длина стороны единичного квадрата, определяющая квадратную подобласть sij области S, характеризующуюся определенным спросом на потребления ресурсов; – SP[i, j] – двумерный массив значений спроса для квадратной подобласти sij, определяемый в виде NI представления.
Применение метода декомпозиции для решения многоиндексных распределительных задач
Оценка эффективности применения метода рационального размещения центров аккумуляции ресурсов. Для оценки эффективности предложенного метода рационального размещения ЦАР сравним полученные результаты (см. раздел 2.6) вариаций условий построения ТРС с результатами группирования областей спроса, рассчитанных следующими методами (см. раздел 2.2): 1. (G) - горный метод, позволяющий определить центры группирования путем вычисления потенциалов каждой точки. В расчете не учитывается спрос и емкость ЦАР; 2. {(сА (v)} совокупность методов, позволяющая определить центры группирования путем вычислений потенциалов взаимосвязи ЦАР и областей потребления ресурсов с учетом недетерминированности значений спроса и емкости центров аккумуляции ресурсов; 3. RR = {(G),(V),(Z),(NI)} - разработанный метод рационального размещения ЦАР, который помимо учета взаимосвязи центров аккумуляции ресурсов и областей недетерминированного спроса позволяет осуществить корректировку координат размещения ЦАР относительно закрепленных областей спроса.
После закрепления за ЦАР областей спроса указанными методами, необходимо рассчитать общую стоимость перемещения ресурсов при данном группировании. Результаты вычислений представлены в таблице 2.16.
ЦАР Стоимость распределения при данных методах группирования Сравнение результатов методов,% (G)(1) KG), (V/f(2) RR(3) A (1),(2) A (2),(3) A (1),(3) 1. Центральный Восточный Южный 150222 136546 116175 10% 15% 23% 2. Центральный Восточный Южный Новый 131605 121856 97760 8% 20% 26% 3. Центральный Восточный 157892 148766 116002 6% 22% 26% 4. ЦентральныйВосточный (увеличение емкости) 156308 148490 121604 5% 18% 22% 5. Центральный 221943 221943 164237 0% 26% 26% Как показывают результаты расчетов, приведенные в таблице 2.16 снижение общей стоимости перевозки при группировании с учетом параметров спроса областей потребления и емкости центров аккумуляции (метод {/сА (к)}), по сравнению с горным методом (G), в котором не учитываются данные параметры задачи, составляет от 5% до 10%. Последующая корректировка координат расположения ЦАР (метод RR = {(G),(V),(Z),(NI)}) внутри области группирования позволит снизить стоимость перевозки ресурсов по сравнению с {(сА(к)} в среднем на 20%, по сравнению с (G) в среднем на 25%. Полученные результаты показывают эффективность применения разработанного метода при решении задачи размещения ЦАР.
В данном разделе определены условия, повышающие эффективность методов определения областей рационального расположения ЦАР, среди которых: - возможность выбора количества ЦАР; - определение центров группирования с учетом не только расстояний между объектами, но и с учетом спроса областей потребления и емкости центров группирования; - возможность учета характера ожидаемого спроса потребителя. Для учета данных условий при определении рационального расположения ЦАР разработан метод, учитывающий не только спрос областей потребления, но и недетерминированный характер параметров задачи.
В основу разработанного метода рационального расположения ЦАР положен принцип, объединяющий следующие методы: метод, определяющий центры аккумуляции ресурсов путем вычисления потенциалов взаимосвязи каждой точки; метод, вычисляющий центры аккумуляции ресурсов с учетом недетерминированности спроса, метод, корректирующий положение центра аккумуляции в зависимости от расположения закрепленных подобластей, метод нечетко-интервального задания исходных данных задачи, соответствующий интуитивным представлениям экспертов о прогнозируемых параметрах.
Результат решения задачи размещения ЦАР представлен множеством нечетких интервалов – координат размещения центров в зависимости от нечеткого спроса каждой подобласти, емкости центра группирования и расстояний между объектами группирования. Место расположения ЦАР определится не конкретными числовыми значениями, а нечетким интервалом, указывающим наилучшее возможное расположение ЦАР, характеризующееся не только расстоянием между объектами, но спросом, заданным в виде нечеткого интервала. Определение значений координат размещения в виде нечетких интервалов позволяет определить область для варьирования данными в зоне наилучших решений. Симбиоз методов позволяет скорректировать координаты размещения ЦАР после группирования, что ведет к снижению затрат на транспортировку до 25%. Данные результаты позволяют судить об эффективности предложенного метода решения задачи рационального размещения ЦАР.
Разработан подход к определению параметров функции принадлежности областей спроса к различным центрам группирования на основе вычисления потенциалов.
Разработана графическая интерпретация алгоритма по результатам предложенного метода определения рационального расположения ЦАР с учетом задания параметров в виде нечетких интервалов.
Разработано программное приложение, включающее совокупность элементов (модулей) системы, позволяющее обеспечить ввод исходных данных в виде нечетких интервалов. Данное программное обеспечение позволяет получить географическое расположение (координаты) ЦАР и общую стоимость транспортировки ресурсов через данные центры. Проведены экспериментальные исследования подтверждающие эффективность предложенного метода и удобство разработанного программного обеспечения.
Экспериментальное исследование результатов предлагаемого метода
Для реализации данной подпрограммы используется вспомогательный массив CKop[i,j,k,l,r], необходимый для пошагового уточнения массива C[i,j,k,l,r] (пошагового распределения имеющихся ресурсов). На начальном шаге CKop[i,j,к,I,г] =C[i,j,к,I,г]. Далее используя формулу (3.9) производится расчет уточняющих коэффициентов , , , , , по значению которых происходит переформатирование массива CKop[i,j,k,l,r]. Массив ограничений на имеющиеся ресурсы Ogr[s] определяется путем установления соответствия значениям CKop[i,j,k,l,r]=0. Элемент массива Ogr[s] представляет собой структуру поля, которой соответствуют: значению параметра A[i]; значению параметра B[J]; значению параметра Q[k]; значению параметра D[l]; значению параметра Р[г];
Среди значений параметров A[i], B[J], Q[k], D[f], P[r], соответствующих каждому элементу CKop[i,j,k,l,r]=0, выбирается наименьшее. Далее среди полученных наименьших значений, необходимо выбрать наибольшее значение и определить соответствующие этому значению индексы [i,j,k,l,r]. Формируется массив критических показателей Z[p]. Значения параметров, соответствующих индексам наибольшего, среди наименьших значений ограничений, уменьшаются на эту величину. После процедуры вычитания наименьшего значения из параметров A[i], B[j], Q[k], D[f], P[r], определяется параметр равный нулю. Сечение соответствующее нулевому значению удаляется из массива параметров, как исчерпанное. Процедура повторяется до размерности матрицы CKop[iJ,k,l,r]=0. Алгоритм подпрограммы Шаг 3. «Расчет значений целевой функции», представляет собой последовательное формирование функции оптимального распределения ресурсов.
Для реализации данной подпрограммы используется массив C[i,j,k,l,r] и массив критических значений Z[p]. Каждому элементу массива Z[p] ставится в соответствие элемент массива C[i,j,k,l,r], сумма произведений соответствующих элементов двух массивов формирует значение целевой функции.
Алгоритм подпрограммы Шаг 4. «Интерпретации полученного решения», представляет собой сопоставление массива Z[p] и массивов Potr[j], CRR[k] Trans[l], Prod[r]. Данное сопоставление позволяет выдать рекомендации по оптимальному планированию и размещению мощностей, обеспечивающих минимальную стоимость распределения ресурсов.
Обширный класс прикладных задач распределения ресурсов можно отнести к классу распределения ресурсов в системах транспортного типа [28, 218]. Алгоритмы и методы, применимые к решению транспортных задач имеют многообразные приложения, в частности при решении различного типа задач, не имеющих ничего общего с доставкой ресурсов потребителю. В этом случае величины затрат на перемещение ресурсов cij имеют различный смысл в зависимости от конкретной задачи. К таким задачам можно отнести следующие задачи [10, 38 – 42, 171, 228]. Оптимальное закрепление за станками операций по обработке деталей. В них cij является таким экономическим показателем, как производительность. Задача позволяет определить, сколько времени и на какой операции нужно использовать каждый из станков, чтобы обработать максимальное количество деталей. Оптимальные назначения или проблема выбора. Имеется S механизмов, которые могут выполнять R различных работ с производительностью cij . Задача 116 позволяет определить, какой механизм и на какую работу надо назначить, чтобы добиться максимальной производительности. Могут решаться следующие задачи: – задача составления расписания; – задача целераспределения; – задача перевозок с промежуточной обработкой; – задача перевозок с резервированием; – задача о сокращении производства с учетом суммарных расходов на изготовление и транспортировку ресурсов; – задача распределения мощностей каналов передачи данных провайдером сети Интернет; – задача о максимальном потоке; – задача о кратчайшем пути; – задача объемно-календарного планирования для предприятий с единичным и мелкосерийным характером производства; – задача сбалансированной загрузки распределенной вычислительной системы; – задачи планирования транспортировки газа; – задачи объемно-календарного планирования для нефтеперерабатывающих предприятий.
Для всех этих задач общим является: – параметры математической модели являются многоиндексными, причем число индексов может быть различным, в зависимости от рассматриваемой задачи; – ограничения математической модели, накладываемые на парамеры задачи распределения ресурсов, представляют собой систему линейных алгебраических неравенств транспортного типа, каждое из которых получается суммированием по некоторым индексам. При этом ограничения могут быть: – ресурсные ограничения элементов системы; – ресурсные ограничения связей между элементами системы; – ограничения суммарных объемов ресурсов [38].
Практическое применение методов решения распределительных задач происходит в рамках функционирования информационно-управляющих систем предприятий или организаций. Если говорить об организационной структуре информационно-управляющих систем, то она непосредственно связана со структурой предприятий или организаций, а также зависит от количества и видов решаемых задач [91]. Задача распределения ресурсов заключается в том, чтобы были соблюдены все ограничения системы, и решение определяло оптимальное функционирование системы, позволяющее эффективно принимать решения по организации и оперативному планированию производственных и распределительных процессов.