Джордж Бернард Данциг
Даты жизни: 1914 — 2005
Сфера интересов: Линейное программирование, Исследование операций, Математическая статистика
Страна: США
Главный вклад: Создатель симплекс-метода, один из отцов-основателей линейного программирования и исследования операций.
2. Биографическая справка
Образование: Окончил Мэрилендский университет и Мичиганский университет. Защитил степень доктора философии в Калифорнийском университете в Беркли под руководством Ежи Неймана.
Академическая карьера: Во время Второй мировой войны работал в службе статистического контроля ВВС США, где столкнулся с невероятно сложными логистическими задачами снабжения армии. Эта работа привела его к формализации задач планирования. Позднее он стал профессором Стэнфордского университета, посвятив всю жизнь алгоритмам оптимизации.
Интересный факт: История из жизни Данцига стала легендой и легла в основу сюжета фильма «Умница Уилл Хантинг». Будучи студентом в Беркли, он опоздал на лекцию профессора Неймана и увидел на доске два статистических уравнения. Решив, что это домашнее задание, он списал их и сдал через несколько дней, извинившись за то, что "задание оказалось немного сложнее обычного". Оказалось, что он решил две нерешенные математические проблемы статистики, которые не мог решить сам профессор.
3. Основные достижения и труды
Ключевые работы:
- «Линейное программирование и его расширения» (Linear Programming and Extensions, 1963) — культовая монография.
- «Максимизация линейной функции переменных при линейных неравенствах» (1947).
Главные теоремы/формулы:
- Симплекс-метод: Итерационный вычислительный алгоритм для решения задач линейного программирования. Он находит глобальный оптимум целевой функции $c^T x$, последовательно перебирая вершины многогранника ограничений $Ax \le b$, двигаясь вдоль ребер в сторону наискорейшего возрастания (убывания) функции: $$c^T x \to \max, \quad Ax = b, \quad x \ge 0$$
- Принцип декомпозиции Данцига — Вулфа: Метод разбиения гигантских задач линейного программирования на более мелкие подзадачи, что позволило решать индустриальные задачи масштаба целых государств или корпораций.
4. Наследие и влияние
«Истинная оптимизация — это умение делать выбор в мире ограничений.»
Влияние на современность: Симплекс-метод Данцига входит в топ-10 важнейших алгоритмов XX века. Он совершил революцию в промышленности, экономике и логистике. Сегодня алгоритмы на основе симплекс-метода (или его модификаций) управляют расписанием полетов авиакомпаний, цепочками поставок Amazon, маршрутизацией пакетов в телекоммуникационных сетях, нефтепереработкой и распределением энергии в умных электросетях.
Награды: Национальная научная медаль США (1975), Теоретическая премия фон Неймана (1974), Медаль Гарольда Пендера.