|
Архитектура Аудит Военная наука Иностранные языки Медицина Металлургия Метрология Образование Политология Производство Психология Стандартизация Технологии |
|
|
Архитектура Аудит Военная наука Иностранные языки Медицина Металлургия Метрология Образование Политология Производство Психология Стандартизация Технологии |
Вопрос №1 (Теория транспортных процессов, Пассажирские автомобильные перевозки)Стр 1 из 6Следующая ⇒
Вопрос №1 (Теория транспортных процессов, Пассажирские автомобильные перевозки) Задача коммивояжера при грузовых автомобильных перевозках. Постановка задачи. Алгоритм решения задачи методом Ветвей и границ. Задача коммивояжера Одна из самых известных и важных задач транспортной логистики (и класса задач оптимизации в целом) – задача коммивояжера (англ. «Travelling salesman problem», TSP). Также встречается название «задача о бродячем торговце». Суть задачи сводится к поиску оптимального, то есть кратчайшего пути проходящего через некие пункты по одному разу. Например, задача коммивояжера может применяться для нахождения самого выгодного маршрута, позволяющего коммивояжеру объехать определенные города со своим товаром по одному разу и вернуться в исходную точку. Мерой выгодности маршрута будет минимальное время, проведенное в пути, минимальные расходы на дорогу или, в простейшем случае, минимальная длина пути. Кто и когда впервые начал исследовать задачу коммивояжера неизвестно, но одним из первых предложил решение подобной проблемы выдающийся математик XIX в. – Уильям Гамильтон. Здесь мы рассмотрим замкнутый вариант задачи (т.е. такой, когда в итоге мы возвращаемся в исходную точку) и ее решение методом ветвей и границ.
Метод «ветвей и границ» Среди методов решения задач маршрутизации мелкопартионных перевозок, дающих точное решение, наибольшее распространение получил метод «ветвей и границ». Метод оказался настолько работоспособным, что с успехом был использован для решения самых разнообразных задач дискретной оптимизации и в том числе для решения задачи развозки. Общая идея метода довольно проста. Изложим ее для решения задачи на минимум целевой функции. Вначале для всего множества допустимых решений задачи определяется нижняя граница значения функционала. Эта граница есть число, меньше которого значение целевой функции заведомо быть не может. Затем все множество допустимых решений (конечное! ) разбивается на несколько непустых подмножеств, для каждого из которых снова определяется нижняя граница функционала. Из всех подмножеств выбирается подмножество с наименьшим значением нижней границы и опять разбивается на непустые подмножества, для которых снова определяются нижние границы значения функционала. Затем снова определяется еще неразбитое подмножество с наименьшей нижней границей и опять тем же приемом делится на несколько непустых подмножеств и т. д. Поскольку множество допустимых решений задачи конечно, такой процесс последовательного разбиения приводит к подмножеству из одного единственного решения, нижняя граница для которого просто совпадает со значением целевой функции для этого решения. Если это значение не выше нижних границ всех неразбитых подмножеств, то имеем одно из лучших решении, а если значение целевой функции для найденного решения строго меньше нижних границ неразбитых подмножеств, то имеем единственное оптимальное решение.
Метод северо-западного угла Допустимое (но не всегда оптимальное с точки зрения стоимости доставки) начальное решение транспортной задачи можно построить, последовательно перебирая строки таблицы (то есть поставщиков) сверху вниз. В пределах каждой строки, нужно перебрать слева направо не охваченных или не полностью охваченных поставками потребителей, записывая в соответствующие ячейки объем поставляемого груза от поставщика в данной строке, и так до исчерпания возможностей поставщика. Таким образом, весь груз от поставщиков будет распределен по потребителям. Этот метод был предложен Данцигом в 1951 г.[8] и назван Чарнесом и Купером[18] «правилом северо-западного угла».[2]: 189
В таблице здесь и далее зеленым цветом отмечены ячейки с ненулевыми объемами перевозки груза (базисные ячейки).[19] Подробности см. в статье Метод северо-западного угла. Метод минимальных тарифов Другой метод получения начального решения — записывать отгрузки в первую очередь в те ячейки, где тариф минимален. Этот метод позволяет получить более приближенное к оптимальному решение, которое, однако, может потребовать дальнейшей оптимизации.[3]: 87 Метод минимальных тарифов с его модификациями (минимальный тариф по строке или минимальный тариф по столбцу) был описан Данцигом в работе 1951 г.[8]Подробнее см. в статье Метод минимальных тарифов. Метод Фогеля Для поиска начального решения транспортной задачи можно применить также метод Фогеля, который обычно дает еще более приближенное к оптимальному решение. Подробнее см. в статье Метод Фогеля. Решение транспортной задачи методом потенциалов Метод потенциалов позволяет за несколько шагов (итераций) найти полностью оптимальное решение транспортной задачи. Перед решением задачи этим методом нужно найти допустимое начальное решение одним из методов, описанных в разделе выше. Вычисление потенциалов Каждому поставщику Ai соответствует потенциал Ui, а каждому потребителю Bj соответствует потенциал Vj. Данциг называет потенциалы Ui и Vjсимплекс-множителями или неявными ценами.[1]: 300, 305 Чтобы определить эти потенциалы, полагают, что U1=0, а остальные потенциалы вычисляют из соотношения Ui + Vj = Cij для всех занятых (базисных) ячеек таблицы (отмечены зеленым).[3]: 89
U1+V1=2. Поскольку U1=0, 0+V1=2, следовательно, V1=2 руб./кг U1+V2=3. Поскольку U1=0, 0+V2=3, следовательно, V2=3 руб./кг U2+V2=2. Поскольку V2=3, U2+3=2, следовательно, U2=–1 руб./кг U2+V3=5. Поскольку U2=–1, –1+V3=5, следовательно, V3=6 руб./кг U3+V3=2. Поскольку V3=6, U3+6=2, следовательно, U3=–4 руб./кг U3+V4=6. Поскольку U3=–4, –4+V4=6, следовательно, V4=10 руб./кг При компьютерной реализации удобно использовать рекурсию: взаимный вызов двух функций, которые отрабатывают алгоритм, соответственно, по строкам и по столбцам. Если на предыдущем шаге 4 (в разделе «Проверка плана на вырожденность») Построение цикла
Цикл перераспределения поставок представляет собой замкнутую ломаную линию, которая соединяет начальную вершину (отмечена красным цветом) и занятые (отмеченные в нашем примере зеленым цветом) ячейки транспортной таблицы по определенным правилам.[3]: 89 1. Все вершины, кроме начальной, находятся в занятых ячейках таблицы (ячейки с ненулевыми перевозками или «введенные в базис» на шаге 4 (в разделе «Проверка плана на вырожденность» ячейки с нулевой перевозкой — здесь они отмечены в примерах зеленым цветом), при этом охвачены циклом могут быть не все, а лишь некоторые занятые ячейки. 2. В каждой вершине цикла встречаются ровно два звена ломаной линии, причем одна из них находится по строке, а другая — по столбцу.Иначе говоря, они пересекаются под прямым углом. 3. Линия может пересекать занятые ячейки, не включая их в цикл (включение их в цикл не допускается). Другими словами, никакие три последовательные вершины не могут находиться в одной и той же строке или одном и том же столбце. 4. Линия может пересекать саму себя, при этом точка пересечения не включается в цикл (исходя из п.2). 5.
Вершины цикла в этом примере помечены звездочкой (*). Горизонтальные и вертикальные линии, соединяющие вершины, в этом примере не показаны. По вершинам цикла нужно перераспределить объемы, чтобы получить следующее приближение к оптимальному решению задачи, как это показано далее. При компьютерной реализации построения цикла удобно использовать рекурсию, то есть взаимный вызов двух функций, которые строят линии цикла по строкам и по столбцам, соответственно.[24] Зацикливание решения Поскольку алгоритм является циклическим (итерационным), переходим к пункту 1. Примечание: есть опасность, что алгоритм впадет в бесконечный цикл из-за вырожденности или каких-либо ошибок реализации, поэтому полезно предусмотреть проверку на максимальное число шагов или максимальное время, которое будет исполняться программа (например, при поиске решения в Microsoft Excel эти параметры вынесены в пользовательские настройки). Впрочем, по мнению Данцига, те меры, которые можно предпринять для исключения вырожденности (см. Вырожденность в транспортной задаче) приводят к успеху в 100 % случаев. Для подстраховки можно применить метод Фогеля, который не склонен «впадать» в бесконечные циклы, и выдает более или менее приближенное к оптимальному решение за ограниченное число шагов. Достижение результата Сюда мы переходим из пункта 6, если решение было признано оптимальным.
Вопрос №2: Основы Логистики + Общий курс транспорта + ОАПиБД. 11.Принципы определения оптимального количества складов в зоне обслуживания. ABC-анализ Методика ABC-анализа ABC-анализ позволяет разбить большой список, например ассортимент товаров, на три группы, имеющие существенно разное влияние на общий результат (объем продаж). Иными словами, ABC-анализ позволяет: · Выделить позиции, которые вносят наибольший вклад в суммарный результат. · Анализировать три группы вместо большого списка. · Работать сходным образом с позициями одной группы. Группы обозначаются латинскими буквами ABC: · А — самые важные · В — средней важности · С — наименее важные
Можно анализировать (ранжировать) любые объекты, если у них есть числовая характеристика. Например: · Ассортимент по объему продаж · Клиентов по объему заказов · Поставщиков по объему поставок · Дебиторов по сумме задолженности · Запасы по занимаемой площади склада Очень важно, что в каждом конкретном случае не надо ломать голову над тем, в какую группу отнести товар (клиента, поставщика и т.д.). Есть простая методика, выполняющая это разделение. Методика основана на принципе Парето (принцип 20/80), открытом итальянским экономистом Парето в 1897 году. В наиболее общем виде он формулируется так: «20% усилий дают 80% результата». В нашем случае: 20% ассортимента дают 80% выручки. Границы ABC-групп
Группы должны быть примерно следующими (на примере анализа ассортимента): · Группа A дает 80% выручки, содержит 20% наименований · Группа B дает 15% выручки, содержит 30% наименований · Группа C дает 5% выручки, содержит 50% наименований На всякий случай уточню: разбиение на группы выполняется по сумме выручки, а доля от числа наименований — какая получится. Понятно, что соотношения (80%-15%-5%) по объему и (20%-30%-50%) по количеству наименований не являются точным законом природы, cуществует несколько методов определения границ ABC-групп. Но при значительных отклонениях от указанных значений следует насторожиться. ТЭА Вопрос 11 11.Произвести анализ скоростных и нагрузочных режимов работы автомобильных двигателей. ТЭА Вопрос 12 12.Произвести анализ тепловых режимов работы ДВС. Вопрос №1 (Теория транспортных процессов, Пассажирские автомобильные перевозки) |
Последнее изменение этой страницы: 2017-05-05; Просмотров: 414; Нарушение авторского права страницы
Поскольку у нас нет ограничений на черно-белую полиграфию, для большей ясности ячейки транспортной таблицы в этой статье отмечены разными цветами.