Matematicamente
|
|
Ti trovi in: Home 
Approfondimenti Problem Solving La programmazione lineare [George B. Dantzig]
| La programmazione lineare [George B. Dantzig] | di Roberto Chiappi |
|
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 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
Soluzione del modello con il metodo del Simplesso di Dantzig:
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.
Scritto da , il 18-04-2011 20:45 Emilio> Si parlò di Sputnik matematico sovietico quando Kachian presentò, alla fine degli anni 70 dello scorso secolo il metodo dell’ellissoide (complessità polinomiale) per la programmazione lineare. Il metodo però ha solo una valenza teorica in quanto praticamente il metodo di Dantzig (complessità esponenziale) è molto più efficiente. Diverso è il caso dello interior point method di Karmarkar che, ideato negli anni 80, si serve di informazioni provenienti dall’interno della regione ammissibile. Per particolari problemi, sempre di grandi dimensioni, l’algoritmo di Karmarkar risulta competitivo e talora più efficiente del Simplesso. Il fatto è che il metodo del Simplesso, pur essendo di complessità esponenziale nel caso peggiore, è nella maggioranza dei casi di complessità polinomiale e talora la complessità cresce solo linearmente con la dimensione del problema. Mi risulta che, data l’importanza dei problemi di P.L., attualmente i ricercatori stiano lavorando sia a varianti del metodo di Karmarkar che al metodo di Dantzig per renderli sempre più efficienti e robusti. Piacerebbe anche a me, che sono solo un utente della P.L., avere informazione dai lettori esperti sul procedere di questi studi. Maria> Effettivamente la P.L. si presta molto bene a risolvere i problemi di massimizzazione di una funzione economica in presenza di risorse limitate. Ricordo però che questi problemi (produzione, trasporto, logistica, ecc.) sono stati affrontati per la prima volta da Kantorovich (premio Stalin e premio Nobel) in Unione Sovietica; nell’ambito quindi di una economia pianificata. I problemi delle università, ospedali, ecc. possono ricondursi al problema di garantire livelli di servizio adeguati (obiettivi multipli primari) cercando di minimizzare una funzione di costo (obiettivo secondario). Anche le organizzazioni che non hanno come obiettivo primario il “creare valore per gli azionisti” debbono sempre tenere in conto l’efficienza e l’eliminazione degli sprechi perché in caso contrario si “distrugge il valore della collettività” e si riducono le possibilità di benessere sociale. Il problema dei livelli di servizio adeguati, al costo minimo, assomiglia molto al problema della dieta affrontato originariamente da Dantzig: in quel caso si trattava infatti di garantire un sufficiente apporto di proteine, vitamine, carboidrati, ecc. ad un costo minimo. La grande difficoltà dei problemi dei “servizi adeguati” sta nel eseguire un corretto passaggio dalla situazione problematica all’ equivalente modello matematico: le vie dell’inferno sono lastricate di soluzioni matematiche corrette che risolvono problemi sbagliati (difficoltà della traduzione tra problema e modello). Scritto da , il 18-04-2011 20:13 Sì, ce ne sono altri. La cosa interessante è che hanno minore complessità computazionale (almeno, da un punto di vista teorico). Puoi partire da qui per qualche ulteriore "ricerca": http://en.wikipedia.org/wiki/Simplex_algorithm#Other_algorithms Scritto da , il 17-04-2011 16:39 Mi sembra che i problemi di programmazione lineare consistano nell’allocare al meglio le risorse per massimizzare i profitti. Si tratta quindi sempre di ottimizzare le prestazioni di una impresa privata operante in una economia capitalistica. Inoltre, anche in una economia, capitalistica esistono organizzazioni (ospedali, scuole, università, enti previdenziali, ecc.) che non hanno l’obiettivo di creare valore per l’azionista, ma che sono volte alla soddisfazione o alla fornitura di servizi ai propri clienti/utenti. Scritto da , il 16-04-2011 15:42 Ho letto che oggi esistono metodi, per la programmazione lineare, migliori del metodo del Simplesso di Dantzig. E’ vero? Quali sono? Scrivi Commento
Powered by AkoComment Tweaked Special Edition v.1.4.6 |
||||||
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 ...
| < Prec. | Pros. > |
|---|
|
Iniziative editoriali
|
Test - quiz - simulazione |
Gioca con la matematica |
 |
|
|
|
|