Составить транспортную таблицу и найти оптимальный план перевозок методом потенциалов, если исходные данные транспортной задачи представлены с помощью матриц:
A -матрица запасов у поставщиков;
B -матрица запросов потребителей;
C -матрица тарифов на перевозку грузов.
Ответ
Х=00100100500020015010000 , Рmion=2350 ден ед
Решение
Проверим необходимое и достаточное условие разрешимости задачи:
a=200+250+250=700b=200+100+100+300=700a=b.
Суммарная потребность груза равна запасам груза у поставщиков. Следовательно, задача является закрытой.
Найдем начальное решение методом минимального элемента.
Минимальный элемент матрицы тарифов находится в ячейке A3B3 и равен 1. Запасы поставщика A1 составляют 200 ед. Потребность потребителя B3 составляет 100 ед. От поставщика A1 к потребителю B3 будем доставлять 100 ед.Мы полностью исчерпали потребности потребителя B3. Вычеркиваем столбец 3 таблицы, т.е. исключаем ее из дальнейшего рассмотрения.
b1= 200
b2= 100
b3= 100
b4= 300
a1= 200
100
1
100
2
a2= 250
200
1
50
2
a3= 250
50
5
200
10
Перемножим числа стоящие в одной клетке (для всех клеток) затем полученные произведения сложим
. Получим значение суммарных затрат, для данного начального решения.
Pнач=
2850
Проведем поэтапное улучшение начального решения, используя метод потенциалов.Составим вспомогательную рабочую матрицу затрат. Ui+Vj=Pij
b1
b2
b3
b4
a1
1 2 u1= 2
a2
1 2 u2= 7
a3
5 10 u3= 10
v1= -6
v2= -5
v3= -1
v4= 0
Порядок вычисления потенциалов был следующий: 1) Пусть V4 = 0 ; 2) U1 = P1,4 - V4 ; 3) U3 = P3,4 - V4 ; 4) V3 = P1,3 - U1 ; 5) V2 = P3,2 - U3 ; 6) U2 = P2,2 - V2 ; 7) V1 = P2,1 - U2 ;Теперь для всех свободных клеток рабочей матрицы затрат вычислим оценки Sij, по формуле Sij = Pij – Ui - Vj .
b1
b2
b3
b4
a1
7 8 1 2 u1= 2
a2
1 2 1 -4 u2= 7
a3
2 5 -1 10 u3= 10
v1= -6
v2= -5
v3= -1
v4= 0
b1= 200
b2= 100
b3= 100
b4= 300
a1= 200
100
100
a2= 250
200
50
-
+
a3= 250
50
+
200
-
b1= 200
b2= 100
b3= 100
b4= 300
a1= 200
100 100
a2= 250
200 50
a3= 250
100 150
Рабочая матрица затрат с пересчитанными потенциалами и оценкам.
b1
b2
b3
b4
a1
3 8 1 2 u1= 2
a2
1 4 5 3 u2= 3
a3
-2 5 -1 10 u3= 10
v1= -2
v2= -5
v3= -1
v4= 0
Ячейка а3,b1, транспортной таблицы, должна загрузиться.
b1= 200
b2= 100
b3= 100
b4= 300
a1= 200
100
100
a2= 250
200
-
50
+
a3= 250
+
100
150
-
b1= 200
b2= 100
b3= 100
b4= 300
a1= 200
100 100
a2= 250
50 200
a3= 250
150 100
Рабочая матрица затрат с пересчитанными потенциалами и оценкам.
b1
b2
b3
b4
a1
3 6 1 2 u1= 2
a2
1 2 5 3 u2= 3
a3
6 5 1 2 u3= 8
v1= -2
v2= -3
v3= -1
v4= 0
В приведенной выше таблице нет отрицательных оценок (план улучшить нельзя), следовательно достигнуто оптимальное решение.
b1= 200
b2= 100
b3= 100
b4= 300
a1= 200
100
1
100
2
a2= 250
50
1
200
3
a3= 250
150
6
100
5
Общие затраты на перевозку всей продукции, для оптимального плана составляют:
Pопт=
2350
Ответ:
Х=00100100500020015010000 , Рmion=2350 ден ед
Задать вопрос
на новый заказ в Автор24.
