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

Содержание

• 1. Постановка задачи оптимального распределения перевозок
• 2. Выбор и определение показателей оптимальности для решения задачи
• 2.1 Автомобильный транспорт
• 2.2 Железнодорожный транспорт
• 2.3. Речной транспорт
• 3. Порядок решение задачи оптимального распределения
• 3.1. Определение расходов на перевозку I т груза по участкам транспортной сети различными видами транспорта
• 3.2 Определение кратчайших путей доставки груза
• 3.3 Составление матрицы задачи
• 3.4 Составление исходного плана и получение оптимального плана
• 1. Постановка задачи оптимального распределения перевозок
• Большое количество грузов перевозится на сети и в транспортных узлах с участием двух и более видов транспорта в смешанном и прямом смешанном сообщениях. перевозка путь доставка груз
• Одной из задач оптимального взаимодействия транспортных систем различных видов транспорта является задача оптимального распределения ограниченных ресурсов и перевозок между ними.
• Задача оптимального распределения перевозок решается, как правило, для уже существующей сети путей сообщения и в рамках имеющейся провозной способности различных видов транспорта. Поэтому в качестве показателей оптимальности при решении этой задачи могут быть приняты эксплуатационные расходы или тарифы на перевозку грузов.
• Задача оптимального распределения перевозок формулируется и решается по типу двухэтапной транспортной задачи линейного программирования.
• В узле имеется двое поставщиков одинаковой или взаимозаменяемой продукции , трое потребителей этой продукции и пунктов перевалки с одного вида транспорта на другой . Ресурсы поставщика равны , потребность потребителя равна , перерабатывающая способность пункта перевалки равна .
• Задача состоит в том, чтобы распределить перевозки между различными видами транспорта, имеющимися в узле, таким образом, чтобы суммарные затраты на перевозку всего объема необходимого потребителям груза с учетом затрат на перевалку его с одного вида транспорта на другой в пунктах перевалки были бы минимальными. Тогда целевую функцию можно записать в следующем виде:
• , ( 1 )
• где
• - объемы перевозок по связям соответственно поставщик - пункт перевалки, пункт перевалки - потребитель, поставщик - потребитель (одним видом транспорта без перевалки);
• - затраты на перевозку одной тонны груза по соответствующим связям;
• - затраты на перевалку одной тонны груза на - ом пункте перевалки.

Требуется отыскать такие значения

,

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

2. Выбор и определение показателей оптимальности для решения задачи

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

В том и другом случае выражения затрат в общем виде можно записать следующим образом:

, ( 2 )

где - постоянные затраты, отнесенные на перевозку 1 т груза и связанные с содержанием постоянных устройств, начально-конечными операциями, простоем транспортных средств под грузовыми операциями, руб/т; - затраты на перевозку 1 т груза на 1 км, руб/ткм; - расстояние перевозки, км.

2.1 Автомобильный транспорт

Удельные эксплуатационные расходы на перевозку 1 т груза автомобильным транспортом определяются из выражения (3)

, ( 3 )

где - соответственно переменные расходы и дорожная составляющая расходов, приходящаяся на 1 км пробега автомобиля (прил. 1); - номинальная грузоподъемность автомобиля, т; - коэффициент использования грузоподъемности автомобиля при перевозке заданного груза; - коэффициент использования пробега автомобиля (при организации перевозок маятниковыми маршрутами = 0,5); - коэффициент, учитывающий дополнительную заработную плату, начисления и надбавки водителям за классность, = 1,25; - сдельные расценки оплаты труда водителей соответственно за 1 т и 1 ткм, принимаются по прил. 1[3].

Для автомобиля КАМАЗ-5511 q_н = 10 т, = 1, = 0,5;

С учетом коэффициентов индексации (С₁ + С_Д) = 0,18*10,3 = 1,85 руб/км; С₂ = 0,18*19,1 = 3,44 руб/т; С₃ =0,045*12,7 = 0,57 руб/ткм.

С_а^Э = 1,08 L_а + 4,3 руб/т. ( 3.1 )

2.2 Железнодорожный транспорт

Удельные эксплуатационные расходы на перевозку I т груза по магистральной железной дороге определяются из выражения :

С_Ж^Э = Э_НК + Э_ДВ L_Ж + Э_ПУ , (4)

где Э_НК , Э_ДВ , Э_ПУ - расходные ставки соответственно по начально-конечной, движенческой операциям, содержанию постоянных устройств, принимаются по прил. 2 [3]; L_Ж - расстояние перевозки груза по железным дорогам, км.

