Транспортная задача

  • 13 марта 2016 г.
  • 1792 Слова
ЗАДАЧА 3 (ЗАКРЫТАЯ ТРАНСПОРТНАЯ ЗАДАЧА)
1 Составить экономическую модель закрытой транспортной задачи (3 поставщика, 5 потребителей).
2 Составить математическую модель закрытой транспортной задачи.
3 Методом наименьшей стоимости построить первоначальный опорный план и вычислить соответствующее ему значение общей стоимости перевозок.
4 Сформулировать двойственную к транспортной задачу и ввести врассмотрение потенциалы пунктов отправления и пунктов назначения.
5 Охарактеризовать метод потенциалов проверки опорного плана транспортной задачи на оптимальность. Проверить, является ли оптимальным первоначальный опорный план рассматриваемой транспортной задачи.
6 Если первоначальный опорный план не является оптимальным, то осуществить переход от одного опорного плана транспортной задачи кдругому? Найти оптимальный план данной транспортной задачи.
Сделать экономические выводы, указав оптимальный план перевозок товара и вычислив минимальную стоимость перевозок.





















1 Экономическая постановка закрытой транспортной задачи
Пусть на трёх базах сосредоточен однородный груз в количествах a1=250, a2=70, a3=170, который нужно перевезти в пять пунктов назначения в количествах b1=80,b2=30, b3=200, b4=130, b5=50. Известны стоимости доставок единицы товара с пунктов отправления в пункты назначения, которые задаются матрицей стоимостей перевозок

В предположении, что весь товар должен быть вывезен из пунктов отправки и все потребности пунктов назначения будут удовлетворены, требуется так организовать доставку товара, чтобы общая стоимость перевозок была минимальной.
2Математическая формулировка закрытой транспортной задачи
Обозначим xij – количество единиц товара, что перевозится с пункта отправки Ai в пункт доставки Bj. Если известна стоимость cij перевозки единицы товара из пункта Ai в пункт Bj, то стоимость перевозки количества xij из Ai в Bj, очевидно, равна cijxij, так что общая стоимость перевозок определяется как сумма всех возможных произведений этого вида. Следовательно,целевая функция
(3.1)
Система ограничений на переменные xij вытекает из условий полного вывоза товара из пунктов Ai и полного удовлетворения потребностей пунктов Bj, то есть имеем две группы ограничений:
(3.2)
(3.3)
Считаем, что перевозка товара из пунктов Bj в пункты Ai не допускается, тогда естественно допустить, что все переменные
xij0. (3.4)
Обратим внимание на тот важный факт, что согласно условию задачи сумма всего вывезенного товара из пунктов Ai равна сумме всех поставок в пункты Bj (250+70+170=80+30+200+130+50=490), то есть
(3.5)
Сформулированная задача (3.1)-(3.5) называется транспортной задачей за критерием стоимости с правильным балансом или закрытой транспортной задачей.
Используязаданную матрицу стоимостей перевозок, а также запасы и потребности товара в данном случае получаем следующую задачу линейного программирования:
S 40 x11 19 x12 25 x13 25 x14 35 x15 49 x21 26 x22 27 x23 18 x24 38 x25 
46 x31 27 x32 36 x33 40 x 34 45 x35 min,
(3.7)
xij 0 i 1, 2, 3; j 1, 2, 3, 4, 5. (3.8)Система линейных уравнений (3.7) содержит 8 уравнений с 15 неизвестными. Она имеет бесчисленное множество решений ( перевозки можно осуществлять бесконечным числом способов ). Поскольку суммарные перевозки совпадают с суммарными потребностями, а именно
.
то переменные транспортной задачи связаны дополнительным условием

Это означает, что ранг системы уравнений (3.7) на единицуменьше числа уравнений, то есть r=8-1=7. Тогда 7 переменных будут базисными, остальные 15-7=8 свободными переменными.
Опорный план (базисное решение) данной транспортной задачи будет содержать 7 базисных и 8 свободных переменных, при этом свободные переменные приравниваются нулю.
Поставим в соответствие каждой переменной транспортной задачи определенную...
tracking img