Моделирование транспортных процессов

МОДЕЛИРОВАНИЕ ТРАНСПОРТНЫХ ПРОЦЕССОВ Отличительной особенностью математических моделей, создаваемых в настоящее время, является их комплексность, связанная со сложностью моделируемых объектов. Это приводит к усложнению модели и необходимости совместного использования нескольких теорий из разных областей знания, применения современных вычислительных методов и вычислительной техники для получения и анализа результатов моделирования. В случае сложных объектов удовлетворить всем предъявляемым требованиям в одной модели обычно невозможно. Приходится создавать целый спектр моделей одного и того же объекта (в некоторых случаях — иерархическую совокупность «вложенных» одна в другую моделей), каждая из которых наиболее эффективно решает возложенные на нее задачи. Необходимость массового построения моделей требует разработки некоторой совокупности правил и подходов, которые позволили бы снизить затраты на разработку моделей и уменьшить вероятность появления трудно устранимых впоследствии ошибок. Подобную совокупность правил можно было бы назвать технологией создания математических моделей. Процесс математического моделирования Процесс построения любой математической модели можно представить последовательностью этапов: 1. Обследование объекта моделирования и формулировка технического задания на разработку модели (содержательная постановка задачи); 2. Концептуальная и математическая постановка задачи; 3. Качественный анализ и проверка корректности модели; 4. Выбор и обоснование выбора методов решения задачи; 5. Поиск решения; 6. Разработка алгоритма решения и исследование его свойств, реализация алгоритма в виде программ; 7. Проверка адекватности модели; 8. Практическое использование построенной модели. Как известно, внутренний водный транспорт в процессе перевозки и обработки грузов, взаимодействует с грузоотправителями, грузополучателями и смежными видами транспорта. Большое количество факторов, влияющих на транспортный процесс по времени, приводит к тому, что состояние объектов и ситуаций, из которых складывается результирующий процесс, имеет значительную вариацию, размер которой зависит не только от внутренних особенностей, присущих ВВТ, но и от постоянного воздействия внешних источников на процесс перевозок. Всё это вносит аспект неопределенности в управление работой флота и портов, порождает факторы трудно предсказуемые заранее, то есть появляются операции и процессы, которые в математики определяются как случайные. С целью исследования и математической формализации этих процессов используют вероятностные методы. При исследовании статистических данных эти методы опираются на математическую статистику – раздел прикладной математики, посвященный методам обработки и анализа статистических данных (дисперсионный, корреляционный, регрессионный анализы), и теорию вероятностей, которая изучает случайные величины и процессы. Развитие вероятностных методов в применении к реальным системам обслуживания в различных сферах человеческой деятельности привело к созданию самостоятельной прикладной области случайных процессов – теории массового обслуживания. На внутреннем водном транспорте эта теория изучает потоки различных заявок (судов, вагонов, пассажиров, информации и т.д.), поступающих в системы обслуживания (порты, шлюзы, пассажирские вокзалы, вычислительные центры и т.д.), с целью регламентации их поступления и обслуживания, а также определения оптимальных режимов работы обслуживающих систем. Дальнейшее расширение применения вероятностных методов при решении практических задач породило определенные трудности аналитического характера. Это привело к созданию численного метода решения математических задач моделирования случайных величин – метода статистических испытаний (Монте-Карло). С появлением компьютеров данный метод получил широкое распространение, включив в себя ряд элементов эвристики и аналитического моделирования; произошел синтез теоретического и экспериментального способов описания реальных процессов, а сам метод все чаще стали называть имитационным моделированием. Важнейшей задачей планирования является его оптимизация, то есть выбор наилучшего варианта из множества возможных решений. Математической наукой разработаны различные методы оптимального планирования и управления разнообразными процессами в технике, экономике, военном деле. Основные понятия моделирования и классификация моделей Понятие моделирование Процесс моделирования связан с построением модели исследуемого объекта. Основная цель моделирования: исследовать реальные объекты, процессы, событий и предсказать результаты будущих наблюдений. Основные этапы моделирования: - исследование реального объекта или процесса (изучение закономерностей, характеристик); - построение модели – описание исследуемого объекта или явления; - решение математической задачи, к которой приводит модель; - интерпретирование полученных из модели следствий; - проверка адекватности модели (соответствие полученных результатов реальному поведению объекта); - модификация модели. Математическая модель – представляет собой формализованное описание какого-либо явления или объекта реального мира на языка математики. Основные направления применения моделирования для решения транспортных задач: - прогнозирование объемов перевозок и технико-эксплуатационных показателей; - обоснование структуры флота; - поиск кратчайших расстояний между пунктами транспортной сети; - оптимизация распределения ресурсов; - маршрутизация перевозок; - выбор транспортного средства и схем перевозок; - распределение транспортных средств по объектам перевозок; - разработка планов, графиков и расписаний; - согласование работы транспортных средств и терминалов и др. Также, математические методы и модели закладываются в основу алгоритмов функционирования автоматизированных рабочих мест специалистов по организации перевозок и управлению на транспорте. Математическая модель представляет собой описание задачи в виде совокупности соотношений (уравнений, неравенств, логических условий), определяющих связи между параметрами функционирования исследуемой системы, ограничениями и критериями оптимальности. Математическая модель должна отражать связи между входными и выходными параметрами системы и является основой для вычислений значений критериев и проверки ограничений. В результате необходимо получить оптимальное решение. Оптимальное решение – это такое решение, которое обеспечивает экстремум (максимум или минимум) целевой функции (критерия оптимальности) при выполнении заданной системы ограничений. Классификация моделей и сфера их применения при моделирования транспортных процессов 1.По временной зависимости математические модели делятся на: - статические – рассматриваются на конкретный момент времени; - динамические – процесс или явление рассматриваются в динамике. 2.Динамические модели относительно своего рассматриваемого состояния во времени могут быть: - непрерывными – состояние системы описывается в каждый момент времени; - дискретными – состояние системы описывается в фиксированные моменты времени. 3.По характеру зависимости модели могут быть: - стохастические – в таких моделях зависимости носят случайный характер; - детерминированные – в таких моделях зависимости носят неслучайный характер. 4.По числу оптимизируемых параметров различают: - одномерные модели – содержат один оптимизируемый параметр; - многопараметрические – содержат несколько оптимизируемых параметров. 4.По возможным значениям оптимизируемых параметров решения модели могут быть: - вещественные; - целочисленные (дискретные). 5.Модели, в которых критерий оптимальности может иметь несколько локальных экстремумов называют многоэкстремальным. 6.По наличию ограничений: - условной оптимизации - модель с ограничениями (относится к задачам математического программирования); - безусловной оптимизации – модель без ограничений. 7.По характеру критериев и ограничений: - задачи линейного программирования – модель оптимизации с линейными критериями и ограничениями; - задачи нелинейного программирования (в том числе динамического и геометрического программирования) – при нелинейных критериях и ограничениях. 8.В зависимости от условий внешней среды и степени информируемости об её состоянии различают следующие модели принятия решений: - в условиях определенности; - в случайных условиях (условиях риска); - в условиях неопределенности; - в условиях конфликтных ситуаций (противодействия, «активного противника»). 9.По способу исследования и оптимизации различают следующие модели: - детерминированные – аналитические или численные; - случайного (статистического) поиска. При исследовании статистических данных эти методы опираются на математическую статистику – раздел прикладной математики, посвященный методам обработки и анализа статистических данных (дисперсионный, корреляционный, регрессионный анализы), и теорию вероятностей, которая изучает случайные величины и процессы. Развитие вероятностных методов в применении к реальным системам обслуживания в различных сферах человеческой деятельности привело к созданию самостоятельной прикладной области случайных процессов – теории массового обслуживания. На внутреннем водном транспорте эта теория изучает потоки различных заявок (судов, вагонов, пассажиров, информации и т.д.), поступающих в системы обслуживания (порты, шлюзы, пассажирские вокзалы, вычислительные центры и т.д.), с целью регламентации их поступления и обслуживания, а также определения оптимальных режимов работы обслуживающих систем. Дальнейшее расширение применения вероятностных методов при решении практических задач породило определенные трудности аналитического характера. Это привело к созданию численного метода решения математических задач моделирования случайных величин – метода статистических испытаний (Монте-Карло). С появлением компьютеров данный метод получил широкое распространение, включив в себя ряд элементов эвристики и аналитического моделирования; произошел синтез теоретического и экспериментального способов описания реальных процессов, а сам метод все чаще стали называть имитационным моделированием. Имитационное моделирование представляет собой экспериментальный метод исследования реальной системы по ее имитационной модели, который сочетает особенности эксперименталь­ного подхода и специфические условия использования вычислительной техники. Важнейшей задачей планирования является его оптимизация, то есть выбор наилучшего варианта из множества возможных решений. Кроме того, модели различают в зависимости от типа (вида) математических моделей. Детерминированные модели транспортных процессов Эксплуатационная постановка и математическая формализация транспортной задачи Транспортная задача – это задача об оптимальном плане перевозок однородного груза из однородных пунктов отправления в однородные пункты назначения на однотипных транспортных средствах с предопределенным количеством со статичными данными и линейным подходом. По критерию оптимизации выделяют следующие типы транспортной задачи: - критерий стоимости – достижение минимальных затрат на перевозку; - критерий расстояния – минимального расстояния перевозки; - критерий времени – минимальные затраты времени на перевозку. Транспортная задача является частным случаем задачи линейного программирования, которая может быть решена оптимальным методом. Решение данного рода задач специальными методами позволяет существенно упростить её решение. Математическая постановка (формулировка) транспортной задачи. Имеется m пунктов отправления некоторого однородного груза и n пунктов его потребления (назначения). Для каждого пункта отправления i=1,2,…,m и пунктов назначения j=1,2,…,n заданы следующие величины: Количество груза ai в пункте отправления и требуемое количество груза bj в пункте назначения, затраты на перевозку единицы груза из i-го пункта отправления в j-тый пункт назначения – Cij. Предположим, что суммарное количество имеющихся в наличии грузов равно суммарному количеству требующихся (). Требуется составить план перевозок, позволяющий полностью вывести грузы всех пунктов отправления, полностью обеспечивающий потребность всех пунктов назначения и дающий минимум суммарных затрат на перевозку. Объемы перевозок грузов из пунктов отправления в пункты назначения обозначаются xij. Математическая запись: (1) (2) (3) Методы решения. Транспортную задачу можно решить симплекс-методом, но в силу ряда особенностей для задач малой размерности существуют более простые методы её решения, например, метод потенциалов. Форма записи. Условие задачи записывают в таблице, занося в ячейки количество перевозимого груза из пунктов отправления в пункты назначения, а также соответствующие стоимости перевозки - Cij. Форма записи исходных данных транспортной задачи показана в таблице 1. Требуется определить опорный план и затем, путем последовательных итераций найти оптимальное решение. Таблица 1 Форма записи исходных данных транспортной задачи Пункт отправления/ Пункт назначения F1 F2 … Fn Наличие S1 C11 C12 … C1n a1 S2 C21 C22 … C2n a2 …. … … … … … Sm Cm1 Cm2 … Cmn am Потребность b1 b2 … bn Опорный план можно найти, используя следующие методы: - северо-западного угла; - минимального элемента. Метод северо-западного угла заключается в том, что на каждом этапе максимально возможным числом заполняют левую верхнюю часть оставшейся части таблицы. Метод минимального элемента заключается в сокращении побочных перераспределений грузов между потребителями: 1. Из таблицы стоимостей выбирают наименьшую и в клетку, которой она соответствует, записывают наибольшее из возможных чисел. 2. Проверяют строки отправителей на наличие строк с израсходованными запасами и столбцы потребителей на наличие потребности, которые удовлетворены полностью. Такие строки и столбцы дальше не рассматривают. 3. Если требуется, то описанные выше операции повторяются Метод потенциалов для решения транспортной задачи С помощью рассмотренных методов построения первоначального опорного плана можно получить вырожденный или невырожденный опор­ный план. Построенный план транспортной задачи как задачи линейного программирования можно было бы довести до оптимального с помощью симплексного метода. Однако из-за громоздкости симплексных таблиц, со­держащих тп неизвестных, и высокой трудоемкости вычислений для получения оптимального плана используют более простые методы. Наиболее часто применяются метод потенциалов (модифицированный распределительный метод) и метод дифференциальных рент. Метод потенциалов является модификацией симплекс-метода решения задачи линейного программирования применительно к транспортной задаче. Он позволяет, отправляясь от некоторого допустимого решения, получить оптимальное решение за конечное число итераций. Решение транспортной задачи методом потенциалов основано на привлечении потенциальности в качестве признака оптимальности. Для того чтобы план перевозок был оптимальным необходимо и достаточно, чтобы были такие числа ui (i=1;m) и vj (j=1;n), для которых выполняется: - для занятых клеток: vj-ui=cij (условие 1); - для свободных клеток vj-ui<=cij (условие 2). Числа vj и ui, для которых выполняется только первое условие называются квазипотенциалами. Числа vj и ui, для которых выполняется оба условия, называются потенциалами. Для определения m+n квазипотенциалов ui и vj всегда есть (m+n-1) уравнение вида vj-ui=cij. Так как число квазипотенциалов на единицу больше, чем число уравнений, из которых они определяются, то один из квазипотенциалов принимают равным произвольной константе. Метод потенциалов заключается в том, что задача решается с помощью конечной последовательности итераций. 2.3. Алгоритм метода потенциалов Алгоритм решения транспортной задачи методом потенциалов: 1. По одному из известных способов (северо-западного угла, метод минимального элемента) находится исходный опорный план перевозок 2. Полученный исходный план проверяется на вырожденность, т.е. в нем должно быть (m+n-1) занятых клеток. Если опорный план вырожденный, то одну из свободных клеток заполняют нулевой перевозкой, но так, чтобы опорный план оставался ацикличным. 3. Для найденного опорного плана вычисляются соответствующие ему квазипотенциалы, пользуясь уравнением u1=const, vj-ui=cij для занятых клеток плана. 4. Выполняется проверка квазипотенциалов найденного плана на потенциальность, т.е. проверяется, выполняется ли соотношение vj-ui<=cij в свободных клетках плана. Если проверка на потенциальность дает положительный результат для всех свободных клеток, то данный опорный план оптимальный и задача решена, Если же обнаружены свободные клетки, в которых потенциальность не имеет места, т.е. vj-ui>cij, то с помощью одной из этих клеток производится улучшение опорного плана перевозок по правилу пересчета по циклу. 5. для улучшения опорного плана повторяем шаги 2,3,4,5. Если на шаге 4 обнаружится несколько непотенциальных клеток, то в план вводят ту из свободных клеток, в которой расхождение между разностью потенциалов и транспортной издержкой наибольшее. Циклом в таблице условий транспортной задачи, называется ломаная линия, вершины которой расположены в занятых клетках таблицы, а звенья - вдоль строк и столбцов, причем в каждой вершине цикла встречается ровно два звена, одно из которых находится в строке, а другое - в столбце. Если ломанная линия, образующая цикл, пересекается, то точки самопересечения не являются вершинами. Особенности при решении транспортной задачи (вырожденность, закольцовывание, несбалансированность) На начальном этапе решения транспортной задачи необходимо получить первоначальный опорный план. После получения опорного плана необходимо проверить его на невырожденность. Невырожденным называется такой опорный план, у которого число базисных (занятых) ячеек равно r = n + m - 1,  где  m - количество строк, n - количество столбцов транспортной задачи.  Вырожденным является такой план, у которого число перевозок меньше чем r = n + m - 1. Правило: количество базисных (заполненных) клеток в первоначальном плане ВСЕГДА должно быть равно m + n - 1, где m - количество поставщиков, n - количество потребителей транспортной задачи. Транспортная задача называется открытой (незамкнуной, несбалансированной), если не соблюдается баланс между наличием груза и его потребностью. Для того, чтобы применить к задаче метод потенциалов, необходимо привести открытую транспортную задачу к закрытой модели. Т.е. необходимо выполнить преобразования, при которых , "то, что есть, станет равным, тому, что надо". Все очень просто. Если не хватает груза (товара), чтобы удовлетворить потребности пунктов назначения (магазинов), нужно добавить мнимого (фиктивного) поставщика.  Если предложение превышает над спросом, добавим мнимого (фиктивного) потребителя. В открытой транспортной задаче это реализуется добавлением строки или столбца, в зависимости от того, чего не хватает. Так как в реальности фиктивный поставщик (потребитель) не существует, то стоимость доставки до него от любого пункта равна нулю. Чтобы привести открытую транспортную задачу к закрытому (замкнутому) виду, добавляем столбец (строку) с нулевыми стоимостями. • Если превышают запасы - добавляем фиктивного потребителя (столбец); • Если превышает спрос - добавляем фиктивного поставщика (строку). Для условий внутреннего водного транспорта наибольший интерес представляют варианты параметрической задачи, в которых изменяются в некоторых пределах величина ресурсов bj, а также технологические коэффициенты aij.