Решить транспортную задачу используя рассмотренные методы
.pdf
Зарегистрируйся в 2 клика в Кампус и получи неограниченный доступ к материалам с подпиской Кампус+ 🔥
Решить транспортную задачу, используя рассмотренные методы. Три предприятия данного экономического района могут производить некоторую однородную продукцию в количествах, соответственно равных А1, А2 и А3 ед. Эта продукция должна быть поставлена пяти потребителям в количествах, соответственно равных В1, В2, В3, B4 и В5 ед. Затраты, связанные с производством и доставкой продукции, задаются матрицей С.
A1=280, A2=160, A3=170
B1=90, B2=140, B3=60, B4=110, B5=210
C=71241566138 655374
Нужно полное решение этой работы?
Ответ
X*=70060201400000 11040000170
F(x) = 7*70 + 4*60 + 6*110 + 5*40 + 1*20 + 5*140 + 4*170 = 2990
Решение
Проверим условие разрешимости транспортной задачи:
i=13ai=280+160+170=610
j=15bj=90+140+60+110+210=610
Т.к. ai=bj, то имеем ТЗ закрытого типа.
Составим математическую модель:
xij > 0, i=1,2,3, j=1..5
x11+x12+x13+x14+x15=280x21+x22+x23+x24+x25=160x31+x32+x33+x34+x35=170x11+x21+x31=90x12+x22+x32=140x13+x23+x33=60x14+x24+x34=110x15+x25+x35=210
F = 7x11 + 12x12 + 4x13 + 6x14 + 5x15 + x21 + 5x22 + 6x23 + 5x24 + 3x25 + 6x31 + 13x32+ 8x33+ 7x34 + 4x35 min
Найдем исходный опорный план методом наименьшей стоимости.
90 140 60 110 210
280
7 110 12 60 4 110 6
5
160 90 1
5
6
5 70 3
170
6 30 13
8
7 140 4
Т.о. мы получили первый опорный план:
X0=01106090000300 11000700140
Проверим число базисных клеток. В общем случае их должно быть: m+n-1=7 шт., т.е. заполненных клеток должно быть 7 штук. В таблице это выполняется, значит, исходный опорный план найден верно. Найдем значение целевой функции
F(x) = 12*110 + 4*60 + 6*110 + 1*90 + 3*70 + 13*30 + 4*140 = 3470
Проверим полученный план на оптимальность
. Для этого найдем значение потенциалов поставщиков и потребителей Ui и Vj соответственно (потенциалы находим только для базисных клеток) по формуле Ui Vj Cij, полагая, что U1=0. Составим и решим следующую систему:
U1+V2=12; V2=12U3+V2=13; U3=1U3+V5=4; V5=3U2+V5=3; U2=0U2+V1=1; V1=1U1+V3=4; V3=4U1+V4=6; V4=6
Найдем оценки свободных клеток по формуле: ij Ui Vj Cij:
11=0+1-7=-615=0+3-5=-222=0+12-5=723=0+4-6=-2
24=0+6-5=131=1+1-6=-433=1+4-8=-334=1+6-7=0
Т.к. среди оценок есть положительные, то план X0 не оптимальный. Строим цикл пересчета для свободной клетки (2;2): 2;22;53;53;2. Определим значение Q; Q min30;70 30
90 140 60 110 210
280
7 110 12 60 4 110 6
5
160 90 1 252978141826 5
6
5 70 3
[+Q]
[-Q]
170
6 30 13
8
7 140 4
[-Q]
[+Q]
Прибавляем 30 к объемам грузов, стоящих в плюсовых клетках, и вычитаем 30 из xij, стоящих в минусовых клетках. В результате получим новый опорный план:
90 140 60 110 210
280
7 110 12 60 4 110 6
5
160 90 1 30 5
6
5 40 3
170
6
13
8
7 170 4
Проверим оптимальность опорного плана.
U1+V2=12; V2=12U2+V2=5; U2=-7U2+V1=1; V1=8U2+V5=3; V5=10U3+V5=4; U3=-6U1+V3=4; V3=4U1+V4=6; V4=6
11=0+8-7=115=0+10-5=523=-7+4-6=-924=-7+6-5=-6
31=-6+8-6=-432=-6+12-13=-733=-6+4-8=-1034=-6+6-7=-7
Т.к
Задать вопрос
на новый заказ в Автор24.
