Metodi e Modelli di Programmazione Lineare · 1 Metodi e Modelli di Programmazione Lineare Massimo...

1

Metodi e Modelli di Programmazione Lineare

Massimo Paolucci([email protected])

DIST – Università di Genova

2

La Programmazione Lineare (LP)

Modello di programmazione matematica

• x vettore delle variabili decisionali • X insieme delle soluzioni ammissibili• f(x) funzione obiettivo scalare

Metodo decisionale = algoritmo di ottimizzazione

max f(x)s.t.x X R n∈ ⊆

2

3

LP – richiami teorici

La definizione di un modello di programmazione matematica

FormulazioneMatematica

Definizionedelle variabili

Definizionedell’obiettivo

Definizionedei vincoli

4

LP – richiami teoriciQuando sia la funzione obiettivo che le relazioni che esprimono i vincoli sono lineari si ha un problema di PL

x è il vettore nx1 delle variabili decisionali

c è il vettore nx1 dei coefficienti della funzione obiettivo

b è il vettore mx1 dei termini noti dei vincoli

A è la matrice mxn dei coefficienti dei vincoli; A=[aij], i=1,...,m, j=1,...,n

n

T0

Rx

0xbxA

xcxmax

∈

≥=

=Problema in

Forma Standard

(1)(2)

3

5


Ipotesi nella forma standard

b≥0 ⇒ bi≥0 ∀i=1,...,m

m<n

m=rango(A)

Qualunque problema di PL può essere trasformato in unproblema equivalente in forma standard

Un vettore x° se soddisfa i vincoli (1) è detto soluzione, se soddisfa (1) e (2) è soluzione ammissibile

Se x∈Rn ⇒ PL a variabili continue

Se x∈Zn ⇒ PL a variabili intere (IP)

Se alcune variabili sono reali ed altre intere ⇒ PL mista (MIP)

6


Consideriamo i risultati fondamentali nel caso di x∈Rn

• L’insieme dei vincoli (in generale disuguaglianze) rappresenta un Poliedro in Rn

• Dato un problema P di PL, se il Poliedro è:chiuso e non vuoto (Politopo) P è ammissibile con soluzioni ottime finite

aperto e non vuoto P può essere ammissibile con soluzioni ottime finite oppure ammissibile senza soluzione ottime finite (illimitato, o con ottimo all’infinito)

vuoto P è non ammissibile (senza soluzioni ammissibili)

• Un poliedro è un insieme convesso i cui vertici sono detti Punti Estremi

4

7


X Politopo

X Aperto

X Vuoto

{ } ∅≠≤∈= bxA:xX nR

X

X

X1

X2

∅=∩= 21 XXX

8


La soluzione ottima finita (se esiste) corrisponde ad uno o più punti estremi del poliedro.

Tali punti estremi sono caratterizzati algebricamente dalle soluzioni di base ammissibili

