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

Джордж Данциг
Джеральд Форд награждение Джорджа Б. Данцига Национальной медалью науки, 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.

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

• Данциг, Джордж Б. (июнь 1940 г.). «Об отсутствии проверки гипотезы« Стьюдента », имеющей степенные функции, не зависящие от σ». Анналы математической статистики. 11 (2): 186–92. Дои:10.1214 / aoms / 1177731912. JSTOR  2235875.
• Wood, Marshall K .; Данциг, Джордж Б. (1949). «Программирование взаимозависимой деятельности: I Общая дискуссия». Econometrica. 17 (3/4): 193–9. Дои:10.2307/1905522. JSTOR  1905522.
• Данциг, Джордж Б. (1949). «Программирование взаимозависимых действий: II математическая модель». Econometrica. 17 (3): 200–211. Дои:10.2307/1905523. JSTOR  1905523.
• Данциг, Джордж Б. (1955). «Оптимальное решение динамической модели Леонтьева с подстановкой». Econometrica. 23 (3): 295–302. Дои:10.2307/1910385. JSTOR  1910385.

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

Примечания

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

• Коттл, Ричард; Джонсон, Эллис; Мокрый, Роджер (март 2007 г.). "Джордж Б. Данциг (1914–2005)" (PDF). Уведомления Американского математического общества. 54 (3): 344–62.
• "Профессору Джорджу Данцигу: основателю линейного программирования исполняется 80 лет", СИАМ Новости, Ноябрь 1994 г.
• О'Коннор, Джон Дж.; Робертсон, Эдмунд Ф., "Джордж Данциг", Архив истории математики MacTutor, Сент-Эндрюсский университет.
• Данциг, Джордж Б. (1990). «Проблема диеты». Интерфейсы. 20 (4): 43–7. Дои:10.1287 / inte.20.4.43. JSTOR  25061369.
• Коттл, Ричард В. (2005). «Джордж Б. Данциг: легендарная жизнь в математическом программировании». Математическое программирование. 105 (1): 1–8. Дои:10.1007 / s10107-005-0674-4. ISSN  0025-5610. S2CID  207054446.

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

• Работы Джорджа Данцига или о нем в библиотеках (WorldCat каталог)
• О'Коннор, Джон Дж.; Робертсон, Эдмунд Ф., "Джордж Данциг", Архив истории математики MacTutor, Сент-Эндрюсский университет.
• Дань Георгию Данцигу и Леониду Хачияну
• Некрологи Джорджа Данцига
• Интервью с Джорджем Б. Данцигом: отцом линейного программирования - College Mathematical Journal, 1986 JSTOR  2686279
• ИНФОРМАЦИЯ Веб-сайт Мемориала Джорджа Данцига
• Джордж Данциг на Проект "Математическая генеалогия"
• Биография Джорджа Данцига от Института исследования операций и наук управления (ИНФОРМС)
• Интервью с лауреатом Нобелевской премии Гарри М. Марковицем [1]