Главная

Вопрос-ответ

Какие формы лизинга различают в настоящее время В настоящее время различают следующие формы...

Формулировка и методы решения транспортной задачи (2008, 288с.)
22.09.2015 17:27

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

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

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

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

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

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

….

Система ограничений по количеству груза, вывозимого из каждого пункта производства:

..

где — обьем перевозок между …-й и …-й точками транспортной сети; …. — количество поставщиков; — количество потребителей; — ограничения по предложению; — ограничения по спросу.

Причем предполагается, что

….

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

….

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

- в уравнениях коэффициенты при неизвестных принимают только два значения: 0 или 1;

- каждая переменная только дважды встречается с коэффициентом равным 1, а в остальных случаях ее коэффициенты равны 0.

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

 

Таблица 8.1 - Матрица условий транспортной задачи

 

В практике планирования ГАП встречаются особые виды транспортных задач.

Модели с несбалансированным спросом и предложением получили название открытых. В таких задачах спрос и предложение не сбалансированы.

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

Если спрос превышает предложение, то вводится фиктивный ГОП, для которого объем вывоза груза составит

Расстояния для фиктивного ГОП или ГПП принимаются равными нулю.

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

Модель с обязательными корреспонденциями используется, если какие-либо ГПП должны получать груз из конкретных ГОП. В этом случае корректируются ограничения.

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

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

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

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

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

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

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

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

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

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

Если при закреплении очередной загрузки оказалось, что спрос потребителя полностью удовлетворен или ресурс поставщика полностью исчерпан, то в соответствующей строке или столбце разностей проставляется буква К (конец), в остальных свободных ячейках строки или столбца проставляется знак «х» и данная строка или столбец матрицы из дальнейшего рассмотрения исключается.

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

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

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

Затем определяем потенциалы остальных столбцов и строк, исходя из того, что и + v = с, при этом определяем потенциалы только строк и столбцов, содержащих загруженные клетки. Для того чтобы определить потенциалы всех столбцов и строк в матрице, необходимо, чтобы матрица содержала не менее (п + т- 1) загруженных клеток.

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

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

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

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

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

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

 

Рис. 8.4. Возможные виды контуров для определения оптимального плана перевозок

 

После того как построен контур для наиболее потенциальной клетки, всем вершинам контура присваиваются попеременно знаки «+» и «-». Начинать надо с клетки, выбранной для начала построения контура (это незагруженная клетка), ей присваивается знак «-».

Затем из всех клеток, обозначенных знаком «+», выбирают наименьшую загрузку. Величину этой загрузки вычитают из величины загрузки во всех клетках, помеченных знаком «+», и прибавляют к величине загрузки в клетках со знаком «-».

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

Если при перераспределении загрузки из клеток со знаком «+» в клетки со знаком «-» в матрице одновременно освобождаются не одна, а две клетки (это происходит, если две вершины контура имеют одинаковую минимальную загрузку), то необходимо одной из освободившихся клеток присвоить нулевую загрузку.

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

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

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

 

Источник: Грузовые автомобильные перевозки: Учеб. пособие для студ. высш. учеб. заведений / А. Э. Горев. — 5-е изд., испр. — М.: Издательский центр «Академия», 2008. — С. 187-193 (288 с.)




Подобные материалы:
Последние похожие материалы:
Более поздние похожие материалы:

 

Результаты тестов

Результаты тестов
<->(ПП) Тема 02. Спрос на пассажирские перевозки (26 тест.заданий) 53.85 %
<->(ГП) Тема 07. Технико-эксплуат. показатели и себест. груз. пер. (37 тест.заданий) 75.68 %
<->(ПП-2013) Розділ VI. Показники якості пасажирських автомобільних перевезень (5 тест.завдань) 60.00 %
Перейти к тестам

Ваше мнение

Какая форма образования для Вас предпочтительна?

Образование в сфере логистики и транспорта Copyright © 2011-2017. При использовании материалов сайта - гиперссылка обязательна. All Rights Reserved.

Seo анализ сайта