Везде
On Flood Algorithm for Approximate Solution of Smooth Nonlinear Programming Problems with Linear Constraints of Large Dimension
Table of contents
Annotation Estimate Publication content
References Comments
Share
QR
Metrics
On Flood Algorithm for Approximate Solution of Smooth Nonlinear Programming Problems with Linear Constraints of Large Dimension
Annotation
PII
S042473880006776-2-1
DOI
10.31857/S042473880006776-2
Publication type
Article
Status
Published
Authors
Elena Volodina 
Occupation: Associate Professor
Affiliation: Moscow Technical University of Communications and Informatics
Address: Moscow, Russian Federation
Veniamin Livchits
Occupation: Principal Scientific Researcher
Affiliation: Federal Research Center "Informatics and Management" of the Russian Academy of Sciences, Russia
Address: Russian Federation
Edition
Volume 55 Volume 55 issue 4
Pages
78-88
Abstract

The article analyzes researches in the field of formulation of linear and nonlinear transport problems and algorithms for their solution. The scientific works on the optimization of flows in networks are considered, which made a significant contribution to the creation and development of a new economic and mathematical area as a whole and in many respects stimulated the formation of optimization models and their practical use in a number of industries, first of all in the transport. Particular attention is paid to solving the nonlinear programming problem, when the costs at each transport link depend substantially and nonlinearly not only on the link parameters, but also on the total volume and structure of the cargo flow passing through it. That is, the solution of a large-sized nonlinear inhomogeneous transport problem of a network structure is given when setting the initial information about transportation in the form of a large-sized correspondence matrix. An effective method for optimizing the distribution of inhomogeneous flows over a fixed nonlinear transport network is described. Based on the tools of functional analysis, the theorem of validity of using the conditions of potentiality of the optimal plan for traffic flows in the nonlinear case is proved. The proposed two-stage algorithm for optimizing the step-by-step distribution of inhomogeneous flows over fixed nonlinear transport network is discussed, based on the given evidence of the legitimacy of the principle of potentiality of an optimal transportation plan being extended to this case.

 

Keywords
optimal planning, nonlinear programming, linear constraint, transport problem, correspondence matrix, costs, cargo flow, step-by-step flow distribution, two-stage optimization algorithm.
Received
21.10.2019
Date of publication
16.12.2019
Number of purchasers
87
Views
1752
Readers community rating
0.0 (0 votes)
Cite   Download pdf
1

1. ВВЕДЕНИЕ
2 Рассмотрим задачу нелинейного программирования
3

