КМИ - 5 Транспортна задача

5.1 Балансирана задача

Дадена е таблица с транспортни разходи между три депа (източници) ($S_i, i = 1, \ldots, 3$) и четири града (дестинации) ($D_j, j = 1, \ldots, 4$).

Таблица 5.1: Транспортни разходи
	$D_1$	$D_2$	$D_3$	$D_4$	Предлагане
$S_1$	18	13	17	14	250
$S_2$	16	18	14	10	200
$S_3$	21	24	13	10	400

Търсене	200	225	275	150

Целта на задачата е да се определят количествата $x_{ij}$ превозени от източник $i$ до дестинация $j$ така, че общите транспортни разходи (Таблица 5.1) да са възможно най-ниски.

Общите разходи са дадени от

\[\begin{aligned} \sum_{i = 1}^{3} \sum_{j = 1}^{4} c_{ij}x_{ij} = & c_{11}x_{11} + c_{12}x_{12} + c_{13}x_{13} + c_{14}x_{14} + \\ & c_{21}x_{21} + c_{22}x_{22} + c_{23}x_{23} + c_{24}x_{24} + \\ & c_{31}x_{31} + c_{32}x_{32} + c_{33}x_{33} + c_{34}x_{34} \end{aligned}\]

В конкретната задача получаваме:

\[\begin{aligned} \sum_{i = 1}^{3} \sum_{j = 1}^{4} c_{ij}x_{ij} = & 18x_{11} + 13x_{12} + 17x_{13} + 14x_{14} + \\ & 16x_{21} + 18x_{22} + 14x_{23} + 10x_{24} + \\ & 21x_{31} + 24x_{32} + 13x_{33} + 10x_{34} \end{aligned}\]

Тази цел трябва да постигнем така, че за всяка дестинация трябва да доставим точно толкова стоки, колкото е търсенето. В същото време от всеки източник не можем да изпратим повече от наличността та (предлагане). Ако запишем превозените количества в матрица (Таблица 5.2), тези ограничения просто означават, че сумите по колоните на матрицата трябва да са равни на търсенето за всички източници и че сумите по редовете трябва да са равни на наличностите в източниците.

Таблица 5.2: Количества от източник към дестинация
	$D_1$	$D_2$	$D_3$	$D_4$	Предлагане
$S_1$	$x_{11}$	$x_{12}$	$x_{13}$	$x_{14}$	$\sum_{j = 1}^4 x_{1j} = 250$
$S_2$	$x_{21}$	$x_{22}$	$x_{23}$	$x_{24}$	$\sum_{j = 1}^4 x_{2j} = 200$
$S_3$	$x_{31}$	$x_{32}$	$x_{33}$	$x_{34}$	$\sum_{j = 1}^4 x_{3j} = 400$

Търсене	$\sum_{i = 1}^3 x_{i1} = 200$	$\sum_{i = 1}^3 x_{i2} = 225$	$\sum_{i = 1}^3 x_{i3} = 275$	$\sum_{i = 1}^3 x_{i4} = 150$

Търсене при дестинация 1:

\[ x_{11} + x_{21} + x_{31} = 200 \\ \]

Търсене при дестинация 2:

\[ x_{12} + x_{22} + x_{32} = 225 \] Търсене при дестинация 3:

\[ x_{13} + x_{23} + x_{33} = 275 \] Търсене при дестинация 4:

\[ x_{14} + x_{24} + x_{34} = 150 \]

Наличност в източник 1:

\[ x_{11} + x_{12} + x_{13} + x_{14} = 250 \]

Наличност в източник 2:

\[ x_{21} + x_{22} + x_{23} + x_{24} = 200 \]

Наличност в източник 3:

\[ x_{31} + x_{32} + x_{33} + x_{34} = 250 \]

Цялата транспортна задача е:

\[\begin{align*} \min z = 18x_{11} + 13x_{12} + 17x_{13} + 14x_{14} + \\ 16x_{21} + 18x_{22} + 14x_{23} + 10x_{24} + \\ 21x_{31} + 24x_{32} + 13x_{33} + 10x_{34} \end{align*}\]

При ограничения:

\[\begin{align*} & x_{11} + x_{21} + x_{31} = 200 \\ & x_{12} + x_{22} + x_{32} = 225 \\ & x_{13} + x_{23} + x_{33} = 275 \\ & x_{14} + x_{24} + x_{34} = 150 \\ & x_{11} + x_{12} + x_{13} + x_{14} = 250 \\ & x_{21} + x_{22} + x_{23} + x_{24} = 200 \\ & x_{31} + x_{32} + x_{33} + x_{34} = 400 \end{align*}\]

