Файл: Экономика практические задачи и решения.pdf

29 5
,
9 105
,
0 1
1
=
=
=
T
N
5. Общие затраты
13951
)
(
2
=
×
+
×
×
+
×
+
=
+
+
T
S
z
E
k
S
z
IC
T
d
IC
T
S
TC
LT
T
LT
T
руб/год
Данная формула по своему существу не отличается от формулы, приведенной в модели точки заказ, но в ней сделаны две замены: Q = d
×T и D/Q = 1/T.
6. Уровень сервиса
9857
,
0 38 14
,
30 8
,
108 1503
,
0 1
)
(
1
=
×
×
−
=
×
×
−
=
+
T
d
S
z
E
SL
LT
T
, или 98,6%.
Вопросы для проверки знаний
1. Что такое материальный запас? Какие виды материальных запасов Вы знаете?
2. Проанализируйте затраты на управление запасов. Как величина этих затрат зависит от ритма и размера партии поставки?
3. Охарактеризуйте базовую модель управления запасами. Дайте определение понятий точ- ки заказа и периода заказа, периода поставки.
4. В чем заключается отличия между базовой моделью, моделями точки заказа и периода заказа?
Задания для самостоятельного решения
Задача 2.1. Базовая модель управления запасами
Рассчитайте параметры базовой модели управления запасами при следующих исход- ных данных:
Варианты
Показатель
1 2 3 4 5 6
Спрос, шт/год
13575 14450 3300 11425 10050 14125
Период поставки, дн
6 5 7 4 6 7
Цена продукции, руб/шт
123 146 76 102 53 56
Затраты на доставку партии груза, руб 615 584 152 306 106 168
Норма прибыли, %/год
6% 15% 6% 8% 5% 10%
Количество рабочих дней в периоде 365 365 365 365 365 365
К числу параметров базовой модели относятся: оптимальная партия поставки, период заказа, количество поставок в течение года, точка заказа, средний уровень запасов и общие затраты.
Задача 2.2. Модель точки заказа
Рассчитайте параметры модели точки заказа при следующих исходных данных:
Варианты
Показатель
1 2 3 4 5 6
Спрос, шт/год
5250 10325 10100 4475 14200 7650
СКО спроса, шт/год
740 1229 1081 443 1590 1132
Период поставки, дн
4 4 5 8 9 5
Цена продукции, руб/шт
134 134 134 97 140 139
Затраты на доставку партии, руб
402 268 268 485 700 278

30
Норма прибыли, %/год
15% 10% 14% 12% 13% 7%
Вероятность покрытия за период
LT,
%
80% 75% 75% 70% 70% 95%
Величина штрафа, руб/шт
13,4 8,04 12,06 5,82 5,6 11,12
Количество рабочих дней в периоде 365 365 365 365 365 365
К числу параметров модели точки заказа относятся: оптимальная партия поставки, пе- риод заказа, количество поставок в течение года, точка заказа, средний уровень запасов, об- щие затраты и уровень сервиса.

31
Кольцевой маршрут
– это направление движения транспортного средства от исходно- го пункта О до пункта А, через пункты A, B, C, … до пункта N и от пункта N обратное дви- жение к пункту О (O-A-B-C-…-N-O).
Рис. 3.2. Схема кольцевого маршрута
Радиальные маршруты используются в тех случаях, когда объем спроса у получателя сопоставим или даже превышает грузоподъемность автомобиля.
Пример 1
В пункты A, B и C необходимо доставить груз X. Единица измерения груза X – штуки.
Объем спроса по пунктам назначения: А = 450 шт., B = 500 шт., C = 750 шт. Грузовмести- мость транспортного средства – 500 шт.
Очевидно, что в рассматриваемом случае доставка груза X может осуществляться толь- ко по радиальным маршрутам. При этом в пункт C груз будет доставлен в два этапа – сперва
500, а затем 250 шт. Решение задачи представлено в следующей таблице:
Таблица 3.1
№ п/п Маршрут
Объем достав-
ки, шт
Коэффициент запол-
нения кузова
1
O-A-O
450 0,90 2 O-B-O
500 1,00 3 O-C-O
500 1,00 4 O-C-O
250 0,50
Кольцевые маршруты используются в тех случаях, когда объем спроса существенно меньше грузовместимости автомобиля. В этом случае в кузовном отсеке транспортного средства формируется сборный груз, предназначенный сразу для нескольких получателей.
Пример 2
Исходные те же, что и в примере 1, кроме объема спроса по пунктам назначения: А =
145 шт., В = 80 шт., С = 200 шт. Суммарный объем спроса составляет 145 + 80 + 200 = 425 шт.
Этот объем меньше грузовместимости транспортного средства, а потому для пунктов
A, B и C формируется сборный груз, который будет развозиться по кольцевому маршруту O-
A-B-C-O. При этом коэффициент заполнения кузова составляет 425/500 = 0,8.

32
Задача для самостоятельного решения
Из исходного пункта, в котором располагается грузовой терминал, необходимо доста- вить грузы 12 получателям. Координаты исходного пункта: x
0
= 10, y
0
= 15. Грузовмести- мость транспортного средства 1500 шт.
Координаты и объем спроса получателей представлены в следующей таблице:
i
x
i
y
i
q
i
i
x
i
y
i
q
i
1 17 15 450 7 4 14 250 2 6 15 400 8 17 2 200 3 13 3 400 9 12 22 450 4 9 20 200 10 6 12 300 5 19 7 150 11 19 17 475 6 8 8 450 12 12 8 550 где x
i
, y
i
– координаты i-го получателя, q
i
– объем спроса i-го получателя, шт.
Требуется построить оптимальную схему развозки грузов получателям, при которой суммарный пробег автотранспорта будет минимальным.
L
Рекомендации по решению задачи
Возьмите лист в клеточку, отложите на нем оси декартовой системы координат Ox и Oy и отметьте в этой системе точками места расположения грузового терминала и 12 получате- лей. Далее, опираясь на Вашу интуицию, нанесите на карту маршруты движения транспорт- ных средств от исходного пункта к пунктам назначения и обратно. Старайтесь, по возможно- сти, использовать кольцевые маршруты вместо радиальных – кольцевые маршруты считают- ся более эффективными. Вместе с тем следите, чтобы объем перевозки по любому из мар- шрутов не превосходил грузовместимости автомобиля. После нанесения маршрутов измерь- те по линейке длину каждого из маршрутов, сложите и переведите полученную величину в километры.
Для сравнения постройте два или три варианта развозки и сравните их при критерию суммарного пробега автотранспорта.
3.1.2. Метод Кларка-Райта
Метод Кларка-Райта был разработан двумя британскими учеными Г. Кларком (G.
Clarke) и Дж.В. Райтом (J.W. Right)
2
Несмотря на давность разработки (метод опубликован в 1963 г.), он до сих пор остается самым популярным методом для решения данной задачи, о чем свидетельствует практика его применения.
Метод Кларка-Райта относится к числу приближенных, итерационных методов и предназначается для компьютерного реше-
2
G. Clarke and J.W. Right, “Scheduling of Vehicles from a Central Depot to a Number of Delivery Points”, Operations
Research, vol. 11 (1963), pp. 568-581.
Рис. 3.3. Исходная схема развозки
Таблица 3.2

33
ния задачи развозки. Погрешность решения не превосходит в среднем 5-10%. Достоинствами метода являются его простота, надежность и гибкость, что позволяет учитывать целый ряд дополнительных факторов, влияющих на конечное решение задачи.
Рассмотрим метод Кларка-Райта на примере. За основу возьмем исходные данные из предыдущего пункта, где предлагалась задача для самостоятельного решения (таблица 3.2).
Местоположение оптовой базы и 12 получателей, а также объем поставок каждому получа- телю приведены на рисунке 3.3. На этом же рисунке указана и исходная схема развозки гру- зов. Согласно исходной схеме, для доставки груза каждому отдельному получателю органи- зуется отдельный маршрут. Например, водитель загружает в кузов партию 450 шт. и везет ее в пункт 1, там разгружается, затем возвращается на базу, берет вторую партию 400 шт. и ве- зет ее в пункт 2 и т.д. Таким образом, исходная схема развозки включает в себя только ради- альные маршруты движения автомобиля, причем количество радиальных маршрутов совпа- дает с количеством получателей. В данном случае, схема развозки состоит из 12 радиальных маршрутов.
Суть метода заключается в том, чтобы, отталкиваясь от исходной схемы развозки, по шагам перейти к оптимальной схеме развозки с кольцевыми маршрутами. С этой целью вво- дится такое понятие, как километровый выигрыш. Обратимся к рисунку 3.4:
На рисунке 3.4 отображены две схемы развозки. Схема развозки А (слева) обеспечивает доставку грузов в пункты 1 и 2 по радиальным маршрутам. В этом случае суммарный пробег автотранспорта равен:
L
А
= d
01
+ d
10
+ d
02
+ d
20
= 2d
01
+ 2d
02
Схема развозки B предполагает доставку грузов в пункты 1 и 2 по кольцевому маршру- ту. Тогда пробег автотранспорта составляет:
L
B
= d
01
+ d
12
+ d
02
Схема В по показателю пробега автотранспорта дает, как правило, лучший результат, чем схема А. И поэтому при переходе от схемы А к схеме В получаем следующий километ- ровый выигрыш:
s
12
= L
A
– L
B
= d
01
+ d
02
– d
12
В общем случае мы имеем километровый выигрыш:
s
ij
= d
0i
+ d
0j
– d
ij
где S
ij
– километровый выигрыш, получаемый при объединении пунктов i и j, км; d
0i
, d oj
– расстояние между оптовой базой и пунктами i и j соответственно, км; d ij
– расстояние между пунктами i и j, км.
Теперь вернемся к нашему примеру. Рассчитаем расстояния между пунктами 0, 1 и 3 по формуле:
0
,
7
)
15 15
(
)
17 10
(
)
(
)
(
2 2
2 1
0 2
1 0
01
=
−
+
−
=
−
+
−
=
y
y
x
x
d
км
Рис. 3.4. Схемы развозки А и B

34
Аналогично получаем, что d
03
= 12,37 и d
13
= 12,65. Тогда для пунктов 1 и 3 получаем километровый выигрыш: s
13
= 7 + 12,37 – 12,65 = 6,72
≈ 6,7 км.
Полученные значения заносим в следующую таблицу, где представлены расстояния между пунктами d ij
(правая верхняя часть матрицы) и километровые выигрыши s ij
(левая нижняя часть матрицы):
Таблица 3.3
Матрица расстояний и километровых выигрышей
Матрица расстояний между пунктами (d
ij
), км
0
7,0 4,0 12,4 5,1 12,0 7,3 6,1 14,8 7,3 5,0 9,2 7,3 0,0
1 11,0 12,6 9,4 8,2 11,4 13,0 13,0 8,6 11,4 2,8 8,6 0,0 0,0 2 13,9 5,8 15,3 7,3 2,2 17,0 9,2 3,0 13,2 9,2 0,0 6,7 2,5 3 17,5 7,2 7,1 14,2 4,1 19,0 11,4 15,2 5,1 0,0 2,7 3,3 0,0 4 16,4 12,0 7,8 19,7 3,6 8,5 10,4 12,4 0,0 10,8 0,8 17,2 0,7 5 11,0 16,6 5,4 16,6 13,9 10,0 7,1 0,0 2,9 4,0 12,6 0,3 8,3 6
7,2 10,8 14,6 4,5 14,2 4,0 0,0 0,0 7,8 4,2 3,4 1,6 6,2 7 17,7 11,3 2,8 15,3 10,0 0,0 8,8 1,7 23,0 0,2 21,4 11,2 3,2 8 20,6 14,9 15,1 7,8 0,0 5,7 2,1 0,6 8,8 2,8 0,0 2,0 1,4 9 11,7 8,6 14,0 0,0 0,6 6,0 6,0 1,6 3,1 7,8 8,3 4,9 0,6 10 13,9 7,2 0,0 13,4 0,1 6,4 3,9 11,3 2,3 0,0 8,9 7,9 0,3 11 11,4
Матрица
километровых
выигрышей
(s
ij
),
км
0,0 5,7 2,1 14,6 0,0 12,3 10,6 3,4 14,2 0,6 5,1 5,1 12
Теперь, когда проведена вся необходимая подготовительная работа, приступим непо- средственно к решению задачи.
Воспользуемся алгоритмом Кларка-Райта. Здесь приводится только пошаговое описа- ние алгоритма. Демонстрация использования данного алгоритма применительно к рассмат- риваемой задаче приводится в таблице 5 и соответствующих комментариях к ней.
Шаг 1.
На матрице километровых выигрышей находим ячейку (i*, j*) с максимальным километровым выигрышем S
max
:
*)
*,
(
)
,
(
max
,
max
j
i
s
j
i
s
S
j
i
=
=
,
При этом должны соблюдаться следующие три условия:
1) пункты i* и j* не входят в состав одного и того же маршрута;
2) пункты i* и j* являются начальным и/или конечным пунктом тех маршрутов, в состав ко- торых они входят;
3) ячейка (i*, j*) не заблокирована (т.е. рассматривалась на предыдущих шагах алгоритма).
Если удалось найти такую ячейку, которая удовлетворяет трем указанным условиям, то переход к шагу 2. Если не удалось, то переход к шагу 6.
Шаг 2.
Маршрут, в состав которого входит пункт i*, обозначим как маршрут 1. Соот- ветственно, маршрут, в состав которого входит пункт j*, обозначим как маршрут 2. Введем следующие условные обозначения:
N = {1, 2, …, n} – множество получателей; N
1
(N
1
⊂ N) – подмножество пунктов, вхо- дящих в состав маршрута 1; N
2
(N
2
⊂ N) – подмножество пунктов, входящих в состав мар- шрута 2.
Очевидно, что i*
∈ N
1
, j*
∈ N
2
и N
1
∩ N
2
=
∅ (согласно шагу 1, условие 1).
Рассчитаем суммарный объем поставок по маршрутам 1 и 2:

