Имеются три пункта поставки однородного груза 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
Найти такой план закрепления потребителей за поставщиками однородного груза, чтобы общие затраты по перевозкам были минимальными.
5. a1=200 a2=250a3=200
b1=120 b2=100b3=120b4=110b5=130
D=241827272633182123273231213134
Нужно полное решение этой работы?
Решение
Занесем исходные данные задачи в распределительную таблицу.
Bj
Ai B1 B2 B3 B4 B5 запасы
A1 24 27 18 27 21 200
A2 18 26 21 32 31 250
A3 27 33 23 31 34 200
потребители 120 100 120 110 130
Проверим условие разрешимости задачи.
A=i=1mai=650; B=j=1nbj=580.
Как видно, суммарная потребность груза в пунктах назначения меньше запасов груза на базах. Следовательно, модель исходной транспортной задачи является открытой. Чтобы получить закрытую модель, введем дополнительную потребность, равной 70. Тарифы перевозки единицы груза к этому магазину полагаем равны нулю.
Занесем исходные данные задачи в распределительную таблицу.
Bj
Ai B1 B2 B3 B4 B5 B6 запасы
A1 24 27 18 27 21 0 200
A2 18 26 21 32 31 0 250
A3 27 33 23 31 34 0 200
потребители 120 100 120 110 130 70
Составим первый план транспортной задачи методом наименьшей стоимости.
Суть метода заключается в том, что из всей таблицы стоимостей выбирают наименьшую, и в клетку, которая ей соответствует, помещают меньшее из чисел ai, или bj.
Bj
Ai B1 B2 B3 B4 B5 B6 запасы
A1 24 27 18
120 27 21
80 0 200
A2 18
120 26
100 21 32 31
30 0 250
A3 27 33 23 31
110 34
20 0
70 200
потребители 120 100 120 110 130 70
Подсчитаем число занятых клеток таблицы, их 8, а должно быть m + n - 1 =87. Следовательно, опорный план является невырожденным. Значение целевой функции для этого опорного плана равно:
FX0=18∙120+21∙80+18∙120+26∙100+31∙30+31∙110+34∙20+0∙70=13620
Оптимизируем план производства и организации перевозок методом потенциалов
. Составим систему уравнений для определения потенциалов
α1+β3=18
α1+β5=21
α2+β1=18
α2+β2=26
α2+β5=31
α3+β4=31
α3+β3=23
α3+β6=0
Проверим оптимальность опорного плана. Найдем потенциалы αi, βj. по занятым клеткам таблицы, в которых αi+βj=cij, полагая, что α1=0.
α1=0; α2=10; α3=13
β1=8; β2=16; β3=18; β4=18; β5=21; β6=-13
Вычислим оценки ∆st свободных переменных (свободных клеток):
∆11=24-0-8=16; ∆12=27-0-16=11; ∆14=27-0-18=90; ∆16=0-0+13=13
∆23=21-10-18=-7; ∆24=32-10-18=4; ∆25=0-10+13=3
∆31=27-13-8=6; ∆32=33-13-16=4; ∆33=23-13-18=-8
Опорный план не является оптимальным, так как существуют отрицательные оценки свободных клеток.
Выбираем максимальную оценку свободной клетки 3;3: ∆33=-8.
Для этого в клетку (3;3) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-».
Bj
Ai B1 B2 B3 B4 B5 B6 запасы
A1 24 27 - 18
149860444500149860508000120 27 + 21
9969557150080 0 200
A2 18
120 26
100 21 32 31
30 0 250
A3 27 33 14986018796000+ 23 31
110 - 34
20 0
70 200
потребители 120 100 120 110 130 70
Цикл приведен в таблице 3,3→3,5→1,5→1,3.
Из грузов, стоящих в минусовых клетках, выбираем наименьшее.
Прибавляем 20 к объемам грузов, стоящих в плюсовых клетках и вычитаем из стоящих в минусовых клетках. В результате перемещения числа k=20 по циклу получим новую распределительную таблицу, в которой клетка 3;3 стала занятой.
Bj
Ai B1 B2 B3 B4 B5 B6 запасы
A1 24 27 18
100 27 21
100 0 200
A2 18
120 26
100 21 32 31
30 0 250
A3 27 33 23
20 31
110 34 0
70 200
потребители 120 100 120 110 130 70
Оптимизируем план производства и организации перевозок методом потенциалов
Задать вопрос
на новый заказ в Автор24.
