Главная Случайная страница Контакты | Мы поможем в написании вашей работы! | ||
|
Наиболее часто в практической деятельности человеку приходится встречаться с задачами о распределении транспортных потоков. Пример простейшей задачи транспортного типа рассмотрен в § 2.2.
Классическая постановка транспортной задачи общего вида такова.
Имеется пунктов отправления – «поставщиков» и пунктов потребления – «потребителей» некоторого одинакового товара. Для каждого пункта определены:
объемы производства -го поставщика,
спрос -го потребителя, ;
стоимость перевозки одной единицы продукции из пункта – i-го поставщика, в пункт – j-го потребителя.
Обычно данные удобно представлять в виде таблицы, которую называют таблицей стоимостей перевозок
Поставщики | Потребители | В1 | В2 | … | Вn | запасы |
А1 | C11 | C12 | C1n | a1 | ||
А2 | C21 | C22 | C2n | a2 | ||
Аm | Cm1 | Cm2 | Cmn | am | ||
Потребности | b1 | b2 | bn |
Требуется в задаче найти план перевозок, при котором бы полностью удовлетворялся спрос всех потребителей, при данных запасах поставщиков, и суммарные транспортные расходы были бы минимальными.
Под планом перевозок понимают объем перевозок – количество товара, которое необходимо перевезти от -го поставщика к -му потребителю. Для построения математической модели задачи необходимо ввести штук переменных каждая переменная обозначает объем перевозок из пункта в пункт . Набор переменных и будет планом, который необходимо найти, исходя из постановки задачи.
Ограничения задачи примут вид (3.1):
Очевидно, что для разрешимости задачи (3.1) необходимо, чтобы суммарный спрос не превышал объемы производства у поставщиков: . Если это неравенство выполняется строго, то задача называется «открытой» или «несбалансированной». Если же , то задача называется «закрытой» транспортной задачей.
Мы остановимся сейчас на решении закрытых транспортных задач (ЗТЗ).
В силу ограничений (3.1) нетрудно увидеть, что ТЗ является задачей ЛП и может быть решена симплекс–методом после приведения ее к специальному виду. Но структура системы ограничений имеет некоторую специфику, а именно каждая переменная входит ровно два раза в неравенства системы и все переменные входят в неравенства системы с коэффициентом 1. В силу этой специфики разработан собственный метод решения, называемый методом потенциалов. По–прежнему идеей является переход от одного опорного плана к другому, обязательно «лучшему», с точки зрения значения целевой функции. Здесь целевая функция последовательно уменьшает свои значения, т.к. цель задачи – минимизировать расходы. Каждому опорному плану также соответствует своя распределительная таблица. Переход осуществляется, пока полученный план не будет удовлетворять условию оптимальности. Сначала необходимо построить первоначальный опорный план. В качестве первоначального плана годится любое решение системы уравнений (3.1). Заметим, что это система линейных уравнений, состоящая из уравнений, с неизвестными. Можно доказать, что линейно–независимых уравнений в системе (3.1) , ввиду условия сбалансированности, т.е. базисных переменных должно быть , остальные будут нулевыми. Итак, в качестве плана будем представлять себе таблицу размера , в которой должно быть занято ровно клеток, отвечающих базисным переменным . Стоимости перевозок всегда будем записывать в правом верхнем углу ячейки таблицы, естественно считая их постоянными на протяжении решения задачи.
Дата публикования: 2015-10-09; Прочитано: 750 | Нарушение авторского права страницы | Мы поможем в написании вашей работы!