I problemi di PL in forma canonica

Teoria della Programmazione

Lineare

I problemi di PL in forma canonica

In forma scalare:

max Pn

j=1 c_jx_j Pn

j=1 a_ijx_j ≤ b_i i = 1, . . . , m x_j ≥ 0 j = 1, . . . , n

Teoria della Programmazione Lineare – p. 2/89

Prodotto scalare tra vettori

Vettore di dimensione n

p = (p₁ · · · p_n) Dato un altro vettore di dimensione n

q = (q₁ · · · q_n)

Il prodotto scalare tra i due vettori è un valore scalare:

pq =

Xn j=1

p_jq_j

Esempio:

Proprietà

Siano p, q₁, q₂ ∈ Rⁿ e α, β ∈ R. Allora:

p(αq₁ + βq₂) = α(pq₁) + β(pq₂)

Esempio:

p = (2 3 6) q₁ = (1 2 5) q₂ = (6 0 3) α = 2 β = 3

p(αq₁ + βq₂) = 2 ∗ 20 + 3 ∗ 4 + 6 ∗ 19 = 166

α(pq₁) + β(pq₂) = 2 ∗ 38 + 3 ∗ 30 = 166

Teoria della Programmazione Lineare – p. 4/89

Generalizzazione della proprietà

Dati i vettori ^p, q₁, q₂, . . . , q_t ∈ Rⁿ e gli scalari α₁, α₂, . . . , α_t ∈ R, si ha che

p[α₁q₁ + α₂q₂ + · · · + α_tq_t] = p

" _t X

i=1

α_iq_i

#

=

Xt i=1

α_i(pq_i)

Prodotto matrice-vettore

Data una matrice A di ordine m × n (m righe e n colonne)





a₁₁ . . . a_1n ... ... ... a_m1 . . . a_mn





ed un vettore p di dimensione n

p = (p₁ · · · p_n)

Il prodotto matrice-vettore è un vettore di dimensione m la cui componente i è il prodotto scalare tra la i-esima riga di A e il vettore ^p:

Xn j=1

a_ijp_j

Teoria della Programmazione Lineare – p. 6/89

Prodotto vettore-matrice

Data una matrice A di ordine m × n (m righe e n colonne)





a₁₁ . . . a_1n ... ... ... a_m1 . . . a_mn





ed un vettore q di dimensione m

q = (q₁ · · · q_m)

Il prodotto vettore-matrice è un vettore di dimensione n la cui componente j è il prodotto scalare tra la j-esima

colonna di ^A e il vettore ^q:

Esempi

A =

"

7 6 3 2 4 8

#

p = (3 8 7) q = (4 5)

Ap = (7 ∗ 3 + 6 ∗ 8 + 3 ∗ 7 2 ∗ 3 + 4 ∗ 8 + 8 ∗ 7) = (90 94) qA = (4 ∗ 7 + 5 ∗ 2 4 ∗ 6 + 5 ∗ 4 4 ∗ 3 + 5 ∗ 8) = (38 44 52)

Teoria della Programmazione Lineare – p. 8/89

PL in forma canonica

Introduciamo i seguenti vettori:

c ∈ Rⁿ: vettore di dimensione n con componenti c_j, j = 1, . . . , n, ovvero:

c = (c₁ c₂ · · · c_n);

x ∈ Rⁿ: vettore di variabili di dimensione n con componenti x_j, j = 1, . . . , n, ovvero:

x = (x₁ x₂ · · · x_n);

a_i ∈ Rⁿ, i = 1, . . . , m: m vettori di dimensione n con componenti a_ij, j = 1, . . . , n, ovvero:

PL in forma canonica

Osservando che

cx =

Xn j=1

c_jx_j

e

a_ix =

Xn j=1

a_ijx_j

abbiamo la seguente rappresentazione vettoriale per un problema di PL in forma canonica:

max cx

a_ix ≤ b_i i = 1, . . . , m x ≥ 0

Teoria della Programmazione Lineare – p. 10/89

PL in forma canonica

Si consideri la matrice A ∈ R^m×n che ha tante righe quanti sono i vincoli del problema (m) e la cui i-esima riga è il

vettore ^a_i e del vettore ^b = (b₁ · · · b_m) ∈ R^m di dimensione m con componenti b_i, i = 1, . . . , m. Osservando che

Ax = (a₁x . . . a_mx)

possiamo scrivere la rappresentazione matriciale del problema di PL in forma canonica:

max cx

Ax ≤ b x ≥ 0

Esempio degli aiuti umanitari

Il vettore c = (14 5 4)

Il vettore di variabili ^x = (x₁ x₂ x₃) I vettori a_i, i = 1, 2, 3

a₁ = (10 30 20) a₂ = (10 20 40) a₃ = (30 10 5) Il vettore ^b = (5100 8000 1805)

