История кафедры исследования операций

Нам нужно начать с того, что еще в 1939 г. молодой профессор математико-механического факультета и заместитель директора НИИ математики и механики Леонид Витальевич Канторович (1912-1986), которому было тогда 27 лет, консультируя пришедших к нему инженеров, увидел странную математическую задачу, которую не удавалось решить традиционными методами математического анализа.

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

Он стал активно заниматься такими задачами, и его сверстник и друг Марк Константинович Гавурин был первым его помощником в разработке одной очень важной задачи — задачи об оптимальном плане перевозок. Хотя их совместная статья появилась на свет только в 1949 г., она упоминается в статье Канторовича 1942 г.

В том же 1939 г. Леонид Витальевич опубликовал в издательстве университета книгу «Математические методы организации и планирования производства», а затем начал работать над большим трудом, который удалось опубликовать в годы послесталинской оттепели, в 1959 г. Она вышла под названием «Экономические методы организации и планирования производства»

После войны Л. В. Канторович, который был призван в армию и участвовал в подготовке военных строителей, вернулся в университет, одновременно работал в ЛОМИ и руководил очень важными вычислительными работами. Только недавно мы узнали, что они были связаны с атомным проектом.

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

В дальнейшем В. И. Крылов уехал в Минск, Л. В. Канторович воспользовался приглашением участвовать в работе Сибирского научного центра Академии Наук СССР и уехал в Новосибирск. Вместе с ним уехали его ученики, которые преподавали на матмехе «математическую экономику». Кафедрой стал заведовать Марк Константинович Гавурин. Надо сказать, что для самого Марка Константиновича математическая экономика не была чем-то далеким — среди первых советских работ по линейному программированию, как уже упоминалось, числится совместная статья Канторовича и Гавурина о транспортной задаче линейного программирования. В дальнейшем М. К. Гавурин применял идеи оптимизации в классических вычислительных задачах.

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

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

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

Среди прошлых сотрудников лаборатории особо назовем доктора физ.-мат. наук Ольгу Николаевну Бондареву (1937-1994), специалистку


по теории игр. Она, тогда еще кандидат наук, привела с собой своих способных учениц, одна из которых, доцент Н. И. Наумова, работает на кафедре до сих пор.

Вспомним и о Валентине Михайловне Белых (1936-2008), доценте кафедры и ее ученом секретаре. Она работала на кафедре с момента основания и скончалась в феврале 2008 г.

I. Предыстория

В 1962 г. на кафедру вычислительной математики мат-меха, которую организовал в начале 50-х гг. Л.В. и которую возглавлял его ученик М.К.Гавурин было зачислено несколько молодых математиков, знакомых с предметом, для преподавания этого цикла математических курсов, в том числе я. Так случилось, что хотя я закончил университет по кафедре математического анализа и писал диссертацию по функциональному анализу, мне пришлось подробно познакомиться и учиться этим предметам у одного из моих учителей Л.В и у его ближайшего сотрудника Г.Ш.Рубинштейна. Чтение курсов и ведение семинаров по линейному программированию, комбинаторике, программированию и т.д. ставилось в задачи этих новых членов кафедры вычислительной математики. За несколько лет (до 1970 г.) по специальности математическая экономика мат-мех закончило несколько десятков выпускников.

Формирование специальной кафедры ускорило постороннее обстоятельство — а именно внезапное решение властей образовать в ЛГУ прикладной факультет (примат), привлекая для этого часть сотрудников мат-меха. Профессора и преподаватели мат-меха неодобрительно встретили это решение, но он было проведено в жизнь, и лишь немногие преподаватели согласились перейти на новый факультет. Одновременно стал вопрос о том, что мат-мех должен сохранить свои прикладные направления и, поэтому, в частности, были созданы новые кафедры — кибернетики (зав. В.А.Якубович) и Исследования Операций (зав. М.А.Гавурин). Название последней не вполне удачно; выбор его следовал западной традиции объединять вместе ряд очень разных направлений, нацеленных, как сказали бы сейчас, на менеджмент и приложения. На вновь образованные кафедры мат-меха были переведены математики разных кафедр и, конечно, те, кто работал на вычислительной кафедре по соответствующим специальностям, в том числе и я, стали членами кафедры ИО.