min f(X), AX=B, X>0,
4 где f — гладкий, необязательно выпуклый сепарабельный функционал; А – прямоугольная матрица размером m×n; X — вектор первого ортанта Rn. С такими задачами нередко приходится сталкиваться в экономике при решении задач моделирования размещения однородного и многономенклатурного производства (Лившиц, 1984), оптимизации потоков грузов и пассажиров в нелинейных транспортных сетях (Лившиц, 1986, 2013) и т.п. При наличии в функционале f невыпуклостей и достаточно большой размерности матрицы m×n приведенная задача весьма непроста в смысле получения даже приближенного, но достаточно хорошего (близкого к глобальному или локальному оптимуму), допустимого решения. Для достижения этой цели воспользуемся несколько неожиданной подсказкой, которую предоставила одному из авторов непосредственно сама природа.
5 Речь идет о том, что в 1934 г. в относительно небольшом донбасском городе Луганске произошло очень редкое для этих мест природное явление — большое наводнение, виновником которого в весенний паводок стала небольшая протекающая вблизи, а частично через окраину города, мелкая речушка Луганка. Поднявшись в ней на несколько метров паводок очень медленно, почти нежно, монотонно повышая дискретными всплесками уровень разлива, в течение нескольких апрельских дней залил все окраинные и центральные улицы города, на которых даже стали ходить лодки, так как через три дня после начала водяной поток был уже толщиной 60–80 см.
6 Когда в 1964 г. В.Н. Лившицу пришлось в плановом порядке в Институте комплексных транспортных проблем (ИКТП) Госплана СССР разрабатывать эффективный метод оптимизации распределения всех заданных таблицей корреспонденций грузовых потоков по железнодорожной сети страны, он вспомнил об этом наводнении. Поставленная перед ним задача состояла в том, чтобы построить достаточно эффективный допустимый сетевой план освоения всех необходимых перевозок, нередко заданных в виде большой шахматной таблицы корресподенций, т.е. указать, как (по каким дугам) должна пройти каждая корреспонденция от своего зарождения (места производства или складирования потенциального вида груза) до места его погашения (места потребления или повторного складирования) привезенного груза и какие в итоге будут загрузки всех звеньев и дуг железнодорожной сети, с тем чтобы суммарные затраты на этот процесс по всей сети были наименьшими. Естественно, что суммарные затраты (т.е. оптимальное значение целевой функции в сформулированной выше сетевой транспортной задаче) будут сильно зависеть от того, как математически выражаются затраты на каждом элементе сети, и с этой точки зрения обычно транспортные задачи классифицируют как линейные (затраты на любом элементе пропорциональны его загрузке) и нелинейные (зависимости имеют более сложный нелинейный характер).
7 Не останавливаясь подробно на линейном случае1, мы последовательно, начиная с более простой линейной постановки транспортной сетевой задачи, рассмотрим алгоритмы оптимизации для обоих случаев, указывая авторов наиболее эффективных и использованных нами алгоритмов. При этом в нелинейном случае весьма существенно, что затраты на каждом транспортном звене (на паре смежных ориентированных железнодорожных и автодорожных дуг) существенно и нелинейно зависят не только от параметров звена, но и от суммарного объема и структуры проходящего по нему грузопотока. Иными словами, и это первое, что пришлось понять и обосновывать, речь идет о необходимости эффективного решения крупноразмерной нелинейной неоднородной транспортной задачи сетевой структуры указанного вида (Лившиц, 1967; Лившиц, Позамантир, 1969) — оптимизация распределения неоднородных потоков по фиксированной нелинейной транспортной сети.
1. В (Канторович, Гавурин, 1949) был опубликован разработанный авторами знаменитый алгоритм оптимального распределения неоднородных потоков по транспортной сети. Затем этому алгоритму были посвящены еще многие работы в нашей стране (см. список литературы в конце статьи) и за рубежом.
8

2. РАБОТЫ ПО РЕШЕНИЮ ЛИНЕЙНЫХ СЕТЕВЫХ ТРАНСПОРТНЫХ ЗАДАЧ И ИХ РАЗВИТИЕ

9 Задачами оптимального планирования производства, в том числе и оптимизации потоков в транспортных сетях, еще в 1939 г. серьезно занялся Леонид Витальевич Канторович (Канторович, 1939). Прошло уже 70 лет, c тех пор как в 1949 г. вышла знаменитая статья (Канторович, Гавурин, 1949), написанная еще в 1940 г. В этой статье были описаны алгоритмы и примеры расчета оптимальных неоднородных потоков в линейных сетях c ограничениями и без ограничений пропускной способности звеньев. То есть (по существу) решение в рассматриваемых условиях сетевой транспортной задачи было (впрочем, как и большинство экономических и транспортных работ Л.В. Канторовича) написано достаточно обще и строго, хотя просто и понятно. Статья вызвала поток связанных с темой научных исследований и практических применений на различных видах транспорта и в других отраслях.
10 Рассмотрим алгоритм решения для линейного случая, следуя достаточно текстуально авторскому изложению (Канторович, 1959), начиная с принятой там вербальной постановки задачи и адекватной ей математической модели. Приведем формальную постановку сетевой транспортной задачи и условий потенциальности оптимального плана, следуя (Канторович, Гавурин, 1949; Канторович, 1959) основополагающим работам в теории оптимального планирования.
11 Пусть имеется т пунктов соединенных транспортной сетью, состоящей из r участков. По участку сети s (s = 1, ..., r) можно производить перевозки из пункта is в пункт js, затраты по перемещению единицы груза составляют as. В каждом пункте-узле сети i (i = 1, ..., m) задан объем потребления bi некоторого однородного продукта (для пунктов потребления bi>0, для пунктов производства bi<0, для прочих пунктов bi=0 ); причем ∑i=1mbi=0 (суммарные объемы производства и потребления совпадают). Требуется найти такой вектор перевозок π=(h1,...,hr), где hs — объем перевозок по участку сети s s=1,  ...,  r, чтобы
12 Z=∑s=1rashs→min
13 при условиях:
14 1) hs≥0,    s=1,...,r;
15 2) ∑js=ihs-∑is=ihs=bi,    i=1,...,m (в каждый пункт поступает необходимое количество продукта).
16 В (Канторович, 1959, с. 289, теорема 5) приводится ранее доказанная им теорема: для оптимальности допустимого вектора перевозок π=(h1,...,hr), удовлетворяющего условиям 1 и 2, необходимо и достаточно, чтобы существовали такие числа с1,…, сm, называемые потенциалами пунктов, для которых выполняются условия:
17
  1. сjs-cis≤as,    s=1,...,r;
  2. сjs-cis=as,    hs≠0,
