Везде
Об алгоритме «наводнение» приближенного решения гладких задач нелинейного программирования с линейными ограничениями большой размерности
Оглавление
Аннотация Оценить Содержание публикации
Библиография Комментарии
Поделиться
QR
Метрика
Об алгоритме «наводнение» приближенного решения гладких задач нелинейного программирования с линейными ограничениями большой размерности
Аннотация
Код статьи
S042473880006776-2-1
DOI
10.31857/S042473880006776-2
Тип публикации
Статья
Статус публикации
Опубликовано
Авторы
Володина Елена Евгеньевна 
Должность: доцент
Аффилиация: Московский технический университет связи и информатики
Адрес: Москва, Российская Федерация
Лившиц Вениамин Наумович
Должность: главный научный сотрудник
Аффилиация: Федеральный исследовательский центр «Информатика и управление» Российской академии наук
Адрес: Российская Федерация
Выпуск
Том 55 Том 55 номер 4
Страницы
78-88
Аннотация

 

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

Ключевые слова
оптимальное планирование, нелинейное программирование, линейное ограничение, транспортная задача, матрица корреспонденций, затраты, грузопоток, пошаговое распределение потоков, двухэтапный алгоритм оптимизации.
Классификатор
Получено
21.10.2019
Дата публикации
16.12.2019
Всего подписок
87
Всего просмотров
1747
Оценка читателей
0.0 (0 голосов)
Цитировать   Скачать 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) и т.п.

Библиография

1. Белоусова Н.И., Бушанский С.П., Васильева Е.М., Лившиц В.Н., Позамантир Э.И. (2004). Совершенствование теоретических основ, моделей и методов оптимизации развития сети автомобильных дорог. В сб.: «Компьютерный аудит». № 3. С. 114–204.

2. Белоусова Н.И., Бушанский С.П., Васильева Е.М., Лившиц В.Н., Позамантир Э.И. (2008). Информационная технология синтеза сложных сетевых структур нестационарной российской экономики: модели, алгоритмы, программная реализация // Аудит и финансовый анализ. № 1. С. 50–88.

3. Васильева Е.М., Левит Б.Ю., Лившиц В.Н. (1981). Нелинейные транспортные задачи на сетях. М.: Финансы и статистика.

4. Володина Е.Е. (2016). Экономико-методические проблемы государственного управления использованием радиочастотного спектра // Экономическая наука современной России. № 3. С. 124–135.

5. Гибшман А.Е. (1965). О размещении грузовых потоков на параллельных ходах // Вестник ВНИИЖТ. № 6. С. 3–6.

6. Дубовицкий А.Я., Милютин А.А. (1965). Задачи на экстремум при наличии ограничений // Журнал вычислительной математики и математической физики. № 3. С. 395–453.

7. Итоги конкурса программ построения матрицы кратчайших расстояний «Транспорт-83» (1985). // Экономика и математические методы. Т. 21. Вып. 3. С. 565–567.

8. Канторович Л.В. (1959). Экономический расчет наилучшего использования ресурсов. М.: Изд-во АН СССР.

9. Канторович Л.В., Гавурин М.К. (1949). Применение математических методов в вопросах анализа грузопотоков. В сб.: «Проблемы повышения эффективности работы транспорта». М., Л.: Изд-во АН СССР. С. 110–138.

10. Козин Б.С., Козлов И.Т. (1964). Выбор схем этапного развития железнодорожных линий. М.: Трансжелдориздат.

11. Левит Б.Ю. (1971). Алгоритмы поиска кратчайших путей на графе. В сб.: «Труды института гидродинамики СО АН СССР. Моделирование процессов управления». Вып. 4. Новосибирск. С. 117–148.

12. Левит Б.Ю., Лившиц В.Н. (1972). Нелинейные сетевые транспортные задачи. М.: Транспорт.

13. Левитин Е.С., Лившиц В.Н. (2012). Об исследовании монотонности по параметру оптимальных решений для одного класса параметрических оптимизационных задач // Автоматика и телемеханика. № 8. С. 91–110.

14. Лившиц В.Н. (1967). О применении математических методов при выборе оптимальной схемы развития транспортной сети. В сб.: «Труды Первой Всесоюзной конференции по оптимизации и моделированию транспортных сетей». Киев: Изд-во Института кибернетики АН УССР. С. 45–64.

15. Лившиц В.Н. (1984). Оптимизация при перспективном планировании и проектировании. М.: Экономика.

16. Лившиц В.Н. (2013). Системный анализ рыночного реформирования нестационарной российской экономики. М.: Поли Принт Сервис.

17. Лившиц В.Н. (1986). Системный анализ экономических процессов на транспорте. М.: Транспорт.

18. Лившиц В.Н., Позамантир Э.И. (1969). Решение нелинейных многопродуктовых транспортных задач. В сб.: «Поиск экстремума». Томск: Изд-во Томского университета. С. 276–288.

19. Лурье А.Л. (1964). О математических методах решения задач на оптимум при планировании социалистического хозяйства. М.: Наука.

20. Позамантир Э.И. (1974). Об одной динамической модели оптимального развития транспортной сети. В сб.: «Труды ИКТП при Госплане СССР». Вып. 46. С. 161–183.

21. Позамантир Э.И. (2014). Вычислимое общее равновесие экономики и транспорта. Транспорт в динамическом межотраслевом балансе. М.: Поли Принт Сервис.

22. Стиглиц Д. (2003). Глобализация: тревожные тенденции. М.: Мысль.

23. Bertalanffy L. von. (1950). An Outline of General Systems Theory // British Journal for Philosophy of Science. No. 2. Vol. 1. P. 139–164.

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

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

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

Комментарии

Сообщения не найдены

Написать отзыв
Перевести