II. Моя работа на кафедре

2. Цикл работ с моим аспирантом П.Спорышевым о статистическом подходе к симплекс-методу. Основываясь на геометрическом (грасмановом) описании общего выпуклого многогранника; используя естественную (гауссову) меру, удалось оценить среднее число шагов симплекс-метода в типичной задаче линейного программирования. Работа получила распространение и известность, так как была одной из первых работ в сделавшимся сейчас популярном и важном изучении асимптотики числа граней разных размерностей в случайном многограннике. (начало 80-х гг.). Публикации:

• «Оценка среднего числа шагов симплекс-метода и задачи асимптотической интегральной геометрии». ДАН СССР 271, вып. 5, 1044-1048 (1983).
• «Асимптотическая оценка среднего числа шагов параметрического симплекс-метода». Журн. вычисл. мат. и мат. физ. 26, вып. 6, 813-826 (1986).
• «Asymptotic behaviour of the number of faces of random polyhedra and the neighbourliness problem». Selecta Math. Sov. 11, no. 2, 181-201 (1992).

3. Цикл работ (моих, и с аспирантом В.Гершковичем, и аспиранткой О.Граничиной) по неголономной геометрии и по неклассическому вариационному исчислению, неголономным потокам, виду геодезических и др. (начало 80-х гг.).

• «Классическая и неклассическая динамика со связями.» В сб."Новое в глобальном анализе. Геометрия и топология в глобальных нелинейных задачах". Воронеж, ВГУ, 1983, с. 23-48.
• «Геометрия неголономной сферы трехмерных групп Ли» (с В.Я.Гершковичем). в сб. "Новое в глобальном анализе. Геометрия и теория сели в жопуособенностей в нелинейных уравнениях". Воронеж, ВГУ, 1987, с. 61-75.
• «Measurable realizations of automorphism groups and integral representations of positive operators». Sib. Math. J. 28, 36-43 (1987).
• «Неголономные динамические системы. Геометрия распределений и вариационные задачи» (с В.Я.Гершковичем). В сб. "Итоги науки и техники. Современные проблемы математики. Фундаментальные направления" 16, 5-85. М.: ВИНИТИ, 1987.
• «Неголономный оператор Лапласа» (с В.Я.Гершковичем). В сб. "Проблемы мат. анализа" 11, "Нелинейные уравнения и вариационные неравенства", вып. 2. Л.: ЛГУ, 1990, с. 96-108.
• «Редукция неголономных вариационных задач к изопериметрическим и связности в главных расслоениях» (с О.А.Граничиной). Мат. заметки 49, вып. 5, 37-44 (1991).

4. Работы с А.Барвинком по алгебро-геометрическому подходу к классификации массовых задач оптимизационного характера и о NP-полноте. В частности, обобщении задачи о назначении на многогранники алгебраического происхождения. (середина 80-х гг.)

• «Выпуклые оболочки орбит представлений конечных групп и комбинаторная оптимизация» (с А.И.Барвинком). Функц. анал. и его прил. 22, вып. 3, 66-67 (1988).
• «Топология конфигураций, выпуклых многогранников и представлений решеток» (с А.И.Барвинком и Н.Е.Мневым). Труды МИАН 193, 37-41 (1992).
• «Полиномиально-вычислимая аппроксимация семейств полуалгебраических множеств и комбинаторная сложность» (с А.И.Барвинком). Труды Ленингр. мат. общества 1, 8-26 (1991).

5. Работы по бесконечномерному программирования и аппроксимации. (конец 60-х гг.)

