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

  Министерство  образования и науки Российской Федерации

Государственное образовательное учреждение высшего  профессионального образования

Северо-Западный государственный заочный технический  университет 

Институт  автомобильного транспорта 

Кафедра организации  перевозок 

Курсовой  проект по дисциплине

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

    Студент: 5 курса, шифр: 7603011003

    Форма обучения: очная дата: 07.01.2012

    Специальность: 190701.65 
 

    Подготовил:

    Образцов  Глеб Александрович    
 

    Преподаватель:

    Янчеленко В.А. 
 
 
 
 

    Санкт-Петербург

    2012г.

   Содержание. 

1. Роль математических методов в принятии эффективных  управленческих решений при автомобильных  перевозках. Виды моделей и эвристические  методы решения задач……………………………………...…...…3
2. Понятие корреляционно-регрессионный анализ………….......…….....7
3. Модели линейного программирования в решении задач автомобильных перевозок. Основные понятия, графоаналитический и симплексный методы………………………………………………………………….10
4. Маршрутизация перевозок помашинными отправками  основные этапы решения задач…………………………………………………………...…….15
5. Методы определения кратчайших расстояний перевозок………......18
6. Методы планирования перевозок по сборно-развозочным маршрутам……………………...………………………………………………………24
7. Понятие о теории массового обслуживания в решении задач  автомобильных  перевозок…………………………………………………………..30
8. Задача 1………………………33
9. Задача 2………………………36

