Решение транспортной задачи о назначении

 

 

Министерство высшего образования РФ

 

 

Алтайский государственный университет

 имени И. И. Ползунова

 

 

Кафедра экономики и производственного менеджмента

 

 

 

 

 

 

 

Расчетное задание

 

по теме: решение транспортной задачи о назначении

 

 

 

 

 

 

 

Выполнила: ст. гр. МА-21

Мамула Е. О.

                                                                     Проверила: Родина Г. Е.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Барнаул 2005

Транспортная задача о назначении

 

Груз находится в пункте А – 4000 кг. Используется автомобиль грузоподъемностью 2,5 т; груз – П класса (γ = 0,8). Необходимо организовать перевозку между пунктами с минимальным пробегом подвижного состава.

 

Пункты	Б	В	Г	Д	Е	Ж	З	И	К
Погрузка	500	485	375	240	680	400	620	240	460
Выгрузка	-	437	400	365	200	145	410	35	90

 

 

 

 

 

 

Решение

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

На данной схеме находим наименьшее звено – К-Е  (2,8). Затем рассматрели все звенья, связанные  с вершинами  выбранного звена, т. е. К-И=3,4; К-З=5,8; Е-Д=6,3; Е-З=3,8; Е-В=5,7; Е-Б=6,0.

 Из них выбрали звено с наименьшим  расстоянием (К- И=3,4км). Далее рассматрели все звенья, связанные с вершинами полученной ломаной линии К-Е -И, из них выбрали наименьшее до последней вершины сети. Получилось КЕИЖЗАГБВД- кратчайшая связывающая сеть, она представлена на рисунке. Около каждого пункта проставлено количество ввозимого (верхняя цифра) и вывозимого грузов (нижняя цифра ).

 

 

 

 

 

 

 

 

 

 

 

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

Группируем маршруты из пунктов с учетом количества ввозимого и вывозимого грузов (исходные данные) и вместимости единицы подвижного состава (2500*0,8=2000 кг.).

Маршруты сгруппированы следующим образом:

 

Маршрут 1			Маршрут 2
Пункт	Количество груза, кг		Пункт	Количество груза, кг
З	620	410	Ж	400	145
К	460	90	Г	375	400
Е	680	200	Д	240	365
И	240	35	Б	500	-
			В	485	437
Итого	2000	735	Итого	2000	1347

 

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

Для расчета очередности объезда пунктов маршрута №1 используем «метод треугольников».

 

А	5,4	10,7	5,2	9,8	4,4
5,4	Б	5,3	10,6	9,1	3,7
10,7	5,3	В	15,9	12	9,0
5,2	10,6	15,9	Ж	7,2	9,6
9,8	9,1	12	7,2	Д	5,4
4,4	3,7	9,0	9,6	5,4	Г
35,5	34,1	52,9	48,5	43,5	32,1

 

 

 

 

 

 

 

 

Начальный маршрут построили для трех пунктов матрицы В, Ж, Д, имеющих наибольшие значения величины, показанной в  итоговой строке (52,9;48,5;43,5), т.е. маршрут ВЖДВ.

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

Для каждой пары пунктов найдена величина приращения маршрута  (∆)  по формуле:

 

∆kp = Cki + Cip –  Ckp , где С – расстояние, км;

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

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

p – индекс второго пункта из пары.

 

∆ВЖ = САВ + Саж –  СВЖ  =  10,7+5,2-15,9=0

∆ЖД = САЖ  + САД – СЖД    =  5,2+9,8-7,2=7,8

∆ДВ = СДА  + САВ – СДВ  =  9,8+10,7-12=8,5

Из полученных значений выбрали минимальное значение, т.е. ∆ВЖ = 0  и между соответствующими пунктами вставляем пункт А. Получаем маршрут ВАЖДВ.

Аналогично рассчитывалось приращение маршрута для Б.

∆ВА  = СВБ + САБ – САВ  =5,3+5,4-10,7=0

∆АЖ  = СБА + СБЖ   – САЖ  = 5,4+10,6-5,2=10,8

∆ЖД  = СБЖ + СБД  –  СЖД = 10,6+9,1-7,2=12,5

∆ДВ  = Сбд + СБВ – СДВ =9,1+5,3-12=2,4

 

Расчеты для пункта Г:

∆ВБ  = СГВ + СБГ  – СБВ  = 9,0+3,7-5,3=7,4

∆БА  = СБГ + САГ   – СБА  = 3,7+4,4-5,4=2,7

∆АЖ  = САГ + СГЖ – САЖ = 4,4+9,6-5,2=8,8

∆ЖД  = Сгж + СДГ – СДЖ =9,6+5,4-7,2=7,8

∆ДВ  = Сгд + СГВ – СДВ = 5,4+9,0-12=2,4

 

Окончательный порядок объезда пунктов первого маршрута ВБАЖДГ, длина которого составит 37,5 км. Можно утверждать, что полученная последовательность объезда дает наименьший или весьма близкий к наименьшему пути путь объезда пунктов маршрута 1.

Аналогично рассчитали очередности объезда пунктов маршрута №2.

 

А	11,4	8,5	11,9	15,2
11,4	Е	6,2	2,8	3,8
8,5	6,2	И	3,4	9,2
11,9	2,8	3,4	К	5,8
15,2	3,8	9,2	5,8	З
47	24,2	27,3	23,9	34

Начальный маршрут – АЗИА(47; 34; 27,3).

Величина приращения маршрута для пункта Е:

∆АЗ  = САЕ + СЕЗ  – САЗ  = 11,4+3,8-15,2=0

∆ЗИ  = СЕЗ + СЕИ   – СЗИ  =3,8+ 6,2-9,2=0,8

∆ИА= СЕИ+ СЕА  –  СИА=6,2+11,4-8,5=9,1.

 Величина приращения маршрута для пункта К:

∆АЕ  = САК + СКЕ  – САЕ  = 11,9+2,8-11,4=3,3

∆ЕЗ  = СЕК + СЗК   – СЕЗ = 2,8+5,8-3,8=4,8

∆ЗИ  = СЗК + СИК  –  СЗИ = 5,8+3,4-9,2=0

∆ИА  = СИК + СКА – СИА = 3,4+11,9-8,5=6,8.

В результате указанных расчетов порядок объезда пунктов в этом маршруте будет АЕЗКИА и путь движения в данном случае составит 32,9 км. На рисунке представлена схема движения по маршрутам 1 и 2.

 

 

 

Маршрут № 2

 

 

Маршрут № 1

 

 

 

 

Этап  4. Определение возможности одновременного развоза и сбора  груза на маршруте

Проверяем, какое количество груза будет находиться в автомобиле на протяжении всего маршрута  № 1.

 

Пункт	Количество груза, кг
	Погрузка	Выгрузка	Всего в автомобиле
А	-	2000	2000
Ж	400	145	1745
Д	240	365	1870
Г	375	400	1895
В	485	437	1847
Б	500	-	1347

 

 

Для маршрута № 2:

 

Пункт	Количество груза, кг
	Погрузка	Выгрузка	Всего в автомобиле
А	-	2000	2000
И	240	35	1795
К	460	90	1425
З	620	410	1215
Е	680	200	735

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

Из таблиц видно, что на протяжении  всего маршрута автомобиль не будет перегружен, так как в примере задано, что максимальная загрузка автомобиля составляет 2,5 т. при грузе – П класса (γ = 0,8).