Programmazione lineare

appunti scolastici di matematica di Elena

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:

1. si determina una prima soluzione ammissibile di base e si calcola il corrispondente valore di z.

2. 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.

3. 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..