Теорема Magnum MCMXLVIII симплексний метод Mathlog
Математична оптимізація розпочалася наприкінці 1930-х років роботою Леоніда Канторовича.
Канторович почав вчитися у віці 14 років у Ленінграді, де спочатку займався описовою теорією множин та деякими проблемами, поставленими Лусіним, потім перейшов до функціонального аналізу, закінчив свою абілітацію у 1935 році у віці 23 років та підручник з колегою наступного року написано про апроксимаційні методи вищого аналізу. Оскільки йому було доручено оптимізувати виробництво фабрики шпону, крім професорської роботи з 1938-39 рр., Він розробив математичні методи, які стали відомими як лінійна оптимізація.
Можна геометрично проілюструвати задачу лінійної оптимізації: нерівності та визначити багатогранник. Максимізація відповідає зміщенню гіперплощини у напрямку вектора c, поки зміщена гіперплощина просто не торкнеться багатогранника, описаного нерівностями. Але питання в тому, як реалізувати цей геометричний принцип на практиці.
Джордж Данциг два роки після закінчення навчання працював статистиком, а також розпочав докторську ступінь у Берклі. Легенда з’явилася пізніше, коли він провів і розв’язав два недоведені припущення щодо домашнього завдання, написаного на дошці професором - статистиком Нейманом - на лекції. Його професор був вражений і підготував докази до публікації. Данциг перервав навчання в докторантурі через війну і став керівником статистичного відділу ВПС. Після війни він знову приступив до навчання і в 1946 році здобув ступінь доктора наук у Неймана з детальною розробкою своїх доказів.
Помірно активний чоловік вагою 154 фунти повинен з'їдати скільки кожного з 77 продуктів щодня протягом дев'яти споживаних поживних речовин, щоб задовольнити принаймні Рекомендовані дієтичні норми (RDA), рекомендовані Національною науковою радою в 1943 році, з мінімальними витратами на дієту залишитися?
Оскільки на той час не було вдосконалених методів лінійної оптимізації, Стіглер повинен був підійти до цієї проблеми евристичними підходами: оскільки 62 з продуктів містять лише кілька поживних речовин, він лише врахував інші 15 і розрахував серед них оптимальне рішення. Річна вартість його рішення становила 39,93 доларів.
За допомогою симплексного методу тепер можна було розрахувати фактично оптимальне рішення. У розрахунках брали участь дев'ять людей з дев'ятьма нерівностями та 77 змінними, які разом вимагали близько 120 людських днів арифметичної роботи. Річна вартість розрахункової оптимальної дієти (за цінами 1939 р.) Становила 39,69 дол. США. Отже, ви заощадили 24 центи порівняно з початково розрахованим рішенням.