Четыре овощехранилища каждый день обеспечивают картофелем три магазина. Магазины подали заявки соответственно на 17, 12 и 32 т. Овощехранилища имеют соответственно 20, 20, 15 и 25 т. (Решение → 9802)

заказ №38669

Четыре овощехранилища каждый день обеспечивают картофелем три магазина. Магазины подали заявки соответственно на 17, 12 и 32 т. Овощехранилища имеют соответственно 20, 20, 15 и 25 т. Тарифы (в д.е. за 1 т) указаны в следующей таблице. Овощехранилища Магазины 1 2 3 1 2 7 4 2 3 2 1 3 5 6 2 4 3 4 7 Составить план перевозок, минимизирующий суммарные транспортные расходы. Решить задачу с помощью метода потенциалов.

Решение

Математическая модель задачи имеет вид Математическая модель транспортной задачи имеет вид: Пусть ij x - количество груза, которое доставляется с пункта отправления Ai в пункт назначения Bj, а ij c тарифы на доставку единицы груза с пункта отправления Ai потребителю Bj, i a - запасы груза на складе Ai, bj – потребность груза в магазине Bj. Тогда математическая модель транспортной задачи имеет вид: Z= min 1 1      n i m j ij ij c x   n i ij j x b 1   m j ij ai x 1 348      m j i n i ai b 1 1 Данная задача носит не замкнутый характер, т.к.      m j i n i ai b 1 1 20+20+15+25=80≠17+12+32=61 Введем еще один виртуальный магазин, потребность которого равна 80-61=19, а тарифы на доставку от всех овощехранилищ равны нулю. Овощехранилища Магазины Запасы В1 В2 В3 В4 А1 2 7 4 0 20 А2 3 2 1 0 20 А3 5 6 2 0 15 А4 3 4 7 0 25 Потребности 17 12 32 19 80 Найдем опорное решение методом минимальной стоимости, т.е. поставку груза будем производить каждый раз в клетку с минимальной стоимостью доставки Овощехранилища Магазины Запасы В1 В2 В3 В4 А1 2 17 7 4 0 3 20 3 А2 3 2 1 20 0 20 А3 5 6 2 12 0 3 15 3 А4 3 4 12 7 0 13 25 13 Потребности 17 12 32 12 19 80 Дадим поставку 20 ед. в клетку (А2, В3). В А2 больше товара нет – вычеркиваем строку А2. В3 нужно еще 12 ед. Дадим поставку 17 ед. в клетку (А1, В1). В В1 товара больше не нужно, вычеркиваем столбец В1, а в А1 осталось 3 ед. груза. Дадим поставку 12 ед. в клетку (А3, В3). В В3 больше товара не нужно – вычеркиваем столбец В2. На А3 осталось 3 ед. Дадим поставку 12 ед. в клетку (А4, В2). В В2 больше товара не нужно, вычеркиваем В2, а в А4 осталось 13 ед. груза. Распределяем оставшийся груз потребителю В4 Опорное решение получено. Овощехранилища Магазины Запасы В1 В2 В3 В4 А1 2 17 7 4 0 3 20 А2 3 2 + 1 20 - 0 20 А3 5 6 2 12 + 0 3 - 15 А4 3 4 12 - 7 0 13 + 25 Потребности 17 12 32 19 80 х11=17,х14=3, х23=20, х33=12, х34=3, х42=12, х44=13. Z=2*17+1*20+2*12+4*12=126 д.ед. Оптимизируем это опорное решение методом потенциалов. Составим систему уравнений для потенциалов в заполненных клетках. u1+v1=2, u1+v4=0, u2+v3=1, u3+v3=2, u3+v4=0, u4+v2=4, u4+v4=0. u1=0, v1=2, v4=0, u3=0,v2=4, u4=0, v3=2, u2=-1. Проверим выполнение неравенств для незаполненных клеток. u1+v2=42, u2+v4=-1<0, u3+v1=2<5, u3+v2=4<6, u4+v1=2<3, u4+v3=2<7.

Четыре овощехранилища каждый день обеспечивают картофелем три магазина. Магазины подали заявки соответственно на 17, 12 и 32 т. Овощехранилища имеют соответственно 20, 20, 15 и 25 т.

 

Четыре овощехранилища каждый день обеспечивают картофелем три магазина. Магазины подали заявки соответственно на 17, 12 и 32 т. Овощехранилища имеют соответственно 20, 20, 15 и 25 т.

Четыре овощехранилища каждый день обеспечивают картофелем три магазина. Магазины подали заявки соответственно на 17, 12 и 32 т. Овощехранилища имеют соответственно 20, 20, 15 и 25 т.

Четыре овощехранилища каждый день обеспечивают картофелем три магазина. Магазины подали заявки соответственно на 17, 12 и 32 т. Овощехранилища имеют соответственно 20, 20, 15 и 25 т.