18 где cis и cjs — потенциалы инцидентных пунктов i и j, т.е. пунктов непосредственно связанных с участком s.
19 Приведенные условия потенциальности оптимального плана допускают трактовку в терминах теории оптимального планирования в виде требований бесприбыльности и безубыточности наивыгоднейших перевозок. Согласно (Лурье, 1964) потенциалы должны быть такими, чтобы перевозки не могли принести прибыль (т.е. оценка груза в любом пункте потребления не должна превышать оценки его в любом пункте производства, увеличенной на расходы по перевозке в данный пункт сjs≤cis+as ). В то же время (безубыточность) перевозки должны быть такими, чтобы оценка груза в пункте производства и издержки его на перевозки в точности покрывались оценкой груза в пункте потребления s = 1, ..., r; сjs=cis+as.
20 В работе (Лурье, 1964) показано, что потенциалами можно пользоваться не только для проверки оптимальности плана, но и для экономического анализа транспортных задач и последовательного улучшения плана перевозок, если он неоптимален. Разность между потенциалами двух пунктов производства показывает, насколько уменьшились бы транспортные затраты в оптимальном плане, если бы ресурсы пункта производства с большим потенциалом увеличились на единицу за счет пункта с меньшим потенциалом. Аналогичное утверждение (но об увеличении транспортных затрат) можно сделать при сравнении потенциалов пунктов потребления и соответствующем изменении его размеров. При одновременном увеличении на единицу размеров потребления в некотором пункте js и размеров производства в некотором пункте is величина сjs-cis покажет, как изменятся транспортные затраты при наиболее выгодном использовании ресурсов.
21 Если рассматривается транспортная задача с ограничениями пропускной способности отдельных участков, то применительно к данной линейной постановке требуется добавление условия:
22 3) hs≤qs,    s=1,...,r, где qs — пропускная способность s участка.
23 В этом случае характеристика оптимального плана принимает вид, указанный в (Канторович, 1959, с. 290). Там же (с. 290, теорема 6) приводится теорема: для оптимальности допустимого вектора перевозок π=(h1,...,hr), удовлетворяющего условиям 1–3, необходимо и достаточно, чтобы существовали такие числа c1,...,cm (потенциалы) и такие числа d1,...,dm (ренты или прокатные оценки отдельных участков маршрута следования, рассчитанные на единицу груза), что:
24
  1. сjs-cis≤as+ds,    s=f,...,r;
  2. сjs-cis=as+ds,    если    hs>0;
  3. ds≥0, причем ds=0, если hs<qs.
25 Если as — расстояние между пунктами is и js, то получается так называемая задача о кратчайшем пути, имеющая очень важное значение не только для распределения грузо- и пассажиропотоков на сети, но и при решении многих других технико-экономических задач.
26 Отысканию эффективных и быстродействующих алгоритмов поиска кратчайших путей уделялось большое внимание на протяжении нескольких десятилетий. Говоря о развитии этого частного, но весьма важного направления в решении сетевых транспортных задач, отметим, что довольно подробный обзор состояния этой проблемы в рассматриваемом периоде и классификация существующих алгоритмов приведены в (Васильева, Левит, Лившиц, 1981). Как показали итоги проведенного в 1985 г. всесоюзного конкурса алгоритмов и программ построения матрицы кратчайших расстояний «Транспорт-83» (Итоги конкурса…, 1985), одним из наиболее эффективных алгоритмов тогда оказался предложенный Б.Ю. Левитом метод «двухсторонняя очередь» (Левит, 1971).
27