La matrice ^A





10 30 20 10 20 40 30 10 5





Teoria della Programmazione Lineare – p. 12/89

PL canonici ≡ PL generici

Osservazione Ogni problema di PL in forma generica può essere trasformato in uno equivalente in forma canonica.

Trasformazione da min ^a max

min cx = − max −cx

Trasformazione vincolo ≥ ^{in vincolo} ≤

a_ix ≥ b_i ⇔ −a_ix ≤ −b_i

Trasformazione vincolo = in due vincoli ≤

a_ix = b_i ⇔ aix ≤ bi, a_ix ≥ bi ⇔ aix ≤ bi, −a_ix ≤ −bi

PL canonici ≡ PL generici

Sostituzione variabile ≤ 0 con variabile ≥ 0 Data x_i ≤ 0, effettuare il cambio di variabile x_i = −x^′_i, dove x^′_i ≥ 0

Sostituzione variabile libera in segno con due variabili ≥ 0 Data x_i libera in segno, effettuare il cambio di variabile x_i = x^′′_i − x^′_i, dove x^′_i, x^′′_i ≥ 0

Teoria della Programmazione Lineare – p. 14/89

Un esempio

Si trasformi il seguente problema di PL in forma generica in un problema di PL in forma canonica

min x₁ + x₂ + x₃ x₁ + 2x₂ − x₃ ≤ 3 x₁ + 4x₂ + 5x₃ = 5

x₁ − 2x₂ + x₃ ≥ 3 x₁ ≥ 0

x₂ ≤ 0

x₃ libera in segno

Insiemi convessi

Un insieme C ⊆ Rⁿ si dice convesso se

∀ x₁, x₂ ∈ C ∀ λ ∈ [0, 1] : λx₁ + (1 − λ)x₂ ∈ C,

ovvero se dati due punti qualsiasi in C, il segmento che li congiunge è anch’esso completamente contenuto in C.

Teoria della Programmazione Lineare – p. 16/89

Insiemi limitati e chiusi

Un insieme C si dice limitato se esiste una sfera di raggio finito R che lo contiene.

Un insieme C si dice chiuso se contiene la sua frontiera.

Semispazi e iperpiani

Si definisce semispazio in Rⁿ l’insieme di punti che soddisfa una disequazione lineare in Rⁿ:

Xn j=1

w_jx_j ≤ v

(in forma vettoriale: wx ≤ v).

Si definisce iperpiano in Rⁿ l’insieme di punti che soddisfa un’equazione lineare in Rⁿ:

Xn j=1

w_jx_j = v

(in forma vettoriale: ^wx = v).

Teoria della Programmazione Lineare – p. 18/89

Poliedri e politopi

Si definisce poliedro l’intersezione di un numero finito di

semispazi e/o iperpiani. Se il poliedro è limitato esso viene chiamato politopo.

La regione ammissibile S _a

La regione ammissibile S_a di un problema di PL in forma canonica

S_a = {x ∈ Rⁿ : a_ix ≤ b_i, i = 1, . . . , m, x ≥ 0}.

è un poliedro.

Semispazi e iperpiani sono insiemi chiusi

L’intersezione di un numero finito di insiemi chiusi è un insieme chiuso

⇓

I poliedri (e quindi S_a) sono insiemi chiusi

Teoria della Programmazione Lineare – p. 20/89

Convessità

Siano x, y ∈ S_a, ovvero

a_ix ≤ b_i i = 1, . . . , m x ≥ 0, e

a_iy ≤ b_i i = 1, . . . , m y ≥ 0.

Per ogni λ ∈ (0, 1) e per ogni i ∈ {1, . . . , m} avremo:

a_i[λx + (1 − λ)y] =

= λ|{z}

>0

a_ix

|{z}

≤bi

+ (1 − λ)

| {z }

>0

a_iy

|{z}

≤bi

≤

Continua

Inoltre:

|{z}λ

>0

|{z}x

≥0

+ (1 − λ)

| {z }

>0

y

|{z}≥0

≥ 0.

Quindi:

λx + (1 − λ)y ∈ S_a.

⇓

La regione ammissibile S_a è un insieme convesso.

Teoria della Programmazione Lineare – p. 22/89

Limitatezza e illimitatezza

La regione ammissibile S_a può essere:

= ∅

max x₁ + x₂ x₁ ≤ −1 x₁ + x₂ ≤ 1

x₁, x₂ ≥ 0 un poliedro limitato (politopo)

max x₁ + x₂ x₁ + x₂ ≤ 1

x₁, x₂ ≥ 0

Continua

un poliedro illimitato

max x₁ + x₂ x₁ − x₂ ≤ 0

x₁, x₂ ≥ 0

Teoria della Programmazione Lineare – p. 24/89

Ricapitolando ...

