17.2. МЕТОДЫ РЕШЕНИЯ ТРАНСПОРТНЫХ ЗАДАЧ
Линейное программирование - это метод поиска неотрицательных значений переменных, максимизирующих или минимизирующих значение линейной целевой функции при наличии ограничений, заданных в виде линейных неравенств.
Метод нахождения решения основной задачи линейного программирования, получивший название «симплексный метод» или «метод решения с помощью мультипликатора», независимо друг от друга открыли в 1940 г. советский ученый Л.В. Канторович и американский математик Дж. Данциг.
Разновидностью общей задачи линейного программирования является так называемая транспортная задача, применяемая как для оптимизации перевоз-ки грузов, так и в ряде других приложений.
Формальным признаком транспортной задачи является то, что каждая переменная входит лишь в два ограничения, причем с коэффициентами, равными единице. Если при этом критерий оптимальности (сумма расходов, общий пробег) прямо пропорционален значениям переменных (транспортных потоков), возникает линейная транспортная задача. В других случаях рассматривается нелинейная транспортная задача, решаемая другими методами.
Транспортные задачи известны в двух постановках: матричной и сетевой.
Матричная задача. Пусть имеется ряд пунктов потребления и предприятий-поставщиков некоторой продукции.
Дано:
Аі - ресурс i-го поставщика (запас продукции или план отгрузки из текущего производства).
Вj - потребности в той же продукции в пунктах j.
Су - расстояние или стоимость перевозки из i в j.
Требуется найти такие размеры поставок от каждого поставщика каждому потребителю Xj (переменные задачи), при которых общая сумма расходов или общий пробег будут минимальными.
Различают следующие разновидности транспортных задач: закрытая, открытая с превышением ресурсов и открытая с превышением потребностей (см.
рис. 17.8).Система ограничений закрытой задачи предусматривает поставку каждому потребителю количество продукции, равного потребности в ней (17.1) и вывоз продукции от каждого поставщика в количестве, равном ее ресурсу (17.2):
XX j = Bj (j = 1, 2, ... л); (17.1)
i
X Xj = Ai (i = 1, 2, ... m). (17.2)
j
В открытой задаче с превышением ресурсов возможен вывоз меньше наличия:
XXj <Аг(i = 1, 2, ... m),
j
где m - отправители; п - получатели.
Каждая конкретная переменная входит в два условия: типа (17.1) для данного потребителя и типа (17.2) для данного поставщика.
Критерием оптимальности решения является минимум общих расходов по перевозке или суммарного пробега в тонно-километрах (вагоно-километрах) по всем планируемым корреспонденциям. Если стоимость перевозки (расстояние) от i до j обозначить как Cj, то целевая функция определится следующим образом:
F = Z Z CjXj ^ min.
i j
Транспортная задача в этой постановке решается на матрице, в строках которой показываются поставщики, в столбцах - получатели, а в клетках (пересе-чениях) - корреспонденции между ними.
Сетевая задача. Оптимальное планирование перевозок может быть произведено непосредственно на схеме сети путей сообщения (см. рис. 17.9). Схема состоит из звеньев (или дуг) и узлов (или вершин). Вершинами являются пункты или (центры агрегации) погрузки и выгрузки, а также все реальные узловые пункты сети.
Вершины без погрузки и выгрузки данного груза являются транзитными.
Каждый участок (звено) сети между двумя соседними вершинами обычно рассматривают как две дуги противоположного направления с движением в одну сторону по каждой дуге.
Каждая дуга характеризуется показателем расстояния (или стоимости) перевозки единицы груза или длиной дуги. При решении задач по критерию стоимости длины прямой и обратной дуг обычно различны (так как издержки перевозки по участку «туда» и «обратно» не совпадают).
Переменными сетевой транспортной задачи являются потоки груза по каж-дой дуге.
Поток может включать в себя много отправок, например, поток по дуге Б-Д включает поставки из Б в Д - 8 единиц груза, а из Б в Г - 7 единиц груза.До решения, как правило, неизвестно, в какую сторону будет перевозиться груз по участку в оптимальном варианте. Поэтому в число переменных включаются потоки в обоих направлениях, а общее число переменных принимается равным удвоенному числу участков сети. При значительном количестве поставщиков и получателей число переменных при сетевой постановке значительно меньше, чем при матричной, что облегчает решение задачи. Например, при наличии на сети 600 участков, 50 пунктов отправления и 200 пунктов назначения число переменных при сетевой постановке составит 1200 (600 • 2), а при матричной поста-новке оно будет гораздо больше (200 • 50 = 10000 переменных).
Обязательным условием сетевой задачи является требование балансировки прибытия и отправления груза в каждой вершине сети: прием груза со всех направлений плюс собственная погрузка равны сдаче на все направления соб-ственная выгрузка:
Z Xks -Z Xrk = Rk, (17.3)
sr
где К - произвольная вершина;
Rk - погрузка (+) или выгрузка (-) (rk - 0 для транзита);
Xks - потоки от К по всем соседним вершинам s;
Xrk - потоки к К от соседних вершин r.
Целевая функция закрытой сетевой задачи имеет вид:
F = ZCrs • Xrs ^ min. (17.4)
Суммирование выполняется по всем дугам сети.
Итак, сетевая транспортная модель включает в себя:
а) расчетную транспортную сеть,
б) переменные Xrs для каждой дуги,
в) уравнение (17.3) для каждой вершины,
г) целевую функцию (17.4) с коэффициентами Сга, равными расстояниям или показателям стоимости перевозок по дугам сети.
Описанная модель сетевой задачи не учитывает пропускной способности участков сети, для этого вводится дополнительное ограничение:
< drs, (17.5)
где drs - пропускная способность участка сети rs в направлении от r к s.
С учетом (17.5) получаем сетевую транспортную задачу с ограничением пропускной способности в простейшем виде (для перевозки одного груза).
Сетевая и матричная модели в большинстве случаев взаимозаменяемы. Но есть и особые ситуации, так, например, при большом количестве потребителей и поставщиков преимущество имеет сетевая постановка задачи; эта же форма применяется при оптимизации перевозок с учетом ограничений пропускной способности участков транспортной сети. Оптимизацию планирования перевозок взаимозаменяемых грузов удобнее производить в матричной форме, и т.д.