3. ИСПОЛЬЗОВАНИЕ УСЛОВИЙ ПОТЕНЦИАЛЬНОСТИ ОПТИМАЛЬНОГО ПЛАНА ПЕРЕВОЗОК ДЛЯ РЕШЕНИЯ НЕЛИНЕЙНЫХ СЕТЕВЫХ ТРАНСПОРТНЫХ ЗАДАЧ
28 Другое важное направление развития идей Л.В. Канторовича по решению сетевых потоковых транспортных задач сформировалось к середине 1960-х годов, когда от рассмотрения линейных задач этого типа перешли к нелинейным. Это было вызвано в том числе потребностями практики планирования потоков, особенно на железнодорожном транспорте, где при возросших грузопотоках затраты на однопутных линиях стали иметь явно выраженный нелинейный характер. По этим причинам при определенных уровнях загрузки возникала целесообразность, а иногда и необходимость менять технический уровень отдельных участков сети или строить разгружающие новые, так как пропускной способности уже оказывалось недостаточно. Ниже нами будут рассмотрены две важные задачи, относящиеся к анализу и синтезу нелинейных транспортных сетей. Построение и обоснование приводимых алгоритмов опирается на сформулированное выше свойство потенциальности оптимального плана распределения перевозок по сети. Анализ показал, что это свойство, первоначально доказанное и опубликованное в классических работах Л.В. Канторовича 1940-х годов для однородных потоков в линейных сетях, обобщается и на нелинейные сети при неоднородных потоках. Именно для этого, достаточно общего, случая ниже будут излагаться модели и алгоритмы оптимизации.
29 Рассмотрим следующую содержательную постановку и модель процесса оптимизации потоков в такой сети.
30 3.1. Задача оптимизации распределения неоднородных потоков по фиксированной нелинейной транспортной сети. Применительно, например, к железнодорожной или автотранспортной сети страны, считаются заданными:
31 а) конфигурация действующей транспортной сети;
32 б) предполагаемые пункты и объемы отправления и прибытия различных грузов (или соответствующая им шахматная таблица корреспонденций), а также размеры и маршруты следования пассажиропотоков различных категорий;
33 в) состояние всех элементов сети на момент планирования, а также все необходимые эксплуатационно-технические и экономические характеристики, позволяющие для каждого элемента сети (звеньев, узлов и т.д.) в зависимости от объема и структуры выполняемой им транспортной работы рассчитать соответствующие величины расходов на перевозки.
34 Требуется определить, как следует освоить все необходимые перевозки, т.е. как направить потоки по сети и сформировать маршруты следования по заданной сети каждой корреспонденции от пунктов их возникновения до пунктов их погашения, чтобы суммарные затраты на перевозки были минимальны.
35 Расчетная модель при этом представляется в виде нелинейной сетевой транспортной задачи
36 min FX=∑jFjXj (1)
37 при ограничениях:
38 SpX=b; (2)
39 ∑lxjl≤dj    ∀  j; xjl≥0    ∀ i, l; (3)
40 где
41 X=Xj=xjl≥0; (4)
42 b=bi=bil;
43 Х — искомый вектор загрузки сети потоками всех родов грузов и пассажиров; F(X) — нелинейная (в рамках рассматриваемой задачи обычно выпуклая) функция затрат, связанных с освоением потока X; b — вектор объемов отправления–прибытия в вершинах сети; Xj — вектор загрузки элемента (звена) сети j; xjl — загрузка элемента сети j потоками вида l; bi — вектор объемов отправления–прибытия в вершине i; bil — объемы отправления–прибытия l вида груза в вершине i; di — пропускная способность i элемента сети; uil — потенциал i вершины по l виду груза; δj — прокатная оценка (рента) j элемента сети; Sp — обобщенная матрица инциденций, соответствующая перевозке неоднородных потоков грузов Sp=Sijl , причем имеет место l = 1,…, p; sijl=1, если дуга j выходит из узла i и по ней может осуществляться перевозка груза l; sijl=-1, если дуга j входит в узел i и по ней может ввозиться груз l; sijl=0 — в остальных случаях.
44 Для реальной сети приведенная задача часто имеет большую размерность, и решать ее общими методами математического программирования довольно непросто. Приходится использовать ее транспортную специфику. Поэтому предварительно докажем правомерность распространения (естественно, в измененной адекватной форме) условий Канторовича о потенциальности оптимального плана потоков на случай нелинейных сетевых транспортных задач. Покажем, что имеет место следующая теорема.
45 Теорема. Для того чтобы допустимый план потоков нелинейной сетевой транспортной задачи вида (1)–(4) был оптимален, необходимо, чтобы он был потенциален2.
2. Определение потенциалов для нелинейного случая будет ясно ниже при доказательстве теоремы (подробнее (Ливщиц, 2013)).
46 Доказательство теоремы приведем, опираясь на необходимые условия экстремума, изложенные, например в (Дубовицкий, Милютин, 1965). Согласно этой работе для задач типа (1)–(4) должно быть пустым пересечение конусов допустимых направлений для ограничений и конуса направлений убывания для функционала.
47 Для функционала F направления его убывания образуют выпуклый конус T1, допустимые направления для ограничения X≥0 — выпуклый конус T2, а допустимые направления для ограничения SpX=b  — подпространство Q. При этом T10≠∅ и T20≠∅ , где Ti0 обозначает внутренность конуса Ti, т.е. в итоге необходимым условием минимума в некоторой точке X˘ является соблюдение в ней равенства
48 T10∩T20∩Q=∅. (5)
49 Для отыскания оптимальной точки X˘ применим следующую теорему Дубовицкого–Милютина: чтобы выполнялось условие T10∩…∩Ts0∩Q=∅, необходимо и достаточно, чтобы существовали линейные функционалы w1,…,ws,q, не равные нулю одновременно и такие, что
50 w1+…+ws+q=0. (6)
51 При этом q∈Q*, wi∈Ti*, где Ti* — конус, сопряженный с конусом Ti, т.е. скалярные произведения
52 wi,Ti≥0,    q,Q=0. (7)
53 В силу выпуклости функционала F необходимое условие минимума будет являться и достаточным. В нашем случае условие (6) примет вид
54 w1+w2+q=0, (8)
55 где w1=-gradF=-∂F/∂xjl, w2=tjl. При X≥0 все компоненты вектора w2 неотрицательны, и, кроме того, в точке их оптимума выполняется условие дополняющей нежесткости, т.е.
56 w2X˘=0. (9)
57 Так как в ограничении SpX=b  матрица Sp — матрица с постоянными членами (1, –1, 0), то:
58 q=Sp*u*=qjl. (10)
59 При этом Sp*  — оператор, сопряженный к Sp, т.е. транспонированная матрица к Sp ; u*={uil} — вектор потенциалов всех узлов для каждого рода груза. Непосредственной проверкой нетрудно убедиться в том, что:
60 qjl=ui1l-ui2l, (11)
61 где i1 и i2 узлы, ограничивающие дугу j. Подставляя найденные значения w1,w2 и q в (8), получим для всех i, j и l условие
62 -∂F∂xjl+qjl+tjl=0; (12)
63 и, так как tjlx˘jl=0, то при x˘jl>0 имеем tjl=0.
64 Необходимым и достаточным условием достижения минимума в точке X˘ является существование для каждого невзаимозаменяемого рода груза l такой системы чисел (потенциалов) ujl, чтобы для каждой дуги j выполнялось условие:
65 ui1l-ui2l≤∂F∂xjl, (13)
66 причем при x˘jl>0 имеет место строгое равенство:
67 ui1l-ui2l=∂F∂xjl. (14)
68 Следовательно, потенциальность оптимального плана нелинейной сетевой транспортной задачи доказана.
69 В нелинейном случае нет необходимости учитывать ограничения пропускной способности звеньев сети, так как это проще сделать соответствующим выбором характера нелинейности функций затрат на перевозки.
70 Теперь перейдем к рассмотрению способов использования полученных обобщенных условий Канторовича — потенциальности оптимального плана нелинейных сетевых потоков для реализации соответствующих алгоритмов.
71 Для этого сначала проанализируем простейшую сеть с нелинейными характеристиками, т.е. две параллельные линии, образующие замкнутый контур, по которым надо оптимально распределить общий поток Х. Условия оптимальности для этой частной задачи были впервые изложены в (Гибшман, 1965).
72 Когда требуется найти minϕx1+ψx2 при ограничениях x1+x2=Х,    xi≥0,    i=1,    2, где xi — потоки на линиях; Х, ϕx1,  ψx2 — заданный объем перевозок и нелинейные функции затрат перевозки по линиям, легко показать, что если в оптимальном плане x1*>0 и x2*>0 , то ϕ'(x1*)=ψ /(x2*). Другими словами, когда поток распределяется по обеим линиям, их загрузка в оптимальном плане перевозок должна быть такой, чтобы совпадали дифференциальные стоимости перевозок (стоимости перевозок «последней тонны»). Это условие оптимальности допускает ясную экономическую интерпретацию: если на одной из линий стоимость перевозки последней тонны груза ниже, то план неоптимален и его можно улучшить, передав с дорогой линии последнюю тонну на эту более дешевую линию.
73 Нетрудно убедиться, что такое условие оптимальности есть частный случай обобщенных условий потенциальности оптимального плана перевозок по нелинейной сети, которые были получены в приведенной выше теореме, и опубликованы, например, в (Лившиц, 1967; Левит, Лившиц, 1972).
74 Учет реального характера затрат на перевозки, естественных нелинейностей, связанных с простоями поездов при скрещениях, обгонами и торможениями «быстрых» автомобилей «медленными» в плотном потоке и т.д., обусловили необходимость создания методов, приспособленных к решению больших сетевых нелинейных транспортных задач с несепарабельным функционалом. Один из таких достаточно эффективных алгоритмов, известный как метод пошагового распределения потоков, подробно проанализирован в (Левит, Лившиц, 1972). Этот метод в значительной степени опирается на обобщенные условия потенциальности Канторовича (13), (14), он широко апробирован, его работоспособность проверена на сетях реальных размеров, поэтому далее остановимся на нем подробнее.
75 На эти условия опираются разработанные Э.И. Позамантиром алгоритмы (Лившиц, Позамантир, 1969; Позамантир, 1974).
76 Сущность метода пошагового распределения потоков состоит в следующем. Заданный объем перевозок реализуется по сети относительно небольшими долями, причем каждая доля направляется по кратчайшему (в смысле дифференциальных затрат) пути. После размещения очередной доли меняются загрузки многих элементов сети, и, следовательно, из-за нелинейности функционала меняются дифференциальные стоимости перевозок. Это означает, что следующая доля объема перевозок распределяется, вообще говоря, по другим кратчайшим маршрутам. Допустимый план считается построенным, когда размещен весь заданный объем перевозок (вся шахматная таблица корреспонденции), причем качество плана зависит от трех главных параметров: числа шагов, величины долей корреспонденции, распределяемых на каждом шаге, и частоты пересчета дифференциальных затрат. Наилучшее соотношение между параметрами обычно выбирается экспериментальным путем (Левит, Лившиц, 1972).
77 В случае когда различные маршруты следования корреспонденции или их частей не содержат одинаковых элементов (звеньев сети), допустимый план является и оптимальным. Для сетей сложной конфигурации маршруты следования долей одной и той же или разных корреспонденций чаще всего содержат одинаковые звенья, поэтому полученный план не обязательно оптимален и допускает улучшение. Улучшение такого плана базируется на следующем положении: поскольку потоки на маршрутах определяются неоднозначно, можно предположить, что часть из них была распределена неправильно (не лучшим образом). Следовательно, целесообразно снять некоторую долю загрузки всех элементов сети, которая была получена на первом этапе алгоритма, и перераспределить ее заново по тем же правилам. При этом далеко не все корреспонденции изменят свой маршрут, однако можно показать, что даже изменения маршрута следования некоторых корреспонденций оказывается достаточным для некоторого улучшения допустимого плана.
78 Второй этап алгоритма можно повторить несколько раз, снимая на каждом шаге уменьшаемую долю корреспонденции. В (Левит, Лившиц, 1972) доказано, что, используя приводимый ниже алгоритм (15)–(18), например, для гладких и выпуклых целевых функций, такая итеративная процедура является релаксационной и обеспечивает сходимость к оптимальному плану перевозок.
79

