Математическая постановка задачи дано




НазваниеМатематическая постановка задачи дано
Дата конвертации24.02.2013
Размер445 b.
ТипПрезентации


Планирование грузовых автомобильных перевозок. Алгоритмы ускоренного планирования.


Три схемы перевозочного процесса



Математическая постановка задачи

  • ДАНО:

  • n - количество пунктов доставок

  • cij — расстояние от пункта i до пункта j



, где Ui и Uj - произвольные вещественные значения



Целевая функция

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



Определение времени доставки груза

  • где - время погрузки у j-го грузоотправителя,

  • - время движения с грузом от i-го до j-го пункта

  • - время разгрузки у i-го грузополучателя

  • k - количество пунктов разгрузки

  • - время на холостой пробег до j-го развозочного маршрута

  • - перерывы поставщика

  • - перерывы потребителя



Пример

  • ТРЕБУЕТСЯ:

  • из пунктов a и b доставить груз в пункты b1-b1и в требуемом кол-ве согласно таблице 1



РЕШЕНИЕ:

  • РЕШЕНИЕ:

  • 1) т. к. имеетя 2 пункта поставки и 15 пунктов приёма груза, то используем схему «многие ко многим»

  • 2) решим транспортную задачу на основе данных таблицы 2, где дано расстояние между пунктами:



3) критерием оптимальности в задаче является минимум транспортной работы в ткм Поэтому из таблицы 2 для каждого bi мы выбираем такое a1 или а2, чтобы расстояние между ними было минимальным и проставляем величину груза в соответствующую ячейку. Получим таблицу 3, где отражены объёмы перевозок:

  • 3) критерием оптимальности в задаче является минимум транспортной работы в ткм Поэтому из таблицы 2 для каждого bi мы выбираем такое a1 или а2, чтобы расстояние между ними было минимальным и проставляем величину груза в соответствующую ячейку. Получим таблицу 3, где отражены объёмы перевозок:



4) решим задачу маршрутизации (коммивояжера) и определим длины маршрутов и порядок объезда пунктов на нём, основываясь на расстояниях между рассматриваемыми на маршруте пунктами

  • 4) решим задачу маршрутизации (коммивояжера) и определим длины маршрутов и порядок объезда пунктов на нём, основываясь на расстояниях между рассматриваемыми на маршруте пунктами



Первый маршрут: a1-b15-b11-b3-b6-b9-b14-b5-b7-b2-a1 (28 км)

  • Первый маршрут: a1-b15-b11-b3-b6-b9-b14-b5-b7-b2-a1 (28 км)

  • Второй маршрут: a2-b8-b12-b1-b13-b4-a2 (26 км)



5) зададим временные ограничения, среднее значение, среднее квадратическое отклонение (СКО) и закон распределения случайных величин.

  • 5) зададим временные ограничения, среднее значение, среднее квадратическое отклонение (СКО) и закон распределения случайных величин.



6) Рассчитаем время движения:

  • 6) Рассчитаем время движения:



Т.к. время погрузки в пункте a1 подчиняется нормальному закону, то:

  • Т.к. время погрузки в пункте a1 подчиняется нормальному закону, то:



Рассчитаем скорость V1 на первом участке по формуле V1= среднее знач. + ơ x ѯ', где ѯ'=-0,127

  • Рассчитаем скорость V1 на первом участке по формуле V1= среднее знач. + ơ x ѯ', где ѯ'=-0,127



Следовательно в пункте b15 разгрузка закончится в 11.25 + 0.03=11.28

  • Следовательно в пункте b15 разгрузка закончится в 11.25 + 0.03=11.28

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

  • Реализуя описанный алгоритм 10 раз для первого маршрута, получим следующую таблицу:







Недостатки алгоритма

  • Трудоёмкость

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

  • Возможные изменения в соглашении с поставщиками (времени, места разгрузки и т.д.)



Ускоренные методы

  • 1) для решения транспортной задачи используется метод аппроксимации Фогеля

  • 2) для составления маршрута — метод воображаемого луча (метод Свира)

  • 3) для решения «задачи коммивояжера» - ускоренный метод ветвей и границ

  • 4) проводится оценка интервалов времени прибытия ср-ва и времени окончания разгрузки для каждого потребителя по формулам: для верхней границы -

  • для нижней границы -



Пример

  • ТРЕБУЕТСЯ:

  • из пунктов a1 a2 перевезти груз восьми получателям b1-b8 в объёме Q. Данные:



  • РЕШЕНИЕ:

  • предположим, что по существующему распределению за пунктом a1 закреплены b2,b3,b4,b7, за a2b1,b5,b6,b8

  • Общая длина маятниковых маршрутов равна 180 км, а пробег с грузом — 90 км

  • Транспортная работа:

  • Поэтому:



