Ricerca operativa per le produzioni industriali - Appunti

TABELLA DEL SIMPLESSO

In questa tabella, nella prima iterazione, si riportano solo i coefficienti delle variabili, e

nella riga “0” si trascrivono le variabili della funzione obiettivo (max z = 3 x + 5 x ).

1 2

z - 3 x - 5 x = 0

1 2

x + r = 4

1 1

x + r = 6

2 2

3 x + 2 x + r = 18

1 2 3 Rappor Op.ele

z x x r r r b

1 2 1 2 3 to m.

0 1 -3 -5 0 0 0 0 / + 5 * II

I = r 0 1 0 1 0 0 4 /

1

II = r 0 0 1* 0 1 0 6 6

2

III = r 0 3 2 0 0 1 18 18/2 -2 *II

3

Riga Colonna Vettore

cardine cardine fondament

*Indica l’elemento cardine e la scelta della variabile entrante, tale scelta è fatta in

ale

funzione del valore delle variabile della funzione obiettivo (**). x è nulla e quindi la

2

farò entrare nella base. Come la variabile entrante si deve scegliere anche la variabile

uscente: si calcola il rapporto tra il termine noto b e il coefficiente della variabile

entrante; il rapporto che ha il valore minimo tra tutti, indica quale è la variabile

uscente. In questo esempio il rapporto minimo è 6 e quindi la variabile uscente sarà r .

2

x e r sono dette rispettivamente colonna e riga cardine; l’intersezione tra la riga e la

2 2

colonna cardine genera l’elemento cardine che dovrà valere sempre 1. L’obiettivo,

quindi, è quello di trasformare la colonna cardine nel vettore fondamentale che ha il

valore 1 in corrispondenza della riga cardine.

** Se la funzione obiettivo è espressa come z = 3 x + 5 x come variabile entrante si

1 2

considera il coefficiente più grande; se invece la funzione obiettivo è in termini di z - 3

x - 5 x = 0 come variabile entrante si considera il coefficiente più piccolo. La

1 2

soluzione data dalla prima iterazione è: (x , x , r , r , r ) = (0, 0, 4, 6, 18) e z = 0.

1 2 1 2 3

Passiamo alla seconda iterazione: Rappor Op.ele

z x x r r r b

1 2 1 2 3 to m.

+ 3 *

0 1 -3 0 0 5 0 30 / III

I = r 0 1 0 1 0 0 4 4 -III

1

II = x 0 0 1 0 1 0 6 /

2

III = r 0 3 0 0 -2 1 6 6/3 *1/3

3 Dall’oper. element:

2-2*II = 0

r e r resteranno basiche e quindi i loro vettori fondamentali rimarranno invariati, ma

1 3

cambieranno i loro valori, così come la riga cardine.

x e r sono diventate nulle.

1 2

La terza riga della seconda iterazione si ottiene applicando l’operazione elementare

alla terza riga della prima iterazione. Stesso procedimento si applica alla riga 0.

Ovviamente le operazioni che si applicano ad un elemento devono essere eseguite

anche tutti gli altri elementi della stessa riga.

La funzione obiettivo, a causa delle varie operazioni elementari, nella seconda

iterazione è diventata z - 3 x + 5 r = 30.

1 2

x è la variabile entrante perché ha il coefficiente minore e quindi essa è la colonna

1

cardine; la variabile uscente è la riga r ovvero quella che ha il rapporto minimo, e che

3

quindi nell’iterazione successiva cambierà.

Quando si prosegue con la tabella successiva, come nella seconda, si devono riportare

i valori delle colonne che non cambieranno poiché rimangono associate allo stesso

vettore fondamentale (in questo caso sono x e r ), inoltre z non cambierà mai.

2 1

Le iterazioni continuano fino a quando nella riga 0 tutti i valori sono positivi. Nella

seconda iterazione nella riga 0 vi è il valore -3 con z = 30 che quindi non sarà la

soluzione ottima.

Si procede allora con la terza iterazione: Rappor Op.ele

z x x r r r b

1 2 1 2 3 to m.

0 1 0 0 0 3 1 36

