На четырех базах Аi находиться однородный груз. Этот граух необходимо развести пяти потребителям Вj , потребности которых в данном грузе равны bjтонн. Стоимость перевозок пропорциональна расстоянию и количеству перевозимого груза. В таблице задана матрица тарифов сij-стоимость перевозки единицы груза от каждой базы каждому потребителю. Запасы поставщиков ai и потребности потребителей bj выбрать в таблицах в соответствии с номером зачетной книжки.
Необходимо спланировать перевозки так, чтобы их общая стоимость была минимальной.
Пункты отправления Пункты назначения Запасы груза
9 10 5 3 6 750
8 4 1 5 9 210
9 3 6 7 1 920
1 8 3 9 5 270
Потребности 530 280 580 910 450
Решение
Проверим необходимое и достаточное условие разрешимости задачи:
a=750+210+920+270=2150,b=530+280+580+910+450=2750a<b.
Суммарная потребность груза больше запасов груза у поставщиков. Следовательно, задача является открытой. Чтобы получить закрытую модель, введем фиктивного поставщика А5 с запасом, равным 2750-2150=600. Тарифы перевозки единицы груза от поставщика всем потребителям положим равными нулю.
Запасы фиктивного поставщика будем рассматривать в последний момент.
Пункты отправления Пункты назначения Запасы груза
9 10 5 3 6 750
8 4 1 5 9 210
9 3 6 7 1 920
1 8 3 9 5 270
0 0 0 0 0 600
Потребности 530 280 580 910 450
Найдем начальное решение методом минимального элемента.
Минимальный элемент матрицы тарифов находится в ячейке A2B3 и равен 1. Запасы поставщика A2 составляют210 ед. Потребность потребителя B3 составляет 580 ед. От поставщика A2 к потребителю B3 будем доставлять 210 ед. Мы полностью исчерпали запасы поставщика А2. Вычеркиваем строку 2 таблицы, т.е. исключаем ее из дальнейшего рассмотрения . Продолжаем аналогичные рассуждения и получим опорное решение
b1= 530
b2= 280
b3= 580
b4= 910
b5= 450
a1= 750
750
3
a2= 210
210
1
a3= 920
210
3
100
6
160
7
450
1
a4= 270
270
3
a5= 600
530
0
70
0
Значение целевой функции для данного опорного плана равно:
F(Х) = 750*3+210*1+210*3+100*6+160*7+450*1+270*3+70*0+530*0=6070ден ед
Число занятых клеток таблицы равно 10, их должно быть m + n - 1 = 10
. Значит, опорный план является невырожденным.
Проведем поэтапное улучшение начального решения, используя метод потенциалов.Составим вспомогательную рабочую матрицу затрат Ui+Vj=Pij
b1
b2
b3
b4
b5
a1
3 u1= -3
a2
1 u2= -4
a3
3 6 7 1 u3= 1
a4
3 u4= -2
a5
0 0 u5= -2
v1= 2
v2= 2
v3= 5
v4= 6
v5= 0
Теперь для всех свободных клеток рабочей матрицы затрат вычислим оценки Sij, по формуле Sij = Pij – Ui - Vj
b1
b2
b3
b4
b5
a1
10 11 3 3 9 u1= -3
a2
10 6 1 3 13 u2= -4
a3
6 3 6 7 1 u3= 1
a4
1 8 3 5 7 u4= -2
a5
0 0 -3 -4 2 u5= -2
v1= 2
v2= 2
v3= 5
v4= 6
v5= 0
Из всех отрицательных оценок имеет смысл выбрать наибольшую по модулю
b1= 530
b2= 280
b3= 580
b4= 910
b5= 450
a1= 750
750
a2= 210
210
a3= 920
210
+
100
160
-
450
a4= 270
270
a5= 600
530
70
-
+
.
b1= 530
b2= 280
b3= 580
b4= 910
b5= 450
a1= 750
750
a2= 210
210
a3= 920
280 100 90 450
a4= 270
270
a5= 600
530 70
Рабочая матрица затрат с пересчитанными потенциалами и оценкам.
b1
b2
b3
b4
b5
a1
6 11 3 3 9 u1= -3
a2
6 6 1 3 13 u2= -4
a3
2 3 6 7 1 u3= 1
a4
-3 8 3 5 7 u4= -2
a5
0 4 1 0 6 u5= -6
v1= 6
v2= 2
v3= 5
v4= 6
v5= 0
Ячейка а4,b1, транспортной таблицы, должна загрузиться.
b1= 530
b2= 280
b3= 580
b4= 910
b5= 450
a1= 750
750
a2= 210
210
a3= 920
280
100
+
90
-
450
a4= 270
+
270
-
a5= 600
530
-
70
+
Ячейка а3,b4 становится свободной.
b1= 530
b2= 280
b3= 580
b4= 910
b5= 450
a1= 750
750
a2= 210
210
a3= 920
280 190 450
a4= 270
90 180
a5= 600
440 160
Рабочая матрица затрат с пересчитанными потенциалами и оценкам.
b1
b2
b3
b4
b5
a1
6 8 0 3 6 u1= 0
a2
9 6 1 6 13 u2= -4
a3
5 3 6 3 1 u3= 1
a4
1 8 3 8 7 u4= -2
a5
0 1 -2 0 3 u5= -3
v1= 3
v2= 2
v3= 5
v4= 3
v5= 0
Ячейка а5,b3, транспортной таблицы, должна загрузиться.
b1= 530
b2= 280
b3= 580
b4= 910
b5= 450
a1= 750
750
a2= 210
210
a3= 920
280
190
450
a4= 270
90
+
180
-
a5= 600
440
-
+
160
Ячейка а4,b3 становится свободной.
b1= 530
b2= 280
b3= 580
b4= 910
b5= 450
a1= 750
750
a2= 210
210
a3= 920
280 190 450
a4= 270
270
a5= 600
260 180 160
Рабочая матрица затрат с пересчитанными потенциалами и оценкам.
b1
b2
b3
b4
b5
a1
6 10 2 3 8 u1= -2
a2
7 6 1 4 13 u2= -4
a3
3 3 6 1 1 u3= 1
a4
1 10 2 8 9 u4= -4
a5
0 3 0 0 5 u5= -5
v1= 5
v2= 2
v3= 5
v4= 5
v5= 0
В приведенной выше таблице нет отрицательных оценок (план улучшить нельзя), следовательно достигнуто оптимальное решение.
b1= 530
b2= 280
b3= 580
b4= 910
b5= 450
a1= 750
750
3
a2= 210
210
1
a3= 920
280
3
190
6
450
1
a4= 270
270
1
a5= 600
260
0
180
0
160
0
Общие затраты на перевозку всей продукции, для оптимального плана составляют:
Pопт= 5160
Таким образом, оптимальный план перевозок груза:
Минимальные общие затраты на перевозку грузов составят:
F(x)min = 750*3+210*1+280*3+190*6+450*1+270*1260*0+180*0+160*0=5160
Ответ
Задать вопрос
на новый заказ в Автор24.
