Содержание к диссертации
Введение
1. Исследование особенностей формализации и методов решения распределительных задач 14
1.1. Разработка системного подхода к решению распределительных задач 14
1.2. Методы моделирования при решении задач исследования операций 20
1.3 Аналитические модели распределительных задач 26
1.4. Алгоритмы решения распределительных задач 35
1.5. Формализация параметров задачи в виде нечетких интервалов '. 41
—ЬбгТеоретико-множественный подход
к моделям распределительных задач 50
1.7. Применение новых информационных технологий 55
1.8. Выводы 57
2. Разработка метода формализации и решения трипланарнои транспортной задачи с нечеткими параметрами 60
2.1. Формулировка и модель задачи с нечеткими параметрами 60
2.2. Метод построения начального опорного плана 72
2.3. Метод потенциалов для решения нечеткой трипланарной транспортной задачи 75
2.4. Алгоритм построения начального опорного плана 84
2.5. Алгоритмизация метода потенциалов 88
2.6. Выводы 94
3. Разработка метода формализации и решения триаксиальнои транспортной задачи с нечеткими параметрами 96
3.1. Формулировка и модель задачи с нечеткими параметрами 96
3.2. Исследование свойств нечеткой триаксиальнои транспортной задачи 106
3.3. Метод построения начального опорного плана 117
3.4. Метод потенциалов для решения нечеткой триаксиальнои транспортной задачи 122
3.5. Особенности алгоритмизации метода потенциалов для решения нечеткой триаксиальнои транспортной задачи 130
3.6. Выводы 133
4. Разработка проблемно-ориентированных программных приложений 135
4.2. Разработка структуры модуля решения распределительных задач с нечеткими параметрами 138
4.3. Программное приложение и примеры решения трипланарной транспортной задачи с нечеткими параметрами 141
4.4. Программное приложение и примеры решения триаксиальнои транспортной задачи с нечеткими параметрами 153
4.5. Выводы 161
Заключение 163
Список источников
- Аналитические модели распределительных задач
- Метод построения начального опорного плана
- Исследование свойств нечеткой триаксиальнои транспортной задачи
- Программное приложение и примеры решения трипланарной транспортной задачи с нечеткими параметрами
Введение к работе
Стабильное развитие экономики России напрямую зависит от повышения эффективности функционирования многочисленных предприятий различных отраслей промышленности. Наблюдается лавинообразное и скачкообразное комплексное развитие науки и техники, что сказывается во всех аспектах развития человеческого общества [1,2].
Существующая особенность изменений в настоящее время состоит в усложнении хозяйственно-производственной деятельности человека, в росте объемов работ и в их технологическом усложнении. Что подтверждается ростом числа, предприятий и организаций, внедрением новых технологий, ростом производства изделий в России.
Объектом исследования в диссертационной работе являются задачи исследования операций, такие как многомерные распределительные задачи (транспортные задачи линейного программирования), решение которых необходимо на предприятиях, успешное функционирование которых зависит друг от друга. Распределительные задачи применяются при переоснащении производственных объектов, управлении запасами, для оптимальной организации транспортных перевозок и прочее.
Решение задач транспортного типа необходимо при составлении оптимального плана перевозки груза от производителей непосредственно или поставщиков к потребителям, общее число которых может быть достаточно большим, порядка нескольких сотен. При этом целевой функцией является стоимость затрат на транспортировку груза.
Известно [9-15] решение многоиндексных распределительных задач, изучены их свойства, разработаны методы построения начальных опорных планов, метод потенциалов для решения этих задач, приближенные методы решения этих задач. Известны общие методы решения целочисленных многоиндексных задач, алгоритмы получения приближенного решения этих задач.
Оптимальное планирование транспортного процесса требует применения компьютерной техники, т.к. вычислительные сложности существуют из-за большого количества переменных, определяющих большую размерность задач, а также многоэкстремальностью целевой функции.
От успешного решения распределительных задач зависит эффективность производства, а повышение эффективности управления производством зависит от применения математических знаний, т.е. применения для нужд производства новых математических методов, включая методы исследования операций, методы моделирования, методы искусственного интеллекта. Это связано с комплексным изучением процессов и объектов, формализацией их параметров и разработкой методов моделирования для решения сложных производственных задач. Решение распределительных задач необходимо рассматривать в рамках системного подхода, применяя методы системного анализа.
Системному подходу, системотехнике, системному анализу, решению задач исследования операций уделяли внимание многие ученые, как в России, так и за рубежом [2-8,15-22]: Берталанфи Л., Валуев С.А., ВенцельЕ.С, Волкова В.Н., Гольштейн Е.Г., КвейдЭ., Месарович JVL, Михалевич B.C., Моисеев Н.Н., Оптнер С, Перегудов Ф.И., Раскин Л.Г., Садовский В.Н., Такахара И., Уемов А.И., Хемди А. Таха, Холл А., Юдин Д.В., Янг С. и многие другие.
При решении распределительных задач выбирается модель решения задачи, однако все известные методы ориентированы на конкретное численное задание параметров задачи и не допускают существование неопределенности в исходных параметрах. Реально при решении практических задач всегда невозможно гарантированно четко указать, какие численные значения будут иметь параметры распределительной задачи. Причинами подобного представления являются непредсказуемые изменения в структуре производителей, поставщиков и потребителей, неучитываемые воздействия во внешней среде, что влечет за собой невозможность точного установления начальных параметров. Так как параметры распределительной задачи не всегда могут быть оценены в физических единицах измерения, но могут быть выражены-качественными показателями,—то для -формализация-параметров применимы методы теории нечетких множеств [23 - 28].
Для решения распределительных задач разрабатываются специальные средства автоматизации в виде прикладных программ (информационно-советующих систем).
Принятие решения о выборе оптимального плана распределительной задачи может быть связано с применением методов искусственного интеллекта на основе обработки знаний экспертов. Теория искусственного интеллекта обладает наиболее эффективными методами решения слабоформализованных задач [25, 26, 29-35].
В диссертационной работе ставится задача развития известных методов решения распределительных (транспортных) задач при условии задания параметров задач в виде нечетких интервалов. Данный подход позволяет получать достоверные результаты в том случае, когда существует неопределенность при задании параметров, существуют ограничения допусков на изменения параметров задача. Диссертационная работа посвящена разработке моделей и методов решения трипланарных и триаксиальных распределительных задач при нечетком задании параметров в виде нечетких интервалов, что позволяет определять оптимальный план решения задачи также в виде нечетких интервалов. Это определяет и подтверждает актуальность диссертационной работы.
Диссертационные исследования в практическом аспекте направлены на проектирование проблемно-ориентированного прикладного программного продукта (модулей аналитического решения и модулей принятия решений) для применения в информационно-управляющих системах предприятий, решающих транспортные задачи.
Цель диссертационной работы состоит в развитии методов системного анализа, в частности, раздела исследования операций, связанного с решением -распределительных задач,-нечеткого ситуационного управления применительно" к транспортным задачам.
В соответствии с поставленной целью в диссертационной работе решаются следующие задачи:
- разработка системного подхода к решению трехиндексных распределительных задач, включающего формализацию и решение распределительной задачи как системы с определенными закономерностями, применением для моделирования, как аналитических, так и неформальных подходов;
-разработка модели, метода формализации трипланарной транспортной задачи с нечеткими параметрами;
- формулировка задачи и определение условий решения двойственной нечеткой трипланарной транспортной задачи, условий оптимальности плана нечеткой трипланарной транспортной задачи;
- разработка метода и алгоритмов построения начального опорного плана в виде нечетких интервалов или чисел нечеткой трипланарной транспортной задачи;
-разработка метода и алгоритмов решения нечеткой трипланарной транспортной задачи;
-разработка модели, метода формализации триаксиальнои транспортной задачи с нечеткими параметрами;
- определение необходимых и достаточных условий разрешимости нечеткой трипаксиальной транспортной задачи, условий существования невырожденного плана решения задачи;
- разработка метода и алгоритмов построения начального опорного плана, а также метод потенциалов для решения нечеткой триаксиальнои транспортной задачи и выполнена его алгоритмизация.
- разработка программных модулей для решения трипланарной и триаксиальнои транспортной задачи с нечеткими параметрами.
Объектом исследования в диссертационной работе являются математические модели трипланарных и триаксиальных распределительных задач, методы разработки моделей принятия решений, а также информационно-управляющая система для решения транспортных задач.
Математическими методами исследования в диссертационной работе являются методы исследования операций, методы функционального анализа, теория нечетких множеств и теория нечеткой логики, теория построения нечетких ситуационных моделей. В экспериментальных исследованиях применялось моделирование на ЭВМ.
Методологическую основу работы составляет концепция системности, суть которой есть представление и исследование моделей решения распределительных задач с нечеткими интервалами, интеллектуальных систем принятия решений применительно к транспортным задачам в условиях частичной априорной неопределенности и нечеткого задания критериальной функции.
Поставленная цель диссертационной работы и сформулированные в соответствии с целью задачи создали предпосылки для получения новых научных результатов в области математического моделирования для решения распределительных задач, проектирования интеллектуальных модулей принятия решений информационно-управляющих систем.
Новыми научными результатами диссертационной работы, выносимыми на защиту, являются:
-системный подход к решению трехиндексных распределительных задач, отличающийся тем, что для решения распределительных задач применяется последовательность методов системного анализа, для разработки математических моделей применять аналитические и неформальные подходы, а в условиях априорной неопределенности для формализации параметров задач применять нечеткие интервалы, лингвистические и нечеткие переменные, задать функции принадлежности нечетких переменных, а также правила принятия решений; -метод формализации и решения трипланарной транспортной задачи, отличающийся заданием параметров задачи в виде нечетких интервалов, заданием целевой функции, как нечеткой функции, определяющей величину транспортных издержек, формализацией условий разрешимости задачи, позволяющих определить оптимальный план транспортной задачи, содержащий параметры в виде нечетких интервалов;
- метод формализации и решения триаксиальной транспортной задачи, отличие которого состоит в формализации параметров в виде нечетких интервалов, нечеткой целевой функции, определением необходимых и достаточных условий разрешимости задачи, позволяющих определить невырожденный план задачи в виде нечетких интервалов;
Практическая ценность результатов исследований определена их применением на предприятиях в структуре информационно-управляющих систем, в задачах управления подготовкой производством, технико-экономического планирования, оперативного управления. Задание параметров задач в виде нечетких интервалов повышает степень информированности лиц, принимающих решения.
Диссертационная работа состоит из четырех разделов, заключения и приложений.
В первом разделе диссертации разработан системный подход к решению трехиндексных распределительных задач, рассмотрена формализация и решение распределительной задачи как системы, определены ее закономерности. Исследование опыта системного подхода позволило предложить для решения распределительных задач последовательность методов системного анализа.
Произведен анализ методов моделирования. Отмечено, что в математических моделях далеко не всегда могут найти отражение особенности всех факторов, от которых зависит решение задач, поэтому при разработке моделей_ применяют , неформальные подходы.--Рассмотрены—аналитические модели распределительных задач, модели достаточно часто встречающихся на практике трипланарных и триаксиальных транспортных задач.
Произведен анализ алгоритмов решения распределительных задач.
Так как существует необходимость формализации параметров при априорной неопределенности, связанной с такими факторами, как нестационарность, нелинейность и последействие, а также случайность, то рассмотрена возможность применения нечетких интервалов для описания параметров распределительных задач.
Разработан теоретико-множественный подход к моделям распределительных задач, позволяющий математическую схему модели представить в виде соответствий. Если параметры задачи задаются на вербальном уровне, предложено определить их в виде лингвистических и нечетких переменных и задать функции принадлежности нечетких переменных, а также правила принятия решений о плане перевозок.
Рассмотрены особенности применения новых информационных технологий для решения распределительных задач.
В втором разделе диссертации разработан метод формализации и решения трипланарной транспортной задачи с нечеткими параметрами. Определены условия, которым должен удовлетворять нечеткий план транспортной задачи при нечетком определении параметров. Получена в формальной виде модель нечеткой трипланарной транспортной задачи. Рассмотрено условие разрешимости нечеткой трипланарной транспортной задачи.
Сформулирована задача и определены условия решения двойственной нечеткой трипланарной транспортной задачи, условия оптимальности плана нечеткой трипланарной транспортной задачи.
Разработан метод и алгоритмы построения начального опорного плана в виде нечетких интервалов или чисел нечеткой трипланарной транспортной задачи. Разработан метод и алгоритмы решения нечеткой трипланарной
— транспортной задачи.- В третьем разделе диссертации разработан метод формализации и алгоритмы решения триаксиальной транспортной задачи при задании параметров модели в виде нечетких интервалов. Рассмотрены необходимые и достаточные условия разрешимости нечеткой триаксиальной транспортной задачи. Определены условия нечеткого баланса нечеткой триаксиальной транспортной задачи. Получены формулы для расчета плана нечеткой триаксиальной транспортной задачи. Определены условия и получен алгоритм для определения неразрешимости нечеткой триаксиальной транспортной задачи. Разработан метод и алгоритм построения начального опорного плана, а также метод потенциалов для решения нечеткой триаксиальной транспортной задачи и выполнена его алгоритмизация.
В четвертом разделе диссертации разработаны проблемно-ориентированные программные приложений, предназначенных для решения распределительных задач с нечеткими параметрами. Определено назначение распределительных задач в структуре информационно-управляющих систем, а также применение методов решения распределительных задач и их практическая значимость в задачах управления подготовкой производством, технико-экономического планирования, оперативного управления. Разработана структура программного модуля для решения трипланарной и триаксиальной транспортной задачи с нечеткими параметрами. Разработано программное приложение для решения трипланарной и триаксиальной транспортной задачи с нечеткими параметрами. Рассмотрены примеры решения задач, которые демонстрируют возможность проведения исследования. Итогом решения является определение оптимального нечеткого плана транспортной задачи, а также возможность эвристического поиска параметров задачи, удовлетворяющих условию минимизации целевой функции.
Заключение содержит выводы о работе.
Результаты работы внедрены в при выполнении в Таганрогском государственном радиотехническом университете госбюджетной НИР «Разработка и исследование методов аналитического синтеза интеллектуальных систем принятия решений и многокритериального управления в условиях неопределенности на основе современных информационных технологий», а также в учебном процессе.
Научные и практические результаты, полученные в диссертации и изложенные в статьях, использованы при подготовке и чтении лекций по дисциплине «Методы оптимизации», «Теория принятия решений», постановке лабораторных работ на кафедре системного анализа и телекоммуникация Технологического института Южного федерального университета в г. Таганроге.
Основные результаты докладывались и обсуждались на международной научной конференции «Статистические методы в естественных, гуманитарных и технических науках (СМ-2006)» (Таганрог, 2006), VIII Всероссийской научной конференции студентов и аспирантов «Техническая кибернетика, радиоэлектроника и системы управления» (Таганрог, 2006), международной научной конференции «Информационные технологии в современном мире» (Таганрог, 2006), международной научно-технической конференции «Интеллектуальные системы, «Интеллектуальные САПР» (Москва, ,2006), международной научной конференции «Проблемы развития естественных, технических и социальных систем» (Таганрог, 2007), международной научной конференции «Проектирование новой реальности» (ПНР-2007) (Таганрог, 2007).
По теме диссертации опубликованы монография, три статьи и шесть тезисов докладов в открытой печати. Все результаты, представленные в диссертационной работе, получены автором лично. В совместных научных публикациях имеет место неделимое соавторство.
Диссертация содержит 186 страниц машинописного текста, включая введение, четыре -раздела, - заключение, -список литературы _ из 110-ти наименований на 9-ти страницах, 49 рисунков, 12 таблиц, приложение на 12-ти страницах.
Аналитические модели распределительных задач
Прикладные задачи производственно-транспортного планирования являются наиболее широко распространенной разновидностью распределительных задач исследования операций. С решением транспортных задач системно связаны следующие задачи: - распределение заказов на поставки между предприятиями с учетом затрат на производство и транспортных издержек; - размещения производства, складов и технических средств; - проектирования сложных транспортных сетей и объектов (дорог, продуктопроводов, тепловых и электрических сетей); - рационального распределения грузопотоков между различными видами транспорта.
Отмечено [9], что математические сложности, возникающие при решении производственно-транспортных задач, связаны с их большой размерностью, многоэкстремальностью, наличием дискретных переменных. Рассмотрим классическую постановку транспортных задач [13, 16, 61 - 66].
Пусть существует п пунктов производства и m пунктов потребления однородного продукта. Для каждого і-го пункта производства задан объем производства ар-0, а для каждого j-ro пункта потребления задан объем потребления bj 0. Стоимость перевозки количества продукта х из пункта і в пункт j равна ci;j(x) и задана в виде матрицы Сц(х) задана.
Требуется составить план перевозки продукта, реализация которого позволит обеспечить все пункты потребления необходимым количеством продукта, причем, ни из какого пункта производства не вывозилось бы продуктов больше, чем там производится, а стоимость перевозки была бы минимальнойгФормализация этого требования представлена в виде формулы- Формализации задач вида (1.3)-(1.11) отличаются достаточно ясной постановкой задачи. Однако, функция стоимости перевозки c(i,j)x может быть линейной, выпуклой или вогнутой функцией от параметра х (количества перевозимого-продукта). В этом случае говорят о нелинейной транспортной (распределительной) задаче [65 - 69].
К числу достаточно часто встречающихся на практике распределительных задач относятся трехиндексные (трипланарные и триаксиальные) транспортных задач. Известна формулировка задач и изучены их свойства, разработаны методы построения начальных опорных планов и обобщен метод потенциалов для решения этих задач [11, 14,70-72] при условии задания параметров задач определенными числовыми значениями. Кратко рассмотрим существо этих задач. Известна формулировка и модель трипланарной транспортной задачи.
Пусть существуют предприятия, производящие однородный продукт (уголь, металлопрокат, вид сельхозпродукции и пр.), который необходимо доставить к потребителям транспортными средствами различных типов так, чтобы минимизировать транспортные издержки.
Отличие данной задачи от задач классической транспортной теории состоит в том, что в стоимость транспортировки единицы продукта зависит не только от взаимного расположения центров производства и потребления, но и от типа транспорта, и к ограничениям добавляются дополнительные ограничения на количество продукта, перевозимого транспортными средствами данного типа. Формализация данной задачи осуществляется следующим образом. Заданы следующие неотрицательные величины: -щ, ієі - количество продукции, находящейся в распоряжении i-ro предприятия; - bj, j є J - количество продукции, необходимое j-му потребителю; - dk, кєК - количество продукции, которое может быть перевезено всеми единицами транспорта k-го типа; - Сук, ієі, jeJ, кєК - стоимость транспортировки единицы продукта от i-ro предприятия к j-му потребителю транспортным средством к—го типа.
Множество чисел {сук}, ієі, JGJ, кєК называют трехиндексной матрицей размера mxnxp.
Если {xjjk}, ієі, JGJ, кєК - количество продукции, планируемое для перевозки от i-ro предприятия к j-му потребителю транспортным средством k-го типа, то множество чисел {хч-к} называют планом перевозки, причем размеры матриц {с-,ік} и {хцк} совпадают.
Множество элементов матрицы {сцк} с фиксированным значением одного индекса, например і, называют двумерным сечением ориентации (jk). Множество элементов матрицы {с к} с фиксированным значением значениями двух индексов, например j и і, называют одномерным сечением ориентации к. Одномерное сечение ориентации і называют столбцом, одномерное сечение ориентации j - строкой, а одномерное сечение ориентации к - колонкой.
Сумму элементов трехиндексной матрицы, принадлежащих некоторому одномерному сечению, называют аксиальной (осевой) суммой. Сумму элементов по двумерному сечению называют планарной (плоскостной).
Метод построения начального опорного плана
Метод построения начального опорного плана нечеткой трипланарной транспортной задачи соответствует методу последовательного распределения [14]. Рассмотрим модификацию данного метода для задачи, параметры которой могут быть заданы в виде нечетких интервалов или чисел.
Выберем произвольный элемент xiiJikj множества нечетких интервалов { xi,j,k, } и положим его равным Нечеткий интервал Xyiki входит в три ограничительных условия Если тіп{а.,Ь ,ск} — a , то первое из ограничительных условий выполнено, а для других двух справедливо нечеткое неравенство
Введем нечеткие интервалы Ь-и = Ь - а и k, = ck, Приняв значения остальных нечетких переменных в сечении матрицы Х нечетко равными нулю, исключим это сечение из множества нечетких интервалов { xijkb уменьшив, таким образом, размерность матрицы на единицу. Получим новую усеченную матрицу (множество нечетких интервалов { xijk}) размера (m-l)xnxp и новый вектор нечетких ограничений И = (aj,..., a j, ai+1,..., am, bj,..., bj,..., bn, Cj,..., ckj,..., cp}. Затем приведенная процедура продолжается. Тот элемент х к матрицы Х={ Хцк} (матрицы нечетких назначений), который на очередном шаге вводится в множество нечетко ненулевых компонент плана, будем называть ведущим. С целью упорядочения выбора очередного ведущего элемента, на первом шаге алгоритма в качестве ведущего выбирают элемент хш, а на каждом из последующих шагов - элемент xijk с минимальными значениями индексов i, j, k. Рассмотрим алгоритм построения начального опорного плана нечеткой трипланарной транспортной задачи, как строгую последовательность действий. После выполнения q шагов алгоритма определены следующие множества: - 1+ ={l?2,...,iq} - множество номеров сечений по индексам (j,k) с известными значениями нечетких интервалов xijk; - J+ ={l,2,...,jq} - множество номеров сечений по индексам (i,k) с известными значениями нечетких интервалов х»к; - K+q ={l,2,...,kq} - множество номеров сечений по индексам (i,j) с известными значениями нечетких интервалов xijk; I q)={iq+l,...,m}, J!q)={jq+l,...,n}, K[q)={kq+l,...,p} -множество сечений по индексам (j,k), (i,k), (i,j) с неизвестными значениями части нечетких интервалов Xjjk; -{ Uk} - матрица нечетких переменных, включая подматрицу {х;Чк}, ієІ(ч), j є J(q), кєК(ч) с неизвестными значениями нечетких интервалов xijk; o(q) _rn n (q) (q) n n v,(q) v,(q) n n (q) (qb вектор нечетких ограничений.
Затем осуществляется переход к выполнению следующего (q+2)-ro шага алгоритма.
Общее число шагов алгоритма равно га+п+р-2, так как на каждом шаге процедуры удовлетворяется одно из условий (2.1) - (2.3), а на последнем шаге все три ограничения нечеткой трипланарной транспортной задачи.
Так как полученное в результате применения метода построения начального опорного плана множество нечетких переменных удовлетворяется всеми трем условиям (2.1)-(2.3), то оно является планом нечеткой трипланарной транспортной задачи.
Найденный план нечеткой трипланарной транспортной задачи является опорным.
Действительно, на каждом шаге определяется одна ненулевая компонента плана, причем номера компонент, вычисленные на двух соседних шагах (q и q+І), отличаются друг от друга только одним индексом. Это означает, что к гиперграфу, содержащему после q шагов q ребер, на (q+l)-M шаге добавляется одно тупиковое ребро. Поэтому гиперграф, полученный на последнем, (т+п+р-2)-м, шаге, является вычеркиваемым и, следовательно, соответствующий ему план (утверждение 2.6) является опорным.
Следовательно, предложенный метод построения начального опорного плана и приведенный выше алгоритм гарантирует получение опорного плана нечеткой трипланарной транспортной задачи.
После получения опорного плана нечеткой трипланарной транспортной задачи осуществляется переход к её решению.
Предлагаемый в диссертации метод решения нечеткой трипланарной транспортной задачи является обобщением известного метода потенциалов [14] для решения трипланарной транспортной задачи с четко заданными параметрами.
Определение опорного плана происходит согласно методу, изложенному в предыдущем разд. 2.2. Затем выполняется процесс решения задачи, который состоит из конечного числа однотипных итераций, составляющих основной этап алгоритм решения.
Каждая итерация основного этапа состоит из двух шагов. На первом шаге проверяется оптимальность полученного в предыдущей итерации (или на предварительном этапе) опорного плана.
Исследование свойств нечеткой триаксиальнои транспортной задачи
Матрица П индексов системы состоит из нулей и единиц, причем в каждом ее столбце имеется три коэффициента, каждый из которых равен единице.
Система условий нечеткой триаксиальной транспортной задачи содержит три группы уравнений, причем каждая группа включает в себя ограничения на нечеткие суммы переменных в виде нечетких интервалов в одномерных сечениях одинаковой ориентации.
Группа нечетких ограничений (3.2) объединяет нечеткие ограничения на нечеткие суммы переменных в колонках Хц. Группа нечетких ограничений (3.3) объединяет нечеткие ограничения на нечеткие суммы переменных в колонках Xjk. Группа нечетких ограничений (3.4) объединяет нечеткие ограничения HajHe ieTKHe cyMMbi переменных в колонках Х . Поэтому-Группы уравнений -(3.2) - (3.4) называют соответственно группами условий типа ij, jk и ik [14].
В множестве Е0={1,2,...,1} номеров строк матрицы П выделим три подмножества Еь Е2 и Е3, порождаемых группами условий типа ij, jk и ik. Подматрицы Пі, П2 и П3, образованные из строк указанных подмножеств, имеют размеры, соответственно равные mnxs, npxs и mpxs, причем Ея = р,ХєЕ19 о=1 шДеЕ25 п,ХєЕ3, а в каждом столбце такой подматрицы содержится единица.
Система уравнений (3.2) - (3.4) в нечеткой триаксиальной транспортной задаче не является линейно-независимой.
Выделим из множеств I, J и К по одному произвольному индексу ijGl, jieJ, kxEK и запишем условия (3.2) - (3.4) следующим образом:
Утверждение 3.5. Система уравнений (3.2)-(3.4) нечеткой триаксиальной транспортной задачи содержит r=mnp-(m-l)(n-l)(p-l) линейно-независимых уравнений, причем следствиями являются уравнения (3.33) - (3.35) для любых произвольно выбранных значений индексов ib ji, kb Рассмотрим доказательство утверждения 3.5. Уравнения (3.33)-(3.35) для любых произвольно выбранных значений индексов ib jb ki. являются следствиями система уравнений (3.2)-(3.4), если они могут быть выражены линейной комбинацией системы ограничений (3.2)-(3.4) и уравнений (3.30) (3.32). Определим сумму левой и правой частей уравнения (3.30) по индексу получаем уравнение (3.34) 2-iXUik== jxk, т.е. уравнение (3.34) является линейной комбинацией уравнений (3.3 ). Определим сумму левой и правой частей уравнения (3.32) по индексу кє {l,2,...,krl,ki+l,...,p}=K\ki: получаем уравнение (3.35) 2-іХ ч і = «ц, т.е. уравнение (3.35) является j=i линейной комбинацией уравнений (3.32). Теперь исключим из системы уравнений (3.2)-(3.4) нечеткой триаксиальной транспортной задачи уравнения следствия (3.33) —(3.35).
Для того чтобы остальные r=mnp-(m-l)(n-l)(p-l) уравнений (3.30)-(3.32) были линейно-независимыми, достаточно показать, что в соответствующей матрице коэффициентов системы существует минор порядка г с неравным нулю определителем.
Пусть ii=m, ji=n, ki=p, т.е. из системы исключаются уравнения, соответствующие строкам, выделенным в матрице П серым цветом на рис. 3.1 и знаком «-» на рис. 3.2. Исключив эти строки из матрицы П, получим матрицу П . Составим подматрицу М из векторов-столбцов матрицы П, отмеченных на рис. 3.2 символом « ». Для примера, приведенного на рис. 3.1, подматрица М составляется из векторов М = {РЇП, Рш, Рх 31, 2П, Т2П, Ґ221, Р , Р 231, Р г}
Квадратная подматрица М, образованная из приведенного набора векторов, является треугольной матрицей с неравными нулю диагональными элементами. Определитель этой подматрицы М не равен нулю, что свидетельству етолинейной независимости "системы уравнений (ЗТЗ 0) (373 2)
Из утверждения 3.5 следует, что опорный план Х={х»к} нечеткой триаксиальной транспортной задачи содержит не более чем mn+mp+np-m-n-р+1 компонент, нечетко больших нуля. Если опорный план Х={ xijk} нечеткой триаксиальной транспортной задачи содержит p mn+mp+np-m-n-p+l нечетко положительных компонент, то такой план называется вырожденным.
Нечеткая триаксиальная транспортная задача называется вырожденной, если для ее решения существует хотя бы один вырожденный опорный план. Нечеткая триаксиальная транспортная задача называется невырожденной, если для ее решения не существует вырожденных опорных планов.
Как и для нечеткой трипланарной транспортной задачи основным методом решения нечеткой триаксиальной транспортной задачи является метод потенциалов, основанный на теории двойственности.
Программное приложение и примеры решения трипланарной транспортной задачи с нечеткими параметрами
В разд. 1.7 предложена структура информационно-управляющей системы (см. рис.1. 13), соответствующая поставленной в диссертации цели и решаемым задачам.
Согласно структуре информационно-управляющей системы модуль решения, как модуль обработки информации (см. рис. 1.13), имеет информационные связи-со следующими-модулями-: - база данных производителей; - база данных стоимости перевозки; - база данных потребителей; - база знаний; - модуль сопряжения с оператором (модуль ввода/вывода); - модуль выдачи решения.
Для разработки проблемно-ориентированного программного приложения необходимо определить структуры баз данных, организацию и содержание баз знаний, а также структуру модуля решения распределительных задач с нечеткими параметрами.
Базы данных предназначены для хранения исходных и промежуточных данных, а их структура соответствует классу реляционных баз данных ведущих производителей (Oracle, Sybase, Informix, Ingres и т.п.), основанных на международных стандартах SQL [108, 109], широко применяемых при формализации проектирования информационно-управляющих систем и систем управления базами данных (СУБД).
Перечисленные выше базы данных содержат необходимую структурированную информацию о производителях и видах изделий (товаров), о потребителях, об организациях, обеспечивающих перевозки, стоимости перевозок на определенных видах транспортных средств. Так как разработка структур баз данных на настоящий момент времени является достаточно тривиальной задачей, то в диссертации не будет рассматриваться решение этой задачи.
Отметим, что оператору предоставляется возможность просмотра баз данных, получения из них необходимых сведений, возможность редактирования баз данных.
База знаний предназначена для хранения долгосрочных данных, определяющих задание экспертами нечетких— интервалов, —задание лингвистических переменных, функций принадлежности нечетких переменных, а также логических правил вывода для принятия решения в том случае, когда распределительные задачи с нечеткими переменными не имеют нечеткого оптимального решения.
Модуль обработки информации содержит программные модули, реализованные в соответствии с моделями решения трипланарной и триаксиальной транспортных задач с нечеткими параметрами. Задача модуля принятия решения состоит в автоматическом выполнении анализа данных, получения решения задач и вывода решения. Программные модули и структура из взаимодействия зависит от выбранного языка программирования, но все они созданы с применением средств библиотеки фонда Microsoft.
Перечень программных модулей для решения трипланарной транспортной задачи с нечеткими параметрами следующий: - transportask-gui2 - основной файл, определяющий объекты и структуру; - transportask-gui2.vcproj - проектный файл, содержащий информацию о платформах, конфигурациях, и проектных особенностях разработанного приложения; - transportask-gui2.h - файл заголовка, включает другие проектные заголовки и объявляет прикладной класс Ctransporttaskgui2App; - transportask-gui2.cpp - основной прикладной исходный файл, который содержит прикладной класс Ctransporttaskgui2App; - transportask-gui2.rc - внесение в список всех ресурсов Windows Microsoft, которые программа использует, включает изображения, массивы, и курсоры, которые сохранены в подсправочнике RES; - res\transportask-gui2.ico - файл изображений, изображение включено главным файлом ресурса transportask-gui2.rc; - res\transporttaskgui2.rc2 - файл содержит ресурсы, которые не отредактированы-Microsoft-Visual-G-H-;— - transportask-gui2Dlg.h, transportask-gui2Dlg.cpp - the dialog - файлы класса Ctransporttaskgui2Dlg диалога, шаблон диалога находится в transportask-gui2.rc; - StdAfx.h, StdAfx.cpp - файлы используются для работы файлов transportask-gui2.pch и StdAfx.obj; - transportask-gui2 .manifest - прикладные файлы загрузки.
Перечень программных модулей для решения триаксиальной транспортной задачи с нечеткими параметрами следующий (язык программирования - Pascal): - Unit 1.pas - файл вывода результатов моделирования; - trip.pas - файл, содержащий процедуры расчетов; - RegistryExt.pas — файл согласования программного приложения с операционной системой Windows; - Master.pas - файл описания работы «мастера» ввода данных; - Main.pas - файл главного диалогового окна;