... la regione ammissibile S_a di un problema di PL è un poliedro e come tale è un insieme chiuso e convesso.

Inoltre, può essere un insieme vuoto, un insieme limitato (politopo) oppure un insieme illimitato.

Vertici di S _a

Si definisce vertice di S_a un punto x ∈ S_a tale che non esistono due punti distinti x₁, x₂ ∈ S_a, x₁ 6= x₂, tali che

x = 1

2x₁ + 1

2x₂.

ovvero x è il punto medio del segmento che congiunge x₁ e x₂.

Teoria della Programmazione Lineare – p. 26/89

Alcuni risultati

Teorema

Dato un problema di PL in forma canonica, se S_a 6= ∅, allora S_a contiene almeno un vertice.

Osservazione

S_a ha sempre un numero finito di vertici.

Raggi

Nel caso S_a sia un poliedro illimitato possiamo anche introdurre le definizioni di raggio e raggio estremo.

Si definisce raggio di S_a un vettore r tale che

∀ x₀ ∈ S_a ∀ λ ≥ 0 : x₀ + λr ∈ S_a, cioè la semiretta con origine in x₀ e direzione r è

completamente contenuta in S_a per qualsiasi punto ^x₀ ∈ S_a.

Teoria della Programmazione Lineare – p. 28/89

Raggi estremi

Un raggio r di S_a si definisce raggio estremo di S_a se non esistono altri due raggi r₁ e r₂ di S_a con direzioni distinte, ovvero

r₁ 6= µr₂ ∀ µ ∈ R, tali che

r = 1

2r₁ + 1 2r₂.

Osservazione

S_a ha sempre un numero finito di raggi estremi.

Teorema di rappresentazione di S _a

Teorema Sia dato un problema di PL in forma canonica con S_a 6= ∅. Siano v₁, . . . , v_k i vertici di S_a e, nel caso in cui S_a sia un poliedro illimitato, siano r₁, . . . , r_h i raggi estremi di S_a. Allora

x ∈ S_a se e solo se

∃ λ₁, . . . , λ_k ≥ 0,

Xk i=1

λ_i = 1, ∃ µ₁, . . . , µ_h ≥ 0

tali che

x =

Xk i=1

λ_iv_i +

Xh j=1

µ_jr_j.

Teoria della Programmazione Lineare – p. 30/89

Ovvero ...

... i punti in S_a sono tutti e soli i punti ottenibili come somma di

una combinazione convessa dei vertici di S_a

una combinazione lineare con coefficienti non negativi dei raggi estremi di S_a

Quindi un numero finito di oggetti (vertici e raggi estremi) mi permettono di rappresentare tutto l’insieme S_a.

L’insieme delle soluzioni ottime S _ott

Insieme soluzioni ottime

S_ott = {x^∗ ∈ S_a : cx^∗ ≥ cx ∀ x ∈ S_a},

S_ott ⊆ S_a, quindi S_a = ∅ ⇒ S_ott = ∅.

Teoria della Programmazione Lineare – p. 32/89

Una, nessuna, infinite

Osservazione

Se S_ott è un insieme finito e non vuoto, S_ott contiene un solo punto.

Dimostrazione Per assurdo sia S_ott un insieme finito e

contenga più di un punto. Siano ^x₁, x₂ ∈ S_ott, ^x₁ 6= x₂, due punti distinti di S_ott.

Continua

Per l’ottimalità di x₁ e x₂ si deve avere cx₁ = cx₂. Per la convessità di S_a e x₁, x₂ ∈ S_a:

λx₁ + (1 − λ)x₂ ∈ Sa ∀ λ ∈ (0, 1),

Per la linearità della funzione obiettivo ∀ λ ∈ (0, 1):

c[λx₁+(1−λ)x₂] = λcx₁+(1−λ)cx₂ = λcx₁+(1−λ)cx₁ = cx₁. Quindi:

λx₁ + (1 − λ)x₂ ∈ S_ott ∀ λ ∈ (0, 1)

cioè tutto il segmento che congiunge ^x₁ e ^x₂ è contenuto in S_ott, il che contraddice la finitezza dell’insieme S_ott.

Teoria della Programmazione Lineare – p. 34/89

Le diverse forme possibili di S _ott

Caso 1 S_a = ∅ ⇒ S_ott = ∅.

Caso 2 S_a 6= ∅ e politopo.

Politopo è insieme chiuso e limitato, funzione obiettivo è lineare e quindi continua ⇒ (Teorema di Weierstrass) S_ott 6= ∅.

Sono possibili due sottocasi.

Caso 2.1 S_ott è costituito da un solo punto.

max 2x₁ + x₂ x₁ + x₂ ≤ 1

x₁, x₂ ≥ 0

Continua

Caso 2.2 S_ott è costituito da un insieme infinito e limitato di punti.

max x₁ + x₂ x₁ + x₂ ≤ 1