Una soluzione di base corrisponde alla scelta di m variabili su n, ossia alla scelta di una sottomatrice B (detta Base) mxm di A invertibile, e si calcola annullando le restanti n-m variabili fuori base.

)1x)mn((basefuori.vardelleVettore)1mx(basedi.vardelleVettore

xx

xN

B−⎥⎦

⎤⎢⎣

⎡=

5

9


Soluzione di base

Soluzione di base ammissibile se

xxx

B bB

N= ⎡

⎣⎢⎤

⎦⎥=

⎡

⎣⎢

⎤

⎦⎥

−1

0

x B bB = ≥−1 0

Teorema

Dato X={Ax=b, x≥0} insieme convesso, dove A è una

matrice mxn di rango m con m<n,

xe è un punto estremo di X se e solo se xe è una

soluzione di base ammissibile.

10


Il numero di soluzioni di base è limitato dal massimo numero di matrici B estraibili da A

Teorema Fondamentale della PL

Se un problema di PL ammette soluzione, allora esiste

una soluzione ammissibile di base.

Se un problema di PL ha soluzione ottima finita, allora

ha anche una soluzione di base ottima.

nm

nm m

⎛⎝⎜

⎞⎠⎟

=−!

!(n )!

6

11

LP – L’algoritmo del simplesso (simplex)Il simplesso cerca la soluzione ottima esplorando le soluzioni di base effettuando una ricerca locale: data una soluzione di base verifica se l’obiettivo può essere migliorato e se ciò è possibile determina una soluzione di base migliore adiacente a quella di partenza

Geometricamente esplora la frontiera del poliedro dei vincoli (algoritmo esterno)

X

x1

x2

A (iniziale)

f.obj

B

CD (ottima)

12

LP – L’algoritmo del simplesso (simplex)Problema in forma standard

Generica equazione (m equ. dei vincoli + 1 equ. obiettivo)

nn1

mnmn11m

1nn1111

nn11

Rx

0x,...,0xbxaxa

bxaxa.t.s

xcxcmax

∈

≥≥

=++

=++

++

L

M

L

L

n

T0

Rx

0xbxA

xcxmax

∈

≥=

=

m,,1,0ixyyxRj

jij0iBi K=∀−= ∑∈

7

13

LP – L’algoritmo del simplesso (simplex)

Il Simplesso (in forma algebrica)1. Inizializzazione

Determinare una soluzione di base ammissibile

2. Verifica dell’ottimalitàSe y0j≥0 ∀j∈R allora la soluzione corrente è ottima e l’algoritmo termina, altrimenti andare al passo 3

3. Scelta della variabile entrante in baseScegliere una var. fuori base xk tale che y0k<0 ed andare al passo 4

4. Scelta della variabile uscente dalla baseScegliere la variabile xBr tale che

Se yik≤0 ∀i=1,...m, allora la soluzione del problema è illimitata (nonesiste ottimo finito), e l’algoritmo termina

⎭⎬⎫

⎩⎨⎧

=

>= ik

0i

0yM,...,1irk

0ryymin

yy

ik

14


Il Simplesso (in forma algebrica)5. Pivoting.

Risolvere le equazioni

ricavando xk e xBr i≠r, in funzione di xj, j∈R-{k} e di xBr

La nuova soluzione si ottiene ponendo xj=0, j∈R-{k} e xBr =0Andare al passo 2.

m,,1,0ixyyxRj

jij0iBi K=∀−= ∑∈

8

15


Il TableauContiene i coeff. delle m+1 equazioni dei vincoli e f.ob. e permette di effettuare i passi dell’algoritmo in maniera semplice

x y x y i mBi ij jj R

i+ ∑ = ∀ =∈

0 0 1, , ,K

x x x x xx y y yx y y y

x y y y

x y y y

B Br Bm j k

j k

B j k

Br rj rk r

Bm mj mk m

10 0 0 00

1 1 1 10

0

0

0 0 01 0 0

0 1 0

0 0 1

L L L L L

L L L L L

L L L L L

M M O M M M M M

L L L L L

M M M O M M M M

L L L L L

16


Il Simplesso (sul tableau)

1. InizializzazioneCostruire il tableau iniziale con una soluzione di base ammissibile

2. Verifica dell’ottimalitàSe nella riga di x0 non esistono coefficienti negativi la soluzione corrente è ottima e l’algoritmo termina, altrimenti andare al passo 3

3. Scelta della variabile entrante in baseScegliere una var. fuori base xk tale che y0k<0 ed andare al passo 4.

4. Scelta della variabile uscente dalla baseSe tutti i coefficienti nella colonna di xk sono yik≤0 ∀i=1,...,m, nonesiste ottimo finito e l’algoritmo termina, altrimenti calcolare i rapporti yi0/ yik i=1,...,m, solo per gli yik>0, e scegliere la riga r-esima associataal rapporto più piccolo. Il coeff. yrk è il pivot

9

17


Il Simplesso (sul tableau)

5. Pivoting.

Portare in base xk al posto di xBr dividendo la riga r-esima per il pivot,

quindi sottraendo la nuova riga r alle altre righe del tableau, obiettivo

incluso, dopo averla moltiplicata per il corrispondente coeff. della

colonna k. In questo modo la nuova colonna k sarà formata da tutti

coeff. nulli tranne il coeff. r-esimo uguale ad 1.

Aggiornare l’etichetta della riga r-esima con xk.

Andare al passo 2.

18


Trasformazione dei problemi in forma standard• Vincoli di ≤ si introducono var. di slack (scarto)

• Vincoli di ≥ si introducono var. di surplus (eccedenza)

• Variabili libere si effettua la sostituzione xj = uj – vj con uj ≥0 vj ≥0

• Termini noti negativi (bi ≤0) si cambia il segno al vincolo

• Problema di minimo si cambia segno alla f.ob. e si massimizza (oppure si inverte la condizione di ottimalità dell’algoritmo)

0sbsxabxa iiin

1jjiji

n

1jjij ≥=+→≤ ∑∑

==

0sbsxabxa iiin

1jjiji

n

1jjij ≥=−→≥ ∑∑

==

10

19


Inizializzazione• Base iniziale formata da var. di slack Ax + Is = b

• Metodo delle due fase (Two-Phase Method)

• Metodo del Big-M

Soluzioni degeneri• Almeno una componente di xB è nulla

• Possono causare loop nell’algoritmo (cycling)

Criteri di scelta della var. entrante• Metodo del gradiente

• Metodo del massimo incremento

20

LP – Il problema della produzione (Product Mix)Il problemaDeterminare quali e quanti prodotti produrre (in generale, quali attività eseguire ed a quale livello) in modo da massimizzare il profitto conseguente tenendo conto della disponibilità limitata delle risorse necessarie alla produzione

• Può essere modellato con la PL se le relazioni tecnologiche che legano prodotti e risorse possono essere approssimate in modo lineare

• Inoltre tutte le grandezze possono essere considerate deterministiche (in particolare, i ricavi dalla vendita dei prodotti)

r

x

r

x

11

21

LP – Il problema della produzione (Product Mix)

Formulazione ed interpretazione del problema

• Si dispone di j=1,...,m risorse produttive (ad esempio, materie prime) in quantità limitata

• La massima disponibilità delle risorse è b1,...,bm

• Si possono produrre i=1,...,n diversi prodotti utilizzando con una data tecnologia le risorse disponibili

• Sono note le quantità di risorse necessarie per produrre una unità di ciascun possibile prodotto: per produrre una unità del prodotto i-mo si utilizzano aij unità della risorsa j-ma (nell’ipotesi di linearità questo coeff. resta costante)

• Agli n prodotti sono associati i profitti unitari c1,..., cn (profitto per unitàdi prodotto, ipotizzando tutta la produzione venga venduta, ovvero chevincolando la produzione ad una domanda supposta costante e nota)

22


Formulazione ed interpretazione del problema

n,...,1ixn,...,1i0x

m,...,1jbxa

xcmax

i

i

jn

1iiij

n

1iii

=∈

=≥

=≤∑

∑

=

=

R

Variabili• xi quantità di prodotto i-mo

• continue (?) e positive

Vincoli• la quantità totale di ogni

risorsa utilizzata nella produzione non può superarela disponibilità massima

Obiettivo• il ricavo totale della

produzione

12

23

LP – Il problema della produzione (Product Mix)Formulazione ed interpretazione del problema• E’ un PL in forma canonica di massimizzazione

• A è detta matrice tecnologica

• All’ipotesi di condizioni deterministiche (parametri costanti) si risponde con l’Analisi di Post-ottimalità

• Esempi ed interpretazione

n

T0

Rx

0xbxA

xcxmax

∈

≥≤

=

24

LP – Il problema della produzione (Product Mix)Esempio 1

0x,0x2x

8xx26x2x

x2x3xmax

21

2

21

21

210

≥≥≤

≤+

≤+

+=

(3)

(2)

(1)

x1

1 2 3 4 5 6

1

2

3

(2)

(3)

(1)A

E

D

B C

x2

x0=0

13

25

LP – Il problema della produzione (Product Mix)Esempio 1: Forma Standard

5,...,1i0x2xx8xxx26xx2x

x2x3xmax

i

52

421

321

210

=≥

=+=++

=++

+=

(3)

(2)

(1)

x1

1 2 3 4 5 6

1

2

3

(2) x4

(3) x5

(1) x3

AE

D

B C

x2

x0=0

26

LP – Il problema della produzione (Product Mix)Esempio 1: Il tableau• Base iniziale formata dalle slack

• Il Tableau iniziale

• 1a iterazione: X1 entra ed x4 esce (dal vertice A al vertice ???; eseguire i calcoli ....)

⎥⎥⎥

⎦

⎤

⎢⎢⎢

⎣

⎡=

⎥⎥⎥

⎦

⎤

⎢⎢⎢

⎣

⎡=

286

xxx

x

5

4

3

B

210010x801012x600121x000023x

xxxxx

5

4

3

0

54321−−

14

27

LP – Il problema della produzione (Product Mix)Esempio 1: Il tableau

• Il Tableau dopo la prima iterazione

• 2a iterazione: X2 entra ed x3 esce (dal vertice ??? al vertice ???; eseguire i calcoli ....)

210010x402/102/11x202/112/30x

1202/302/10xxxxxx

5

1

3

0

54321

−−

28

LP – Il problema della produzione (Product Mix)Esempio 1: Il tableau

• Il Tableau dopo la seconda iterazione

• Il tableau è ottimo• La soluzione ottima

3/213/13/200x3/1003/23/101x3/403/13/210x3/3803/43/100x

xxxxx

5

1

2

0

54321

−−

−

⎥⎥⎥

⎦

⎤

⎢⎢⎢

⎣

⎡=

⎥⎥⎥

⎦

⎤

⎢⎢⎢

⎣

⎡=

3/23/103/4

xxx

x

5

1

2*B 0

xx

x4

3*N =⎥

⎦

⎤⎢⎣

⎡=

15

29

LP – Il problema della produzione (Product Mix)Esempio 1: Domande

• Cosa succede alla soluzione se il poliedro fosse aperto?Provare con

• Come si riconosce il caso di più soluzioni ottime equivalenti?Provare con

0x,0x2x

x3xxmax

21

2

210

≥≥≤

+=

0x,0x2x

8x2x36x2x

x2x3xmax

21

2

21

21

210

≥≥

≤

≤+

≤+

+=

30


Esempio 2: 4 prodotti e 3 risorse

• Risoluzione:Manuale (Tableau)Sotware: Excel (solver), Lingo (www.lindo.com), Cplex e OplStudio (www.ilog.com)

4,...,1i0x100x15x10x4x3

120x2x3x5x716xxxx

x11x9x5x4xmax

i

4321

4321

4321

43210

=≥

≤+++

≤+++

≤+++

+++=

16

31

LP – Il problema della produzione (Product Mix)Interpretazione economica• Funzione Obiettivo Curva Isoguadagno

• Vincoli Saturi (binding constraints) Risorse ScarseSlack nulleConverrebbe aumentarne la disponibilità e se sì cosa accadrebbe?

• Vincoli non saturi Risorse abbondantiSlack positiveConverrebbe diminuirne la disponibilità e se sì cosa accadrebbe?

• Domande di carattere economico/gestionale conseguenti alla soluzione:

Vi sono risorse non utilizzate? Posso diminuire lo spreco?Ci sono risorse che mi converrebbe acquisire ulteriormente? Quali e con che priorità?Di quanto ha senso aumentare la disponibilità delle risorse?Che accade se variano i ricavi per i miei prodotti, ovvero quanto è robusta la soluzione?

32

LP – L’analisi di sensitività (post-ottimalità)

L’analisi di sensitività consente di valutare gli effetti di piccole variazioni dei parametri rispetto la soluzione ottima del problema (variazioni marginali)

I casi che vedremo:

• Range di variazione della disponibilità delle risorseAumento di risorse scarseDiminuzione di risorse abbondanti

• Range di variazione dei coeff. di guadagno • Effetti causati dall’acquisizione di nuove risorse• Effetti causati da produzione diversa dall’ottimo (prodotto non

conveniente, nuovo prodotto)

Teoria necessaria: definizione di alcune grandezze e la teoria della dualità

17

33

LP – Definizione di alcune grandezze

Coefficienti di costo ridotto r = (rj, j∈R)• Sono i coeff. delle variabili fuori base nella riga della f.ob. nel

tableau = y0j j∈R• Consideriamo un tableau in forma matriciale ed il caso in cui la

base iniziale è formata da slack

bAIs0c0x

xsTT

0 −bNBIs0cc0x

xxsTN

TB

T0

NB−−

bBNBIBx

bBccNBc0Bcxxxs

111B

1TB

TN

1TB

T1TB0

NB

−−−

−−− −

34

LP – Definizione di alcune grandezze

Coefficienti di costo ridotto r = (rj, j∈R)

• Corrispondono a

e la condizione di ottimalità è rj≥0 j∈RDomanda: che significato ha la presenza di almeno un rj=0 nel tableau ottimo?

I moltiplicatori del simplesso π = (πj, j∈R)

• Corrispondono a

Osservazioni sul tableau ottimo• I moltiplicatori del simplesso sono parte degli r e si riducono agli r

corrispondenti alle slack fuori base• Se la base iniziale era costituita da slack, le colonne delle slack

all’ottimo contengono B-1

jj1T

Bj caBcr −= −

1TBBc −=π

18

35LP – La Teoria della Dualità

Ad ogni problema di PL (Primale) è associato unproblema Duale

Problema Primale (P)

mnmn11m

1nn1111

nn11

bxaxa

bxaxa.t.s

xcxcmax

≤++

≤++

++

L

M

L

L

Problema Duale (D)

nmmn1n1

1m1m111

mm11

cyaya

cyaya.t.s

ybybmin

≥++

≥++

++

L

M

L

L

(n variabili, m vincoli) (m variabili, n vincoli)

36

Il problema D ha tante variabili quanti sono i vincolidi P e tanti vincoli quante sono le variabili di P.

In forma matriciale:

n

T

x

0xbxA

xcmax)P(

R∈

≥≤

m

T

T

y

0ycyA

ybmin)D(

R∈

≥

≥

LP – La Teoria della Dualità

19

37

Forma simmetrica della dualitàregole di trasformazione

(P) (D)

max ⇒ min vincoli ≥

min ⇒ max vincoli ≤


38

Duale di un Primale con vincoli di uguaglianza:

n

T

x

0xbxA

xcmax)P(

R∈

≥=

m

T

T

y

libere.varycyA

ybmin)D(

R∈

≥


Infatti: bxA = equivale a⎩⎨⎧

−≤−⇒≥

≤

bxAbxAbxA

introducendo 2m variabili duali, u e ve sostituendo y= u - v si ottiene (D)

m

TT

TT

v,u

0v0ucvAuA

)vbub(min

R∈

≥≥≥−

−

20

39

Forma non simmetrica della dualità: regoledi trasformazione

(P) (D)

max ⇒ min vincoli ≥

min ⇒ max vincoli ≤

vincolo = ⇒ var. libera

var. libera ⇒ vincolo =

Le trasformazioni sono reversibili: il duale del duale è il primale.


40

La teoria della Dualità è importante perchè:

le soluzioni di P e D sono legate tra loro

le soluzioni duali hanno un’interpretazione economica utile per l’analisi di sensitività (post-ottimalità);

sulla teoria della dualità sono basati algoritmi, quali il Simplesso Duale e l’Algoritmo Primale-Duale, alternativi alSimplesso (Primale) utili per certe classi di problemi;

può in certi casi essere conveniente risolvere D al posto di P (conviene risolvere il problema con il minor numero di vincoli)


21

41

LP – La Teoria della Dualità: risultati fondamentali

Consideriamo la coppia di problemi (P) e (D)

0xbxA

xcmin)P( T

≥≥

0ycyA

ybmax)D(T

T

≥

≤

1. Teorema (debole) della dualità

Siano x e y soluzioni ammissibili rispettivamente per (P) e (D),allora

ybxc TT ≥

42

Dimostrazione:

y soluzione A y c

x A y x c x

T

T T T

⇒ ≤

≥ ⇒ ≤0 ( )

x soluzione A x b

y A x y b yT T⇒ ≥

≥ ⇒ ≥0 ( )

c x A y x x A y A x y b yT T T T T T T≥ = = ≥( ) ( )


Corollario

Se (P) è illimitato ⇒ (D) non è ammissibile

Se (D) è illimitato ⇒ (P) non è ammissibile

Se (P) ha soluzione ottima finita ⇒ (D) ha soluzione ottima finita

Se (D) ha soluzione ottima finita ⇒ (P) ha soluzione ottima finita

22

43

2. Teorema (forte) della dualitàSe (P) e (D) ammettono soluzione ottima finita, allora per ogni ottimo x* per (P) esiste una soluzione ottima y* per (D) tale che

*T*T ybxc =

Dal Teorema della dualità forte si ricava valore della soluzione ottima di (D) corrispondente alla soluzione ottima di (P)

1TB

T* Bcy −=

⎥⎦

⎤⎢⎣

⎡=

⎥⎥⎦

⎤

⎢⎢⎣

⎡=

−

0bB

xxx

1*N

*B* bBcxcxc 1T

B*B

TB

*T −==

*T1TB ybbBc =−


44

LP – La Teoria della Dualità: risultati fondamentaliOsservazioni• La base B è ottima per (P) e per (D).• Una base B ammissibile per (P) corrisponde ad una

base ammissibile per (D) solo se B è ottima.

0bBXx 1 ≥⇒∈ −

1TB

T Bcy −=

0x0xbxNxB

xcxcmax

NBNB

NTNB

TB

≥≥=+

+(P) (D)

libere.vary

cNy

cBy

ybmin

TN

T

TB

T

T

≥

≥

⎩⎨⎧

≥≥⇒∈ −

−

TN

1TB

TB

1TBT

cN)Bc()bcB)Bc()aYy

