17.2. МЕТОДЫ РЕШЕНИЯ ТРАНСПОРТНЫХ ЗАДАЧ

Линейное программирование - это метод поиска неотрицательных значений переменных, максимизирующих или минимизирующих значение линейной целевой функции при наличии ограничений, заданных в виде линейных неравенств.

Метод нахождения решения основной задачи линейного программирования, получивший название «симплексный метод» или «метод решения с помощью мультипликатора», независимо друг от друга открыли в 1940 г. советский ученый Л.В. Канторович и американский математик Дж. Данциг.

Разновидностью общей задачи линейного программирования является так называемая транспортная задача, применяемая как для оптимизации перевоз-ки грузов, так и в ряде других приложений.

Формальным признаком транспортной задачи является то, что каждая переменная входит лишь в два ограничения, причем с коэффициентами, равными единице. Если при этом критерий оптимальности (сумма расходов, общий пробег) прямо пропорционален значениям переменных (транспортных потоков), возникает линейная транспортная задача. В других случаях рассматривается нелинейная транспортная задача, решаемая другими методами.

Транспортные задачи известны в двух постановках: матричной и сетевой.

Матричная задача. Пусть имеется ряд пунктов потребления и предприятий-поставщиков некоторой продукции.

Дано:

Аі - ресурс i-го поставщика (запас продукции или план отгрузки из текущего производства).

Вj - потребности в той же продукции в пунктах j.

Су - расстояние или стоимость перевозки из i в j.

Требуется найти такие размеры поставок от каждого поставщика каждому потребителю Xj (переменные задачи), при которых общая сумма расходов или общий пробег будут минимальными.

Различают следующие разновидности транспортных задач: закрытая, открытая с превышением ресурсов и открытая с превышением потребностей (см.

Система ограничений закрытой задачи предусматривает поставку каждому потребителю количество продукции, равного потребности в ней (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). Схема состоит из звеньев (или дуг) и узлов (или вершин). Вершинами являются пункты или (центры агрегации) погрузки и выгрузки, а также все реальные узловые пункты сети.

Вершины без погрузки и выгрузки данного груза являются транзитными.

Каждый участок (звено) сети между двумя соседними вершинами обычно рассматривают как две дуги противоположного направления с движением в одну сторону по каждой дуге.

Каждая дуга характеризуется показателем расстояния (или стоимости) перевозки единицы груза или длиной дуги. При решении задач по критерию стоимости длины прямой и обратной дуг обычно различны (так как издержки перевозки по участку «туда» и «обратно» не совпадают).

Переменными сетевой транспортной задачи являются потоки груза по каж-дой дуге.

До решения, как правило, неизвестно, в какую сторону будет перевозиться груз по участку в оптимальном варианте. Поэтому в число переменных включаются потоки в обоих направлениях, а общее число переменных принимается равным удвоенному числу участков сети. При значительном количестве поставщиков и получателей число переменных при сетевой постановке значительно меньше, чем при матричной, что облегчает решение задачи. Например, при наличии на сети 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) получаем сетевую транспортную задачу с ограничением пропускной способности в простейшем виде (для перевозки одного груза).

Сетевая и матричная модели в большинстве случаев взаимозаменяемы. Но есть и особые ситуации, так, например, при большом количестве потребителей и поставщиков преимущество имеет сетевая постановка задачи; эта же форма применяется при оптимизации перевозок с учетом ограничений пропускной способности участков транспортной сети. Оптимизацию планирования перевозок взаимозаменяемых грузов удобнее производить в матричной форме, и т.д.