35
∑
∈
=
1 1
N
k
k
q
q
и
∑
∈
=
2 2
N
k
k
q
q
, где q
k
– объем спроса k-го пункта, шт (см табл. 3).
Шаг 3.
Проверим на выполнение следующее условие: q
1
+ q
2
≤ c где c – грузовместимость автомобиля, шт.
Если условие выполняется, то переход к шагу 4, если нет – к шагу 5.
Шаг 4.
Производим объединение маршрутов 1 и 2 в один общий кольцевой маршрут X.
Будем считать, что пункт i* является конечным пунктом маршрута 1, а пункт j* – начальным пунктом маршрута 2. При объединении маршрутов 1 и 2 соблюдаем следующие условия: последовательность расположения пунктов на маршруте 1 от начала и до пункта i* не меняется; пункт i* связывается с пунктом j*; последовательность расположения пунктов на маршруте 2 от пункта j* и до конца не ме- няется.
Шаг 5.
Повторяем шаги 1-4 до тех пор, пока при очередном повторении не удастся найти S
max
, который удовлетворяет трем условиям из шага 1.
Шаг 6.
Рассчитываем суммарный пробег автотранспорта.
Теперь рассмотрим применение этого алгоритма к рассматриваемой задаче. Весь ход последовательного решения задачи представлен в таблице 5.
Таблица 3.4
Решение задачи развозки методом Кларка-Райта
Шаг 1
Шаг 2
Шаг 3
Шаг 4
Условия
№
п/п i* j* S
max
1 2 3
q
1
q
2
q
1
+q
2
≤ c?
№
маршрута
Маршрут
1
2 3
4
5 6 7
8
9
10
11
12
1
8 3 23,0 + + + 200 400
+
1 0-3-8-0
2
8 5 21,4 + + + 600 150
+
1 0-3-8-5-0
3
5 3 17,2 - + + -
-
-
-
-
4
12 3 14,6 + + + 550 750
+
1 0-12-3-8-5-0
5
12 8 14,2 - - + -
-
-
-
-
6
11 1 13,4 + + + 475 450
+
2 0-1-11-0
7
6 3 12,6 + - + -
-
-
-
-
8
12 5 12,3 - + + -
-
-
-
-
9
11 5 11,3 + + + 925 1300
-
-
-
10
8 6 11,2 + - + -
-
-
-
-
11
5 1 10,8 + + + 1300 925
-
-
-
12 12 6 10,6 + + + 1300 450
-
-
-
13 11 8 8,9 + - + -
-
-
-
-
14
9 4 8,8 + + + 450 200
+
3 0-9-4-0
15
8 1 8,8 + - + -
-
-
-
-
16
6 5 8,3 + + + 450 1300
-
-
-
17 10 7 8,3 + + + 300 250
+
4 0-7-10-0
18 11 9 7,9 + + + 925 650
-
-
-
19
7 2 7,9 + + + 550 400
+
4 0-2-7-10-0
20 10 6 7,8 + + + 950 450
+
4 0-2-7-10-6-0

