Джордж Данциг - Википедия - George Dantzig

Джордж Данциг
Джордж Б. Данциг на церемонии вручения Национальной медали науки, 1976.jpg
Джеральд Форд награждение Джорджа Б. Данцига Национальной медалью науки, 1976
Родившийся
Джордж Бернард Данциг

(1914-11-08)8 ноября 1914 г.
Умер13 мая 2005 г.(2005-05-13) (в возрасте 90 лет)
ГражданствоАмериканец
Альма-матерУниверситет Мэриленда (BS )
университет Мичигана (РС )
Калифорнийский университет в Беркли (кандидат наук )
ИзвестенЛинейное программирование
Симплексный алгоритм
Принцип разложения Данцига-Вульфа
Обобщенное линейное программирование
Обобщенная верхняя граница
Теорема о максимальном потоке и минимальном разрезе сетей
Квадратичное программирование
Дополнительные алгоритмы поворота
Проблема линейной дополнительности
Стохастическое программирование
НаградыПремия Джона фон Неймана по теории (1975)
Национальная медаль науки в области математических, статистических и вычислительных наук (1975)
Приз Харви (1985)
Премия Гарольда Пендера (1995)
Научная карьера
ПоляМатематика
Исследование операций
Промышленная инженерия
Информатика
Экономика
Статистика
УчрежденияУправление статистического контроля ВВС США
RAND Corporation
Калифорнийский университет в Беркли
Стэндфордский Университет
ДокторантЕжи Нейман
Докторанты
Роберт Фурер
Альфредо Ноэль Юсем
Эллис Л. Джонсон
Томас Маньянти
Роджер Джей Би Мокрый
Yinyu Ye
ВлиянияВасилий Леонтьев
Джон фон Нейман
Маршал К. Вуд
Под влияниемКеннет Дж. Эрроу
Мартин Бил
Роберт Дорфман
Леонид Гурвич
Тьяллинг К. Купманс
Элвин Рот
Томас Л. Саати
Пол Самуэльсон
Гарри М. Марковиц
Филип Вулф

Джордж Бернард Данциг (/ˈdæптsɪɡ/; 8 ноября 1914-13 мая 2005) был американцем ученый-математик кто внес вклад в промышленная инженерия, исследование операций, Информатика, экономика, и статистика.

Данциг известен разработкой симплексный алгоритм,[1] алгоритм решения линейное программирование задач, а также за другие его работы с линейным программированием. В статистика, Данциг решил два открытые проблемы в статистическая теория, которое он принял за домашнее задание после того, как опоздал на лекцию Ежи Нейман.[2]

На момент смерти Данциг был почетным профессором транспортных наук и профессором операционных исследований и компьютерных наук. Стэндфордский Университет.

ранняя жизнь и образование

Рожден в Портланд, штат Орегон, Джордж Бернар Данциг был назван в честь Джордж Бернард Шоу, ирландский писатель.[3][4] Он родился в Еврейский родители; его отец, Тобиас Данциг, был математиком и лингвистом, а его мать, Аня Данциг (урожденная Ориссон), была лингвистом Французско-еврейский источник. Родители Данцига познакомились во время учебы в Парижский университет, где Тобиас изучал математику под Анри Пуанкаре, в честь которого был назван брат Данцига.[4] Семья Данцигов иммигрировала в Соединенные Штаты, где они поселились в Портленде, штат Орегон.

В начале 1920-х годов семья Данцигов переехала из Балтимор к Вашингтон, округ Колумбия. Его мать стала лингвистом в Библиотека Конгресса, а его отец стал репетитором математики в Университет Мэриленда, Колледж-Парк. Данциг учился в неполной средней школе Пауэлла и Центральная средняя школа; один из его друзей был Авраам Зайденберг, который также стал математиком.[4] К тому времени, когда он пошел в среднюю школу, он уже был очарован геометрией, и этот интерес в дальнейшем подпитывал его отец, ставя перед ним сложные задачи, особенно проективная геометрия.[2][4]

Джордж Данциг получил степень бакалавра наук. из Университет Мэриленда в 1936 г. по математике и физике, что является частью Колледж компьютерных, математических и естественных наук Мэрилендского университета. Он получил степень магистра математики в университет Мичигана в 1938 году. После двухлетнего периода в Бюро статистики труда он поступил на докторскую программу по математике в Калифорнийский университет в Беркли, где изучал статистику под Ежи Нейман.

Карьера

Со вспышкой Вторая Мировая Война Данциг взял отпуск по программе докторантуры в Беркли, чтобы поработать штатским сотрудником ВВС армии США. С 1941 по 1946 год - начальник отдела боевого анализа Главного статистического управления ВВС сухопутных войск.[2] В 1946 году он вернулся в Беркли, чтобы выполнить требования своей программы и получил диплом. Кандидат наук. этот год.[3] Хотя у него было предложение факультета из Беркли, он вернулся в ВВС в качестве математического советника контролер.[4]

