Simpleks metoda

George Dantzig radio je na načinima planiranja zrakoplovstva američke vojske tijekom Drugog svjetskog rata koristeći stolni kalkulator. Tijekom 1946. kolega ga je izazvao da mehanizira postupak planiranja kako bi ga odvratio od zaposlenja. Dantzig je problem formulirao kao linearne nejednakosti nadahnute radom Wassilya Leontiefa , međutim, u to vrijeme nije uključio cilj kao dio svoje formulacije. Bez cilja, ogroman broj rješenja može biti izvediv, i stoga za pronalaženje „najboljeg“ izvedivog rješenja moraju se koristiti vojno određena „osnovna pravila“ koja opisuju kako se ciljevi mogu postići za razliku od samoga određivanja cilja. Dantzigov temeljni uvid bio je shvatiti da se većina takvih osnovnih pravila može prevesti u linearnu objektivnu funkciju koju je potrebno maksimalno iskoristiti. Razvoj simpleks metode bio je evolucijski i dogodio se u razdoblju od oko godinu dana.
Nakon što je Dantzig uključio objektivnu funkciju kao dio svoje formulacije sredinom 1947., Problem je bio matematički više uočljiv. Dantzig je shvatio da je jedan od neriješenih problema koji je pogriješio kao domaći zadatak u klasi svog profesora Jerzyja Neymana (i zapravo kasnije riješen) bio primjenjiv u pronalaženju algoritma za linearne programe. Ovaj problem uključivao je pronalaženje Lagrangeovih množitelja za opće linearne programe preko kontinuuma varijabli, svaka ograničena između nule i jedne, i zadovoljavanje linearnih ograničenja izraženih u obliku Lebesgueovih integrala. Dantzig je svoju domaću zadaću kasnije objavio kao tezu da bi stekao doktorat. Geometrija stupaca korištena u ovoj tezi dala je Dantzigu uvid koji ga je natjerao da vjeruje da će Simplex metoda biti vrlo učinkovita.