Имеются три пункта поставки однородного груза 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=230, a2=250, a3=170,
b1=140, b2=90, b3=160, b4=110, b5=150.
D=404946 192627 252736 251840 353845.
Нужно полное решение этой работы?
Решение
Проверим задачу на сбалансированность:
i=13ai=230+250+170=650;
i=15bj=140+90+160+110+150=650.
Так как i=13ai=i=15bj, следовательно, задача закрытая.
Построим начальный базисный план методом минимальной стоимости. Назначение перевозок начинаем с клетки (2;4), имеющей минимальную стоимость перевозки 18. В клетку (2;4) записываем наименьшее из значений a2 и b4 x24=min250;110=110 и исключаем из дальнейшего рассмотрения четвертый столбец. Вычеркнув третий столбец, корректируем запасы первого поставщика на величину x24=110, a2=250-120=130. Следующая поставка осуществляется от первого поставщика второму потребителю. В клетку (1;2) назначаем перевозку x12=min230;90=90, исключаем из дальнейшего рассмотрения второго потребителя. Корректируем запасы первого поставщика a1=230-90=140. С оставшейся матрицей поступаем аналогично предыдущему:
x13=min140;160=140; a1=140-140=0;b3=160-140=20;
x23=min140;20=20; a2=140-20=120;b2=20-20=0;
x25=min120;150=120; a2=120-120=0;b5=150-120=30;
x35=min170;30=30; a3=170-30=140;b5=30-30=0;
x31=min140;140=140; a3=140-140=0;b1=140-140=0.
План перевозок, построенный методом минимальной стоимости:
bj
ai
140 90 160 110 150
230 40
19
90 25
140 25
35
250 49
26 27
20 18
110 38
120
170 46
140 27
36 40
45
30
Суммарные затраты, соответствующие данному плану X0 равны
FX0=19∙90+25∙140+27∙20+18∙110+38∙120+46∙140+45∙30=20080 усл. ед.
Построенный начальный план перевозок является невырожденным, так как число назначенных перевозок xij равно m+n-1=3+5-1=7
.
С помощью метода потенциалов вычислим потенциалы строк и столбцов по стоимости перевозок в загруженных клетках. Если известен ui, то vj=cij-ui, если известен vj, то ui=cij-vj. Положим, например, u1=0. Тогда будут вычислены и остальные потенциалы строк и столбцов.
u1=0;
v2=c12-u1=19-0=19;
v3=c13-u1=25-0=25;
u2=c23-v3=27-25=2;
v4=c24-u2=18-2=16;
v5=c25-u2=38-2=36;
u3=c35-v5=45-36=9;
v1=c31-u3=46-9=37.
vj
ui v1=37
v2=19
v3=25
v4=16
v5=36
u1=0
40
19 -
90 25 +
140 25
35
u2=2
49
26 27 -
20 18
110 38 +
120
u3=9
46
140 27 +
36 40
45 -
30
Для незагруженных клеток вычислим величины превышения стоимости ∆ij=cij-ui-vj:
∆11=40-0-37=3; ∆14=25-0-16=9;
∆15=35-0-36=-1<0; ∆21=49-2-37=10;
∆22=26-2-19=5; ∆32=27-9-19=-1<0;
∆33=36-9-25=2; ∆34=40-9-16=15.
Полученный план не оптимален. Среди оценок ∆ij имеются отрицательные значения. Потенциальной является клетка 3;2. От клетки 3;2 строим замкнутый контур: 3;2, 1;2, 1;3, 2;3,2;5,(3;5). Начиная с клетки 3;2 разметим вершины контура попеременно знаками плюс «+», минус «-», обходя замкнутый контур в любом направлении. Из клеток, помеченных знаком «-», выбираем наименьшее значение объема перевозки θ=min90;20;30=20. Сформируем новый улучшенный план: на 20 увеличим перевозки в клетках, помеченных знаком «+», и уменьшим в клетках, помеченных знаком «-».
vj
ui v1=38
v2=19
v3=25
v4=17
v5=37
u1=0
40
19 -
70 25
160 25
35 +
u2=1
49
26 27
18
110 38
140
u3=8
46
140 27 +
20 36 40
45 -
10
Определим полную стоимость перевозок по найденному опорному плану:
FX1=19∙70+25∙160+18∙110+38∙140+46∙140+27∙20+45∙10=20060 усл
Задать вопрос
на новый заказ в Автор24.