В 1952 году Данциг присоединился к математическому отделению Covid Corporation. К 1960 году он стал профессором в Департамент промышленной инженерии в Калифорнийском университете в Беркли, где он основал и руководил Исследовательским центром операций. В 1966 году он поступил на Стэнфордский факультет в качестве профессора исследования операций и компьютерных наук. Год спустя Программа исследований операций стала полноценным отделом. В 1973 году он основал здесь Лабораторию оптимизации систем (СОЛ). В том же году в творческом отпуске он руководил методической группой в Международный институт прикладного системного анализа (IIASA) в Лаксенбурге, Австрия. Позже он стал профессором транспортных наук К. А. Крили в Стэндфордский Университет.[3]

Он был членом Национальная Академия Наук, то Национальная инженерная академия, а Американская академия искусств и наук. Данциг был удостоен многих наград, в том числе первой Премия Джона фон Неймана по теории в 1974 г. Национальная медаль науки в 1975 г.[5] ан почетный доктор от Университет Мэриленда, Колледж-Парк в 1976 г. Общество математического программирования почтил Данциг, создав Премия Джорджа Б. Данцига, вручается каждые три года, начиная с 1982 г., одному или двум людям, оказавшим значительное влияние в области математического программирования. Был избран в класс 2002 г. Стипендиаты из Институт исследований операций и управленческих наук.[6]

Исследование

Далее Фройнд писал, что «своими исследованиями в области математической теории, вычислений, экономического анализа и приложений к промышленным проблемам Данциг внес больше, чем любой другой исследователь, в замечательное развитие линейного программирования».[7]

Работа Данцига позволяет авиационной отрасли, например, планировать составы экипажей и распределять флот. На основе его рабочих инструментов разработаны инструменты, «которые судоходные компании используют, чтобы определить, сколько самолетов им нужно и где их грузовики должны быть развернуты. В нефтяной промышленности давно используется линейное программирование при планировании нефтепереработки, поскольку оно определяет, сколько сырого продукта должно становятся разными сортами бензина и сколько следует использовать для побочных продуктов на основе нефти. Он используется в производстве, управлении доходами, телекоммуникациях, рекламе, архитектуре, схемотехнике и во многих других областях ".[2]

Математическая статистика

Событие в жизни Данцига стало началом знаменитой истории в 1939 году, когда он был аспирантом в Калифорнийский университет в Беркли. Ближе к началу урока, на который опоздал Данциг, профессор Ежи Нейман написал два примера известных нерешенных статистика проблемы на доске. Когда Данциг прибыл, он решил, что эти две задачи были домашним заданием, и записал их. По словам Данцига, проблемы «казались немного сложнее, чем обычно», но несколько дней спустя он представил готовые решения для двух проблем, все еще полагая, что это задание, которое просрочено.[4][8]

Шесть недель спустя Данцига посетил взволнованный профессор Нейман, который хотел сказать ему, что домашние задания, которые он решил, были двумя из самых известных нерешенных проблем в статистике.[2][4] Он подготовил одно из решений Данцига для публикации в математическом журнале.[9] Как сказал Данциг в интервью 1986 г. Журнал математики колледжа:[10]

Год спустя, когда я начал беспокоиться о теме диссертации, Нейман просто пожал плечами и сказал мне завернуть две задачи в папку, и он примет их как мою диссертацию.

Спустя годы другой исследователь, Авраам Вальд, готовился к публикации статьи, в которой был сделан вывод по второй проблеме, и включил Данцига в качестве соавтора, когда он узнал о более раннем решении.[4][11]

Эта история стала распространяться и использовалась в качестве мотивационного урока, демонстрирующего силу позитивного мышления. Со временем имя Данцига было удалено, а факты изменены, но основная история сохранилась в форме городская легенда и как вступительная сцена в фильме Хорошая будет охота.[8]

Линейное программирование

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

Основоположниками этого предмета являются Леонид Канторович, русский математик, разработавший задачи линейного программирования в 1939 году, Данциг, опубликовавший симплексный метод в 1947 г. и Джон фон Нейман, который разработал теорию двойственность в том же году.

Данцига попросили разработать метод, который ВВС США могли бы использовать для улучшения процесса планирования.[12] Это привело к его оригинальному примеру поиска наилучшего распределения 70 человек на 70 должностей, показывающего полезность линейное программирование. Вычислительная мощность, необходимая для тестирования всех перестановок для выбора наилучшего назначения, огромна; количество возможных конфигураций превышает количество частиц во Вселенной. Тем не менее, требуется всего лишь мгновение, чтобы найти оптимальное решение, поставив задачу в виде линейной программы и применив симплексный алгоритм. Теория линейного программирования резко сокращает количество возможных оптимальных решений, которые необходимо проверить.

В 1963 году Данциг Линейное программирование и расширения был опубликован Princeton University Press. Богатая глубоким пониманием и освещением важных тем, книга быстро стала «библией» линейного программирования.

Личная жизнь

Данциг получил степень бакалавра математики и физики в Университете штата Мэриленд в 1936 году, когда он женился на Энн С. Шмунер.[13][14] Он умер 13 мая 2005 г. в своем доме в г. Стэнфорд, Калифорния, осложнений от сахарный диабет и сердечно-сосудистые заболевания. Ему было 90 лет.[2]

Публикации

