Транспортная задача
Вариант 6
Составить экономико-математическую модель и найти оптимальное распределение поставок и минимальные затраты на перевозку.
Поставщики Потребители Мощность
поставщиков
B1 B2 B3 B4
A1 2
4
3
6
25
A2 3 5
7
5
18
A3 1
8
4
5
12
A3 4
3
2
8
15
Спрос
потребителей 15 25 8 12
Решение:
Составим экономико-математическую модель задачи.
Введем неизвестные ‒ количество единиц груза, перевозимого от каждого поставщика к каждому потребителю, причем 0. Справедливы следующие системы ограничений.
Система ограничений по поставкам:
Система ограничений по потребителям:
Целевая функция, выражающая общую стоимость перевозок, имеет вид:
Таким образом, запишем экономико-математическую модель задачи:
Проверим выполнение необходимого условия разрешимости транспортной задачи:
Приведем задачу к закрытому виду: введем фиктивного поставщика со спросом груза равным 10 (70‒60). Тарифы перевозки единицы груза от поставщика к потребителю полагаем равны нулю.
Поставщики Потребители Мощность
поставщиков
B1 B2 B3 B4 B5
A1 2
4
3
6
0
25
A2 3 5
7
5
0
18
A3 1
8
4
5
0
12
A3 4
3
2
8
0
15
Спрос
потребителей 15 25 8 12 10
Составим опорный план по методу минимального элемента.
В клетку (1,4) с оценкой 0 запишем min(10,25)=10 ‒ 4-й столбец закрыт.
В клетку (3,1) с оценкой 1 запишем min(15,12)=12 ‒ 3-я строка закрыта.
В клетку (1,1) с оценкой 2 запишем min(15-12,25-10)=3 ‒ 1-й столбец закрыт.
В клетку (4,3) с оценкой 2 запишем min(8,15)=8 ‒ 3-й столбец закрыт.
В клетку (4,2) с оценкой 3 запишем min(25,15-8)=7 ‒ 4-я строка закрыта.
В клетку (1,2) с оценкой 4 запишем min(25-7,25-3-10)=12 ‒ 1-я строка закрыта.
В клетку (2,2) с оценкой 5 запишем min(25-12-7,18)=3 ‒ 2-й столбец закрыт.
В клетку (2,4) с оценкой 5 запишем min(12,18-6)=12 ‒ 4-я строка закрыта.
Поставщики Потребители Мощность
поставщиков
B1 B2 B3 B4 B5
A1 2
3 4
12 3
6
0
10 25
A2 3 5
6 7
5
12 0
18
A3 1
12 8
4
5
0
12
A3 4
3
7 2
8 8
0
15
Спрос
потребителей 15 25 8 12 10
Опорное решение запишем в виде матрицы:
872490146050
Критерий загруженности клеток выполняется, т.к. m+n-1=4+5-1=9-1=8, число загруженных клеток тоже равно 8.
Затраты по перевозке составят:
Проверим полученное решение на оптимальность методом потенциалов.
Найдем оценки пустых клеток:
Среди оценок есть положительные числа, поэтому можно улучшить опорное решение.
Выберем максимальную оценку свободной клетки (2;5): 0
12
10
+ –
– +
6
0
Т.к. min (6; 10) =6, то окончательно получим:
18
4
0
6
Поставщики Потребители Мощность
поставщиков
B1 B2 B3 B4 B5
A1 2
3 4
18 3
6
0
4 25
A2 3 5
7
5
12 0
6 18
A3 1
12 8
4
5
0
12
A3 4
3
7 2
8 8
0
15
Спрос
потребителей 15 25 8 12 10
Новое решение имеет вид:
Затраты по перевозке составят:
Проверим полученное решение на оптимальность методом потенциалов.
Найдем оценки пустых клеток:
Среди оценок нет положительных, следственно, получен оптимальный план по перевозкам, который определяется матрицей:
Минимальные затраты на перевозку составят 187 у.е.