23

45

LP – La Teoria della Dualità: risultati fondamentaliOsservazioni• La base B è ottima per (P) e per (D).• Una base B ammissibile per (P) corrisponde ad una

base ammissibile per (D) sono se B è ottima.

⎪⎩

⎪⎨⎧

≥

≥⇒∈ −

−

TN

1TB

TB

1TBT

cN)Bc()b

cB)Bc()aYy

0cNBc)b

cc)a

TN

1TB

TB

TB

≥−

≥

−

(vera sempre)

Rj0caBc jj1T

B ∈≥−−

sono le condizioni di ottimalità su costi ridotti di (P)

46


Osservazioni• Solo in corrispondenza dell’ottimo dalla base B

ammissibile per (P) si ottiene una soluzione ammissibileper (D) (che è anche ottima).

• Ad una generica iterazione del simplesso dalla base di(P) si può costruire il vettore dei moltiplicatori del simplesso che non è soluzione di (D).

Qual è il significato economico del problema duale? Cosa rappresentano le variabili duali?

24

47

LP – La Dualità: interpretazione economica

Consideriamo:• un problema (P)

• la soluzione (non degenere)

• ed una piccola variazione ∆b>0 di b non cambia la baseottima B

0xbxA

xcmax T

≥≤

0x0

bBxxx *

