Транспортные задачи

Практическая часть.

Задача 1.

Поставщик       Потребитель		D1	D2	D3	D4	D5
		17	14	20	19	15
C1	35	2	4	6	8	3
C2	20	9	7	2	3	6
C3	30	7	3	1	9	4

 

Есть три поставщика С1, С2, С3 и пять потребителей (их спрос D1, D2, D3, D4, D5 соответственно) некоторого груза. Стоимость доставки единицы груза от каждого поставщика к каждому потребителю задается матрицей. Найдите оптимальный план поставок и минимальные затраты на перевозку груза.

Решение.

1.Определим тип задачи:

 

Σn = 17 + 14 + 20 + 19 + 15 = 85

Σm = 35 + 20 + 30 = 85, задача является сбалансированной (закрытой).

 

2. Находим незанятую клетку с минимальным тарифом: (3,3). Помещаем туда меньшее из чисел C₃=30 и D₃=20. Потребности D₃ удовлетворены, остаток C3=10

Заполняем клетку с минимальным тарифом (1,1) Помещаем туда меньшее из чисел C1=35 и D1=17. Потребности D₁ удовлетворены, остаток С₁=18

Заполняем клетку с минимальным тарифом (1,5) Помещаем туда меньшее из чисел C1=18 и D5=15. Потребности D₅ удовлетворены, остаток С₁=3

Заполняем клетку с минимальным тарифом (2,4) Помещаем туда меньшее из чисел C2=20 и D4=19. Потребности D₄ удовлетворены, остаток С₂=1

Заполняем клетку с минимальным тарифом (3,2) Помещаем туда меньшее из чисел C3=10 и D2=14. Потребности D₂ не удовлетворены, остаток С₃=0, D₂=4

Заполняем клетку с минимальным тарифом (1,2) Помещаем туда меньшее из чисел C1=3 и D2=4. Потребности D₂ не удовлетворены, остаток С₁=0, D₂=1

Заполняем клетку с минимальным тарифом (2,2) Помещаем туда меньшее из чисел C2=1 и D2=14. Потребности D₂ удовлетворены, остаток С₃=0, D₂=0

Запишем транспортную таблицу в которой совместим найденный опорный план с величинами издержек. В левом верхнем углу каждой клетки будем указывать количество единиц продукции а в правом нижнем затраты на перевозку единицы продукции.

 

Поставщик       Потребитель		D1	D2	D3	D4	D5
		17	14	20	19	15
C1	35	2 17	4 3	6	8	3 15
C2	20	9	7 1	2	3 19	6
C3	30	7	3 10	1 20	9	4

 

Проверим полученный опорный план на невырожденность. Количество заполненных клеток должно удовлетворять условию n+m-1 . В нашем случае n+m-1=5+3-1=7 , что удовлетворяет условию невырожденности плана.

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

Pнач=  2*17+4*3+3*15+7*1+3*19+3*10+1*20=205

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

Определим потенциалы поставщиков  и потребителей, составив уравнения  Ui+Vj=Sij (где Sij-стоимость перевозок от i-поставщика j-му потребителю; Ui потенциал i-ного поставщика; Vj – потенциал j-ного потребителя) для заполненных клеток.

 

1) Пусть V₅ = 0 ;

   2) U₁ = P_1,5 - V₅ →  3-0=3 → U₁ =3

   3) V₁ = P_1,1 - U₁ → 2-3= -1 → U₁ = -1

   4) V₂ = P_1,2 - U₁ →  4-3= 1 → V₂ =1

   5) U₂ = P_2,2 - V₂ →  7-1= 6 → U₂ =6

   6) V₄ = P_2,4 - U₂ →  3-6= -3 → V₄=  -3

   7) U₃ = P_3,2 - V₂ →  3-1= 2 → U₃= 2

   8) V₃ = P_3,3 - U₃ →1-2= -1 → V₃= -1

 

Теперь для всех свободных клеток рабочей матрицы затрат вычислим оценки Sij, по формуле Sij = Pij – Ui - Vj . Каждая такая оценка показывает на сколько изменятся общие транспортные затраты при загрузке данной клетки единицей груза.

∆₁₃=( U₁+ V₃)-S₁₃= (3-1)-6=-4

∆₁₄=( U₁+ V₄)-S₁₄= (3-3)-8=-8

∆₂₁=( U₂+ V₁)-S₂₁= (6-1)-9=-4

∆₂₃=( U₂+ V₃)-S₂₃= (6-1)-2=3

∆₂₅=( U₂+ V₅)-S₂₅= (6-0)-6=0

∆₃₁=( U₃+ V₁)-S₃₁= (2-1)-7=-6

∆₃₄=( U₃+ V₄)-S₃₄= (2-3)-9=-10

∆₃₅=( U₃+ V₅)-S₃₅= (2-0)-4=-2

 

Если все  разности ∆_ij ≤ 0, то найденный план перевозок является оптимальным, в противном случае, его можно улучшить. Для клетки ∆₂₃ =3 › 0 изменяем цикл перевозок (Цикл-четное количество клеток, причем пустой должнабыть всего одна клетка)см.  табл.

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

 

Поставщик       Потребитель		D1	D2	D3	D4	D5
		17	14	20	19	15