I = r 0 0 0 1 2/3 -1/3 2

1

II = x 0 0 1 0 1 0 6

2

III = x 0 1 0 0 -2/3 1/3 2 -->III *1/3

1 (precedente)

r2 e r3 sono le variabili non basiche perché nulle (lo determino perché nella primissima

colonna non compaiono dopo tutte le iterazioni). In questa iterazione nella riga 0 non

ci sono più valori negativi per cui la soluzione unica ottimale sarà (x , x , r , r , r )* =

1 2 1 2 3

(2, 6, 2, 0, 0) e z* = 36. Quando invece, l’insieme ammissibile X è vuoto oppure z è

superiormente illimitata, tale metodo non ha soluzioni.

Il metodo del simplesso fallisce quando ci sono vertici degeneri, in tal caso si viene a

creare il fenomeno del CICLAGGIO: le iterazioni fanno rimanere nello stesso vertice

fino a tornare ad una base già considerata. Il vertice degenere non viene più

abbandonato e quindi si ottiene sempre la stessa sequenza di soluzioni non ottimale.

Questo problema si verifica raramente, e comunque si può risolvere con delle

modifiche.

Esempio di vertice degenere:

max z = 3 x + 5 x

1 2

x ≤ 4

1

x ≤ 6

2

3 x + 2 x ≤ 12  x ≤ 6 – 1/2 x

1 2 2 1

x , x ≥ 0

1 2

Risolvendo l’esercizio col metodo del simplesso, la prima soluzione sarà data dal

Il gradiente di z è (3, 5);

vertice posto all’origine, poiché si tratta di un problema normale; la seconda e la terza

iterazione daranno lo stesso risultato e quindi ci si sposterà sino al vertice A; nella

A

quarta iterazione ci si sposterà sul vertice B. è il vertice degenere

perché in esso sono

Quindi, in conclusione, i passaggi sono: attivi i vincoli II, III e il

vincolo di non

z x

z = negatività x = 0.

max z = cx 1

0 1 -c

0

c.v. Ax ≤ b I

x ≥ 0 … 0 A

Forma per il simplesso: m

z – cx = 0

Ax + Ir = b

x, r ≥ 0

1. Si individua una soluzione basica ammissibile (perché questa indica il vertice e

perché ha almeno due variabili nulle); la prima soluzione sarà l’ origine, in

quanto il problema è normale.

2. Verificare l’eventuale ottimalità della soluzione, la quale si ha quando non c’è

nessun coefficiente negativo nella riga zero. Se si ha l’ottimalità, si termina,

altrimenti si deve scegliere la variabile entrante (quindi la colonna cardine) con

il criterio del massimo incremento di z.

3. Determinare la variabile uscente (quindi la riga cardine) con il criterio del

minimo rapporto b/a (con a > 0) e con i variabile entrante.

ji ji

4. Determinare la nuova soluzione basica ammissibile e si torna al punto 2.

La soluzione potrà essere:

• UNICA --> vertice;

• INFINITE --> spigolo, eventualmente “infinito”;

• NON ESISTE --> quando X = 0 e il problema non è normale, oppure quando z è

superiormente illimitato.

Esempio sulla NON ESISTENZA DELLA SOLUZIONE:

max z = 3 x + 5 x Forma aumentata --> z – 3x – 5x = 0

1 2 1 2

x ≤ 4 x + r = 4

1 1 1

x - x ≤ 2 x – x + r = 2

1 2 1 2 2

x , x ≥ 0 x , x , r , r ≥ 0

1 2 1 2 1 2

z x x r r b rapporti

1 2 1 2

z = 0 1 -3 -5 0 0 0

r = I 0 1 0 1 0 4 4/0 !

Non esiste punto di

1

r =II 0 1 -1 0 1 2 2/-1 !

massimo e quindi z è

2 illimitato

superiormente.

Soluzione corrente (x , x , r , r ) = (0, 0, 4, 2) e z = 0. x è la colonna cardine perché ha

1 2 1 2 2

il coefficiente più piccolo; soprattutto non posso considerare i rapporti in quanto hanno

il denominatore negativo. Quindi si ha la variabile entrante ma non quella uscente,

