Транспортная задача
Задача нахождения алгоритма прокладки оптимальной сети дорог при заданных источниках строках грузов была поставлена перед автором в 1984 г. В.А. Уфимцевым на курсах по систематическому проектированию. Алгоритм был разработан для конкретной транспортной ситуации — реальных перевозок грузов. При этом, однако,выяснилось, что ключевые методы, заложенные в алгоритм, имеют более широкое применение в классе «транспортных» задач — передача сигналов, заряженных частиц и т.п. Здесь излагается общее описание логики алгоритма, в нем опущены многие частные детали и проверочные тесты. Но уже в таком виде найденные методы
2[править]
2) Дороги прокладываются по наиболее легким участкам территории таким образом, чтобы их стоимость была минимальна и все грузоперевозки при этом сохранялись (рис. 4б). Затраты на перевозки значительно превышают минимально возможные. Если отбросить частные случаи, когда транспортные расходы пренебрежительно малы по сравнению со строительными, либо наоборот, то оптимальное решение всегда отличается от экстремальных. Рассмотрим два варианта решения. Вариант первый. Вся территория разбивается на участки с одинаковой стоимостью прокладки единичного отрезка пути -Si. Выбирается наиболее дешевый базисный участок с So. Строится полная сеть дорог. Для этого на карту территории наносятся все пункты Аi и соединяются прямыми отрезками. Затем каждому отрезку приписывается соответствующе грузообороту Pi. Вычисляется средняя стоимость перевозок (Со) (рубли/усл.грузы · км) и определяется стоимость грузопотока Сi (рубли/км) за амортизационный период. Далее производится поэтапное «стягивание» дорог с целью удешевления затратна строительство за счет слияния в одну транспортную артерию близких дорог. Получаемая при этом экономия должна превышать увеличение расходов на транспортирование грузов, возникшее за счет искривления путей.
Для стягивания на сети дорог выбираются такие пары при Ai, углы между ко-торыми минимальны. На рис. 5а приведен пример стягивания. Из узла Д откла-дывается единичный отрезок ДОi под таким углом α1кАД, чтобы выполнялось условие:
(lBOiD – lBD) · CBD + (lAOiD – lAD) · CAD = ΔPi→ min.
Выбор αi можно осуществлять пошаговой проверкой условия (1) в диапазоне значений:
0 ≤α1≤α
Проверка на: оптимальность стягивания после окончательного выбор аα1, осуществляется по формуле:
ΔPi≤ΔSi,
где:
ΔSi= (lDOi + lDA) · So – (lDOi + lOiB + lOiA) · So.
(3)[править]
Экономия на строительстве дорог должна быть больше возросших затрат на транспортировку. Точность расчета зависит от степени дискретности шагов
(от Δαi и ΔlDO).
Поэтапное стягивание производится до момента, когда неравенство (2) пере-станет выполняться. Точка Оi, при которой достигается условиеΔPi = ΔSi, принимается в качестве оптимального узла стягивания дорог АД и ВД. Далее выбирается следующий наименьший угол в ряду углов при вершинах Ai. Операция стягивания повторяется. Таким образом достигается постепенное стягивание всех дорог до оптимальных узлов. В результате может появиться несколько вариантов оптимальных сетей, например, таких как на рис. 6.
На следующем этапе на карту с идеальной оптимальной сетью дорог наносятся участки различной стоимости прокладки дорог, Si и выбираются локальные экстремумы — наиболее дешевые участки различных топологических типов: «плато», «овраги», «ямы». Эти участки покрываются триангуляционной сеткой с единичной длиной ребра. В полную сеть (в полный граф) соединяются все Аi, узлы Oi и узлы сетки Oi. Затем последовательно проверяются всевозможные варианты сечений стоимостного рельефа между Аi, и Oi. Взбирается наиболее дешевый вариант. В результате на карту реального рельефа наносится ужe реальная оптимальная сеть дорог 1 типа (рис. 7).
Описанный метод при всей его простоте и наглядности имеет существенный недостаток — узлы дорог O1 и О2 идеальной оптимальной сети необоснованно сохраняются неизменными при проектировании реальной оптимальной сети.
Однако уже в этом решении можно увидеть две интересные физические аналогии, которые будут необходимы нам в дальнейшем. Аналогия первая. Операцию поэтапного стягивания можно проводить на физической модели, в которой дороги между Ai, заменены пружинами, жесткость которых прямо пропорциональна Pi. Тогда стягивание пружин проводят кольцом С(рис. 5б) до тех пор, пока оно не будет уравновешено реакциями пружин F1и F2. Усилие R — аналогΔSi, сумма реакций F1+F2 — аналогΔPi. Аналогия вторая. При определении оптимального пути через неоднородную территорию, мы использовали алгоритм перебора вариантов, как наиболее традиционный метод при решении задач на ЭВМ. Однако, если бы нам удалось «за-ставить» природу решать эту задачу, она скорее всего «воспользовалась» бы закономерностью прохождения света через неоднородную среду. Известный принцип Ферма гласит: вне однородной среде свет избирает такую траекторию, вдоль которой время, затрачиваемое им на преодоление пути от одной точки до другой минимально. Углы преломления при этом пропорциональны скоростям распространения света. Т.о., чтобы минимизировать затраты на строительство пути между двумя пунктами A1иА2, можно построить физическую модель, в которой по контуру участков с различной Si вырезаются прозрачные пластины достаточной толщины, из которых набирается модель территории между A1 и А2. При этом материал пластин подбирается так, чтобы скорость распространения в них света была пропорциональна соответствующим значениям 1/Si. Затем посылается из точки A1 узкий луч света таким образом, чтобы он попал точно в А2. «Выбранная» лучом траектория и есть искомый путь, минимизированный по строительным затратам. Если бы при этом удалось еще и каким-то образом учитывать возрастание ΔPi, то данный метод позволил бы весьма оперативно решать задачу оптимизации транспортных сетей.
Вариант второй.[править]
Его отличие в том, что реальная оптимальная сеть дорог со всеми ее связями между Ai (полный граф) находится сразу (рис. 8.). Выбор оптимальной дороги между двумя Ai решается автономно с помощью триангуляционной сетки, масштаб которой можно сделать переменным, в зависимости от изменчивости стоимостного рельефа.
Затем опять же проводится операция стягивания, но уже не с минимального угла при Аi, а начиная с минимальной площади, ограничиваемой соседними единичными отрезками дорог, если между ними нет границы участков с различной стоимостью, Si. Если такая граница есть, то расчет ведется по минимальному объему участка стоимостного рельефа, заключенного между упомянутыми единичными отрезками дорог (рис. 9)
Второй вариант, безусловно, даст действительно оптимальные решения, но он требует гораздо большего перебора вариантов при стягивании. На всех примерах мы рассматривали небольшое число Аi: от 3 до 7. Но если пунктов на порядок больше, то происходит качественный скачок и возникает ситуация по уровневого укрупнения дорог. Это возможно за счет своеобразного «дефекта стоимости», т.к. пропускная способность дороги растет с некоторым опережением ее стоимости. Ведь очевидно, что проложить дорогу два разашире единичной — дешевле, чем по строить две единичные дороги в различных местах. Т.о. при значительном укрупнении транспортных магистралей, пропускная способность дороги возрастает быстрее, чем ее категориальная стоимость. Этот экономический выигрыш позволяет при наличии сквозных грузопотоков укрупнять дороги (повышать их категориальность). В результате на карте территории от сети дорог можно перейти к иерархической сети оптимальных траекторий(рис. 10).
Образующийся при этом выигрыш позволяет проводить полную оптимизацию по всем возможным уровням иерархии. Замечательно, при этом иерархия сетей порождается в динамическом процессе как бы самопроизвольно, она стимулируется экономическим выигрышем (выигрышем в энергии, затрачиваемой на транспортирование.) Следовательно, для появления иерархии сети транспортных потоков достаточно исходно иметь большую сеть источников стоков нижнего уровня иерархии и условия, обеспечивающие
оптимизацию перемещений по этой сети. Причем, эта динамическая иерархия приводит и к статической иерархии Ai (см. рис. 10б), а число уровней в этой иерархии зависит лишь от исходных условий и устанавливается оптимально. Итак, мы видам, что задача оптимизации транспортных перевозок при ее решении приводит к появлению оптимальной иерархической структуры грузопотоков и связанной с ней статических параметров даже в том случае, когда исходная среда Ai была масштабно однородной. Приведем пример еще одной физической аналогии — аналогии стягивания. Если на карту траекторий в полной реальной сети положить проводники электрического тока и пустить по ним ток в одном направлении величиной обратно пропорциональной Pi, то между ними возникнут силы, достаточные для «растягивания» проводников или их выпрямления, которые будут стремиться их сблизить в соответствии с законом:
F=B(I1I1)(I2I2) делёное на d2
где I — ток, l —длина участка проводника с током, d — расстояние между проводниками. Эта аналогия, очевидно, имеет гораздо большее значение для токов свободных зарядов в межэлектродном пространстве, где в результате, должны образовываться узлы и ребра МК-структуры. Существенная разница между стягиванием в имитационной системотехнической модели и физической модели заключается в том, что в первой операция проводится последовательно и по шагово, а во второй — параллельно и одновременно во всех точках проводника.
Заключение[править]
Описывая задачу оптимизации затратна транспортирование грузов по неоднородной территории, мы показали, что она имеет несколько физических аналогий. Можно использовать эти аналогии для более эффективного решения экономических задач. Но и наоборот — полученные оптимизационные принципы использовать при рассмотрении реальных физических процессов. Во втором случае достаточно более абстрактно подойти к понятиям:территории — неоднородного n — мерного пространства; груза — электрических зарядов, атомов, сигналов и т.п.; дороги — траектории, последовательности прохождения информационных блоков и т.п. А главное, рассматривать оптимизацию не экономических расходов, а энергетических затрат. Если в этом случае применить полученные принципы к процессу генерации ШМ или УСПов, то следует отметить, что аналогия с световым лучом, прокладывающим оптимальную траекторию через неоднородное оптическое пространство и аналогия со стягиванием в иерархические структуры траекторий медленно стекающих электрических зарядов трансформируются из аналогий в детали реального процесса грозы, в котором протекание разряда самоорганизуется по оптимальному пути, что на порядок снижает напряжение «пробоя». Именно в этом мы видим ключ к пониманию процессов правления ШМ и генерации УСПов.