Решить транспортную задачу методом потенциалов. Первоначальный опорный план составьте методом северо-западного угла.
Имеется три ткацких фабрики А1, А2 и А3, которые поставляют ткань на три швейные фабрики в пределах России В1, В2 и В3. Известны запасы ткани на каждой ткацкой фабрике (в рулонах) и потребности в ней на каждой швейной фабрике. Известна также стоимость перевозки одного рулона ткани (у. е.) от каждого поставщика к каждому потребителю.
Найти такой план перевозок, при котором суммарные затраты оказались бы минимальными.
Условия (запасы, потребности и цена перевозки каждого рулона ткани) приведены в таблице.
4.07
запас B1 B2 B3
A1 30 9 7 4
A2 15 5 3 2
A3 45 10 8 5
потребность 20 18 17
Решение
Стоимость доставки единицы груза из каждого пункта отправления в соответствующие пункты назначения задана матрицей тарифов
B1 B2 B3 Запасы
A1 9 7 4 30
A2 5 3 2 15
A3 10 8 5 45
Потребности 20 18 17
Проверим необходимое и достаточное условие разрешимости задачи.∑a = 30 + 15 + 45 = 90∑b = 20 + 18 + 17 = 55
Как видно, суммарная потребность груза в пунктах назначения меньше запасов груза на базах. Следовательно, модель исходной транспортной задачи является открытой. Чтобы получить закрытую модель, введем дополнительную (фиктивную) потребность, равной 35 (90-55). Тарифы перевозки единицы груза к этому потребителю полагаем равны нулю.
Занесем исходные данные в распределительную таблицу.
B1 B2 B3 B4 Запасы
A1 9 7 4 0 30
A2 5 3 2 0 15
A3 10 8 5 0 45
Потребности 20 18 17 35
Этап I. Поиск первого опорного плана.
1. Используя метод северо-западного угла, построим первый опорный план транспортной задачи.
План начинается заполняться с верхнего левого угла.
Искомый элемент равен c11=9. Для этого элемента запасы равны 30, потребности 20. Поскольку минимальным является 20, то вычитаем его.x11 = min(30,20) = 20.
9 7 4 0 30 - 20 = 10
x 3 2 0 15
x 8 5 0 45
20 - 20 = 0 18 17 35
Искомый элемент равен c12=7. Для этого элемента запасы равны 10, потребности 18. Поскольку минимальным является 10, то вычитаем его.x12 = min(10,18) = 10.
9 7 x x 10 - 10 = 0
x 3 2 0 15
x 8 5 0 45
0 18 - 10 = 8 17 35
Искомый элемент равен c22=3
. Для этого элемента запасы равны 15, потребности 8. Поскольку минимальным является 8, то вычитаем его.x22 = min(15,8) = 8.
9 7 x x 0
x 3 2 0 15 - 8 = 7
x x 5 0 45
0 8 - 8 = 0 17 35
Искомый элемент равен c23=2. Для этого элемента запасы равны 7, потребности 17. Поскольку минимальным является 7, то вычитаем его.x23 = min(7,17) = 7.
9 7 x x 0
x 3 2 x 7 - 7 = 0
x x 5 0 45
0 0 17 - 7 = 10 35
Искомый элемент равен c33=5. Для этого элемента запасы равны 45, потребности 10. Поскольку минимальным является 10, то вычитаем его.x33 = min(45,10) = 10.
9 7 x x 0
x 3 2 x 0
x x 5 0 45 - 10 = 35
0 0 10 - 10 = 0 35
Искомый элемент равен c34=0. Для этого элемента запасы равны 35, потребности 35. Поскольку минимальным является 35, то вычитаем его.x34 = min(35,35) = 35.
9 7 x x 0
x 3 2 x 0
x x 5 0 35 - 35 = 0
0 0 0 35 - 35 = 0
В результате получен первый опорный план, который является допустимым, так как все грузы из баз вывезены, потребность потребителей удовлетворена, а план соответствует системе ограничений транспортной задачи.
B1 B2 B3 B4 Запасы
A1 9[20] 7[10] 4 0 30
A2 5 3[8] 2[7] 0 15
A3 10 8 5[10] 0[35] 45
Потребности 20 18 17 35
2
Заказать работу
на новый заказ в Автор24.
