Однако линейное программирование имеет серьезные связи с дискретной математикой и комбинаторикой. Более точно, некоторые задачи линейного программирования являются линеаризацией комбинаторных задач. Примеры: задача о назначениях и теорема Биркгофа-фон Неймана, теорема Форда-Фулкерсона. Эта сторона теории не была замечена у нас сразу и пришла к нам из западной литературы позже. Основную задачу теории матричных игр с нулевой суммой (а именно, теорему о минимаксе) блестяще связал с линейным программированием еще фон Нейман, см. воспоминания Данцига, цитированные в статье А.М.Вершика, А.Н.Колмогорова и Я.Г.Синая "Джон фон Нейман" (Фон Нейман. "Избранные труды по функциональному анализу, т.1" М. "Наука",1987), где Данциг пишет о поразившем его разговоре с фон Нейманом, в котором тот за час изложил связь теории двойственности и теорем о матричных играх и наметил метод решения этих задач.
Эта связь была освоена не сразу, -- я помню, что ленинградские специалисты по теории игр первое время не принимали в расчет, что решение матричной игры с нулевой суммой есть задача линейного программирования, и, несомненно красивый, метод решения игр, принадлежащий Дж. Робинсон, считался чуть ли не единственным численным методом нахождения значения игры. В итоговом доказательстве теоремы фон Неймана о минимаксе (первое доказательство было топологическим и использовало теорему Брауэа) фактически содержалась теория двойственности. Позже эквивалентость игровой задачи и линейного программирования широко использовалась.
Акценты на связь с дискретной математикой и комбинаторикой превалируют в большинстве зарубежных работ первых лет по линейному программированию, в то время как в отечественных работах в первое время более подчеркивалась связь с функциональным и выпуклым анализом и развивались численные методы.
В связи с линейным и выпуклым программированием на первый план из комбинаторных теорий выступает комбинаторная геометрия выпуклых и целочисленных многогранников и комбинаторика симметрической группы. Важными работами первого периода по комбинаторике многогранников была книга Грюнбаума, и статьи Кли и др, а в комбинаторике - работы Дж. Рота и Р.Стенли. Одновременно возникли близкие темы в теории особенностей (многогранники Ньютона), алгебраической геометрии (торические многообразия и целочисленные многогранники) и др. А позже открылись обширные связи с симметрической группой, комбинаторной теорией диаграмм Юнга - одной из основных тем "новой комбинаторики", - а также посетами и матроидами. Интересно, что почти одновременно (и независимо) к ряду близких задач комбинаторики пришел И.М.Гельфанд (матроиды, клетки Шуберта, вторичные многогранники), назвавший комбинаторику математикой ХХI века. Сейчас новые комбинаторные задачи являются ключевыми в разнообразных математических проблемах.
Мой интерес к к линейному программированию в первые годы возник совершенно независимо от моих математических пристрастий тех лет и, в частности, не только потому, что я учился у Л.В. функциональному анализу и слушал его первые захватывающие рассказы о линейном программировании и его применении в экономике. В тот момент (1956-58 гг). это был скорее практический, чем теоретический интерес.
Дело в том, что отказавшись после окончания университета по некоторым причинам от аспирантуры, я работал в военно-морском ВЦ, и заинтересовался задачей многомерного наилучшего приближения как прикладник. Одной из моих задач в этом ВЦ было представление таблиц стрельбы в ЭВМ, и я предложил аппроксимировать их вместо того, чтобы хранить в памяти ЭВМ. Я сформулировал некоторое обобщение задачи о наилучшем приближении, а именно, о кусочно полиномиальном наилучшем приближении (ни о каких сплайнах тогда нам известно не было) для функций нескольких переменных. Позже, когда я уже стал работать в университете, в 60-х гг. этой задачей занимались мои первые дипломанты. Еще позже была написана подробная статья об этом.
Постепенно мой интерес к задаче о наилучшей аппроксимации превратился в интерес к самому методу, позволяющему ее решить, - одним из них и был метод линейного программирования. Г.П.Акилов посоветовал поговорить по этому поводу с Г.Ш.Рубинштейном. Во время наших бесед Г.Ш. дополнял доклады Л.В. рассказами о близких работах других математиков, - несомненно, Г.Ш. был тогда одним из лучших знатоков линейного программирования и всего этого круга идей Л.В. -- о работах американцев (симплекс-методе) мы узнали несколько позже. Основным для нас был "метод разрешающих множителей". Он укладывался как частный случай в то, что у нас называлось симплекс-методом, но наше понимание было шире американского, -- классический симплекс-метод Данцига есть также частный случай этого, более общего, класса методов. К сожалению, как часто бывает, русская терминология не была достаточно продумана и зафиксирована и слова "симплекс-метод" допускают массу различных толкований.
Школа численных методов линейного программирования в СССР была исключительно сильной, и в этом безусловная заслуга Л.В. и двух его основных помощников первой поколения -- В.А.Залгаллера и Г.Ш.Рубинштейна, а позже И.В.Романовского и его группы, В.Л.Булавского, в Москве -- Д.Б.Юдина и Е.Г.Гольштейна и др. В последующем с развитием вычислительной и программистской техники численное решение любых задач разумной размерности стало доступным.
В) Метрика Канторовича.
Однажды весной 1957 г. Г.Ш.Рубинштейн рассказал мне, что он наконец понял, как можно использовать теорему Л.В. о задаче Монжа (теперь ее называют задачей Монжа - Канторовича), доказанную им в заметке ДАН 1942 г. - а именно, как метрику Канторовича, т.е. оптимальное значение целевого функционала в транспортной задаче, использовать для введения нормы в пространстве мер и как критерий Л.В. становится теоремой двойственности с пространством функций Липшица. По сути дела, это было важным методическим замечанием, так как сама метрика уже была описана в заметке Л.В. Но именно эта работа Л.В. и Г.Ш., появившаяся в Вестнике ЛГУ в 1958 г., в выпуске, посвященном Г.М.Фихтенгольцу, содержала общую теорию знаменитой теперь метрики, назывемой иногда метрикой Канторовича-Рубинштейна, или транспортной.
Кстати, в том же номере была опубликована и моя первая работа совместно с моим первым руководителем Г.П.Акиловым, посвященная новому определению распределений Шварца, но в которой также в качестве одного из примеров рассматривалась эта, только что появившаяся, метрика. В той же работе Л.В. и Г.Ш.-- это обычно вспоминается реже, - был дан критерий оптимальности первозок в двойственных терминах -- функций Липшица или потенциалов.
С тех пор я превратился в постоянного пропагандиста этой замечательной метрики, и убедил очень многих математиков наших и зарубежных, в приоритете Л.В. и в важности этой работы. Она переоткрывалась огромное число раз и потому имеет очень много названий (метрика Вассерштейна, Орнштейна и т.д., не знавших о работе Л.В.) а сам метод ее введения известен как спаривание (coupling), как метода фиксированных маргинальных мер и т.д. Ее применения обширны и в самой математике, и в статфизике, и в математической статистике, в эргодической теории и в других приложениях. О ней написаны книги, которые далеко не исчерпывают всех ее сторон. Весьма близки к ней метрика Леви - Прохорова - Скорохода, популярная в теории вероятностей. Возможность дальнейшего обобщения этой метрики для широкого круга задач оптимизации была понята несколько позже, этому посвящены одна моя работа в "Успехах" 1970 г. и ее развитие в статье с М.М.Рубиновым.
Одновременно я применил эту метрику в 1970 для одной из важных задач теории меры и эргодческой теории (в теории убывающих последовтельностей измеримых разбиений). Там понадобилась дикая на первый взгляд беконечная итерация этой метрики ("башня мер"). Приблизительно в то же время Д.Орнштейн переоткрыл и ввел ее в эргодичскую теорию по другому поводу (метрика Орнштейна).
История этой метрики и всего, что относится к ней -- прекрасный пример того, как прикладная (в данном случае -- транспортная) задача инициирует введение исключительно полезного чисто математического понятия.