La programmazione lineare e l'algoritmo del simplesso

X

|α| = α

i

i=1

c

In oltre definiamo il multi-indice complementare α come:

0 α = 1

i

c

α =

i 1 α = 0

i

Definiamo in oltre traccia di un multi-indice l’insieme:

n o

∈ ∩

γ(α) := k [0, n] : α = 1

N k

n n

ni=1 1

{e } ∈

Sia in oltre la base canonica di e x . Chiameremo, in oltre, con k (α) la posizione dell’i-simo 1

R R

i i

nel multi-indice. n

{0,

In particolare ci vogliamo concentrare sul sottoinsieme di 1} che chiameremo Q:

n o

n

∈ {0, |α|

Q = α 1} : = m

1 o anche k dove sarà evidente a quale multi-indice ci si riferisca

i 2

n n

|Q| ∈

Chiaramente = . Quindi se α Q possiamo introdurre una nuova struttura algebrica in che indicheremo

R

m

con:

n m k

⊕

=

R R R

α α

⊕ Per poter definire questa nuova struttura usiamo delle funzioni lineari

Dove non indica una somma diretta!

indicizzate nell’intero insieme dei multi-indici definite come: s

X

s

∈ |α|

x , = s =⇒ i (x) = x e

R α i k i

i=1

n

∈

Usando questa regola è possibile scrivere per ogni x :

R m k

⊕ ∈ ∈

x = x x := i (x ) + i (x ) x , x (1)

R R

c

m k α m α k m k

n

2

In questo modo dunque interpretiamo ogni elemento di come la somma delle sue proiezioni inverse su sottospazi

R

di dimensione m e k. I due sottospazi M e K sono determinati dalle basi:

{e } {e }

M = span K = span c

k (α) k (α )

i i

n

∪

Sono ovviamente ortogonali e M K = . Tuttavia noi non usiamo direttamente le proiezioni di x su questi due

R m k

spazi, ma associamo a x due vettori uno di e uno di . Ovvero scriviamo x e x non rispetto alla base di

R R k m

n , ma rispetto alle basi intrinseche di M e K. Per ricostruire x abbiamo quindi bisogno di due funzioni i e i

R c

α α

n

che mappino le basi intrinseche di M e K in quella di .

R

Detto in parole povere abbiamo splittato le n componenti di x in due vettori di componenti, ora, per ricostruire x

dobbiamo sapere in che posizione mettere tutte le componenti dei due vettori . . .

La trasformazione i è una trasformazione lineare (al lettore la facile verifica) ed è in pratica una generalizzazione

della matrice identità infatti: n×|α|

∼ ∈

i I , (I ) = δ , I R

α α α ij k j α

i

m×n

∈ ∈

Sia ora A una matrice a rango pieno. Per ogni α Q possiamo scrivere:

R A x = AI x +AI x = B x +N x

c

α m α k m k m×k

× ∈

Dove B è una matrice quadrata invertibile m m (A ha rango massimo) e N . Che riscriviamo nella forma:

R

A x = B x +N x

B N

Ponendo x = x e x = x . Come si può vedere abbiamo scomposto A in due sottomatrici ovvero:

B m N k

⊕

A = B N α

m k

⊕ ⊕

Dove (B N ) é un operatore lineare su (R ) (la dimostrazione è lasciata al lettore). Per cui useremo anche

R

α α

la notazione: ⊕ ⊕

A x = (B N )[x x ] := B x +N x (2)

B N B N

In particolare utilizzeremo questa definizione per generare gli spazi M e K. Infatti se B è una sotto-matrice quadrata

n

di A e N è la matrice delle colonne rimanenti allora la (2) definisce una struttura di e una partizione su x.

R

Motivo per cui si usa la notazione x dove B è una matrice in luogo dalla notazione (più corretta) in cui si pone a

B

pedice l’indicazzione del sottospazio su cui si proietta x.

È ovvio che si possono estendere le nozioni viste fin ora prendendo in esame strutture generate da più multindici

scelti in maniera tale da avere: k

X m ∀i

α = 1 = 1, 2, . . . n

i

m=1

e quindi generare strutture del tipo: k

i

M |α |

=

R R

1 2 k

α α ...α 1 2 k

α α ...α

i=1

Ma cio esula dagli scopi di questo testo

Si può dimostrare che B è composta da m colonne di A e che N è composta dalle rimanenti.

n m k

2 al lettore la facile verifica del fatto che sia completamente generato dalle basi di e unitamente all’elemento nullo se

R R R

n

pensiamo gli elementi di scritti nella forma (1)

R 3

Def 2.1 (base) Una base é una sottomatrice B di A invertibile.

Siccome, tornando al problema originale, A x = b abbiamo: −1 −1

−B

B x +N x = b =⇒ x = N x +B b

B N B N

−1 ≥