B1

*N

*B* >⎥

⎦

⎤⎢⎣

⎡=

⎥⎥⎦

⎤

⎢⎢⎣

⎡=

−

⎥⎦

⎤⎢⎣

⎡ ∆+=⎥⎥⎦

⎤

⎢⎢⎣

⎡ ∆+=−

0)bb(B

xxxx

1*N

*B

*B*

48


Come cambia il valore dell’obiettivo?

• Varia della variazione delle risorse per il valore della

soluzione ottima duale !

• Allora y* può essere interpretato come il prezzo (valore)

marginale delle risorse (b) poichè indica qual è la

variazione dell’obiettivo (guadagno) conseguente ad

una maggior disponibilità delle risorse.

• I valori duali ottimi sono anche detti prezzi ombra

byxbBcx)bb(BcxT*

01T

B01T

B0 ∆=∆⇒∆=∆⇒∆+= −−

25

49


Lo scarto complementare (complementary slackness)• Consideriamo una coppia (P), (D)

0xbxA

xcmax T

≥≤

slackdi.varm0s.varn0x

bsIxA

≥≥

=+

0ycyA

ybminT

T

≥

≥

surplusdi.varn0v.varm0y

cvIyAT

≥

≥

=−

(P)

(D)

Ad ogni variabile di (D) è associato un vincolo di (P) e quindi lacorrispondente variabile di slack e viceversa.

50


Lo scarto complementare (complementary slackness

3. Teorema della slackness complementareData la coppia di soluzioni x e y rispettivamente ammissibiliper (P) e (D), x e y sono ottime per (P) e (D) se e solo se

dove aj è il vettore riga j-esima di A

ai è il vettore colonna i-esima di A

n,,1i0x)cya(xv

m,,1j0y)xab(ys

iiTiii

jj

jjj

K

K

==⋅−=⋅

==⋅−=⋅

26

51


Lo scarto complementare (complementary slackness• Il teorema stabilisce che

(vincolo duale saturo: vi=0)

(vincolo duale non saturo: vi>0)

(vincolo primale saturo: sj=0)

(vincolo primale non saturo: sj>0)0ybxa.d

bxa0y.c

0xcya.b

cya0x.a

jjj

jj

j

iiTi

iTii

=⇒<

=⇒>

=⇒>

=⇒>

52


Il problema del Product Mix• Stabilire i livelli ottimi di produzione per un insieme di prodotti in

modo da massimizzare il profitto ricavato dalla loro vendita, rispettando la disponibilità limitata delle risorse necessarie alla produzione

0xbxA

xcmax T

≥≤

(P) xi livello di produzione del prodotto i-moci profitto per unità di prodotto i-mobj disponibilità della risorsa j-maaij quantità di risorsa j-ma necessaria per

produrre un’unità di prodotto i-mo

j-mo vincolo di (P)

jj bxa ≤ il consumo totale di risorsa j-ma non

supera la sua disponibilità massima

27

53


Il duale del problema del Product Mix• Avendo scelto di vendere le risorse produttive, determinare il loro

prezzo minimo, imponendo che la loro vendita sia almeno tanto conveniente che vendere i beni prodotti con le risorse

(D)

i-mo vincolo di (D) il valore di una unità di prodotto i-mo, calcolato considerando le risorse necessarie per produrlo e il loro prezzo minimo, deve superare il prezzo unitario di vendita del prodotto stesso

0ycyA

ybminT

T

≥

≥

yj prezzo minimo a cui vendere la j-ma risorsa ci profitto per unità di prodotto i-mobj disponibilità della risorsa j-maaij quantità di risorsa j-ma necessaria per

produrre un’unità di prodotto i-mo

iTi cya ≥

54

LP – La Dualità: interpretazione economicaInterpretazione economica della slackness complementare• Primale:

Il valore delle risorse (il valore ottimo delle variabili duali) è positivo solamente quando le risorse sono utilizzate completamente (risorse scarse), ovvero quando sono nulle le variabili di slack associate ai vincoli corrispondenti

• Duale

Il livello di produzione dei prodotti (il valore ottimo delle variabili primali) è positivo solamente quando il profitto unitario che si ricava dalla loro vendità è pari a quanto si ricaverebbe vendendo le risorse necessarie alla produzione al loro prezzo minimo (condizione di bilancio economico), ovvero quando il surplus di guadagno unitario della vendita delle risorse rispetto la produzione dei prodotti è nullo

0ysxabs jjj

jj =⇒−=

0vxcyav iiiTii =⇒−=

28

55


Il problema della Dieta (blending)• Determinare la dieta bilanciata più economica avendo la possibilità

di acquistare n diversi cibi. Una dieta è bilanciata se soddisfa i livelliminimi giornalieri di calorie e di altri elementi nutrizionali (e.g.,proteine, calcio, ferro, vitamine). Quindi determinare la quantità che deve essere acquistata per ciascun cibo, minimizzando la spesa complessiva e soddisfacendo i livelli nutrizionali minimi

(P)

j-mo vincolo di (P)

jj bxa ≥

0xbxA

xcmin T

≥≥

xi quantità di cibo i-mo da acquistareci costo per unità di cibo i-mobj livello minimo per l’elemento nutriz. j-moaij quantità di elemento nutrizionale j-mo

presente in una unità di cibo i-mo

la quantità complessiva dell’elemento nutriz. j-ma fornita dai cibi acquistati deve essere almeno pari al relativo livello minimo.

56


Il duale del problema della Dieta• Volendo acquistare singolarmente gli m elementi nutrizionali (e.g.,

in pillole) per ottenere la dieta bilanciata, determinare il massimo prezzo per i singoli elementi in modo che il loro acquisto sia competitivo rispetto quello dei cibi contenenti tali elementi

(D)

i-mo vincolo di (D)

0ycyA

ybmaxT

T

≥

≤

yj prezzo massimo a cui acquistare il j-mo elemento nutriz.

ci costo per unità di cibo i-mobj livello minimo per l’elemento nutriz. j-moaij quantità di elemento nutriz. j-mo presente

in una unità di cibo i-mo

iTi cya ≤

il prezzo unitario del cibo i-mo “sintetico” (il prezzo della quantità di elementi nutriz.forniti da una unità di cibo i-imo) deve non superare il prezzo reale del cibo i-mo

29

57

LP – L’analisi di post-ottimalitàConsideriamo un problema di PL con soluzione ottima x* e base ottima associata B, determinare con quali condizionipossono variare certi coefficienti del problema lasciando invariata la base ottima.

Considereremo tre casi:a) variazione di un coefficiente della funzione obiettivo associato ad

una variabile fuori base (cN)

b) variazione di un coefficiente della funzione obiettivo associato aduna variabile in base (cB)

c) variazione del termine noto di un vincolo (b)

