ВЫПОЛНЕНИЕ КОНТРОЛЬНОЙ РАБОТЫ
В контрольной работе студент решает 6 задач по вариантам задания.
Номер варианта определяется по последней цифре номера зачетной книжки.
Порядок решения задач в контрольной работе описан в методических указаниях.
Контрольная работа должна быть оформлена: страницы пронумерованы,
оставлены поля, в конце контрольной работы должен быть список использованной
литературы.
ЗАДАЧА 1. Методика расчета развозочных маршрутов.
Потребность в мелкопартийных поставках пролдукции потребителям с
баз и складов систематически возрастает. Поэтому организация маршрутов на
отгрузку потребителям мелких партий груза имеет большое значение.
На конкретных примерах рассмотрим разработку кольцевых
развозочных маршрутов со снабженческо-сбытовых баз и складов потребителям.
Введем обозначения:
Xi - пункт потребления ( i = 1,2…n);
Xo - начальный пункт (склад);
qi - потребность пунктов потребления в единицах объема груза ( i = 1,...n);
Qt - грузоподъемность транспортных средств ( t=1,….d);
d - количество транспортных средств;
Cij- стоимость перевозки (расстояние);
Mj- поставщики (j = 1,2…m);
Имеются пункты потребления Xi (i = 1,2…n). Груз необходимо развес-
ти из начального пункта Xo (склад) во все остальные Xi(потребители). Потреб-
ность пунктов потребления в единицах объема груза составляет: q1, q2, q3…qn.
В начальном пункте имеются транспортные средства грузоподъёмно- стью Q1, Q2…Qd.
При этом Qd > qn, в пункте Xo количество груза Xo >= Xi (i = 1,…n),
каждый пункт потребления снабжается одним типом подвижного состава.
Для каждой пары пунктов (Xi, Xj) определяют стоимость перевозки
(расстояние) Cij > 0, причем матрица стоимостей в общем случае может быть
ассиметричная, т.е. Cij = Cij.
Требуется найти m замкнутых путей L1,L2…Lm из единственной об-
щей точки Xo, так чтобы выполнялось условие:
m
Lk min
k=1
Методика составления рациональных маршрутов при расчётах
вручную. Схема размещения пунктов и расстояния между ними:
2,2 Б 7,0
В А
4,4 3,6 4,2 5,0 3,2
Г 5,6
З 4,2 Е 3,8 2,0
5,0 Ж
2,0 3,4 Д
2,8
К 5,8
2,6 И
Табл. 1
Потребители продукции Б В Г Д Е Ж З И К
Объем продукции, кг 375 500 500 300 425 525 575 675 125
M = 4000 кг
Q = 2,5 т
Груз находится в пункте А - 4000 кг. Используется автомобиль грузо-
подъёмностью 2,5 т.; груз - II класса (y = 0,8). Необходимо организовать пере-
возку между пунктами с минимальным пробегом подвижного состава.
Решение состоит из нескольких этапов:
Этап 1. Строим кратчайшую сеть, связывающую все пункты без замкнутых
контуров.
Кратчайшая связывающая сеть ("минимальное дерево"):
375 кг Б А 4000 кг
2,2 км 3,2 км
500 кг В Г 500 кг
3,6 км 2,0 км
425 кг Е Д 300 кг
2,4 км 2,8 км 5,0 км 525 кг
575 кг З 2,0 км К 2,6 км И 675 кг
125 кг
Затем по каждой ветви сети, начиная с пункта, наиболее удалённого от
начального А (считается по кратчайшей связывающей сети), группируем
пункты на маршруте с учётом количества ввозимого груза и грузоподъёмности
единицы подвижного состава. Причём ближайшие с другой ветви пункты
группируем вместе с пунктами данной ветви.
Исходя из заданной грузоподъёмности подвижного состава Q = 2,5
y = 0,8 все пункты можно сгруппировать так:
Таблица 2
Маршрут 1 Маршрут 2
пункт объём завоза,кг. пункт объём завоза,кг.
Б 375 Ж 525
В 500 Д 300
Е 425 И 675
З 575 Г 500
К 125
Итого: 2000 Итого: 2000
Сгруппировав пункты по маршрутам, переходим ко второму этапу под- счётов.
Этап 2. Определяем рациональный порядок объезда пунктов каждого мар-
шрута. Для этого строим таблицу - матрицу, в которой по диагонали размеща-
ем пункты, включаемые в маршрут, и начальный пункт А, а в соответствую-
щих клетках - кратчайшие расстояния между ними. Для примера матрица яв-
ляется симметричной Cij = Cji, хотя приведенный ниже способ применим для
размещения несимметричных матриц.
Таблица 3
(А) 7,0 9,2 9,0 11,4 10,6
7,0 (Б) 2,2 4,2 6,6 7,6
9,2 2,2 (В) 3,6 4,4 6,4
9,0 4,2 3,6 (Е) 2,4 3,4
11,4 6,6 4,4 2,4 (З) 2,0
10,6 7,6 6,4 3,4 2,0 (К)
47,2 27,6 25,8 22,6 26,8 30,0
Начальный маршрут строим для трёх пунктов матрицы АКБА, имею-
щих наибольшее значение величин, показанных в строке (47,2; 30,0; 27,6),
т.е А; К; Б. Для включения последующих пунктов выбираем из оставшихся
пункт, имеющий наибольшую сумму, например З (сумма 26,8), и решаем, ме-
жду какими пунктами его следует включать, т.е. между А и к, К и Б или Б и А.
Поэтому для каждой пары пунктов необходимо найти величину при-
ращения маршрута по формуле:
Lkp = Lki + Lip - Lkp,
C - расстояние, км.; i - индекс включаемого пункта; k - индекс первого
пункта из пары; р - индекс второго пункта из пары.
При включении пункта В между первой парой пунктов А и К, определя-
ем размер приращения Lak при условии, что i = З, k = А, p = К. Тогда
Lak = Lаз + Lзк - Lак .
Подставляя значения из табл. 3, получаем, что
Lак = 11,4 + 2,0 - 10,6 = 2,8.
Таким же образом определяем размер приращения КБ, если З включим
между пунктами К и Б:
Lкб = Lкз + Lзб - Lкб = 2,0 + 6,6 - 7,6 = 1,0 км.,
Если 3 включить между пунктами Б и А, то
Lба = Lбз + Lза - Lба = 6,6 + 11,4 - 7,0 = 11,0 км.
Из полученных значений выбираем минимальное, т.е. КБ = 1,0 км. Тогда
А - К - Б - А А -К - З - Б - А.. Используя этот метод и формулу приращения,
определяем, между какими пунктами расположить пункты В и Е. Начнём с В, т.к.
размер суммы (см. табл.) этого пункта больше (25,8 > 22,6):
Lак = Lав + Lвк - Lак = 9,2 + 6,4 - 10,6 = 5,0 км,
Lкз = Lкв + Lвз - Lкз = 6,4 + 4,4 - 2,0 = 8,8 км,
Lзб = Lзв + Lвб - Lзб = 4,4 + 2,2 - 6,6 = 0 км.
В случае, когда .= 0, для симетричной матрицы расчёты можно не
продолжать, т.к. значение меньше чем 0 получено быть не может. Поэтому
пункт В должен быть между пунктами З и Б. Тогда маршрут получит вид:
А - К - З - В - Б - А .
В результате проведённого расчёта пункт Е между пунктами
З и В, т.к. для этих пунктов мы получим минимальное приращение 1,6 км:
Lак = Lае + Lек - Lак = 9,0 + 3,4 - 10,6 = 1,8 км;
Lкз = Lке + Lез - Lкз = 3,4 + 2,4 - 2,0 = 3,9 км; 1150кг
Lзв = Lзе + Lев - Lзв = 2,4 + 3,6 - 4,4 = 1,6 км;
Lвб = Lве + Lеб - Lвб = 3,6 + 4,2 - 2,2 = 5,4 км;
Lба = Lбе + Lеа - Lба = 4,2 + 9,0 - 7,0 = 6,1 км.
Таким образом, окончательный порядок движения по маршруту 1 будет
А - К - З - Е - В - Б - А .
Таким же методом определим кратчайший путь объезда пунктов по
маршруту 2. В результате расчётов получим маршрут А - Г - Д - И - Ж - А
длиной 19,4 км. Порядок движения по маршрутам 1 и 2 приведен ниже:
Б 7,0
3,2 А
2,2 А
1 Г 2
В L= 27,8 км
За= kg 2,0 L= 19,4 км 5,6
3,6 За= kg
Е 10,6 Д
Ж
2,4
2,8 5,8
З 2,0 К И
Исходные данные для задачи 1. (по вар.)
9. M = 15 т.
Q = 5 т. 1,8 А Б 1900 Ж 980
9,2 В 1680 З 750
Б 10,4 Г 1920 И 1300
И Д 1420 К 1570
1,4 8,9 5,6 Е 1330 Л 1150
З 5,3
В Ж 3,8 К
2,1
8,7 5,5 4,5
7,4 4,1
Г
3,2
3,6 Л
8,8 Е 10,6
5,4
Д
ЗАДАЧА 2. Расчет рациональных маршрутов.
На конкретных примерах рассмотрим разработку маятниковых
развозочных маршрутов со снабженческо-сбытовых баз и складов по-
требителям.
а)
(2 ездки)
П1 6 км Т
8 км 13 км 7,5 км
Б П2 (2 ездки)
15 км
б) Г Lоб = 103 км (общий пробег)
Б1 6 км L пор = 57 км (порожний пробег)
L гр = 46 км (пробег с грузом)
13 км Коэффициент использования автомобиля:
8 км . = Lгр / L об = 0,44
15 км
Б Б2
в)
Г Lоб = 97,5 км
Б1 L пор = 51,5 км
L гр = 46 км
13 км 7,5 км
8 км .= 0,47
15 км
Б2
Т - транспортное автохозяйство, Б - база или склад, П1,П2 - потребители продукции.
Маятниковые маршруты с обратным холостым пробегом. При выпол-
нении маятниковых маршрутов с обратным пробегом без груза возникает не-
сколько вариантов движения автомобилей с разным по величине порожним
пробегом. Необходимо разработать такой маршрут, при котором порожний
пробег был бы минимальным.
На рисунке приведены условия перевозочной задачи, на примере реше-
ния которой составим маршрут движения автомобиля с минимальным порож-
ним пробегом.
Из пункта Б (база) необходимо доставить груз в пункты П1 и П2. Объёмы
перевозок (в ездках) и расстояния указаны на рисунке.
За время в наряде автомобиль может выполнить на маршруте БП1 и БП2
по две ездки с грузом.
Необходимо составить маршруты движения автомобилей, дающих ми-
нимум порожних пробегов.
Количество ездок определяется по формуле:
Q
ne = -----------------
q * y
где Q - объём поставок продукции за рассматриваемый период, т.;
q - грузоподъёмность автомобиля, т.;
у - коэффициент использования грузоподъёмности в зависимости
от класса груза.
При решении этой задачи могут возникнуть два варианта:
1. Продукция поставляется в П2, а потом в П1, из П1 - в Т-автохозяйство (рис. б)
2. Продукция поставляется в П1, а потом в П2, из П2 - в Т-автохозяйство (рис. в )
Как видим из рисунков наиболее эффективен второй вариант, поскольку ко-
эффициент использования во втором случае выше, чем в первом.
Однако на практике при разработке маршрутов, руководствуются правилом:
чтобы уменьшить нулевой пробег, необходимо разрабатывать такую систему
маршрутов, при которой первый пункт погрузки и последний пункт разгрузки
находился вблизи от автохозяйства, мы склонны принять первый вариант.
Чтобы проверить правильность выбора, решим задачу математическим ме-
тодом.
Задача составления рациональных маршрутов, обеспечивающих мини-
мальный порожний пробег транспортных средств, сводится к следующей за-
даче линейного программирования:
Минимизируем линейную форму
n
minL = ( Lтпj - Lбпj ) * Xj
j = 1
n
при условиях 0 <= Xj <=Qj и Xj <=N
j=1
пункты назначения пронумерованы в порядке возрастания разностей (Lпjт - Lбпj )
Lп1т - Lбп1 < Lп2т - Lбп2 < Lп3т - Lбп3 < … < Lпnт - Lбпn
Оптимальное решение:
X1 = min (Q1, N);
X2 = min (Q2, N - X1);
X3 = min (Q3, N - X1 - X2 );
n-1
Xn = min (Q2, N - Xj ),
j=1
где
L - порожний пробег, км;
LПjТ - расстояние от пункта назначения Пj до Т (второй порожний пробег);
LБПj - расстояние от Б до Пj (гружёный пробег);
j - индекс потребителя (j=1,2,…,n);
Xj - количество автомобилей, работающих на маршрутах с последним
пунктом разгрузки Пj;
N - число автомобилей, работающих на всех маршрутах;
Qj - объём перевозок (в ездках автомобиля).
Решая эту задачу, мы должны знать, что наилучшее решение получается
при такой системе маршрутов, когда максимальное число автомобилей закан-
чивает работу в пунктах назначения c минимальными разностями ( Lтпj - Lбпj ),
т.е. второго порожнего и гружёного пробега.
Для решения задачи необходимо исходные данные записать в специ-
альную таблицу, чтобы с её помощью произвести все необходимые
вычисления по составлению маршрутов. Для каждого пункта назначения, т.е.
по каждой строке, рассчитывают алгебраические разности, которые записы-
вают в соответствующие клетки столбца разностей.
Таблица 1
|