Применение транспортной задачи для повышения эффектив¬ности работы транспортного комплекса (ржд)

Перевозка на фиктивную станцию назначения означает количество груза, которое необходимо отложить в запас на соответствующей станции отправления, а перевозка с фиктивной станции отправления – количество груза, которое следует недодать соответствующей станции назначения.Пример решения транспортной задачи по методу потенциалов изложен в пункте 2.3. данной курсовой работы.2.2 Составление плана перегона порожних вагонов решением транспортной задачиРешим классическую транспортную задачу, на примере организации работы железнодорожного транспорта. Пусть мы имеем на трехстанциях избыток порожних вагонов в размере соответственно 110, 130, 220 вагонов. Необходимо распределить данные вагоны по четырем станциям с недостатком порожняка (соответственно 80, 170, 110, 100, вагонов). Расстояние между каждой станцией отправления (избытка вагонов) и каждой станцией назначения (недостатка порожняка) представлено в виде матрицы (табл.5). Необходимо составить план распределения вагонов между указанными станциями с минимальным суммарным пробегом порожних вагонов. Таблица 5 – Исходные данныеСтанция отправленияСтанция назначенияН1Н2Н3Н4С115X1110X1245X1330X14С240X2135X2220X2335 Х24С325X3115X329X3315X34Разработка плана перевозок означает, что необходимо указать, сколько порожних вагонов каждая станция отправления должна отправить в адрес каждой станции назначения.Сначала проверим сбалансированность (закрытость) задачи.Это задача закрытого типа, так как суммарное количество избыточных порожних вагонов равно суммарному количеству требующихся вагонов.При построении математической модели поставленной задачи, неизвестными будут считаться количество вагонов.Пусть хij – количество вагоновот i-йстанции отправлениянаj-юстанцию назначения. Целевая функция, это суммарный пробег порожних вагонов:где lij – расстояние перевозки одного вагона от i-й станции отправления на j-ю станцию назначения. Неизвестные в этой задаче должны удовлетворять следующим ограничениям:• Объемы перевозок не могут быть отрицательными, т. е. хij ≥0;• Поскольку модель сбалансирована, то весь порожнякдолжен быть вывезен состанций отправления, а потребности всех пунктов потребления должны быть полностью удовлетворены, т. е. где ai – ресурсы i-ой станции отправления;bj – потребность j-ой станции назначенияИтак, имеем следующую задачу линейного программирования, найти минимум функции: Иначе L=15Х11+10Х12+45Х13+30Х14+40Х21+35Х22+20Х23+35Х24+25Х31++15Х32+9Х33+15Х34 → minОграничения:Количество вагонов, расположенныхна каждой станции отправления должен быть вывезено в полном объеме.Х11+ Х12 + Х13 + Х14  = 110Х21+ Х22 + Х23 + Х24 = 130Х31 + Х32+ Х33 + Х34 = 2202) Потребности каждого пункта назначения должны быть удовлетворены в полном объеме.Х11 + Х21 + Х31  = 80Х12 + Х22 + Х32  = 170Х13 + Х23+ Х33  = 110Х14 + Х24+ Х34  = 100Xij≥0, (i=1, 2, 3; j=1, 2, 3, 4)Для решения задачи необходимо построить исходный опорный план перевозок, который в дальнейшем будет подвергаться корректировке.2.2.1Методы построения исходного опорного плана перевозокИсходный опорный план перевозок может быть построен различными методами. В данном курсовом проекте приводятся наиболее распространенные из них.Метод северо-западного углаМетод северо-западного угла (диагональный). Построение начального опорного плана начинается с левой верхней клетки (называемой северо-западным углом) матрицы и продолжается, двигаясь далее вправо по строке и вниз по столбцу.В вверху каждой ячейки матрицы располагаются данные об объемах перевозок, в правом нижнем углу – расстояние перевозки.Порядок решения следующий.В первую клетку помещают: х11 = min(80;110) = 80. Спрос первой станции назначения полностью удовлетворен, первый столбец вычеркивают. Остаток свободных вагонов в первом пункте составляет: 110 – 80=30 ед. Двигаемся по первой строке вправо х21 =min(110 – 80;170) = 30.Предложение первой станции отправления исчерпано, первая строка вычеркивается. Второму потребителю не хватает 170 – 30 =140 ед. Двигаемся по второму столбцу вниз х22 = min(130;140) = 130 ед.Предложение второй станции отправления исчерпано, вторая строка вычеркивается.Второму потребителю не хватает 140 – 130 =10 ед.Двигаемся по второму столбцу вниз х32 = min(220;10) = 10 ед. Второй столбец вычеркивается. Предложение третьей станции отправления составляет 220 – 10 = 210 ед.Двигаемся по третьей строке вправо х33 = min(210;110) = 110. Третий столбец вычеркивается, так как потребности третьей станции назначения полностью удовлетворены. Предложение третьей станции отправления составляет 210 – 110 = 100 ед.Двигаемся по третьей строке вправо x34 = min(100,100) = 100. Таблица заполнена. Число базисных переменных задачи 3+4 – 1=6. Таблица 6 –Исходный опорный план, построенный методом северо-западного углаСТАНЦИИ ОТПРАВЛЕНИЯСТАНЦИИ НАЗНАЧЕНИЯвозможностьН1Н2Н3Н4С18030  110 15 10 45 30С2 130  130 40 35 20 35С3 10110100220 25 15 9 15потребность 080140110100 Значение целевой функции составит L = 15·80 + 10·30 + 35·130 + 15·10 + 9·110 + 15·100 = 8690 ваг-км •Метод минимального элементаПостроение начального опорного плана начинается с клетки, имеющей минимальное расстояние перевозки в таблице. Эта клетка исключается из дальнейшего рассмотрения матрицы, потом заполняется клетка с очередным минимальным элементом и т.д. (табл. 7). Порядок решения задачи.Минимальноерасстояние перевозкиl33 = 9, x33= min(110,220) = 110 ед. Первый столбец вычеркивают, остаток свободных вагонов на третьей станции назначения 220 – 110 = 110 ед.Минимальноерасстояние для оставшихся клеток l12 = 10, x12 = min(110,170) = 110 ед. Первую строку вычеркивают, свободных вагонов больше на этой станции нет. Неудовлетворенная потребность второй станции назначения составляет 170 – 110 = 60 ед.Для оставшихся клеток минимальноерасстояние:l32= 15, x32 = min(110,60) = 60 ед.Второй столбец вычеркивают, остаток свободных вагонов на третьей станции назначения 110 – 60 = 50 ед.Для оставшихся клеток минимальноерасстояние:l33 = 15, x33 = min(50,100) = 50 ед.Третью строку вычеркивают, лимит третьей станции отправления исчерпан.Для оставшихся клеток минимальноерасстояние:l23 = 35, x23 = min(130,50) = 50 ед.Третий столбец вычеркивают.Для одной оставшейся клетки х21= min(80,80) = 80.Таблица 7 –Исходный опорный план, построенный методом минимального элементаСТАНЦИИ ОТПРАВЛЕНИЯСТАНЦИИ НАЗНАЧЕНИЯвозможностьН1Н2Н3Н4С1110  110 15 10 45 30С2 80 50 130 40 35 20 35С3 6011050220 25 15 9 15потребность 80140110100 Значение целевой функции составит L = 40·80 + 10·110 + 15·60 + 9·110 + 15·50 + 35·50 = 8690 ваг-кмМетод аппроксимации ФогеляОдин из, чаще всего применяющихся на практике, методов формирования опорного плана в транспортной задаче– метод аппроксимации Фогеля. Последовательность действий при его использовании совершенно иная, чем при заполнении транспортной таблицы методом «Северо-Западного угла» или методом «Минимального элемента». Метод достаточно прост и позволяет получить опорный план максимально приближенный к оптимальному решению, чем в случае применения вышеназванных методов. Сущность аппроксимации Фогеля в нахождении разности (по модулю) между парой минимальных тарифов (в нашем случае – расстояний) в каждой строке и столбце. Затем строка или столбец с наибольшей разностью заполняются в направлении от клетки с минимальным тарифом (расстоянием) к клетке с максимальным. Первое, что необходимо сделать в рамках данного метода, придать немного другой вид таблице с опорным планом, то естьдобавить к исходной таблице дополнительные строку и столбец (табл. 8)Затем для каждой строки и каждого столбца находим абсолютные разности (по модулю) между двумя минимальными тарифами. Найденные разности выписываем в соответствующие строку и столбец.Например, по первой строке минимальные расстояния это l11=15 и l12=10∆i = 10 – 15 = 5Заносим полученное значение в соответствующую ячейку.Среди вычисленных разностей выбираем наибольшую (нашем случае две максимальных разницы, выберем ту, что соответствует загрузке ячейки с минимальным значением расстояния).Таблица 8 –ИсходнаятаблицаСТАНЦИИ ОТПРАВЛЕНИЯСТАНЦИИ НАЗНАЧЕНИЯвозможность∆iН1Н2Н3Н4С1  1105 15 10 45 30С2 13015 40 35 20 35С3 1002206 25 15 9 15потребность 80140110100 ∆j1051115Затем повторяем все вышеописанные действия снова, только уже не учитывая заполненные клетки с минимальным расстоянием. И так до тех пор, пока не будет полностью найден опорный план по данному методуТаблица 9 – Ход решенияСТАНЦИИ ОТПРАВЛЕНИЯСТАНЦИИ НАЗНАЧЕНИЯвозможность∆iН1Н2Н3Н4С1  1105 15 10 45 30С2 11013015 40 35 20 35С3 1001206 25 15 9 15потребность 80140110 ∆j10511ХТаблица 10 – Ход решенияСТАНЦИИ ОТПРАВЛЕНИЯСТАНЦИИ НАЗНАЧЕНИЯвозможность∆iН1Н2Н3Н4С180  1105 15 10 45 30С2 110205 40 35 20 35С3 1001206 25 15 9 15потребность 8014000 ∆j105ХХТаблица 11 – Ход решенияСТАНЦИИ ОТПРАВЛЕНИЯСТАНЦИИ НАЗНАЧЕНИЯвозможность∆iН1Н2Н3Н4С18030  3020 15 10 45 30С2 110205 40 35 20 35С3 1001206 25 15 9 15потребность 014000 ∆jХ5ХХТаблица 12 – Ход решенияСТАНЦИИ ОТПРАВЛЕНИЯСТАНЦИИ НАЗНАЧЕНИЯвозможность∆iН1Н2Н3Н4С18030  0Х 15 10 45 30С2 110205 40 35 20 35С3 1201001206 25 15 9 15потребность 014000 ∆jХ5ХХТаблица 13 – Опорный план, построенный по методу аппроксимации ФогеляСТАНЦИИ ОТПРАВЛЕНИЯСТАНЦИИ НАЗНАЧЕНИЯвозможность∆iН1Н2Н3Н4С18030  0Х 15 10 45 30С220 110205 40 35 20 35С3 1201000Х 25 15 9 15потребность 02000 ∆jХ5ХХЗначение целевой функции составит L = 15·80 + 10·30 + 35·20 + 15·120 + 20·110 + 15·100 = 7700 ваг-км2.2.3Оптимизация опорного решения методом потенциаловПрежде чем приступить к процессу оптимизации опорного решения методом потенциалов, следует проверить выбранный (по критерию минимума затрат) опорный план наневырожденность.Согласно теореме Данцига количество занятых клеток (Кз) в оптимальном плане не должно превышать суммарного числа строк и столбцов (суммы количества пунктов отправления и назначения): Кз ≤ m + n – 1 ,(24)где m – число строк матрицы (пунктов отправления); n – число столбцов (пунктов назначения). ЕслиК з = m + n – 1, задача решается обычным порядком. ЕслиК з < m + n – 1, задача называется "вырожденной" и распадается на несколько самостоятельных задач. Чтобы этого избежать, назначаются дополнительные фиктивные перевозки (перевозки равные 0). В нашем примере условие "вырождения" выполняется во всех случаях: Кз = 3 + 4 – 1 = 6После проверки опорного плана на «вырождение», приступают к процессу его оптимизации методом потенциалов.Суть данного метода в следующем: каждой станции отправления поставим в соответствие некоторый потенциал Ui, а каждой станции назначения – потенциал Vj.Присвоим любому потенциалу произвольное значение, например U1=0. Остальные потенциалы легко определяются из условия, что для любой занятой клетки:Ui + Vj=Zij(25)То есть, через занятые клетки определяются потенциалы столбцов, связанных с первой строкой по формуле Vj = Zij – Ui(26)где Zij– критерий расстояния (или другой показатель критерия оптимизации) в заданной клетке. Через занятые клетки определяются потенциалы строк, связанных со столбцами, получившими потенциал, по формуле Ui = Zij –Vj(27)Эти действия повторяются до тех пор, пока все столбцы и строки не получат потенциал. Это всегда возможно, если выполняется условие "вырождения".Для каждой свободной клетки вычислим псевдостоимость:Pij=Ui + Vj(28)и разность между стоимостью и псевдостоимостью:Δij=Zij – Pij(29)Запишем разность в левых нижних уголках свободных клеток. Запишем псевдостоимость в левых нижних уголках свободных клеток, а разность в кружках. Сравнивая эти разности с результатами, полученными в предыдущем разделе, убеждаемся, что эти разности характеризуют оценки соответствующих циклов.Для клетки с наибольшей по модулю отрицательной разностью составляется единственный цикл, по которому и производится перестановка.Перестановки могут осуществляться и сразу по нескольким циклам, но только в том случае, если они охватывают разные клетки.По циклам, как и ранее, переставляется минимальное количество грузов, стоящее в отрицательных клетках.Процедура повторяется до тех пор, пока есть отрицательные циклы.Порядок решения задачи согласно формулам 25 – 29 выглядит следующим образом: Задаём любой из потенциаловравным нулю, например U1= 0(1,1) U1 + V1 =15(1,2) U1 + V2 =10(2,2) U2 + V2 =35(2,3) U2 + V3 =20(3,2) U3 + V2 =15(3,4) U3 + V4 =15V1 =15, V2 =10, U2 =25, U3 =5, V3 =-5, V4 =10Проверим условие оптимальности для свободных клеток Δij=Zij – Pij = Zij – (Ui + Vj)(1,3) Δ13 = 45 – (0 – 5) = 50(1,4) Δ14 = 30 – (0 + 10) = 20(2,1) Δ21 = 40 – (25 + 15) = 0(2,4) Δ24 = 35 – (25 + 10) = 0(3,1) Δ31 = 25 – (5 + 15) = 5(3,2) Δ32 = 9 – (5 – 5) = 9Таблица 14 -План перевозок порожних вагонов (начальный) СТАНЦИИ ОТПРАВЛЕНИЯСТАНЦИИ НАЗНАЧЕНИЯUiН1Н2Н3Н4С18030  0 15 10 5045 2030С220 110250 40 35 20 35С3 1201005 525 15 99 15Vj1510-510 Отсутствуют клетки с отрицательными значениями, следовательно это оптимальный план. Так как план, полученный с помощью аппроксимации Фогеля является оптимальным, поэтому для демонстрации возможностей метода потенциалов «просчитаем» по данному методу опорный план, полученный с помощью метода северо-западного угла.Таблица 15 - План перевозок порожних вагонов (начальный), полученный с помощью метода северо-западного углаСТАНЦИИ ОТПРАВЛЕНИЯСТАНЦИИ НАЗНАЧЕНИЯUiН1Н2Н3Н4С18030  0 15 10 3945 2030С2 130  25 040 35 -920 035С3 101101005 525 15 9 15Vj1510410 Для клетки с наибольшей по модулю отрицательной разностью (С2Н3) составляется единственный цикл, по которому и производится перестановка.Строим цикл, начинающийся и заканчивающийся в этой клетке. Вершинами цикла являются клетки: С2Н3–С3Н3–С3Н2 – С2Н2 (на первом месте стоит номер строки, на втором – столбца). В клетке (С2Н3) ставим "+", в клетке (С3Н3) "-", в клетке (С3Н2) "+", в клетке (С2Н2) "-". Перераспределяем продукцию по циклу. Минимальное значение для клеток со знакам "-" находится в клетке (С3Н3) ХС3Н3= 110. Отнимаем 110 от значений, стоящих в клетках со знаком "-", и прибавляем к значениям, стоящим в клетках со знаком "+". Получаем новый план перевозок, представленный в следующей транспортной таблице.Таблица 16 – Определение разности. Построение циклаСТАНЦИИ ОТПРАВЛЕНИЯСТАНЦИИ НАЗНАЧЕНИЯUiН1Н2Н3Н4С18030  0 15 10 3945 2030С2 130-110 +110 25 040 35 -920 035С3 10+110110-1101005 525 15 9 15Vj1510410 Таблица 17 – План перевозок по методу потенциалов.СТАНЦИИ ОТПРАВЛЕНИЯСТАНЦИИ НАЗНАЧЕНИЯUiН1Н2Н3Н4С18030  0 15 10 4045 30С220 110250 40 35 20 35С3 1201005 525 15 99 15Vj1510-510 Значение целевой функции составит L = 15·80 + 10·30 + 35·20 + 15·120 + 20·110 + 15·100 = 7700 ваг-км2.2.4Решениетранспортной задачи на компьютере, в ПП ExcelВ условиях стремительно развивающихся информационных технологий, можно и нужно автоматизировать существующие модели решения основных логистических задач. Так и для транспортной задачи,возможно, найти решение средствами MSExcel.Порядок решения следующий:В ячейки B3:Е5выставляется стоимость перевозок единицы груза.В ячейках B14:Е14 укажем формулы для расчета суммарной потребности продукции для j-го пункта (например, для ячейки B14=СУММ(B11:B13)), в ячейках F11:F13 – формулы суммарного объема производства i-го предприятия (например, для ячейки F11.=СУММ(B11:E11)).В ячейки B15:E15 заносим значения месячного объема производства продукции соответствующего пункта потребления, в ячейки G11:G13 заносим значения объема соответствующего пункта потребления.В ячейку B18будет занесена формула целевой функции =СУММПРОИЗВ(B3:E5;B11:E14)Рис.4. Исходный формат решения Выполним команду Поиск решения. В полеУстановить целевую ячейку указываем ячейку, содержащую оптимизируемое значение. Установим переключатель Равный в положение минимальному значению.В полеИзменяя ячейки мышью зададим диапазон подбираемых параметров $B$11:$E$13.В поле Ограничения введем необходимые ограничения и нажмем на кнопкуДобавить, затем Выполнить. Рис.5. Выполнение команды «Поиск решения»В результате получится оптимальный набор переменных при данных ограничениях:Рис.6. Оптимальный планЗначение целевой функции соответствует полученному расчетным способом. ЗАКЛЮЧЕНИЕДанный курсовой проект был выполнен на тему: «Применение транспортной задачи для повышения эффективности работы транспортного комплекса». Таким образом, целью данного курсовогопроекта было провести анализ современного состояния теории решения транспортной задачи и найти практическое применение транспортной задачи для повышения эффективности работы транспортного комплекса.В рамках данного курсового проекта была проанализирована деятельность одной из крупных логистических компаний на рынке железнодорожных перевозок – АО «РЖД Логистика».Глава первая – проанализирована деятельность одной из крупных логистических компаний на рынке железнодорожных перевозок – АО «РЖД Логистика», даны определения показателей эффективности работы железнодорожного транспорта, рассмотрено влияние одного из показателей (пробег порожних вагонов) на эффективность работы подвижного состава железнодорожного транспорта.Глава вторая – расчетно-технологическая. В ней приводится обзор некоторых моделей линейного программирования, и пример решения классической транспортной задачи – распределение порожних вагонов по станциям назначения. Задача решена аналитическим способом и с помощью средств ПП Excel. Значение целевой функции, полученной посредством решения задачи в Excel, соответствует значению рассчитанному вручную.В результате проведенных вычислений расчетные величины вагонокилометров составят:Метод северо-западного углаL = 15·80 + 10·30 + 35·130 + 15·10 + 9·110 + 15·100 = 8690 ваг-кмМетод наименьшего элементаL = 40·80 + 10·110 + 15·60 + 9·110 + 15·50 + 35·50 = 8690 ваг-кмМетод ФогеляL = 15·80 + 10·30 + 35·20 + 15·120 + 20·110 + 15·100 = 7700 ваг-кмМетод потенциаловL = 15·80 + 10·30 + 35·20 + 15·120 + 20·110 + 15·100 = 7700 ваг-кмТаким образом, построение плана вывоза порожних вагонов, выполненного с помощью транспортной задачи позволяет определить оптимальную величину транспортной работы (вагоно-км.)СПИСОК ЛИТЕРАТУРЫБродецкий Г. Л. Моделирование логистических систем. Оптимальные решения в условиях риска. – М.: Вершина, 2006. – 376 с.Гаджинский А. М. Логистика: Учебник. – М.: Дашков и К˚, 2004. – 432 с.Горев А. Э. Грузовые автомобильные перевозки: Учеб.пособие. – М.: Академия, 2004. – 288 с.Гольштейн Е.Г.ЮдинД.Б. Задачи линейного программирования транспортного типа, Изд-во Наука, Москва, 1969, –383 стр.Котиков Ю. Г. Основы системного анализа транспортных систем: Учеб.пособие. – СПб.: Изд-во СПбГАСУ, 2001. – 264 с.Логистика: управление в грузовых транспортно-логистических системах: Учеб. пособие / Под ред. Л. Б. Миротина. – М.: Юристъ, 2002. – 414 с.Логистические транспортно-грузовые системы: Учебник / В. А.Апатцев, С. Б. Левин, В. М. Николашин и др.; Под ред. В. М. Николашина. – М.: Академия, 2003. – 304 с.Ляско В. И. Стратегическое планирование развития автотранспортных предприятий. – М.: Благовест-В, 2003. – 200 с.Николайчук В. Е. Транспортно-складская логистика: Учеб. пособие. –М.: Дашков и К˚, 2006. – 452 с.Сервис на транспорте: Учеб.пособие / В. М. Николашин, Н. А. Зудилин, А. С. Синицына и др.; Под ред. В. М. Николашина. – М.: Академия, 2004. – 272 с.Транспортная логистика: Учебник / Под общ.ред. Л. Б. Миротина. – 2-е изд. – М.: Экзамен, 2005. – 512 с.http://www.loglink.ru– портал по логистике и транспорту.http://logist.ru– Российский клуб логистов.