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