Методы решения транспортных задач

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

Линейное программирование =метод поиска неотрицатель­ных значений переменных, максимизирующих или минимизирующих значение линейной целевой функции при наличии ограничений, задан­ных в виде линейных неравенств. Метод нахождения решения основной задачи линейного програм­мирования, получивший название "симплексный метод".

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

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

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

Переменными сетевой транспортной задачи являются потоки груза по каждой дуге. Поток может включать много отправок, поток по дуге Б-Д включает поставки из Б в Д-8 единиц груза, а из Б в Г-7 единиц груза.

До решения, как правило, неизвестно, в какую сторону будет перевозиться груз по участку в оптимальном варианте. Поэтому в число переменных включают потоки в обоих направлениях, а общее число переменных принимают равным удвоенному числу участков сети. При значительном числе отправителей и получателей число переменных при сетевой постановке значительно меньше, чем при матричной, что облегчает решение задачи, например, при наличии на сети 600 участков, 50 пунктов отправления и 200 пунктов назначения число переменных при сетевой постановке составит 1200=(600*2), а при матричной постановке оно будет гораздо больше (200*50 = 10000 переменных).

Обязательным условием сетевой задачи является требование балансировки прибытия и отправления груза в каждой вершине сети: прием груза со всех направлений плюс собственная погрузка равны сдаче на все направления плюс собственная выгрузка:

åХкs – åХrk = Rk

S r

к - произвольная вершина

R_K - погрузка (+) или выгрузка (-)

Хкs - потоки от К по всем соседним вершинам S

Хrk- потоки к К от соседних вершин Г.

Целевая функция закрытой сетевой задачи имеет вид: F = åC_rc * Хrs — > min

Суммирование выполняется по всем дугам сети. Описанная модель сетевой задачи не учитывает пропускной способности участков сети - для этого вводится дополнительное ограничение:

Xrs < drs,

drs= пропускная способность участка сети rs в направлении от г к s.

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

Пусть имеется некоторая схема потоков однородного ресурса (груза, порожних вагонов) по транспортной сети с ограниченной пропускной способностью звеньев. Пропускную способность звена г-s в направлении к s обозначим d_rs. Все звенья в зависимости от наличия потока x_rs данного груза делятся на три категории: 1. базисные с потоками 0<x_rs<d_rs;2. пустые без потока данного груза x_rs=0;3. насыщенные x_rs=d_rs. Рассматривается однопродуктовая задача. В многопродуктовой задаче насыщенными являются звенья с суммой потоков всех грузов, равной пропускной способности.

Если схема потоков оптимальна, всем вершинам сети могут быть присвоены потенциалы U, удовлетворяющие следующим условиям: 1. для базисных звеньев U_s -U_r=C_rs,(1),где C_rs-расстояние или издержки (в зависимости от используемого критерия) перевозки единицы груза от г до s; 2. для пустых звеньев U_s-U_r ≤ С_rs (2); 3. для насыщенных звеньев U_s-U_r ≥ С_rs(3.)

Равенство U_s-U_r = C_rs во всех случаях допустимо и не противоречит оптимальности схемы. Нарушение условий (2) и (2), т.е. U_s-U_r ≤ С_rs – для пустого звена и U_s-U_r ≥ С_rsдля насыщенного - говорит о неоптимальности плана и указывает путь к его улучшению.

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

Порядок вычислений:

1. Построение начального плана. Начальная схема потоков должна удовлетворять следующим требованиям: а) соблюдения условия баланса для всех вершин сети: ΣX_ks-ΣX_rk = R_k

^{сдача прием +погрузка, -выгрузка}

б) непревышение пропускной способности звеньев; поток x_rs<d_rs на всех дугах сети; в) отсутствие замкнутых контуров, образованных базисными звеньями с потоками 0<x_rs<d_rs.

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

