Ricerca Operativa

Capitolo 7a metodo del simplesso

Un poliedro ha sempre un numero finito di vertici che può essere anche zero, inoltre può ammettere più soluzioni ottime.

Forma standard 7.1

Per passare dalla forma normale a quella standard si devono modificare tutti i vincoli in modo da avere solo uguaglianze, aggiungendo una variabile negativa di surplus in caso si abbia ≥, oppure una positiva di slack per il ≥. Da notare che per un problema in forma standard si può applicare sempre il teorema fondamentale della PL poiché esso è contenuto nell’orlante positivo (si impostano le ≥ variabili x ≥ 0) senza perdita di generalità. Ogni PL può essere trasformato in forma standard.

Vertici e soluzioni di base 7.2

Assunzione: il poliedro P è non vuoto e di rango(A)=m, con A matrice m×n. Questa assunzione garantisce la presenza di almeno una sottomatrice non singolare (det ≠ 0) poiché m < n, inoltre non è limitativa.

Teorema 7.2.1

Sia x un punto appartenente al poliedro P. Allora x è un vertice di P se e solo se le colonne di A (matrice coefficienti dei vincoli) relative alle componenti di x positive sono linearmente indipendenti.

Corollario 7.2.1

Se il punto x è un vertice di P (scritto come sopra) allora n-m componenti di x sono nulle.

Tip per pretest

Da questi due punti possiamo risolvere facilmente la parte dei pretest dove viene chiesta l’appartenenza di un punto oppure se questo è un vertice. Per verificare l’appartenenza basta che tutti i vincoli siano rispettati (valgono le disuguaglianze), invece per verificare la proprietà di essere vertice bisogna avere al massimo m (vincoli) componenti non nulle nel vettore x e le colonne relative alle variabili non nulle devono essere linearmente indipendenti.

Definizione 7.2.4

Data la matrice A del problema in forma standard. Una sottomatrice B non singolare di A è detta matrice di base di A.

Osservazione 7.2.7

Un problema di PL in forma standard può essere scritto nella forma equivalente in tanti modi diversi quante sono le matrici di base di A.

Definizione 7.2.8

Un vettore x è detto soluzione di base se i suoi sottovettori (delle variabili in base e non) sono tali che: x_b = B^-1b e x_n = 0.

Definizione 7.2.9

Una matrice di base B di A è detta matrice di base ammissibile di un problema in forma standard se: B^-1b ≥ 0.

Definizione 7.2.10

Un vettore x è detto soluzione di base ammissibile (SBA) se: x_b = B^-1b e x_n = 0, con B base ammissibile di A in forma standard.

Teorema 7.2.2

Sia x un punto appartenente al problema P tale che n-m componenti sono nulle. Allora x è un vertice di P se e solo se è una SBA.

Dimostrazione:
1) Dato che x è una SBA allora abbiamo n-m variabili nulle, quindi le restanti (quelle in base) saranno strettamente maggiori di zero. Inoltre per la definizione di matrice di base, le colonne di B sono linearmente indipendenti. Quindi per il teorema 7.2.1 x è vertice.
2) Supponiamo che x sia un vertice e dimostriamo che esiste una SBA uguale. Abbiamo che le prime r m componenti di x sono positive e le restanti nulle. Per il teorema 7.2.1, siccome x è un vertice allora le colonne non nulle { a₁, ..., a_r } sono linearmente indipendenti. Per il teorema del completamento possiamo trovare m-r colonne di A, oltre a quelle già trovate, tali che queste siano linearmente indipendenti, quindi B = { a₁, ..., a_r, a_r+1, ..., a_m }, con B non singolare. Ora dobbiamo dimostrare le ipotesi del teorema 7.2.10. Abbiamo che poiché le restanti colonne (rb + N_nx_n = B_b + 0 = b = B^-1b.

Teorema 7.2.3

Il numero di SBA (cioè vertici) è finito e al massimo pari a n! / (m! (n-m)!).

Osservazione 7.2.14

Mentre a ciascuna base ammissibile B corrisponde una sola SBA, è possibile che ad una SBA corrispondano più basi ammissibili, questo avviene se la SBA è degenere.

Definizione 7.2.16

Una SBA si dice degenere se il numero di componenti positive è minore di m (vincoli). Quindi se x è non degenere allora ogni componente del vettore B^-1b è strettamente positiva.

Teorema 7.2.4

Se una SBA è non degenere allora esiste una sola base ammissibile che rispetta le ipotesi del 7.2.10.

Dimostrazione:
Perché se ho una SBA degenere allora ho minimo una componente del vettore in base nulla. Ma allora se scambio questa componente con un'altra pari a zero non cambia nulla e produco la stessa base ammissibile.

Introduzione al metodo del simplesso 7.3

Nella fase 1: eliminazione di vincoli sovrabbondanti (dipendenti linearmente) fino a ottenere matrice di rango massimo. Identificazione della base ammissibile B e calcolo delle matrici B^-1N e B^-1b.

Nella fase 2: calcolo della SBA. Verifica criterio di ottimalità, se fallisce verifica criterio di illimitatezza. Se falliti entrambi, allora viene determinata una nuova base ammissibile e ricalcolate le due matrici iniziali.

Assunzioni:
1) l’insieme ammissibile del problema è non vuoto
2) il rango(A) = m
3) data una base ammissibile B si hanno B^-1N e B^-1b.