C1	35	2 17	4 3	6	8	3 15
C2	20	9	7    -     1	2 +	3 19	6
C3	30	7	3 +   10	1 -    20	9	4

 

Таким образом после переноса таблица  будет иметь следующий вид:

Поставщик       Потребитель		D1	D2	D3	D4	D5
		17	14	20	19	15
C1	35	2 17	4 3	6	8	3 15
C2	20	9	7	2 1	3 19	6
C3	30	7	3   11	1 19	9	4

 

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

Pнач=  2*17+4*3+3*15+2*1+3*19+3*11+1*19=202

Проверим полученное решение на оптимальность используя метод потенциалов.

1) Пусть V₅ = 0 ;

   2) U₁ = P_1,5 - V₅  → 3-0=3 → U₁ =3

   3) V₁ = P_1,1 - U₁ → 2-3= -1 → U₁ = -1

   4) V₂ = P_1,2 - U₁ →  4-3= 1 → V₂ =1

   5) U₃ = P_3,2 – V₂ →  2-1= 2 → U₃ =2

   6) V₃ = P_3,3 – U₃  →  1-2= -1 → V₃=  -1

   7) U₂ = P_2,3 – V₃ →  2+1= 0 → U₂= 3

   8) V₄ = P_3,4 – U₂ →3-3= 0 → V₃= 0

 

Теперь для всех свободных клеток рабочей матрицы затрат вычислим оценки Sij, по формуле Sij = Pij – Ui - Vj . Каждая такая оценка показывает на сколько изменятся общие транспортные затраты при загрузке данной клетки единицей груза.

∆₁₃=( U₁+ V₃)-S₁₃= (3-1)-6=-4

∆₁₄=( U₁+ V₄)-S₁₄= (3+0)-8=-5

∆₂₁=( U₂+ V₁)-S₂₁= (3-1)-9=-7

∆₂₂=( U₂+ V₂)-S₂₂= (3+1)-7=-3

∆₂₅=( U₂+ V₅)-S₂₅= (3-0)-6=-3

∆₃₁=( U₃+ V₁)-S₃₁= (2-1)-7=-6

∆₃₄=( U₃+ V₄)-S₃₄= (2-0)-9=-7

∆₃₅=( U₃+ V₅)-S₃₅= (2-0)-4=-2

 

Так как все разности ∆_ij ≤ 0, то найденный план перевозок является оптимальным.

Pмин= 2*17+4*3+3*15+2*1+3*19+3*11+1*19=202

 

Задача №2

Существует четыре базы: С₁, С₂, С₃,С₄ и четрыре торговые точки D₁,D₂,D₃,D₄ соответственно. Расстояние от баз до торговых точек задается матрицей(см.ниже)

Базы       Торг.точки		D1	D2	D3	D4
		1	1	1	1
C1	1	2	4	6	8
C2	1	3	9	7	2
C3	1	3	6	7	3
C4	1	1	9	4	3

 

Решение:

Данная задача- задача о назначениях- сводится к транспортной задаче, для ее решения можно применять те же методы, что и для транспортной задачи.

Составим математическую модель  задачи.

Вводим переменные:

х_ij-это переменная, отражающая соответствие определенной торговой базы конкретной торговой точке, может принимать значение 1 или 0

Тогда система ограничений будет  иметь вид:

 х₁₁+х₁₂+х₁₃+х₁₄=1

 х₂₁+х₂₂+х₃₃+х₄₄=1

 х₃₁+х₃₂+х₃₃+х₃₄=1

 х₄₁+х₄₂+х₄₃+х₄₄=1

х₁₁+х₂₁+х₃₁+х₄₁=1

 х₁₂+х₂₂+х₃₂+х₄₂=1

 х₁₃+х₂₃+х₃₃+х₄₃=1

 х₁₄+х₂₄+х₃₄+х₄₄=1

х_ij≥ 0; i-1..4; j-1..4

х_ij-целое

Целевая функция-суммарное расстояние от баз до торговых точек:

Р=2х₁₁+4х₁₂+6х₁₃+8х₁₄+3х₂₁+9х₂₂+7х₃₃+2х₄₄+3х₃₁+6х₃₂+7х₃₃+3х₃₄+1х₄₁+9х₄₂+4х₄₃+3х₄₄→min

 

Для решения задачи составим таблицу. В которой отображаем расстояние от баз до торговых точек(в правом верхнем углу ячеек) Начальное решение данной задачи найдем методом минимального элемента.

Полученное решение представлено в таблице ( рис..)

Количество заполненных клеток должно быт равным m+n-1=4+4-1=7

 

Базы       Торг.точки		D1	D2	D3	D4
		1	1	1	1
C1	1	2 0	4 1	6	8
C2	1	3	9	7	2 1
C3	1	3 0	6	7 1	3
C4	1	1 1	9	4	3 0

 В нашем случае количество  заполненных клеток равно 4, следовательно,  вводим дополнительно три фиктивных  значения( три  нуля)

Суммарное расстояние между базами и торговыми точками при этом составляет

S= 1*1+2*1+4*1+7*1=14

Получим полученное решение на оптимальность: Проверку на оптимальность производим методом потенциалов:

U₁=0

U₁+V