Ricerca operativa

N

x

Una scelta particolarmente importante è porre =0, da cui si ottiene la corrispondente soluzione di base

N

−1

B b Ax = b, x ≥ 0

≥ 0 si ottiene una soluzione di base ammissibile (BFS) per il sistema:

Se

Il problema non è ancora in forma standard, per fare ciò si introducono delle variabili di scarto le quali vanno

unite ai vari vincolo in questo modo:

x x

max z: 2 +

1 2

x x x x x x x x x x

+ + =5; - + + =0; 6 +2 + =21; ;

1 2 3 1 2 4 1 2 5 1

x x x x ≥ 0

: ; ;

2 3 4 5

Se ci fossero stati dei vincoli di ≥ o se fosse stato di min si sarebbero introdotte variabili surplus

con segno opposto

In questo caso abbiamo: m(vincoli)=3; n=5

Avremo quindi la matrice di base B=mxm=3x3 invece N=mx(m-n) =3x2

In maniera grafica prendiamo i vincoli (non standard) li poniamo =n e troviamo le intersezioni con gli assi:

x x x x x x

+ =5; - + =0; 6 +2 =21;

1 2 1 2 1 2 x

La variabile di base associata al vertice p3, in ci sono le

N

componenti che sono uguali a zero, cioè è soddisfatta

x x

l’uguaglianza e in questo caso abbiamo e e di

3 5

x x x x

conseguenza avremo in ,

B 1 2 4

La Matrice A sarà la composizione di tutti i vincoli cioè:

Se faccio questa scelta (p3) la matrice di base sarà composta

dalla 1°,2°,4° colonna di A e invece la Matrice N sarà la 3°e la 5°

x −1

B

= b =

B ❑ p x x x x x x x

Rispetto al vertice avrò = ; invece = ; ;

4 N 2 5 B 1 3 4

x −1

B

La Matrice B sarà : 1 1 0 = b= 0 0 1/6 5 7/2

B ❑

-1 0 1 1 0 -1/6 0 = 3/2

6 0 0 0 1 1/6 21 7/2

N.B. poiché il numero di possibili basi di un problema di PL è comunque al massimo n!/m!(n-m)!, il problema ha

una struttura discreta, i.e., ottimizza selezionando tra un numero finito di alternative, la PL appartiene alla classe

dei problemi combinatori

n!/m!(n-m)! mi definisce in maniera grafica il numero di vertici, o 10 soluzioni di base, nel nostro esempio in cui

n=5 ed m=3 avremo:

120/6*6 = 120/12 = 10

L’insieme dei vincoli e della funzione obiettivo possono essere scritti come un sistema lineare rispetto al quale si

può supporre di aver individuato una base B ammissibile:

Dalla forma vettoriale costruisco il tableau composto dalle righe dei vincoli e dalla riga funzione obiettivo.

ESEMPIO c x c x

Inizialmente noi avevamo una funzione obiettivo z = cx = +

B B N N

x x x x

−1 −1

B B

lo troviamo come: = b - N sostituendo alla prima avremo che:

B B N B

c c c x c c

−1 −1 −1

B B B

z= b - ( N - ) ;; ( N - ) sono i costi ridotti

B B N N B N

x x

B N Valore di z

Termini noti dei vincoli

Riprendendo con l’esempio di prima avremo: x x x

Se ; ; sono le variabili in

3 4 1

base però ancora non mi rappresenta ancora la matrice identica e

per fare ciò dato che abbiamo dobbiamo

moltiplicare le varie righe affinché ottengo la

matrice identica x

Abbiamo anche una non nulla

B

presente nell’espressione in z, ma

sappiamo che l’espressione in z deve

essere tutta 0

p

Per ora io sono su ma capisco anche graficamente che non mi trovo sul vertice ottimo, analiticamente

4

devo prendere l’espressione di z:

x x

z ⅓

+ -⅓ = 7

5 2 x x x x

Faccio entrare in base (lo faccio salire lungo la retta) e fermo cioè pongo =0; mentre

2 5 5 2

x

aumenta automaticamente vi è una variabile in base che si pone =0, come in questo caso =0 in quanto mi

3

p

trovo nel vertice ;

3 x x x x

Scriviamo in questo caso l’equazione di -1/6 +2/3 =3/2 e determiniamo a che valore di ,

