Карта → событие
Данциг: симплекс-метод
Слово, которое всех путает
Начнём с названия, потому что оно вводит в заблуждение всех и всегда.
«Линейное программирование» не имеет отношения к программированию машин. В американском военном обиходе 1940-х program означало план, расписание, программу снабжения — документ, расписывающий, кто, что, куда и когда везёт. Задача составления такого плана называлась programming, и когда выяснилось, что ограничения в ней линейны, приём назвали линейным программированием. Машин в этом слове нет и не было.
Джордж Данциг (1914–2005) работал в Пентагоне, в проекте ВВС США со звучным именем SCOOP — «научное вычисление оптимальных программ». Задача была ровно такая: снабжение военно-воздушных сил, где тысячи ограничений и надо выбрать наилучший из допустимых планов.
Многогранник
Формально задача выглядит невинно: максимизировать линейную функцию при линейных неравенствах-ограничениях.
Геометрически множество допустимых планов — выпуклый многогранник в пространстве очень большой размерности, а линейная функция достигает максимума обязательно в вершине. Значит, ответ где-то среди вершин, и задача, казалось бы, конечна.
Беда в том, что вершин у такого многогранника астрономически много: при сотне ограничений и сотне переменных их больше, чем атомов в наблюдаемой Вселенной. Перебор исключён.
Симплекс-метод (лето 1947 года) устроен так: начать с любой вершины и идти по рёбрам, каждый раз переходя в соседнюю вершину, где значение функции больше. Когда улучшающего ребра нет — вы в оптимуме, и это доказано выпуклостью, а не проверено перебором.
Работает он неприлично хорошо: на реальных задачах число шагов оказывается порядка числа ограничений, а не числа вершин.
Парадокс, который не разрешён до сих пор
Через двадцать пять лет Кли и Минти (1972) построили пример — деформированный куб, — на котором симплекс-метод честно обходит все $2^{n}$ вершин. То есть в худшем случае метод экспоненциален.
Получилась странность, которой в математике немного: алгоритм с плохой теоретической оценкой, десятилетиями безотказно работающий на практике. Объяснение появилось только в 2001 году — сглаженный анализ Спилмана и Тенга, показавший, что дурные примеры вроде куба Кли и Минти исчезающе редки: они существуют, но малейшее случайное возмущение задачи их разрушает.
Здесь стоит отметить, что для линии это поворот. Раньше вопрос был «сколько стоит вычисление». Здесь впервые спрашивают иначе: сколько оно стоит в худшем случае и сколько — обычно, и выясняется, что это совершенно разные вопросы с разными ответами.
Ленинград, восемью годами раньше
Ту же задачу и по существу тот же класс методов нашёл в 1939 году Канторович, разбираясь с раскроем фанеры на ленинградском тресте. Его работа осталась неизвестной на Западе до конца 1950-х — язык, война, закрытость.
Нобелевскую премию по экономике 1975 года получили КанторовичЛеонид Витальевич КанторовичИз фанерного треста пришла задача о раскрое — и из неё вышло линейное программирование, теория оптимального транспорта и единственная советская Нобелевская премия по экономике. и Купманс. Данцига в списке не было, и многие считают это несправедливостью: метод, которым мир решает задачи планирования, придумал он.
И ещё одна история про него
Она слишком хороша, чтобы её опустить, и, в отличие от большинства подобных, правдива.
В 1939 году аспирант Данциг опоздал на занятие к Ежи Нейману в Беркли и списал с доски две задачи, приняв их за домашнее задание. Решил обе — с трудом, но решил — и через несколько дней принёс. Это были две нерешённые проблемы математической статистики; Нейман просто разбирал их на доске как открытые. Одна из них стала диссертацией Данцига.
Из этого случая потом выросла городская легенда, кочующая по мотивационным брошюрам в неузнаваемом виде. Оригинал лучше пересказов: человек решил открытую проблему потому, что не знал, что она открытая.
Следующая точка: Сиэтл — где посчитали конструкцию, для которой нет уравнения.