Решить транспортную задачу методом потенциалов
.pdf
Зарегистрируйся в 2 клика в Кампус и получи неограниченный доступ к материалам с подпиской Кампус+ 🔥
Решить транспортную задачу методом потенциалов. Первоначальный опорный план составьте методом северо-западного угла. Имеются три ткацких фабрики А1, А2 и А3 , которые поставляют ткань на три швейные фабрики в пределах России В1, В2 и В3. Известны запасы ткани на каждой ткацкой фабрике (в рулонах) и потребности в ней на каждой швейной фабрике. Известна также стоимость перевозки одного рулона ткани (у. е.) от каждого поставщика к каждому потребителю. Найти такой план перевозок, при котором суммарные затраты оказались бы минимальными.
Нужно полное решение этой работы?
Решение
Рассмотрим выполнение условия баланса:
Условие баланса не выполнено, введем фиктивного потребителя мощностью В4 = 56 – 40 = 16. Начальный план строим методом «минимального элемента». Первая таблица:
-5524563500 Вj
Аi
20 12 8
16 Ui
22
7
3
3
0
12 10
18
8
4
2
0
2
12
16
2
3
1
0
8
8
Vj
Задачу решаем методом потенциалов.
Теперь определим потенциалы Ui, Vj из условий для заполненных клеток:
Вычисляем потенциалы:
U1 = 0; U2 = -2; U3 = -5;
V1 = 7; V2 = 6; V3 = 6; V4 = 2.
Определим суммы потенциалов для незаполненных клеток, запишем в левом правом их углу.
-5524563500 Вj
Аi
20 12 8
16 Ui
22
7
3 6 3 2 0 0
350520831852667009080512 - 10 70866060325 +
18 5 8
4 4 2
0 -2
2
16
16
2 1 3
1 -3 0 -5
8 + -8801104254500 8 -
Vj
7 6 6 2
Для клетки (1; 3) организуем перестановку, поскольку:
, при этом величина перестановки Q = 10
.
Изобразим в таблице:
-5524563500 Вj
Аi
20 12 8
16 Ui
22
7
3
3 2 0 0
4 16764011747516002011747510 - 8 79248079375 +
18 5 8
4 1 2
0 -2
274320450852 +
16 -
16
2 1 3 -2 1 -3 0 -5
16
Vj
7 6 3 2
Снова определили все потенциалы и их суммы для незаполненных клеток. Для клетки (1, 4) строим перестановку. Получаем:
-5524563500 Вj
Аi
20 12 8
16 Ui
22
7 4 3
3
0 0
4
1447801447801295401600208 - 76200013716010 +
18 7 8
4 3 2
0 0
12 15621014287500 + 6 -
16
2 -1 3 -2 1 -5 0 -5
16
Vj
7 4 3 0
Снова определили все потенциалы и их суммы для незаполненных клеток