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

а11х1 + а12х2 + …+ а1nхn = b1 ;

                                  а21х1 + а22х2 + … + а2nхn = b2 ;                            (1)

 

                                         ……………………………..

amх1 + аm2х2 + …+ аmnхn = bm..

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

а11х1 + а12х2 + …+ а1nхn ≤ b1 ;

                                 а21х1 + а22х2 + … + а2nхn ≤ b2  ;                            (2)

 

                                         ……………………………..

amх1 + аm2х2 + …+ аmnхn ≤ bm,..

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

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

                             L = с1 х1 + с2 х2…сn хn → min,                              (3)

где с1, с2… сn – коэффициенты целевой функции L при переменных хj.

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

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

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

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

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

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

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

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

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

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

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

1) в двухмерном пространстве  область допустимых решений представляет  собой многоугольник;

2) каждой стороне многоугольника  соответствует значение одной  переменной, равной нулю;

3) каждой вершине многоугольника  допустимых решений соответствуют  значения двух переменных, равных  нулю;

4) каждому значению целевой  функции соответствует прямая;

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

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

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

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

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

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

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

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

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

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

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

Сформулируем основные правила симплексного метода линейного программирования (при решении задачи на минимум):

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

2) составить симплексную  таблицу. Если в индексной строке  все элементы отрицательны, то  базисное решение оптимально. Задача  решена;

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

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

4. Маршрутизация перевозок помашинными отправками – основные этапы решения задач.

 

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

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

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

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

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

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

,

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

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

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

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

Эта задача маршрутизации состоит в следующем.

Разнородный груз сосредоточен в пунктах отправления А1, А2…Аi…Аm в количествах соответственно а1, a2…ai…am единиц. Его необходимо доставить в пункты назначения В1, В2…Вj…Вn в количествах  в1, в2…вj…вn соответственно.

      Объём перевозок  из i-го пункта отправления в j-й  пункт назначения составляет qij единиц  и известен для всех пунктов.

      Расстояние  от i-го пункта отправления до j-го пункта назначения равно lij и известно для всех комбинаций ij.

      В процессе  выполнения перевозок в пунктах  назначения В1, В2…Вj…Вn после разгрузки автомобилей будет образовываться порожняк в количествах   в11,  в21…вj1…вn1 единиц.

      Этот порожняк  необходимо подать под очередную  загрузку в пункты отправления  А1, А2…Аi…Аm в количестве   а11, а21…аi1…аm1.

      Величины  аi, вj, qij, ai1, вj1 могут выражаться либо в тоннах, либо в ездках автомобиля. Для существа задачи это безразлично, тем более что тонны всегда можно перевести в ездки. Однако с методической точки зрения удобнее пользоваться ездкой автомобиля с грузом и без груза.

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

    По смыслу рассматриваемой  задачи всегда имеет место  условие

вj1 = вj= ,   где   j=1, 2…n;

ai1 = ai = ,   где   i=1,2…m.

      Расстояние  от Вj до Аi, равное lji=lji, известно для всех сочетаний i, j.

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

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