x₁, x₂ ≥ 0

Teoria della Programmazione Lineare – p. 36/89

Continua

Caso 3 S_a 6= ∅ e poliedro illimitato. Sono possibili quattro sottocasi.

Caso 3.1 S_ott = ∅ in quanto l’obiettivo è illimitato, ovvero esiste una sequenza infinita di punti {x_k} di S_a lungo cui la funzione obiettivo cresce a +∞. Formalmente:

∃ {x_k} : x_k ∈ S_a ∀ k e ^cx_k → +∞ k → +∞.

max x₁ + x₂

−x₁ + x₂ ≤ 0 x₁ − x₂ ≤ 1

x ≥ 1

Continua

Caso 3.2 S_ott è costituito da un solo punto.

max −x₁

−x₁ + x₂ ≤ 0 x₁ − x₂ ≤ 1

x₂ ≥ 1 x₁, x₂ ≥ 0

Teoria della Programmazione Lineare – p. 38/89

Continua

Caso 3.3 S_ott è costituito da un insieme infinito e limitato di punti.

max −x₂

−x₁ + x₂ ≤ 0 x₁ − x₂ ≤ 1

x₂ ≥ 1 x₁, x₂ ≥ 0

Continua

Caso 3.4 S_ott è costituito da un insieme infinito e illimitato di punti.

max x₁ − x₂

−x₁ + x₂ ≤ 0 x₁ − x₂ ≤ 1

x₂ ≥ 1 x₁, x₂ ≥ 0

Teoria della Programmazione Lineare – p. 40/89

Un lemma

Lemma

Dato un problema di PL in forma canonica, se S_ott 6= ∅, allora per ogni raggio estremo r di S_a si ha:

cr ≤ 0.

Dimostrazione

Per assurdo supponiamo esista un raggio estremo ^r tale che

cr > 0 S_ott 6= ∅ ⇒ S_a 6= ∅.

Sia x₀ ∈ S_a. Per definizione di raggio avremo che

∀ λ ≥ 0 : x₀ + λr ∈ S_a. Valore funzione obiettivo in punti ^x₀ + λr:

c(x₀ + λr) = cx₀ + λ cr

|{z}>0

|{z}→

λ→+∞

+∞

Allora S_ott = ∅ in quanto l’obiettivo è illimitato sulla regione ammissibile, il che contraddice S_ott 6= ∅.

Teoria della Programmazione Lineare – p. 42/89

Teorema fondamentale della PL

Teorema

Dato un problema di PL in forma canonica, se S_ott 6= ∅, allora S_ott contiene almeno un vertice di S_a.

Dimostrazione

Siano v₁, . . . , v_k i vertici di S_a e, nel caso in cui S_a sia un

poliedro illimitato, indichiamo con r₁, . . . , r_h i raggi estremi di S_a.

Se S_ott 6= ∅, sia ^x∗ ∈ S_ott.

Per assurdo supponiamo che

v₁, . . . , v_k 6∈ S_ott da cui:

cv_i < cx^∗ i = 1, . . . , k

Teoria della Programmazione Lineare – p. 44/89

Continua

Per il teorema di rappresentazione di S_a, ^x∗ ∈ S_a implica che

∃ λ^∗₁, . . . , λ^∗_k ≥ 0,

Xk i=1

λ^∗_i = 1, ∃ µ^∗₁, . . . , µ^∗_h ≥ 0

tali che

x^∗ =

Xk i=1

λ^∗_i v_i +

Xh j=1

µ^∗_jr_j.

Quindi:

cx^∗ = c





Xk

λ^∗_i v_i +

Xh

µ^∗_jr_j





Continua

Per la linearità della funzione obiettivo

cx^∗ =

Xk i=1

λ^∗_i (cv_i) +

Xh j=1

µ^∗_j(cr_j).

Dal lemma precedente:

cr_j ≤ 0 j = 1, . . . , h.

Teoria della Programmazione Lineare – p. 46/89

Continua

Quindi:

cx^∗ =

Xk i=1

λ^∗_i (cv_i) +

Xh j=1

µ^∗_j

|{z}≥0

(cr_j)

| {z }

≤0

.

da cui:

cx^∗ ≤

Xk i=1

λ^∗_i (cv_i).

Continua

Da ^cv_i < cx^∗, ∀ i segue che:

cx^∗ ≤

Xk i=1

λ^∗_i (cv_i)

| {z }

<cx^∗

<

Xk i=1

λ^∗_i (cx^∗).

NB: lo strettamente minore vale perchè almeno uno dei λ^∗_i è strettamente positivo in quanto la loro somma deve essere pari a 1.

Quindi:

cx^∗ < (cx^∗)

Xk i=1

λ^∗_i = cx^∗.

il che è assurdo.

Teoria della Programmazione Lineare – p. 48/89

