Однородный груз сосредоточен у трех поставщиков в объемах a1, a2, a3. Данный груз необходимо доставить четырем потребителям, потребности которых составляют b1, b2, b3, b4 соответственно. Стоимости перевозок единицы груза от каждого поставщика к каждому потребителю заданы матрицей C. Требуется составить план перевозок, обеспечивающий минимальные суммарные затраты на перевозку.
a) a1=150;a2=200;a3=100; b1=150;b2=105; b3=90; b4=105C=152310171412132416 172012; б) a1=200;a2=300;a3=190; b1=190;b2=210;b3=180; b4=170C=262516322025262534 233332
Решение
Занесем исходные данные задачи в распределительную таблицу.
Bj
Ai B1 B2 B3 B4 запасы
A1 15 23 10 17 150
A2 17 14 12 20 200
A3 13 24 16 12 100
потребители 150 105 90 105
Проверим условие разрешимости задачи.
A=i=1mai=150+200+100=450;
B=j=1nbj=150+105+90+105=450.
Как видно, суммарная потребность груза в пунктах назначения равна запасам груза. Следовательно, модель исходной транспортной задачи является закрытой. Занесем исходные данные в распределительную таблицу.
Составим первый план транспортной задачи методом наименьшей стоимости. Заполнение клеток таблицы начнем с левой верхней клетки.
Bj
Ai B1 B2 B3 B4 запасы
A1 15
60 23 10
90 17 150
A2 17
90 14
105 12 20
5 200
A3 13 24 16 12
100 100
потребители 150 105 90 105
Подсчитаем число занятых клеток таблицы, их 6, а должно быть m + n - 1 =3+4-1=7-1=8
. Следовательно, опорный план является невырожденным.
Запишем исходное опорное решение в виде матрицы перевозок
X0=6009090105000005100
Значение целевой функции для этого опорного плана равно:
FX0=15∙60+10∙90+17∙90+14∙105+20∙5+12∙10=6100
Оптимизируем план производства и организации перевозок методом потенциалов. Составим систему уравнений для определения потенциалов
α1+β1=15
α1+β3=10
α2+β1=17
α2+β2=14
α2+β4=20
α3+β4=12
Проверим оптимальность опорного плана. Найдем потенциалы αi, βj. по занятым клеткам таблицы, в которых αi+βj=cij, полагая, что α1=0.
α1=0; α2=2; α3=-6
β1=15; β2=12; β3=10; β4=18
Вычислим оценки ∆st свободных переменных (свободных клеток):
∆12=23-0-12=11
∆14=17-0-18=-1
∆23=12-2-10=0
∆31=13+6-15=4
∆32=24+6-12=18
∆33=16+6-10=12
Опорный план не является оптимальным, так как существует отрицательная оценка свободной клетки.
Для этого в клетку (1;4) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-».
Bj
Ai B1 B2 B3 B4 запасы
A1 17843516700500178669167272- 15
60 23 10
90 273685167272+ 17 150
A2 + 17
1786681868290 14
105 12 - 20
5 200
A3 13 24 16 12
100 100
потребители 150 105 90 105
Цикл приведен в таблице 1,4→1,1→2,1→2,4.
Из грузов, стоящих в минусовых клетках, выбираем наименьшее, то есть вычислим число k=min60;5=5.
Прибавляем 5 к объемам грузов, стоящих в плюсовых клетках и вычитаем из стоящих в минусовых клетках
Задать вопрос
на новый заказ в Автор24.