Алгоритм решения задачи
80 Этап 1. Формирование достаточно хорошего первоначального допустимого плана:
81 X0=∑p=1MZ-p,Z-p:    mingrad  F∑j=0P-1Z-j,ZP, (15)
82 SZp=γpb, Z0=0, (16)
83 ∑P=1γp=1,    γp≥0.
84 На первом этапе суммируются оптимальные планы задач (15) и (16) c сокращенными объемами отправления и прибытия. Они по существу имитируют поведение природы г. Луганска во время наводнения в 1934 г. Поэтому не случайно, когда на Всесоюзной конференции по математическому программированию и смежным вопросам В.Н. Лившиц впервые сделал доклад о первом этапе алгоритма (Лившиц, 1967), литовский математик Й.Б. Моцкус тут же высказал гипотезу, что и в задачах невыпуклого программирования в итоге первого этапа будет получаться очень хорошее приближение к оптимуму, а иногда, возможно и оптимальное решение. В (Белоусова и др., 2008) авторы проверили эту гипотезу, и она оказалась достаточно корректной (но не всегда) — отклонение от глобального оптимума, найденного после второго этапа, нередко было менее 3%, но были случаи и 5%.
85 Этап 2. Итеративное улучшение допустимого плана на итерации h:
86 Xh+1=1-khXh+Yh, (17)
87 Yh:    mingradFXh-khXh,Y¯h,
88 Y-h≥0, SY-h=khb. (18)
89 При таком способе выбора шагов к итеративная процедура (17)–(18) относится к типу процедур Браун–Робинсон, которая сходится к оптимальному решению, вообще говоря, может быть, локальному, если функция F невыпуклая: kh→0;    ∑hkh→∞.
90 Нетрудно убедиться, что приведенные выше условия потенциальности и построенные на их основе алгоритмы оптимизации потоков однородной и неоднородной сетевой транспортной задачи в линейном (Канторович, Гавурин, 1949) и нелинейном случаях (Лившиц, 1967, 2013) явно используют методологию и инструментарий системного анализа (Bertalanffy, 1950; Лившиц, 1986, 2013). Значимость этих идей и обращение к ним в последующих периодах ни в коей мере не уменьшились, о чем можно судить по достаточно представительному, хотя и ни в коей мере не претендующему на полноту, обзору и анализу публикаций по проблематике оптимизации потоков в сетях, содержащимся, например, в работах (Белоусова и др., 2004, 2008; Quinet, 1990; 1998; Левитин, Лившиц, 2012; Козин, Козлов, 1964; Лившиц, 1986, 2013; Позамантир, 2014; Stiglitz, 2002; Стиглиц, 2003).
91 В частности, в (Белоусова и др., 2004, 2008) большое внимание уделено информационной технологии решения задач синтеза сложных иерархических нелинейных сетевых структур на базе динамических моделей и алгоритмов их компьютерной реализации, включая блоки имитационного моделирования, уточнения с учетом факторов макроэкономической нестационарности используемых в алгоритмах развития сети критериев (как стоимостных нормативных, так и допускающих самоорганизацию потоков по сети) и, что особенно важно, учитывающих диверсификацию источников и схем финансирования в рыночных условиях.
92

