Транспортная задача. Оптимизация стоимости перевозок продукции

1.

Транспортная задача
Оптимизация стоимости
перевозок продукции

2.

Математическая модель
транспортной задачи
дано m поставщиков продукции одного вида и n
потребителей;
предложение каждого i-го поставщика составляет ai
единиц;
спрос каждого j-го потребителя – bj единиц;
тарифы перевозок (т.е. цены перевозок единицы
продукции от i-го поставщика j-му потребителю) равны
cij;
Требуется определить оптимальный план перевозок
продукции (т.е. количество продукции, перевозимой от
каждого поставщика каждому потребителю), при
котором суммарная стоимость перевозок минимальна.

3.

Оптимизация транспортных потоков
АО "Свежий хлеб"
Исходные данные:
j --->
Поставщики
i
1
2
3
4
5
Запросы (b j )
1
Потребители
2
3
4
Пекарня №1
Пекарня
"Бублик"
"Пита хлеб"
"Одесские
баранки"
240,0
115,0
280,0
370,0
Запасы (a i )
Мелькомбинат
Мелькомбинат
Мельница №1
Мелькомбинат
Мелькомбинат
№17
№18
№20
№21
300,0
240,0
170,0
120,0
320,0
470,00
390,00
236,50
195,00
390,00
415,00
323,00
273,00
194,00
360,00
450,00
380,00
210,00
90,00
275,00
Фирма (АО "Свежий хлеб") имеет несколько производственных предприятий:
j = 1, 2, 3, 4
Сырье (мука) для фирмы поставляется несколькими поставщиками:
i = 1, 2, 3, 4, 5
Стоимость сырья одинакова, но стоимость перевозки зависит от расстояния и
отличается для каждого поставщика и потребителя. Тарифы на перевозку 1 т сырья от iго поставщика j-му потребителю (cij) приведены в матрице.
326,50
410,00
180,00
240,00
440,00

4.

Цель:
минимизация суммарной стоимости перевозок S
m
n
S cij xij min;
i 1 j 1
n
количество продукции, вывозимой от i-го
xij a i , i 1, m;
поставщика, не должно превышать его
i 1
предложение;
n
xij b j , j 1, n; количество продукции, ввозимой j-му
потребителю, должно удовлетворять спросу j-ro
j 1
потребителя;
n
m
суммарное предложение не должно быть
a i b j ;
меньше суммарного спроса.
j 1
i 1
x 0.
ij

5.

Р е ш е н и е
A
B
C
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
D
j --->
Поставщики
i
1
2
3
4
5
Запросы (b j )
1
Хлебозавод
№1
240,0
Запасы (a i )
Мелькомбинат
Мелькомбинат
Мелькомбинат
Мелькомбинат
Мелькомбинат
№17
№18
№19
№20
№21
Факт
Мелькомбинат №17
Мелькомбинат №18
Мелькомбинат №19
Мелькомбинат №20
Мелькомбинат №21
300,0
240,0
170,0
120,0
320,0
470,00
390,00
236,50
195,00
390,00
4,0
4,0
4,0
4,0
4,0
Всего на перевозки требуется
=СУММ(D19:G19)
5,0
1,00
1,00
1,00
1,00
1,00
1681,5
E
F
G
Потребители
2
3
Пекарня
"Пита "Бублик"
хлеб"
115,0
280,0
H
4
"Одесские
баранки"
370,0
Предполагаем, что от каждого
415,00
450,00
326,50
поставщика
каждому
потребителю
323,00
380,00
410,00
поставляется
1-ца210,00
(т.е. 1 т) продукции
273,00
180,00
194,00
360,00
5,0
1,00
1,00
1,00
1,00
1,00
1565
90,00
275,00
5,0
1,00
1,00
1,00
1,00
1,00
1405
Тарифы за
перевозку 1 т
муки от i-го
240,00 поставщика j-му
440,00 потребителю
=СУММ(G15:G19)
5,0
1,00
Колическтво
1,00 муки, постав1,00 ляемой от i-го
1,00 поставщика j-му
1,00 потребителю
1596,5
6248
=СУММПРОИЗВ(D7:D11;D15:D19)
=СУММ(D20:G20)

6.

Суммарная стоимость
перевозок
Поиск
решения

7.

Готовая работа
A
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
B
C
D
E
F
Оптимизация транспортных потоков АО "Свежий хлеб"
Поставщики
Хлебозавод
№1
Запросы (b j )
240,0
Потребители
Пекарня
"Пита "Бублик"
хлеб"
115,0
280,0
"Одесские
баранки"
370,0
Запасы (a i )
Мелькомбинат №17
Мелькомбинат №18
Мелькомбинат №19
Мелькомбинат №20
Мелькомбинат №21
300,0
240,0
170,0
120,0
320,0
Факт
Мелькомбинат №17
Мелькомбинат №18
Мелькомбинат №19
Мелькомбинат №20
Мелькомбинат №21
300,00
135,00
170,00
120,00
280,00
470,00
390,00
236,50
195,00
390,00
240,00
20,00
100,00
120,00
54 850,00
Всего на перевозки требуется
415,00
323,00
273,00
194,00
360,00
115,00
115,00
37 145,00
450,00
380,00
210,00
90,00
275,00
280,00
280,00
77 000,00
279 545,00
326,50
410,00
180,00
240,00
440,00
370,00
300,00
70,00
110 550,00
G