Проверим необходимое и достаточное условие разрешимости задачи:
a=300+300+250=850b=150+140+115+225+220=850a=b.
Суммарная потребность груза равна запасам груза у поставщиков. Следовательно, задача является закрытой.
Ответ
Оптимальный план Х=120001800014011545030000230
Расходы по его осуществлению минимальны и составляют 12685 руб
Пусть таких этапов будет 4 .
соответсвии с начальными условиями H, I, K.
i=1: F1H=CHL=60, F1H=CIL=90,F1H=CKL=100
Двигаясь по этапам от начала до конца, составляем оптимальный режим движения поезда. Скоростной оптимальный режим: ADFHL при этом минимальные расходы передвижения составят 310 единиц.
Решение
Найдем начальное решение методом наименьшей стоимости.
Минимальный элемент матрицы тарифов находится в ячейке A3B1 и равен 7. Запасы поставщика A3 составляют 250 ед. Потребность потребителя B1 составляет 150 ед. От поставщика A3 к потребителю B1 будем доставлять 150 ед.
Мы полностью исчерпали запасы потребителя B1. Вычеркиваем столбец 1 таблицы, т.е. исключаем ее из дальнейшего рассмотрения. Продолжаем данные рассуждения аналогичным образом получим первоначальный опорный план:
b1= 150
b2= 140
b3= 115
b4= 225
b5= 220
a1= 300
225
16
75
25
a2= 300
140
16
115
17
45
30
a3= 250
150
7
100
9
Проверим полученный опорный план на невырожденность. Количество заполненных клеток N должно удовлетворять условию N=n+m-1 . В нашем случае N=7, n+m=5+3=8 , что удовлетворяет условию невырожденности плана.
Найдем стоимость перевозок:F=225*16+75*25+140*16+115*17+45*30+150*7+100*9=12970
Проведем поэтапное улучшение начального решения, используя метод потенциалов.Составим вспомогательную рабочую матрицу затрат
. Ui+Vj=Pij
b1
b2
b3
b4
b5
a1
16 25 u1= 25
a2
16 17 30 u2= 30
a3
7 9 u3= 9
v1= -2
v2= -14
v3= -13
v4= -9
v5= 0
Порядок вычисления потенциалов был следующий: 1) Пусть V5 = 0 ; 2) U1 = P1,5 - V5 ; 3) U2 = P2,5 - V5 ; 4) U3 = P3,5 - V5 ; 5) V4 = P1,4 - U1 ; 6) V2 = P2,2 - U2 ; 7) V3 = P2,3 - U2 ; 8) V1 = P3,1 - U3 ;Теперь для всех свободных клеток рабочей матрицы затрат вычислим оценки Sij, по формуле Sij = Pij – Ui - Vj
b1
b2
b3
b4
b5
a1
-2 13 9 16 25 u1= 25
a2
2 16 17 -1 30 u2= 30
a3
7 17 15 10 9 u3= 9
v1= -2
v2= -14
v3= -13
v4= -9
v5= 0
Из всех отрицательных оценок имеет смысл выбрать наибольшую по модулю (красный цвет).
b1= 150
b2= 140
b3= 115
b4= 225
b5= 220
a1= 300
+
225
75
-
a2= 300
140
115
45
a3= 250
150
-
100
+
b1= 150
b2= 140
b3= 115
b4= 225
b5= 220
a1= 300
75 225
a2= 300
140 115 45
a3= 250
75 175
Рабочая матрица затрат с пересчитанными потенциалами и оценкам.
b1
b2
b3
b4
b5
a1
21 15 11 16 2 u1= 23
a2
2 16 17 -3 30 u2= 30
a3
7 17 15 8 9 u3= 9
v1= -2
v2= -14
v3= -13
v4= -7
v5= 0
b1= 150
b2= 140
b3= 115
b4= 225
b5= 220
a1= 300
75
+
225
-
a2= 300
140
115
+
45
-
a3= 250
75
-
175
+
b1= 150
b2= 140
b3= 115
b4= 225
b5= 220
a1= 300
120 180
a2= 300
140 115 45
a3= 250
30 220
Рабочая матрица затрат с пересчитанными потенциалами и оценкам.
b1
b2
b3
b4
b5
a1
21 12 8 16 2 u1= 23
a2
5 16 17 20 3 u2= 27
a3
7 14 12 8 9 u3= 9
v1= -2
v2= -11
v3= -10
v4= -7
v5= 0
В приведенной выше таблице нет отрицательных оценок (план улучшить нельзя), следовательно достигнуто оптимальное решение.
b1= 150
b2= 140
b3= 115
b4= 225
b5= 220
a1= 300
120
21
180
16
a2= 300
140
16
115
17
45
20
a3= 250
30
7
220
9
Общие затраты на перевозку всей продукции, для оптимального плана составляют: Fmax=12685
Ответ: Оптимальный план Х=120001800014011545030000230
Расходы по его осуществлению минимальны и составляют 12685 руб
Пусть таких этапов будет 4 .
соответсвии с начальными условиями H, I, K.
i=1: F1H=CHL=60, F1H=CIL=90,F1H=CKL=100
Двигаясь по этапам от начала до конца, составляем оптимальный режим движения поезда
Задать вопрос
на новый заказ в Автор24.