При перевозке груза в полувагоне с использованием электрической тяги с учетом коэффициентов индексации Э_ДВ = 0,0106*9,4 = 0,1 руб/ткм; Э_НК + Э_ПУ = (0,88 + 0,12)*27 = 27 руб/т. Тогда

С_Ж^Э = 0,1 L_Ж + 27 руб/т. ( 4.1 )

2.3 Речной транспорт

Удельные эксплуатационные расходы на перевозку I т груза речным транспортом определяются из выражения :

1

С_Р^Э = ( Э_ДВ L_Р + Э_НК + Э_ГР),(5)

где - коэффициент загрузки судна; Э_НК , Э_ДВ , Э_ГР - расходные ставки соответственно по начально-конечной, движенческой операциям, при стоянке судов под погрузкой и выгрузкой, принимаются по прил. 3[3]; L_Р - расстояние перевозки груза по речным путям, км.

Для судна типа 1а и коэффициента загрузки = 1 с учетом коэффициентов индексации Э_ДВ = 0,0057*12,3 = 0,07 руб/ткм; Э_НК + Э_ГР = (1,11 + 0,79)*17,4 = 33 руб/т.

С_Р^Э = 0,07L + 33 руб/т( 5.1 )

3. Порядок решение задачи оптимального распределения

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

Расходы на перевозку I т груза различными видами транспорта по участкам транспортной сети определяются по выражениям (3.1, 4.1 и 5.1) путем подстановки в них кратчайшего расстояния между соответствующими пунктами отправления и назначения.

3.2. Определение кратчайших путей доставки груза

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

При определении кратчайшего пути доставки груза между двумя пунктами по сети автомобильных дорог целесообразно использовать метод динамического программирования. Для этого вырисовывается сеть автомобильных дорог между пунктами с учетом всех связей, кроме заведомо проигрышных. Все точки пересечения дорог нумеруются в порядке возрастания от конечного пункта к начальному. Так как динамическое программирование представляет собой метод пошагового принятия оптимального решения, то и процесс поиска кратчайшего расстояния разбивается на несколько шагов. К первому шагу относятся точки, из которых можно попасть в конечную не более чем за один шаг; к точкам i-го шага относят точки, из которых не более чем за один шаг можно попасть в точки (i -1)-го , (i -2)-го и т.д. шагов. На каждом шаге принимается условно-оптимальное решение, которое представляет собой кратчайший путь из данной точки до конечной. Рассмотрим пример определения кратчайшего пути доставки груза и минимальной стоимости доставки I т груза между пунктами R₁ и Р₂ по сети автомобильных дорог методом динамического программирования (рис. 1).

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

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

Рисунок 1 - Пример отыскания кратчайшего расстояния по полигону автодорог между пунктами R₁ и Р₂ методом динамического программирования

I шаг: из 1 и 3 в Р₂; L₁ = 63; L₃ = 16;

II шаг: из Р₃ в 1 и 3; из 5 в 3; L_Р3 = min [(10+63); (20+16)] = 36;

L₅ = 34+16 = 50;

III шаг: из 2 в Р₃ и 3; L₂ = min [(17+36); (10+16)] = 26;

IV шаг: из 4 в 2 и 5; L₄ = min [(11+26); (20+50)] = 37;

V шаг: из П₂ в 1, 2 и 4; из 6 в 4 и 5;

L_P2 = min [(38+63); (14+26); (15+37)] = 40;

L₆ = min [(16+37); (40+50)] = 53;

VI шаг: из Р₁ в 1 и П₂; из 7 в П₂ и 4;

L_P1 = min [(60+63); (35+40)] = 75;

L₇ = min [(12+40); (30+37)] = 52;

VII шаг: из 9 в Р₁, П₂ и 7;L₉ = min [(15+75); (20+40); (18+52)] = 60;

VIII шаг: из 8 в 9, 7, 4 и 6;

L₈ = min [(18+60); (26+52); (35+37); (16+53)] = 69;

IX шаг: из 10 в 9 и 8; L₁₀ = min [(10+60); (12+69); (8+14+69)] = 70;

X шаг: из R₁ в Р₁, 10 и 8;

L_R1 = min [(25+75); (9+70); (50+18+69)] = 79 (км).

Таким образом, кратчайший путь из R₁ в Р₂ проходит через точки 10, 9 и П₂, 2 и 3 , а минимальная стоимость доставки груза из R₁ в Р₂ равна 1,08*79+4,3 = 89,6 руб./ т.

