Решение транспортной задачи 3 — страница 2

  • Просмотров 350
  • Скачиваний 5
  • Размер файла 108
    Кб

покрывающий потребности в каждом пункте потребления, при заданной стоимости перевозки единицы транспортируемого продукта между каждой парой пунктов поставки и потребления. Транспортная задача была впервые сформулирована Хитчкоком и с тех пор применяется для решения практических задач доставки и распределения однородных продуктов. Для решения транспортной задачи разработано несколько методов, каждый из которых

отличается от другого методом заполнения матрицы перевозок. Существуют два типа транспортной задачи: открытая и закрытая. Транспортная задача называется открытой если сумма запасов товара на складах отличается от суммы потребностей товаров у магазинов. Транспортная задача называется закрытой, если сумма запасов товара на складах равняется сумме потребностей магазинов. Решение существует только для закрытой транспортной

задачи, поэтому если транспортная задача открытая, то ее надо привести к закрытому типу. Для этого в случае, если запас товара на складах превышает потребность магазинов, то вводят фиктивного потребителя, который выбирает весь избыток товара. В случае же, если существует дефицит товара, т.е. потребность магазинов больше, чем запас товаров на складах, то вводят фиктивного поставщика, с фиктивным запасом товара на складе. В обоих

случаях в матрице тарифов перевозок данному складу или магазину проставляется нулевая цена перевозки. В качестве задания транспортная задача имеет следующий вид: Таблица 1 Фабрика Склады (расходы на 1 партию) Предложение Г Д Е Ж А 20 40 15 30 60 Б 10 25 25 35 100 В 15 45 30 20 80 Спрос 70 50 90 30 240 В таблице 1 приведены расходы на транспортировку партий товаров с трех фабрик (А, Б и В) к четырем складам (Г, Д, Е и Ж). в ней также приведены количество товара на

каждой из фабрик и вместимость складов. Требуется определить маршруты, по которым следует направлять товары, чтобы минимизировать общие расходы. 2 МАТЕМАТИЧЕСКОЕ ОБЕСПЕЧЕНИЕ 2.1 Математическая модель Имеется m пунктов поставки (поставщиков) и n пунктов потребления некого однородного продукта. Для каждого поставщика i = 1,...,m задан объем производства Ai, а для каждого потребителя j = 1,...,n задан объем потребления Bj и известна

стоимость доставки единицы продукта Ci,j из пункта производства i в пункт потребления j. Управляемые параметры Xi,j характеризуют объем перевозки между каждым поставщиком i = 1,...,m и потребителем j = 1,...,n. В случае сбалансированного производства и потребления: A1 + ... + Am = B1 + ... + Bn (1) оптимальный план транспортировки соответствует минимизации линейной целевой функции: (2) при m линейных ограничениях по поставке: Xi,1 + ... + Xi,j + ... + Xi,n =