5. ЗАКЛЮЧЕНИЕ

93 В статье приведен краткий обзор важнейших работ по экономико-математическому моделированию и оптимизации транспортных сетей, включая разработанный авторский вариант — двухэтапный алгоритм пошагового распределения неоднородных потоков по нелинейной необязательно выпуклой и сепарабельной сети, работоспособность и эффективность которого при оптимизации потоков в больших сетях была успешно проверена в экспериментальных расчетах на примерах железнодорожной сети России.
94 Сетевые транспортные задачи имеют чрезвычайно широкую сферу применения и допускают различного рода обобщения. Эти задачи используются не только для планирования движения транспорта — выбора направлений грузо- и пассажиропотоков в сетях, при установлении транспортно-экономических связей, определении наиболее выгодных вариантов развития сети и т.д., но могут применяться в качестве самостоятельных блоков в задачах размещения однородного и неоднородного производства, при планировании материально-технического снабжения, для решения многих задач в градостроительстве, энергетике, связи, распределении государственных природных ресурсов, в том числе радиочастотного спектра (Володина, 2016) и т.п.

References

1. Belousova N.I., Bushanskij S.P., Vasil'eva E.M., Livchits V.N., Pozamantir E.I. (2004). Improving the Theoretical Foundations Models and Methods for Optimizing the Development of the Road Network. Computer Audit, 3, 114–204 (in Russian).

