<<
>>

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

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

<< | >>
Источник: Н.П. Терёшина, В.Г. Галабурда, М.Ф. Трихунков и др.. Экономика железнодорожного транспорта: Учеб. для вузов ж.-д. транспорта Н.П. Терёшина, В.Г. Галабурда, М.Ф. Трихунков и др. ; Под ред. Н.П. Терёшиной, Б.М. Лапидуса, М.Ф. Трихункова. - М.: УМЦ ЖДТ.. 2006

Еще по теме 17.2. МЕТОДЫ РЕШЕНИЯ ТРАНСПОРТНЫХ ЗАДАЧ:

  1. 2 ТРАНСПОРТНАЯ ЗАДАЧА И ЗАДАЧА О НАЗНАЧЕНИЯХ: АЛГОРИТМЫ РЕШЕНИЯ
  2. 2.1 РЕШЕНИЕ ТРАНСПОРТНЫХ ЗАДАЧ С ИСПОЛЬЗОВАНИЕМ МЕТОДОВ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ
  3. 2.2 АЛГОРИТМЫ РЕШЕНИЯ ТРАНСПОРТНОЙ ЗАДАЧИ
  4. 2.3 Модификации транспортной задачи
  5. 2П ТРАНСПОРТНАЯ ЗАДАЧА И ЗАДАЧА О НАЗНАЧЕНИЯХ: АЛГОРИТМЫ РЕШЕНИЯ
  6. 2.1П РЕШЕНИЕ ТРАНСПОРТНЫХ ЗАДАЧ С ИСПОЛЬЗОВАНИЕМ МЕТОДОВ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ
  7. 2.2П АЛГОРИТМЫ РЕШЕНИЯ ТРАНСПОРТНОЙ ЗАДАЧИ
  8. 3.1. Методы решения образовательных, развивающих и воспитательных задач
  9. 12.2. Аналитический метод решения задач параметрического программирования
  10. 17.2. МЕТОДЫ РЕШЕНИЯ ТРАНСПОРТНЫХ ЗАДАЧ
  11. 11.2. Методы решения оптимизационных задач
  12. § 65. Симплекс-метод решения задач линейного программирования, М-метод