3 5 2 2

x diventa 0 cioè:

3 x x

=3/2 ⇒

0-0+2/3 =3/2 * 3/2 =9/4

2 2

x x x x x x

=7/2 ⇒ 4/3 =7/2 ⇒

Rispettivamente si annullerà quando = 1/6 + 4/3

4 4 5 2 2 2

=21/8 x x x x x x

=7/2 ⇒ 1/3 =7/2 ⇒

Rispettivamente si annullerà quando = 1/6 + 1/3

1 1 5 2 2 2

=21/2 x x x x x

Quindi il passo più corto sarà quando =0 quindi in tal caso

3 3 4 1 5

x 2 z 1/2 0 0 1/4 0 31/4

x 3/2 0 0 -1/4 1 9/4

2

x -2 1 0 1/2 0 1/2

4

x -1/2 0 1 1/4 0 11/4

1

Capiamo che il vertice è ottimo quando i coefficienti sono tutti positivi quindi:

x x x

z=31/4-1/2 -1/4 in questi casi se pongo =0 è come se tornassi indietro perché decresce,

3 5 5

x

succede anche se pongo =0 quindi non mi conviene scendere.

3 ¿ ¿

x

x z

Quindi la mia x ottima sarà: = 11/4 invece il valore ottimo della funzione obiettivo =

1

❑

31/4 x

9/4 2

x

0 3

x

1/2 4

x

0 5

Esempio: x x x

max z= 2 - 2 +3

1 2 3

x x x ≤ 4

- + +

1 2 3

x x x ≤ 2

2 - +

1 2 3

x x x ≤ 12

+ +

1 2 3

x x x ≥ 0

, ,

1 2 3

1. Portare in forma standard introducendo variabili di scarto:

x x x x x x x x x x x

- + + + = 4; 2 - + + = 2; + +

1 2 3 4 1 2 3 5 1 2 3

x x x x x x x ≥ 0

+ = 12; , , , ,

6 1 2 3 4 5 6

2. Facciamo il tableau iniziale

x x x x x x

1 2 3 4 5 6

z -2 2 -3 0 0 0 0

-1 1 1 1 0 0 4

2 -1 1 0 1 0 2

1 1 3 0 0 1 12

3. Trovare la matrice identica, nel nostro caso ci è già stata data quindi conosciamo le 3 variabili in base e

il fatto che siano proprio le variabili di scarto significa che ci troviamo nell’origine

x 4

x 5

x 6

4. Ora facciamo entrare nella base la variabile che ha il costo ridotto più piccolo segno incluso, cioè quello

che mi da migliore incremento marginale: x

In questo caso facciamo entrare in base 3 x x

5. Ora dobbiamo capire chi esce dalla base, cioè capire il valore di che va ad annullare ;

3 4

x x

;

5 6

x

a) = 4/1 = 4

4

x

b) = 2/1 = 2

5

x

c) = 12/3 = 4

6 x

Nel nostro caso il passo più breve me lo fa fare 5

6. Sappiamo chi entra e chi esce, all’intersezione abbiamo il pivot il quale deve essere uguale ad 1, in

x

questo caso già lo è quindi non lo dobbiamo trasformare, e le altre variabili in devono essere =0

3

7. Capire se siamo all’ottimo ovvero l’espressione in z deve essere tutta positiva ma ancora non lo è,

x

quindi facciamo entrare in base e rifaccio il procedimento di prima:

2

x

a) = 2/2 =1

4

x

b) è negativo quindi non si annulla mai

3

x

c) = 6/4 = 3/2

6

Rifacciamo il punto 6. e viene:

8. Capiamo che il vertice è ottimo quando i coefficienti sono tutti positivi

ESEMPIO: FASE 1

x x

minz=4 +

1 2

x x x x x

3 + =3 =1; =0 ; =0;

1 2 1 2 1

x =3

2 x x x x

≥ 6

4 +3 =3/2; =0 ;

1 2 1 2

x x

=0; =2

1 2

x x x x

≤ 4 (2/5 ; 9/5 )

+2 =4; =0 ;

1 2 1 2

x x

=0; =2

1 2

x x ≥ 0 (3/5 ; 6/5) La soluzione

;

1 2

ammissibili sono nel segmento in nero

x x