0xbxA

xcmax T

≥=

58

LP – L’analisi di post-ottimalitàCasi (a) e (b): variazione dei prezzi di vendita dei prodotti• (a) – grafico nel piano dei prodotti

all’ottimo x2 è fuori base

x1

1 2 3 4 5 6

1

2

3

AE

D

B C

x2

il coeff.angolare dell’obiettivo è21

cc−

c1 diminuisce

c2 aumenta

E diventa sol. ottima ⇒ x2 entra in base

30

59

LP – L’analisi di post-ottimalitàCasi (a) e (b): variazione dei prezzi di vendita dei prodotti• (a) – analitico

Sia ck, k∈R, il coefficiente che viene variato. Il coefficiente dicosto ridotto associato alla k-esima variabile fuori base èpositivo poichè la base è ottima e variando ck varia rk

Perchè la soluzione corrente resti ottima il nuovo valore di rkdeve rimanere positivo (altrimenti la variabile fuori baseassociata sarebbe candidata ad entrare in base)

0caycaBcr kk*

kk1T

BkT

≥−=−= −

)c(ayr̂cc kk*

kkkT

δ+−=⇒δ+←

⇒−≤δ⇒≥δ+−⇒≥ kk*

kk*

k cay0)c(ay0r̂TT

kr≤δ

60

LP – L’analisi di post-ottimalitàCasi (a) e (b): variazione dei prezzi di vendita dei prodotti• (b) – grafico nel piano dei prodotti

all’ottimo x2 è in base

x1

1 2 3 4 5 6

1

2

3

AE

D

B C

x2

il coeff.angolare dell’obiettivo è21

cc−

c1 diminuisce

c2 aumenta

c1aumenta

c2 diminuisce

C diventa sol. ottima ⇒ la base cambia

D diventa sol. ottima⇒ x2 esce di base

31

61

LP – L’analisi di post-ottimalitàCasi (a) e (b): variazione dei prezzi di vendita dei prodotti• (b) – analitico

Sia cBi, i=1,...,m , il coefficiente che viene variato. La variazione modifica tutti gli rk delle var. fuori base che devono restare positivi perché la base non cambi

• Come si effettuano i casi (a) e (b) utilizzando il tableau ottimo?

RkcaBcr kk1T

Bk ∈−= −

iBBBB ecccc ii δ+←⇒δ+←

)moi(

0

1

0

ei −

⎥⎥⎥⎥⎥⎥

⎦

⎤

⎢⎢⎢⎢⎢⎢

⎣

⎡

=

M

M

k1T

ikk1T

Bk aBecaBcr̂ −− δ+−= i11Ti )B(Be −− =

k0a)B(rr̂ ki1

kk ∀≥δ+= −

62

LP – L’analisi di post-ottimalitàCaso (c): variazione della disponibilità delle risorse• Due possibilità

(1)aumentare le risorse scarse per migliorare l’obiettivo

(2) ridurre le risorse abbondanti lasciando invariato l’obiettivo

• (c) – grafico nel piano dei prodotti

x1

1 2 3 4 5 6

1

2

3(2) x4

(3) x5

AE

D

B C

x2

(1) x3

b2 (scarsa) aumenta

D’L

32

63

LP – L’analisi di post-ottimalitàCaso (c): variazione della disponibilità delle risorse• Due possibilità

(1)aumentare le risorse scarse per migliorare l’obiettivo

(2) ridurre le risorse abbondanti lasciando invariato l’obiettivo

• (c) – grafico nel piano dei prodotti

x1

1 2 3 4 5 6

1

2

3(2) x4

(3) x5

AE

D

B C

x2

(1) x3

b3 (abb.) diminuisce

64

LP – L’analisi di post-ottimalitàCaso (c): variazione della disponibilità delle risorse• (c) – analitico

Sia bi, i=1,...,m , il termine noto del i-mo vincolo che viene variatoA causa di tale variazione si modificano i valori delle variabili di base

• Come si effettua questa analisi usando il tableau ottimo (caso particolare)?

i11

i1

Bii )B(bB)eb(Bx̂bb −−− δ+=δ+=⇒δ+←

i1

i1 )B(eB −− = colonna i-ma di B-1

0)B(xx̂ i1

BB ≥δ+= −

i1

BB )B(xx̂ −δ+=⇒

33

65

LP – L’analisi di post-ottimalitàUn esempio

0x,0x2x

8xx26x2x

x2x3xmax

21

2

21

21

210

≥≥

≤

≤+≤+

+=

5,...,1i0x2xx8xxx26xx2x

x2x3xmax

i

52

421

321

210

=≥

=+

=++

=++

+=

210010x801012x600121x000023x

xxxxx

5

4

3

0

54321−−

3/213/13/200x3/1003/23/101x3/403/13/210x3/3803/43/100x

xxxxx

5

1

2

0

54321

−−

−

il tableau iniziale il tableau ottimo

66

LP – L’analisi di post-ottimalitàUn esempio

• in questo caso i coeff. ck che moltiplicano le var. fuori base sono tutti nulli, e le corrispondenti colonne ak della matrice N sono ivettori ek, i coeff. di costo ridotto nel tableau ottimo forniscono direttamente il valore dell’ottimo duale

3/213/13/200x3/1003/23/101x3/403/13/210x3/3803/43/100x

xxxxx

5

1

2

0

54321

−−

−B-1

⎥⎥⎥

⎦

⎤

⎢⎢⎢

⎣

⎡=

101021012

B

*kk

T*k

1TBkk

1TBk yeyeBccaBcr ===−= −−

[ ]03431yT* =⇒ (... perché y3

*=0 ?)

34

67

LP – L’analisi di post-ottimalitàUn esempio• Caso (a) – coeff. dell’obiettivo di una var. fuori base

variazione di c3: (inizialmente c3=0 - slack) c3 ← c3+ δ


Interpretazione economica?

3/213/13/200x3/1003/23/101x3/403/13/210x3/3803/43/100x

xxxxx

5120

54321

−−

−

31c

31r 33 ≤≤∞−⇒≤δ⇒≤δ

34c

34r 44 ≤≤∞−⇒≤δ⇒≤δ

68

LP – L’analisi di post-ottimalitàUn esempio• Caso (b) – coeff. dell’obiettivo di una var. in base

variazione di c1: (inizialmente c1=3) c1 ← c1+ δ


3/213/13/200x3/1003/23/101x3/403/13/210x3/3803/43/100x

xxxxx

5

1

2

0

54321

−−

−

20r̂

10r̂

32

344

31

313

−≥δ⇒≥δ+=

≤δ⇒≥δ−=4c1 1 ≤≤⇒

35

69


variazione di c2: (inizialmente c2=2) c2 ← c2+ δ


3/213/13/200x3/1003/23/101x3/403/13/210x3/3803/43/100x

xxxxx

5

1

2

0

54321

−−

−

40r̂

0r̂

31

344

21

32

313

≤δ⇒≥δ−=

−≥δ⇒≥δ+=6c

23

2 ≤≤⇒

70




3/213/13/200x3/1003/23/101x3/403/13/210x3/3803/43/100x

xxxxx

5

1

2

0

54321

−−

−

40r̂

0r̂

31

344

21

32

313

−≥δ⇒≥δ+=

≤δ⇒≥δ−=

21c4 5 ≤≤−⇒

36

71

LP – L’analisi di post-ottimalitàUn esempio• Caso (c) – variazione della disponibilità delle risorse

Due possibilità:c.1) aumentare la disponibilità delle risorse scarse (b1 e b2)

