Транспортная задача. Закрытая и открытая транспортная задача. Метод северо-западного угла

1 Тема 3: ТРАНСПОРТНАЯ ЗАДАЧА 2 План темы 3 «Транспортная задача»: 3.1. Постановка задачи, основные определения 3.2. Закрытая и открытая транспортная задача 3.3. Метод северо-западного угла 3.4. Метод минимального тарифа 3.5. Метод потенциалов 3.1. Постановка задачи, основные определения 3 Цель транспортной задачи - разработка наиболее рациональных путей и способов транспортировки товаров, устранение чрезмерно дальних, встречных и повторных перевозок. 3.1. Постановка задачи, основные определения 4 Исторические этапы исследований транспортной задачи I этап. Задача национального плана перевозок, позволяющего минимизировать суммарный километраж в железнодорожных перевозках при наличии не более двух поставщиков Толстой А. Н. Методы устранения нерациональных перевозок при планировании. Социалистический транспорт, 1939, № 9. II этап. Одну из разновидностей транспортной задачи в 1941 г. Поставил американец Хичкок. Детально разобрал Тьяллинг Чарльз Купманс, который работал членом Объединенного комитета перевозок во время Второй мировой войны. III этап. Первый общий, законченный метод решения транспортной задачи («метод потенциалов») разработан Леонидом Канторовичем. Канторович Л. В., Гавурин М. К., Применение математических методов в вопросах анализа грузопотоков, Сб. ст. Проблемы повышения эффективности работы транспорта, АН СССР, 1949 3.1. Постановка задачи, основные определения 5 На практике существуют 3 основные постановки транспортной задачи: 1. Необходимо найти оптимальную структуру транспортных средств, обеспечивающую минимизацию издержек на транспортировку. эксплуатационные и экономические показатели зависят от состава транспорта 3.1. Постановка задачи, основные определения 6 На практике существуют 3 основные постановки транспортной задачи: 2. Необходимо установить такое распределение грузов между имеющимися в хозяйстве видами транспорта, при котором затраты на перевозки всего объёма грузов были бы минимальными эффективность использования различного транспорта на одной и той же работе не всегда одинакова 3.1. Постановка задачи, основные определения 7 На практике существуют 3 основные постановки транспортной задачи: 3. Задача прикрепления потребителей к поставщикам экономичный план перевозок однородного груза из пункта производства в пункты потребления 3.1. Постановка задачи, основные определения 8 минимум денежноматериальных затрат на перевозки 1. минимум приведенн ых затрат 4. Критерии оптимизации транспортной задачи 2. 3. минимум объёма транспортных работ минимум затрат времени на перевозки 3.1. Постановка задачи, основные определения Однородный продукт, сосредоточенный в m пунктах отправления в количествах а1, a2, … am единиц соответственно, необходимо доставить в каждый из n пунктов назначения в количествах b1 , b2 , … bn единиц соответственно. Стоимость (расстояние) перевозки единицы продукта из i-го пункта отправления в j-й пункт назначения равна cij (стоимость доставки) и известна для каждого маршрута. 9 Содержательная постановка задачи Пусть хij – количество продукта, перевозимого из i-го пункта отправления в j-й пункт назначения. Задача заключается в определении таких величин хij для всех маршрутов, при которых суммарная стоимость или расстояние перевозок были бы минимальными. 3.1. Постановка задачи, основные определения 10 Обозначения: m – количество пунктов отправления (поставщиков); i – номер поставщика; n – количество пунктов назначения (потребителей); j – номер потребителя; ai – объем однородного груза i-го поставщика (запасы); bi – объем однородного груза, требуемого j-ому потребителю (спрос); cij – стоимость доставки единицы груза i-го поставщика jому потребителю; xij – количество груза, доставляемое от i-го поставщика к jму потребителю; С – общие затраты на перевозки. 3.1. Постановка задачи, основные определения 11 потребители поставщики Потреб. Поставщ. 1 1 c11 x11 … i … xi1 … … … … c1j x1j … … n xij … … … cmj xmj … Запас c1n a1 x1n … cij … cm1 xm1 … j … ci1 … m … … … cin ai xin … … cmn am xmn m Спрос b1 … bj … bn a i 1 стоимость доставки единицы груза от i-го поставщика к j-ому потребителю n b j 1 3.1. Постановка задачи, основные определения 12 Стоимость перевозок можно выразить так C = c11x11 + … + cijxij + … + cmnxmn → min или более компактно m n C c ij x ij min i 1 j 1 это целевая функция, которая позволяет определить численное значение критерия оптимальности на всех этапах расчетов и в оптимальном плане 3.1. Постановка задачи, основные определения 13 Необходимо найти минимальное значение целевой функции при следующих возможных условиях: 1 условие. Вывоз всего груза от каждого поставщика: x 11 ... x ij ... x 1n ... ... ... ... ... x ij ... x in ... ... ... ... ... ... x m1 ... x mj ... x mn am ... x i1 a1 ... ai или n x ij j 1 a i где i = 1 … m 3.1. Постановка задачи, основные определения 14 Необходимо найти минимальное значение целевой функции при следующих возможных условиях: 2 условие. Удовлетворение спроса каждого потребителя: x 11 ... x 1j ... x 1n ... x i1 ... x m1 ... ... ... ... ... x ij ... x mj ... ... ... ... ... x 1n ... x mn b1 ... bj ... bn или m x ij i 1 b j где j = 1 … m 3.1. Постановка задачи, основные определения 15 Необходимо найти минимальное значение целевой функции при следующих возможных условиях: 3 условие. Равенство запаса и спроса: a1 ... ai ... am b1 ... bj ... bn или m n ai i 1 b j j 1 Равенство запаса и спроса есть необходимое и достаточное условие совместимости и, следовательно, разрешимости транспортной задачи. 16 3.2. Закрытая и открытая транспортная задача Закрытая модель транспортной задачи Открытая модель транспортной задачи Спрос равен запасу m n m ai i 1 b j Спрос не равен запасу 1 n ai j i 1 b j 1 j 17 3.2. Закрытая и открытая транспортная задача Модель закрытой транспортной задачи m n C При ограничениях: c ij x ij min i 1 j 1 n i x ij ai , i x ij bj, j 1, m 1 m i 1 x ij 1, n 18 3.2. Закрытая и открытая транспортная задача Открытая модель транспортной задачи 1. Запас превышает спрос 2. Спрос превышает запас m n ai i bj 1 j m 1 n ai i 1 bj j 1 19 3.2. Закрытая и открытая транспортная задача 1. Запас превышает спрос m n C При ограничениях: если n i x ij ai x ij b 1 1 x ij min i 1 j 1 m n ai i 1 bj j 1 Не требуется весь имеющийся груз вывозить от поставщика, после удовлетворения спроса часть его может остаться не вывезенной m i c ij x ij j Потребности (спрос) каждого потребителя необходимо удовлетворить полностью 20 3.2. Закрытая и открытая транспортная задача 1. Запас превышает спрос Решение m n ai i 1 bj bn 1 j 1 cn 1 Фиктивный потребитель При введении фиктивного потребителя открытая модель преобразуется в закрытую 21 3.2. Закрытая и открытая транспортная задача 2. Спрос превышает запас m n C При ограничениях: если c ij x ij min i 1 j 1 m n ai i bj 1 j n i x ij ai , i x ij bj, j 1, m 1 m i 1 x ij 1, n 1 22 3.2. Закрытая и открытая транспортная задача 2. Спрос превышает запас Решение n m bj j 1 ai am 1 i 1 Фиктивный поставщик 23 3.3. Метод северо-западного угла «Метод северо-западного угла» на примере: Пример: С 3-х баз требуется доставить в магазины однородный товар. Пусть на базе А1 имеется 50 единиц груза, на базе А2 – 40 единиц, на базе А3 – 20 единиц. Указанный товар нужно отгрузить 4-м потребителям: В1, В2, В3, В4, потребности которых составляют соответственно 35, 25, 30, 25 единиц товара. Стоимость перевозки от базы до потребителей представлена в таблице: В1 В2 В3 В4 А1 3 2 4 6 А2 2 3 1 2 А3 3 2 7 4 Требуется составить такой план перевозок, который обеспечит минимальные транспортные расходы. 24 3.3. Метод северо-западного угла Решение: 1 этап. Составление распределительной таблицы В1 В2 В3 В4 Наличие товара А1 3 2 4 6 50 А2 2 3 1 2 40 А3 3 2 7 4 20 Потребность в товаре 30 25 30 25 110 25 3.3. Метод северо-западного угла Решение: 2 этап. Составление модели Целевая функция (стоимость всей перевозки): C 3 x11 2 x12 4 x13 6 x14 2 x 21 3 x 22 x 23 2 x 24 Проверяем задачу на разрешимость: 3 7 x 33 4 x 34 min ai bj j 1 4 ai 50 40 i 1 20 110 , bj 30 25 30 25 110 j 1 Ограничения по поставкам x11 + x12 + x13 + x14 = 50 x21 + x22 + x23 + x 24 = 40 x31 + x32 + x33 + x34 = 20 x ij 2 x 32 4 i 1 3 3 x 31 0, i 1,3, j 1, 4 Ограничения по потребителям x11 + x21 + x31 = 30 x12 + x22 + x32 = 25 x13 + x23 + x33 = 30 x14+ x24 + x34 = 25 Ограничения по перевозкам • Запрещенный маршрут • «Гарантированная» перевозка • Ограничения по поставкам Запрещенный маршрут осложнение транспортной задачи – это запрещение определенной перевозки от i-го поставщика к j-му потребителю для составляемого плана перевозок (ремонт дороги, неплатеж и пр.). можно просто ввести ограничение xij =0. Чтобы сохранить форму транспортной задачи и учесть этот запрет, достаточно в таблице транспортных издержек заменить cij на очень большое число (на порядок большее, чем максимальная цена перевозки в таблице транспортных издержек). Это фактически будет означать, что оптимизационный алгоритм наверняка положит соответствующее значение перевозки xij равным нулю, поскольку перевозка по этому маршруту просто крайне невыгодна. Задача о назначениях С математической точки зрения, задача о назначениях – это частный случай транспортной задачи Кроме того, в задаче о назначениях от каждого поставщика к каждому потребителю поставляется только одна единица "груза" (например, только одного рабочего можно назначить для выполнения данной работы) или ни одной. Поэтому все "запасы" и все "заказы" равны 1. Задача о назначениях все переменные решения в задаче о назначениях могут принимать только значения 1 или 0. Работа А 1 2 3 4 Работники B C D 15 20 18 24 12 17 16 15 14 15 19 15 11 14 12 3 Задача о назначениях Как распределить рабочих по операциям, чтобы суммарные затраты рабочего времени были бы минимальны? Однако не следует требовать явно, чтобы они были целыми и меньшими или равными 1! Задача о назначениях все переменные окажутся равными 0 или 1. Однако не следует требовать явно, чтобы они были целыми и меньшими или равными 1! ПРИМЕР Задача о назначениях Фирма, занимающаяся продажей оборудования для компьютерных сетей, имеет 10 специалистов по маркетингу и 10 техниковпрограммистов, которых необходимо объединить в пары (техник - менеджер по маркетингу) - команды по продаже оборудования, соответствующего нуждам конкретного клиента.. ПРИМЕР Задача о назначениях Менеджер по работе с персоналом провел среди них тест Майера-Бриггса и определил индекс взаимной несовместимости между i-м техником и j-м маркетологом. Индекс варьирует от 20 (выраженная враждебность) до 1 (дружеские отношения). Результаты представлены в таблице индексов несовместимости. Составить команды так, чтобы суммарный индекс был минимальным ПРИМЕР Задача о назначениях ПРИМЕР Задача о назначениях ПРИМЕР Задача о назначениях Интересно отметить, что оно, как говорят математики, "вырождено". Это значит, что различным наборам переменных решения отвечает одно и то же оптимальное значение целевой функции. Модель производства с запасами  Pi –затраты на производство единицы готовой продукции в течение периода i;  Si - затраты на хранение единицы готовой продукции в течение периода i;  Задержка в поставке единицы продукции в период i приводит к издержкам, равным ri .  Необходимо составить такой план поставок продукции потребителю, чтобы суммарные затраты f, связанные с производством, хранением и издержками, были минимальны. Обозначим:  Xij – кол-во продукции, изготовляемой в период i и поставляемой в период j. 20 Модель производства с запасами. Аналогия с транспортной задачей Транспортная модель (f-стоимость перевозок) Модель производства с запасами (fстоимость поставок) Пункты отправления Аi Периоды производства i Запасы ai в пункте отправления i Объём производства ai за период i Пункты назначения Bj Периоды потребления j Заявка bj пункта назначения j Поставка продукции bj за период j Стоимость перевозки Cij Затраты Cij на производство за период i и на реализацию за период j Количество груза Xij Кол-во продукции Xij произведённый за период I и реализованный за период j 21 Модель производства с запасами Cij =pi ,если i=j, т.е. если продукция изготовлена и реализуется в период i; j 1 Cij=pi +  sk,если ij, т.е. если продукция изготовлена и k j реализуется в период i в счёт долга, образованного недопоставкой в период j.   M M f ( X )   cij xij  min i 1 j 1 M x j 1 ij M  ai ,  xij  b j , xij  0 i 1 22 4. Оптимальное распределение оборудования Оборудование m различных видов нужно распределить между n рабочими участками. Производительность единицы оборудования i-го вида на j-м рабочем участке равна pij , i=1,..m;  J=1,..n. Запас оборудования i-го вида равен aI ,  Потребность j-го участка в оборудовании составляет bj . Найти распределение оборудования по рабочим участкам, при котором суммарная производительность максимальна.  Xij – число единиц оборудования i-го вида , выделенное на j-й рабочий участок.  23 Оптимальное распределение оборудования 24 5.Формирование оптимального штата фирмы Фирма набирает штат сотрудников. Она располагает n группами различных должностей по bj , j=1,..n, вакантных единиц в каждой группе. По результатам тестирования кандидатов разделяют на m групп по  aI кандидатов в каждой группе, i=1,..m. Для каждого кандидата из i-ой группы требуются определённые затраты cIj на обучение для занятия j-й должности.  cIj=0, кандидат полностью соответствует должности,  cIj=∞, кандидат не может занять данную должность.  Требуется распределить кандидатов на должности, затратив минимальные средства на их обучение.  25 Формирование оптимального штата фирмы 26