5  Транспортна задача

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

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

Таблица 5.1: Транспортни разходи
D1 D2 D3 D4 Предлагане
S1 18 13 17 14 250
S2 16 18 14 10 200
S3 21 24 13 10 400
Търсене 200 225 275 150

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

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

i=13j=14cijxij=c11x11+c12x12+c13x13+c14x14+c21x21+c22x22+c23x23+c24x24+c31x31+c32x32+c33x33+c34x34

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

i=13j=14cijxij=18x11+13x12+17x13+14x14+16x21+18x22+14x23+10x24+21x31+24x32+13x33+10x34

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

Таблица 5.2: Количества от източник към дестинация
D1 D2 D3 D4 Предлагане
S1 x11 x12 x13 x14 j=14x1j=250
S2 x21 x22 x23 x24 j=14x2j=200
S3 x31 x32 x33 x34 j=14x3j=400
Търсене i=13xi1=200 i=13xi2=225 i=13xi3=275 i=13xi4=150

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

x11+x21+x31=200

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

x12+x22+x32=225 Търсене при дестинация 3:

x13+x23+x33=275 Търсене при дестинация 4:

x14+x24+x34=150

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

x11+x12+x13+x14=250

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

x21+x22+x23+x24=200

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

x31+x32+x33+x34=250

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

minz=18x11+13x12+17x13+14x14+16x21+18x22+14x23+10x24+21x31+24x32+13x33+10x34

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

x11+x21+x31=200x12+x22+x32=225x13+x23+x33=275x14+x24+x34=150x11+x12+x13+x14=250x21+x22+x23+x24=200x31+x32+x33+x34=400

Решение на задачата в 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 Предлагане надвишаващо търсенето

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

D1 D2 D3 D4 Предлагане
S1 18 13 17 14 250
S2 16 18 14 10 200
S3 21 24 13 10 500
Търсене 200 225 275 150

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

D1 D2 D3 D4 D5 Предлагане
S1 18 13 17 14 0 250
S2 16 18 14 10 0 200
S3 21 24 13 10 0 500
Търсене 200 225 275 150 100

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

mini=13j=15cijxij=c11x11+c12x12+c13x13+c14x14+c15x15+c21x21+c22x22+c23x23+c24x24+c25x25+c31x31+c32x32+c33x33+c34x34+c35x35=18x11+13x12+17x13+14x14+0x15+16x21+18x22+14x23+10x24+0x25+21x31+24x32+13x33+10x34+0x35

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

x11+x12+x13+x14+x15=250Предлагане 1x22+x22+x23+x24+x25=200Предлагане 2x32+x32+x33+x34+x35=500Предлагане 3x11+x21+x31=200Търсене 1x12+x22+x32=225Търсене 2x13+x23+x33=275Търсене 3x14+x24+x34=150Търсене 4x15+x25+x35=100Търсене 5

Решение в 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. В настоящото решение това са S1 и S3. Ако по някаква причина искаме оптимум при условие, че първият източник доставя цялата си наличнос можем да поставим висока цена на доставка към фиктивната дестинация. Следващото решение показва оптимумът, когато цената за доставка от S1 към D5 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 единици в периода от март до юни. Търсенето през текущия месец може да бъде посрещнато по един от три начина:

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

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

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

D1 D2 D3 D4 Предлагане
S1 0 0 0 0 300
S2 0 0 0 0 500
S3 0 0 0 0 400
Търсене 100 700 50 350
D1 D2 D3 D4 Предлагане
S1 100 0 0 0 200
S2 0 0 0 0 500
S3 0 0 0 0 400
Търсене 0 700 50 350
D1 D2 D3 D4 Предлагане
S1 100 200 0 0 0
S2 0 0 0 0 500
S3 0 0 0 0 400
Търсене 0 500 50 350
D1 D2 D3 D4 Предлагане
S1 100 200 0 0 0
S2 0 500 0 0 0
S3 0 0 0 0 400
Търсене 0 0 50 350
D1 D2 D3 D4 Предлагане
S1 100 200 0 0 0
S2 0 500 0 0 0
S3 0 0 500 0 350
Търсене 0 0 0 350
D1 D2 D3 D4 Предлагане
S1 100 200 0 0 0
S2 0 500 0 0 0
S3 0 0 (0) 500 350 0
Търсене 0 0 0 0

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

D1 D2 D3 D4 Предлагане
S1 3 8 7 12 300
S2 13 10 5 9 500
S3 2 1 14 15 400
Търсене 100 700 50 350

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

D1 D2 D3 D4 Предлагане
S1 3 8 7 12 300
S2 13 10 5 9 500
S3 2 1 (400) 14 15 0
Търсене 100 300 50 350

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

D1 D2 D3 D4 Предлагане
S1 3 (100) 8 7 12 200
S2 13 10 5 9 500
S3 2 1 (400) 14 15 0
Търсене 0 300 50 350

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

D1 D2 D3 D4 Предлагане
S1 3 (100) 8 7 12 200
S2 13 10 5 (50) 9 450
S3 2 1 (400) 14 15 0
Търсене 0 300 0 350
D1 D2 D3 D4 Предлагане
S1 3 (100) 8 (200) 7 12 0
S2 13 10 5 (50) 9 (350) 150
S3 2 1 (400) 14 15 0
Търсене 0 100 0 0
D1 D2 D3 D4 Предлагане
S1 3 (100) 8 (200) 7 12 0
S2 13 10 (100) 5 (50) 9 (350) 0
S3 2 1 (400) 14 15 0
Търсене 0 0 0 0

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

D1 D2 D3 D4 Предлагане
S1 2 (10) 5 (50) 1 2 60
S2 8 1 2 (30) 4 30
S3 6 2 (400) 2 9 (10) 10
Търсене 10 50 30 10
D1 D2 D3 D4 Предлагане
S1 2 (10) 5 (50) 1 2 60
S2 8 (0) 1 2 (30) 4 30
S3 6 2 (400) 2 (0) 9 (10) 10
Търсене 10 50 30 10