c.2) diminuire l’eccesso di risorse abbondanti (b3)

• Caso (c.1)variazione di b1: (inizialmente b1 =6) b1 ← b1 + δ


3/213/13/200x3/1003/23/101x3/403/13/210x3/3803/43/100x

xxxxx

5

1

2

0

54321

−−

−10x̂

100x̂

20x̂

32

325

31

3101

32

342

≤δ⇒≥δ−=

≤δ⇒≥δ−=

−≥δ⇒≥δ+=

7b4 1 ≤≤⇒(NB: possibile perché il tableau contiene B-1)

72






3/213/13/200x3/1003/23/101x3/403/13/210x3/3803/43/100x

xxxxx

5

1

2

0

54321

−−

−

(NB: possibile perché il tableau contiene B-1)

20x̂

50x̂

40x̂

31

325

32

3101

31

342

−≥δ⇒≥δ+=

−≥δ⇒≥δ+=

≤δ⇒≥δ−=

12b6 2 ≤≤⇒

37

73






3/213/13/200x3/1003/23/101x3/403/13/210x3/3803/43/100x

xxxxx

5

1

2

0

54321

−−

−

(NB: possibile perché il tableau contiene B-1)

34b3 ≥⇒

320

32x̂5 −≥δ⇒≥δ+=

