5.2 Общая постановка и решение транспортной задачи
Общая постановка задачи выглядит следующим образом:
Имеется три пункта отправления груза:
A1 - Медвежьегорск;
А2 - Шала (пристань);
А3 - Важины.
Имеется три пункта назначения:
В1 - Городец;
В2 - Пенза;
В3 - Н. Новгород.
Для каждого пункта отправления известно количество отправляемого груза(а1, а2 и а3 соответственно), а для каждого пункта назначения - количество груза, которое нужно туда доставить(b1, b2, b3). (Из табл. 2 исходных данных.)
Известны также тарифы на перевозки. Обозначим их как dij, где i - индекс пункта отправления, j - индекс пункта назначения.
Требуется найти конкретные объемы груза xij, чтобы схема доставки груза обеспечивала минимальные издержки, т.е. чтобы выполнялось условие
Более подробное и наглядное представление дает нижеследующая таблица:
Таблица 21 Транспортная таблица
Пункты назначения Пункты отправления |
B1 |
В2 |
В3 |
||
b1 |
b2 |
b3 |
|||
A1 |
a1 |
d11 |
d12 |
d13 |
|
x11 |
x12 |
x13 |
|||
A2 |
a2 |
d21 |
d22 |
d23 |
|
x21 |
x22 |
x23 |
|||
A3 |
a3 |
d31 |
d32 |
d33 |
|
x31 |
x32 |
x33 |
Подставляя конкретные числа, получим:
Таблица 22 Матрица решения задачи
Пункты назначения Пункты отправления |
B1 |
В2 |
В3 |
||
45 |
120 |
60 |
|||
A1 |
80 |
388 |
659 |
703 |
|
A2 |
90 |
346 |
617 |
661 |
|
A3 |
55 |
367 |
638 |
682 |
При решении задачи должны соблюдаться следующие условия допустимости (ограничения):
1) , j = 1, 2, 3.
т.е. из всех пунктов отправления в каждый пункт назначения должно быть завезено столько груза, сколько предусмотрено планом.
V1 = 45 V2 = 120 V3 = 60
2) , i = 1, 2, 3.
т.е. во все пункты назначения из каждого пункта отправления необходимо вывезти весь запланированный к перевозке груз.
Q1 = 80 Q2 = 90 Q3 = 55
3) Хij ? 0, i = 1, 2, 3; j = 1, 2, 3.
т.е. объем перевозок между любыми пунктами не должен быть величиной отрицательной.
Решение
Транспортная задача является сбалансированной, так как общее количество отправляемого груза(80т.+90т.+55т.=225т.) равно общему количеству получаемого (45т.+120т.+60т.=225т.)
Составим начальное решение (опорный план) методом минимального элемента [10]*:
Находим незанятую клетку с минимальным тарифом: (2,1). Помещаем туда меньшее из чисел A2=90 и B1=45. После этого клетки (1,1) и (3,1) дальше рассматриваться не будут, так как в пункт B1 уже отправлено необходимое количество груза.
Находим незанятую клетку с минимальным тарифом: (2,2). Помещаем туда меньшее из чисел A2=90-45=45 (45т из 90 т. уже отправили) и B2=120.
После этого клетка (2,3) дальше рассматриваться не будет, так как из пункта А2 уже отправлен весь груз.
Находим следующую незанятую клетку с минимальным тарифом: (3,2). Помещаем в нее меньшее из чисел A3=55 и B2=120-45=75. (в пункт B2 уже отправлено 45т. из пункта А2).
После этого клетка (3,3) дальше рассматриваться не будет, так как из пункта А3 уже отправлен весь груз.
Находим незанятую клетку с минимальным тарифом: (1,2). Помещаем туда меньшее из чисел A1=80 и B2=120-45-55=20 (в пункт B2 уже отправлено 45т. из пункта А2 и 55т. из пункта А3).
Оставшиеся 60т. из пункта A1 отправляем в пункт B3.
Весь груз из пунктов отправления распределен, во все пункты назначения отправлено требуемое количество груза. Результат проделанных операций изображен в таблице 21.
Таблица 23 Начальное решение (опорный план) транспортной задачи
. Пункты . назнач. Пункты отправления |
B1 |
В2 |
В3 |
||
45 |
120 |
60 |
|||
A1 |
80 |
659 20 |
703 60 |
||
A2 |
90 |
346 45 |
617 45 |
||
A3 |
55 |
638 55 |
Проверим полученный опорный план на невырожденность. Количество заполненных клеток N должно удовлетворять условию N=n+m-1. В нашем случае N=5, n+m=3+3=6, что удовлетворяет условию невырожденности плана.
Вычислим общие затраты на перевозку всего груза. Перемножим числа стоящие в одной клетке (для всех клеток), т.е. количество груза, отправляемого по маршруту, умножим на величину тарифа; затем полученные произведения сложим. Получим значение суммарных затрат, для данного начального решения.
Pнач= 13180+42180+15570+27765+35090 = 133785 (руб)
Проведем поэтапное улучшение начального решения, используя метод потенциалов. Составим вспомогательную рабочую матрицу затрат. За основу берем таблицу 21, в заполненные клетки (которые соответствуют задействованным маршрутам) пишем только величину тарифа dij. Остальные клетки остаются пустыми. Кроме того, введем вспомогательный столбец, в который внесем значения неизвестных U1 ... U3 (для трех пунктов отправления) и вспомогательную строку, в которую внесем значения неизвестных V1 ... V3 (для трех пунктов назначения). Эти n+m неизвестных должны для всех (i,j), соответствующих загруженым клеткам, удовлетворять линейной системе уравнений: Ui+Vj=dij Эту систему всегда можно решить следующим способом: На первом шаге полагаем V3=0. Если на k-м шаге найдено значение неизвестной, то в системе всегда имеется еще не определенная неизвестная, которая однозначно может быть найдена на (k+1)-м шаге из уравнения Ui+Vj=dij, так как значение другой неизвестной в этом уравнении уже известно. То, какую неизвестную можно найти на (k+1)-м шаге, определяют методом проб. Переменные Ui и Vj называются симплекс-множителями или потенциалами.
Порядок вычисления потенциалов был следующий: 1) Пусть V3 = 0; 2) U1 = P1,3 - V3; 3) V2 = P1,2 - U1; 4) U2 = P2,2 - V2; 5) U3 = P3,2 - V2; 6) V1 = P2,1 - U2;
Рабочая матрица тарифов с рассчитанными потенциалами представлена ниже.
Таблица 24 Матрица тарифов
. Пункты . назнач. Пункты отправления |
B1 |
В2 |
В3 |
|||
b1 |
b2 |
b3 |
||||
A1 |
a1 |
659 |
703 |
U1=703 |
||
A2 |
a2 |
346 |
617 |
U2=661 |
||
A3 |
a3 |
638 |
U3=682 |
|||
V1=-315 |
V2=-44 |
V3=0 |
Теперь для всех свободных клеток рабочей матрицы затрат вычислим оценки Sij, по формуле Sij = dij - Ui - Vj. Каждая такая оценка показывает, на сколько изменятся общие транспортные затраты при загрузке данной клетки единицей груза. Таким образом, если среди оценок имеются отрицательные (затраты уменьшаются) то данный план можно улучшить переместив в соответствующую клетку некоторое количество груза. Если же среди оценок нет отрицательных - план является оптимальным.
Рабочая матрица затрат с заполненными оценками клетками представлена ниже, оценки выделены курсивом.
Таблица 25 Матрица тарифов с оценками
. Пункты . назнач. Пункты отправления |
B1 |
В2 |
В3 |
|||
b1 |
b2 |
b3 |
||||
A1 |
a1 |
0 |
659 |
703 |
U1=703 |
|
A2 |
a2 |
346 |
617 |
0 |
U2=661 |
|
A3 |
a3 |
0 |
638 |
0 |
U3=682 |
|
V1=-315 |
V2=-44 |
V3=0 |
Из таблицы 25 видно, что отрицательных оценок нет, значит, план улучшить нельзя, следовательно, решение, полученное в табл. 23 является оптимальным.
- Введение
- 1. Общетеоретическая характеристика транспортных грузовых тарифов
- 1.1 Система тарифов на железнодорожном транспорте
- 1.2 Система тарифов на речном транспорте
- 2. Индивидуальное задание для выполнения курсового проекта
- 3. Установление возможного маршрута доставки груза
- 4. Разработка тарифов на перегрузочные работы и перевозку груза речным транспортом
- 4.1 Расчет тарифов (сборов) на погрузку/выгрузку груза
- 4.2 Расчет тарифов на перевозку груза водным транспортом
- 4.2.1 Продолжительность стояночных операций
- 4.2.2 Время хода по отдельным участкам
- 4.2.3 Себестоимость перевозки грузов отдельных типов
- 4.2.4 Средняя себестоимость перевозки грузов
- 4.2.5 Тарифы за перевозку 1т груза
- 4.3 Расчет тарифов на перевозку грузов железнодорожным транспортом
- 5. Определение рациональной схемы доставки груза с помощью распределительного метода линейного программирования
- 5.1 Подготовка исходных данных
- 5.2 Общая постановка и решение транспортной задачи
- Заключение
- Тема: Общая хар-ка и принципы построения тарифов на доставку грузов.
- Обоснование оптимальной схемы перевозки груза.
- Выбор оптимальной схемы доставки груза
- 7.Определение оптимальной схемы доставки груза с помощью распределительного метода линейного программирования
- 2.1 Анализ возможных транспортных схем доставки груза
- 1. Методические положения по выполнению контрольной работы № 1 «Обоснование и выбор оптимального варианта логистической схемы доставки грузов»
- 2. Системы доставки грузов
- Системы доставки грузов
- 7 Технология доставки груза при смешенной перевозке
- 20. Договорные тарифы.