La programmazione lineare e l'algoritmo del simplesso

La Programmazione Lineare e l’Algoritmo del Simplesso

Albanesi Valentina, Radice David e Travaglino Ermanno

Sommario

Questo breve testo ha come obbiettivo la descrizione concisa dei principali risultati connessi con la program-

mazione lineare. Si tratterà in particolare l’algoritmo del simplesso.

1 La Programmazione Lineare

Qui descriviamo la programmazione lineare come problema base.

1.1 Ipotesi Base modelli PL

Ipotesi di modelli di PL:

Linearità: proporzionalità e additività della funzione obiettivo e dei vincoli

×

Proporzionalità: contributo di ogni variabile = costante variabile. Non si tiene conto di economie di scala!

⇒

Additività: contributo di tutte le variabili = somma dei singoli contributi. Prodotti in competizione guadagni

non indipendenti!

Divisibilità: le variabili possono assumere valori frazionari (reali)

Parametri: supponiamo che tutti i parametri numerici del modello possano essere considerati costanti, ovvero

stimati con un grado di precisione sufficiente.

1.2 Forme Equivalenti

Abbiamo una forma generale: T

min z = c x funzione obbiettivo

(max)

≥ ←

A x b vincoli di diseguaglianza

1 1

≤ ←

A x b vincoli di diseguaglianza

2 2 ←

A x = b vincolo di uguaglianza

3 3

E una forma standard: T ←

min z = c x funzione obbiettivo

←

A x = b solo vincoli di uguaglianza

≥ ←

x 0 tutte variabili non negative

le due formulazioni sono equivalenti

1.3 Regole di trasformazione

Delle regole di trasformazione regolano il passaggio da una all’altra forma.

NB: Passando da una all’altra forma possono variare numero di variabilie di vincoli.

1

PRIMA DOPO

T T

−

max c x min c x

T

A x +s = b

T ≤

A x b ≥

s 0 variabile di scarto

T

−s

A x = b

T ≥

A x b ≥

s 0 variabile di surplus

−

+

 −

x = x x

j j j

 + ≥

x 0

x libera

j j

− ≥

x 0

 j

2 Il Metodo del Simplesso

Ci occupiamo di problemi in forma standard: T

min z = c x

s.t:

A x = b

≥

x 0

e in particolare della loro risoluzione per mezzo dell’algoritmo del simplesso.

2.1 La Geometria del Simplesso

Qui di seguito descriviamo la geometria del simplesso. L’approccio è assolutamente non convenzionale e fa uso di

una notazione sintetica inventata ad-hoc con lo scopo di rendere più chiaro l’algoritmo e in particolare di descrivere

in maniera compatta matriciale i vari passaggi. In particolare consente di dare pieno significato a espressioni del

tipo “x = x + x ” e di “vedere” in azione l’algoritmo del simplesso in un caso generale, senza dover andare a

N B

scrivere tutti i vincoli come sommatorie. Il nostro problema di partenza richiede l’ottimizzazione vincolata di z su:

n o n o

∩ ≥

Ω := A x = b x 0

m×n n m

∈ ∈ ∈

Dove A , x e b .

R R R

É chiaro che essendo: ∇z = c

Non ci sono minimi in punti interni di Ω.

L’obbiettivo é quindi quello di trovare un modo più “furbo” per rappresentare A x e ∂Ω. Per farlo ci dimenticheremo

inizialmente del problema di partenza per sviluppare una breve teoria.

Cominciamo prendendo tre numeri naturali non nulli n,k, m tali che n = m + k. Prendiamo in esame i multi-indici

n

{0, |α|

α dell’insieme 1} . Definiamo norma di un multi-indice il numero:

n

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