È facile dimostrare che il numero delle iterazioni della fase 2 è finito poiché il numero di basi ammissibili è finito e maggiore o uguale a uno.

Teorema 7.4.7

Se nessuna base si ripete nella sequenza allora esiste un indice t tale che la t-esima base delle sequenza soddisfa uno dei due criteri. Ma se abbiamo una SBA degenere è possibile che si ripetano alcune basi ammissibili e il teorema non è più valido, quindi:

Corollario 7.4.14

Se ogni SBA è non degenere allora la fase 2 del simplesso termina in un numero finito di passi.

Ma come assicurarsi che non vi siano ripetizioni?
Regola anticiclaggio di Bland: Ogni volta che vi sono più variabili candidate ad entrare o uscire si scelgono quelle con l’indice più piccolo, quindi non verrà mai generata la stessa base ammissibile.

La fase 1 del simplesso 7.5

Bisogna:
1) verificare l’ammissibilità del problema originario da risolvere.
2) Identificare una base ammissibile B.
3) Calcolare B^-1N e B^-1b.
4) Eliminare i vincoli ridondanti se presenti.

Assunzione:
Il vettore b dei vincoli di uguaglianza del problema è tale che: b ≥ 0 per m componenti. Il problema ausiliario PA viene introdotto per verificare l’ammissibilità di quello originario PO. Il PA ha m nuove variabili (non negative) dette artificiali mentre mantiene quelle originali x.

Per ottenere la verifica di ammissibilità devono essere soddisfatte le seguenti ipotesi:

• Denotando con un punto del problema ausiliario formato sia dalle variabili originarie che da quelle ausiliarie, dobbiamo avere che (x; α) = 0, da questo deriva che il PA ha sempre almeno una soluzione ottima.
• Chiamando la matrice identità I_m×m, dobbiamo avere che il rango(A, I) = m, ovvero non sono presenti vincoli ridondanti nel PA.
• La matrice B = I_m è una base ammissibile del problema PO.

Da notare che la non negatività delle variabili artificiali implica la non negatività della funzione obiettivo e quindi il PA non è illimitato inferiormente: Σα_i ≥ 0, quindi non si deve fare il criterio di illimitatezza quando il vettore dei costi ridotti è negativo.

Teorema 7.5.1

Il PO ha una soluzione ammissibile se e solo se la soluzione ottima del PA ha valore pari a zero, per la non negatività allora abbiamo che Σα_i = 0.

Individuazione base ammissibile 7.5.2

B: base ammissibile associata alla soluzione ottima del PA
Iq: numero di colonne della matrice associata alle variabili artificiali, presenti in B
p: numero di colonne della matrice A associata alle variabili originarie, presenti in B
e_i: vettori colonna composti dalle variabili artificiali
a_i: vettori colonna composti dalle variabili originali

Abbiamo la matrice B divisa in due parti:

