Укрупненный алгоритм программы для исследования случайных величин приведен на рисунке 12. 1


НазваниеУкрупненный алгоритм программы для исследования случайных величин приведен на рисунке 12. 1
страница5/9
Дата публикации06.05.2013
Размер1.03 Mb.
ТипЗакон
userdocs.ru > География > Закон
1   2   3   4   5   6   7   8   9
Рисунок 3.15 – Графическая интерпретация метода наискорейшего спуска


Шкальность определяется зависимостью Si = (xн – xв )i bш , где xн, xв – соответственно принятая нижняя и верхняя граница интервала поиска; bш – коэффициент, определяющий шкальность по переменным.

Имеется ряд методов оптимизации на основе случайного поиска. Ниже приведен алгоритм метода случайного поиска с пересчетом. В алгоритме приняты обозначения: r – псевдослучайные числа в интервале от 0 до 1.0; Si – шкальность изменения xi ; Xт = {xтi} – текущее значение X; Xп = {xпi} – текущее приближение к решению X.
Общая схема маршрутизации перевозок мелких партий ресурсов по кратчайшей связывающей сети.
Задача маршрутизации перевозок мелких партий ресурсов состоит в том, чтобы найти такое множество маршрутов, на которых достигались бы минимальные издержки на транспортирование (минимальный общий пробег транспортных средств, минимальное общее время работы транспортных средств, минимальная общая сумма произведений разрешенной максимальной массы на пробег транспортных средств и другие). Наиболее часто в качестве критерия оптимальности решения задачи принимается минимум общего пробега транспортных средств

,

где loj – длина оборота транспортного средства на j-м маршруте;

n – общее число маршрутов для освоения заданных объемов перевозок ресурсов.

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

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

Этап 1. Находится кратчайшая связывающая сеть

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

Этап 2. Набор пунктов в маршруты

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

Результаты набора пунктов в маршруты сводятся в таблице 3.15.
Таблица 3.15 – Набор корреспонденций (перевозок) в маршруты

Маршрут ...

Маршрут ...

Пункты

Количество ресурса, ед.(т)

Пункты

Количество ресурса, ед. (т)




Ввоз

вывоз




ввоз

вывоз

Всего







Всего








Этап 3. Определение очередности объезда пунктов маршрута

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

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

Пункт

А

1

...

i

...

m

А

0

lAB1




lABi




lABm

1

lB1A

0




l B1Bi




l B1Bm

...







0










J

lBjA

lBjB1




l BjBi




lBjBm

...













0




M

lBmA

lBmB1




lBmBi




0

Сумма



















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

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

lkp = lki + lip - lkp ,

где l – расстояние (стоимость, время и т.п.);

k – первый соседний пункт;

p – второй соседний пункт;

i – индекс включаемого пункта.

Из всех получаемых величин lkp выбирают минимальную и между пунктами k и p включают в маршрут пункт i.

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

Проверка возможности использования транспортного средства для одновременного развоза и сбора ресурсов на маршруте производится в той последовательности объезда пунктов, которая получена на 3-м этапе расчетов.

Для проверки составляем таблицу нижеприведенного вида (таблица 3.17).
Таблица 3.17 – Расчет загрузки транспортного средства при перевозке на маршруте

Пункт

Количество ресурса, ед.




Разгружено

Загружено

Всего


Количество ресурса на транспортном средстве при выходе из пункта i определяется по формуле

Qi,i+1 = Qi-1,i - Qpi + Qci,

где Qi,i+1 – объем перевозимого ресурса на участке маршрута (при выходе из пункта i);

Qi-1,i – объем перевозимого ресурса на предшествующем участке i-1, i маршрута;

Qpi – объем выгрузки ресурса в пункте i;

Qci – объем погрузки ресурса в пункте i.

Одним из возможных способов избежать перегруза транспортного средства является изменение направления объезда пунктов маршрута.

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

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

Схема маршрута в этом случае выглядит следующим образом:

базовый пункт – загрузка;

пункты повторного заезда – разгрузка;

прочие пункты – разгрузка-загрузка;

пункты повторного заезда – загрузка;

базовый пункт – разгрузка.

Общая схема маршрутизации перевозок мелких партий ресурсов по методу Кларка-Райта.

Метод Кларка-Райта предусматривает совмещенное решение задачи маршрутизации перевозок по сборочным или развозочным, осуществляемых в общем случае парком транспортных средств различной вместимости.

Основой решения являются следующие исходные данные:

число K видов транспортных средств различной k-й вместимости и значения вместимостей qk, ;

число промежуточных пунктов (m), в которые доставляется или из которых собирается ресурс;

количество ресурса (Qpi, ), подлежащего завозу или вывозу по промежуточным пунктам;

стоимость перевозок ресурса (расстояния, время перевозок) между пунктами транспортной сети (cij, ; ), включающими исходный (индекс 0) и промежуточные пункты;

различного рода ограничения – по числу промежуточных пунктов на маршруте (nп), использованию вместимости транспортных средств, длине маршрута, времени оборота на маршруте и т.п.

Алгоритм одной из реализаций метода следующий:

1) строится система маятниковых маршрутов, на каждом из которых предполагается обслуживать один пункт. Для каждого такого i-го маршрута назначается объем перевозок Qi = Qpi, число пунктов заезда ni=1 и транспортное средство возможно минимальной вместимости, но не менее Qi, т.е. ;

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