36
Комментарии к таблице 5
Графа 1 – номер итерации
Графы 2, 3 – номера пунктов i* и j*, которые обозначают ячейку с максимальным ки- лометровым выигрышем S
max
= s(i*,j*), найденную в результате просмотра матрицы кило- метровых выигрышей (таблица 4).
Графа 4 – значение максимального километрового выигрыша S
max
Графы 5, 6 и 7 – результаты проверки условий 1, 2 и 3 при выполнении шага 1. “+” – положительный результат, “–” – отрицательный результат.
Графы 8 и 9 – объем перевозок по маршруту 1, в состав которого входит пункт i* (q
1
), и маршруту 2, в состав которого входит пункт j* (q
2
).
Графа 10 – проверка на условие q
1
+ q
2
≤ c, где c – грузовместимость транспортного средства. “+” – положительный результат проверки условия, “–” – отрицательный результат.
Графа 11 – порядковый номер кольцевого маршрута (всего в ходе решения получено всего четыре кольцевых маршрута, см. рис. 6).
Графа 12 – структура кольцевого маршрута, образовавшегося на данной итерации.
Рассмотрим, как происходит поэтапный поиск оптимального решения задачи.
Начнем с того, что исходный план развозки состоит из 12 радиальных маршрутов, ко- гда доставка груза в каждый из пунктов назначения осуществляется по отдельному маршру- ту (см. рис. 4). При этом общий пробег автотранспорта составляет (см. треугольную матрицу расстояний, табл. 4):
L
0
= 2
× d
01
+ 2
× d
02
+ … + 2
× d
0,12
= 2
× 7,0 + 2 × 4,0 + … + 2 × 7,3 = 195 км
Теперь начнем пошаговый переход к новому оптимальному решению задачи, которое за счет объединения радиальных маршрутов в кольцевые позволит уменьшить суммарный пробег автотранспорта (графически это новое решение представлено на рис. 6).
Итерация 1.
Объединяем два радиальных маршрута: 0-8-0 (объем доставки 200 шт.) и
0-3-0 (объем доставки 400 шт.) в общий кольцевой маршрут (под № 1) 0-8-3-0 (объем достав- ки 600 шт.). При этом суммарный пробег автотранспорта сокращается на 23,0 км.
Итерация 2.
К кольцевому маршруту
№ 1 – 0-8-3-0 (600 шт.) присоединяем радиальный маршрут 0-5-0 (150 шт.). При этом пункт 5 присоединяем к пункту 8, в результате чего получаем новую структуру кольцевого маршрута 0-5-8-3-0 (750 шт.).
Суммарный пробег автотранспорта сокращается еще на 21,4 км.
Отметим важность соблюдения последовательности пунктов в кольцевом маршруте: именно 0-5-8-3-0, а не 0-5-3-8-0 или 0-8-3-5-0. Если i* = 5 и j* = 8, то после объединения они должны стоять на маршруте друг за другом.
Итерация 3.
Объединение пунктов 3 и 5 обеспечило бы выигрыш в 17,2 км. Но это объединение невозможно, поскольку оба пункта уже входят в состав кольцевого маршрута №1 – 0-5-8-3-0, а объединять можно пункты только из разных маршрутов. Таким образом, констатируем нарушение условия 1 и переходим к сле-
Рис. 3.5. Оптимальная схема развозки