(транспортная задача)
1. Содержание задачи. Планирование перевозок в условиях нехватки транспорта приводит на практике к простоям в ожидании обслуживания на погрузочно-разгрузочных работах, к порожним пробегам, встречным и нерациональным перевозкам. В связи с этим необходимо решать задачи оптимального планирования перевозок из пунктов отправления (баз, станций, фабрик, заводов) в пункты назначения (склады, перерабатывающие цеха) методами, позволяющими оптимизировать план по какому-либо экономическому показателю, например, минимум затрат на перевозки.
Для составления маршрутов перевозок существует особый класс задач математических методов линейного программирования — транспортные задачи.
2. Экономико-математическая постановка задачи. Имеется пунктов отправления (поставщиков) товаров:
на которых сосредоточены запасы какого-либо однородного товара в объёмах соответственно:
что определяет максимально возможные величины поставок с этих баз. Следовательно, должно выполняться условие .
|
|
Кроме того, имеется пунктов назначения (потребителей):
которые подавали заявки на товары в объёмах соответственно:
Стоимость перевозки одной единицы груза от поставщика к потребителю обозначим через . Общая стоимость перевозок составит матрицу транспортных издержек . В качестве критерия оптимальности выбираем суммарные издержки по перевозке грузов.
На этом основании задача формулируется следующим образом: необходимо составить оптимальный план, то есть найти такие значения объёма перевозок грузов от поставщиков к потребителям , при которых все заявки были бы выполнены, а суммарная стоимость всех перевозок была бы минимальной.
Совокупность составляет матрицу , называемую планом перевозок. Исходные данные таких задач записывают в виде специальных транспортных таблиц (таблица 1), объединяющих обе матрицы — и .
Таблица 1
Поставщики | Потребители | Запасы поставщиков | ||||||
… | … | |||||||
… … | … … | |||||||
… … | … … | |||||||
… … | … … | |||||||
… | … … | … … | … … | … … | … … | … … | … … | … |
… … | … … | |||||||
… | … … | … … | … … | … … | … … | … … | … … | … |
… … | … … | |||||||
Заявки потребителей, | … | … |
Экономико-математическая формулировка и модель транспортной задачи имеют следующий вид: найти такие неотрицательные значения которые обращают в минимум линейную функцию цели
при линейных ограничениях вида:
– условие вывоза всех грузов от поставщиков;
– условие поставок груза потребителям;
|
|
- условие исключения встречных перевозок.
В более компактном виде транспортная задача формулируется следующим образом: минимизировать затраты на перевозку грузов:
при ограничениях
Определение. Если в транспортной задаче спрос равен предложению (), то имеем закрытую (сбалансированную, каноническую) модель транспортной задачи. Если спрос не равен предложению () то имеем открытую модель транспортной задачи.
Правило приведения транспортной задачи к каноническому виду:
· если предложение превышает спрос, то есть , следует ввести „фиктивного” потребителя с заявкой с транспортными издержками . При решении задачи часть груза попадает к фиктивному потребителю, а фактически это означает, что этот груз останется на соответствующей базе поставщика;
· если предложение меньше спроса, то есть , следует ввести „фиктивного” поставщика с запасом с транспортными издержками .
Пример. Необходимо составить оптимальный план перевозок некоторого однородного груза с четырех баз , мощности которых составляют и тонн к четырем потребителям , мощности которых соответственно: и тонн. Исходные данные и матрица транспортных издержек приведены в транспортной таблице (таблица 2).
Таблица 2
Поставщики | Потребители | Запасы поставщиков | |||
Заявки потребителей, |
Определим тип транспортной задачи путем проверки баланса суммарной мощности поставщиков:
(тонн)
и суммарной мощности потребителей:
(тонн).
Спрос и предложение сбалансированы:
(тонн),
следовательно, данная задача закрытого типа.
Составим экономико-математическую модель транспортной задачи: найти такие неотрицательные значения (), которые доставляют минимальное значение целевой функции задачи
при ограничениях
– условие вывоза всех грузов с поставщиков;
– условие поставок груза потребителям;
- условие исключения встречных перевозок.
Рассмотренная постановка задачи является примером экономико-математической модели оптимального прикрепления перерабатывающих предприятий к поставщикам и может быть оптимизирована не только по затратам на перевозку, но и по другим показателям: времени перевозки, материальным затратам и т.д. Данная задача может быть решена симплекс-методом и, как следствие, её решение легко реализуется в прикладных программах на ЭВМ (например, в Excel). На практике решение задач симплексным методом очень трудоемко и целесообразно применение более простых методов: метода потенциалов, распределительного метода и др.