|
Wiki
UniCrema
Materie per semestre
Materie per anno
Materie per laurea
Help
|
|
Uni.RO-AlgoritmoDelSimplesso History
Hide minor edits - Show changes to output
Changed line 148 from:
Per fortuna esiste una regolina che ci evita l'imbarazzo di andare a tentoni, e consiste nello scegliere la riga - tra tutte quelle in cui il pivot è positivo - che minimizza il rapporto tra termine noto e pivot. Seguire questo metodo ci permetterà di spostarci sulla prima soluzione di base che incontriamo nella direzione scelta, il che implica la garanzia di ammissibilità. to:
Per fortuna esiste una regolina che ci evita l'imbarazzo di andare a tentoni, e consiste nello scegliere la riga - tra tutte quelle in cui il pivot è strettamente positivo - che minimizza il rapporto tra termine noto e pivot. Seguire questo metodo ci permetterà di spostarci sulla prima soluzione di base che incontriamo nella direzione scelta, il che implica la garanzia di ammissibilità.
Changed line 8 from:
Tutte le immagini di questa pagina sono prese dalle slide del prof [[Giovanni Righini]]
to:
Alcune immagini di questa pagina sono prese dalle slide del prof [[Giovanni Righini]]
Changed lines 143-144 from:
Come facciamo a scegliere il pivot giusto? I prossimi due capitoli ci daranno una risposta.
to:
Ricapitolando, a quanto pare a seconda della scelta del pivot otteniamo una soluzione diversa, migliore o peggiore. Ma come facciamo a scegliere quello giusto? I prossimi due capitoli ci daranno una risposta. Changed lines 146-148 from:
to:
Attraverso la scelta della riga del pivot determiniamo la variabile di base che deve uscire, quindi dobbiamo fare in modo di garantire l'ammissibilità della soluzione. Andando per tentativi provando su tutte le righe posso verificare l'ammissibilità controllando se le coordinate ''(termine noto riga pivot; coefficiente funzione obiettivo colonna pivot)'' ottenute alla fine del pivoting individuano effettivamente un vertice del poliedro o se si trovano al di fuori della regione ammissibile.
Per fortuna esiste una regolina che ci evita l'imbarazzo di andare a tentoni, e consiste nello scegliere la riga - tra tutte quelle in cui il pivot è positivo - che minimizza il rapporto tra termine noto e pivot. Seguire questo metodo ci permetterà di spostarci sulla prima soluzione di base che incontriamo nella direzione scelta, il che implica la garanzia di ammissibilità.
!!!Scelta della colonna del pivot
Per quanto riguarda la scelta della colonna del pivot dobbiamo riprendere in considerazione il ''test di ottimalità'', che ricordiamo ci permette di conoscere (grazie ai coefficienti di costo ridotto) di quanto varierebbe la funzione obiettivo se le variabili fuori base non valessero 0 ma un qualsiasi numero positivo. Grazie a questo test possiamo scoprire se esistono delle direzioni ammissibili di miglioramento della soluzione oppure no. In particolare, nella scelta della colonna del pivot potremo scegliere quella che ha il coefficiente di costo ridotto che fa fallire il test di ottimalità:
* valore positivo se il problema è di massimizzazione
* valore negativo se è di minimizzazione (il caso più frequente, dato che per convenzione si trasformano tutti i problemi in ottimizzazioni di questo tipo)
%rframe%Attach:ROpivoting1.jpg
Nel nostro esempio (vedi figura accanto) entrambi i coefficienti di costo ridotto sono sbagliati, perché stiamo minimizzando e loro sono entrambi negativi. \\
Facendo riferimento all'aspetto grafico del problema, se faccio entrare in base la variabile x'_1_' avrò uno spostamento della soluzione verso destra (verso [@C@]); mentre se faccio entrare in base x'_2_', la soluzione si sposta verso l'alto (verso [@A@]). In entrambi i casi la situazione migliora.
[[<<]]
Ma che fare se stiamo minimizzando ed abbiamo più di una colonna con costo ridotto negativo? Abbiamo diverse strategie:
* scegliere quella con minimo costo ridotto
* scegliere la prima da sinistra
* scegliere a caso
* utilizzare metodi di scelta come quello di Bland
* scegliere la colonna che produce il massimo miglioramento della soluzione
Ora sappiamo tutto quello che ci serve per individuare riga e colonna del pivot. Abbiamo inoltre capito che la scelta della riga garantisce l'ammissibilità della soluzione, mentre quella della colonna l'ottimalità.
!!Test di illimitatezza
Concludiamo i nostri approfondimenti sulle varie fasi dell'algoritmo del simplesso andando a vedere il '''test di illimitatezza''', ovvero il test grazie al quale l'algoritmo capisce che non esiste una soluzione ottima perché il problema è illimitato. \\
Il test di illimitatezza è molto semplice: se le colonne del tableau che hanno costo ridotto negativo (quelle che fanno fallire il test di ottimalità) non hanno nemmeno un elemento positivo, allora il problema è illimitato.
Quando l'algoritmo riconosce questa situazione si blocca ed esce dal processo risolutivo.
Added lines 141-148:
[[<<]]
Come facciamo a scegliere il pivot giusto? I prossimi due capitoli ci daranno una risposta.
!!!Scelta della riga del pivot
TO BE CONTINUED
Changed lines 135-140 from:
Per capire cosa succede da un punto di vista geometrico facciamo riferimento al grafico riportato a destra (che corrisponde al problema in esame). Un iterazione di pivoting consiste nello spostarci da un vertice del poliedro (ad esempio [@A@]), che sappiamo corrispondere a una soluzione di base ammissibile, ad un altro vertice (ad esempio [@B@]). Tutto qui. Si noti che quando diciamo che le variabili di base sono x'_2_', x'_4_' e x'_5_', il vertice corrispondente è quello dato dall'intersezione dei vincoli attivi, e quindi x'_1_' e x'_3_'. to:
Per capire cosa succede da un punto di vista geometrico facciamo riferimento al grafico riportato a destra (che corrisponde al problema in esame). \\
Un iterazione di pivoting consiste nello spostarci da un vertice del poliedro (ad esempio [@A@]), che sappiamo corrispondere a una soluzione di base ammissibile, ad un altro vertice (ad esempio [@B@]). \\
Tutto qui? Tutto qui.
Si noti che quando diciamo che le variabili di base in [@A@] sono x'_3_', x'_4_' e x'_5_', il vertice corrispondente è quello dato dall'intersezione dei vincoli attivi, e quindi x'_1_' e x'_2_'.\\
Stesso ragionamento per [@B@]: le variabili di base sono x'_2_', x'_4_' e x'_5_', quindi il vertice corrispondente è dato dall'intersezione di x'_1_' e x'_3_'.
Changed line 121 from:
(:cellnr width=49% align=center valign=middle bgcolor=#f9f9f9:) to:
(:cellnr width=46% align=center valign=middle bgcolor=#f9f9f9:) Changed line 127 from:
(:cell width=49% align=center valign=middle bgcolor=#f9f9f9:) to:
(:cell width=46% align=center valign=middle bgcolor=#f9f9f9:) Added lines 131-135:
Se proviamo a fare il tableau di questo nuovo sistema otteniamo esattamente quello che prima avevamo ricavato con la tecnica del pivoting.
%rframe%Attach:ROpivotingGeom.jpg
Per capire cosa succede da un punto di vista geometrico facciamo riferimento al grafico riportato a destra (che corrisponde al problema in esame). Un iterazione di pivoting consiste nello spostarci da un vertice del poliedro (ad esempio [@A@]), che sappiamo corrispondere a una soluzione di base ammissibile, ad un altro vertice (ad esempio [@B@]). Tutto qui. Si noti che quando diciamo che le variabili di base sono x'_2_', x'_4_' e x'_5_', il vertice corrispondente è quello dato dall'intersezione dei vincoli attivi, e quindi x'_1_' e x'_3_'.
Changed line 106 from:
(:table cellpadding=10 cellspacing=10:) to:
(:table cellpadding=10 cellspacing=10 width=80%:) Changed line 113 from:
(:cellnr width=49% align=center valign=middle bgcolor=#f9f9f9:) to:
(:cell width=49% align=center valign=middle bgcolor=#f9f9f9:) Changed line 120 from:
(:table cellpadding=10 cellspacing=10:) to:
(:table cellpadding=10 cellspacing=10 width=80%:) Changed line 127 from:
(:cellnr width=49% align=center valign=middle bgcolor=#f9f9f9:) to:
(:cell width=49% align=center valign=middle bgcolor=#f9f9f9:)
Changed lines 106-107 from:
(:table cellpadding=5:)
(:cellnr width=49%:)%lframe%Attach:ROpivotingSP1.jpg '''Problema in forma canonica''' to:
(:table cellpadding=10 cellspacing=10:)
(:cellnr width=49% align=center valign=middle bgcolor=#f9f9f9:)
Attach:ROpivotingSP1.jpg \\
'''Problema in forma canonica''' Changed lines 113-115 from:
(:cell width=49%:)%lframe%Attach:ROpivotingSP2.jpg '''Lo stesso problema riscritto esprimendo le variabili in base in funzione di quelle non in base''' to:
(:cellnr width=49% align=center valign=middle bgcolor=#f9f9f9:)
Attach:ROpivotingSP2.jpg \\
'''Lo stesso problema riscritto esprimendo le variabili in base in funzione di quelle non in base''' Changed lines 120-121 from:
(:table cellpadding=5:)
(:cellnr width=49%:)%lframe%Attach:ROpivotingSP2.jpg '''Sistema prima del cambio basi''' to:
(:table cellpadding=10 cellspacing=10:)
(:cellnr width=49% align=center valign=middle bgcolor=#f9f9f9:)
Attach:ROpivotingSP2.jpg \\
'''Sistema prima del cambio basi''' Changed lines 127-129 from:
(:cell width=49%:)%lframe%Attach:ROpivotingSP3.jpg '''Sistema dopo il cambio basi''' to:
(:cellnr width=49% align=center valign=middle bgcolor=#f9f9f9:)
Attach:ROpivotingSP3.jpg \\
'''Sistema dopo il cambio basi'''
Changed line 107 from:
(:cellnr width=49%:)%lframe%Attach:ROpivotingSP1.jpg'''Problema in forma canonica''' to:
(:cellnr width=49%:)%lframe%Attach:ROpivotingSP1.jpg '''Problema in forma canonica''' Changed line 111 from:
(:cell width=49%:)%lframe%Attach:ROpivotingSP2.jpg'''Lo stesso problema riscritto esprimendo le variabili in base in funzione di quelle non in base''' to:
(:cell width=49%:)%lframe%Attach:ROpivotingSP2.jpg '''Lo stesso problema riscritto esprimendo le variabili in base in funzione di quelle non in base''' Changed line 117 from:
(:cellnr width=49%:)%lframe%Attach:ROpivotingSP2.jpg'''Sistema prima del cambio basi''' to:
(:cellnr width=49%:)%lframe%Attach:ROpivotingSP2.jpg '''Sistema prima del cambio basi''' Changed line 121 from:
(:cell width=49%:)%lframe%Attach:ROpivotingSP3.jpg|'''Sistema dopo il cambio basi''' to:
(:cell width=49%:)%lframe%Attach:ROpivotingSP3.jpg '''Sistema dopo il cambio basi'''
Changed lines 104-122 from:
to:
Ok, funziona, ma che significato hanno questa serie di operazioni? Rivediamo lo stesso esempio in un altro modo, così da poterne osservare meglio le corrispondenze.
(:table cellpadding=5:)
(:cellnr width=49%:)%lframe%Attach:ROpivotingSP1.jpg'''Problema in forma canonica'''
(:cell align=center:)[+[@->@]+]\\
'''pivot'''\\
[+[@->@]+]
(:cell width=49%:)%lframe%Attach:ROpivotingSP2.jpg'''Lo stesso problema riscritto esprimendo le variabili in base in funzione di quelle non in base'''
(:tableend:)
Questo problema ha lo stesso tableau che abbiamo usato sopra come esempio. Se facciamo pivot sull'elemento in riga 1 e colonna 2, faremo entrare in base x'_2_' e uscire x'_3_'. Dovremo quindi aggiornare le equazioni del sistema, esprimendo stavolta x'_2_', x'_4_' e x'_5_' in funzione di x'_1_' e x'_3_'. Ciò che otteniamo è riportato nella figura sotto.
(:table cellpadding=5:)
(:cellnr width=49%:)%lframe%Attach:ROpivotingSP2.jpg'''Sistema prima del cambio basi'''
(:cell align=center:)[+[@->@]+]\\
'''pivot'''\\
[+[@->@]+]
(:cell width=49%:)%lframe%Attach:ROpivotingSP3.jpg|'''Sistema dopo il cambio basi'''
(:tableend:)
Changed line 80 from:
(:table cellpadding=8 width=70%:) to:
(:table cellpadding=8 width=80%:)
Changed line 102 from:
Come risultato avremo ancora una forma canonica, ma abbiamo fatto entrare in base la colonna del pivot e fatto uscire quella che aveva il valore 1 sulla sua riga (in corrispondenza delle variabili in base). Ovviamente non è questo l'unico risultato, ma possiamo osservare che la funzione obiettivo è migliorata, passando da 0 a -8. to:
Come risultato avremo ancora una forma canonica, ma abbiamo fatto entrare in base la colonna del pivot e fatto uscire quella che aveva il valore 1 sulla sua riga (in corrispondenza delle variabili in base). Ovviamente non è questo l'unico risultato, ma possiamo osservare che la funzione obiettivo è migliorata: '''z'_ott_' = - z'_B_' = -8'''.
Changed line 14 from:
to:
Changed line 80 from:
(:table cellspacing=5 width=70%:) to:
(:table cellpadding=8 width=70%:)
Changed lines 16-17 from:
to:
(:cell bgcolor=#f2f6f9:)Forma standard. Changed line 19 from:
(:cell:)%lframe%Attach:ROformaCan1.jpg to:
(:cell bgcolor=#f2f6f9:)%lframe%Attach:ROformaCan1.jpg Changed lines 24-25 from:
(:cell:)Moltiplichiamo a sinistra per '''B'^-1^''''.
(:cell:)%lframe%Attach:ROformaCan3.jpg to:
(:cell bgcolor=#f2f6f9:)Moltiplichiamo a sinistra per '''B'^-1^''''.
(:cell bgcolor=#f2f6f9:)%lframe%Attach:ROformaCan3.jpg Changed lines 82-83 from:
(:cell:)Forma iniziale.
(:cell:)%lframe%Attach:ROpivoting1.jpg to:
(:cell bgcolor=#f2f6f9:)Forma iniziale.
(:cell bgcolor=#f2f6f9:)%lframe%Attach:ROpivoting1.jpg Changed lines 90-91 from:
(:cell:)Dividere la riga ([@r@]) che contiene il pivot per il valore del pivot stesso.
(:cell:)%lframe%Attach:ROpivoting3.jpg to:
(:cell bgcolor=#f2f6f9:)Dividere la riga ([@r@]) che contiene il pivot per il valore del pivot stesso.
(:cell bgcolor=#f2f6f9:)%lframe%Attach:ROpivoting3.jpg
Changed line 15 from:
to:
(:cellnr bgcolor=#f2f6f9:)'''1''' Changed line 23 from:
to:
(:cellnr bgcolor=#f2f6f9:)'''3''' Changed line 81 from:
to:
(:cellnr bgcolor=#f2f6f9:)'''1''' Changed line 89 from:
to:
(:cellnr bgcolor=#f2f6f9:)'''3'''
Changed line 80 from:
(:table cellspacing=5 width=80%:) to:
(:table cellspacing=5 width=70%:)
Changed line 80 from:
to:
(:table cellspacing=5 width=80%:)
Added lines 42-43:
L' '''algoritmo del simplesso''' garantisce l'ottimalità attraverso un processo iterativo di miglioramento che si sposta da un vertice all'altro. Ciò vuol dire che ad ogni iterazione la soluzione o viene lasciata invariata o viene migliorata, e dato che il poliedro è convesso non si può che terminare nella soluzione ottima. Non è polinomiale (nel caso peggiore ha complessità esponenziale), ma nella pratica - anche grazie a costanti raffinamenti - si dimostra più efficiente di questa classe di algoritmi. \\
Eccolo qui: Changed lines 46-102 from:
to:
Affronteremo i vari passi via via nel corso del capitolo.
!!Tableau
La struttura dati che rappresenta la forma canonica su cui lavora l'algoritmo del simplesso si chiama '''tableau''' ed è una matrice.\\
Facciamo un esempio di derivazione di un tableau da un problema già espresso in forma canonica. In particolare le variabili di slack in base (B = {x'_3_',x'_4_',x'_5_'}) saranno scritte in verde, mentre quelle fuori base (N = {x'_1_',x'_2_'}) in rosso.
%center%Attach:ROtableau1.jpg
Facciamo qualche considerazione sul tableau:
* nella posizione (0,0) si mette il termine noto della funzione obiettivo. Per convenzione il problema si esprime sempre in forma di minimo, quindi se sto massimizzando devo invertire i segni (come andrà fatto in questo caso)
* la riga 0 è quella dei '''coefficienti di costo ridotto''', ovvero i coefficienti delle x che compaiono nella funzione obiettivo. Il perché del loro nome lo capiremo poi
* sulla colonna 0 si mettono i vari termini noti [@b@]
* in tutte le altre righe si mettono i coefficienti delle x che compaiono nei vincoli
!!Test di ottimalità
Guardando l'algoritmo del simplesso osserviamo che una volta posto il problema in forma canonica forte ci chiediamo se la soluzione è ottima o no. Come posso rispondere a questa domanda? Con il '''test di ottimalità'''.
Ricordiamo anzitutto che:
%center%Attach:ROtestOtt.jpg
, dove i coefficienti di costo ridotto C'_N_' indicano di quanto cambierebbe la funzione obiettivo [@z@] se il valore delle variabili fuori base x'_N_' passasse da 0 a un numero positivo.
A questo punto possiamo distinguere due ''test di ottimalità'' a seconda della direzione di ottimizzazione:
* se stiamo massimizzando, allora siamo all'ottimo quando ho i coefficienti di costo ridotto minori o uguali a 0
* se stiamo minimizzando, allora siamo all'ottimo quando ho i coefficienti di costo ridotto maggiori o uguali a 0
In entrambi i casi non sarà possibile migliorare ulteriormente la soluzione [@z@] corrente, il che significa che è quella ottima.
Ci ricordiamo il discorso sulla ''degenerazione''? Avevamo detto che era una situazione critica ma non ne avevamo spiegato bene i motivi. Ora però sappiamo che dato che a una soluzione degenere possono corrispondere tante basi diverse, le condizioni di ottimalità non valgono più, e quindi ci potremmo trovare nella situazione in cui siamo già all'ottimo ma non riusciamo ad accorgercene. In questi casi ci vorranno diverse iterazioni in più del necessario per rendersi conto che magari siamo alla soluzione ottima già da un po', ed è tutto tempo computazionale buttato alle ortiche.
!!Pivoting
Passiamo alla parte divertente.\\
Come si fa a cambiare base? Come si passa da una forma canonica all'altra?
A queste domande - peraltro equivalenti - si risponde con la tecnica del '''pivoting'''.
Facciamo un esempio commentato.
(:table cellspacing=5:)
(:cellnr:)'''1'''
(:cell:)Forma iniziale.
(:cell:)%lframe%Attach:ROpivoting1.jpg
(:cellnr:)'''2'''
(:cell:)Scegliere da una delle colonne fuori base un elemento positivo, che chiameremo '''pivot'''. Nel nostro caso quello sulla riga 1 e colonna 2.
Il perché deve essere positivo lo vedremo poi, per ora ci basti sapere che è un requisito per mantenere l'ammissibilità.
(:cell:)%lframe%Attach:ROpivoting2.jpg
(:cellnr:)'''3'''
(:cell:)Dividere la riga ([@r@]) che contiene il pivot per il valore del pivot stesso.
(:cell:)%lframe%Attach:ROpivoting3.jpg
(:cellnr:)'''4'''
(:cell:)Tenetevi forte: sottrarre ad ogni riga [@i@] diversa da [@r@] (quella del pivot) il valore della riga del pivot moltiplicata per l'elemento di [@i@] sulla stessa colonna del pivot.
Facciamo prima con un esempio:\\
riga 0: si sottrae (-2) * (riga del pivot)\\
riga 2: si sottrae (1) * (riga del pivot)\\
riga 3: si sottrae (0) * (riga del pivot)
(:cell:)%lframe%Attach:ROpivoting4.jpg
(:tableend:)
Come risultato avremo ancora una forma canonica, ma abbiamo fatto entrare in base la colonna del pivot e fatto uscire quella che aveva il valore 1 sulla sua riga (in corrispondenza delle variabili in base). Ovviamente non è questo l'unico risultato, ma possiamo osservare che la funzione obiettivo è migliorata, passando da 0 a -8.
Changed lines 31-32 from:
A cosa serve tutto questo? A far vedere che una volta azzerate le variabili fuori base x'_N_' ottengo che: '''z = z'_B_'''' e '''x'_B_' = b (segnato)'''. to:
A cosa serve tutto questo? A far vedere che una volta azzerate le variabili fuori base x'_N_' ottengo che:\\
'''z = z'_B_'''' e '''x'_B_' = b (segnato)'''.
Changed line 27 from:
(:cell:)Sostituiamo tutto in '''z''' e finalmente otteniamo la forma canonica. to:
(:cell:)Sostituiamo tutto in '''z''' ottenendo finalmente la forma canonica.
Changed lines 21-23 from:
(:cell:)Scegliamo una base e dividiamo il problema in "parte in base" (indicata in verde) e "parte fuori base" (indicata in rosso).
In altre parole dobbiamo dividere la matrice '''A''' in due matrici '''B''' ed '''N''', e il vettore '''x''' in '''x'_B_'''' e '''x'_N_''''. to:
(:cell:)Scegliamo una base e dividiamo il problema in "parte in base" (indicata in verde) e "parte fuori base" (indicata in rosso). In altre parole dobbiamo dividere la matrice '''A''' in due matrici '''B''' ed '''N''', e il vettore '''x''' in '''x'_B_'''' e '''x'_N_''''.
Changed line 14 from:
(:cellnr:)%rframe%Attach:ROformaCan1.jpg to:
Changed lines 18-22 from:
(:cellnr:)%rframe%Attach:ROformaCan2.jpg
(:cell:)Abbiamo scelto una base e abbiamo diviso il problema in "parte in base" (indicata in verde) e "parte fuori base" (indicata in rosso).
Abbiamo quindi diviso la matrice '''A''' in due matrici '''B''' ed '''N''', e il vettore '''x''' in '''x'_B_'''' e '''x'_N_''''.
(:cellnr:)%rframe%Attach:ROformaCan3.jpg to:
(:cell:)%lframe%Attach:ROformaCan1.jpg
(:cellnr:)'''2'''
(:cell:)Scegliamo una base e dividiamo il problema in "parte in base" (indicata in verde) e "parte fuori base" (indicata in rosso).
In altre parole dobbiamo dividere la matrice '''A''' in due matrici '''B''' ed '''N''', e il vettore '''x''' in '''x'_B_'''' e '''x'_N_''''.
(:cell:)%lframe%Attach:ROformaCan2.jpg
(:cellnr:)'''3''' Changed lines 26-27 from:
(:cellnr:)%rframe%Attach:ROformaCan4.jpg
(:cell:)Abbiamo sostituito tutto in '''z''' e ottenuto la forma canonica. to:
(:cell:)%lframe%Attach:ROformaCan3.jpg
(:cellnr:)'''4'''
(:cell:)Sostituiamo tutto in '''z''' e finalmente otteniamo la forma canonica.
(:cell:)%lframe%Attach:ROformaCan4.jpg
Changed lines 13-14 from:
(:table cellspacing=5 width=80%:)
(:cellnr:)%lframe%Attach:ROformaCan1.jpg to:
(:table cellspacing=5:)
(:cellnr:)%rframe%Attach:ROformaCan1.jpg Changed line 18 from:
(:cellnr:)%lframe%Attach:ROformaCan2.jpg to:
(:cellnr:)%rframe%Attach:ROformaCan2.jpg Changed line 22 from:
(:cellnr:)%lframe%Attach:ROformaCan3.jpg to:
(:cellnr:)%rframe%Attach:ROformaCan3.jpg Changed line 24 from:
(:cellnr:)%lframe%Attach:ROformaCan4.jpg to:
(:cellnr:)%rframe%Attach:ROformaCan4.jpg
Added lines 1-43:
(:title Ricerca Operativa - Algoritmo del simplesso:)
[[Torna alla pagina di Ricerca Operativa->Ricerca Operativa]]
----
%titolo%''':: Ricerca Operativa - Algoritmo del simplesso ::'''
>>frame<<
Tutte le immagini di questa pagina sono prese dalle slide del prof [[Giovanni Righini]]
>><<
!!Forma canonica di un problema di PL
Nella [[scorsa lezione->RO-Programmazione lineare]] abbiamo visto cosa sono i problemi di programmazione lineare e abbiamo anticipato che per darli in pasto all'algoritmo del simplesso dobbiamo scriverli in '''forma canonica'''. Vediamo come ottenerla a partire dalla forma standard.
(:table cellspacing=5 width=80%:)
(:cellnr:)%lframe%Attach:ROformaCan1.jpg
(:cell:)Forma standard.
Notare che non importa se stiamo minimizzando o massimizzando, la funzione obiettivo è indicata con la notazione generica [@opt@]
(:cellnr:)%lframe%Attach:ROformaCan2.jpg
(:cell:)Abbiamo scelto una base e abbiamo diviso il problema in "parte in base" (indicata in verde) e "parte fuori base" (indicata in rosso).
Abbiamo quindi diviso la matrice '''A''' in due matrici '''B''' ed '''N''', e il vettore '''x''' in '''x'_B_'''' e '''x'_N_''''.
(:cellnr:)%lframe%Attach:ROformaCan3.jpg
(:cell:)Moltiplichiamo a sinistra per '''B'^-1^''''.
(:cellnr:)%lframe%Attach:ROformaCan4.jpg
(:cell:)Abbiamo sostituito tutto in '''z''' e ottenuto la forma canonica.
(:tableend:)
A cosa serve tutto questo? A far vedere che una volta azzerate le variabili fuori base x'_N_' ottengo che: '''z = z'_B_'''' e '''x'_B_' = b (segnato)'''.
Avremo intuito che esistono tante forme canoniche quanti sono i modi in cui posso dividere le variabili di base da quelle fuori base, o analogamente, tante quanto sono le sue basi.
Formalmente, un problema è in forma canonica se e solo se:
# i coefficienti delle x'_B_' nel sistema dei vincoli formano una matrice identità [@I@]
# le x'_B_' non compaiono nella funzione obiettivo [@z@]
Inoltre si dice che la forma canonica è ''forte'' se e solo se i termini noti (b segnato) sono non negativi, altrimenti è detta debole. Quindi se ho una forma canonica forte avrò una serie di soluzioni di base ammissibili, mentre se ho una forma canonica debole saranno non ammissibili.
!!Algoritmo del simplesso
%center%Attach:ROalgSimplesso.jpg
TO BE CONTINUED
----
[[Torna alla pagina di Ricerca Operativa->Ricerca Operativa]]
|
|
