La programmazione lineare divenne di uso diffuso a partire dal 1947 in corrispondenza con la pianificazione delle attività militari. ... E' interessante notare che prima del 1947, nonostante la sua ampia applicabilità, la programmazione lineare era sconosciuta ...
Nel 1939 Kantorovitch fece una proposta molto importante che venne trascurata nell' U.S.S.R. ... Io fui affascinato dal lavoro di Wassily Leontieff che nel 1932 propose una semplice struttura matriciale che viene chiamata 'modello delle interdipendenze settoriali' della economia americana.
Il modello era concepito in modo semplice e poteva essere applicato, grazie al sufficiente dettaglio, in modo da essere utile per le esigenze pratiche di pianificazione. Io capii subito che doveva essere generalizzato. ... Era necessario un modello con molte variabili alternative. ... A metà del 1947 decisi che l'obiettivo doveva essere reso esplicito. Formulai il problema generale di pianificazione con un insieme di assiomi. Gli assiomi riguardavano le relazioni tra due tipi di insiemi: il primo insieme (termini noti) riguardava le quantità di prodotti/servizi che dovevano essere consumati o prodotti e il secondo riguardava le attività o processi produttivi (variabili) che dovevano soddisfare, essendo non negative, questi fabbisogni. Il sistema matematico risultante che doveva essere risolto era: la minimizzazione di una funzione obiettivo lineare soggetta a vincoli lineari di uguaglianza o disuguaglianza. ... L' intuizione di vedere le variabili come colonne mi fece capire che il metodo del Simplesso sarebbe stato una tecnica molto efficiente per risolvere i programmi lineari. Fu questo che proposi nel 1947 e per fortuna funzionò! La prima applicazione in grande scala del metodo del Simplesso fu il problema di trovare una dieta adeguata (sistema vincolante) al costo minimo (funzione obiettivo). ... La possibilità di stabilire obiettivi sufficientemente generali e trovare poi vie di soluzione ottimali a problemi pratici di grande complessità, è stato uno sviluppo rivoluzionario. La programmazione lineare è diventata strumento di uso diffuso in alcuni settori come ad esempio la pianificazione delle industrie chimiche e petrolifere". George B. Dantzig (1914, 2005) Reminiscenze sulle origini della programmazione lineare. Intervistato nel Febbraio1999 da Peter Horner per la rivista ORMS (Operation Research - Management Science) Dantzig ha detto tra l'altro: Quale è la sua definizione di ricerca operativa? "Io la chiamo la scienza per prendere le decisioni (decision making). 
Tutti i modi per astrarre da un problema al fine di tradurlo in forma matematica. Questa definizione comprende sia le persone con inclinazione matematica teorica portati a generalizzare i problemi sia, dall'altro estremo le persone che hanno problemi molto specifici e concreti comprese quelle che sono pressate per dare risposte tempestive al loro capo. La ricerca operativa è tutto questo, ma se chiedete ad altri potrete avere aspetti diversi del quadro."
Nel mondo reale trovare la soluzione ottimale è solo una parte del problema. La parte più difficile è spesso quella di convincere il capo decisore (decision maker) a mettere in pratica la soluzione individuata.
"Questo è corretto perché il decision maker sa bene che il modello utilizzato rappresenta spesso solo una parte del problema che lui è chiamato a risolvere. Ritengo che abbia ragione ad essere scettico e prudente."
Quali sono le persone che la colpiscono maggiormente?
"Bene, io presto sempre grande attenzione alle persone che hanno risolto dei problemi ai quali io stesso ho lavorato senza ottenere successo. Questo è il mio criterio per riconoscere uno scienziato di valore. Ralph Gomory ne è un esempio. Il lavoro che lui ha fatto per la programmazione matematica a numeri interi rientra in questa categoria."
Problema
Si consideri una piccola azienda che vende due soli prodotti (X1 e X2). Ogni unità di X1 richiede 1.5 ore di lavorazione sulla macchina M1 e 2.5 ore sulla macchina M2. Ogni unità di X2 richiede 2.5 ore su M1 e 1.5 ore su M2. M1 può lavorare per un massimo di 365 ore al mese ed M2 per 336. Il margine di contribuzione, che va a coprire i costi fissi mensili (50.000 Eur), è di 550 Eur per ogni unità di X1 venduta e di 500 Eur per ogni unità di X2. L'azienda si impegna a rendere disponibile per un importante cliente almeno 75 unità di X1 ogni mese. Quante unità di X1 ed X2 conviene produrre ogni mese per ottimizzare il profitto Z?
Approccio contabile: Il prodotto X1 ha il miglior margine di contribuzione (550 Eur) dunque conviene produrne il massimo compatibile con il vincolo più restrittivo: (X1 = 336/2.5 = 134.4; X2 = 0). Il profitto risultante è: Z = 550*134 - 50.000 = 73.700 -50.000 = 23.700 Eur/mese.
Modello di Programmazione lineare
Z = 550*X1 + 500*X2 - 50.00 Max Z! Funzione obiettivo da massimizzare
1.5*X1 + 2.5 X2 2.5*X1 + 1.5 X2 X1 >= 75 Bound Vincolo di mercato per il prodotto X1
Soluzione del modello con il metodo del Simplesso di Dantzig:
X1 = 75 unità/mese; X2 = 99 unità mese; tutti i vincoli sono soddisfatti.
Z = 550*75 + 500*99 - 50.000 = 40.750 Eur/mese; profitto totale massimo ottenibile. D% = (40.750 - 23.700)/23.700 = 72%; differenza percentuale rispetto alla soluzione contabile.
In figura è rappresentato geometricamente il problema: la pianta (X1, X2) rappresenta tutte le possibili alternative produttive, il triangolo blu rappresenta la regione (chiamata ammissibile) dello spazio (X1, X2) che rispetta tutti i vincoli del problema. Il profitto (Z , terza cordinata ) deve essere pensato come un piano inclinato che cresce al crescere di X1 ed X2: le rette trattegiate sono le curve di livello del profitto che cresce nella direzione della freccia. Dantzig ha dimostrato che in generale la regione ammissibile di un problema di programmazione lineare, anche se formato da migliaia di variabili e di vincoli, è costituita da un poliedro convesso n-dimensionale (simplesso) e che la soluzione ottimale si trova sempre su uno dei (in generale tantissimi) vertici del poliedro. Il suo metodo permette di evolvere da un vertice ad uno migliore evitando di doverli esplorare tutti, compito proibitivo anche per i più potenti computer di oggi. Nel semplice problema descritto il poliedro convesso si riduce ad un triangolo e la soluzione ottimale al vertice (75,99) indicato in figura. Si osservi che il vincolo (VM1) relativo alla macchina M1 è ridondante cioè non contribusce a delimitare la regione ammissibile. Tuttavia se il limite delle ore massime mensili sopportate da M1 dovesse ridursi il vincolo diventerebbe operativo e la regione ammissibile si trasformerebbe da un triangolo ad un quadrangolo (4 vertici). (R: Chiappi Il foglio elettronico come strumento per il problem solving: metodi e modelli per le organizzazioni, F. Angeli, Milano 2008).
In Excel (il sistema di calcolo più diffuso nelle organizzazioni, se si prescinde dalle applicazioni specialistiche scientifiche o gestionali) i problemi di programmazione matematica, sino a circa cento variabili e cento vincoli, possono essere affrontati con il Risolutore richiamabile dal menù Strumenti. Il Risolutore utilizza il metodo del simplesso (Dantzig) per la programmazione lineare, il metodo generalizzato del gradiente ridotto (Abadie) per la programmazione non lineare ed il metodo del branch and bound (Land&Doig) per la programmazione a numeri interi.