Книги Джорджа Данцига:

  • 1953. Замечания по линейному программированию. Корпорация РЭНД.
  • 1956. Линейные неравенства и родственные системы. С другими. Под редакцией Х.В. Кун и А. Такер. Издательство Принстонского университета.
  • 1963. Линейное программирование и расширения. Princeton University Press и RAND Corporation. pdf от RAND
  • 1966. О непрерывности минимального множества непрерывной функции. С Джон Х. Фолкман и Норман Шапиро.
  • 1968. Математика наук о принятии решений. С Артуром Ф. Вейноттом-младшим Летний семинар по прикладной математике 5-е: 1967: Стэнфордский университет. Американское математическое общество.
  • 1969. Лекции по дифференциальным уравнениям. Азиз А.К., главный редактор. Авторы: Джордж Б. Данциг и другие.
  • 1970. Оптимизация системы транспортировки природного газа. С другими.
  • 1973. Компактный город; план создания пригодной для жизни городской среды. С Томасом Л. Саати.
  • 1974. Исследования по оптимизации. Отредактировано B.C. Карнизы. Математическая ассоциация Америки.
  • 1985. Математическое программирование: эссе в честь Джорджа Б. Данцига. Под редакцией Р. В. Коттла. Общество математического программирования.
  • 1997. Линейное программирование 1: Введение. G.B.D. и Мукунд Н. Тапа. Springer-Verlag.
  • 2003. Линейное программирование 2: теория и расширения. G.B.D. и Мукунд Н. Тапа. Springer-Verlag.
  • 2003. The Basic Джордж Б. Данциг. Под редакцией Ричарда В. Коттла. Stanford Business Books, Stanford University Press, Стэнфорд, Калифорния.[15]

Главы книги:

  • Данциг, Джордж Б. (1960), «Общие выпуклые объективные формы», в Эрроу, Кеннет Дж.; Карлин, Сэмюэл; Суппес, Патрик (ред.), Математические модели в социальных науках, 1959: Труды первого Стэнфордского симпозиума, Стэнфордские математические исследования в социальных науках, IV, Стэнфорд, Калифорния: Stanford University Press, стр. 151–158, ISBN  9780804700214.

Статьи, подборка:

Смотрите также

Примечания

  1. ^ Гасс, Саул И. (2011). "Джордж Б. Данциг". Профили в исследовании операций. Международная серия исследований по операциям и менеджменту. 147. С. 217–240. Дои:10.1007/978-1-4419-6281-2_13. ISBN  978-1-4419-6280-5.
  2. ^ а б c d е ж Джо Холли (2005). "Некрологи Джорджа Данцига". В: Вашингтон Пост, 19 мая 2005 г .; B06
  3. ^ а б c Ричард В. Коттл, Б. Кертис Ивз и Майкл А. Сондерс (2006). "Мемориальная резолюция: Джордж Бернар Данциг". Стэнфордский отчет, 7 июня 2006 г.
  4. ^ а б c d е ж грамм час Альберс, Дональд Дж .; Александерсон, Джеральд Л.; Рид, Констанс, ред. (1990). "Джордж Б. Данциг". Больше математиков. Харкорт Брейс Йованович. стр.60–79. ISBN  978-0-15-158175-7.
  5. ^ Национальный научный фонд - Национальная медаль президента за науку
  6. ^ Стипендиаты: Алфавитный список, Институт исследований операций и управленческих наук, заархивировано из оригинал на 2019-05-10, получено 2019-10-09
  7. ^ Роберт Фройнд (1994). "Профессору Джорджу Данцигу: основателю линейного программирования исполняется 80 лет". В: Новости SIAM, Ноябрь 1994 г.
  8. ^ а б «Неразрешимая математическая задача». Сноупс. 28 июня 2011 г.
  9. ^ Данциг, Джордж (1940). «Об отсутствии тестов гипотезы« Стьюдента », имеющих степенные функции, не зависящие от σ». Анналы математической статистики. 11 (2): 186–192. Дои:10.1214 / aoms / 1177731912.
  10. ^ Альенде, Сира М .; Боуза, Карлос Н. (2005). "Профессор Джордж Бернард Данциг, Life & Legend" (PDF). Revista Investigación Operacional. 26 (3): 205–11.
  11. ^ Данциг, Джордж; Уолд, Абрахам (1951). "Об основной лемме Неймана и Пирсона". Анналы математической статистики. 22: 87–93. Дои:10.1214 / aoms / 1177729695. Получено 14 октября 2014.
  12. ^ "Биографические данные: Данциг, Джордж Б." ИНФОРМАЦИЯ. Получено 2020-10-30.
  13. ^ https://news.stanford.edu/news/2005/may25/dantzigobit-052505.html
  14. ^ https://www.telegraph.co.uk/news/obituaries/1490820/George-Dantzig.html
  15. ^ Тодд, Майкл Дж. (2011). "Рассмотрение: The Basic Джордж Б. Данциг, Ричард У. Коттл ". Бык. Амер. Математика. Soc. (Н.С.). 48 (1): 123–129. Дои:10.1090 / S0273-0979-2010-01303-3.

дальнейшее чтение

внешняя ссылка