Решение на задачата в Excel можете да изтеглите от тук

Целева функция = 11250.0
x_0_0 = 25.0
x_0_1 = 225.0
x_0_2 = 0.0
x_0_3 = 0.0
x_1_0 = 175.0
x_1_1 = 0.0
x_1_2 = 0.0
x_1_3 = 25.0
x_2_0 = 0.0
x_2_1 = 0.0
x_2_2 = 275.0
x_2_3 = 125.0
Ограничение: Предлагане_от_източник_0, скрита цена: 12.0, slack -0.0
Ограничение: Предлагане_от_източник_1, скрита цена: 10.0, slack -0.0
Ограничение: Предлагане_от_източник_2, скрита цена: 10.0, slack -0.0
Ограничение: Търсене_при_дестинация_0, скрита цена: 6.0, slack -0.0
Ограничение: Търсене_при_дестинация_1, скрита цена: 1.0, slack -0.0
Ограничение: Търсене_при_дестинация_2, скрита цена: 3.0, slack -0.0
Ограничение: Търсене_при_дестинация_3, скрита цена: 0.0, slack -0.0

5.2 Предлагане надвишаващо търсенето

Дадена е таблица с транспортни разходи между три депа (източници) ($S_i, i = 1, \ldots, 3$) и четири града (дестинации) ($D_j, j = 1, \ldots, 4$).

	$D_1$	$D_2$	$D_3$	$D_4$	Предлагане
$S_1$	18	13	17	14	250
$S_2$	16	18	14	10	200
$S_3$	21	24	13	10	500

Търсене	200	225	275	150

Добавяме фиктивна дестинация (потребител)

	$D_1$	$D_2$	$D_3$	$D_4$	$D_5$	Предлагане
$S_1$	18	13	17	14	0	250
$S_2$	16	18	14	10	0	200
$S_3$	21	24	13	10	0	500

Търсене	200	225	275	150	100

Разходите за транспорт до този фиктивен потребител са равни на нула. Наличието на фиктивен потребител не променя структурата на задачата и тя е:

\[\begin{align*} \min \sum_{i = 1}^3 \sum_{j = 1}^{5} c_{ij}x_{ij} = & c_{11}x_{11} + c_{12}x_{12} + c_{13}x_{13} + c_{14}x_{14} + c_{15}x_{15} + \\ & c_{21}x_{21} + c_{22}x_{22} + c_{23}x_{23} + c_{24}x_{24} + c_{25}x_{25} + \\ & c_{31}x_{31} + c_{32}x_{32} + c_{33}x_{33} + c_{34}x_{34} + c_{35}x_{35} = \\ & 18x_{11} + 13x_{12} + 17x_{13} + 14x_{14} + 0x_{15} + \\ & 16x_{21} + 18x_{22} + 14x_{23} + 10x_{24} + 0x_{25} + \\ & 21x_{31} + 24x_{32} + 13x_{33} + 10x_{34} + 0 x_{35} \end{align*}\]

При ограничения

\[\begin{align*} & x_{11} + x_{12} + x_{13} + x_{14} + x_{15} = 250 \quad \text{Предлагане 1} \\ & x_{22} + x_{22} + x_{23} + x_{24} + x_{25} = 200 \quad \text{Предлагане 2} \\ & x_{32} + x_{32} + x_{33} + x_{34} + x_{35} = 500 \quad \text{Предлагане 3} \\ & x_{11} + x_{21} + x_{31} = 200 \quad \text{Търсене 1} \\ & x_{12} + x_{22} + x_{32} = 225 \quad \text{Търсене 2} \\ & x_{13} + x_{23} + x_{33} = 275 \quad \text{Търсене 3} \\ & x_{14} + x_{24} + x_{34} = 150 \quad \text{Търсене 4} \\ & x_{15} + x_{25} + x_{35} = 100 \quad \text{Търсене 5} \\ \end{align*}\]

Решение в excel можете да свалите тук

Целева функция = 11200.0
x_0_0 = 0.0
x_0_1 = 225.0
x_0_2 = 0.0
x_0_3 = 0.0
x_0_4 = 25.0
x_1_0 = 200.0
x_1_1 = 0.0
x_1_2 = 0.0
x_1_3 = 0.0
x_1_4 = 0.0
x_2_0 = 0.0
x_2_1 = 0.0
x_2_2 = 275.0
x_2_3 = 150.0
x_2_4 = 75.0
Ограничение: Предлагане_от_източник_0, скрита цена: 10.0, slack -0.0
Ограничение: Предлагане_от_източник_1, скрита цена: 10.0, slack -0.0
Ограничение: Предлагане_от_източник_2, скрита цена: 10.0, slack -0.0
Ограничение: Търсене_при_дестинация_0, скрита цена: 6.0, slack -0.0
Ограничение: Търсене_при_дестинация_1, скрита цена: 3.0, slack -0.0
Ограничение: Търсене_при_дестинация_2, скрита цена: 3.0, slack -0.0
Ограничение: Търсене_при_дестинация_3, скрита цена: 0.0, slack -0.0
Ограничение: Търсене_при_дестинация_4, скрита цена: -10.0, slack -0.0

