АННОТАЦИЯ.
Курсовой проект на тему транспортный процесс и производительность подвижного состава.
Выполнил – Кирьянов А. В.
Руководитель – Савиновских А. Г.
Курсовой проект состоит из двух частей: теоретической и практической.
В теоретической части раздела описывается сама суть проблемы и характеристики рассматриваемой организации и ее автомобилей.
В практической части непосредственно идёт решение транспортной задачи, благодаря которой получается оптимальный сменно-суточный план перевозки грузов.
Курсовой проект состоит из 44 листов формата А4. А так же имеется 32 таблицы, содержание, введение, заключение и список литературы.
СОДЕРЖАНИЕ
ВВЕДЕНИЕ………………………………………………………………………..3
1. ТРАНСПОРТНЫЙ ПРОЦЕСС И ПРОИЗВОДИТЕЛЬНОСТЬ ПОДВИЖНОГО СОСТАВА
1.1 Характеристика маршрутов…………………………………………………..5
1.2 Технико-эксплуатационные показатели работы автомобилей…………….6
1.3 Производительность автомобиля…………………………………………….8
2. ПРАКТИЧЕСКИЙ РАЗДЕЛ
2.1 Математическая модель задачи…………………………………………….12
2.2 Алгоритм и метод решения задачи…………………………………………13
2.3 Решение задачи маршрутизации методом потенциалов………………….16
2.4 Определение маршрутов методом совмещенных планов………………...32
2.5 Технологический расчет маршрутов…………………………………….....36
2.6 Сводные показатели сменно-суточного пробега…………………………..39
ЗАКЛЮЧЕНИЕ………………………………………………………………….41
СПИСОК ИСПОЛЬЗОВАННЫХ ИСТОЧНИКОВ……………………………43
ВВЕДЕНИЕ
В современных экономических условиях, эффективное управление системой снабжения является обязательным условием успешного функционирования и развития предприятия. резкое ухудшение макроэкономических показателей вынуждает предприятия оптимизировать собственную систему снабжения. В большей степени это касается организаций с небольшим годовым оборотом.
Актуальность темы объясняется тем, что на сегодняшний день складывается жесткая конкуренция при выборе транспортных услуг, эффективного вида транспорта для доставки внешнеторговых грузов. В связи с этим деятельность транспортных фирм, в том числе и автотранспортных, должна отвечать предъявляемым повышенным требованиям к качеству транспортного обслуживания внешнеэкономической деятельности предприятий. Исследование особенностей работы автотранспортных фирм может позволить разработать и обосновать предложения по совершенствованию деятельности транспортной организации
Объектом исследования в работе является акционерное общество (далее по тексту АО) «VEZU». Предмет исследования – процесс организации и технологии перевозки грузов.
Основной целью работы является разработка мероприятий по совершенствованию перевозки грузов на предприятии.
При написании работы использовались следующие источники информации:
- учебные пособия по логистике, экономике предприятия и экономико-математическому моделированию;
- научные статьи и публикации, в том числе труды отечественных ученых Аникина Б.А., Касимова А.Х., Николаева В.П., а также зарубежных ученых Андерсона Дж., Миллена А., Наруса Дж., Фостера Т. и других;
- материалы сети Интернет, посвященные проблематике работы.
Практическая значимость работы состоит в том, что полученные в ходе выполнения модели могут быть использованы для оптимизационных процессов в организации в будущих периодах.
ТРАНСПОРТНЫЙ ПРОЦЕСС И ПРОИЗВОДИТЕЛЬНОСТЬ ПОДВИЖНОГО СОСТАВА
1.1 Характеристика маршрутов.
В условиях такого большого города как Челябинск, автоперевозки могут быть вызваны совершенно различными ситуациями: переезд офиса, квартирный переезд, перевозка имущества за город. В связи с этим автотранспортное предприятие должно иметь у себя в штате квалифицированных координаторов, которые смогут быстро и качественно организовать перевозку груза.
В компании «VEZU» 2 координатора обеспечивают организацию перевозок груза по городу, 3 координатора организовывают перевозку по междугороднему направлению на собственном транспорте и 3 координатора на наёмном транспорте.
Организация перевозки по городским маршрутам осуществляется наёмным транспортом. Координатору поступает заявка на перевозку в которой заказчик указывает все параметры груза, который необходимо перевезти. Далее начинается поиск подвижного состава, подходящего для перевозки. Координатор просматривая анкеты наёмных водителей и автомобилей подыскивает подходящую кандидатуру. Согласовав все детали перевозки, координатор договаривается с водителем и выдаёт ему сопроводительные документы на перевозку.
Выбор маршрута следования является очень ответственным заданием для организатора перевозки. Требования к выбранному маршруту:
- маршрут перевозки должен быть определен по кратчайшему расстоянию;
- доля холостых и нулевых пробегов в общем пробеге автомобиля должна быть минимальной;
- обеспечивать максимальное использование грузоподъёмности автомобилей;
- обеспечение возможности диспетчерского руководства и управления перевозками.
Маршруты движения подразделяются на маятниковые и кольцевые.
Маятниковым называется маршрут, при котором путь следования подвижного состава в прямом и обратном направлениях проходит по одной и той же трассе. Кольцевым маршрутом называется путь следования подвижного состава по замкнутому контуру, соединяющему несколько пунктов погрузки-разгрузки.
1.2 Технико-эксплуатационные показатели работы автомобилей.
Работа грузового автомобильного транспорта характеризуется двумя основными показателями: объемом перевозок грузов и грузооборотом.
Объем перевозок – это количество груза, которое уже перевезено или необходимо перевезти за определенный период времени.
В каждом конкретном случае перевозок грузов автомобильный транспорт обслуживает отдельные корреспонденции клиентуры между двумя определенными пунктами. Таким образом, между каждой парой корреспондирующих между собой пунктов возникают грузовые потоки.
Грузовым потоком (грузопотоком) называется количество груза в тоннах, следующего в определенном направлении за определенный период времени. Грузопотоки бывают односторонние и двусторонние.
Грузооборот – это объем транспортной работы по перемещению груза, которая уже выполнена или должна быть выполнена в течение определенного периода времени.
Представим в таблице 1 объем перевозок грузов за сутки:
Таблица 1. Объем перевозок грузов за сутки
| Отправитель груза и его условное обозначение | Получатель груза и его условное обозначение | Наименование и класс груза | Количество | |||
| Поездок | тонн | |||||
| Склад «Аврора» | А1 | Максидом | Б1 | Цемент в упаковках 1 кл | ||
| Склад «Авансстрой» | А1 | ОБИ | Б2 | Цемент в упаковках 1 кл | ||
| Склад «Астроплас-тика» | А3 | Строитель | Б3 | Цемент в упаковках 1 кл | ||
| Завод «Молодой Ударник» | А4 | Метрика | Б4 | Цемент в упаковках 1 кл | ||
| Завод «ТСК Континент» | А5 | Петрович | Б5 | Цемент в упаковках 1 кл | ||
| Всего |
В таблице 2 приведены технико-эксплуатационные показатели работы подвижного состава.
Таблица 2 –Технико-эксплуатационные показатели работы ПС
| Марка подвижного состава | Грузо- подъемность, т | Время в наряде, ч | Техническая скорость, км/ч | Время простоя под | |||||
| погрузкой, мин | разгрузкой, мин | ||||||||
| MAN | 8,5 | ||||||||
Подвижной состав – это транспортные средства, предназначенные для перевозок грузов, людей, а также транспортные средства, оснащенные специальным оборудованием, предназначенным для производства определенного вида работ. К ним относятся автомобили, тягачи, прицепы, полуприцепы и автомобили специального назначения. К транспортному подвижному составу относятся грузовые автомобили, седельные тягачи с полуприцепами, грузовые прицепы, легковые автомобили, автобусы и пассажирские прицепы, а к специальному – пожарные автомобили, автокраны, машины для уборки городских территорий, передвижные ремонтные мастерские.
1.3 Производительность автомобиля.
Транспортный подвижной состав в свою очередь делится на подвижной состав общего назначения и специализированный (по виду грузов и характеру перевозок). Для каждого вида грузовых и пассажирских перевозок должен выбираться подвижной состав с техническими характеристиками, соответствующими свойствами перевозимых грузов и характеру перевозок.
На основании типа перевозимого груза предприятию АО «VEZU» целесообразно использовать автомобиль марки MANTGLBLс грузоподъемностью в 5 тонн.
В таблице 3 приведена техническая характеристика автомобиля MANTGLBL:
Таблица 3 – Техническая характеристика автомобиля
| Наименование показателя | Значение |
| Снаряженная масса автомобиля, кг | |
| Полная масса, т | |
| Шины | R17.5 |
| Коробка передач | 6-ти ступенчатая механическая коробка передач |
| Подвеска (передняя) | рессорная |
| Подвеска (задняя) | пневмо |
| Объем топливного бака, л | |
| Модель двигателя | D0834 |
| Длина фургона, мм | |
| Ширина фургона, мм | |
| Высота фургона, мм | |
| Грузоподъемность, т | |
| Толщина стенок фургона, мм |
MANTGLBL это надёжный немецкий автомобиль. Производитель грузовых автомобилей MAN является одним из лидеров на автомобильном рынке. Компания была основана 1758 году. В 2008 году фирмой было достигнуто лидерство по продажам грузовиков в России, преодолев отставание от Scania и Volvo.
Определить погрузочно-разгрузочные работы можно как совокупность действий по перемещению груза, которые не вызывают изменения его свойств. Такие работы считаются наиболее трудоемкой частью процесса транспортировки товара.
При грамотном логистическом подходе погрузка-разгрузка оптимизирована и рациональна. В этом аспекте важную роль играет работа на складах. К моменту прибытия автомобиля на склад, груз должен быть готов к перемещению — товар упакован в транспортную тару. Его местонахождение должно легко определяться. При этом партия груза формируется с учетом грузоподъемности автомобиля, а тарно-штучные товары пакетируются.
Подъездные пути всегда должны содержаться в состоянии полной исправности. Твердое покрытие — это обязательное условие для организации погрузочно-разгрузочных работ. Подъемы и спуски зимой очищаются ото льда и посыпаются шлаком или песком. Подъездные пути должны быть шириной не меньше шести метров двадцати сантиметров, если движение двустороннее. При одностороннем движении эта величина составляет три с половиной метра. Площадка для погрузочных работ должна быть ровной. В темное время ее обязательно освещают. Во время погрузки-разгрузки, груз запрещено проносить над кабиной транспортного средства. Кроме того, пока проводятся работы, водителю нельзя находиться в кабине.
Предприятие АО «VEZU» осуществляет перевозку строительных материалов. В качестве транспортной тары применяется упаковка из плотной бумаги. Упаковки укладываются на европаллет в несколько рядов друг на друга, формируя определенную партию груза.
После того как партия груза сформирована, её оборачивают стрейч-пленкой, которая обеспечивает сохранность груза и упрощает погрузочно-разгрузочную работу. Далее партию груза укладывают в автомобиль с помощью погрузочно-разгрузочных механизмов.
Для погрузки и разгрузки грузов применяются дизельные вилочные погрузчики марки LiuGong CPCD20, с грузоподъемностью в 2 тонны.
Таблица 4. Техническая характеристика погрузчика LiuGong CPCD20.
| Наименование показателя | Ед. Изм. | Значение |
| Грузоподъемность | кг | |
| Максимальная высота подъема груза на вилах | мм | 3000-5500 |
| Габаритная ширина | мм | |
| Количество колес | - | |
| Максимальный угол уклона | % | |
| Радиус поворота (внешний) | мм | |
| Тип двигателя | - | Дизельный |
| Производитель | - | LiuGong |
| Размер вил | мм | 45х122х1070 |
| Скорость передвижения | км/ч |
Все грузы укладываются партиями на стандартные европаллеты. Европаллет представляет собой специальный поддон, на котором надежно крепится определенный груз. Европаллеты предназначены для максимально быстрой транспортировки и удобства хранения продукции. Они обеспечивают надежную защиту грузов от деформации и прочих повреждений, которые могут возникнуть в процессе их доставки. Стандартные размеры европаллета 800*1200*150 мм.
На каждом паллете обязательно наличие фирменного клейма EUR в овале, выжженного на правых несущих ножках паллета. На остальных ножках также нанесена маркировка, указывающая производителя и цифровая информация (серия, год выпуска).
Таким образом, АО «VEZU» обладает достаточным парком автотранспортных средств. Погрузка автоматизирована с помощью погрузчиков – это существенно ускоряет саму процедуру погрузки-разгрузки.
ПРАКТИЧЕСКИЙ РАЗДЕЛ.
2.1 Математическая модель задачи.
В автотранспортное предприятие поступили заявки на перевозки однородных грузов на следующий день (табл. 5). Требуется:
1) составить оптимальный сменно-суточный план перевозки грузов (маршруты движения автомобилей и сменные задания водителей), обеспечивающий вывоз заданных объемов при минимальном суммарном порожнем пробеге автомобилей;
2) рассчитать выработку автомобиля в тоннах и тонно-километрах при изменении qγ, Vm, tпв, lг, Tн;
3) по выполненным расчётам сделать выводы об эффективности перевозок.
2.2 Алгоритм и метод решения задачи.
Имеются отправители грузов Ai, А2...Ai...Am с имеющимся у каждого отправителя количеством груза a1, а2...аi...аmтонн.
Имеются получатели груза В1B2...Bj...Bn с требуемым каждому количеством груза в1 в2...вj..вnтонн.
Каждый отправитель может удовлетворить запросы любого получателя.
Расстояния между отправителями и получателями известны и составляют 
км. Общее количество грузов, имеющееся у отправителей и требуемое получателю, равно.
Количество тонн груза для доставки в пункт Вj, из всех пунктов отправления равно
где Хij - количество тонн груза предназначенного к отправке из Аi, в Вj, а так как потребность пункта Вj, составляет bjтонн, то
Сказанное справедливо для любого пункта Вj, поэтому получаем систему п- уравнений:
С другой стороны общее количество груза, отправляемого из пункта Аi, во все пункты назначения Вj, составит
По условиям задачи эта сумма равна наличию груза в пункте Аi.
Сказанное справедливо к любому пункту отправления, имеем т аналогичных (1) уравнений:
(2)
Более компактно уравнения (1) и (2) записываются в форме
Суммарная транспортная работа Р из условий, таким образом, равна
Таким образом, в математической форме транспортная задача требует определения значений переменных Хij, минимизирующих линейную формулу
При этом суммарное количество груза у отправителей должно быть равно количеству, требуемому получателю
Рассмотрим метод потенциалов. Этот метод рекомендуется использовать в курсовом проектировании.
Метод потенциалов реализуется с помощью строго регламентированной процедуры вычислений - алгоритма метода. При этом все вычисления производят в таблице-матрице, составленной по условиям задачи, представленной на рисунке 1.
Задача формулируется так: имеется ряд поставщиков транспортно-однородного груза и ряд потребителей этого груза. Требуется получить такой план закрепления, чтобы при перевозке грузов транспортная работа (ткм) была минимальной. Так как оптимизации подлежит транспортная работа, поэтому в качестве затрат в матрицу вводится расстояние между всеми пунктами.
Для решения задач по составлению оптимальных планов закрепления необходимо провести подготовительную работу, заключающуюся в определении следующих исходных данных:
1. Наименование грузоотправителей и объём поставок грузов.
2. Наименование грузополучателей и объёмы потребления.
3. Расстояние перевозки от каждого грузоотправителя до каждого получателя.
Представим на рис.1 алгоритм метода потенциалов:
Рис. 1. Алгоритм метода
2.3 Решение задачи маршрутизации методом потенциалов
Используем метод минимального километража для построения первого опорного плана (таблица 6):
Таблица 6. Метод минимального километража
Искомый элемент равен c52=1, но т.к. ограничения выполнены, то x52=0.
Опорный план представлен в следующей таблице:
Таблица 7. Первоначальный опорный план
F(x) = 5*207 + 1*108 + 6*27 + 1*27 + 7*54 + 14*27 + 12*81 + 15*99 + 1*162 + 1*27 + 3*54 + 2*27 = 4950
Этап II. Улучшение опорного плана.
Проверим оптимальность опорного плана. Найдем предварительные потенциалы ui, vj. по занятым клеткам таблицы, в которых ui + vj = cij, полагая, что u1 = 0.
u1 + v1 = 5; 0 + v1 = 5; v1 = 5
u6 + v1 = 3; 5 + u6 = 3; u6 = -2
u6 + v8 = 2; -2 + v8 = 2; v8 = 4
u5 + v8 = 1; 4 + u5 = 1; u5 = -3
u5 + v2 = 1; -3 + v2 = 1; v2 = 4
u5 + v5 = 1; -3 + v5 = 1; v5 = 4
u3 + v3 = 14; 0 + u3 = 14; u3 = 14
u3 + v3 = 14; 14 + v3 = 14; v3 = 0
u4 + v3 = 15; 0 + u4 = 15; u4 = 15
u3 + v7 = 12; 14 + v7 = 12; v7 = -2
u2 + v7 = 7; -2 + u2 = 7; u2 = 9
u2 + v4 = 6; 9 + v4 = 6; v4 = -3
u2 + v6 = 1; 9 + v6 = 1; v6 = -8
Опорный план не является оптимальным, так как существуют оценки свободных клеток, для которых ui + vj > cij
(1;2): 0 + 4 > 1; ∆12 = 0 + 4 - 1 = 3
(2;1): 9 + 5 > 5; ∆21 = 9 + 5 - 5 = 9
(2;3): 9 + 0 > 8; ∆23 = 9 + 0 - 8 = 1
(2;5): 9 + 4 > 3; ∆25 = 9 + 4 - 3 = 10
(2;8): 9 + 4 > 3; ∆28 = 9 + 4 - 3 = 10
(3;1): 14 + 5 > 12; ∆31 = 14 + 5 - 12 = 7
(3;2): 14 + 4 > 4; ∆32 = 14 + 4 - 4 = 14
(3;5): 14 + 4 > 11; ∆35 = 14 + 4 - 11 = 7
(3;6): 14 -8 > 4; ∆36 = 14 -8 - 4 = 2
(3;8): 14 + 4 > 10; ∆38 = 14 + 4 - 10 = 8
(4;1): 15 + 5 > 16; ∆41 = 15 + 5 - 16 = 4
(4;2): 15 + 4 > 7; ∆42 = 15 + 4 - 7 = 12
(4;5): 15 + 4 > 13; ∆45 = 15 + 4 - 13 = 6
(4;6): 15 -8 > 5; ∆46 = 15 -8 - 5 = 2
(4;8): 15 + 4 > 12; ∆48 = 15 + 4 - 12 = 7
(6;2): -2 + 4 > 1; ∆62 = -2 + 4 - 1 = 1
max(3,9,1,10,10,7,14,7,2,8,4,12,6,2,7,1) = 14
Выбираем максимальную оценку свободной клетки (3;2): 4
Для этого в перспективную клетку (3;2) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-».
Таблица 8. Опорный план №2
Проверим оптимальность опорного плана. Найдем предварительные потенциалы ui, vj. по занятым клеткам таблицы, в которых ui + vj = cij, полагая, что u1 = 0.
u1 + v1 = 5; 0 + v1 = 5; v1 = 5
u6 + v1 = 3; 5 + u6 = 3; u6 = -2
u6 + v8 = 2; -2 + v8 = 2; v8 = 4
u5 + v8 = 1; 4 + u5 = 1; u5 = -3
u5 + v2 = 1; -3 + v2 = 1; v2 = 4
u3 + v2 = 4; 4 + u3 = 4; u3 = 0
u3 + v3 = 14; 0 + v3 = 14; v3 = 14
u4 + v3 = 15; 14 + u4 = 15; u4 = 1
u3 + v7 = 12; 0 + v7 = 12; v7 = 12
u2 + v7 = 7; 12 + u2 = 7; u2 = -5
u2 + v4 = 6; -5 + v4 = 6; v4 = 11
u2 + v6 = 1; -5 + v6 = 1; v6 = 6
u5 + v5 = 1; -3 + v5 = 1; v5 = 4
Опорный план не является оптимальным, так как существуют оценки свободных клеток, для которых ui + vj > cij
(1;2): 0 + 4 > 1; ∆12 = 0 + 4 - 1 = 3
(1;3): 0 + 14 > 7; ∆13 = 0 + 14 - 7 = 7
(1;4): 0 + 11 > 8; ∆14 = 0 + 11 - 8 = 3
(1;6): 0 + 6 > 2; ∆16 = 0 + 6 - 2 = 4
(2;3): -5 + 14 > 8; ∆23 = -5 + 14 - 8 = 1
(3;6): 0 + 6 > 4; ∆36 = 0 + 6 - 4 = 2
(4;6): 1 + 6 > 5; ∆46 = 1 + 6 - 5 = 2
(5;4): -3 + 11 > 6; ∆54 = -3 + 11 - 6 = 2
(5;6): -3 + 6 > 1; ∆56 = -3 + 6 - 1 = 2
(5;7): -3 + 12 > 4; ∆57 = -3 + 12 - 4 = 5
(6;2): -2 + 4 > 1; ∆62 = -2 + 4 - 1 = 1
(6;3): -2 + 14 > 5; ∆63 = -2 + 14 - 5 = 7
(6;4): -2 + 11 > 3; ∆64 = -2 + 11 - 3 = 6
(6;7): -2 + 12 > 3; ∆67 = -2 + 12 - 3 = 7
max(3,7,3,4,1,2,2,2,2,5,1,7,6,7) = 7
Выбираем максимальную оценку свободной клетки (1;3): 7
Для этого в перспективную клетку (1;3) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-».
Цикл приведен в таблице (1,3 → 1,1 → 6,1 → 6,8 → 5,8 → 5,2 → 3,2 → 3,3).
Таблица 9. Перераспределение по циклу.
Из грузов хij стоящих в минусовых клетках, выбираем наименьшее, т.е. у = min (5, 2) = 0. Прибавляем 0 к объемам грузов, стоящих в плюсовых клетках и вычитаем 0 из Хij, стоящих в минусовых клетках. В результате получим новый опорный план.
Таблица 10. Опорный план №3
Проверим оптимальность опорного плана. Найдем предварительные потенциалы ui, vj. по занятым клеткам таблицы, в которых ui + vj = cij, полагая, что u1 = 0.
u1 + v1 = 5; 0 + v1 = 5; v1 = 5
u6 + v1 = 3; 5 + u6 = 3; u6 = -2
u6 + v8 = 2; -2 + v8 = 2; v8 = 4
u5 + v8 = 1; 4 + u5 = 1; u5 = -3
u5 + v5 = 1; -3 + v5 = 1; v5 = 4
u1 + v2 = 1; 0 + v2 = 1; v2 = 1
u3 + v2 = 4; 1 + u3 = 4; u3 = 3
u3 + v3 = 14; 3 + v3 = 14; v3 = 11
u4 + v3 = 15; 11 + u4 = 15; u4 = 4
u3 + v7 = 12; 3 + v7 = 12; v7 = 9
u2 + v7 = 7; 9 + u2 = 7; u2 = -2
u2 + v4 = 6; -2 + v4 = 6; v4 = 8
u2 + v6 = 1; -2 + v6 = 1; v6 = 3
Опорный план не является оптимальным, так как существуют оценки свободных клеток, для которых ui + vj > cij
(1;3): 0 + 11 > 7; ∆13 = 0 + 11 - 7 = 4
(1;6): 0 + 3 > 2; ∆16 = 0 + 3 - 2 = 1
(2;3): -2 + 11 > 8; ∆23 = -2 + 11 - 8 = 1
(3;6): 3 + 3 > 4; ∆36 = 3 + 3 - 4 = 2
(4;6): 4 + 3 > 5; ∆46 = 4 + 3 - 5 = 2
(5;7): -3 + 9 > 4; ∆57 = -3 + 9 - 4 = 2
(6;3): -2 + 11 > 5; ∆63 = -2 + 11 - 5 = 4
(6;4): -2 + 8 > 3; ∆64 = -2 + 8 - 3 = 3
(6;7): -2 + 9 > 3; ∆67 = -2 + 9 - 3 = 4
max(4,1,1,2,2,2,4,3,4) = 4
Выбираем максимальную оценку свободной клетки (1;3): 7
Для этого в перспективную клетку (1;3) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-».
Таблица 11. Перераспределение по циклу.
Цикл приведен в таблице (1,3 → 1,2 → 3,2 → 3,3).
Из грузов хij стоящих в минусовых клетках, выбираем наименьшее, т.е. у = min (3, 3) = 27. Прибавляем 27 к объемам грузов, стоящих в плюсовых клетках и вычитаем 27 из Хij, стоящих в минусовых клетках. В результате получим новый опорный план.
Таблица 12. Опорный план №4
Проверим оптимальность опорного плана. Найдем предварительные потенциалы ui, vj. по занятым клеткам таблицы, в которых ui + vj = cij, полагая, что u1 = 0.
u1 + v1 = 5; 0 + v1 = 5; v1 = 5
u6 + v1 = 3; 5 + u6 = 3; u6 = -2
u6 + v8 = 2; -2 + v8 = 2; v8 = 4
u5 + v8 = 1; 4 + u5 = 1; u5 = -3
u5 + v5 = 1; -3 + v5 = 1; v5 = 4
u1 + v2 = 1; 0 + v2 = 1; v2 = 1
u3 + v2 = 4; 1 + u3 = 4; u3 = 3
u3 + v7 = 12; 3 + v7 = 12; v7 = 9
u2 + v7 = 7; 9 + u2 = 7; u2 = -2
u2 + v4 = 6; -2 + v4 = 6; v4 = 8
u2 + v6 = 1; -2 + v6 = 1; v6 = 3
u1 + v3 = 7; 0 + v3 = 7; v3 = 7
u4 + v3 = 15; 7 + u4 = 15; u4 = 8
Опорный план не является оптимальным, так как существуют оценки свободных клеток, для которых ui + vj > cij
(1;6): 0 + 3 > 2; ∆16 = 0 + 3 - 2 = 1
(3;6): 3 + 3 > 4; ∆36 = 3 + 3 - 4 = 2
(4;2): 8 + 1 > 7; ∆42 = 8 + 1 - 7 = 2
(4;4): 8 + 8 > 15; ∆44 = 8 + 8 - 15 = 1
(4;6): 8 + 3 > 5; ∆46 = 8 + 3 - 5 = 6
(4;7): 8 + 9 > 15; ∆47 = 8 + 9 - 15 = 2
(5;7): -3 + 9 > 4; ∆57 = -3 + 9 - 4 = 2
(6;4): -2 + 8 > 3; ∆64 = -2 + 8 - 3 = 3
(6;7): -2 + 9 > 3; ∆67 = -2 + 9 - 3 = 4
max(1,2,2,1,6,2,2,3,4) = 6
Выбираем максимальную оценку свободной клетки (4;6): 5
Для этого в перспективную клетку (4;6) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-».
Цикл приведен в таблице (4,6 → 4,3 → 1,3 → 1,2 → 3,2 → 3,7 → 2,7 → 2,6).
Таблица 13. Перераспределение по циклу.
Из грузов хij стоящих в минусовых клетках, выбираем наименьшее, т.е. у = min (2, 6) = 27. Прибавляем 27 к объемам грузов, стоящих в плюсовых клетках и вычитаем 27 из Хij, стоящих в минусовых клетках. В результате получим новый опорный план.
Таблица 14. Опорный план №5
Проверим оптимальность опорного плана. Найдем предварительные потенциалы ui, vj. по занятым клеткам таблицы, в которых ui + vj = cij, полагая, что u1 = 0.
u1 + v1 = 5; 0 + v1 = 5; v1 = 5
u6 + v1 = 3; 5 + u6 = 3; u6 = -2
u6 + v8 = 2; -2 + v8 = 2; v8 = 4
u5 + v8 = 1; 4 + u5 = 1; u5 = -3
u5 + v5 = 1; -3 + v5 = 1; v5 = 4
u1 + v2 = 1; 0 + v2 = 1; v2 = 1
u3 + v2 = 4; 1 + u3 = 4; u3 = 3
u3 + v7 = 12; 3 + v7 = 12; v7 = 9
u2 + v7 = 7; 9 + u2 = 7; u2 = -2
u2 + v4 = 6; -2 + v4 = 6; v4 = 8
u1 + v3 = 7; 0 + v3 = 7; v3 = 7
u4 + v3 = 15; 7 + u4 = 15; u4 = 8
u4 + v6 = 5; 8 + v6 = 5; v6 = -3
Опорный план не является оптимальным, так как существуют оценки свободных клеток, для которых ui + vj > cij
(4;2): 8 + 1 > 7; ∆42 = 8 + 1 - 7 = 2
(4;4): 8 + 8 > 15; ∆44 = 8 + 8 - 15 = 1
(4;7): 8 + 9 > 15; ∆47 = 8 + 9 - 15 = 2
(5;7): -3 + 9 > 4; ∆57 = -3 + 9 - 4 = 2
(6;4): -2 + 8 > 3; ∆64 = -2 + 8 - 3 = 3
(6;7): -2 + 9 > 3; ∆67 = -2 + 9 - 3 = 4
max(2,1,2,2,3,4) = 4
Выбираем максимальную оценку свободной клетки (6;7): 3
Для этого в перспективную клетку (6;7) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-».
Цикл приведен в таблице (6,7 → 6,1 → 1,1 → 1,2 → 3,2 → 3,7).
Таблица 15. Перераспределение по циклу
Из грузов хij стоящих в минусовых клетках, выбираем наименьшее, т.е. у = min (1, 2) = 54. Прибавляем 54 к объемам грузов, стоящих в плюсовых клетках и вычитаем 54 из Хij, стоящих в минусовых клетках. В результате получим новый опорный план.
Таблица 16. Опорный план №6
Проверим оптимальность опорного плана. Найдем предварительные потенциалы ui, vj. по занятым клеткам таблицы, в которых ui + vj = cij, полагая, что u1 = 0.
u1 + v1 = 5; 0 + v1 = 5; v1 = 5
u6 + v1 = 3; 5 + u6 = 3; u6 = -2
u6 + v7 = 3; -2 + v7 = 3; v7 = 5
u2 + v7 = 7; 5 + u2 = 7; u2 = 2
u2 + v4 = 6; 2 + v4 = 6; v4 = 4
u3 + v7 = 12; 5 + u3 = 12; u3 = 7
u3 + v2 = 4; 7 + v2 = 4; v2 = -3
u6 + v8 = 2; -2 + v8 = 2; v8 = 4
u5 + v8 = 1; 4 + u5 = 1; u5 = -3
u5 + v5 = 1; -3 + v5 = 1; v5 = 4
u1 + v3 = 7; 0 + v3 = 7; v3 = 7
u4 + v3 = 15; 7 + u4 = 15; u4 = 8
u4 + v6 = 5; 8 + v6 = 5; v6 = -3
Опорный план не является оптимальным, так как существуют оценки свободных клеток, для которых ui + vj > cij
(2;1): 2 + 5 > 5; ∆21 = 2 + 5 - 5 = 2
(2;3): 2 + 7 > 8; ∆23 = 2 + 7 - 8 = 1
(2;5): 2 + 4 > 3; ∆25 = 2 + 4 - 3 = 3
(2;8): 2 + 4 > 3; ∆28 = 2 + 4 - 3 = 3
(3;8): 7 + 4 > 10; ∆38 = 7 + 4 - 10 = 1
max(2,1,3,3,1) = 3
Выбираем максимальную оценку свободной клетки (2;5): 3
Для этого в перспективную клетку (2;5) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-».
Цикл приведен в таблице (2,5 → 2,7 → 6,7 → 6,8 → 5,8 → 5,5).
Таблица 17. Перераспределение по циклу
Из грузов хij стоящих в минусовых клетках, выбираем наименьшее, т.е. у = min (6, 8) = 27. Прибавляем 27 к объемам грузов, стоящих в плюсовых клетках и вычитаем 27 из Хij, стоящих в минусовых клетках. В результате получим новый опорный план.
Таблица 18. Опорный план №7
Проверим оптимальность опорного плана. Найдем предварительные потенциалы ui, vj. по занятым клеткам таблицы, в которых ui + vj = cij, полагая, что u1 = 0.
u1 + v1 = 5; 0 + v1 = 5; v1 = 5
u6 + v1 = 3; 5 + u6 = 3; u6 = -2
u6 + v7 = 3; -2 + v7 = 3; v7 = 5
u2 + v7 = 7; 5 + u2 = 7; u2 = 2
u2 + v4 = 6; 2 + v4 = 6; v4 = 4
u2 + v5 = 3; 2 + v5 = 3; v5 = 1
u5 + v5 = 1; 1 + u5 = 1; u5 = 0
u5 + v8 = 1; 0 + v8 = 1; v8 = 1
u3 + v7 = 12; 5 + u3 = 12; u3 = 7
u3 + v2 = 4; 7 + v2 = 4; v2 = -3
u1 + v3 = 7; 0 + v3 = 7; v3 = 7
u4 + v3 = 15; 7 + u4 = 15; u4 = 8
u4 + v6 = 5; 8 + v6 = 5; v6 = -3
Опорный план не является оптимальным, так как существуют оценки свободных клеток, для которых ui + vj > cij
(2;1): 2 + 5 > 5; ∆21 = 2 + 5 - 5 = 2
(2;3): 2 + 7 > 8; ∆23 = 2 + 7 - 8 = 1
(5;7): 0 + 5 > 4; ∆57 = 0 + 5 - 4 = 1
max(2,1,1) = 2
Выбираем максимальную оценку свободной клетки (2;1): 5
Для этого в перспективную клетку (2;1) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-».
Цикл приведен в таблице (2,1 → 2,7 → 6,7 → 6,1).
Таблица 19. Перераспределение по циклу
Из грузов хij стоящих в минусовых клетках, выбираем наименьшее, т.е. у = min (6, 1) = 0. Прибавляем 0 к объемам грузов, стоящих в плюсовых клетках и вычитаем 0 из Хij, стоящих в минусовых клетках. В результате получим новый опорный план.
Таблица 20. Опорный план №8
Проверим оптимальность опорного плана. Найдем предварительные потенциалы ui, vj. по занятым клеткам таблицы, в которых ui + vj = cij, полагая, что u1 = 0.
u1 + v1 = 5; 0 + v1 = 5; v1 = 5
u2 + v1 = 5; 5 + u2 = 5; u2 = 0
u2 + v4 = 6; 0 + v4 = 6; v4 = 6
u2 + v5 = 3; 0 + v5 = 3; v5 = 3
u5 + v5 = 1; 3 + u5 = 1; u5 = -2
u5 + v8 = 1; -2 + v8 = 1; v8 = 3
u2 + v7 = 7; 0 + v7 = 7; v7 = 7
u3 + v7 = 12; 7 + u3 = 12; u3 = 5
u3 + v2 = 4; 5 + v2 = 4; v2 = -1
u6 + v7 = 3; 7 + u6 = 3; u6 = -4
u1 + v3 = 7; 0 + v3 = 7; v3 = 7
u4 + v3 = 15; 7 + u4 = 15; u4 = 8
u4 + v6 = 5; 8 + v6 = 5; v6 = -3
Опорный план не является оптимальным, так как существуют оценки свободных клеток, для которых ui + vj > cij
(5;7): -2 + 7 > 4; ∆57 = -2 + 7 - 4 = 1
Выбираем максимальную оценку свободной клетки (5;7): 4
Для этого в перспективную клетку (5;7) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-».
Цикл приведен в таблице (5,7 → 5,5 → 2,5 → 2,7).
Таблица 21. Перераспределение по циклу
Из грузов хij стоящих в минусовых клетках, выбираем наименьшее, т.е. у = min (2, 7) = 54. Прибавляем 54 к объемам грузов, стоящих в плюсовых клетках и вычитаем 54 из Хij, стоящих в минусовых клетках. В результате получим новый опорный план.
Таблица 22. Опорный план №9
Проверим оптимальность опорного плана. Найдем предварительные потенциалы ui, vj. по занятым клеткам таблицы, в которых ui + vj = cij, полагая, что u1 = 0.
u1 + v1 = 5; 0 + v1 = 5; v1 = 5
u2 + v1 = 5; 5 + u2 = 5; u2 = 0
u2 + v4 = 6; 0 + v4 = 6; v4 = 6
u2 + v5 = 3; 0 + v5 = 3; v5 = 3
u5 + v5 = 1; 3 + u5 = 1; u5 = -2
u5 + v7 = 4; -2 + v7 = 4; v7 = 6
u3 + v7 = 12; 6 + u3 = 12; u3 = 6
u3 + v2 = 4; 6 + v2 = 4; v2 = -2
u6 + v7 = 3; 6 + u6 = 3; u6 = -3
u5 + v8 = 1; -2 + v8 = 1; v8 = 3
u1 + v3 = 7; 0 + v3 = 7; v3 = 7
u4 + v3 = 15; 7 + u4 = 15; u4 = 8
u4 + v6 = 5; 8 + v6 = 5; v6 = -3
Опорный план является оптимальным, так все оценки свободных клеток удовлетворяют условию ui + vj ≤ cij.
Значение целевой функции:
F(x) = 5*261 + 7*54 + 6*27 + 3*81 + 4*108 + 15*72 + 5*27 + 1*81 + 4*54 + 1*54 + 3*81 = 4329 т/км
2.4 Определение маршрутов методом совмещенных планов.
Составляем оптимальный план возврата порожняка под погрузку:
Таблица 23. Оптимальный план возврата порожняка
Составляем матрицу совмещенных планов. Выделим отдельным цветом добавленные в матрицу совмещенные планы:
Таблица 24. Матрица совмещенных планов
Строим маршруты движения автомобилей непосредственно на матрице совмещенных планов. Вначале выбираем маятниковые маршруты, после кольцевые.
Маятниковые маршруты определяются клетками с двойной нагрузкой, при этом выбираем наименьшее из значений (в тоннах). В нашем случае клеток с двойной нагрузкой две:
Таблица 25. Выбор маятниковых маршрутов
Итак, маятниковые маршруты:
1) А1-Б1-А1, на котором необходимо развезти 126 тонн;
2) А4-Б3-А4, на котором необходимо развезти 72 тонны.
Удаляем из матрицы клетки с двойной загрузкой и составляем кольцевые маршруты:
Кольцевые маршруты составляем по следующему принципу: все нечетные вершины должны лежать в «груженых» клетках, а четные – в клетках с порожняком. Для удобства будем отмечать каждый четырехзвенный маршрут отдельным цветом.
1) Кольцевой маршрут А2-Б2-А3-Б5-А2 на 81 тонну. Исключаем данный маршрут и ищем новые маршруты.
Таблица 26. Четырехзвенный кольцевой маршрут
2) Кольцевой маршрут А5-Б3-А1-Б8-А5 на 54 тонны. Исключаем данный четырехзвенный маршрут и ищем новые маршруты.
Таблица 27. Четырехзвенный кольцевой маршрут
3) Кольцевой маршрут А5-Б1-А1-Б7-А5 на 54 тонны. Удаляем его из рассмотрения.
Таблица 28. Четырехзвенный кольцевой маршрут
Поиск четырехзвенных маршрутов завершен. Осуществляем поиск шестизвенных маршрутов:
4) Маршрут А5-Б1-А1-Б7-А6-Б5-А5 на 54 тонны. Исключаем его из рассмотрения:
Таблица 29. Шестизвенный кольцевой маршрут
| Б1 | Б2 | Б3 | Б4 | Б5 | Б6 | Б7 | |
| А1 | 5 (81) | 14 81 | |||||
| А2 | 13 27 | 6 (27) | |||||
| А3 | 4 (27) | 11 27 | |||||
| А4 | 15 27 | 5 (27) | |||||
| А5 | 9 81 | 1 (81) | |||||
| А6 | 8 54 | 10 27 | 3 (81) |
Имеем следующую матрицу.
Таблица 30. Заключительный поиск кольцевых маршрутов
Осталось развести 6 точек по 27 тонн в каждую, а также осталось 6 клеток с 27 тоннами порожняка. В данном случае остался единственный замкнутый маршрут из 12 звеньев, который полностью удовлетворит запросы всех потребителей в грузах.
Маршрут выглядит следующим образом:
Таблица 31. 12-звенный кольцевой маршрут
| Б1 | Б2 | Б3 | Б4 | Б5 | Б6 | Б7 | Б8 | |
| А1 | 5 (27) | 14 27 | ||||||
| А2 | 13 27 | 6 (27) | ||||||
| А3 | 4 (27) | 11 27 | ||||||
| А4 | 15 27 | 5 (27) | ||||||
| А5 | 9 27 | 1 (27) | ||||||
| А6 | 10 27 | 3 (27) |
А5-Б1-А1-Б7-А6-Б6-А4-Б4-А2-Б2-А3-Б5-А5 на 27 тонн.
Проверяем, весь ли груз таким образом будет доставлен по