1)Определить сбалансированность задачи.
2) Найти начальное опорное решение методом минимальной стоимости.
3) Найти оптимальное решение, используя метод потенциалов.
Решить следующую транспортную задачу:
21) аі
Ответ
Х=2002000003005045013240
Ххчч
Рmin = 240 ден ед
Решение
1) Проверим необходимое и достаточное условие разрешимости задачи:
a=40+30+50=120 b=20+18+44+75=157a<b.
Суммарная потребность груза больше запасов груза у поставщиков. Следовательно, задача является открытой. Чтобы получить закрытую модель, введем фиктивного поставщика А4 с запасом, равным 157-120=37. Тарифы перевозки единицы груза от поставщика всем потребителям положим равными нулю. Запасы фиктивного поставщика будем рассматривать в последний момент.
2) Найдем начальное решение методом минимального элемента.
Минимальный элемент матрицы тарифов находится в ячейке A4B1 и равен 0. Запасы поставщика A4 составляют 17 ед. Потребность потребителя B1 составляет 20 ед. От поставщика A4 к потребителю B1 будем доставлять 17 ед. Мы полностью исчерпали запасы поставщика А4. Вычеркиваем строку 4 таблицы, т.е. исключаем ее из дальнейшего рассмотрения. Продолжая данные рассуждения аналогичным образом получим опорное решение:
b1= 20
b2= 18
b3= 44
b4= 75
a1= 40
40
a2= 30
30
a3= 50
1 4 45
a4= 37
20 17
Проверим полученный опорный план на невырожденность
. Количество заполненных клеток N должно удовлетворять условию N=n+m-1 . В нашем случае N=7, n+m=4+4=8 , что удовлетворяет условию невырожденности плана.
Вычислим общие затраты на перевозку всей продукции.
b1= 20
b2= 18
b3= 44
b4= 75
a1= 40
40
2
a2= 30
30
1
a3= 50
1
3
4
5
45
3
a4= 37
20
0
17
0
Перемножим числа стоящие в одной клетке (для всех клеток) затем полученные произведения сложим. Получим значение суммарных затрат, для данного начального решения.
Pнач= 268
3)Проведем поэтапное улучшение начального решения, используя метод потенциалов.Составим вспомогательную рабочую матрицу затрат. Ui+Vj=Pij
b1
b2
b3
b4
a1
2 u1= 0
a2
1 u2= 1
a3
3 5 3 u3= 3
a4
0 0 u4= 0
v1= 0
v2= 0
v3= 2
v4= 0
Порядок вычисления потенциалов был следующий: 1) Пусть V4 = 0 ; 2) U2 = P2,4 - V4 ; 3) U3 = P3,4 - V4 ; 4) V2 = P3,2 - U3 ; 5) V3 = P3,3 - U3 ; 6) U4 = P4,2 - V2 ; 7) U1 = P1,3 - V3 ; 8) V1 = P4,1 - U4 ;Теперь для всех свободных клеток рабочей матрицы затрат вычислим оценки Sij, по формуле Sij = Pij – Ui - Vj
b1
b2
b3
b4
a1
1 7 2 5 u1= 0
a2
2 7 1 1 u2= 1
a3
3 3 5 3 u3= 3
a4
0 0 -2 0 u4= 0
v1= 0
v2= 0
v3= 2
v4= 0
Из всех отрицательных оценок имеет смысл выбрать наибольшую по модулю
b1= 20
b2= 18
b3= 44
b4= 75
a1= 40
40
a2= 30
30
a3= 50
1
+
4
-
45
a4= 37
20
17
-
+
b1= 20
b2= 18
b3= 44
b4= 75
a1= 40
40
a2= 30
30
a3= 50
5 45
a4= 37
20 13 4
Рабочая матрица затрат с пересчитанными потенциалами и оценкам.
b1
b2
b3
b4
a1
-1 5 2 3 u1= 2
a2
2 7 3 1 u2= 1
a3
3 3 2 3 u3= 3
a4
0 0 0 0 u4= 0
v1= 0
v2= 0
v3= 0
v4= 0
b1= 20
b2= 18
b3= 44
b4= 75
a1= 40
+
40
-
a2= 30
30
a3= 50
5
45
a4= 37
20
-
13
4
+
b1= 20
b2= 18
b3= 44
b4= 75
a1= 40
20 20
a2= 30
30
a3= 50
5 45
a4= 37
13 24
Рабочая матрица затрат с пересчитанными потенциалами и оценкам.
b1
b2
b3
b4
a1
1 5 2 3 u1= 2
a2
3 7 3 1 u2= 1
a3
4 3 2 3 u3= 3
a4
1 0 0 0 u4= 0
v1= -1
v2= 0
v3= 0
v4= 0
В приведенной выше таблице нет отрицательных оценок (план улучшить нельзя), следовательно достигнуто оптимальное решение.
b1= 20
b2= 18
b3= 44
b4= 75
a1= 40
20
1
20
2
a2= 30
30
1
a3= 50
5
3
45
3
a4= 37
13
0
24
0
Общие затраты на перевозку всей продукции, для оптимального плана составляют:
Pопт= 240
Ответ:
Х=2002000003005045013240
Ххчч
Рmin = 240 ден ед
Задать вопрос
на новый заказ в Автор24.
