Стратегия управления доставкой груза на транспорте

Размещено на http://www.allbest.ru/

МИНИСТЕРСТВО ОБРАЗОВАНИЯ РЕСПУБЛИКИ БЕЛАРУСЬ

УЧРЕЖДЕНИЕ ОБРАЗОВАНИЯ

«БЕЛОРУССКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ ТРАНСПОРТА»

Кафедра «Управление грузовой и коммерческой работой»

Курсовая работа

по дисциплине

«Менеджмент в отрасли»

на тему: «Стратегия управления доставкой груза на транспорте»

Гомель 2012

Содержание

Введение

1. Оптимизация грузопотоков для заданного региона транспортной сети

1.1 Общее положение

1.2 Постановка и решение задачи оптимизации грузопотоков

2. Определение оптимального замкнутого маршрута

2.1 Общие теоретические положения

2.2 Расчет оптимального замкнутого маршрута

3. Выбор и расчет загрузки транспортных средств для доставки грузов потребителю

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

3.2 Транспортные тарифы и правила их применения

3.3 Выбор наиболее производительного транспортного средства

4. Расчет оптимальной интенсивности поступления вагонов

4.1 Общие положения теории очередей

4.2 Характеристика трехканальной модели очереди

4.3 Расчет оптимальной интенсивности поступления вагонов в транспортно-грузовую систему

Заключение

Список использованной литературы

транспортный груз маршрут

Введение

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

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

1. Оптимизация грузопотоков для заданного региона транспортной сети

1.1 Общие положения

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

Разработка модели оптимизации грузопотоков условно включает 5 взаимосвязанных этапов:

постановка или формулировка задачи;

разработка математической модели изучаемой системы;

отыскание решения с помощью этой модели;

проверка данной модели и получаемого решения;

уточнение принятого решения на практике.

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

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

Одним из методов решения задач транспортной оптимизации является линейное программирование.

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

1.2 Постановка и решение задачи оптимизации грузопотоков

Для решения задач оптимизации используют линейное программирование. При этом задачи должны иметь следующие условия:

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

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

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

Математическая модель этой задачи такова:

; , ;

, ; , ;

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

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

В таблице 1.1 и 1.2 приведены условия задачи и удельный (на 1 грузовой вагон) затраты на порожний пробег.

Таблица 1.1 Условие задачи

Пункты отправления	Пункты назначения
	D1	D2	D3	D4	D5	Избыток вагонов
S1	X11	X12	X13	X14	X15	180
S2	X21	X22	X23	X24	X25	180
S3	X31	X32	X33	X34	X35	170
Недостаток вагонов	30	110	125	80	185	530

Таблица 1.2 Расстояние между пунктами отправления и назначения

Пункты отправления	Пункты назначения
	D1(Г)	D2(В)	D3(Е)	D4(З)	D5(И)	Избыток вагонов
S1(А)	225	235	325	520	415	180
S2(Б)	100	110	200	395	290	180
S3(Д)	90	235	75	270	165	170
Недостаток вагонов	30	110	125	80	185	530

В таблице 1.1 указано, что в пунктах S1, S2 и S3 имеется избыток порожних вагонов в количествах 180, 180 и 170 вагонов. Соответственно в пунктах D1, D2, D3, D4 и D5 не хватает 30, 110, 125, 80 и 185 порожних вагонов.

В таблице 1.2 приведены расстояния Lij на порожний пробег одного вагона из пункта отправления i в пункт назначения j.Таким образом, определим такие значения Xij (i=1, 2, 3; j = 1, 2, 3, 4, 5) таблицы 1.1, чтобы удовлетворить поставленным ограничениям и минимизировать суммарные затраты:

min L = 225X11 + 235X12 + 325X13 + 520X14 + 415X15 + 100X21 + 110X22 + + 200X23 + 395X24 + 290X25 + 90X31 + 235X32 + 75X33 + 270X34 + 165X35;

X11 + X12 +X13 +X14 +X15 = 180;

X21 + X22 + X23 + X24 + X25 = 180;

X31 + X32 + X33 + X34 + X35 = 170;

X11 + X21 + X31 = 30;