Применим метод Фогеля.

  • Применим метод Фогеля.



По завершении метода получим допустимую программу распределения:

  • По завершении метода получим допустимую программу распределения:

  • в числителе — объём перевозок в соответствующий пункт (Q), в знаменателе -расстояние перевозки (l).

  • Общее расстояние по маятниковым маршрутам:

  • Т.к. то P=0.25x10 +0.3x12 +...+1.1x8=61.2 ткм



Набор пунктов в маршрут (метод Свира)

  • Положим грузоподъёмность средства 2.2 т В квадратных скобках — потребность получателя в тоннах.



Ускоренный метод ветвей и границ

  • Определим кратчайшие расстояния между пунктами в одном маршруте:

  • применим метод для a1,b1,b2 и b4





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

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

  • Нижняя граница второго подмножества равна сумме значений нижней границы разделяемого мн-ва (28) и величины оценки a1b1, т. е. 28+16=44



В рез-те преобразований получим:

  • В рез-те преобразований получим:

  • выбирая, например, пару b1b4, увеличим протяжённость мн-ва на 1 (44+1=45). Вычёркиваем соответствующие столбец и строку. Появилась константа 1, значит увеличиваем нижнюю границу на 1.



Получившуюся матрицу 2*2 легко решается. Недостающие пары — b4b2 b2a1

  • Получившуюся матрицу 2*2 легко решается. Недостающие пары — b4b2 b2a1

  • полученный маршрут: a1b1-b1b4-b4b2-b2a1, протяжённость 45 км



Определение временных интервалов

  • Для определения временных интервалов прибытия транспорта в пункты воспользуемся формулами

  • Скорость движения, время простоя при погрузке/разгрузке представлены в таблице:



Среднее значение времени движения определяется как отношение расстояния перевозки (12 км — для a1b2) к среднему значению скорости:

  • Среднее значение времени движения определяется как отношение расстояния перевозки (12 км — для a1b2) к среднему значению скорости:

  • Коэффициент вариации для тех. Скорости 0.08 из таблицы, поэтому СКО времени движения = 0.39 *0.08=0.03 ч

  • tβ определяется в зависимости от установленной вероятности нахождения затрат времени в расчётных пределах (табличные данные)



Предположим tβ=1.5, тогда верхняя граница времени доставки:

  • Предположим tβ=1.5, тогда верхняя граница времени доставки:

  • Нижняя граница:



Итог

  • 1) высокая степень надёжности рез-та ускоренных методов, простота и практичность



  • Спасибо за внимание



Похожие:

Математическая постановка задачи дано icon1. Постановка задачи Постановка задачи
Вывод формулы для дифференциального парникового эффекта и оценка параметра температурной климатической чувствительности
Математическая постановка задачи дано iconЗадача Постановка задачи. Основные понятия
Общая постановка транспортной задачи состоит в определении оптимального плана перевозок некоторого однородного груза из
Математическая постановка задачи дано iconПостановка задачи Постановка задачи
Даны две матрицы а и b размера n на n каждая. Реализовать блочный алгоритм умножения матриц, сгенерировать граф, вершинами будут...
Математическая постановка задачи дано iconТема 5 Порядок выполнения постановок задач маркетинга Компоненты постановки задачи
Постановка каждой отдельной задачи документально оформляется в виде соответствующего определенного раздела технорабочего проекта
Математическая постановка задачи дано iconДано: Дано
В движущемся вагоне поезда на столе лежит книга. В покое или движении находится книга относительно
Математическая постановка задачи дано iconТипология логических блоков постановка задачи Конечный потребитель эор
Создания информационной среды способствующей проявлению познавательной активности
Математическая постановка задачи дано iconВведение Постановка задачи
Алгоритм исправления ошибок при анализе в парсерах типа перенос-свертка, основанный на предположении об избыточности языка
Математическая постановка задачи дано iconПостановка проблемы компьютерный класс
Баричев Сергей Геннадьевич, к т н преподаватель информатики сош №593 (г. Москва) постановка проблемы
Математическая постановка задачи дано icon«Школа-2100…» Личностно-ориентированное
...
Математическая постановка задачи дано iconЗадача k коммивояжёров
В данной работе сформулирована упрощенная постановка задачи без учета максимальной загрузки одного коммивояжёра, задержки при посещении...
Разместите кнопку на своём сайте:
hnu.docdat.com


База данных защищена авторским правом ©hnu.docdat.com 2012
обратиться к администрации
hnu.docdat.com
Главная страница