Un commento

Il teorema fondamentale della PL è alla base della

procedura di risoluzione che descriveremo, l’algoritmo del simplesso.

Infatti, tale algoritmo ricerca la soluzione ottima cercando di spostarsi ad ogni iterazione in modo intelligente da un

vertice all’altro di S_a. Per modo intelligente si intende che l’algoritmo tenta di spostarsi ad una data iterazione da un vertice a uno con valore della funzione obiettivo maggiore.

I problemi di PL in forma standard

I problemi di PL in forma standard hanno la seguente formulazione:

max cx

a_ix = b_i i = 1, . . . , m x ≥ 0

o, equivalentemente, in forma matriciale:

max cx

Ax = b x ≥ 0

Teoria della Programmazione Lineare – p. 50/89

Un’osservazione

Osservazione

Ogni problema di PL in forma canonica può essere trasformato in uno equivalente in forma standard.

Dimostrazione

Problema di PL in forma canonica

max cx

a_ix ≤ b_i i = 1, . . . , m x ≥ 0

a_ix ≤ b_i ⇔ a_ix + y_i = b_i, y_i ≥ 0.

Quindi, il problema di PL in forma canonica è equivalente al seguente:

max cx

a_ix + y_i = b_i i = 1, . . . , m x ≥ 0

y_i ≥ 0 i = 1, . . . , m

che è in forma standard. Teoria della Programmazione Lineare – p. 52/89

Continua

Ogni problema di PL può essere ricondotto ad uno equivalente in forma canonica.

Ogni problema in forma canonica può essere ricondotto ad uno equivalente in forma standard.

Quindi: ogni problema di PL può essere ricondotto ad uno equivalente in forma standard.

NB: nella pratica si passa direttamente da un problema di PL in forma generica ad uno equivalente in forma standard, senza passare necessariamente attraverso un problema in forma canonica.

Un esempio

Si trasformi il seguente problema di PL in forma generica in un problema di PL in forma standard

min x₁ + x₂ + x₃ x₁ + 2x₂ − x₃ ≤ 3 x₁ + 4x₂ + 5x₃ = 5

x₁ − 2x₂ + x₃ ≥ 3 x₁ ≥ 0

x₂ ≤ 0

x₃ libera in segno

Teoria della Programmazione Lineare – p. 54/89

Ipotesi aggiuntiva

Si richiede che la matrice dei vincoli A ∈ R^m×n abbia rango (= numero di righe linearmente indipendenti = numero di colonne linearmente indipendenti) pari a m, il numero delle sue righe, il che equivale a richiedere che:

non ci sono righe di ^A ottenibili come combinazioni lineari di altre righe di ^A;

esistono m colonne della matrice A che formano una matrice quadrata invertibile.

NB: Si può dimostrare che anche questa non è una

condizione restrittiva e che ci si può sempre ricondurre ad essa.

Esempi

A₁ =





1 2 1 3 2 1 3 4 3 0 5 5





Rango di ^A₁ < m = 3

A₂ =

"

1 2 2 1 −1 3 7 1 3 1

#

Rango di A₂ = m = 2

Teoria della Programmazione Lineare – p. 56/89

Base di un problema di PL

Si definisce base di un problema di PL in forma standard un sottinsieme:

B = {x_i1, . . . , x_im}

di m delle n variabili del problema di PL con la proprietà che la matrice A_B ∈ R^m×m ottenuta considerando le sole

colonne di ^A relative alle variabili x_ik, k = 1, . . . , m, sia invertibile.

Le variabili dell’insieme B verranno dette variabili in base, quelle al di fuori di B verranno raggruppate nell’insieme:

N = {x_im+1, . . . , x_in}

Un esempio

Dato

max 3x₁ + 4x₂ + 2x₃ + 2x₄ + x₅ x₁ + 2x₂ + 2x₃ + x₄ − x₅ = 2 x₁ + 2x₂ + x₃ + 4x₄ − 2x₅ = 2

x₁, x₂, x₃, x₄, x₅ ≥ 0 Matrice dei vincoli

A =

"

1 2 2 1 −1 1 2 1 4 −2

#

Teoria della Programmazione Lineare – p. 58/89

Continua

B₁ = {x₁, x₂} → non è una base. Infatti

A_B1 =

"

1 2 1 2

#

non è invertibile

Invece, B₂ = {x₁, x₃} è una base in quanto:

A_B2 =

"

1 2 1 1

#

è invertibile

Allo stesso modo si verifichi che B₃ = {x₃, x₄} e B₄ = {x₄, x₅} sono basi.

Riformulazione rispetto alla base B

Data una base B, indichiamo con:

x_B ∈ R^m il vettore delle variabili in base

x_N ∈ R^n−m il vettore delle variabili fuori base