Кои източници не успяват да доставят цялата си наличност? Поглеждаме кои източници доставят на фиктивния потребител $j = 5$. В настоящото решение това са $S_1$ и $S_3$. Ако по някаква причина искаме оптимум при условие, че първият източник доставя цялата си наличнос можем да поставим висока цена на доставка към фиктивната дестинация. Следващото решение показва оптимумът, когато цената за доставка от $S_1$ към $D_5$ e 100.

Целева функция = 11250.0
x_0_0 = 25.0
x_0_1 = 225.0
x_0_2 = 0.0
x_0_3 = 0.0
x_0_4 = 0.0
x_1_0 = 175.0
x_1_1 = 0.0
x_1_2 = 0.0
x_1_3 = 25.0
x_1_4 = 0.0
x_2_0 = 0.0
x_2_1 = 0.0
x_2_2 = 275.0
x_2_3 = 125.0
x_2_4 = 100.0
Ограничение: Предлагане_от_източник_0, скрита цена: 12.0, slack -0.0
Ограничение: Предлагане_от_източник_1, скрита цена: 10.0, slack -0.0
Ограничение: Предлагане_от_източник_2, скрита цена: 10.0, slack -0.0
Ограничение: Търсене_при_дестинация_0, скрита цена: 6.0, slack -0.0
Ограничение: Търсене_при_дестинация_1, скрита цена: 1.0, slack -0.0
Ограничение: Търсене_при_дестинация_2, скрита цена: 3.0, slack -0.0
Ограничение: Търсене_при_дестинация_3, скрита цена: 0.0, slack -0.0
Ограничение: Търсене_при_дестинация_4, скрита цена: -10.0, slack -0.0

5.3 Задача 1

Autoparts AG разполага с три завода в Мюнхен, Хамбурт и Бремен и с два големи центъра за дистрибуция в Берлин и в Хановер. Тримесечният капацитет на трите завода е 1000, 1500 и 500 автомобила, а търсенето в двата дистрибуторски центъра за същия период е 2300 и 1400 автомобила. Диаграмата на разстоянията между заводите и разпределителните центрове е дадена в Таблица 5.3.

Таблица 5.3: Разстояния между заводи и дистрибуторски центрове
	Берлин	Хановер
Мюнхен	500	480
Хамбург	250	130
Бремен	200	100

Транспортните разходи между заводите и дистрибуторските центрове са 8 евроцента на автомобил и километър. Формулирайте целевата функция в евро, както и ограниченията на транспортната задача.

Формулирайте транспортна задача, която да намери този оптимум.

5.4 Задача 2

Предприятие произвежда туристически раници. Търсенето на нейния продукт през пиковия период от март до юни всяка година е съответно 100, 200, 180 и 300 единици. Дружеството използва работници на непълно работно време, за да посрещне колебанията в търсенето. Знаем, че, предприятието може да произведе 50, 180, 280 и 270 единици в периода от март до юни. Търсенето през текущия месец може да бъде посрещнато по един от три начина:

Производството за текущия месец на цена от 40 USD на раница
Излишък на продукция през по-ранен месец при допълнителни разходи за складиране от $0.50 на раница на месец.
Излишък на продукция през по-късен месец (обратно поръчване) при допълнителни наказателни разходи от $2.00 на раница на месец.

Предприятието търси да определи оптималния производствен график за четирите месеца. Формулирайте транспортна задача, която да намери този оптимум.

5.5 Първоначален опорен план (северозападен ъгъл)

	$D_1$	$D_2$	$D_3$	$D_4$	Предлагане
$S_1$	0	0	0	0	300
$S_2$	0	0	0	0	500
$S_3$	0	0	0	0	400
Търсене	100	700	50	350

	$D_1$	$D_2$	$D_3$	$D_4$	Предлагане
$S_1$	100	0	0	0	200
$S_2$	0	0	0	0	500
$S_3$	0	0	0	0	400
Търсене	0	700	50	350

	$D_1$	$D_2$	$D_3$	$D_4$	Предлагане
