Theorema Magnum MCMXLVIII simplexná metóda Mathlog

magnum

Matematická optimalizácia sa začala koncom 30. rokov 20. storočia dielom Leonida Kantorowitscha.
Kantorowitsch začal študovať ako 14-ročný v Leningrade, kde sa spočiatku zaoberal deskriptívnou teóriou množín a niektorými problémami, ktoré Lusin predstavoval, potom prešiel na funkčnú analýzu, habilitoval sa v roku 1935 vo veku 23 rokov a nasledujúci rok učebnicu s kolegom. písané o aproximačných metódach vyššej analýzy. Pretože mu okrem profesúry v rokoch 1938–39 bola zverená optimalizácia výroby továrne na výrobu dýhového dreva, vyvinul matematické metódy známe ako lineárna optimalizácia.

Dá sa geometricky ilustrovať problém lineárnej optimalizácie: nerovnosti a definovať mnohosten. Maximalizácia zodpovedá posunutiu nadroviny v smere vektora c, kým sa nadsadená nadrovina nedotkne mnohostenu opísaného nerovnosťami. Otázkou ale je, ako tento geometrický princíp uplatniť v praxi.

George Dantzig pracoval po ukončení štúdia dva roky ako štatistik a tiež si urobil doktorát v Berkeley. Legenda prišla neskôr, keď na prednáške držal a vyriešil dva nedokázané predpoklady pre domáce úlohy, ktoré na tabuľu napísal profesor - štatistik Neyman. Jeho profesor bol ohromený a pripravil dôkazy na zverejnenie. Dantzig kvôli vojne prerušil doktorandské štúdium a stal sa vedúcim štatistického oddelenia vo vzdušných silách. Po vojne sa dal na ďalšie štúdium a doktorát získal v roku 1946 u Neymana s rozpracovaním svojich dôkazov.

Mierne aktívny muž s hmotnosťou 154 libier by mal zjesť koľko z každej zo 77 potravín denne na príjem deviatich živín, aby spĺňal aspoň odporúčané diétne dávky (RDA) odporúčané Národnou radou pre výskum v roku 1943, s minimálnymi nákladmi na stravu pobyt?

Pretože v tom čase neexistovali žiadne pokročilé metódy lineárnej optimalizácie, musel Stigler pristupovať k tomuto problému pomocou heuristických prístupov: pretože 62 potravín obsahovalo iba niekoľko výživných látok, zvážil iba ďalších 15 a vypočítal medzi nimi optimálne riešenie. Ročné náklady na jeho riešenie boli 39,93 dolárov.
Pomocou simplexnej metódy bolo teraz možné vypočítať skutočne optimálne riešenie. Do výpočtov bolo zapojených deväť ľudí s deviatimi nerovnosťami a 77 premennými, ktorí si spolu vyžadovali aritmetickú prácu okolo 120 človekodní. Ročné náklady na vypočítanú optimálnu stravu (v cenách roku 1939) boli 39,69 USD. Ušetrili ste teda 24 centov v porovnaní s pôvodne vypočítaným riešením.