determinata dai rapporti che però non si possono tenere in considerazione. Ciò prova

che non esistono soluzioni quando z è illimitato superiormente.

LA DUALITA’

max z = cx DUALE --> min w = b’y con --> c = b’

c.v. Ax ≤ b c.v. A’y ≥c’ b = c’

x ≥ 0 y ≥ 0 A = A’ trasposta di A

Primale: Ax ≤ c ---> Ax + r ≤

PROBLEMA PRIMALE PROBLEMA DUALE

c r ≥ 0

min w = b’y

c.v. A’y – s ≥ c’ Duale: A’y ≥ c’

y ≥ 0, s ≥ 0 ---> A’y – s ≥ c’

FORMA AUMENTATA DEL DUALE

Trasformazioni da effettuare:

max --> min;

Tn,m

A --> A il numero di vincoli viene scambiato col numero delle variabili;

m,n

b, c --> scambiano i loro ruoli;

c.v. “≤” --> c.v. “≥” eccetto i vincoli non negatività che rimangono uguali.

1 1

-1 1

1 -1

1 1

Esempio guida:

max z = 2 x - 3 x min w = 4 y – 6 y

1 2 1 2

T

c.v. x + x ≤ 4 A= c.v. y – y ≥ 2 A =

1 2 1 2

-x + x ≤ - 6 y + y ≥ - 3

1 2 1 2

x , x ≥ 0 y , y ≥ 0

1 2 1 2

PROPRIETA’ DEL DUALE

D D

1) (p ) = p ---> si considera il duale, se ne fa nuovamente il duale e si ottiene

nuovamente il problema di partenza p;

2) (x*, r*) soluzione ottima di p D

(y*, s*) soluzione ottima di p

y*r* + x*s* = 0  CONDIZIONE DI COMPLEMENTARIETA’

3) (x*, r*) soluzione ottima di p D

(y*, s*) soluzione ottima di p

Uno viene massimizzato, l’altro viene minimizzato sino al raggiungimento dello

stesso punto

z* = w*  TEOREMA DELLA DUALITA’ z =

z w

w

D

4) Dato un problema e il suo duale p e p se uno dei due è positivo, l’altro si deve

annullare:

- Se hanno entrambi soluzione ottima con lo stesso valore;

- Nessuno dei due ammette soluzione ammissibile:

- Uno dei due non ha soluzione ammissibile, l’altro è illimitato.

5) (x, r) soluzione ammissibile di p D

(y, s) soluzione ammissibile di p

TESI: z ≤ w e quindi la soluzione del primale p è inferiore alla soluzione del duale

D

p .

DIMOSTRAZIONE:

- considero i vincoli di p: Ax + r = b

- premoltiplico(*) per y’: y’Ax + y’r = y’b = w

- Premoltiplico anche i vincoli del duale: x’A’y – x’s = x’c’ = z

- w – z = y’r + x’s ≥ 0 z ≤ w

(*) premoltiplicare vuol dire moltiplicare da sinistra; con le matrici si deve sempre

precisare si si moltiplica da destra o da sinistra perché esse non godono della

proprietà commutativa e quindi è giusto precisare e fare una distinzione.

Esempio: 1 0

=

1 -2

r 3

x

1 0

+ 1

x r

2 Premoltiplicazione:

x + r = 3

1 1

x - 2x + r 0

1 2 2

y y

1 2

y y

1 2

y (x + r ) + y (x – x + r ) = 3y

1 1 1 2 1 2 2 1

INTERPRETAZIONE ECONOMICA DEL DUALE (problema della dieta)

x = unità di pizza alla nutella

1

x = unità di crepes al mascarpone

2

La fun. Obiettivo: minimizzare il costo di z

Cioccolata Zucchero Formaggio Prezzo

x 3 2 2 50

1

x 0 4 5 80

2

Requisiti 6 10 8

Min z = 50 x + 80 x

1 2

3 0

2 4

2 5

c.v. 3 x ≥ 6 A=

1 PROBLEMA

2 x + 4 x ≥ 10

1 2

2 x + 5 x ≥ 8 PRIMALE

1 2