Кантарович

Эта связь была освоена не сходу, -- я помню, что  ленинградские мастера по теории игр первое время не воспринимали в расчет, что решение матричной  игры с нулевой суммой есть задачка линейного программирования, и, непременно прекрасный, способ решения игр, принадлежащий Дж. Робинсон, числился чуток ли не единственным численным способом нахождения значения игры. В итоговом подтверждении теоремы фон Неймана о минимаксе (первое подтверждение было топологическим и употребляло теорему Брауэа) практически содержалась теория двойственности. Позднее эквивалентость игровой задачки и линейного программирования обширно использовалась.

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

В связи с  линейным и выпуклым программированием  на первый план из комбинаторных теорий выступает комбинаторная геометрия  выпуклых и целочисленных многогранников и комбинаторика симметрической группы. Необходимыми работами первого  периода по комбинаторике многогранников была книга Грюнбаума, и статьи Кли и др, а в комбинаторике - работы Дж. Рота и Р.Стенли. Сразу появились близкие темы в теории особенностей (многогранники Ньютона), алгебраической геометрии (торические обилия и целочисленные многогранники) и др. А позднее раскрылись обширные связи с симметрической группой, комбинаторной теорией диаграмм Юнга - одной из главных тем "новой комбинаторики", - а также посетами и матроидами. Интересно, что практически сразу (и независимо) к ряду близких задач комбинаторики пришел И.М.Гельфанд (матроиды, клеточки Шуберта, вторичные многогранники), назвавший комбинаторику математикой ХХI века. Сейчас новейшие комбинаторные задачки являются ключевыми в разнообразных математических проблемах.

Мой энтузиазм  к к линейному программированию в первые годы появился совсем независимо от моих математических пристрастий тех лет и, в частности, не лишь потому, что я обучался у Л.В. Функциональному анализу и слушал его первые захватывающие рассказы о линейном программировании и его применении в экономике. В тот момент (1956-58 гг). это был быстрее практический, чем теоретический энтузиазм.

Дело в том, что отказавшись после окончания  института по неким причинам от аспирантуры, я работал в военно-морском  ВЦ, и заинтересовался задачей многомерного наилучшего приближения как прикладник. Одной из моих задач в этом ВЦ было представление таблиц стрельбы в ЭВМ, и я предложил аппроксимировать их заместо того, чтоб хранить в памяти ЭВМ. Я определил некое обобщение задачки о наилучшем приближении, а конкретно, о кусочно полиномиальном наилучшем приближении (ни о каких сплайнах тогда нам понятно не было) для функций нескольких переменных. Позднее, когда я уже стал работать в институте, в 60-х гг. Данной задачей занимались мои первые дипломанты. Еще позднее была написана подробная статья об этом.

равномерно мой  энтузиазм к задачке о наилучшей  аппроксимации превратился в  энтузиазм к самому способу, позволяющему её решить, - одним из них и был  способ линейного программирования. Г.П.Акилов посоветовал поговорить по этому поводу с Г.Ш.Рубинштейном. Во время наших бесед Г.Ш. Дополнял доклады Л.В. Рассказами о близких работах остальных математиков, - непременно, Г.Ш. Был тогда одним из наилучших знатоков линейного программирования и всего этого круга идей Л.В. -- О работах американцев (симплекс-способе) мы узнали несколько позднее. Главным для нас был "способ разрешающих множителей". Он укладывался как частный вариант в то, что у нас называлось симплекс-способом, но наше понимание было шире американского, -- классический симплекс-способ Данцига есть также частный вариант этого, более общего, класса способов. К огорчению, как частенько бывает, российская терминология не была довольно обмыслена и зафиксирована и слова "симплекс-способ" допускают массу разных толкований.

Школа численных  способов линейного программирования в СССР была только сильной, и в  этом безусловная награда Л.В. И  двух его главных помощников первой поколения -- В.А.Залгаллера и Г.Ш.Рубинштейна, а позднее И.В.Романовского и его  группы, В.Л.Булавского, в Москве -- Д.Б.Юдина и Е.Г.Гольштейна и др. В последующем с развитием вычислительной и программистской техники численное решение всех задач разумной размерности стало легкодоступным.

В) Метрика Канторовича.

Однажды весной 1957 г. Г.Ш.Рубинштейн поведал мне, что он наконец сообразил, как можно употреблять теорему Л.В. О задачке Монжа (сейчас её называют задачей Монжа - Канторовича), доказанную им в заметке ДАН 1942 г. - А конкретно, как метрику Канторовича, т.Е. Наилучшее значение целевого функционала в транспортной задачке, употреблять для введения нормы в пространстве мер и как критерий Л.В. Становится теоремой двойственности с пространством функций Липшица. По сути дела, это было принципиальным методическим замечанием, так как сама метрика уже была описана в заметке Л.В. Но конкретно эта работа Л.В. И Г.Ш., Появившаяся в Вестнике ЛГУ в 1958 г., В выпуске, посвященном Г.М.Фихтенгольцу, содержала общую теорию известной сейчас метрики, назывемой время от времени метрикой Канторовича-Рубинштейна, либо транспортной.

Кстати, в том  же номере была опубликована и моя  первая работа вместе с моим первым управляющим Г.П.Акиловым, посвященная  новому определению распределений  Шварца, но в которой также в  качестве одного из примеров рассматривалась эта, лишь что появившаяся, метрика. В той же работе Л.В. И Г.Ш.-- Это традиционно вспоминается реже, - был дан критерий оптимальности первозок в двойственных определениях -- функций Липшица либо потенциалов.