74

LP – L’analisi di post-ottimalitàUn esempio – Il valore delle risorse• Per i vincoli sul consumo delle risorse si ha

• Conviene aumentare le risorse scarse • Marginalmente la f.ob. cresce del valore delle risorse (il valore

delle var. duali ottime yj*)

• Il valore delle risorse abbondanti è nullo (yj*=0)• Conviene aumentare per prima la risorsa scarsa a cui è associato

il valore maggiore

Vincolo saturo Risorsa scarsa(slack nulla) (var.duale ottima positiva)

Vincolo non saturo Risorsa abbondante(slack positiva) (var.duale ottima nulla)

38

75

LP – L’analisi di post-ottimalitàUn esempio – Il valore delle risorse• Nell’esempio i valori duali si possono leggere direttamente sul

tableau ottimoquesto è caso particolare, ... perché?

3/213/13/200x3/1003/23/101x3/403/13/210x3/3803/43/100x

xxxxx

5

1

2

0

54321

−−

−

76

LP – L’analisi di post-ottimalità

Osservazioni finali• Se si diminuisce (entro i limiti calcolati) una risorsa

abbondante la soluzione non cambia

• Cosa succede se invece si scoprisse di avere una disponibilità inferiore di una risorsa scarsa?

• Quali valutazioni possiamo fare nel caso di:introduzione di un nuovo prodotto

variazione della tecnologia

...?

• L’analisi di post-ottimalità è un processo locale (la sua validità è limitata ad un intorno della soluzione ottima)

39

77L’analisi del caso lineare nel piano delle risorse

L’analisi si basa sulla proiezione sul piano delle risorse della funzione di produzione

Risorse Prodotti

Tecnologia

Processo di

Trasformazione

Funzione di Produzione (FP)Date r risorse e x prodotti, la FP è il luogo dei punti di trasformazione efficiente, ossia dei punti corrispondenti alle massima produzione a parità di risorse


Un esempio monodimensione di FP x = x(r)

Non ammissibile

r

x

Ammissibile

x*

r*

40


Il problema

Ipotesi• Le variabili xj: quantità di uno stesso prodotto prodotte con

tecnologie diverse (processi produttivi)• Coeff. aij: differente uso delle risorse dei diversi processi produttivi• Coeff. cj: guadagni associati ai processi produttivi (ricavi-costi)• Analisi rispetto 2 risorse (possibile l’analisi grafica)

Due problemi• Massimizzare la produzione • Massimizzare il guadagno

0xbxA

xcmax T

≥≤


La funzione di produzione dei prodotti/processi• Retta nello spazio (e.g., per il prodotto/processo 1)

• Identifica la combinazione di risorse che permette la realizzazione del processo

• Un esempio con Excel ...

r1

r2

x1

a11

a21

1

⎪⎩

⎪⎨

⎧

=

=

=

txtar

tar

1

212

111

41


La funzione di produzione dei processi• La proiezione nel piano delle risorse di più processi

• Processi efficienti e processi dominati

r1

r2 x1

a11

a21

1

x2

x3

x41

1

1

a22

a12

r1

r2

a11

a21

x1

x2

1

1a22

a12

regione dominata da x1


Gli isoquanti• La pendenza delle rette è a2i/a1i• I punti sulle rette rappresentano i diversi livelli di produzione• Unendo punti sulle rette a parità di produzione si ottengono dei

segmenti che identificano la produzione combinata

• Isoquanti = luogo dei punti a produzione costante⇒ la spezzata che unisce i punti a pari produzione

r1

r2x1

1 x2

x3

1

1

p

a

b

⎪⎩

⎪⎨

⎧

=

=

=

txtar

tar

1

212111

⎪⎩

⎪⎨

⎧

=

=

=

vxvar

var

2

222121

⎪⎩

⎪⎨

⎧

+=

+=

+=

vtxvatar

vatar

2221212111

42


Gli isoquanti• Eliminando t e v si ottiene il segmento dell’isoquanto relativo alla

combinazione di x1 e x2

• La curva definisce l’uso delle risorse a produzione fissata• Gli isoquanti sono formati solo dai segmenti che identificano una

combinazione efficienti di coppie di processi

r1

r2x1

1 x2

x31

1

11121112122212 aa