X12 + X22 + X32 = 110;

X13 + X23 + X33 = 125;

X14 + X24 + X34 = 80;

X15 + X25 + X35 = 185.

Получение исходного опорного плана. Первым шагом при решении транспортной задачи является получение допустимого плана, т. е. возможного решения, которое удовлетворяет поставленным ограничениям. Если при этом получены минимальные суммарные затраты, то такой план называется оптимальным планом или решением, в данном случае это минимальный план. Исходный план можно легко построить, используя разработанный алгоритм, называемый «правилом северо-западного угла».

«Правило северо-западного угла» формулируется следующим образом:

1. Начать с северо-западного угла исходной таблицы (таблица 1.1) и сравнить количество вагонов, имеющихся в пункте отправления Si с количеством вагонов, потребных в пункте назначения Dj.

Если D1 < S1, т. е. если количество вагонов, потребных в пункте D1 меньше количества вагонов, имеющихся в пункте S1, то принять X11 = D1 и перейти к переменной Х12 (т. е. к следующей переменной по горизонтали).

Если D1 = S1,то принять X11 = D1 и перейти к переменной Х22 (т. е. по диагонали).

Если D1 > S1, то принять X11 = S1 и перейти к переменной Х21 (т. е. по вертикали).

2. Продолжать этот процесс шаг за шагом (от северо-западного до юго-восточного угла таблицы).

Таблица 1.3 Первый опорный план

Пункты отправления	Пункты назначения
	Г (325)	В (335)	Е (425)	З (620)	И (515)	Избыток вагонов
А (100)	100	50	80			180
Б (225)			30	170		180
Д (305)				10	90	170
Недостаток вагонов	30	110	125	80	185	530

Исходный план задачи, полученный с помощью правила северо-западного угла, приведен в таблице 1.3 в виде возможных значений Xij. Легко проверить, что этот набор значений Xij является планом, так как удовлетворяются ограничения по каждой строке и каждому столбцу. Суммарные затраты регулировки порожних вагонов для этого плана можно получить, умножая выделенные значения Xij таблицы 1.3 на соответствующие значения Lij из таблицы 1.2 и суммируя полученные произведения. При этом получим:

L=(30·225+50·235+40·325+85·200+80·395+15·290+170·165)= 85250 ваг-км.

Построим систему потенциалов на основе равенства

.

Присвоим первому поставщику потенциал U1 = 100. От первого поставщика порожние вагоны направляют первому, второму и третьему потребителю. Следовательно, V1 = 100 + 225 = 325, V2 = 100 + 235 = 335, V3 = 100 + + 325 = 425. Зная потенциалы третьего потребителя, найдем потенциал второго поставщика: U2 = V3 - L23 = 425 - 200 = 225. Потенциал четвертого потребителя V4 = 225 + 395 = 620. Потенциал третьего поставщика V5 = V4 + - L34 = 225 + 290 = 515. Потенциал пятого потребителя V5 = 515 - 165 = 350.

Проверка плана на оптимальность. Когда построен план и определена соответствующая ему целевая функция, определим, является ли полученный план оптимальным. План считается оптимальным, если для всех свободных ячеек выполняется условие

.

Осуществляем проверку:

U1 + L14 = 100 + 520 = 620 ? 620 - условие выполняется;

U1 + L15 = 100 + 415 = 515 ? 515 - условие выполняется;

U2 + L21 = 225 + 100 = 335 ? 325 - условие выполняется;

U2 + L22 = 225 + 110 = 335 ? 335 - условие выполняется;

U2 + L25 = 350 + 90 = 440 ? 325 - условие выполняется;

U3 + L31 = 350 + 235 = 585 ? 335 - условие выполняется;

U3 + L32 = 350 + 75 = 425 ? 425 - условие выполняется;

U3 + L33 = 350 + 270 = 620 ? 620 - условие выполняется.

Выполнив проверку по свободным ячейкам, видим, что условие выполняется. Количество занятых клеток равно 7, что также удовлетворяет требованиям. Следовательно, данный план является оптимальным.

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