1. I primi q elementi sono dati dai vettori colonna associati alle variabili artificiali
2. Mentre gli ultimi p dai vettori colonna delle variabili originarie B = {e₁, ..., e_q, a₁, ..., a_p} con p+q=m.

Mentre la matrice fuori base è data dai restanti vettori: N = {e_q+1, ..., e_m, a_p+1, ..., a_n} e può essere partizionata in due sotto matrici ognuna contenente i due insiemi di variabili: G = {e_q+1, ..., e_m} e H = {a_p+1, ..., a_n}.

Ora possono verificarsi i seguenti casi:

Caso 1: p = m

Adesso la matrice di base ammissibile del PA è composta solo dalle colonne relative alle variabili originali, B = {a₁, ..., a_m} e quindi è una matrice di base ammissibile anche per il PO. Quindi per ottenere la forma canonica basta eliminare le variabili artificiali fuori base e le colonne corrispondenti.

Caso 2: p < m

Dobbiamo eliminare dalla matrice di base B tutte le colonne relative alle variabili artificiali e ricondurci al caso 1. L’idea di base consiste nel sostituire una colonna in base con una fuori base. Più precisamente l’elemento presente nelle prime q colonne della matrice B deve essere sostituito con l’elemento presente nella matrice fuori base. Adesso il professore sfaciola perché ha confuso la matrice H con G. Quindi osservando la k-esima riga della matrice G (quella che contiene le variabili artificiali) si possono presentare due sotto casi:

Sotto Caso 2.1

Se tutta la riga k-esima di G ha solo elementi nulli allora è presente un vincolo ridondante nel PO e quindi il rango(A) < m. Allora basta eliminare tale vincolo e riapplicare la Fase 1 per ottenere una nuova forma canonica con un vincolo in meno.

Sotto Caso 2.2

Chiamiamo π_hk (l’elemento h-esimo della riga k-esima di G non nullo). Quindi effettuiamo lo scambio con l’elemento a_p+h e otteniamo una nuova base con le colonne linearmente indipendenti: B = {e₁, ..., a_p+h, ..., e_q, a₁, ..., a_p} e N = {e_q+1, ..., a_p+1, ..., a_n}. Introduciamo la matrice di pivot T rispetto all’elemento π_hk. Grazie a vari teoremi (7.4.6, 7.5.19, 7.5.16 e 7.5.20) troviamo che B è ammissibile perciò possiamo passare alla nuova forma canonica in cui la variabile artificiale associata alla riga k-esima non appartiene più al vettore delle componenti in base. Questo inghippo è chiamato scambio degenere e si può applicare ad una SBA degenere per cambiare la base senza cambiare la SBA. Guardare l’esempio 7.5.6 per ulteriori chiarimenti.

Capitolo 8

Abbreviazioni

• PL: Programmazione lineare
• P: Primale
• D: Duale
• SA: Soluzione ammissibile
• SO: Soluzione ottima
• FO: Funzione obiettivo
• PA: Punto ammissibile

La dualità della PL 8.1

Il concetto di dualità della PL è legato alla possibilità di associare ad ogni problema (chiamato primale) un altro (chiamato duale) che ha la particolarità di permettere la deduzione di importanti proprietà del problema originario. Infatti, sarà possibile risolvere il problema duale al posto del problema primale.

Regole per il passaggio da problema primale a duale

• Il D di un problema di minimizzazione è un problema di massimizzazione e viceversa;
• Ad ogni variabile in uno corrisponde un vincolo nell’altro;
• Avviene uno scambio di coefficienti tra quelli della funzione obiettivo e i termini noti nell’altra.

Esempio:
A: matrice dei coefficienti dei vincoli
b: vettore dei valori noti
Fo: vettore coefficienti della funzione obiettivo

{ min [2x₁ + 3x₂ + x₃ + 4x₄] | x₁, x₂, x₃, x₄ ≥ 0}

A = \[\begin{bmatrix} 1 & 0 & 2 & 7 \\ -5 & 2 & 2 & 4 \end{bmatrix}\], b = \[\begin{bmatrix} 9 \\ -6 \end{bmatrix}\], Fo = \[\begin{bmatrix} 2 \\ 3 \\ 4 \\ 1 \end{bmatrix}\]