Выигрыши рассчитываются по формуле

сij = сAi + сAjij,

где сij – величина сокращения пробега транспортного средства при объединении маршрутов A-Bi-A и A-Bj-A ;

сAi , сAj – стоимость перемещения от исходного пункта A соответственно до пунктов Bi и Bj ;

сij – расстояние между пунктами Bi и Bj, ед. Вариантность попарного объединения пунктов описывается треугольной матрицей и соответственно общее число вариантов определяется выражением (m (m-1))/2, где m – число промежуточных пунктов;

3) последовательно производится объединение текущих маршрутов следующим образом:

3.1) находится максимальный выигрыш от возможного попарного объединения исходных маршрутов , где r и s – соответственно пункты, по которым может быть рассмотрено объединение маршрутов. Если максимальный выигрыш нулевой или отрицательный – то решение закончено;

3.2) оценивается возможность объединения маршрутов с учетом наличия транспортных средств необходимой вместимости и выполнения других заданных ограничений. Для этого необходимо рассчитать общий объем перевозимого ресурса как сумму ресурсов объединяемых маршрутов Qт=Qr+Qs, число пунктов заезда на объединенном маршруте nт = nr+ns и др. Если такое объединение невозможно (или nт  nп и т.п.), то переход на пункт 3.5. Иначе на 3.3.

3.3) формируется новый объединенный маршрут, состоящий из двух объединяемых по пунктам r и s. Полученный маршрут имеет вид A-Bp-...-Br-Bs-...-Bu-A;

3.4) производится корректировка текущих значений параметров в связи с объединением маршрутов:

  • маршруты r и s, вошедшие в сформированный маршрут, аннулируются и соответственно присваиваются Qr(…)= 0 и Qs(…)= 0;

  • формируется индекс маршрута, определяемый номерами крайних пунктов (пункты p и u);

  • назначается на маршруте с индексом p(u) объем перевозок Qp(u)= Qт и число промежуточных пунктов заезда np(u)=nт ;

  • назначается транспортное средство, удовлетворяющее условию ;

  • если nт>2, то на отрицательный, например, -1 заменяется выигрыш между конечными пунктами маршрута p и u (cpu=-1);

  • на отрицательные заменяются выигрыши всех других пунктов с пунктом r, если nr>1 (сri= -1, ) и с пунктом s, если ns>1 (сsi= -1, );

3.5) реальное значение выигрыша сrs заменяется отрицательным (сrs=-1) независимо от того состоялось формирование нового маршрута или нет;

3.6) переход на 3.1.

При реализации алгоритма возможно многократное присвоение отрицательного значения выигрышу для одной и той же пары пунктов, что не влияет на конечный результат.
1   2   3   4   5   6   7   8   9

Похожие:

Укрупненный алгоритм программы для исследования случайных величин приведен на рисунке 12. 1 iconКурс «Статистические методы управления качеством» специальность 200503...
Особенности эмпирических данных. Случайные величины. Распределения случайных величин. Статистические гипотезы
Укрупненный алгоритм программы для исследования случайных величин приведен на рисунке 12. 1 iconКоллоквиум 2 тв и мс
Числовые характеристики случайных величин: математическое ожидание (понятие, свойства)
Укрупненный алгоритм программы для исследования случайных величин приведен на рисунке 12. 1 iconЗакон больших чисел
Корреляционная матрица случайного вектора. Коэффициент корреляции двух случайных величин
Укрупненный алгоритм программы для исследования случайных величин приведен на рисунке 12. 1 iconАвтокорреляция случайного возмущения. Причины. Последствия
Алгоритм теста Голдфелда-Квандта на наличие (отсутствие) гетероскедастичности случайных возмущений
Укрупненный алгоритм программы для исследования случайных величин приведен на рисунке 12. 1 iconЗакон распределения Пуассона и его характеристики
Локальная предельная теорема Муавра-Лапласа. Теорема Пуассона Понятие случайной величины. Виды случайных величин
Укрупненный алгоритм программы для исследования случайных величин приведен на рисунке 12. 1 iconЗачет Казаринова Ирина Николаевна Старовойтова Ольга Рафаэльевна...
Методология, методика, программа, метод, алгоритм исследования, парадигма, научная традиция
Укрупненный алгоритм программы для исследования случайных величин приведен на рисунке 12. 1 icon2: Элементы векторной алгебры
Различают понятия величин, которые характеризуются од -ним числом скалярные величины (например: масса, объём, длина, площадь и т...
Укрупненный алгоритм программы для исследования случайных величин приведен на рисунке 12. 1 iconНа рисунке 1 приведен график зависимости скорости движения тела от...
Чему равно отношение силы гравитационного взаимодействия, действующей со стороны Луны на Землю, к силе гравитационного взаимодействия,...
Укрупненный алгоритм программы для исследования случайных величин приведен на рисунке 12. 1 iconЧто такое метрология?
Размерность качественная характеристика физических величин. Правила определения размерности производных величин
Укрупненный алгоритм программы для исследования случайных величин приведен на рисунке 12. 1 iconПрограмма учебного курса «Физическая география России»
В конце программы приведен перечень экзаменационных вопросов за все три семестра: два на 4 курсе и 1 на пятом курсе см!!!
Вы можете разместить ссылку на наш сайт:
Школьные материалы


При копировании материала укажите ссылку © 2020
контакты
userdocs.ru
Главная страница