2. Belousova N.I., Bushanskij S.P., Vasil'eva E.M., Livchits V.N., Pozamantir E.I. (2008). Information Technology of Synthesis of Complex Network Structures of Non-Stationary Russian Economy: Models, Algorithms, Software Implementation. Audit and Financial Analysis, 1, 50–88 (in Russian).

3. Bertalanffy L. von (1950). An Outline of General Systems Theory. British Journal for Philosophy of Science, 2, 1, 139–164.

4. Dubovickij A.YA., Milyutin A.A. (1965). Tasks for Extremum in the Presence of Restrictions. Computational Mathematics and Mathematical Physics, 3, 395–453 (in Russian).

5. Gibshman A.E. (1965). On the Placement of Cargo Flows on Parallel Moves. Vestnik of the Railway Research Institute (Vestnik VNIIZHT), 6, 3–6 (in Russian).

6. Kantorovich L.V. (1959). Economic Calculation of the Best Use of Resources. Moscow: Izd. AN SSSR (in Russian).

7. Kantorovich L.V., Gavurin M.K. (1949). The Use of Mathematical Methods in the Cargo Flow Analysis. In: “Problems of Increasing the Efficiency of Transport”. Moscow, Leningrad: Izd-vo AN SSSR, 110–138 (in Russian).