Possiamo ottenere il problema D nel seguente modo:
La matrice A trasposta ci darà il sistema dei vincoli, avendo avuto prima 4 incognite e 2 vincoli, nel problema D avremo 4 vincoli e 2 incognite dove i segni di disuguaglianza si trasformano in uguaglianza (poiché le variabili x non sono vincolate, ovvero non hanno i vincoli di non negatività). Inoltre trasponendo il vettore dei termini noti otteniamo i coefficienti della funzione obiettivo e lo stesso con la trasposta di Fo.

{ max [7u₁ + 9u₂] | u₁ + 2u₂ = 2
4u₁ = 3
-u₁ - 6u₂ = 4
u₂ = 11
u₁, u₂ ≥ 0}

Trasformazioni Primale Duale
Vincoli diventano Uguaglianza
Variabili
Disuguaglianza
Variabile ≥ 0

Dualità

OTTIMO ILLIMITATO INAMMISSI
PRIMALE OTTIMO SI NO NO
ILLIMITATO NO NO SI
INAMMISSI NO SI SI

Teorema della dualità debole (8.1.1)

Il valore della Fo di D è minore di quello di P
∀(x, u) ∈ SA, x di P e u di D abbiamo che b^Tu ≤ c^Tx

Dimostrazione:
Visto che x è SA di P allora vale (sono rispettati i vincoli). A questo punto trasponiamo tutto e facciamo il prodotto scalare per u ottenendo:
x^TAx ≥ b^Tx
Facendo i passaggi analoghi per A^Tu ≤ c otteniamo x^TA^Tu ≤ c^Tx.
Questo porta alla conclusione: b^Tu ≤ c^Tx

Corollario

Se x è una SA del problema P e u una SA del problema D tali che: c^Tx = b^Tu, allora sono SO.

Teorema della dualità forte (8.1.2)
Se il problema (P) ammette una SO x, allora anche il problema (D) ammette una SO u e viceversa. Inoltre i valori delle FO dei due problemi all’ottimo sono uguali cioè risulta: c^Tx = b^Tu.

Teorema condizioni di ottimalità (8.1.3)

Siano dati x e u, queste sono SO se e solo se valgono le seguenti condizioni:
1) Ax ≥ b, x ≥ 0 (ammissibilità primale)
2) A^Tu ≤ c, u ≥ 0 (ammissibilità duale)
3) c^Tx = b^Tu (coincidenza dei valore delle FO)

Teorema 8.1.4

Sia x un PA del problema (P) e sia u un punto ammissibile del problema (D). Allora x e u sono SO se e solo se soddisfano le seguenti condizioni:
(Ax - b)^Tu = 0 && (c - A^Tu)^Tx = 0

Dimostrazione:
Ipotesi: x e u sono SA e valgono condizioni del Teo 8.1.4
1) Tesi: x e u sono SO
Facendo il prodotto vettoriale otteniamo:
u^TAx = u^Tb e anche x^Tc = x^TA^Tu
Ma quindi e grazie al teo (8.1.3) è verificata la tesi.
Ipotesi: x e u sono SO
2) Tesi: devono valere le condizioni del teo 8.1.4
Abbiamo che per 8.1.3 e dato che x e u sono SA allora b^Tu = c^Tx rispettano i vincoli e la non negatività quindi: u^TAx = b^Tu = x^TA^Tu = c^Tx
Corollario: Sia x un PA del problema (P) e sia u un PA del problema (D). Allora x e u sono SO se e solo se soddisfano la seguente proprietà: per ogni variabile di (P) non nulla il corrispondente vincolo di (D) deve essere soddisfatto all’uguaglianza e viceversa.

Teorema condizioni di ottimalità (8.1.5)

Due punti x e u sono SO se e solo se valgono le seguenti condizioni:
1) Vengono rispettati i vincoli e la non negatività in entrambi.
2) Vale quello detto nel teorema 8.1.

Interpretazione della dualità 8.2

La dualità rende esplicito l’effetto dei cambiamenti nei vincoli (disponibilità di risorse) sul valore della FO. Le variabili duali possono essere interpretate...