Il problema di P.L in due variabili ha il seguente modello matematico costituito da una funzione economica, o funzione obiettivo , da massimizzare o da minimizzare.
Si risolve il sistema dei vincoli mediante rappresentazione grafica e si determina l’area ammissibile, o dominio dei vincoli costituita, da un poligono, o da una regione poligonale illimitata (se l’insieme non è vuoto) che possono eventualmente ridursi ad un segmento, o ad una semiretta, o ad un punto.
Indichiamo la terminologia utilizzata:
Ogni coppia di valori (x1,x2) appartenente al dominio dei vincoli viene detta soluzione ammissibile:
Ogni coppia di valori (x1,x2) ottenuta come intersezione fra due rette che limitano il dominio è detta soluzione di base;
Le coppie di valori(x1,x2) che hanno per immagine i vertici del dominio dei vincoli, sono dette soluzioni ammissibili di base e fra esse è da ricercarsi la soluzione ottima.
1. determinare il dominio dei vincoli mediante la rappresentazione grafica dei vincoli sul piano Ox1x2;
2. se il dominio dei vincoli è un poligono, calcolare il valore della funzione economica nei vertici e ricavare il vertice in cui la funzione assume valore massimo o minimo; se il dominio dei vincoli è illimitato, esaminare l’andamento delle linee di livello per dedurre se esiste un vertice che ottimizza la funzione.
PROBLEMI DI P.L IN TRE O PIU VARIABILI RISOLUBILI CON METODO GRAFICO
Un problema di P.L in n variabili e riconducibile ad un problema di P.L in due variabili e quindi risolubile per via grafica, se nel sistema dei vincoli compaiono n-2 equazioni dalle quali ricavare n-2 variabili in funzione delle restanti 2.
PROBLEMI DI P.L IN N VARIABILI: METODO DEL SIMPLESSO
Il metodo del simplesso, è un algoritmo che permette, attraverso un numero finito di iterazioni, di passare da una soluzione ammissibile di base alla soluzione ottima (naturalmente se il problema ammette soluzione, ossia se i vincoli sono compatibili e quindi l’insieme delle soluzioni ammissibili non è vuoto).
Se il problema di P.L è espresso nella forma standard(2) il procedimento per la sua risoluzione è costituito dai seguenti passi:
si determina una prima soluzione ammissibile di base e si calcola il corrispondente valore di z.
si passa da questa prima soluzione ad una seconda soluzione ammissibile di base che migliori il valore di z, modificando i valori della incognite della prima soluzione in modo che una variabile, che prima era nulla, entri nella base e ne esca un’altra.
si procede successivamente finché si arriva alla soluzione ottima.
PROBLEMI PARTICOLARI DI PROGRAMMAZIONE LINEARE:
PROBLEMI DI TRASPORTO
Il problema di trasporto consiste nel programmare il trasporto di prodotti da m punti di origine O1,O2,.Om (stabilimenti) aventi le disponibilità a1,a2,..am ad n destinazioni D1,D2,.Dn(magazzini o clienti) aventi la capacità b1,b2,.bn in modo che il costo totale sia minimo.
METODO NORD OVEST
Un metodo semplice per trovare una soluzione ammissibile di base è detto metodo nord-ovest.
Si forma una matrice di m righe e n colonne e si inizia dalla posizione più in alto a sinistra. In tale punto si assegna la massima quantità possibile da O1 a D1.
METODO DI HOUTHAKKER
Il metodo di houthakker , a differenza del metodo nord-ovest tiene conto dei costi di trasporto e permette di trovare una soluzione ammissibile di base molto vicina a quella ottima. Si selezionano nella tabella dei costi gli elementi che sono il minimo della propria riga e della propria colonna e si assegna in quella posizione, la massima quantità possibile saturando così la riga o la colonna che si incrociano in quell’elemento. Eliminate le righe e le colonne saturate rimane una matrice nella quale di nuovo si selezionano gli elementi minimi della propria riga e della propria colonna, ecc..