Ricerca operativa

B F

base e fuori base fatto per le variabili anche ai coefficienti della funzione obiettivo)

z = c x = [c , c ] [ ] (= c x + c x ) = c ( B b - B Fx ) + c x =

T TB TF TB TF TB -1 -1 TF

B F F F

= c B b + (c - c B F ) x = c B b + c ̅ x (x =0) =>

T -1 T TB -1 TB -1 T

F F F

B F F

z = c B b = c x

TB -1 TB B

Quando questa soluzione è ottima?

c ̅ = c – c B A : questi coefficienti c ̅ sono detti COSTI RIDOTTI.

T T TB -1

Posso estendere i costi ridotti a tutta la matrice A perché si potrebbe riscrivere:

= [c , c ] = c B [B F] (B F = A)

c ̅ T TB TF TB -1

Riprendendo la z di prima vediamo che il valore della funzione obiettivo è il valore

che è dato dalla costante + il contributo dato dalle variabili fuori base moltiplicate per

i costi ridotti

Quando una variabile fuori base entra in soluzione, cioè cresce di valore, viene

moltiplicata per il suo corrispettivo costo ridotto e fa cambiare il valore totale della

funzione obiettivo.

La soluzione attuale che avremo è ottima se scopriamo che tutti i costi ridotti (coeff)

hanno un valore negativo o nullo (per la massimizzazione)

TEOREMA: una soluzione di base ammissibile in un problema di P.L.C. in forma di

massimo è ottima se i costi ridotti sono tutti non positivi (≤ 0)

(in un problema di minimo se i costi ridotti sono ≥ 0)

Ora c’è da capire che colonna far uscire dalla soluzione: chiamiamo

A(segnato)= B A, F(segn)= B F, b(segn)= B b

-1 -1 -1

la soluzione di base: x = B b - B F = b(segn) – F(segn)

-1 -1

b xF xF

Identifichiamo le colonne di base x = [x , … , x ]

T

B [1] [m]

se x (colonna h) entra nella base allora il sistema verrà riscritto

h

x[1] = b(segn)1 − a(segn)1hxh ≥ 0 ()1ℎℎ ≤ ()1

[] = () − ()ℎℎ ≥ 0 ()ℎℎ ≤ ()

� => �

()ℎℎ ≤ ()

[] = () − ()ℎℎ ≥ 0

Due casi da considerare:

se => cambiando il valore della x , facendola crescere, la disuguaglianza è

� ≤ 0 h

ℎ

sempre verificata �

se => �

� > 0 ≤ =

= ; �

ℎ ℎ ℎ

� ℎ

ℎ

Dato che devo consisderarli tutti il valore più restrittivo è

�

= { : i=1,..,m } ; questo è il massimo valore a cui può crescere

� > 0,

ℎ ℎ ℎ

� ℎ

Riassumendo:

considerando tutti gli elementi della colonna entrante con coefficiente positivo nella

�

matrice trasformata e consideriamo il minimo di questi rapporti identifichiamo la

� ℎ

riga che è più critica, cioè la riga che mi da il limite, chiamando t questa riga vuol dire

che l’operazione di cambiamento avverrà su t e sarà la variabile in posizione t nella

base che uscirà. Quando è cresciuta al suo massimo che è il rapporto, la variabile

ℎ

in posizione t nella base va fuori e va a zero

�

t= riga con min { : i=1,..,m }

� > 0,

 ℎ

� ℎ

�

=

allora x − �

[t] ℎ ℎ

���

=> e lascia la base

= = 0

[]

ℎ � ℎ

Se invece TUTTI i coefficienti sono NEGATIVI o NULLI (� allora x

≤ 0 ∀ = 1, . . , ) h

ℎ

può crescere INDEFINITIVAMENTE e quindi il problema è un PROBLEMA ILLIMITATO

ALGORITMO DEL SIMPLESSO:

Elementi principali:

CRITERIO dell’OTTIMALITA’: per un problema di massimo, una soluzione è

• ottima se i costi ridotti risultano tutti NON POSITIVI

VARIABILI che ENTRANO: quando la soluzione non è ottima, scelta di una

• variabile guardando i costi ridotti, scegliendo, per il massimo, una variabile fuori

base che ha costo ridotto positivo

RIGA per OPERAZIONI di PIVOT: scegliere riga per il pivot e variabile di base

• che esce allora si fa il rapporto tra termini noti e elementi della colonna scelta

per entrare selezionando solo gli elementi strettamente positivi

CONDIZIONE di ILLIMITATEZZA: se in una colonna fuori base risultano tutti gli

• elementi minori o uguali a zero e la colonna ha un coefficiente di costo ridotto

positivo allora il problema è illimitato perché non c’è nessun vincolo che limita

la crescita della variabile x e si può allora far crescere la funzione obiettivo

h

(si calcola inversa base e u , si calcolano i costi ridotti per le colonne non in base

T

test di ottimalità, se => giusto, Test di illimitatezza )

̅ ≤ 0

ℎ

COME TROVARE LA BASE INIZIALE AMMISSIBILE:

L’idea è quella di modificare il problema aggiungendo delle variabili/colonne

adatte a una base iniziale

Delle variabili artificiali ottengo una matrice identità, quindi si prendono queste