c_B ∈ R^m il vettore dei costi relativi alle variabili in base c_N ∈ R^n−m il vettore dei costi relativi alle variabili fuori base

A_N ∈ R^m×(n−m) la matrice ottenuta da A considerando le sole colonne relative alle variabili fuori base.

Teoria della Programmazione Lineare – p. 60/89

Nell’esempio

Con la base B = {x₁, x₃} abbiamo:

x_B = (x₁ x₃)

x_N = (x₂ x₄ x₅) c_B = (3 2)

c_N = (4 2 1)

A_N =

"

2 1 −1 2 4 −2

#

Riscrittura della riformulazione

Possiamo ora riscrivere il problema di PL in forma standard nella seguente forma equivalente:

max c_Bx_B + c_Nx_N

A_Bx_B + A_Nx_N = b x_B, x_N ≥ 0

e quindi anche in questo modo:

max c_Bx_B + c_Nx_N A_Bx_B = b − A_Nx_N

x_B, x_N ≥ 0

Teoria della Programmazione Lineare – p. 62/89

Nell’esempio

max

c_Bx_B

z }| { 3x₁ + 2x₃ +

c_Nx_N

z }| {

4x₂ + 2x₄ + x₅

A_Bx_B

z }| { x₁ + 2x₃ +

A_Nx_N

z }| {

2x₂ + x₄ − x₅ = 2 x₁ + x₃ + 2x₂ + 4x₄ − 2x₅ = 2

x₁, x₃

| {z }

x_B

, x₂, x₄, x₅

| {z }

x_N

≥ 0

E quindi ...

max

c_Bx_B

z }| { 3x₁ + 2x₃ +

c_Nx_N

z }| {

4x₂ + 2x₄ + x₅

A_Bx_B

z }| { x₁ + 2x₃ =

b−ANx_N

z }| {

2 − 2x₂ − x₄ + x₅ x₁ + x₃ = 2 − 2x₂ − 4x₄ + 2x₅

x₁, x₃

| {z }

x_B

, x₂, x₄, x₅

| {z }

x_N

≥ 0

Teoria della Programmazione Lineare – p. 64/89

Continua

Moltiplichiamo ora i vincoli di uguaglianza per ^A−1_B : max c_Bx_B + c_Nx_N

A⁻¹_B A_Bx_B = A⁻¹_B b − A⁻¹_B A_Nx_N x_B, x_N ≥ 0

e quindi da A⁻¹_B A_Bx_B = Ix_B = x_B

max c_Bx_B + c_Nx_N

x_B = A⁻¹_B b − A⁻¹_B A_Nx_N x_B, x_N ≥ 0

Questo equivale a risolvere il sistema dato dai vincoli di

Nell’esempio

max 3x₁ + 2x₃ + 4x₂ + 2x₄ + x₅ x₁ = 2 − 2x₂ − 7x₄ + 3x₅

x₃ = 0 + 3x₄ − x₅ x₁, x₃, x₂, x₄, x₅ ≥ 0

Teoria della Programmazione Lineare – p. 66/89

Riformulazione rispetto alla base B

Infine, sostituendo x_B nell’obiettivo:

c_Bx_B + c_Nx_N = c_B A⁻¹_B b − A⁻¹_B A_Nx_N

+ c_Nx_N da cui:

max c_BA⁻¹_B b + (c_N − c_BA⁻¹_B A_N)x_N x_B = A⁻¹_B b − A⁻¹_B A_Nx_N

x_B, x_N ≥ 0

Questa riformulazione viene detta riformulazione del problema di PL rispetto alla base B.

NB: tale riformulazione è del tutto equivalente al problema

Nell’esempio

Riformulazione rispetto alla base B = {x₁, x₃}: max 6 − 2x₂ − 13x₄ + 8x₅

x₁ = 2 − 2x₂ − 7x₄ + 3x₅ x₃ = 0 + 3x₄ − x₅

x₁, x₃, x₂, x₄, x₅ ≥ 0

Teoria della Programmazione Lineare – p. 68/89

Soluzioni di base

Si definisce soluzione di base associata alla base B, la seguente soluzione del sistema di vincoli di uguaglianza ottenuta ponendo x_N = 0:

x_B = A⁻¹_B b x_N = 0.

Nell’esempio:

x₁ = 2 x₃ = 0 x₂ = x₄ = x₅ = 0

Ammissibilità e non degenerazione

Se ^A−1_B ^b ≥ 0 la soluzione di base si dice ammissibile.

Questo vuol dire che appartiene alla regione ammissibile del problema di PL in quanto, oltre a soddisfare i vincoli di uguaglianza del problema, soddisfa anche quelli di non negatività delle variabili.

Se inoltre si ha ^A−1_B ^b > 0 si parla di soluzione di base non degenere, altrimenti si parla di soluzione di base degenere.

Teoria della Programmazione Lineare – p. 70/89

Nell’esempio

B₂ = {x₁, x₃} → soluzione di base ammissibile e degenere B₃ = {x₃, x₄}: la soluzione di base è

x₃ = 6/7 x₄ = 2/7 x₁ = x₂ = x₅ = 0, che è ammissibile e non degenere

B₄ = {x₄, x₅}: la soluzione di base è

x₄ = −1 x₅ = −3 x₁ = x₂ = x₃ = 0, che è non ammissibile.

Osservazione

Data una soluzione di base ammissibile e non degenere esiste un’unica base che la rappresenta, mentre una

soluzione di base ammissibile e degenere è rappresentata da più basi.

Si verifichi, ad esempio, che la base B₅ = {x₁, x₄} ha come soluzione di base associata:

x₁ = 2 x₄ = 0 x₂ = x₃ = x₅ = 0, che è la stessa associata alla base B₂.

Teoria della Programmazione Lineare – p. 72/89

Ma ...

... cosa hanno a che fare le basi e le soluzioni di base con il teorema fondamentale della PL?

La risposta ci viene dalla seguente osservazione.

Osservazione L’insieme dei vertici di S_a coincide con l’insieme delle soluzioni di base ammissibili del problema di PL.

In pratica, vertici e di soluzioni di base ammissibili sono la stessa cosa vista da due punti di vista diversi: quello

geometrico (i vertici) e quello algebrico (le soluzioni di base ammissibili).

Basi adiacenti

Due basi B^′ e B^′′ si definiscono adiacenti se hanno m − 1 variabili uguali e differiscono per una sola variabile.

Nell’esempio le basi B₃ = {x₃, x₄} e B₄ = {x₄, x₅} sono adiacenti, mentre non lo sono B₂ = {x₁, x₃} e B₄.

Teoria della Programmazione Lineare – p. 74/89

Soluzioni di base adiacenti

Due soluzioni di base distinte si definiscono adiacenti se

esistono due basi B^′ e B^′′ che le rappresentano e che sono tra loro adiacenti.

Si noti che due basi adiacenti non corrispondono

necessariamente a due soluzioni di base adiacenti. Esse infatti possono corrispondere alla stessa soluzione di base come accade, ad esempio, con le basi B₂ = {x₁, x₃} e

B₅ = {x₁, x₄}.

Riformulazione rispetto alla base B

Sia data la base:

B = {x_i1, . . . , x_im}.

con

N = {x_im+1, . . . , x_in}

l’insieme delle variabili fuori base. Abbiamo visto che, data la base B, la riformulazione del problema di PL rispetto alla base B è data da

max c_BA⁻¹_B b + (c_N − c_BA⁻¹_B A_N)x_N x_B = A⁻¹_B b − A⁻¹_B A_Nx_N

x_B, x_N ≥ 0

Teoria della Programmazione Lineare – p. 76/89

Continua

Indichiamo con:

γ₀ il valore c_BA⁻¹_B b;

γ_j, j = 1, . . . , n − m, le componenti del vettore c_N − c_BA⁻_B¹A_N;

β_r, r = 1, . . . , m, le componenti del vettore ^A−1_B ^b;

α_rj, r = 1, . . . , m, j = 1, . . . , n − m, le componenti della matrice −A⁻¹_B A_N

Continua

In forma scalare possiamo riscrivere la riformulazione rispetto alla base B nel seguente modo:

max γ₀ + Pn−m

j=1 γ_jx_im+j x_i1 = β₁ + Pn−m

j=1 α_1jx_im+j

· · · x_ik = β_k + Pn−m

j=1 α_kjx_im+j

· · ·

x_im = β_m + Pn−m

j=1 α_mjx_im+j x₁, . . . , x_n ≥ 0

Teoria della Programmazione Lineare – p. 78/89

Nell’esempio

Riformulazione rispetto alla base B₂ = {x₁, x₃}: max 6 − 2x₂ − 13x₄ + 8x₅

x₁ = 2 − 2x₂ − 7x₄ + 3x₅ x₃ = 0 + 3x₄ − x₅

x₁, x₃, x₂, x₄, x₅ ≥ 0

Passaggio ad una base adiacente

Supponiamo ora di voler passare dalla base B alla base adiacente B^′ ottenuta rimuovendo da B la variabile x_ik,

1 ≤ k ≤ m, e sostituendola con la variabile fuori base x_im+h, 1 ≤ h ≤ n − m, ovvero:

B^′ = {x_i1, . . . , x_ik−1, x_im+h, x_ik+1, . . . , x_im}.

La prima domanda che ci dobbiamo porre è :

quando B^′ è effettivamente una base. Perché lo sia si deve avere che A_B^′ è invertibile.

Teoria della Programmazione Lineare – p. 80/89

Continua

Si ha che A_B^′ è invertibile e quindi B^′ è una base ^{se e solo}

se nella riformulazione associata alla base B il coefficiente di x_im+h nell’equazione relativa a x_ik è diverso da 0, ovvero se e solo se:

α_kh 6= 0.

Nell’esempio:

{x₁, x₂} non è una base {x₁, x₅} è una base

L’operazione di cardine

Tale operazione consente di passare dalla riformulazione rispetto alla base B a quella rispetto alla base adiacente B^′. Per fare questo dovremo compiere le seguenti operazioni.

Ricavare x_im+h dall’equazione relativa a x_ik, cioè:

x_im+h = − β_k

α_kh + 1

α_kh x_ik −

n−mX

j=1, j6=h

α_kj

α_kh x_im+j. sostituire ogni occorrenza della variabile x_im+h nelle

restanti equazioni e nell’obiettivo con la parte destra di tale equazione

Teoria della Programmazione Lineare – p. 82/89

Esempio

Dalla riformulazione rispetto a B₂ = {x₁, x₃} a quella rispetto a B₆ = {x₁, x₅}

Ricavo x₅ dall’equazione relativa a x₃ x₅ = 0 − x₃ + 3x₄

Sostituisco la parte destra dell’equazione nei restanti vincoli e nell’obiettivo

max 6 − 2x₂ − 13x₄ + 8(0 − x₃ + 3x₄) x₁ = 2 − 2x₂ − 7x₄ + 3(0 − x₃ + 3x₄)

x₅ = 0 − x₃ + 3x₄ x₁, x₃, x₂, x₄, x₅ ≥ 0

Riformulazione rispetto a B ₆ = {x 1 , x ₅ }

max 6 − 2x₂ − 8x₃ + 11x₄ x₁ = 2 − 2x₂ + 2x₄ − 3x₃

x₅ = 0 − x₃ + 3x₄ x₁, x₃, x₂, x₄, x₅ ≥ 0

Teoria della Programmazione Lineare – p. 84/89

Nota bene

Per poter recuperare dalle riformulazioni alcune

informazioni (nel seguito vedremo, ad esempio, come

sfruttare la riformulazione rispetto a una base B per poter ottenere la matrice ^A−1_B ) è necessario mantenere un ordine tra le variabili in una base. Quindi se nella base B^′ la

variabile x_im+h sostituisce la variabile x_ik a cui corrisponde la k-esima equazione della riformulazione rispetto a B,

nella riformulazione rispetto a B^′ l’equazione relativa alla variabile x_im+h dovrà ancora essere la k-esima, mentre la posizione delle equazioni relative a tutte le altre variabili deve rimanere invariata rispetto alla precedente

riformulazione.

Nell’esempio ...

... la variabile x₅ ha preso il posto della x₃ e l’equazione relativa alla x₅ è stata messa nella stessa posizione (la

seconda) in cui si trovava quella della x₃, mentre la restante equazione ha mantenuto la posizione originaria.

Teoria della Programmazione Lineare – p. 86/89

Un altro esempio

Passaggio da B₆ = {x₁, x₅} a B₄ = {x₄, x₅} Ricavo x₄ dall’equazione relativa a x₁

x₄ = −1 + 1/2x₁ + x₂ + 3/2x₃

Sostituisco la parte destra dell’equazione nei restanti vincoli e nell’obiettivo

max 6 − 2x₂ − 8x₃ + 11(−1 + 1/2x₁ + x₂ + 3/2x₃) x₄ = −1 + 1/2x₁ + x₂ + 3/2x₃

x₅ = 0 − x₃ + 3(−1 + 1/2x₁ + x₂ + 3/2x₃) x₁, x₃, x₂, x₄, x₅ ≥ 0

Continua

Riformulazione rispetto a B₄ = {x₄, x₅}:

max −5 + 11/2x₁ + 9x₂ + 17/2x₃ x₄ = −1 + 1/2x₁ + x₂ + 3/2x₃ x₅ = −3 + 3/2x₁ + 3x₂ + 7/2x₃

x₁, x₃, x₂, x₄, x₅ ≥ 0

Teoria della Programmazione Lineare – p. 88/89

Nota bene

Le operazioni di cardine che abbiamo eseguito sugli

esempi ci hanno consentito di passare da una base ad una adiacente e, nel secondo esempio, anche da una soluzione di base ad una adiacente. Tuttavia, nel secondo caso

siamo passati da una soluzione di base ammissibile (quella associata a B₆) ad una non ammissibile (quella associata a B₄). Nell’algoritmo di risoluzione che ci apprestiamo a

discutere la scelta della base adiacente verso cui muoversi non verrà fatta a caso come abbiamo fatto nei precedenti esempi, ma sarà guidata da regole precise che

fondamentalmente ci consentiranno di spostarsi tra vertici della regione ammissibile migliorando il valore della

funzione obiettivo.