$S_1$	100	200	0	0	0
$S_2$	0	0	0	0	500
$S_3$	0	0	0	0	400
Търсене	0	500	50	350

	$D_1$	$D_2$	$D_3$	$D_4$	Предлагане
$S_1$	100	200	0	0	0
$S_2$	0	500	0	0	0
$S_3$	0	0	0	0	400
Търсене	0	0	50	350

	$D_1$	$D_2$	$D_3$	$D_4$	Предлагане
$S_1$	100	200	0	0	0
$S_2$	0	500	0	0	0
$S_3$	0	0	500	0	350
Търсене	0	0	0	350

	$D_1$	$D_2$	$D_3$	$D_4$	Предлагане
$S_1$	100	200	0	0	0
$S_2$	0	500	0	0	0
$S_3$	0	0 (0)	500	350	0
Търсене	0	0	0	0

5.6 Първоначален опорен план (най-ниски разходи)

	$D_1$	$D_2$	$D_3$	$D_4$	Предлагане
$S_1$	3	8	7	12	300
$S_2$	13	10	5	9	500
$S_3$	2	1	14	15	400
Търсене	100	700	50	350

Най-ниските транспортни разходи намираме в маршрута $S_3 \to D_2$. Най-голямото количество, което можем да превозим по този маршрут е дадено от минимума между търсене и предлагане: $\min(400, 700) = 400$.

	$D_1$	$D_2$	$D_3$	$D_4$	Предлагане
$S_1$	3	8	7	12	300
$S_2$	13	10	5	9	500
$S_3$	2	1 (400)	14	15	0
Търсене	100	300	50	350

Следващият маршрут с най-ниски разходи е $S_1 \to D_1$ (маршрутът $S_3 \ to D_1$ има по-ниски транспортни разходи, но предлагането от третия източник е изчерпано). Най-голямото количество, което можем да превозим по този маршрут е $\min(300, 100) = 100$

	$D_1$	$D_2$	$D_3$	$D_4$	Предлагане
$S_1$	3 (100)	8	7	12	200
$S_2$	13	10	5	9	500
$S_3$	2	1 (400)	14	15	0
Търсене	0	300	50	350

Следващият маршрут с най-ниски разходи е $S_2 \to D_3$. Най-голямото количество, което можем да превозим по този маршрут е $\min(500, 50) = 50$

	$D_1$	$D_2$	$D_3$	$D_4$	Предлагане
$S_1$	3 (100)	8	7	12	200
$S_2$	13	10	5 (50)	9	450
$S_3$	2	1 (400)	14	15	0
Търсене	0	300	0	350

	$D_1$	$D_2$	$D_3$	$D_4$	Предлагане
$S_1$	3 (100)	8 (200)	7	12	0
$S_2$	13	10	5 (50)	9 (350)	150
$S_3$	2	1 (400)	14	15	0
Търсене	0	100	0	0

	$D_1$	$D_2$	$D_3$	$D_4$	Предлагане
$S_1$	3 (100)	8 (200)	7	12	0
$S_2$	13	10 (100)	5 (50)	9 (350)	0
$S_3$	2	1 (400)	14	15	0
Търсене	0	0	0	0

5.7 Изроден първоначален план

	$D_1$	$D_2$	$D_3$	$D_4$	Предлагане
$S_1$	2 (10)	5 (50)	1	2	60
$S_2$	8	1	2 (30)	4	30
$S_3$	6	2 (400)	2	9 (10)	10
Търсене	10	50	30	10

	$D_1$	$D_2$	$D_3$	$D_4$	Предлагане
$S_1$	2 (10)	5 (50)	1	2	60
$S_2$	8 (0)	1	2 (30)	4	30
$S_3$	6	2 (400)	2 (0)	9 (10)	10
Търсене	10	50	30	10

	\(D_1\)	\(D_2\)	\(D_3\)	\(D_4\)	Предлагане
\(S_1\)	\(x_{11}\)	\(x_{12}\)	\(x_{13}\)	\(x_{14}\)	\(\sum_{j = 1}^4 x_{1j} = 250\)
\(S_2\)	\(x_{21}\)	\(x_{22}\)	\(x_{23}\)	\(x_{24}\)	\(\sum_{j = 1}^4 x_{2j} = 200\)
\(S_3\)	\(x_{31}\)	\(x_{32}\)	\(x_{33}\)	\(x_{34}\)	\(\sum_{j = 1}^4 x_{3j} = 400\)

Търсене	\(\sum_{i = 1}^3 x_{i1} = 200\)	\(\sum_{i = 1}^3 x_{i2} = 225\)	\(\sum_{i = 1}^3 x_{i3} = 275\)	\(\sum_{i = 1}^3 x_{i4} = 150\)