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

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

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 является оптимальным.

Делись добром ;)