8. Kozin B.S., Kozlov I.T. (1964). The Choice of Schemes for the Stage Development of Railway Lines. Moscow: Transzheldorizdat (in Russian).

9. Levit B.Yu. (1971). Algorithms for Searching the Shortest Paths on a Graph. In: “Proceedings of the Institute of Hydrodynamics of the USSR Academy of Sciences. Modeling of Management Processes”, 4, 117–148 (in Russian).

10. Levit B.Yu., Livchits V.N. (1972). Nonlinear Network Transport Problems. Moscow: Transport (in Russian).

11. Levitin E.S., Livchits V.N. (2012). On the Study of Monotonicity with Respect to the Parameter of Optimal Solutions for a Class of Parametric Optimization Problems. Avtomatika i telemekhanika, 8, 91–110 (in Russian).

12. Livchits V.N. (1967). On the Application of Mathematical Methods in Choosing the Optimal Scheme for the Development of the Transport Network. In: “Proceedings of the Institute of hydrodynamics of the USSR Academy of Sciences. Modeling of management processes AN USSR”, 45–64 (in Russian).

13. Livchits V.N. (1984). Optimization in Forward Planning and Design. Moscow: Ekonomika (in Russian).

14. Livchits V.N. (1986). System Analysis of Economic Processes in Transport. Moscow: Transport (in Russian).

15. Livchits V.N. (2013). System Analysis of Market Reform of Non-Stationary Russian Economy. Moscow: Poli Print Servis (in Russian).

16. Livchits V.N., Pozamantir E.I. (1969). Solving Nonlinear Multiproduct Transport Problems. In: “Search for the Extremum”. Tomsk: Izd-vo Tomskogo universiteta, 276–288 (in Russian).

17. Lur'e A.L. (1964). On the Mathematical Methods for the Optimum Solving Problems in the Planning of a Socialist Economy. Moscow: Nauka (in Russian).

18. Pozamantir E.I. (1974). On One Dynamic Model of Optimal Development of the Transport Network. In: “Proceedings of the Institute of Complex Transport Problems at the State Planning Committee of the USSR”, 46, 161–183 (in Russian).

19. Pozamantir E.I. (2014). Computable General Equilibrium of Economy and Transport. Transport in Dynamic Inter-Industry Balance. Ì.: Poli Print Servis (in Russian).

20. Quinet E. (1990). Analyse economique des transports. Paris: Presses Universitaires de France.

21. Quinet E. (1998). Principes d’ Economie des Transports. Paris: Economica.

22. Results of the Competition of Programs for the Construction of the Shortest Distance Matrix “Transport-83” (1985). Economics and Mathematical Methods, 21, 3, 565–567 (in Russian).

23. Stiglic D. (2003). Globalization: Disturbing Trends. Moscow: Mysl' (in Russian).

24. Stiglitz J.E. (2002). Globalization and Its Discontents. New York, London: W.W. Norton & Company.

25. Vasil'eva E.M., Levit B.YU., Livchits V.N. (1981). Nonlinear Transport Problems on Networks. Moscow: Finansy i statistika (in Russian).

26. Volodina E.E. (2016). Economic and Methodical Problems of State Management of the Radio Frequency Spectrum Uses. Economic Science of Contemporary Russia, 3, 124–135 (in Russian).

Comments

No posts found

Write a review
Translate