Имеются три пункта поставки однородного груза A1
.pdf
Зарегистрируйся в 2 клика в Кампус и получи неограниченный доступ к материалам с подпиской Кампус+ 🔥
Имеются три пункта поставки однородного груза A1, A2, A3 и пять пунктов B1, B2, B3, B4, B5 потребления этого груза. На пунктах A1, A2 и A3 находится груз соответственно в количестве a1, a2 и a3 тонн. В пункты B1, B2, B3, B4, B5 требуется доставить соответственно b1, b2, b3, b4, b5 тонн груза. Расстояние между пунктами поставки и пунктами потребления приведено в таблице:
Пункты
поставки Пункты потребления
B1 B2 B3 B4 B5
A1 D11 D12 D13 D14 D15
A2 D21 D22 D23 D24 D25
A3 D31 D32 D33 D34 D35
Найти такой план закрепления потребителей за поставщиками однородного груза, чтобы общие затраты по перевозкам были минимальными.
a1=200, a2=250, a3=200,
b1=190, b2=100, b3=120, b4=110, b5=130.
D=281827 272633 182723 273231 242134.
Нужно полное решение этой работы?
Решение
Проверим задачу на сбалансированность:
i=13ai=200+250+200=650;
i=15bj=190+100+120+110+130=650.
Так как i=13ai=i=15bj, следовательно, задача закрытая.
Построим начальный базисный план методом минимальной стоимости. Назначение перевозок начинаем с клетки (1;3), имеющей минимальную стоимость перевозки 18. В клетку (1;3) записываем наименьшее из значений a1 и b3 x13=min200;120=120 и исключаем из дальнейшего рассмотрения третий столбец. Вычеркнув третий столбец, корректируем запасы первого поставщика на величину x13=120, a1=200-120=80. Следующая поставка осуществляется от второго поставщика первому потребителю. В клетку (2;1) назначаем перевозку x21=min250;190=190, исключаем из дальнейшего рассмотрения первого потребителя. Корректируем запасы второго поставщика a2=250-190=60. С оставшейся матрицей поступаем аналогично предыдущему:
x25=min60;130=60; a2=60-60=0;b5=130-60=70;
x15=min80;70=70; a1=80-70=10;b5=70-70=0;
x12=min10;100=10; a1=10-10=0;b2=100-10=90;
x34=min200;110=110; a3=200-110=90;b4=110-110=0;
x32=min90;90=90; a3=90-90=0;b2=90-90=0.
План перевозок, построенный методом минимальной стоимости:
bj
ai
190 100 120 110 130
200 28
27
10 18
120 27
24
70
250 18
190 26 27 32
21
60
200 27
33
90 23 31
110 34
Суммарные затраты, соответствующие данному плану X0 равны
FX0=10∙27+120∙18+70∙24+190∙18+60∙21+90∙33+110∙31=15170 усл
. ед.
Построенный начальный план перевозок является невырожденным, так как число назначенных перевозок xij равно m+n-1=3+5-1=7.
С помощью метода потенциалов вычислим потенциалы строк и столбцов по стоимости перевозок в загруженных клетках. Если известен ui, то vj=cij-ui, если известен vj, то ui=cij-vj. Положим, например, u1=0. Тогда будут вычислены и остальные потенциалы строк и столбцов.
u1=0;
v2=c12-u1=27-0=27;
v3=c13-u1=18-0=18;
v5=c15-u1=24-0=24;
u2=c25-v5=21-24=-3;
v1=c21-u2=18-(-3)=21;
u3=c32-v2=33-27=6;
v4=c34-u3=31-6=30.
vj
ui v1=21
v2=27
v3=18
v4=25
v5=24
u1=0
28
27 +
10 18 -
120 27
24
70
u2=-3
18
190 26 27 32
21
60
u3=6
27
33 -
90 23 + 31
110 34
Для незагруженных клеток вычислим величины превышения стоимости ∆ij=cij-ui-vj:
∆11=28-0-21=7; ∆14=27-0-25=2;
∆22=26--3-27=2; ∆23=27--3-18=12;
∆24=32--3-25=10; ∆31=27-6-21=0;
∆33=23-6-18=-1<0; ∆35=34-6-24=4.
Полученный план не оптимален
Задать вопрос
на новый заказ в Автор24.