Se B b 0 allora possiamo trovare un valore ammissibile di x ponendo x = 0 e si avrebbe quindi (sottointen-

N

dendo d’ora in anzi il multi-indice α: −1 ⊕0

x = B b

Da cui:

Def 2.2 Una base B di A t.c: −1 ≥

B b 0

é detta base ammissibile di A

Una base ammissibile ha questa importante proprietà V{Ω}

Teorema 2.1 (di Caratterizzazione) Se Ω é un poliedro e é l’insieme dei suoi vertici allora:

n o n o

−1

n

V{Ω} ∈ ⊕ ∩ ≥ ∀B

= x : x = x x , x = B b, x = 0 x 0 sottomatrice di A con rango pieno

R B N B N

Questo è abbastanza evidente se pensiamo che:

n o

−1 −1

− ⊕ ∩ ≥

Ω = B N x +B b x x 0 (3)

N N

α α

Qui si vede che Ω ha un vertice in x = 0 infatti il punto:

N −1 ⊕0

B b 3

Non può essere espresso come combinazione convessa di alcuna coppia di altri punti nella forma (3) .

L’importanza di questo teorema è evidente anche alla luce di questo risultato: ∃x

Teorema 2.2 (Fondamentale) Se il poliedro Ω non é vuoto e z é limitata interiormente in Ω allora vertice

i

del poliedro t.c: ·

z(x ) = min c x

i x∈Ω

Infatti sostituendo nella funzione obbiettivo si ha:

T T

c x = c (I x +I x )

c

α B α N

T T

= c I x + c I x

c

α B α N

TB TN

= c x + c x

B N

−1 −1

TB TN

−B

= c (B b N x ) + c x

N N −1

−1 TN TB

T −

+ (c c B N ) x

= c B b N

B {z }

| | {z }

Costo soluzione di base ammissibile costi ridotti

Come si vede é possibile, esprimendo z, in funzione delle variabili fuori base, valutare i costi “risparmiati” ovvero

TN

ridotti ponendo a zero le variabili x . É chiaro che se i costi ridotti c̄ sono tutti positivi siamo all’ottimo.

N

Viceversa é possibile che cambiando la matrice B si trovi un’altra soluzione ammissibile con un valore migliore della

funzione obbiettivo. In pratica si dimostra che, purché il problema non sia illimitato, con un numero finito di cambi

di base é sempre possibile giungere alla soluzione ottima (scegliendo opportunamente le variabili da portare dentro

e fuori base). →

Per passare da una base all’altra è sufficiente cambiare l’α scelto. In particolare se α : 0 1 si dice che la variabile

i

x è stata portata in base. Viceversa x è stata portata fuori base. In pratica poi per non stare a calcolare B e x

i i B

ogni volta si agisce tenendo memoria dei passaggi precedenti dell’algoritmo, anche perché la moltiplicazione per le

−1

matrici I e B corrisponde a eseguire un pivoting sulla matrice:

α −1

T T TN T

    

 −z̄

−z c c B b c̄ c̄

0 0

B

−→ =

    

 −1 −1

⊕

b A B b I B N b̄ Ā

3 · ⊕ ·

La dimostrazione rigorosa che fa uso della propritá distributiva di rispetto alla moltiplicazione per uno scalare (anch’essa da

dimostrare) é lasciata al lettore. 4

2.2 Regola di Bland

La regola di Bland serve a determinare quali variabili far entrare in base e quali far uscire:

1. La variabile da far uscire é x dove s = min{j : c̄ < 0}

s j

2. Immaginiamo di voler portare in base x e di dover quindi scegliere la x da portare fuori. Sia:

j i

b̄ i

θ =

ij ā

ij

é il massimo valore di cui si può incrementare la x (se θ > 0) senza uscire dal poliedro. Infatti grazie alle

j

trasformazioni di cui si é parlato prima le x saranno descritte nella forma:

i X

−

x = b̄ ā x

i i ij j

j∈γ(α)

Quindi per evitare di uscire dal poliedro occorre scegliere la variabile x in modo tale che:

i

n o

∈ ≤ ∀q

x Q = x : θ θ

i s sj qj

|Q|

Se > 1 si sceglie l’x con indice minimo

i

Osserviamo in oltre che vale il seguente:

∃ ≤ ∀i

Teorema 2.3 Se c̄ < 0 con ā 0 allora il problema è illimitato.

j ij

Def 2.3 Una soluzione di base ammissibile che abbia una variabile in base di valore 0 é detta degenere.

Geometricamente una base degenere corrisponde a un vertice in cui si incontrano più vincoli. Quindi a un punto

geometrico cui corrispondono più basi ammissibili! É possibile quindi che, con una scelta non ideale delle variabili

da far entrare e uscire di base, si generino successioni di basi ammissibili cui corrisponde sempre lo stesso punto

andando a generare cicli senza uscita. Un buon metodo per evitare tutto ciò é usare la regola di Bland di cui si é

parlato prima. Infatti vale il seguente: n

Teorema 2.4 L’algoritmo del simplesso con la regola di Bland termina al più dopo iterazioni all’ottimo.

m

In realtà tranne che in casi patologici si sa da campagne di prove sperimentali che T , la complessità temporale

dell’algoritmo, ha l’andamento: ≤ ≤

m T 3m

2.3 Metodo del Simplesso a Due Fasi

Spesso non è molto semplice trovare una soluzione di base ammissibile con cui inizializzare l’algoritmo del simplesso.

Per cui si ricorre a un problema ausiliario: m

 X

 

T min v = y

min z = c x  i





 ←→

A x = b i=1

A x +I y = b

≥

x 0 

 

 ≥ ≥

x 0, y 0



Le y sono dette variabili artificiali perché rappresentano la distanza di x dai vincoli. Qui é molto facile trovare

i ∗

una base da cui partire: y = b. Se v é la soluzione all’ottimo, possono esservi 2 casi:

∗

1. v > 0 allora il problema di partenza é inammissibile.

∗ ∗ ∗

2. v = 0 allora y = 0 e x é una soluzione di base ammissibile per il problema di partenza. Possono verificarsi

2 sottocasi:

• Se y é fuori base allora avremo:

i ⊕ ⊕ → ⊕ ⊕ ⊕ ⊕

(A I)[