Per tracciare la funzione obiettivo (arancio) poniamo 4 + = k esempio 4, invece per la soluzione

1 2

ottima abbiamo il punto dove s’incontra il vincolo 1 ed il vincolo 3, le coordinate saranno:

x x x x x

=3 ⇒ 12 - 6 - 3 = 0 ⇒

3 + + = 9/5

1 2 2 2 2

x x x x x

= 4 ⇒ ⇒

+2 = 4 - 2 = 2/5

1 2 1 2 1

1. Forma Standard

x x

max z -4 -

1 2

x x x x x x x x x

3 + =3 4 +3 - = 6 +2 + = 4 ;

1 2 1 2 3 1 2 4 1

x x x ≥ 0

; ;

2 3 4

2. Facciamo il tableau iniziale, in questo caso non abbiamo direttamente la matrice identica, quindi

μ μ ≥ 0. Con l’annessione di tali vincoli, siamo

immettiamo delle variabili ausiliarie 1 2 μ

davanti ad un problema ausiliario, ma possiamo risolvere questo problema in cui 1

μ μ

= 0 per trovare una soluzione ammissibile per il problema di partenza. Quindi minz

2 1

μ μ μ

cioè maxz - -

2 1 2

x x x x μ μ

1 2 3 4 1 2

z 0 0 0 0 1 1

μ 3 1 0 0 1 0 3

1

μ 4 3 -1 0 0 1 6

2

x 1 2 0 1 0 0 4

4

2*. Prima di continuare dobbiamo sistemare la funzione obiettivo poiché essa non è mai funzione delle

variabili base,

3. Trovare la matrice identica

x

4. Entra in base cioè la variabile che ha il costo ridotto più piccolo segno incluso

1

μ μ μ x

5. esce dalla base poichè: = 3/3 = 1: = 6/4 = 3/2; = 4/1 = 4

1 1 2 4

x

6. abbiamo il pivot il quale deve essere uguale ad 1, e le altre variabili in devono essere =0

1

7. Non viene l’ottimo e rifaccio il punto 6

8. Definisco il tableau ottimo del problema ausiliario x x x x

9. Dalla fase 1 si estrapola solamente solo le colonne associate a , , , e

1 2 3 4

successivamente la rendiamo ammissibile ⅕

10. Non è la soluzione ottima perchè abbiamo - , quindi rifacciamo il punto 4. 5. 6.

+ DUALITA’

Problema mix di produzione

(P) (D)

Funzione obiettivo

x x

max 15 +10

1 2

x x π

≤ 2000

+

1 2 p

x x π

≤ 1000

- 0.5

1 2 q

x x π

≤ 3000

2 +

1 2 r

x x ≥ 0

;

1 2

REGOLE DI TRASFORMAZIONE ESEMPIO

Teorema debole della dualità Teorema forte della dualità

Simplesso Duale

Abbiamo già trovato l’ottimo però a questo punto decidiamo di mettere un altro vincolo

x x s

≤ 3 ovvero si aggiunge il vincolo e una variabile di slack nel tableau + = 3

1 1 5 Ammissibilità

Analisi Sensibilità Commenti: x

Vincoli stringenti sono e

3

x 5 si legge in corrispondenza

−1

B

delle variabili di slack

Variabili duali ottime= ai prezzi

ombra cioè ½; 0; ¼

Se fosse venuto ≥ 0 allora si

eravamo anche all’ottimo

Il problema diventa illimitato se il costo ridotto è sempre negativo (in questo caso -2) e i coefficienti nei

strettamente negativo ( 1; 2; 2)

ESEMPIO

Per esempio se avessimo N=3 la cardinalità sarebbe 7 cioè 7 sottoinsiemi come (1)(2)(3)(1;2)(2;3)(1;3)(1;2;3) e

se considerassimo anche l’insieme ø sarebbe 8 anche se non avrebbe senso ma considerarlo e provando a

definire una legge partendo dalle possibili soluzione sarebbe:

n

2 -1 es. 3 oggetti viene 8-1(insieme ø ); 4 oggetti viene 16-1(insieme ø) ect..

Il problema di questo tipo è il fatto che cresce esponenzialmente.

Per i problemi di programmazione lineare intera vediamo due modelli fondamentali come:

Partendo dal primo e da un pr