1.  РОЛЬ МАТЕМАТИЧЕСКИХ  МЕТОДОВ В РЕШЕНИИ  ПРОИЗВОДСТВЕННЫХ  ЗАДАЧ АВТОМОБИЛЬНОГО  ТРАНСПОРТА.

  Транспортная  система – это совокупность реальных объектов и связей между ними, которые  используются на определенной территории для выполнения перевозок.

  Автомобильно-дорожный комплекс России (АДК) включает в себя: автотранспортные предприятия и  транспортные средства; автомобильные  дороги и организации, поддерживающие их в рабочем состоянии; организации, обеспечивающие ремонт и техническое  обслуживание автотранспортных средств; организацию и систему контроля транспортными потоками на дорожной сети; места стыковки автомобилей  с другими видами транспорта.

  АДК России имеет  все признаки большой сложной, динамической системы, так как включает наличие  большого числа взаимодействующих  подсистем и элементов, имеет  иерархический характер построения (подчиненности), множественность функций, наличие управления, взаимодействие с окружающей средой и воздействие  случайных факторов, большую размерность  задач.

  По мощности осваиваемых пассажиро и грузопотоков отдельные транспортные подсистемы АДК принято подразделять на 7 групп (систем).

  1. Микросистемы (маятниковые маршруты с одним автомобилем  и

  обратным холостым пробегом).

  2. Особо малые   системы (кольцевые  и маятниковые  маршруты с одним автомобилем)  различных типов  с несколькими  работающими транспортными средствами.

   3. Малые системы  – кольцевые и маятниковые  маршруты различных типов с  несколькими работающими транспортными  средствами. Сюда относятся небольшие транспортные фирмы и транспортные отделы фирм малого бизнеса.

   4. Средние системы – совокупность  нескольких малых систем. Сюда  относятся, например, железобетонные  заводы, контейнерные станции, базы  снабжения вместе с транспортными  средствами и получателями товаров.

  5. Большие системы  – сюда относятся автомобильные  парки и грузовые АТП с подвижным  составом и их маршрутами.

   6. Особо большие  системы  - автотранспортные тресты, производственные управления и  объединения.

   7. Суперсистема  включает множество вышеуказанных  систем, например Департамент автомобильного  транспорта России.

  Автомобильные и транспортные процессы в вышеуказанных  системах включают большое количество задач по управлению АДК, разработке технологических схем  организации  перевозок, формированию систем оптимальных  грузопотоков, маршрутизации перевозок, формированию сменно-суточных планов, выбору кратчайших путей движения, закреплению потребителей за поставщиками, транспортные задачи с запретами  и по критерию  времени и так  далее.

  Для решений  задач разрабатываются новые  методики, базирующиеся на использовании  новых технологий и методов расчета.

  К таким новым  технологиям относятся моделирование  и использование моделей для  решений задач управления и принятия решений. Во многих ситуациях они  являются единственно возможным  и эффективным методом, позволяющим  получить ответ на поставленный вопрос.

  Модель –  это аналог, макет или иной вид  отражения наиболее важных черт, свойств  и результатов транспортных систем и процессов.

   Адекватность  модели – это свойство модели быть основой для прогнозирования  событий, протекающих в транспортных системах и процессах, и давать подтверждаемые результаты.

   Моделирование – это замещение  одного объекта другим с целью  получения информации о важнейших  свойствах объекта–оригинала с  помощью объекта– модели.

  Теория моделирования  – это теория замещения одних  объектов– оригиналов другими объектами (моделями) и исследования свойств объектов на их моделях.

  В зависимости  от характера изучаемых процессов  в системе все виды моделирования  могут быть разделены: на детерминированные и стохастические; статические и динамические; дискретные, непрерывные и дискретно-непрерывные.

  Детерминированное моделирование отображает детерминированные  процессы, то есть процессы, в которых  предполагается  отсутствие всяких случайных воздействий.

  Стохастическое  моделирование отражает вероятностные  процессы и события. В этом случае анализируется ряд  реализаций случайного процесса   и оцениваются средние характеристики.

  Статическое моделирование  служит для описания поведения объекта  в какой-либо момент времени, а динамическое моделирование отражает поведение  объекта во времени.

  Дискретное  моделирование служит для описания процессов, которые предполагаются дискретными, а непрерывное отражает непрерывные процессы в системах.

  В зависимости  от формы представления объекта (системы) можно выделить мысленное  и наглядное моделирование.

   При наглядном моделировании на базе представлений человека о реальных объектах создаются различные наглядные модели, отображающие  явления и процессы, протекающие в объекте (механические, графические и другие).

   При исследовании  транспортных процессов  и систем на автомобильном транспорте наиболее широко используется математическое моделирование, являющееся разделом мысленного моделирования.

  Под математическим моделированием понимают  установление соответствия данному реальному  транспортному процессу или системе  некоторого математического объекта, называемого  математической моделью, и исследование этой модели, позволяющее  получить характеристики рассматриваемого реального транспортного процесса и транспортной системы. 

  Любая математическая модель, как и всякая другая описывает  реальную систему и процесс лишь с некоторой степенью приближения  к действительности.

  При решении  практических задач автомобильно-дорожного  комплекса, как правило, не применяются  строгие методы решений. Широко используются смекалка и интуиция инженерно-технического и управленческого персонала.

  В модели реальных транспортных процессов и систем вносятся упрощающие допущения. Такой  метод позволяет подобрать для  решаемой задачи из набора средств  современной математики приемлемый алгоритм и найти хотя бы приближенное решение.

  Такие методы решений задач в условиях, когда  нельзя точно определить границы  их применения и оценить допустимые погрешности, называются эвристическими.

  Преимущества  математического моделирования  перед другими видами (графическим, аналоговым, механическим и т.д.) заключаются  в широком использовании математических моделей, низкой стоимости их создания, быстром получении результатов  исследований, возможности проведения расчетных экспериментов и проверки правильности построения модели.

   Конечно, математическая  модель всегда является упрощенной, однако она является достаточно наглядной  и позволяет адекватно описать  транспортную систему и транспортный процесс.

   Математическое моделирование при  решении задач АДК можно разделить  на оптимизационное (аналитическое) и имитационное. Соответственно математические модели  можно разделить на аналитические и имитационные.

  2. КОРРЕЛЯЦИОННО-РЕГРЕССИОННЫЙ АНАЛИЗ МАТЕМАТИЧЕСКИХ МОДЕЛЕЙ

  Корреляция  в переводе с латинского обозначает соответствие или взаимосвязь. Корреляционная зависимость отражает связь между величинами, когда определенным значениям факториальных величин соответствует много значений зависимой величины.

  Корреляционный  анализ в задачах моделирования  транспортных процессов и систем имеет фундаментальное значение, так как теснота корреляционной связи определяет структуру модели. Высокая и полная  корреляционная связь требует объединения величин. Отсутствие или слабость корреляционных связей позволяют рассматривать  величину как независимую.

  Во многих случаях  выбор независимых величин на базе исследования их корреляционных связей требует дополнительного  экспертного исследования и решения.

  Например, при  формировании имитационной модели (см. пример 1.2 и рис. 1.1) независимость источников грузопотоков между собой, а также и получателей грузов между собой требует корреляционного анализа. При наличии зависимости (например, дополнительных перевозок грузов между источниками грузопотоков) требуются изменение структуры имитационной модели, учет этих связей.

   Корреляционная  связь между двумя переменными  изучается с помощью парной корреляции. О тесноте корреляционной связи  можно судить по характеру расположения точек на графике, связующем переменные х и у. Такой график называется полем корреляции (рис. 2.1). Разброс точек по всему полю свидетельствует об отсутствии корреляции (рис. 2,а), рис. 2,б свидетельствует о слабой умеренной корреляции, рис. 2,в - о полной корреляции.

   Численное значение корреляционной связи  оценивается коэффициентом корреляции  r.

  Задачей регрессионного анализа является установление вида зависимости (1.2) (зависимости параметра  оптимизации у от факториальных  величин х₁, х₂…х_n). Указанная зависимость называется уравнением регрессии. Корреляционно-регрессионный анализ позволяет прогнозировать развитие рассматриваемого явления и решать задачу построения модели и ее оптимизации. Регрессионный анализ введен в практику расчетов английским математиком и механиком У.Р. Гамильтоном в 1840-х годах.

  При проведении регрессионного анализа применяются  понятия парных и множественных  коэффициентов регрессии. На рис. 2.2 показано корреляционное поле парной линейной зависимости, отказов автомобилей  в эксплуатации от числа капитальных  ремонтов. Рассмотрение расположения точек на поле рис. 2.2 позволяет говорить о слабой корреляционной зависимости, разброс точек на рис. 2.2 примерно соответствует рис. 2.1,б. Из рис. 2.2 видно, что если для каждой величины х найти средние значения у и соединить эти точки,  то получится ломанная линия, называемая опытной линией регрессии. Очевидно, что полученная линия является следствием ошибок замеров, недостаточного их количества, дискретности графика. По мере увеличения числа данных (увеличения объема выборки) ломаная линия асимптотически приближается к какой-то плавной кривой. Поскольку объем данных всегда ограничен, то возникает задача аппроксимации опытной линии регрессии теоретической функцией. Функция, аппроксимирующая опытную ломаную линию, называется теоретической линией регрессии.

  При парной зависимости  опытная линия регрессии может  быть аппроксимирована с помощью  следующих функций:

   у = а + b х – прямая линия;

  у = а х²  + b х  + с – парабола второго порядка;

  у =     – гипербола; 

  у = а + b lg х  – логарифмическая функция.

  Используются  также показательная и степенная  функции, арифметическая и геометрическая прогрессии, алгебраический полином, тригонометрический ряд (ряд Фурье) и другие функции.

  3. МОДЕЛИ ЛИНЕЙНОГО  ПРОГРАММИРОВАНИЯ  В РЕШЕНИЯХ ЗАДАЧ  УПРАВЛЕНИЯ ТРАНСПОРТНЫМИ  ПРОЦЕССАМИ.

   Линейное программирование – это наиболее разработанный раздел математического программирования,  с помощью которого выполняются анализ и решение экстремальных задач с линейными связями и ограничениями.

  Линейное программирование включает в себя целый ряд эвристических (приближенных) методов решения, позволяющих  при заданных условиях из всех возможных  вариантов решений производственных задач выбрать наилучший, оптимальный. К этим методам относятся следующие  – графический, симплексный, метод  потенциалов (модифицированный распределительный  метод – МОДИ), Хичкова, Креко, метод аппроксимации Фогеля и другие.

  Часть этих методов  объединяют общим названием - распределительный, или транспортный, метод.

  Родиной линейного  программирования является Россия. Первые работы по линейному программированию будущим академиком Л.В. Канторовичем были опубликованы в 1939 г.  В 1975 г. за разработку методов линейного программирования им была получена Нобелевская премия по экономике. Поскольку большинство работ академика Л.В. Канторовича посвящено решению транспортных задач, можно считать, что указанная Нобелевская премия отмечает и заслуги российской транспортной науки.

  На автомобильном  транспорте методы линейного программирования используются с 1960-х годов для  решения большого числа важнейших  производственных задач, а именно: сокращение дальности перевозок грузов; составление  оптимальной схемы перевозок; выбор  кратчайших маршрутов движения; задачи перевозки разных, но взаимозаменяемых грузов; сменно-суточное планирование; планирование перевозок мелкопартионных  грузов; распределение автобусов  по маршрутам и другие.

   Особенности модели линейного программирования заключаются  в следующем:

   - целевая функция и ограничения  выражены линейными зависимостями  (равенствами или неравенствами);

  - число зависимостей  всегда меньше числа неизвестных  (условие неопределенности);

  -неотрицательность искомых переменных. Общая форма записи модели линейного программирования в сокращенном виде выглядит следующим образом:

  - найти х_ij ≥ 0 (j = 1, 2…n) при ограничениях следующего типа:

                       .

  Эти ограничения  минимизируют (или максимизируют) целевую  функцию

   min (max).

  Стандартной формой записи модели линейного программирования является система линейных уравнений, записанная в канонической форме, т. е. в форме линейных равенств, в неотрицательных числах:

  а₁₁х₁ + а₁₂х₂ + …+ а_1nх_n = b₁ ;                                                                                                                 

                                       а₂₁х₁ + а₂₂х₂ + … + а_2nх_n = b₂ ;                            (3.1)

  a_mх₁ + а_m2х₂ + …+ а_mnх_n = b_m..

  Если модель записана в форме неравенств в  неотрицательных числах, т. е. имеет  вид

  а₁₁х₁ + а₁₂х₂ + …+ а_1nх_n ≤ b₁ ;                                                                                                                  

                                       а₂₁х₁ + а₂₂х₂ + … + а_2nх_n ≤ b₂  ;                            (3.2)

   a_mх₁ + а_m2х₂ + …+ а_mnх_n ≤ b_m,..

  то эта запись приводится к канонической форме (3.1) путем введения дополнительных переменных х_n+1> 0 (i=1,2…m) в левую часть неравенства (или сокращения числа переменных, если знак неравенства направлен в другую сторону). Дополнительные переменные составляют базис.

  Стандартной формой решения задачи линейного программирования является нахождение решений системы  линейных уравнений в неотрицательных  числах, которые минимизируют целевую  функцию. Целевая функция при  этом имеет вид 

                                       L = с₁ х₁ + с₂ х₂…с_n х_n → min,                              (3.3)

  где с₁, с₂… с_n – коэффициенты целевой функции L при переменных х_j.

  В целевую функцию  дополнительные переменные входят с  нулевыми коэффициентами.

  В случае максимизации целевой функции  L следует знаки при переменных целевой функции изменить на противоположные, и мы вновь придем к задаче минимизации, т.е. одна задача сводится к другой заменой L на –L или max L = min (–L).

  Базисным решением системы линейных уравнений (3.1) называется решение, в котором небазисным переменным даны нулевые значения.

  Допустимым  называется такое базисное решение,  в котором вошедшие в базис  переменные являются неотрицательными.

  Оптимальным называется допустимое решение, максимизирующее (или минимизирующее) целевую функцию (3.3).

   Каждой задаче линейного программирования соответствует  другая, называемая двойственной задачей линейного программирования. Исходная задача по отношению к двойственной называется прямой. Прямая и двойственная задачи образуют пару, называемую в линейном программировании двойственной парой. Прямая и двойственная пара образуют несимметричную пару, когда прямая задача записана в канонической форме, и симметричную пару, когда условия задач записаны неравенствами.

   Правила составления математической модели двойственной задачи базируются на правилах матричного исчисления.

  Понятие двойственности широко используется в анализе задач  линейного программирования. Свойство двойственности детально рассматривается  в каждом конкретном случае.

  Графоаналитический  метод – это один из простейших методов линейного программирования. Он наглядно раскрывает сущность линейного  программирования, его геометрическую интерпретацию. Его недостаток в  том, что он позволяет решать задачи с 2 или 3 неизвестными, т. е. применим для  узкого круга задач. Метод основан  на правилах аналитической геометрии.

  Решение задачи с двумя переменными х₁ и х₂, которые по смыслу задачи не должны быть отрицательными, выполняется в системе декартовых координат. Уравнения х₁=0 и х₂ = 0 являются осями системы координат первого квадранта

  (рис. 3.1).

  3.3. Симплексный  метод.

  Симплексный метод – это распространенный метод решения задач линейного программирования. Свое название метод получил от слова «симплекс», обозначающего простейший выпуклый многоугольник, число вершин которого всегда на единицу больше, чем размерность пространства. Симплексный метод разработан в США математиком Дж. Данцигом в конце 1940-х годов.

  Симплексный метод  включает получение неотрицательного базисного решения системы канонических линейных уравнений типа (3.1), последующую  минимизацию (максимизацию) целевой  функции (3.3) и нахождение таким способом оптимальных значений искомых переменных х₁, х_2… х_n.

  Идея симплексного метода заключается в том, что  в процессе вычисления последовательно  переходят от первого базисного  решения ко второму, третьему и т.д. с помощью так называемых симплексных преобразований. Преобразования производятся в форме симплексных таблиц, что значительно упрощает и ускоряет расчеты.

  Чтобы получить неотрицательные  базисные решения  системы линейных уравнений, надо процесс  исключения неизвестных вести так, чтобы свободные члены уравнений  на всех этапах процесса оставались неотрицательными. При этом следует руководствоваться  следующим правилом: в качестве новой  базисной переменной принимается любая  свободная переменная, при которой  есть хотя бы один положительный коэффициент; выводится из базиса  переменная, которая соответствует наименьшему  отношению свободных членов уравнений  к соответствующим положительным  коэффициентам уравнений при  вводимой в базис переменной. Такие  преобразования называются симплексными преобразователями.

  Это очень важно, поскольку для нахождения частного неотрицательного решения, отвечающего  наибольшему возможному значению какой-то одной свободной переменной при нулевых значениях других свободных переменных, вместо определения области изменения указанной переменной и подстановки ее наибольшего возможного значения в общее решение достаточно принять эту переменную за базисную и подвергнуть систему симплексному преобразованию, перейдя к новому базису, что значительно упрощает расчеты.

   4. МАРШРУТИЗАЦИЯ  ПЕРЕВОЗОК ГРУЗОВ  ПОМАШИННЫМИ ОТПРАВКАМИ

  При помашинных отправках грузов каждый отдельный  автомобиль загружается только в  адрес одного потребителя. Сменно-суточное планирование таких перевозок занимает одно из центральных мест в задачах  маршрутизации и включает составление  маршрутов движения подвижного состава  и порядок его следования между  корреспондирующими точками. Оптимальное  планирование рассматриваемой задачи позволяет получать значительный экономический  эффект.

  Первым шагом  работы по составлению рациональных маршрутов является классификация  грузов, предъявляемых к перевозке, на группы, однородные с точки зрения возможности их перевозки на одном  и том же подвижном составе.

  Маршруты составляются по каждой группе грузов.

  Практика решения  задач по маршрутизации перевозок  грузов учитывает множество ограничений, вызываемых конкретными условиями  работы грузовых точек и автомобильного транспорта. К ним относятся: заданное множество пунктов отправления  и получения грузов; объемы грузооборота у поставщиков и потребителей; характер груза, время доставки, структура  и наличие парка подвижного состава; мощность и размещение автотранспортных предприятий; режимы работы водителей  и так далее.

   Многообразие  ограничений в каждом конкретном случае привело к созданию различных  методов маршрутизации, в том  числе и эвристических, базирующихся на материалах опыта прошлой работы. Имеется большое число методов маршрутизации массовых грузов, когда грузы перевозятся помашинными отправками, используются сложные алгоритмы решения задач.

   В настоящем разделе рассмотрен один широко используемый метод маршрутизации  – метод совмещенных планов. Метод используется на базе линейного программирования. Основной задачей сменно-суточного планирования является составление такого плана работы транспортных средств на данную смену, который позволит выполнить заданные перевозки в установленные сроки минимальным количеством автомобилей. Достигается это при максимальной производительности подвижного состава, которая в общем виде выражается формулой

   ,

  где Р – производительность автомобиля за смену, т·км; Т_н – время в наряде, ч; g –грузоподъемность автомобиля, т; γ – коэффициент использования грузоподъемности; β – коэффициент использования пробега; V_т – техническая скорость, км/ч; l_г – расстояние перевозки груза, км; t_пр –простой автомобиля при погрузке и выгрузке, ч.