Имеются три пункта поставки однородного груза 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=300 a2=250a3=200
b1=210 b2=150b3=120b4=135b5=135
D=49384161311102917174
Нужно полное решение этой работы?
Решение
Занесем исходные данные задачи в распределительную таблицу.
Bj
Ai B1 B2 B3 B4 B5 запасы
A1 4 8 13 2 7 300
A2 9 4 11 9 17 250
A3 3 16 10 1 4 200
потребители 210 150 120 135 135
Проверим условие разрешимости задачи.
A=i=1mai=750; B=j=1nbj=750.
Как видно, суммарная потребность груза в пунктах назначения равна запасам груза. Следовательно, модель исходной транспортной задачи является замкнутой.
Составим первый план транспортной задачи методом наименьшей стоимости. Заполнение клеток таблицы начнем с левой верхней клетки.
Bj
Ai B1 B2 B3 B4 B5 запасы
A1 4
145 8 13
20 2 7
135 300
A2 9 4
150 11
100 9 17 250
A3 3
65 16 10 1
135 4 200
потребители 210 150 120 135 135
Подсчитаем число занятых клеток таблицы, их 7, а должно быть m + n - 1 =7. Следовательно, опорный план является невырожденным.
Значение целевой функции для этого опорного плана равно:
FX0=4∙145+13∙20+7∙135+4∙150+11∙100+3∙65+1∙135=3815
Оптимизируем план производства и организации перевозок методом потенциалов. Составим систему уравнений для определения потенциалов
α1+β1=4
α1+β3=13
α1+β5=7
α2+β2=4
α2+β3=11
α3+β1=3
α3+β4=1
Проверим оптимальность опорного плана. Найдем потенциалы αi, βj. по занятым клеткам таблицы, в которых αi+βj=cij, полагая, что α1=0.
α1=0; α2=-2; α3=-1
β1=4; β2=6; β3=13; β4=2; β5=7
Вычислим оценки ∆st свободных переменных (свободных клеток):
∆12=8-0-6=2; ∆14=2-0-2=0
∆21=9+2-4=7; ∆24=9+2-2=9
∆25=17+2-7=12; ∆32=16+1-6=11
∆33=10+1-13=-2; ∆35=4+1-7=-2
Опорный план не является оптимальным, так как существуют отрицательные оценки свободных клеток.
Выбираем максимальную оценку свободной клетки 3;3: ∆33=-2.
Для этого в клетку (3;3) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-».
Bj
Ai B1 B2 B3 B4 B5 запасы
A1 + 4
145 8 - 13
20 2 7
135 300
A2 9 4
150 11
100 9 17 250
A3 - 3
65 16 + 10 1
135 4 200
потребители 210 150 120 135 135
Цикл приведен в таблице 3,3→3,1→1,1→1,3.
Из грузов, стоящих в минусовых клетках, выбираем наименьшее, то есть вычислим число k=min20;65=20.
Прибавляем 20 к объемам грузов, стоящих в плюсовых клетках и вычитаем из стоящих в минусовых клетках
. В результате перемещения числа k=20 по циклу получим новую распределительную таблицу, в которой клетка 3;3 стала занятой.
Bj
Ai B1 B2 B3 B4 B5 запасы
A1 4
165 8 13 2 7
135 300
A2 9 4
150 11
100 9 17 250
A3 3
45 16 10
20 1
135 4 200
потребители 210 150 120 135 135
Оптимизируем план производства и организации перевозок методом потенциалов. Составим систему уравнений для определения потенциалов
α1+β1=4
α1+β5=7
α2+β2=4
α2+β3=11
α3+β1=3
α3+β3=10
α3+β4=1
Проверим оптимальность опорного плана. Найдем потенциалы αi, βj. по занятым клеткам таблицы, в которых αi+βj=cij, полагая, что α1=0.
α1=0; α2=0; α3=-1
β1=4; β2=4; β3=11; β4=2; β5=7
Вычислим оценки ∆st свободных переменных (свободных клеток):
∆12=8-0-4=4; ∆13=13-0-11=2; ∆14=2-0-2=0
∆21=9-0-4=5; ∆24=9-0-2=7; ∆25=17-0-7=10
∆32=16+1-4=13; ∆35=4+1-7=-2
Опорный план не является оптимальным, так как существуют отрицательные оценки свободных клеток.
Выбираем максимальную оценку свободной клетки (3;5): ∆35=-4.
Для этого в клетку (3;5) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-».
Bj
Ai B1 B2 B3 B4 B5 запасы
A1 + 4
165 8 13 2 - 7
135 300
A2 9 4
150 11
100 9 17 250
A3 - 3
45 16 10
20 1
135 + 4 200
потребители 210 150 120 135 135
Цикл приведен в таблице 3,5→3,1→1,1→1,5.
Из грузов, стоящих в минусовых клетках, выбираем наименьшее
Задать вопрос
на новый заказ в Автор24.