С тех пор  я превратился в неизменного  пропагандиста данной замечательной метрики, и убедил совсем многих математиков наших и забугорных, в приоритете Л.В. И в значимости данной работы. Она переоткрывалась большущее число раз и потому имеет совсем много заглавий (метрика Вассерштейна, Орнштейна и т.Д., Не знавших о работе Л.В.) А сам способ её введения известен как спаривание (coupling), как способа фиксированных маргинальных мер и т.Д. Её внедрения обширны и в самой математике, и в статфизике, и в математической статистике, в эргодической теории и в остальных приложениях. О ней написаны книги, которые далеко не исчерпывают всех её сторон. Очень близки к ней метрика Леви - Прохорова - Скорохода, популярная в теории вероятностей. Возможность дальнейшего обобщения данной метрики для широкого круга задач оптимизации была понята несколько позднее, этому посвящены одна моя работа в "Успехах" 1970 г. И её развитие в статье с М.М.Рубиновым.

сразу я применил эту метрику в 1970 для одной  из принципиальных задач теории меры и эргодческой теории (в теории убывающих последовтельностей измеримых разбиений). Там понадобилась дикая на первый взор беконечная итерация данной метрики ("башня мер"). Приблизительно в то же время Д.Орнштейн переоткрыл и ввел её в эргодичскую теорию по другому поводу (метрика Орнштейна).

История данной метрики и всего, что относится к ней -- красивый пример того, как прикладная (в данном случае -- транспортная) задачка инициирует введение только полезного чисто математического понятия.

Г) Связи с вариационным исчисленим и множителями  Лагранжа.

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

необходимо сказать, что в эстетическом отношении  теория Понтрягина уступала теории Л.В., Хотя первая по сути более сложна (лишь из-за изначальной бесконечномерности задач). О связи линейного и выпуклого программирования с хорошим управлением писалось много. Но по ряду обстоятельств эта связь не была доведена до довольно глубочайшего уровня.

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

Я занялся ими  в середине 60-х годов, когда стал обдумывать популярные тогда работы по инвариантным формулировкам механики (Арнольд, Годбийон, Марсден и др.). Увидев в неголономной механике -- падчерице классической механики -- нетривиальную оптимизационную задачку, я сообразил, как её поставить в современной форме. В те годы у нас был молодежный образовательный семинар в ЛОМИ -- по дифференциальной геометрии, теории представлений, группам Ли и всему остальному (Л.Д.Фаддеев, Б.Б.Венков, я и др.).

Как-то раз случаем  выяснилось, что и Л.Д. Тоже обдумывал неголономную механику, и мы решили совместно разобраться во всем полностью. Мы написали поначалу краткую, в ДАН, а позже и огромную статью об инвариантной форме лагранжевой и, в частности, неголономной механики. Эти работы обильно цитируются до сих пор, в них дан словарь соответствия меж определениями дифференциальной геометрии и понятиями классической механики. Сейчас эта тема стала престижной, она является замечательным промежуточным звеном меж классическим и неклассическим вариационным исчислением. В нем множители Лагранжа стают в еще одной новой форме - как переменные, отвечающие ограничениям и следствиям (скобкам Ли) всех порядков. Тут также нереально не вспомнить о разрешающих множителях Л.В.

Д) Линейные модели и  марковские процессы.

Поскольку Л.В. Много  занимался в 60-х гг. Экономическими моделями, не непременно связанными с  оптимизацией, нельзя хотя бы мельком  не упомянуть связи теории моделей  экономической динамики (Дж. Фон  Нейман, В.Леонтьев, Л.В. И др.) С динамическими  системами. Я хочу выделить тут лишь одну недостаточно изученную связь, а конкретно, что эти линейные экономические модели напрямую соединены с особым типом марковских действий, в которых необыкновенную роль играется понятие положительности в множестве состояний. Теоремы магистрального типа и марковские процессы принятия решений самым непосредственным образом соединены с данной проблематикой. Сюда же относятся теории многозначных отображений, трудности непрерывного выбора и т.Д.

По-видимому, эти  вопросы сейчас теряют свое прикладное значение, но непременно интересны с математической точки зрения, как и всякие теории многозначных и положительных отображений. Напомним, что еще до войны Л.В. Создал теорию полуупорядоченных пространств (К-пространств), которая скоро замкнулась в себе и закончила интересовать и его, и тех, кто не занимался ею конкретно. Но полупорядоченность в более широком смысле постоянно была предметом особенного энтузиазма математиков ленинградской и украинской школ.

Е) Глобализация линейного  программирования.

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

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

мощное впечатление  произвели в 80-х гг. Работы Хачияна  и Кармаркара, дававшие полиномиальную (в неком смысле) равномерную (по классу задач) оценку трудности способа  эллипсоидов для решения задач  линейного программирования. Тем не менее, этот способ ни в каком отношении не заменил разные варианты симплекс-способа. Оценки, о которых шла речь выше, дают линейную либо квадратичную оценку трудности только статистически. В целом неувязка о полиномиальности л.П. В подлинном смысле слова до сих пор (2001) еще не решена.

Ж) Линейное программирование и способы вычислений.

Еще одно направление, начатое Л.В. И не получившее подабающего  развития, -- линейное программирование как способ приближенного решения  задач математической физики (двусторонние оценки линейных функционалов от решений). Работа на эту тему (1962) содержала совсем плодотворную идею, и несколько работ на эту тему было выполнено в ЛГУ. Подход Л.В. Можно разглядывать также как альтернативный подход к некорректным задачкам. Эта задачка совсем актульна в математической геофизике и дискуссировалась Л.В. С Кейлис-Бороком.