Решите транспортную задачу линейного программирования
.pdf
Зарегистрируйся в 2 клика в Кампус и получи неограниченный доступ к материалам с подпиской Кампус+ 🔥
Решите транспортную задачу линейного программирования
Имеются три пункта поставки однородного груза А1, А2, А3 и пять пунктов потребления этого груза В1, В2, В3, В4, В5. На пунктах поставки Аi,
i = находится груз соответственно в количествах а1, а2 и а3 тонн. В пункты потребления Вj, j = требуется доставить соответственно b1, b2, b3, b4 и b5 тонн груза. Расходы на перевозку единицы груза между пунктами поставки и пунктами потребления приведены в таблице.
Найти такой план закрепления потребителей за поставщиками однородного груза хij, i = ; j = , чтобы общие затраты по перевозкам были минимальными.
5.8.
Вj
Ai В1
В2
В3 В4
В5 Запасы
А1
22 14 16 28 30 350
А2
19 17 26 36 36 200
А3 37 30 31 39 41 300
Потребности 170 140 200 195 145 850
Нужно полное решение этой работы?
Решение
I=13ai=350+200+300=850;
i=15bj=170+140+200+195+145=850.
Так как i=13ai=i=15bj, следовательно, задача закрытая.
Построим начальный базисный план методом минимальной стоимости. Назначение перевозок начинаем с клетки (1;2), имеющей минимальную стоимость перевозки 1. В клетку (1;2) записываем наименьшее из значений a1 и b2 x12=min350;140=140 и исключаем из дальнейшего рассмотрения второй столбец. Вычеркнув второй столбец, корректируем запасы первого поставщике на величину x12=140, a1=350-140=210. Следующая поставка осуществляется от первого поставщика третьему потребителю. В клетку (1;3) назначаем перевозку x13=min210;200=200, исключаем из дальнейшего рассмотрения третьего потребителя. Корректируем запасы первого поставщика a1=210-200=10. С оставшейся матрицей поступаем аналогично предыдущему:
x21=min200;170=170; a2=200-170=30;b1=170-170=0;
x24=min30;185=30; a3=30-30=0;b4=185-30=155;
x34=min300;155=155; a3=300-155=145;b4=155-155=0;
x44=min300;155=155; a4=300-155=145;b4=155-155=0;
x45=min145;145=145; a4=145-145=0;b5=145-145=0.
План перевозок, построенный методом минимальной стоимости:
bj
ai
170 140 200 195 145
350 22
14
140 16
200 28
10 30
200
19
170 17 26 36
30 36
300 37
30 31 39
155 41
145
Суммарные затраты, соответствующие данному плану X0 равны
ZX0=14∙140+16∙200+28∙10+19∙170+36∙30+39∙155+41∙145=21740 ден
. ед.
Построенный начальный план перевозок является невырожденным, так как число назначенных перевозок xij равно m+n-1=3+5-1=7.
С помощью метода потенциалов вычислим потенциалы строк и столбцов по стоимости перевозок в загруженных клетках [2]. Если известен ui, то vj=cij-ui, если известен vj, то ui=cij-vj. Положим, например, u1=0. Тогда будут вычислены и остальные потенциалы строк и столбцов.
u1=0;
v2=c12-u1=14-0=14;
v3=c13-u1=16-0=16;
v4=c14-u1=28-0=28;
u2=c24-v4=36-28-8;
v1=c21-u2=19-8=11;
u3=c34-v4=39-28=11;
v5=c35-u3=41-11=30.
vj
ui v1=11
v2=14
v3=16
v4=28
v5=30
u1=0
22
14 -
140 16
200 28 +
10 30
u2=8
19
170 17 + 26 36 -
30 36
u3=11
37
30 31 39
155 41
145
Для незагруженных клеток вычислим величины превышения стоимости ∆ij=cij-ui-vj:
∆11=22-0-11=11; ∆15=30-0-30=0;
∆22=17-8-14=-5<0; ∆23=26-8-16=2;
∆25=36-8-30=-2<0; ∆31=37-11-11=15;
∆32=30-11-14=5; ∆33=31-11-16=4.
Полученный план не оптимален
Задать вопрос
на новый заказ в Автор24.
