На трех базах А1, А2, А3 находится однородный груз в количестве а1, а2, а3 т. Этот груз необходимо развести пяти потребителям В1, В2, В3, В4, В5, потребности которых в данном грузе составляют b1, b2, b3, b4, b5 т соответственно .Стоимость перевозок пропорциональна расстоянию и количеству перевозимого груза (Решение → 14245)

Заказ №38664

На трех базах А1, А2, А3 находится однородный груз в количестве а1, а2, а3 т. Этот груз необходимо развести пяти потребителям В1, В2, В3, В4, В5, потребности которых в данном грузе составляют b1, b2, b3, b4, b5 т соответственно. Стоимость перевозок пропорциональна расстоянию и количеству перевозимого груза. Матрица тарифов и значений ai, bj приведены в таблице: Таблица 1 Транспортная таблица В1 В2 В3 В4 В5 Запасы А1 16 19 12 25 12 150 А2 22 13 19 14 23 150 А3 14 28 8 18 41 200 Потребности 70 100 30 120 180 60 Требуется спланировать перевозки так, чтобы их стоимость была минимальной.

Решение:

1. Сформулируем экономико-математическую модель задачи Определим тип транспортной задачи аi –наличие груза на базах; bj –потребности потребителей. Рассчитываем суммарные потребности и общее наличие груза: 150 150 200 500 3 1      i аi 70 100 30 120 180 500 5 1        j bj Поскольку   3 i 1 i а  5 j 1 j b , то данная задача закрытого типа (сбалансированная). Т.е. со всех баз будут вывезены запасы груза и все запросы потребителей будут удовлетворены. Введем переменные: хij – количество груза, вывезенного с i – й базы j-му потребителю. Составим целевую функцию:     n j m i ij ij f x C x 1 1 ( ) min 14 28 8 18 41 min ( ) 16 19 12 25 12 22 13 19 14 23 31 32 33 34 35 11 12 13 14 15 21 22 23 24 25                  x x x x х f x x x x х x x x x х 11 12 18 34 41 35 16x 19x  ...  x  x - стоимость перевозки груза от всех поставщиков всем потребителям Введем ограничения: - по строкам 11 12 13 14 15 x  x  x  x  х - количество единиц груза с 1-й базы всем потребителям. 21 22 23 24 25 x  x  x  x  х - количество единиц груза от со 2-й базы всем потребителям. 31 32 33 24 35 x  x  x  x  х - количество единиц груза с 3-й базы всем потребителям. Т.к. от всех поставщиков будет вывезен груз, то в ограничениях по строкам знак « = » - по столбцам 11 21 31 x  x  x - количество единиц груза со всех баз 1-му потребителю. 61 12 22 32 x  x  x - количество единиц груза со всех баз 2-му потребителю. 13 23 33 x  x  x - - количество единиц груза со всех баз 3-му потребителю. 14 24 34 x  x  x - - количество единиц груза со всех баз 4-му потребителю. 15 25 35 x  x  x - - количество единиц груза со всех баз 4-му потребителю. Т.к. все потребности потребителей будут удовлетворены, то в ограничениях по столбцам – знак «=» Поскольку количество груза не может быть отрицательным числом, то вводим прямое ограничение: xij  0. Система ограничений имеет вид: 150 x11  x12  x13  x14  х15  150 x21  x22  x23  x24  х25  200 x31  x32  x33  x34  х35  70 x11  x21  x31  100 x12  x22  x32  30 x13  x23  x33  120 x14  x24  x34  180 x15  x25  x35  x  0(i 1,3; j 1,5) ij 2. Найдем оптимальное решение задачи методом потенциалов 2.1. Найдем исходное опорное решение методом минимального элемента При нахождении исходного решения по правилу «минимального элемента» в первую очередь заполняют клетки с наименьшим тарифом на перевозку. Наименьший тариф с33 = 8. Тогда x33  min{200;30}  30 - потребности 3-го потребителя полностью удовлетворены, вычеркиваем 3-й столбец. Следующий наименьший тариф из невычеркнутых с15 = 12. x15  min{150;180} 150 - с 1-ой базы вывезен весь груз, вычеркиваем 1-ю строку. Следующий наименьший тариф из невычеркнутых с22 = 13. 62 x22  min{150;100} 100 - потребности 2-го потребителя полностью удовлетворены, вычеркиваем 2-й столбец. Следующий наименьший тариф из невычеркнутых с24 = с31 = 14. x24  min{150 100;120}  50 со 2-ой базы вывезен весь груз, вычеркиваем 2-.ю строку. x31  min{200  30;70}  70 - потребности 1-го потребителя полностью удовлетворены, вычеркиваем 1-й столбец. Следующий наименьший тариф из невычеркнутых с34 = 18. x34  min{200  70  30;120  50}  70 - потребности 4-го потребителя полностью удовлетворены, вычеркиваем 4-й столбец. Оставшиеся 30 единиц груза отправляются в клетку (3;5): x35  min{200