2. Присвоение потенциалов всем вершинам сети. Какой либо вершине, к которой примыкает хотя бы одно базисное звено, присваивается произвольный потенциал (число одного порядка с наибольшей дальностью перевозок). Затем присваиваются потенциалы остальным вершинам сети, следуя по всем базисным звеньям и используя равенство U_s - U_r=C_rs. При потоке от R к S вершине S присваивается потенциал U_s=U_r+C_rs (где С_гs-длина звена). Если поток следует от S к R, то потенциал определяется по следующей формуле U_s=U_r - C_rs. В процессе присвоения потенциалов может обнаружиться, так называемый, случай вырождения: совокупность (граф) базисных звеньев распадается на n не связанных между собой систем. В этом случае имеющихся базисных звеньев недостаточно для присвоения потенциалов всем вершинам. Тогда вводятся n-1 нулевых потоки, связывающих между собой отдельные системы базисных звеньев. Звенья с нулевыми потоками считаются базисными и используются для присвоения потенциалов.

В задаче с ограничениями пропускной способности компоненты базисного графа могут быть отделены друг от друга не только пустыми, но и насыщенными звеньями.

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

3. Проверка соблюдения условий (2и3) на всех пустых и насыщенных звеньях сети.

Если эти условия соблюдаются везде, то задача решена и план оптимален. При наличии нарушений - невязок H_ij выбираем участок с наибольшей невязкой и переходим к пункту 4.

4. Поиск пути по базисным звеньям между вершинами-концами звена с невязкой.

Совокупность этого пути и звена с невязкой называется контуром.

Дальнейшее действие зависит от того, является ли звено с невязкой пустым или насыщенным.

5. Классификация потоков контура.

а) Устанавливается направление потока на звене с невязкой от меньшего потенциала к большему;

б) Все другие потоки в контуре делятся на попутные и встречные этому потоку.

6. Определение изменение потоков ∆Х.

а) для пустого звена с невязкой ∆Х = min[minX;min(d-х)] (4), где d-пропускная способность звена.

Следовательно, поправка равна меньшей из двух величин: наименьшего встречного потока и наименьшего свободного остатка пропускной способности для попутных потоков.

б) для насыщенного звена с невязкой (в точности обратное правило).

∆Х = min[minX;min(d-х) (5), т.е. берется наименьший попутный поток и наименьший из резервов пропускной способности для встречных потоков.

При использовании правил (4и5)звено с невязкой учитывается в числе попутных.

7. Исправление плана. а) При исправлении невязки на пустом звене потоки по всем попутным звеньям контура (включая звенья с невязкой) увеличиваются на ∆Х, а по встречным уменьшается на ∆Х.

6) При исправлении невязки на насыщенном звене, наоборот, потоки на всех попутных звеньях контура уменьшаются, а на встречных увеличиваются на ∆Х. В расчете получается новый вариант плана, для которого заново определяются потенциалы, проверяется наличие невязок и т.д.

51.Экономико-географическая характеристика и особенности транспортной системы страны. Место в ней железнодорожного транспорта.
Понятие «инфраструктура железных дорог”

Транспортная система России характеризуется развитой транспортной сетью, включающей в себя 87 тыс. кмжелезных дорог, более 745 тыс. км автомобильных дорог с твердым покрытием, свыше 600 тыс. км воздушных линий, 70 тыс. км магистральныхнефте - и продуктопроводов, свыше 140 тыс. км магистральных газопроводов, 115 тыс. км речныхсудоходных путей и множество морских трасс. В ней занято свыше 3,2 млн человек, что составляет 4,6 % работающего населения.

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

Современное состояние транспортной системы характеризуется низким техническим уровнем производственной базы большинства предприятий и износом подавляющего большинства транспортных средств, что приводит к снижениюе безопасности ее работы, а также отсутствием инвестиций для преодоления данных проблем^[1].

Транспортное пространство представляет собой совокупность самостоятельных организаций — перевозчиков и посредников — с преобладанием мелкого капитала, что явилось следствием дезинтеграции экономики в 90-е годы XX века.