Аналогично определяются минимальные стоимости доставки I т груза от каждого поставщика до каждого потребителя, от каждого пункта перевалки до каждого потребителя, от каждого поставщика до каждого пункта перевалки. Результаты сводятся в табл. 1 - 3, в которых указывается: вид транспорта (буквой), кратчайшее расстояние и минимальная стоимость доставки.

При определении минимальной стоимости доставки I т груза с пунктов перевалки до потребителей должна быть учтена возможность других перевалок в пути следования и стоимость этих перевалок. В этом случае в табл. 3 указываются: вид транспорта до пункта перевалки, пункт перевалки и вид транспорта от пункта перевалки, например при доставке груза от П₁ до Р₃ через пункт перевалки П₂ речным и железнодорожным транспортом: рП₂ж. Стоимость такой доставки указывается в табл. 3, если она меньше стоимости доставки одним видом транспорта.

Таблица 1 - Минимальные стоимости C_{i j} доставки I т груза от поставщиков до потребителей без перевалки в пути

Таблица 2 - Минимальные стоимости C_{i k} доставки I т груза от поставщиков до пунктов перевалки, включая затраты на перевалку S_k

Таблица 3 - Минимальные стоимости C _{k j} доставки I т груза с пунктов перевалки до потребителей

3.3 Составление матрицы задачи

Для решения задачи оптимизации распределения перевозок по типу двухэтапной транспортной задачи линейного программирования составляется матрица (табл. 4) , в которую из задания на курсовую работу заносятся ресурсы поставщиков а _i , потребности потребителей b_j и перерабатывающие способности пунктов перевалки q _k . Для того, чтобы транспортная задача была закрытой, должно выполняться условие

m n

a_i = b_j (6)

i=1 j=1

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

Условием двухэтапности транспортной задачи является :

r n

q_k > b_j(7)

k=1 j=1

Если условие (7) не выполняется, то задача решается как две обыкновенные транспортные задачи.

В качестве показателей оптимальности в правой верхней части клеток матрицы записываются :

в правой верхней части матрицы - C _{i j} из табл. 1;

в левой верхней части матрицы - C _{i k} + S _k из табл. 2;

в правой нижней части матрицы записываются C_kj из табл. 3, если выполняется условие:

C _{i k} + S _k + C _{k j} < C _{i j} (8)

Если же условие (8) не выполняется, в клетке этой части матрицы записывается запрет М.

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

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

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

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

клетка П₁ Р₁: 51,0 + 36,7 > 31,3 ; 53,1 + 36,7 > 52,3 ;

клетка П₁ Р₂: 51,0 + 61,0 > 80,0 ; 53,1 + 61,0 > 101,5 ;

клетка П₁ Р₃: 51,0 + 47,5 > 74 ; 53,1 + 47,5 > 52,3 ;

клетка П₂ Р₁: 50,4 + 42,7 > 31,3 ; 45,1 + 42,7 > 52,3 ;

клетка П₂ Р₂: 50,4 + 38,0 > 80 ; 45,1 + 38,0 < 101,5 ;

клетка П₂ Р₃: 50,4 + 32,0 > 74 ; 45,1 + 32,0 > 52,3 ;

клетка П₃ Р₁: 77,0 + 57 > 31,3 ; 52,5 + 57 > 52,3 ;

клетка П₃ Р₂: 77,0 + 33,0 > 80,0 ; 52,5 + 33 < 101,5 ;

клетка П₃ Р₃ : 77,0 + 0 > 74,0 ; 52,5 + 0 > 52,3 ;

В соответствии с этими системами неравенств в клетки правой нижней части матрицы П₂ Р₂ , П₃ Р₂ нужно записать показатели оптимальности соответственно 38,0 и 33,0 , а в остальные клетки поставить запрет М.

3.4 Составление исходного плана и получение оптимального плана

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

m + n - 1 = 5 + 6 - 1 = 10.

Если таких клеток меньше, то необходимо дополнить их до этого числа 10, поставив в свободные клетки необходимое число “искусственных нулей”. Они ставятся в клетки, стоящие на пересечении строки с последней загруженной клеткой R₂П₃ и столбцов с клетками П₁П₁ и П₂П₂, при записи значений в которые произошло вырождение - были “вычеркнуты” сразу и строка, и столбец. Клетки, содержащие “искусственные нули”, считаются загруженными (x_ij > 0). Исходный план, имеющий 10 загруженных клеток, является базисным . Этот план нужно проверить на выполнение условий оптимальности при решении транспортной задачи методом потенциалов. Как правило, исходный план не является оптимальным. Поэтому необходимо выполнить одну или более итераций ( табл. 4 - 5) , чтобы получить оптимальный план.

