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

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

   у = а + 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_пр –простой автомобиля при погрузке и выгрузке, ч.