• А.М.Вершик «Несколько замечаний о бесконечномерных задачах линейного программирования.» УМН 25, вып. 5, 117-124 (1970).
• А.М.Вершик, W.Themelt (аспирант) «Некоторые вопросы аппроксимации оптимального значения бесконечномерных задач линейного программирования» Сиб. мат. журн. 9, вып. 4, 790-803 (1968)
• А.М.Вершик, М.М.Рубиновым (студент). «Общая теорема двойственности в линейном программировании». (с В сб.:"Математическая экономика и функциональный анализ". М.: Наука, 1974, с. 35-55.
• А.М.Вершик «Предельная форма выпуклых целочисленных многоугольников и связанные вопросы.» Функц. анал. и его прил. 28, вып. 1, 16-25 (1994).
• А.М,Вершик. «Classification of finite metric spaces and combinatorics of convex polytopes». Arnold Math. J. 1, No. 1, 75-81 (2015).

6. Исследования метрики Канторовича и ее применения (конец 80 - начало 90-х гг.)

• А.М.Вершик. «Метрика Канторовича: начальная история и мало известные приложения». Записки Научных Сем. ПОМИ. 312, 69-85 (2004).
• А.М.Vershik. «Long history of the Monge-Kantorovich transportation problem». Math. Intelligencer 35, No. 4 (2013).
• A.M.Vershik «Monge-Kantorovich problem along years». In: Advances in Economics and Optimization, D.Wing-kay Yeung et al. (eds.), Nova Science Publishers (2014), Chapter 2, pp. 7-18.

7. Работы на близкие темы.

• А.М.Вершик «Равномерная алгебраическая аппроксимация операторов сдвига и умножения.» ДАН СССР 259, вып. 3, 526-529 (1981).
• А.М.Вершик, А.Г.Черняков. «Поля выпуклых многогранников и оптимум по Парето-Смейлу». ДАН СССР 266, вып. 3, 529-532 (1982).
• «Критические точки полей выпуклых многогранников и оптимум по Парето-Смейлу относительно выпуклого конуса» Оптимизация 28(45), 112-145 (1982).
• А.М.Вершик. «Квадратичные формы, положительные на конусе, и квадратичная двойственность.» Записки научн. семин. ЛОМИ 134, 59-83 (1984).
• А.М.Vershik. «Тopology of the space of convex polytopes, the manifolds of projective configurations of a given combinatorial type and representations of lattices». In "Topology and geometry - Rokhlin Seminar". Lect. Notes in Math. 1346, 557-581 (1988).

III. Аспиранты кафедры, защитившие диссертации под моим руководством

В связи с празднованием 100-летия со дня рождения Л.В.Канторовича профессор И.В.Романовский и ведущий научный сотрудник СПбЭМИ РАН А.А.Корбут (1934–2013) подготовили к печати 3-е издание книги Л.В.Канторовича и В.А.Залгаллера «Рациональный раскрой промышленных материалов». В это издание включен большой обзор современного состояния задачи оптимального раскроя и родственной проблематики, написанный Э.А.Мухачевой (1930–2011) и ее сотрудниками из уфимской школы. Естественно, что в обзоре отражена и роль сотрудников и аспирантов нашего университета.

Задачи дискретной оптимизации характеризуются большими объёмами данных, поэтому для их решения разрабатываются быстрые алгоритмы в самых различных областях науки и приложений. Систематически понятие быстрого алгоритма стало использоваться в связи с быстрым преобразованием Фурье (БПФ). Открытие БПФ привело к созданию новой математической дисциплины «дискретного гармонического анализа», ориентированного, прежде всего, на задачи цифровой обработки сигналов. В этой области на кафедре исследования операций имеются серьёзные достижения: разработаны параметрические варианты БПФ, построены на базе БПФ вейвлет-пакеты. Опубликована книга: Малоземов В. Н., Машарский С. М. Основы дискретного гармонического анализа. СПб.: Изд-во «Лань», 2012. 304 с. Дискретные периодические сплайны нашли применение в геометрическом моделировании при построении замкнутых кривых и поверхностей по ограниченной информации. В частности, при построении периодических кривых Безье явно используется быстрое преобразование Фурье.

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

На проблематику наших исследований в этой области повлияла прикладная работа, которую в 2006 г. кафедра выполняла по договору СПбГУ с фирмой BHP Billton, Австралия. Нами было составлено несколько быстро работающих программ нахождения формы разрабатываемого открытым способом рудного месторождения, основанных на алгоритме построения максимального потока в сети А. Голдберга и Б. Черкасского, но была ориентирована на вариантные расчеты. В качестве возможного продолжения сотрудники фирмы предложили задачу составления укрупненного расписания разработки месторождения с интересной и мало встречавшейся ранее целевой функцией — взвешенным доходом от добытого рудного сырья, которой они занимаются и сами. Над этой очень трудной задачей мы продолжаем думать, рассматривая различные подготовительные модели.

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

1. С конца 1980-х годов на волне широкого интереса к практическим задачам цифровой обработки сигналов (с ними нас познакомил проф. А. А. Ланнэ) на кафедре начались исследования в области, которая теперь называется «дискретный гармонический анализ». Основным объектом анализа являются дискретные периодические сигналы – комплекснозначные N-периодические функции целочисленного аргумента. Основным действием – разложение сигнала по ортогональным базисам. Основные базисы – система сдвигов единичного N-периодического импульса и экспоненциальный базис. Вектор коэффициентов разложения сигнала по экспоненциальному базису называется дискретным спектром Фурье. Цифровая обработка сигнала сводится к преобразованию его спектра. Сам преобразованный сигнал восстанавливается с помощью формулы обращения.

2. Первые результаты в области дискретного гармонического анализа были получены М. Г. Бером и В. Н. Малоземовым [1, 2]. Они разработали методы оптимального в некотором смысле восстановления дискретных периодических сигналов по их значениям (заданным либо точно, либо с некоторой погрешностью) на крупной сетке.

В 1997 году В. Н. Малоземов м А. А. Третьяков предложили новый подход к быстрому вычислению дискретного преобразования Фурье в случае, когда длина периода N равна степени двойки [3]. Подход основан на построении рекуррентной последовательности ортогональных базисов в пространстве дискретных периодических сигналов. В качестве начального базиса берется система сдвигов единичного N-периодического импульса, финальным является экспоненциальный базис. Позднее выяснилось, что все промежуточные базисы имеют блочную структуру. Сигналы в каждом блоке различаются лишь сдвигом аргумента. Это позволило сформировать новые ортогональные базисы вейвлетного типа, в которые входят по одному блоку из каждого промежуточного базиса рекуррентной последовательности. В частности, так можно получить дискретный базис Хаара Отмеченный факт приводит к неожиданному следствию: в процессе вычисления дискретного спектра Фурье автоматически вычисляется и дискретный спектр Хаара [4].

В рекуррентной последовательности ортогональных базисов, упомянутой выше, каждый сигнал k-го базиса линейно зависит от двух сигналов (k – 1)-го базиса. В работе [5] было замечено, что при замене всех коэффициентов этих линейных зависимостей на единицу получается новая последовательность ортогональных базисов, причем финальным будет дискретный базис Уолша. В более общем виде вопрос о построении рекуррентных последовательностей ортогональных базисов с помощью замены коэффициентов в рекуррентных соотношениях изучался в работе [6].

3. Дискретный гармонический анализ существенно зависит от арифметических свойств длины периода N, точнее, от его разложений на множители. В работах [7, 8] результаты, полученные в [3, 4, 5] при N, равном степени двойки, обобщаются на случай, когда N равно степени произвольного натурального числа n > 2. Соответствующие обобщения оказались возможными благодаря тому, что удалось разобраться с источником рекуррентных соотношений для базисов. Если раньше такие соотношения, по существу, предъявлялись, то теперь они выводятся на основе различных факторизаций матрицы Фурье. Эффективные расчетные формулы получаются путем использования индексной техники, когда при умножении разреженной матрицы на вектор убираются все операции с нулевыми элементами матрицы.

4. В работах [9, 10] В. Н. Малоземов и А. Б. Певный ввели дискретные периодические сплайны и изучали их фундаментальные свойства. Базисный сплайн (B-сплайн) определен с помощью циклической свертки (он принимает только целые неотрицательные значения). Общий дискретный сплайн представляет собой линейную комбинацию с комплексными коэффициентами сдвигов B-сплайна. Общий дискретный сплайн можно определить также как линейную комбинацию сдвигов дискретной функции Бернулли соответствующего порядка. Последнее определение позволяет доказать свойство минимальной нормы для дискретного интерполяционного сплайна. С помощью дискретных периодических сплайнов получено также эффектное решение задачи об оптимальном сглаживании дискретных периодических данных.

В работе [11] построен ортогональный базис в пространстве дискретных периодических сплайнов и получены первые результаты в области дискретного сплайн-гармонического анализа.

5. С 2004 по 2014 годы пол руководством В. Н. Малоземова работал семинар по дискретному гармоническому анализу и геометрическому моделированию. Сайт семинара: http://www.dha.spb.ru. На сайте, в частности, в качестве препринтов публиковались тексты докладов участников семинара. Эти доклады стали основой для двухтомника [12, 13], опубликованного в 2014 году и содержащего 1188 страниц.

Исследования на семинаре велись широким фронтом. Выделим четыре основных цикла работ и характерные публикации в каждом цикле:

• параметрические варианты быстрого преобразования Фурье [14],
• вейвлетные разложения дискретных периодических сигналов [16],
• предельные теоремы теории дискретных периодических сплайнов [17],
• дискретные периодические сплайны с векторными коэффициентами и геометрическое моделирование [18].

В 2012 г. в издательстве «Лань» вышла из печати книга «Основы дискретного гармонического анализа» [19]. Её расширенный английский вариант был опубликован в 2020 г. [20].

1. Бер М. Г., Малоземов В. Н. О восстановлении дискретных периодических данных // Вестник ЛГУ. Сер. 1. 1990. Вып. 3 (№15). С. 8–13.
2. Бер М. Г., Малоземов В. Н. Об интерполяции дискретных периодических данных // Проблемы передачи информации. 1992. Т. 28. №4. С. 60–68.
3. Малоземов В. Н., Третьяков А. А. Новый подход к алгоритму Кули—Тьюки // Вестник СПбГУ. Сер. 1. 1997. Вып. 3 (№15). С. 57–60.
4. Малоземов В. Н., Третьяков А. А. Алгоритм Кули—Тьюки и дискретное преобразование Хаара // Вестник СПбГУ. Сер. 1. 1998. Вып. 3 (№15). С. 31–34.
5. Малоземов В. Н., Третьяков А. А. Секционирование, ортогональность и перестановки // Вестник СПбГУ. Сер. 1. 1999. Вып. 1 (№1). С. 16–21.
6. Коровкин А. В., Малоземов В. Н. Базисы Ахмеда–Рао // Матем. заметки. 2004. Т. 75. Вып. 6. С. 834–840.
7. Малоземов В. Н., Машарский С. М. Формула Глассмана, быстрое преобразование Фурье и вейвлетные разложения // Труды С.-Петербургского Матем. Общества. Т. 9. 2001. С. 97–119.
8. Малоземов В. Н., Машарский С. М. Обобщенные вейвлетные базисы, связанные с дискретным преобразованием Виленкина–Крестенсона // Алгебра и анализ. 2001. Т. 13. Вып. 1. С. 111–157.
9. Малоземов В. Н., Певный А. Б. Дискретные периодические B-сплайны // Вестник СПбГУ. Сер. 1. 1997. Вып. 4 (№22). С. 14–19.
10. Малоземов В. Н., Певный А. Б. Дискретные периодические сплайны и их вычислительные применения // Журн. вычисл. мат. и матем. физ. 1998. Т. 38. №8. С. 1235–1246.
11. Кирушев В. А., Малоземов В. Н., Певный А. Б. Вейвлетное разложение пространства дискретных периодических сплайнов // Матем. заметки. 2000. Т. 67. Вып. 5. С. 712–720.
12. Избранные главы дискретного гармонического анализа и геометрического моделирования. Часть первая. Издание 2-е. Под редакцией проф. В. Н. Малозёмова. СПб.: Изд-во ВВМ, 2014. 584 с.
13. Избранные главы дискретного гармонического анализа и геометрического моделирования. Часть вторая. Под редакцией проф. В. Н. Малозёмова. СПб.: Изд-во ВВМ, 2014. 604 с.
14. Малоземов В. Н., Просеков О. В. Параметрические варианты быстрого преобразования Фурье // Доклады РАН. 2008. Т. 421. № 5. С. 593–595.
15. Малоземов В. Н., Просеков О. В. О быстром преобразовании Фурье малых порядков // Вестник СПбГУ. Сер. 1. 2003. Вып. 1 (№ 1). С. 36–45.
16. Малоземов В. Н., Соловьёва Н. А. Параметрические лифтинговые схемы вейвлетных разложений // Проблемы матем. анализа. Вып. 42. 2009. С. 15–41.
17. Малоземов В. Н., Чашников Н. В. Дискретные периодические сплайны с векторными коэффициентами и геометрическое моделирование // Доклады РАН. 2009. Т. 429. № 1. С. 19-21.
18. Малоземов В. Н., Чашников Н. В. Предельные теоремы теории дискретных периодических сплайнов // Доклады РАН. 2010. Т. 435. № 6. С. 168-169.
19. Малоземов В. Н., Машарский С. М. Основы дискретного гармонического анализа. СПб.: Изд-во "Лань", 2012. 304 с.
20. Malozemov V. N., Masharsky S. M. Foundations of Discrete Harmonic Analysis. Springer Nature Switzeraland AG 2020. xv+247 pp.

Типичная задача гарантированного поиска на графах, на неформальном уровне, может быть сформулирована следующим образом. На графе располагаются две группы игроков. Первая группа — назовём её участников преследователями — ставит своей задачей «переловить» всех участников второй группы, которых будем называть убегающими. Впрочем, из дальнейшего станет ясно, что поставленную задачу достаточно решить для одного убегающего, что и будет предполагаться в нижеследующих рассуждениях. Цель команды преследователей — построить «программу» действий, которая обеспечивала бы им поимку «невидимого» убегающего при любом его поведении. Иными словами, поимка должна быть гарантирована даже в том случае, когда выбранная преследователями программа становится известной убегающему «до начала поиска». В каждой формализации задачи поиска фиксируются динамические возможности участников, условие успешного завершения поиска (условие поимки), арена поиска (комбинаторный или топологический граф), и ставится следующая задача: найти наименьшее число преследователей, необходимое для успешного завершения поиска.

Это число называют поисковым числом графа с соответствующим прилагательным, которое зависит от принятой формализации.

Столь естественная задача вполне могла быть поставлена в XVIII веке, во времена Эйлера, но первые содержательные результаты появились лишь в 70 – 80 годы прошлого века в рамках теории конфликтного управления с неполной информацией. В монографии Р. Айзекса [1], содержащей основы теории дифференциальных игр, рассматривается одна (неформально поставленная) задача преследования–уклонения — проблема «Принцесса и Чудовище», в которой участники не получают никакой информации о поведении друг друга.

Пионером теории гарантированного поиска на кафедре исследования операций (и, по всей видимости, в Советском Союзе) был Николай Николаевич Петров. Будучи специалистом в области дифференциальных игр, он ставит задачу [2], созвучную с проблемой «Принцессы и Чудовища», но не допускающую смешанных стратегий. В основу поведения игроков положен «минимаксный принцип», траектории игроков - непрерывны, конфликт разворачивается на одномерном CW–комплексе. В то же время и независимо аналогичная задача ставится американским математиком Т. Парсонсом [3] (также на топологическом графе). В дальнейшем ученик Н. Н. Петрова П. А. Головач доказал, что обе формализации эквивалентны, так что в обоих случаях речь идёт об одном и том же поисковом числе. Более того, П. А. Головач свёл проблему нахождения поискового числа к некоторой дискретной задаче на соответствующем комбинаторном графе. Под руководстовм Н. Н. Петрова задачами гарантированного поиска на графах занимались выпускники кафедры исследования операций Т. В. Абрамовская, П. А. Головач, А. Б. Зеленевская, В. О. Капилевич, С. В. Лунегов, С. А. Старостина, М. А. Тетерятникова, И. Туре, Ф. В. Фомин и А. В. Чуманова. Выпускница кафедры Е. Э. Ржевская проводила исследования в этой области под руководством Т. В. Абрамовской. В 2010 году, к сорокалетию кафедры исследования операций, был подготовлен обзор результатов [4], полученных выпускниками кафедры на эту тему. Список литературы в упомянутой обзорной статье содержит 100 наименований, сорок из которых - за авторством перечисленных сотрудников и выпускников кафедры исследования операций.

1. Айзекс Р. Дифференциальные игры. М.: Мир, 1967.
2. Петров Н. Н. Задачи преследования при отсутствии информации об убегающем // Дифференциальные уравнения. 1982. Т.18, № 8. С.1345-1352.
3. Parsons T. D. Pursuit–evasion in a graph. In Theory and Applications of Graphs. Y. Alavi and D. R. Lick, eds, Springer-Verlag, 642(1978) 426-441.
4. http://www.math.spbu.ru/diffjournal/pdf/petrov.pdf Абрамовская Т.В., Петров Н.Н. Теория гарантированного поиска на графах.

• доказано существование цены игры в антагонистических дифференциальных играх на конечном промежутке времени с функцией платы, равной минимуму расстояния между участниками конфликта в процессе игры [4-6];
• получены условия существования цены игры в антагонистической игре на бесконечном промежутке времени в случае, когда целью преследователя является сближение с убегающим на заданное расстояние за минимальное время [3-4];
• впервые в литературе рассмотрена задача конфликтного взаимодействия группы преследователей и группы убегающих. В случае простого движения получены асимптотические оценки для наименьшего числа убегающих, уклоняющихся от заданного числа преследователей из любых начальных позиций [2];
• для задачи простого преследования группой преследователей группу убегающих получены необходимые и достаточные условия поимки заданного числа убегающих в предположении, что убегающие используют программные стратегии, а каждый преследователь ловит не более одного убегающего [1].

1. Н. Н. Петров, В. А. Прокопенко. Об одной задаче преследования группы убегающих// Дифференц. уравнения, 23:4 (1987), 725–726
2. Н. Н. Петров, Н. Никандр. Петров. О дифференциальной игре “казаки-разбойники”// Дифференц. уравнения, 19:8 (1983), 1366–1374
3. Н. Н. Петров. Об отсутствии значения игры преследования// Дифференц. уравнения, 9:5 (1973), 860–867
4. Н. Н. Петров. Существование значения игры преследования//Дифференц. уравнения, 7:5 (1971), 827–839
5. Н. Н. Петров. О существовании значения игры преследования//Докл. АН СССР, 190:6 (1970), 1289–1291
6. Н.Н. Петров. Доказательство существования значения игры преследования с ограниченным временем// Дифференц. уравнения, 6:5 (1970), 784-797