Транспортная задача по критерию «минимум стоимости»

Транспортная задача по критерию «минимум стоимости»

В m пунктах отправления (ПО) A₁, A₂, ... A_m имеются запасы (производство) одноименных грузов изделий в количестве а₁, а₂, ... а_m. Имеются n пунктов назначения (ПН) В₁, В₂,.. ,B_n, подавших заявки (спрос) на b₁, b₂,.. b_n единиц продукции. Сумма заявок равна сумме запасов: a_i= b_j.

Перевозка груза осуществляется автотранспортом, один автомобиль может перевозить не более 18 единиц груза. Стоимость перевозки груза из А_i в В_j в расчете на 1 км пути равна С руб. Расстояния d_ij задаются матрицей, которая получается при решении задачи кратчайшего пути из пункта А_i в пункт В_j.

Требуется: найти наиболее экономичные  маршруты перевозки грузов, то есть составить план перевозок (откуда, сколько, куда), чтобы все заявки были выполнены и общая стоимость была минимальная. Вычертить граф «транспортная сеть», представить таблицу распределения потоков перевозок по критерию «минимум стоимости».

Исходные данные табл.1.

Таблица 1

№ вар-та	С, руб.	Производство (ПО)			Потребление (ПН)
		А1	А3	А4	Б1	Б2	Б3	Б4	Б5
4	40	150	400	200	140	150	160	200	100

 

Решение

      Решаем задачу, используя метод построения графа «транспортная сеть»

Будем рассматривать величины С_ij как длины соответствующих дуг.

Транспортная сеть, соответствующая  данной задаче, строится следующим образом. Вход x₀ соединяется с каждой из вершин пунктов отправления x_i дугой с пропускной способностью c(x₀, x_i)=а_i. Каждая из вершин пунктов назначения y_j соединяется с выходом z дугой с пропускной способностью c(y_j, z)=b_j. Стоимость прохождения потока по дугам (x₀, x_i) и (y_j, z) считается равной 0. Далее каждая вершина x_i соединяется с каждой вершиной y_j дугой с бесконечной пропускной способностью, стоимость прохождения по которой равна С_ij. Затем в графе G=(x, u) ищется кратчайший путь от x₀ до z. Весь запас a_i или его часть x_ij –поток прохождения грузов – отправляется по этому пути, но потребность b_j не должна быть превышена. Процедура повторяется до тех пор, пока не будут выполнены все заявки. Общая стоимость перевозки грузов по транспортной сети:

С_ij x_ij Þ min.

 

Находим матрицу стоимости грузов, перевозимых из каждого пункта отправления в каждый пункт назначения (вычисляется по графу – рисунок 1). Матрица представлена в таблице 2.

 

 

Рисунок 1 – Связной неориентированный  граф G

 

 

Таблица 2 – Матрица стоимости  грузов

	Б1	Б2	Б3	Б4	Б5
А1	62	179	126	19	50
А3	51	66	183	132	94
А4	189	72	45	172	232

 

 

Вычертим граф «транспортная сеть» (рисунок 2).

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Рисунок 2 – Граф «транспортная  сеть»

По схеме сети дорог найдём кратчайшее расстояние от всех пунктов отправления  до всех пунктов назначения. В  результате распределения грузов делаем подсчёт стоимости переходов. Распределение потоков перевозок по критерию «минимум стоимости» представлено в таблице 3.

 

Таблица 3 – Распределение потоков перевозок по критерию «минимум стоимости».

Путь     перевозки		Длина пути	Количество рейсов	Стоимость одного рейса, руб.		Стоимость перевозки, тыс. руб.
		179	9	7160		64440
		51	8	2040		16320
		183	9	7320		65880
		94	6	3760		22560
		172	12	6880		82560
Итого:	251760