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 obiettivo la descrizione concisa dei principali risultati connessi con la programmazione 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:

min z = c^Tx funzione obiettivo

(max)

≥ ←

A₁x ≥ b₁ vincoli di diseguaglianza

≤ ←

A₂x ≤ b₂ vincoli di diseguaglianza

A₃x = b₃ vincolo di uguaglianza

È una forma standard:

min z = c^Tx funzione obiettivo

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 un’altra forma.

NB: passando da un’altra forma possono variare numero di variabili e di vincoli.

1

Prima e dopo

Prima

max c^Tx

Dopo

min c^Tx

A x + s = b

A x ≤ b

s ≥ 0 variabile di scarto

A x − s = b

A x ≥ b

s ≥ 0 variabile di surplus

x_j = x_j⁺ − x_j⁻

x_j⁺ ≥ 0

x_j⁻ ≥ 0

x_j libera

2. Il metodo del simplesso

Ci occupiamo di problemi in forma standard:

min z = c^Tx

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 scrivere tutti i vincoli come sommatorie.

Il nostro problema di partenza richiede l’ottimizzazione vincolata di z su:

Ω := {x ∈ Rⁿ : A x = b, x ≥ 0}

A ∈ R^m×n, x ∈ Rⁿ e b ∈ R^m.

È chiaro che essendo: ∇z = c

Non ci sono minimi in punti interni di Ω.

L’obiettivo è 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

{α ∈ {0, 1}ⁿ : |α| = m}.

Definiamo norma di un multi-indice il numero:

|α| = ∑_i=1ⁿ α_i.

Inoltre definiamo il multi-indice complementare α^c come:

α_i^c = 1 se α_i = 0

α_i^c = 0 se α_i = 1.

Definiamo inoltre traccia di un multi-indice l’insieme:

γ(α) := {k ∈ [0, n] : α_i = 1}.

Sia inoltre {e_i}_i=1ⁿ la base canonica di Rⁿ e x ∈ Rⁿ. Chiameremo, inoltre, con k_i(α) la posizione dell’i-simo 1 nel multi-indice.

In particolare ci vogliamo concentrare sul sottoinsieme di {0, 1}ⁿ che chiameremo Q:

Q = {α ∈ {0, 1}ⁿ : |α| = m}

o anche k_i dove sarà evidente a quale multi-indice ci si riferisca.

Chiaramente |Q| = n su m. Quindi se α ∈ Q possiamo introdurre una nuova struttura algebrica in Rⁿ che indicheremo con:

Rⁿ = R^m ⊕ R^k

α ⊕ α^c.

Per poter definire questa nuova struttura usiamo delle funzioni lineari indicizzate nell’intero insieme dei multi-indici definite come:

s_α(x) = s ⇒ i_k(x) = x_ie_i

Usando questa regola è possibile scrivere per ogni x ∈ Rⁿ:

x = x_α ⊕ x_α^c := i_α(x) + i_α^c(x), x ∈ R^m ⊕ R^k. (1)

2

In questo modo dunque interpretiamo ogni elemento di Rⁿ come la somma delle sue proiezioni inverse su sottospazi di dimensione m e k. I due sottospazi M e K sono determinati dalle basi:

M = span {e_ki(α)}

K = span {e_ki(α^c)}

Sono ovviamente ortogonali e M ∪ K = Rⁿ.