В таблице 1.4 и 1.5 приведены условия задачи и удельный (на 1 грузовой вагон) затраты на порожний пробег.

Таблица 1.4 Условие задачи

Пункты отправления	Пункты назначения
	D1	D2	D3	Избыток вагонов
S1	X11	X12	X13	105
S2	X21	X22	X23	175
S3	X31	X32	X33	160
Недостаток вагонов	150	135	155	440

Таблица 1.5 Расстояние между пунктами отправления и назначения

Пункты отправления	Пункты назначения
	D1(В)	D2(К)	D3(З)	Избыток вагонов
S1(А)	235	110	235	105
S2(Б)	435	310	245	175
S3	520	395	270	160
Недостаток вагонов	150	135	155	440

Таблица 1.6 Первый опорный план

Пункты отправления	Пункты назначения
	В (335)	К (210)	З (85)	Избыток вагонов
Г (100)	105			105
Ж (-100)	45	130		175
Д(-185)		5	155	160
Недостаток вагонов	150	135	155	440

L=(105·235+45·435+130·310+5·395+155·270)=128375 ваг-км.

Осуществляем проверку:

U1 + L14 = 100 + 110 = 210 ? 210 - условие выполняется;

U1 + L15 = 100 + 235 = 335 ? 85 - условие выполняется;

U2 + L21 = -100 + 245 = 145 ? 85 - условие выполняется;

U2 + L22 = -185 + 520 = 335 ? 335 - условие выполняется.

Выполнив проверку по свободным ячейкам, видим, что условие выполняется. Количество занятых клеток равно 5, что также удовлетворяет требованиям. Следовательно, данный план является оптимальным.

2. Определение оптимального замкнутого маршрута

2.1 Общие теоретические положения

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

Рисунок 2.1 Схема размещения транспортных узлов, посещаемых коммивояжерами

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

Дня решения этой задачи необходимо составить математическую модель. Введем обозначения: i и j - номера пунктов выезда и въезда, lij - расстояние от пункта i до пункта j. Из таблицы 2.1 видно, что lij в общем случае может быть не равно расстоянию в обратном направлении lij ? lji.

Таблица 2.1 Расстояния между пунктами

Из пункта i	В пункт j
	1	2	3	4	5	6
1	l11	l12	l13	l14	l15	l16
2	l21	l22	l23	l24	l25	l26
3	l31	l32	l33	l34	l35	l36
4	l41	l42	l43	l44	l45	l46
5	l51	l52	l53	l54	l55	l56
6	l61	l62	l63	l64	l65	l66

Построим математическую модель задачи, введя булевы переменные:

xij={

1, если коммивояжер из пункта i переезжает в пункт j,

0, если не поедет,

где i,j - 1, 2, ..., n. Требуется минимизировать выражение:

(2.1)

при следующих ограничениях:

,

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

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

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

вычисление нижней границы (оценки);

разбиение на подмножества, т. е. ветвление;

пересчет оценок;

нахождение решений;

определение признака оптимальности;

оценка точности приближенного решения.

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

Сущность метода ветвей и границ применительно к задаче коммивояжера состоит в следующем.

1. Обозначим через G0 множество всех циклов, среди которых отыскивается кратчайший цикл t*: l(t*)=min l(t). При этом под циклом будем понимать набор из n упорядоченных пар городов, образующих замкнутый маршрут, который проходит через каждый город только один раз:

t=[(i1,i2),(i2,i3),…,(in-1,in),(in,i1)].

Длина цикла равна

(2.2)

2. Вычислим оценку для множества G0.Для этого введем понятие приведенной матрицы и процесса приведения.

Пусть hi=minj Сij, тогда Cij'=Сij-hi0 и l(t)=.

Пусть Hj=mini Cij', тогда Cij''=Cij'-Hj0 и l(t)=.

Полученная матрица С" называется приведенной. Она обладает тем свойством, что в каждой ее строке и столбце имеется по крайней мере один нуль. Процесс, позволяющий из неотрицательной матрицы С получить приведенную неотрицательную матрицу С", называется приведением. Сумма вычитаемых в процессе приведения элементов называется приводящими константами и обозначается hУ. Оптимальный план задачи о коммивояжере с матрицей С" является оптимальным и для задачи о коммивояжере с матрицей С. Длина цикла l(t) на приведенной матрице будет меньше длины цикла l(t) на исходной матрице на сумму приводящих констант: l(t)=l(t)+hУ.

Так как приведенная матрица содержит только неотрицательные элементы, то сумма приводящих констант может служить нижней границей длины цикла при исходной матрице С, т. е. является оценкой исходного множества G0: о(G0)=hУ.

3. Произведем ветвление множества G0 на два непересекающихся подмножества G1 и G2:

подмножество G1 получается из множества G0 при добавлении следующего условия: из пункта r следует непосредственно идти в пункт s;

подмножество G2 получается из множества G0 при добавлении условия: из пункта r запрещается непосредственный переход в пункт s.

При этом пару городов (r, s) выбирают так, чтобы множество G1 с наибольшей вероятностью содержало оптимальный цикл, а множество G2 - не содержало. Следовательно, пара (r, s) выбирается из множества пар претендентов (i, j), которым соответствуют нулевые элементы матрицы С, то есть Сij=0, таким образом, чтобы циклам, входящим в подмножество G2, соответствовали как можно более длинные пути. Так как по определению подмножества G2 путь по любому из этих циклов переходит из города r в некоторый промежуточный пункт j (js), а в город s коммивояжер приезжает из некоторого пункта i (ir), длина этого пути будет не меньше чем

И(r, s)=

Поэтому необходимо выбрать пару (r, s) так, чтобы И(r, s) было максимально, т. е.

И(r,s)= (2.3)

при условии, что Сij=0.

4. Выполним преобразование матрицы расстояний при ветвлении и пересчитаем оценки. Каждому подмножеству, полученному в результате ветвление, будет соответствовать своя приведенная матрица и своя оценка. Матрица С2, соответствующая подмножеству G2, получается из матрицы С в результате следующих преобразований:

запрещается переезд из города r в город s: Сrs>;

проводится процедура приведения матрицы. Оценка подмножества G2 равна оценке исходного множества G0 и И(r, s):

о(G2)=о(G0)+И(r, s).

Для построения матрицы С1 соответствующей подмножеству G1 выполняются следующие преобразования матрицы С:

вычеркивается строка r и столбец s из матрицы С, так как из каждого города можно выезжать только один раз и в каждый город можно въезжать только один раз;

запрещается переезд из города s в город r (Сsr>), а также все другие переезды, которые приводят к образованию замкнутых подциклов;

выполняется процесс приведения матрицы С.

Оценка подмножества G1 равна оценке исходного множества G0 и сумме приводящих констант:

о( G1)=о( G0) +.

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

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

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

2.2 Расчет оптимального замкнутого маршрута

Условие задачи. Имеется 6 городов, соединенных между собой дорогами так, что из любого транспортного узла можно проехать в любой другой пункт. Выезжая из одного пункта, коммивояжер должен побывать в других пунктах по одному разу и вернуться в исходный пункт. Поэтому маршрут коммивояжера образует замкнутый цикл без петель. Требуется найти такой маршрут, проходящий через все пункты и заканчивающийся в пункте выезда, чтобы пройденное расстояние (время поездки) было минимальным. Расстояния между городами заданы матрицей C=(Сij); i=1, 2, 3, 4, 5, 6; j=1, 2, 3, 4, 5, 6.

Таблица 2.2 Расстояние между пунктами

С =	?	84	24	84	112	154
	96	?	48	70	84	56
	36	60	?	84	112	28
	72	36	60	?	42	168
	48	72	96	70	?	126
	120	60	36	168	56	?

Решение

1. Осуществим приведение матрицы С по строкам и столбцам. Приведенную матрицу С(0) представим в виде таблицы, приводящие константы по строкам и столбцам запишем соответственно справа матрицы и снизу.

С' =		1	2	3	4	5	6	hi
	1	?	60	0	60	88	130	24
	2	28	?	0	22	36	8	48
	3	8	32	?	56	84	0	28
	4	36	0	24	?	6	132	36
	5	0	24	48	22	?	78	48
	6	84	24	0	132	18	?	36
	Hj	0	0	0	18	0	0
С(0) =		1	2	3	4	5	6	hi
	1	?	60	0	38	82	130	24
	2	48	?	0	0	30	8	48
	3	8	32	?	34	78	0	28
	4	36	0	24	?	6	132	36
	5	0	24	48	22	?	78	48
	6	84	24	0	132	20	?	36
	Hj	0	0	0	18	0	0	28 220

2. Определим оценку множества G0, вычислив сумму приводящих констант

о(G0)= = 220 + 28 = 248.

Шаг 1.

1.1 Выбираем пары городов-претендентов на ветвление, т.е. (i,j) для которых Cij=0: C13=0; C23=0; C24=0; C36=0; C42=0; C45=0; C51=0; C54=0; C63=0. Для выделенных претендентов подсчитаем оценки по формуле:

И(i,j)=.

И(1,3)=38; И(2,3)=0; И(2,4)=0; И(3,6)=16; И(4,2)=24; И(4,5)=14; И(5,1)=8; И(5,4)=0; И(6,3)=12. Для ветвления выберем пару претендентов с максимальной оценкой И(i,j), то есть пару (1,3), так как max И(i,j)=И(1,3)=38.

1.2. Произведем ветвление:

G0=G11 G21,

где G11={1,3}, а G21={1,3}.

1.3. Вычислим оценку для G21:

о(G21)=о(G0)+И(1,3)=248+38=286.

1.4. Построим матрицу С1(1). Для этого вычеркнем в матрице С(0) первую строку и третий столбец. Чтобы избежать образования замкнутых подциклов, запретим переезд коммивояжера из города 3 в город 1, полагая С31>, и выполним процесс приведения. В результате получим матрицу С1(1):

С1(1) =		1	2	4	5	6	hi
	2	48	?	0	30	8	0
	3	8	32	34	78	0	0
	4	36	0	?	0	132	0
	5	0	24	0	?	78	0
	6	70	10	96	0	?	14
	Hj	0	0	0	0	0

Определим оценку для множества G11:

о(G11)=о(G0)+= 248 + 14 = 262.

Так как о(G11)<о(G21), то на следующем шаге производим ветвление подмножества G11.

Шаг 2.

2.1 Выбираем пары городов-претендентов на ветвление, т.е. (i,j) для которых Cij=0:

C24=0; C26=0; C36=0; C42=0; C45=0; C51=0; C54=0; C65=0.

Для выделенных претендентов подсчитаем оценки по формуле:

И(i,j)=.

И(2,4)=8; И(3,6)=16; И(4,2)=10; И(4,5)=0; И(5,1)=8; И(5,4)=0; И(6,5)=10.

Для ветвления выберем пару претендентов с максимальной оценкой И(i,j), то есть пару (3,6), так как max И(i,j)=И(3,6)=54.

2.2. Произведем ветвление:

G11=G12 G22,

где G12={(1,3), (3,6}, а G22={(1,3), (3,6)}.

2.3. Вычислим оценку для G22: о(G22)=о(G11)+И(3,6)= 286 + 16 = 302.

2.4. Построим матрицу С1(2). Для этого вычеркнем в матрице C1(1) третью строку и шестой столбец. Чтобы избежать образования замкнутых подциклов, запретим переезд коммивояжера из города 6 в город 1, полагая С61>, и выполним процесс приведения. В результате получим матрицу С1(2):

С1(2) =		1	2	4	5	hi
	2	48	?	0	30	0
	4	36	0	?	0	0
	5	0	24	0	?	0
	6	?	10	96	0	0
	Hj	0	0	0	0

Определим оценку для множества G12:

о(G12)=о(G11)+= 262 + 0 = 262.

Так как о(G12)<о(G22), то на следующем шаге производим ветвление подмножества G12.

Шаг 3.

3.1 Выбираем пары городов-претендентов на ветвление, т.е. (i,j) для которых Cij=0:

C24=0; C42=0; C45=0; C51=0; C54=0; C65=0.

Для выделенных претендентов подсчитаем оценки по формуле:

И(i,j)= (2.4)

И(2,4)=30; И(4,2)=10; И(4,5)=0; И(5,1)=36; И(5,4)=0; И(6,5)=10.

Для ветвления выберем пару претендентов с максимальной оценкой И(i,j), то есть пару (2,4), так как max И(i,j)=И(5,1)=30.

3.2. Произведем ветвление:

G12=G13 G23,

где G13={(1,3), (3,6), (5,1)}, а G22={(1,3), (3,6), (5,1)}.

3.3. Вычислим оценку для G23: о(G23)=о(G12)+И(5,1)= 286 + 36 = 322.

3.4. Построим матрицу С1(3). Для этого вычеркнем в матрице C1(2) пятую строку и первый столбец. Чтобы избежать образования замкнутых подциклов, запретим переезд коммивояжера из города 6 в город 5, полагая С65>, и выполним процесс приведения. В результате получим матрицу С1(3):

С1(3) =		2	4	5	hi
	2	?	0	30	0
	4	0	?	0	0
	6	0	86	?	10
	Hj	0	0	0

Определим оценку для множества G13:

о(G13)=о(G12)+= 262 + 10 = 272.

Так как о(G13)<о(G23), то на следующем шаге производим ветвление подмножества G13.

Шаг 4.

4.1 Выбираем пары городов-претендентов на ветвление, т.е. (i,j) для которых Cij=0:

C24=0; C42=0; C45=0; C62=0.

Для выделенных претендентов подсчитаем оценки по формуле:

И(i,j)=.

И(2,4)=86; И(4,2)=0; И(4,5)=30; И(6,2)=86.

Для ветвления выберем пару претендентов с максимальной оценкой И(i,j), то есть пару (3,6), так как max И(i,j)=И(2,4)=86.

4.2. Произведем ветвление:

G13=G14 G24,

где G14={(1,3), (3,6), (5,1), (2,4)}, а G22={(1,3), (3,6), (5,1), (2,4)}.

4.3. Вычислим оценку для G24:

о(G24)=о(G13)+И(2,4)= 272 + 86= 358.

4.4. Построим матрицу С1(4). Для этого вычеркнем в матрице C1(3) вторую строку и четвертый столбец. Чтобы избежать образования замкнутых подциклов, запретим переезд коммивояжера из города 4 в город 2, полагая С42>, и выполним процесс приведения. В результате получим матрицу С1(4):

С1(4) =		2	5	hi
	4	?	0	0
	6	0	?	0
	Hj	0	0

Определим оценку для множества G14:

о(G14)=о(G13)+= 272 + 0 = 272.

Матрица С1(4) имеет размерность 22 и допускает включение в маршрут только двух пар городов (4,5) и (6,2), что соответствует шагам 5 - 6. В результате получаем цикл l(t)={(1,3), (3,6), (5,1), (2,4), (4,5), (6,2)}, отвечающий подмножеству G16. Длина цикла l(t) равна оценке подмножества G16: l(t)=о(G16)=272 или 24+28+60+70+42+48=272.

Последовательность объезда городов можно представить следующим образом: 1>3>6>2>4>5>1 (рисунок 2.2).



Рисунок 2.2 Оптимальный маршрут коммивояжера

Таким образом, используя метод линейного программирования, был составлен оптимальный маршрут коммивояжера. Определяющим фактором стало расстояние между пунктами. Полученный маршрут имеет вид: 1>3>6>2>4>5>1, расстояние данного маршрута составило 378 километров.

3. Выбор и расчет загрузки транспортных средств для доставки груза потребителю

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

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

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

В процессе выполнения данной курсовой работы требуется определить:

свойства заданных грузов;

значимость факторов, влияющих на выбор того или иного вида груза;

используемые виды транспортных тарифов на перевозку грузов;

коэффициенты загрузки транспортных средств;

количество транспортных средств, необходимых для доставки грузов потребителям.

К перевозке предъявляются следующие виды грузов:

ветчина в упаковке;

картофель;

мясные консервы;

станки.

Для указанных грузов характеристика следующая.

Ветчина - весьма распространенный мясной консервант, чаще всего свиной окорок, просоленный и прокопченный. Состав ветчины: воды около - 30 %, белковых веществ - 25 %, жира - 35 %, негорючих веществ (золы) - 10 %. Различают сорта: вареная ветчина, запеканка легкого копчения, вестфальская ветчина, полендвица и др.

История ветчины насчитывает более 2 тыс. лет. Уже в 1 веке до н.э. жители Галлии прослыли большими экспертами в области обработки свиного мяса и активно экспортировали в Рим куски ветчины размером с четверть откормленного борова. Качественная ветчина - это не просто деликатес. Она очень подходит приверженцам правильного питания, которые соблюдают здоровую диету. В ветчине содержится много белка и очень мало жиров, она малокалорийна, содержит железо и цинк.

Картофель - многолетнее растение семейства пасленовых, широко возделываемое ради его съедобных клубней. Род Solanum, к которому принадлежит картофель, насчитывает около 2000 видов, но лишь несколько десятков из них образуют клубни.

Картофель клубненосный выращивают в 130 странах, где проживает 75% населения планеты. Это пятый по значению после пшеницы, кукурузы, риса и ячменя источник калорий в рационе современного человека. Средний урожай этой культуры - около 150 ц/га. Ведущими производителями картофеля являются Россия, Китай, Польша, США и Индия.

В мире 50% производимого картофеля идет в пищу, 35% - на корм скоту и около 10% оставляется на посадочный материал. В США на продовольственные нужды расходуется 92% продукции, причем 57% ее перерабатывается промышленностью и 35% продается в сыром виде для домашнего приготовления. Пищевая промышленность выпускает картофель жареный (чипсы), сушеный, быстрозамороженный, в виде дегидратированных ломтиков для жарки, картофельных хлопьев для пюре и т.п.

В сыром клубне картофеля клубненосного 79% воды, 18% углеводов, 2% белка, 0,9% зольных веществ и 0,4% целлюлозы. Клубни богаты витамином С, магнием, фосфором и калием.

Мясные консервы - мясные продукты, герметично упакованные в жестяные или стеклянные банки и подвергнутые воздействию высокой температуры для уничтожения микроорганизмов и придания продукту стойкости при хранении.

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

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

В консервах содержится 50--70 % воды, 10--30 % белков, 8--30 % жиров, до 3,5 % минеральных веществ.

Для производства мясных консервов используют мясо всех видов, жир, субпродукты, готовые мясные изделия, кровь, различные продукты растительного происхождения, пряности. Тару для консервов изготовляют из белой жести, стекла, сплавов алюминия и полимерных материалов

По назначению консервы подразделяют на обеденные, употребляемые, как правило, после кулинарной обработки, закусочные, детские и для диетического питания.

Станки металлорежущие - машины для изготовления частей других машин в основном путем снятия с заготовки стружки режущим инструментом. Многое из того, что производится в результате человеческой деятельности в настоящее время, делается на металлорежущих станках или с помощью машин, изготовленных с применением таких станков. Их спектр очень широк - от строгальных станков с ручным управлением до компьютеризованных и роботизованных систем. Более 500 разных типов существующих металлорежущих станков могут быть подразделены не менее чем на десять групп по характеру выполняемых работ и применяемому режущему инструменту: разрезные, токарные, сверлильные, фрезерные, шлифовальные, строгальные, зубообрабатывающие, протяжные, многопозиционные автоматические и др.

Режущий инструмент того или иного вида (резец, фреза и т.п.) снимает с обрабатываемого (металлического, пластмассового, керамического) изделия стружку примерно так же, как это происходит при чистке картофеля ножом. Материал режущего инструмента должен быть значительно более твердым и прочным, чем материал обрабатываемой детали. Станок оборудуется механизмом, обычно состоящим из салазок, шпинделей, ходовых винтов и столов с поперечным и продольным перемещением, который позволяет перемещать инструмент относительно обрабатываемой детали. На станках с ручным управлением такое относительное перемещение задает оператор, пользуясь маховичками подачи для перемещения суппорта с резцедержателем. На станках с числовым программным управлением (ЧПУ) перемещения задаются программой последовательных команд, записанной в памяти компьютера. Программа включает и выключает приводные механизмы, например электродвигатели и гидроцилиндры, которые осуществляют подачу суппорта с автоматическим регулированием взаимного положения обрабатываемой детали и режущей кромки.

Станки почти всех типов выпускаются как с ручным управлением, так и в варианте с ЧПУ. В механических мастерских бытового обслуживания, в любительских домашних, на машиностроительных заводах чаще всего встречаются разрезные, сверлильные, токарные, фрезерные и шлифовальные станки. Для указанных грузов определяются их свойства согласно следующей классификации, представленной в таблице 3.1. В данной таблице выбранные свойства помечаются знаком «+», а при отсутствии какого-либо свойства - «-».

Таблица 3.1 Свойства грузов, намеченных к перевозке, для выполнения заказов потребителей

№ п./п.	Классификация грузов	Наименование грузов
		Ветчина в упаковке	Картофель	Мясные консервы	Станки
А. по происхождению
1	продукция растениеводства	-	+	-	-
2	продукция лесоводства	-	-	-	-
3	продукция добывающей (горнорудной) промышленности	-	-	-	-
4	продукция текстильной промышленности	-	-	-	-
5	продукция швейной промышленности	-	-	-	-
6	продукция металлообрабатывающей промышленности	-	-	-	+
7	продукция химической промышленности	-	-	-	-
8	продукция животноводства	+	-	+	-
9	продукция птицеводства	-	-	-	-
10	продукция рыболовства	-	-	-	-
Б. по физико-химическим свойствам
11	скоропортящаяся продукция полеводства, садоводства, огородничества, животноводства, птицеводства, рыболовства	-	-	-	-
12	гигроскопические грузы	-	+	-	-
13	грузы, впитывающие посторонние запахи	-	-	-	-
14	грузы, обладающие специфическим запахом	-	-	-	-
15	устойчиво сохраняющиеся грузы	-	-	+	+
16	смерзающиеся (слеживающиеся) грузы	+	+	-	-
17	опасные грузы	-	-	-	-
18	грузы, убывающие в весе	+	+	-	-
В. по способу перевозки
19	бестарные сыпучие грузы (перевозка насыпью или навалом)	-	-	-	-
20	бестарные жидкие грузы (перевозка наливом)	-	-	-	-
21	сухие грузы (насыпные навалочные, тарно-упаковочные)	+	+	+	+
22	наливные грузы (в таре)	-	-	-	-
Г. по весовым характеристикам и габаритам
23	легковесные грузы	-	-	-	-
24	тяжеловесные грузы	-	-	-	+
25	негабаритные грузы	-	-	-	-
26	длинномерные грузы	-	-	-	-
Д. по технологии хранения
27	ценные грузы и грузы, портящиеся от воздействия влаги и изменения температуры	+	+	+	-
28	грузы, портящиеся от воздействия влаги	-	+	-	+
29	грузы, на подвергающиеся воздействию внешней среды, хранящиеся на открытых площадках	-	-	-	-

В таблице 3.2 дается краткая сравнительная характеристика различных видов транспорта с точки зрения факторов (наиболее благоприятный показатель 1).

Таблица 3.2 Оценка видов транспорта по критериям отправителей

Виды транспорта	Факторы
	Время доставки	Частота отправления грузов	Надежность соблюдения графика доставки	Способность перевозить разные грузы	Способность доставить товар в любую точку территории	Стоимость перевозки
Железнодорожный	4	2	3	1	2	3
Водный	5	4	5	3	4	2
Автомобильный	2	3	2	2	1	4
Воздушный	1	5	4	4	3	5
Трубопроводный	3	1	1	5	5	1

3.2 Транспортные тарифы и правила их применения

Расчеты за услуги, оказываемые транспортными организациями, осуществляются с помощью транспортных тарифов. Тарифы включают в себя:

плату, взыскиваемую за перевозку грузов;

сборы за дополнительные операции, связанные с перевозкой грузов;

правила исчисления платы и сборов.

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

На железнодорожном транспорте для определения стоимости перевозки грузов используют общие, исключительные, льготные и местные тарифы.

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