xar)aa(xar−

−−+=

⎪⎩

⎪⎨

⎧

+=

+=

+=

vtxvatar

vatar

2221212111

x1-x3 è dominato da x1-x2 e x2-x3


Gli isoquanti• Se si varia il livello di produzione si ottiene una spezzata parallela

r1

r2

x1

1 x2

x31

1

43


Gli isoquanti• Nelle zone A e B la produzione avviene con spreco di risorse

• Le risorse in R:non permettono la produzione x1 di Ppermettono la produzione x1 di Qcon sprecopermettono la produzione x2 di Ncon spreco

r1

r2

x1

1 x2

x31

1 B

A

r1

r2

x1

Q

x2P

R

N


Gli isoquanti• Nelle zone oltre gli ultimi processi divengono paralleli agli assi

r1

r2

x1

1x2

x31

1

44


Il problema della massimizzazione della produzione• Si considera la disponibilità delle risorse• Si identifica l’isoquanto ammissibile associato alla maggior

produzione

Quali sono i processi prodotti?

r1

r2

x1

ottimox2

x3

b2

b1


Il problema della massimizzazione del guadagno• Si devono costruire le curve di isoguadagno:

ai punti sulle le rette dei processi vengono associati i valori di guadagno (scalando con i coeff. cj)si uniscono i punti a pari guadagno identificando una diversa spezzata

r1

r2

x1

x2

x3

1

C1

1

1 isoquanto

isoguadagno

C2

C3

⎪⎩

⎪⎨

⎧

=

=

=

=

tcGtar

tar)x(guad

11

212111

1

45


Il problema della massimizzazione del guadagno• Le curve di isoguadagno devono risultare convesse

esempio: x2 non verrà mai prodotto perchè a parità di guadagno consuma più di x1 e x3

r1

r2

x1

x2

x3

G=1

G=1

G=1

dominata

dominata


Il problema della massimizzazione del guadagno• La produzione a guadagno massimo

• Cosa accade se si considera un problema di blending (e.g., la dieta)? ... un esempio con Excel

r1

r2

x1

x2

x3

ottimob2

b1

46


Il Simplesso nel piano delle risorse• Consideriamo il problema di Product-Mix con 2 risorse

• Le xj rappresentano diversi processi con cui produrre un prodotto• I guadagni unitari: cj = p – kj dove

p = prezzo unitario del prodottokj costo delle risorse necessarie a produrre un’unità di prodotto con il processo j-mo

pi costo unitario della risorsa i-ma

• La soluzione di base iniziale ⇒ produzione nulla, slack in base

0xbxA

xcmax T

≥≤

∑=

⋅=m

1iiijj pak


Il Simplesso nel piano delle risorse• I passi del Simplesso

Chi entra e chi esce di base ad ogni passo? Perchè?

r1

r2

x1

x3

x2Ottimo

b2

b1A(soluzione iniziale)

B

ipotesi c1>c2>c3

C

isoguadagno

47


Il Simplesso nel piano delle risorse• I passi del Simplesso

Il ragionamento deve considerare le variabili di slack delle 2 risorse.

• Esercizi...

ipotesi c3>c2>c1

ipotesi c2>c1>c3

r1

r2 x1x3

x2

b2

b1A

r1

r2x1 x3

x2

b2

b1A

94La pianificazione della produzione: modelli lineari

Production Planning• definire i livelli di produzione su un orizzonte temporale di N periodi• nei diversi periodi può variare:

la capacità produttivai costi di produzione, i costi di magazzino, i costi di set-upla domanda (con e senza backlogging)

t1 t2 tNz0magazzino

iniziale

zNmagazzino finale

produzione periodo 1 x1

d1

domanda periodo 1

z1

48


Production Planning• Il modello a singolo prodotto:

xi produzione nel periodo izi magazzino nel periodo i (fine periodo)pi costo di produzione nel periodo ihi costo di inventory nel periodo ici capacità produttiva nel periodo idi domanda nel periodo iM0 magazzino iniziale

( )

N,...,1izxN,...,1i0z0x

MzN,...,1icxN,...,1idzzx

zhxpmin

ii

ii

00

ii

ii1ii

N

1iiiii

=∈∈

=≥≥

=

=≤

==−+

+

−

=∑

RR

equazioni di continuità (senza backlogging)


Production Planning• Il modello multi-prodotto:

con t si indica il periodo (t=1,...,N) e con i il prodotto (i=1,...,K)i costi, la domanda sono riferiti a prodotto e periodola capacità è complessiva del periodo (ipotesi)sit set-up del prodotto i nel periodo t (costo fisso che si produce i in t)yit var. binaria: se produrre i nel periodo tDit produzione massima del periodo t (≈ big-M)

( )

t,iBy,z,xt,i0z,0x

iMziMz

i,tyDx

tcx

i,tdzzx

yszhxpmin

ititit

itit

iTiT

0i0i

ititit

tK

1iit

itit1t,iit

K

1i

N

1titititititit

∀∀∈∈∈

∀∀≥≥

∀=

∀=

∀∀≤

∀≤

∀∀=−+

++

∑

∑ ∑

=

−

= =

RR

49

97

LP – I problemi a numeri interi e mistiMolti problemi decisionali richiedono l’uso di variabili intere per rappresentare alternative discrete

Questo tipo di problemi si chiamano combinatorici

In qualche caso può essere ragionevole “rilassare” il problema considerando le variabili come reali

Attraverso l’uso di variabili binarie (0-1) è possibile modellare condizioni logiche• XA=1 si verifica l’evento A (e.g., compro il prodotto, affitto una

macchina, passo per la strada A, ...)

• XA=0 non si verifica l’evento A

• Esempi: scheduling, location problems, routing ...

98

LP – I problemi a numeri interi e mistiEsempi di formulazioni con variabili binarie• Knapsack Problem

n possibili progetti possibili da realizzareb budget massimo disponibileaj investimento necessario al progetto jcj guadagno ricavato dal progetto ji progetti non possono essere realizzati parzialmente (o tutto o nulla)problema: cosa finanziare per massimizzare il guadagno?

Knapsack binario

(xj=1 finanzio il progetto j)

{ } n,...,1j1,0x

bxa

xcmax

j

n

1jjj

n

1jjj

=∀=∈

≤∑

∑

=

=

B

50

99

LP – I problemi a numeri interi e mistiEsempi di formulazioni con variabili binarie• Matching Problem (assegnazione)

m attività da assegnare ad n processori (macchine, persone,...)ogni processore può eseguire una sola attivitàl’attività non è interrompibilecij costo dell’assegnazione di i a jproblema: assegnare tutte le attività a costo minimo

Matching binario

(xij=1 assegno i a j)

{ } n,...,1jm,...,1i1,0x

n,...,1j1x

m,...,1i1x

xcmin

ji

m

1iij

n

1jij

n

1jijij

m

1i

=∀=∀=∈

=∀≤

=∀=

∑

∑

∑∑

=

=

==

B

100

LP – I problemi a numeri interi e mistiLa soluzione dei problemi a numeri interi (Integer Programming, IP)• I problemi IP e MIP sono generalmente difficili (NP-hard)

• In alcuni (pochi) casi la soluzione “rilassata” è intera

• In generale si possono usare tre tipi di metodi di soluzione:

1. Metodi basati su una enumerazione implicita delle soluzioni (Branch and Bound Methods)

2. Metodi basati sull’uso di “piani di taglio” (Cutting Planes Methods)

3. Metodi specifici per particolari classi di problemi

Metodi e Modelli di Programmazione Lineare · 1 Metodi e Modelli di Programmazione Lineare Massimo...

Documents

Transcript of Metodi e Modelli di Programmazione Lineare · 1 Metodi e Modelli di Programmazione Lineare Massimo...