Исходный план составляется способом наименьшего показателя оптимальности. Сначала в клетках правой (верхней и нижней) части матрицы отыскивается наименьшее значение показателя оптимальности - c_ij = 31,3. В клету R₁Р₁ заносится максимально возможное значение x_ij = 150. Затем заполняется клетка П₃Р₂, в которой c_kj = 33,0 - в эту клетку записывается x_kj = 110 и т.д. до тех пор, пока не будут удовлетворены потребности всех потребителей. Избыток перерабатывающей способности пунктов перевалки 200, 300 и (400-110) = 290 заносится в клетки фиктивной диагонали (с нулями) левой нижней части матрицы.

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

V_j - U_i = c_ij

для загруженных клеток

(x_ij > 0),

где V_j - потенциал столбца, U_i - потенциал строки.

V_j = U_i + c_ij ; U_i = V_j - c_ij .

Присвоим первой строке с наибольшим показателем оптимальности в загруженной клетке R₁П₃ (c_ik = 77) потенциал V₂ = 0. Тогда потенциал третьего столбца V₃ = 0 + 77 = 77, четвертого столбца V₄ = 0 + 31,3 = 31,3; потенциал второй строки U₁ = 77 - 52,5 = 24,5 и т.д. (Потенциалы отыскиваются только через загруженные клетки!).

После определения потенциалов все свободные клетки матрицы проверяются на выполнение второго условия оптимальности решения задачи методом потенциалов: V_j - U_i <= c_ij для клеток с x_ij = 0 (свободных). Если это условие выполняется, то план оптимален. В табл. 4 для клетки R₁Р₂ это условие не выполняется и величина нарушения

H = 110 - 0 - 80 = 30. Улучшение плана начинается с исправления максимального по величине нарушения (если их несколько), причем только одного. Поместим в клетку с нарушением максимально возможную величину потока. Строим замкнутый контур по правилу: выйдя из клетки с нарушением и поворачивая только в загруженных клетках возвращаемся в клетку с нарушением. Вершины контура обозначаем знаками “ + ” и

“ - “, начиная со знака “ + ” в клетке с нарушением и чередуя их. В клетку с нарушением помещаем минимальное из чисел, стоящих у отрицательных вершин контура. x_ул. = min [x_ij^(-)] = min [ 30, 160 ] = 30. Это значение убираем из клеток R₁П₃, П₃П₂ и добавляем в клетки R₁Р₂ и П₃П₃.

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

, тыс. руб. Или тыс. руб.

По полученному оптимальному плану в произвольном масштабе ширины потоков вычерчивается диаграмма оптимальных грузопотоков (лист 1 курсовой работы со штампом).

Таблица 4 - Матрица задачи и исходный план

ж77

30

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

ж33

110

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

Затраты на перевозки по исходному плану:

С_исх = 30*77 + 150*31,3 + 80*52,5 + 90*49,5 + 110*33 = 19290 тыс. руб.

Затраты на перевозки по оптимальному плану:

С_опт. = 150*31,3 + 30*80 + 80*45,1 + 90*49,5 + 80*38 = 18198 тыс. руб.

Сокращение затрат на перевозки:

С_исх - С_опт. = 19290 - 18198 = 1092 тыс. руб.

Или

30*30 + 80*2,4 = 1092 тыс. руб.

Таблица 5 - Результат первой итерации

Таблица 6 - Результат второй итерации - оптимальный план

Список использованных источников

1. Правдин Н.В., Негрей В.Я., Подкопаев В.А. Взаимодействие различных видов транспорта: примеры и расчеты / Под ред. Н.В. Правдина. - М.: Транспорт, 1989. - 208 с.

2. Тихончук Ю.Н., Елисеева Т.В., Каяшев А.В. Рациональное распределение грузовых перевозок между железнодорожным и автомобильным транспорт. - М.: Транспорт, 1972. - 136 с.

3. Сопоставимые издержки разных видов транспорта при перевозке грузов / Под ред. В.И. Дмитриева и К.Н. Шишко. - М.: Транспорт, 1972. - 488 с.

4. Белов И.В., Каплан А.В. Математические методы в планировании на железнодорожном транспорте. - М.: Транспорт, 1972. - 248 с.

Размещено на Allbest.ru