due colonne come variabili di base e le altre le metto fuori. Ci sono però più

soluzioni dato che ha aggiunto più variabili, sono soluzioni non del problema,

bisognerà farle uscire. Nella funzione obiettivo ci sono due - che sono variabili

molto negative. Ci potrebbero essere però problemi numerici perché i numeri

potrebbero essere troppo piccoli.

Allora modifichiamo la funzione obiettivo dando peso 1 alle variabili artificiali e 0

alle altre. Questa è la Funzione Obiettivo del problema artificiale, NON DEL

NOSTRO e serve per trovare una base iniziale.

METODO DELLE 2 FASI:

Si risolve il problema in DUE FASI, la PRIMA corrisponde a risolvere questo

problema artificiale, che è SEMPRE IN FORMA DI MINIMO, per trovare una

soluzione di base che non ha in base le colonne artificiali ma che le colonne

originarie. Dopo aver trovato una base con le variabili originali si passa alla

SECONDA FARE in cui si tiene buona la base trovata, si tolgono le variabili artificiali

e si rimette in gioco la FUNZIONE OBIETTIVO di PARTENZA.

Trasformo il tableau di prima per ottenerne uno in forma di base.

Dato che il problema è di minimo e c’è un costo ridotto negativo allora so che x

2

deve entrare. La seconda riga è la riga del Pivot A

Si continuano a scegliere i costi ridotti negativi. Scelgo x da far entrare e il pivot lo

1

faccio sicuramente sulla prima riga dato che il coefficiente è positivo.

Tableau finale con in base x e x e le variabili artificiali sono fuori, si possono allora

1 2

cancellare. B

Rimangono i coefficienti trovati e si rimette la funzione obiettivo di partenza.

Ottengo allora il tableau in forma di base facendo operazioni tra righe e risulta.

In questo caso la base trovata è anche soluzione ottima perché i costi ridotti sono

tutti negativi e il problema iniziale era di massimo

METODO DELLE DUE FASI:

DEGENERAZIONE:

x x + x (vincolo rindondante)

vincoli: x ≥ 2; ≥ 2; ≥ 4

1 2 1 2

X X X X X Scegliamo una base Facciamo l’inversa B -1

1 2 3 4 5 B:

1 -1 2 0 −1 1

1 0 −1

1 -1 2 � �

0 1 0

� �

0 1 0 −1 −1 1

1 -1 4 1 1 0

e moltiplicando i tableau iniziali per B :

-1

X X X X X

1 2 3 4 5

1 -1 2

1 -1 2

1 1 -1 0 Variabile in base con valore zero

SOLUZIONE DI BASE DEGENERE

Chiamiamo una soluzione che ha una o più

componenti pari a zero. Questo rende la variabile in base uguale a zero equivalenti a

quello fuori base, è quindi indistinguibile

X X X X X

1 2 3 4 5 X entrata in base, il

4

1 2 tableau è cambiato

1 1 -1 2 ma i termini noti

rimangono gli stessi

1 1 -1 0

X X X X X

1 2 3 4 5

1 -1 -1 Ora facciamo entrare la x e

5

1 -1 2 vediamo che i termini noti ^1: 1, 2, 3

-1 -1 1 0 non sono cambiati (2,2,0,0,0)

^2: 1, 2, 3

� ^3: 1, 2, 3

In questo tipo di problema pur svolgendo le operazioni di pivot la Funzione obiettivo

rimane sempre la stessa

In un sistema degenere si potrebbe entrare in un loop infinito ma questo si può

REGOLA DI BLAND

evitare attraverso la

REGOLA DI BLAND:

Ogni volta che si hanno nel tableau due colonne equivalenti che potrebbero

• entrare nella base, la scelta deve essere sempre fatta con la colonna di indice

minimo (quella più a sinistra)

Quando la scelta riguarda due righe equivalenti bisogna scegliere la riga con il

• �

minimo indice (righe equivalenti: stesso rapporto ( ) tra termini noti ed

� ℎ

elementi della colonna)

DUALITA’ ANDANDO A MINIMIZZARE

Si può arrivare alla soluzione ottima o la funzione

ANDANDO A MASSIMIZZARE

obiettivo dentro la regione ammissibili oppure la

funzione obiettivo rimanendo fuori dalla regione ammissibile.

PROBLEMA PRIMALE PROBLEMA DUALE

Definiamo due tipi di problemi: e

PRIMALE: DUALE: Vettori termini noti, b, nel duale sono i

min c x

T max u b

T coefficienti della funzione obiettivo.

Ax ≥ I coefficienti della funzione obiettivo

u A c

T T

≤ del primale sono i termini noti del duale

x ≥ 0 u 0

≥

Trasformazione duale:

PRIMALE DUALE Variabili

Vincoli

Digitare l'equazione qui.

FORMA CANONICA:

min c x

T max u b

T

Ax ≥ u A c

T T

≤

x ≥ 0 u 0

≥

FORMA STANDARD: max u b

T

min c x

T u A c

T T

≤

u unrestricted

Ax=

x ≥ 0

TABELLA PRIMALE-DUALE: PRIMALE

DUALE Finito Vuoto Illimitato

Finito X

Vuoto X X

Illimitat