Basi ammissibili
Ciao a tutti,
sto studiando ricerca operativa e in particolare il metodo del simplesso e devo dire che ci sto capendo ben poco, di teoria non ci capisco nulla quindi in pratica (purtroppo!) sto studiando sugli esempi e non capisco questo esempio:
Il programma lineare
[tex]max z = 8x_1 + 3x_2[/tex]
soggetto a
[tex]4x_1 + 5x_2 \geq 10[/tex]
[tex]4x_1 + 10x_2 \geq 15[/tex]
[tex]x_2 \geq 1[/tex]
[tex]x_1, x_2 \geq 0[/tex]
equivale al seguente programma in forma standard.:
[tex]max z = 8x_1 + 3x_2[/tex]
soggetto a
[tex]4x_1 + 5x_2 + x_3 = 10[/tex]
[tex]4x_1 + 10x_2 + x_4 = 15[/tex]
[tex]x_2 + x_5 = 1[/tex]
[tex]x_1, ... , x_5 \geq 0[/tex]
Fino a qui ho capito, trasforma semplicemente un programma lineare in forma generica in uno in forma standard, ho fatto diversi esercizi di questo tipo e mi vengono. Ora va avanti in questo modo:
Si possono identificare le seguenti basi ammissibili:
[tex]\left \{ A_3, A_4, A_5 \right \} $=>$ A_B = $((1,0,0),(0,1,0),(0,0,1))$[/tex] x_B = $((x_3,x_4,x_5))$ = $((10,15,1))$
[tex]\left \{ A_2, A_3, A_4 \right \} $=>$ A_B = $((5,1,0),(10,0,1),(1,0,0))$[/tex] x_B = $((x_2,x_3,x_4))$ = $((1,5,5))$
[tex]\left \{ A_1, A_2, A_3 \right \} $=>$ A_B = $((4,5,1),(4,10,0),(0,1,0))$[/tex] x_B = $((x_1,x_2,x_3))$ = $((5/4,1,0))$
[tex]\left \{ A_1, A_2, A_4 \right \} $=>$ A_B = $((4,5,0),(4,10,1),(0,1,0))$[/tex] x_B = $((x_1,x_2,x_4))$ = $((5/4,1,0))$
[tex]\left \{ A_1, A_2, A_5 \right \} $=>$ A_B = $((4,5,0),(4,10,0),(0,1,1))$[/tex] x_B = $((x_1,x_2,x_5))$ = $((5/4,1,0))$
[tex]\left \{ A_1, A_4, A_5 \right \} $=>$ A_B = $((4,0,0),(4,1,0),(0,0,1))$[/tex] x_B = $((x_1,x_4,x_5))$ = $((5/2,5,1))$
(chiedo scusa se non ho scritto in modo giusto ma non riesco a capire dove sbaglio. A destra dove c'è [tex]x_B[/tex] i vettori dovrebbero essere in colonna e non in riga)
Non sono riportate esplicitamente le variabili fuori base, perchè esse hanno sempre valore [tex]0[/tex]. Si noti come le basi degeneri (dalla 3 alla 5) descrivano tutte la stessa soluzione, pur essendo basi distinte. E' invece una base non ammissibile, ad esempio, la
[tex]\left \{ A_1, A_3, A_5 \right \} $=>$ A_B = $((4,1,0),(4,0,0),(0,0,1))$[/tex] x_B = $((x_1,x_3,x_5))$ = $((15/4,-5,1))$
perchè la [tex]x_B[/tex] viola i vincoli di non-negatività.
Io ho capito che prende tre colonne (a caso?) e guarda i corrispettivi coefficienti nei vincoli e li mette nella matrice. Ma poi non capisco come ottiene [tex]x_B[/tex].
E non capisco nemmeno lo scopo finale dell'esercizio, questo è il metodo del simplesso? Non credo, cos'è allora quest'algoritmo del simplesso? Cosa sono le variabili fuori base, le basi degeneri, le basi non ammissibili ecc? Non capisco..
So che sembra che io non abbia aperto un libro ma non è assolutamente vero, sono mesi che cerco di capire questa materia studiando sul libro e cercando su internet ma non ci capisco assolutamente niente, forse mi mancano delle basi o forse sono proprio io scema ma ho proprio bisogno di qualcuno che me la spiega in maniera molto semplice, tutte le dispende o slide che ho trovato su internet sono complicate, c'è un sacco di teoria che non capisco..
Grazie!
sto studiando ricerca operativa e in particolare il metodo del simplesso e devo dire che ci sto capendo ben poco, di teoria non ci capisco nulla quindi in pratica (purtroppo!) sto studiando sugli esempi e non capisco questo esempio:
Il programma lineare
[tex]max z = 8x_1 + 3x_2[/tex]
soggetto a
[tex]4x_1 + 5x_2 \geq 10[/tex]
[tex]4x_1 + 10x_2 \geq 15[/tex]
[tex]x_2 \geq 1[/tex]
[tex]x_1, x_2 \geq 0[/tex]
equivale al seguente programma in forma standard.:
[tex]max z = 8x_1 + 3x_2[/tex]
soggetto a
[tex]4x_1 + 5x_2 + x_3 = 10[/tex]
[tex]4x_1 + 10x_2 + x_4 = 15[/tex]
[tex]x_2 + x_5 = 1[/tex]
[tex]x_1, ... , x_5 \geq 0[/tex]
Fino a qui ho capito, trasforma semplicemente un programma lineare in forma generica in uno in forma standard, ho fatto diversi esercizi di questo tipo e mi vengono. Ora va avanti in questo modo:
Si possono identificare le seguenti basi ammissibili:
[tex]\left \{ A_3, A_4, A_5 \right \} $=>$ A_B = $((1,0,0),(0,1,0),(0,0,1))$[/tex] x_B = $((x_3,x_4,x_5))$ = $((10,15,1))$
[tex]\left \{ A_2, A_3, A_4 \right \} $=>$ A_B = $((5,1,0),(10,0,1),(1,0,0))$[/tex] x_B = $((x_2,x_3,x_4))$ = $((1,5,5))$
[tex]\left \{ A_1, A_2, A_3 \right \} $=>$ A_B = $((4,5,1),(4,10,0),(0,1,0))$[/tex] x_B = $((x_1,x_2,x_3))$ = $((5/4,1,0))$
[tex]\left \{ A_1, A_2, A_4 \right \} $=>$ A_B = $((4,5,0),(4,10,1),(0,1,0))$[/tex] x_B = $((x_1,x_2,x_4))$ = $((5/4,1,0))$
[tex]\left \{ A_1, A_2, A_5 \right \} $=>$ A_B = $((4,5,0),(4,10,0),(0,1,1))$[/tex] x_B = $((x_1,x_2,x_5))$ = $((5/4,1,0))$
[tex]\left \{ A_1, A_4, A_5 \right \} $=>$ A_B = $((4,0,0),(4,1,0),(0,0,1))$[/tex] x_B = $((x_1,x_4,x_5))$ = $((5/2,5,1))$
(chiedo scusa se non ho scritto in modo giusto ma non riesco a capire dove sbaglio. A destra dove c'è [tex]x_B[/tex] i vettori dovrebbero essere in colonna e non in riga)
Non sono riportate esplicitamente le variabili fuori base, perchè esse hanno sempre valore [tex]0[/tex]. Si noti come le basi degeneri (dalla 3 alla 5) descrivano tutte la stessa soluzione, pur essendo basi distinte. E' invece una base non ammissibile, ad esempio, la
[tex]\left \{ A_1, A_3, A_5 \right \} $=>$ A_B = $((4,1,0),(4,0,0),(0,0,1))$[/tex] x_B = $((x_1,x_3,x_5))$ = $((15/4,-5,1))$
perchè la [tex]x_B[/tex] viola i vincoli di non-negatività.
Io ho capito che prende tre colonne (a caso?) e guarda i corrispettivi coefficienti nei vincoli e li mette nella matrice. Ma poi non capisco come ottiene [tex]x_B[/tex].
E non capisco nemmeno lo scopo finale dell'esercizio, questo è il metodo del simplesso? Non credo, cos'è allora quest'algoritmo del simplesso? Cosa sono le variabili fuori base, le basi degeneri, le basi non ammissibili ecc? Non capisco..
So che sembra che io non abbia aperto un libro ma non è assolutamente vero, sono mesi che cerco di capire questa materia studiando sul libro e cercando su internet ma non ci capisco assolutamente niente, forse mi mancano delle basi o forse sono proprio io scema ma ho proprio bisogno di qualcuno che me la spiega in maniera molto semplice, tutte le dispende o slide che ho trovato su internet sono complicate, c'è un sacco di teoria che non capisco..
Grazie!
Risposte
nessuna risposta? 
Va bè mi rispondo da sola..Forse ho capito!
[tex]x_b[/tex] è il risultato del sistema composto dai termini che considera e ponendo a 0 quelli che non considera..è corretto? Ma perchè sceglie proprio quelli? Per esempio, perchè sceglie [tex](A_3,A_4,A_5)[/tex], [tex](A_2,A_3,A_4)[/tex], [tex](A_1,A_2,A_3)[/tex] ecc.. e non (ad esempio) [tex](A_1,A_3,A_5)[/tex] ? C'è un motivo particolare?
[tex]x_b[/tex] è il risultato del sistema composto dai termini che considera e ponendo a 0 quelli che non considera..è corretto? Ma perchè sceglie proprio quelli? Per esempio, perchè sceglie [tex](A_3,A_4,A_5)[/tex], [tex](A_2,A_3,A_4)[/tex], [tex](A_1,A_2,A_3)[/tex] ecc.. e non (ad esempio) [tex](A_1,A_3,A_5)[/tex] ? C'è un motivo particolare?
Ciao,
vediamo un po'...
il testo è corretto? Se da dove lo hai preso è un esercizio risolubile secondo me è sbagliato (non ha vincoli ammissibili).
questa non è la forma standard di quel problema, casomai la forma slack, ma è sbagliata comunque
forma standard (si massimizza):
[tex]max z = 8x_1 + 3x_2[/tex]
soggetto a
[tex]-4x_1 - 5x_2 <= -10[/tex]
[tex]4x_1 + 10x_2 + x_4 <= -15[/tex]
[tex]-x_2 -x_5 <= -1[/tex]
[tex]x.. \geq 0[/tex]
[/quote]
forma slack:
[tex]max z = 8x_1 + 3x_2[/tex]
soggetto a
[tex]x_3 = 4x_1 + 5x_2 - 10[/tex]
[tex]x_4 = 4x_1 + 10x_2 - 15[/tex]
[tex]x_5 = x_2 -1[/tex]
[tex]x.. \geq 0[/tex]
non so se il problema è corretto perciò i conti non li guardo, casomai domani
Sì è l'algoritmo del simplesso, sotto certe condizioni da rispettare come formula slack e standard in input.
Spiegare si può anche fare, ma bisogna capire cosa non hai compreso. Le varibili di base sono quelle "a sinistra" dell'uguaglianza, quelle non di base "a destra" tipo... E' macchinoso il procedimento, è di più la teoria che ci sta sotto il difficile il resto sono calcoli (fino 3 varibili sono accettabili e va sotto il nome di "metodo algebrico", poi esistono i comodi computer...).
esatto questa è una soluzione di base ammissibile, durante il procedimento chiamato pivoting.
il motivo è che così si ha una scelta deterministica e prevedibile. Nel senso che i teoremi hanno una dimostrazione chiara e precisa se un problema è ammissibile, illimitato o inamissibile. Se non fosse così l'algoritmo potrebbe ciclare all'infinito, perciò esistono delle tecniche per scegliere la varibile uscente/entrante (base/non di base) in modo accurato. Se vuoi una regola semplice ed immediata cerca "regola di Bland". Di solito si può scegliere quello che minimizza maggiormente la variabile uscente (o entrante, dipende dal punto di vista) e che non renda negativo il termine noto.
E' un discorso lungo come vedi...se specifichi meglio i tuoi dubbi forse è più facile aiutarti.
PS: attenta a non fare UP dei post troppe volte nel giro di 24 ore, non è visto di buon occhio nel forum...
vediamo un po'...
"vfldj":
Il programma lineare
[tex]max z = 8x_1 + 3x_2[/tex]
soggetto a
[tex]4x_1 + 5x_2 \geq 10[/tex]
[tex]4x_1 + 10x_2 \geq 15[/tex]
[tex]x_2 \geq 1[/tex]
[tex]x_1, x_2 \geq 0[/tex]
il testo è corretto? Se da dove lo hai preso è un esercizio risolubile secondo me è sbagliato (non ha vincoli ammissibili).
equivale al seguente programma in forma standard.:
[tex]max z = 8x_1 + 3x_2[/tex]
soggetto a
[tex]4x_1 + 5x_2 + x_3 = 10[/tex]
[tex]4x_1 + 10x_2 + x_4 = 15[/tex]
[tex]x_2 + x_5 = 1[/tex]
[tex]x_1, ... , x_5 \geq 0[/tex]
questa non è la forma standard di quel problema, casomai la forma slack, ma è sbagliata comunque
forma standard (si massimizza):
[tex]max z = 8x_1 + 3x_2[/tex]
soggetto a
[tex]-4x_1 - 5x_2 <= -10[/tex]
[tex]4x_1 + 10x_2 + x_4 <= -15[/tex]
[tex]-x_2 -x_5 <= -1[/tex]
[tex]x.. \geq 0[/tex]
[/quote]
forma slack:
[tex]max z = 8x_1 + 3x_2[/tex]
soggetto a
[tex]x_3 = 4x_1 + 5x_2 - 10[/tex]
[tex]x_4 = 4x_1 + 10x_2 - 15[/tex]
[tex]x_5 = x_2 -1[/tex]
[tex]x.. \geq 0[/tex]
non so se il problema è corretto perciò i conti non li guardo, casomai domani
E non capisco nemmeno lo scopo finale dell'esercizio, questo è il metodo del simplesso? Non credo, cos'è allora quest'algoritmo del simplesso? Cosa sono le variabili fuori base, le basi degeneri, le basi non ammissibili ecc? Non capisco..
Sì è l'algoritmo del simplesso, sotto certe condizioni da rispettare come formula slack e standard in input.
Spiegare si può anche fare, ma bisogna capire cosa non hai compreso. Le varibili di base sono quelle "a sinistra" dell'uguaglianza, quelle non di base "a destra" tipo... E' macchinoso il procedimento, è di più la teoria che ci sta sotto il difficile il resto sono calcoli (fino 3 varibili sono accettabili e va sotto il nome di "metodo algebrico", poi esistono i comodi computer...).
"vfldj":
Va bè mi rispondo da sola..Forse ho capito!
[tex]x_b[/tex] è il risultato del sistema composto dai termini che considera e ponendo a 0 quelli che non considera..è corretto?
esatto questa è una soluzione di base ammissibile, durante il procedimento chiamato pivoting.
Ma perchè sceglie proprio quelli? Per esempio, perchè sceglie [tex](A_3,A_4,A_5)[/tex], [tex](A_2,A_3,A_4)[/tex], [tex](A_1,A_2,A_3)[/tex] ecc.. e non (ad esempio) [tex](A_1,A_3,A_5)[/tex] ? C'è un motivo particolare?
il motivo è che così si ha una scelta deterministica e prevedibile. Nel senso che i teoremi hanno una dimostrazione chiara e precisa se un problema è ammissibile, illimitato o inamissibile. Se non fosse così l'algoritmo potrebbe ciclare all'infinito, perciò esistono delle tecniche per scegliere la varibile uscente/entrante (base/non di base) in modo accurato. Se vuoi una regola semplice ed immediata cerca "regola di Bland". Di solito si può scegliere quello che minimizza maggiormente la variabile uscente (o entrante, dipende dal punto di vista) e che non renda negativo il termine noto.
E' un discorso lungo come vedi...se specifichi meglio i tuoi dubbi forse è più facile aiutarti.
PS: attenta a non fare UP dei post troppe volte nel giro di 24 ore, non è visto di buon occhio nel forum...
Ti ringrazio molto per la risposta..
Non farò più il reup..
L'esercizio si, è corretto..
Quando dici che non ha vincoli ammissibili cosa intendi? come lo capisci?
La differenza tra la forma standard e quella slack è semplicemente che nella forma slack esplicito i vincoli in funzione delle variabili slack? poi per il resto è uguale? Per usare il metodo del simplesso devo sempre passare dalla forma generica alla standard e poi a quella slack, giusto? Quindi alla fine lavoro sempre su max e mai su min perchè per trasformare in forma standard trasformo min in max, può essere? Se non è così (e quindi posso risolvere con il metodo del simplesso anche una funzione obbiettivo min) c'è qualche differenza con max? Quale? e poi se posso lavorare su min vuol dire che non trasformo in forma standard...
Io ho capito (non so è corretto) che le variabili di base sono quelle che "uso" (cioè quelle a sinistra dell'uguale) mentre quelle fuori base sono sempre uguali a 0 (non possono assumere valori diversi da 0) e non possono cambiare di numero. I miei dubbi sono:
- Come faccio a sapere quante variabili fuori base ho? sono, per caso, tante quante le variabili slack?
- Le variabili in base possono assumere valore negativo o nullo?
la regola di Bland in pratica dice che entra in base la variabile non di base con indice più piccolo tra quelle con coeff. di costo ridotto positivo ed esce quella con indice più piccolo..
Quindi le variabili con coeff nullo non le considero minimamente?
quindi se per esempio ho (ho messo numeri a caso):
[tex]max[/tex] [tex]z = 3 + 2x_1 - x_2 + 2x_5[/tex] e [tex]B^1 = (x_3, x_4)[/tex]
faccio entrare in base [tex]x_1[/tex] perchè sia [tex]x_1[/tex] che [tex]x_5[/tex] hanno coefficiente positivo ma [tex]x_1[/tex] ha indice minore.
faccio uscire la variabile [tex]x_3[/tex] perchè ha indice minore di [tex]x_4[/tex].
e se avessi (sempre se è possibile) una funzione che mi richiede il minimo? prendo sempre come variabile entrante una con coeff positivo?
Troppi dubbi..
Grazie
Non farò più il reup..
L'esercizio si, è corretto..
Quando dici che non ha vincoli ammissibili cosa intendi? come lo capisci?
La differenza tra la forma standard e quella slack è semplicemente che nella forma slack esplicito i vincoli in funzione delle variabili slack? poi per il resto è uguale? Per usare il metodo del simplesso devo sempre passare dalla forma generica alla standard e poi a quella slack, giusto? Quindi alla fine lavoro sempre su max e mai su min perchè per trasformare in forma standard trasformo min in max, può essere? Se non è così (e quindi posso risolvere con il metodo del simplesso anche una funzione obbiettivo min) c'è qualche differenza con max? Quale? e poi se posso lavorare su min vuol dire che non trasformo in forma standard...
Io ho capito (non so è corretto) che le variabili di base sono quelle che "uso" (cioè quelle a sinistra dell'uguale) mentre quelle fuori base sono sempre uguali a 0 (non possono assumere valori diversi da 0) e non possono cambiare di numero. I miei dubbi sono:
- Come faccio a sapere quante variabili fuori base ho? sono, per caso, tante quante le variabili slack?
- Le variabili in base possono assumere valore negativo o nullo?
la regola di Bland in pratica dice che entra in base la variabile non di base con indice più piccolo tra quelle con coeff. di costo ridotto positivo ed esce quella con indice più piccolo..
Quindi le variabili con coeff nullo non le considero minimamente?
quindi se per esempio ho (ho messo numeri a caso):
[tex]max[/tex] [tex]z = 3 + 2x_1 - x_2 + 2x_5[/tex] e [tex]B^1 = (x_3, x_4)[/tex]
faccio entrare in base [tex]x_1[/tex] perchè sia [tex]x_1[/tex] che [tex]x_5[/tex] hanno coefficiente positivo ma [tex]x_1[/tex] ha indice minore.
faccio uscire la variabile [tex]x_3[/tex] perchè ha indice minore di [tex]x_4[/tex].
e se avessi (sempre se è possibile) una funzione che mi richiede il minimo? prendo sempre come variabile entrante una con coeff positivo?
Troppi dubbi..
Grazie
"vfldj":
La differenza tra la forma standard e quella slack è semplicemente che nella forma slack esplicito i vincoli in funzione delle variabili slack? poi per il resto è uguale?
qui ti volevo dire che ho sbagliato a sottolinearti questo "errore". Sono andato a controllare se la terminologia è universalmente uguale, ma non è così. Alcuni autori utilizzano la "formula standard" per indicare la slack, la "formula canonica" o generale per indicare la standard. Ognuno utilizza quello che vuole...
Per le differenze, la formula standard è quella dove si utilizzano le disuguaglianze e si minimizza (altri adottano la massimizzazione come default, ma come ben sai la differenza è un $-$ (max f(x) = min -f(x))).
La formulazione slack è quella con uguaglianze.
per semplificare il tutto, scegli una terminologia ed una standardizzazione ed utilizza sempre quella (io su tre libri ne ho trovate tre differenti, per quello ho controllato non volevo farti cadere in errore).
Troppi dubbi..
lo ho notato, vedo dopo se riesco a scriverti qualcosa
Grazie 
vediamo un po'...
quando lo ho scritto avevo in mente un'altra cosa, che non ha senso in questo caso.
cmq un vincolo non ammissibile è tipo
$x + y <= -1$
$x,y >=0$
se ci sono termini noti $<0$ e i vincoli di non negatività si vede subito che il vincolo è inutile... (immagina la versione cartesiana, se ti è più facile).
Poi ci sono casi che può sembrare che un vincolo non è ammissibile per il problema, ma in questo caso si complicano le cose; che penso comunque non vedrai mai su di un esercizio che devi calcolare a mano...
sì, qui dipende da come sei abituata a ragionare.
Se la forma standard/generica la intendi con $min$ allora convergi sempre in questa forma, con $<=$ o $>=$ (tutti e due insieme non te lo consiglio).
Poi la slack viene da se...
la differenza tra min e max:
$max f(x) = - min -f(x)$
puoi lavorare con quello che vuoi, basta che ragioni di conseguenza con l'algoritmo. (*)
Poi se è già standardizzato come lo vuoi te, non serve trasformarlo...che ne dici
bhe all'inizializzazione del problema sono le variabili slack.
Poi ad ogni iterazione sono sempre quelle a sinistra, che si mescolano con quelle non-di-base che originariamente erano di base.
No! il vincolo di non-nagatività a che servirà mai?? (Sì per il valore nullo, con riserva mi hai fatto venire un dubbio...)
mi pare di sì. Ma è solo un consiglio usarla, era solo per darti una regola fissa
Io tipo se massimizzo, scelgo quella che mi aumenta il valore obbiettivo (variabile entrante), e il valore più piccole che diminuisce lo scarto.
per la verità non ho in mente casi che ci sia un coefficiente nullo, ma per logica direi di Sì.
mi pare di sì.
Io comunque considererei anche i valori nei vincoli, cioè quanto si "toglie" dai termini noti, ma è una regola come un'altra.
eh No!
Se minimizzi il fattore di terminazione del metodo è quando tutti i coefficienti sono positivi, e considererai solo i coefficienti negativi per la scelta di entrante/uscente (come dicevo (*) ragiona di conseguenza se massimizzi è un metodo, minimizzi è il contrario).
Devo dirti che mi hai fatto venire alcuni dubbi, con i tuoi dubbi
Se non ho scritto cose scorrette, questo è tutto, se hai domande...
PS: curisità, che libro hai utilizzato per studiare questo argomento?
"vfldj":
Quando dici che non ha vincoli ammissibili cosa intendi? come lo capisci?
quando lo ho scritto avevo in mente un'altra cosa, che non ha senso in questo caso.
cmq un vincolo non ammissibile è tipo
$x + y <= -1$
$x,y >=0$
se ci sono termini noti $<0$ e i vincoli di non negatività si vede subito che il vincolo è inutile... (immagina la versione cartesiana, se ti è più facile).
Poi ci sono casi che può sembrare che un vincolo non è ammissibile per il problema, ma in questo caso si complicano le cose; che penso comunque non vedrai mai su di un esercizio che devi calcolare a mano...
Per usare il metodo del simplesso devo sempre passare dalla forma generica alla standard e poi a quella slack, giusto? Quindi alla fine lavoro sempre su max e mai su min perchè per trasformare in forma standard trasformo min in max, può essere?
sì, qui dipende da come sei abituata a ragionare.
Se la forma standard/generica la intendi con $min$ allora convergi sempre in questa forma, con $<=$ o $>=$ (tutti e due insieme non te lo consiglio).
Poi la slack viene da se...
Se non è così (e quindi posso risolvere con il metodo del simplesso anche una funzione obbiettivo min) c'è qualche differenza con max? Quale? e poi se posso lavorare su min vuol dire che non trasformo in forma standard...
la differenza tra min e max:
$max f(x) = - min -f(x)$
puoi lavorare con quello che vuoi, basta che ragioni di conseguenza con l'algoritmo. (*)
Poi se è già standardizzato come lo vuoi te, non serve trasformarlo...che ne dici
Io ho capito (non so è corretto) che le variabili di base sono quelle che "uso" (cioè quelle a sinistra dell'uguale) mentre quelle fuori base sono sempre uguali a 0 (non possono assumere valori diversi da 0) e non possono cambiare di numero. I miei dubbi sono:
- Come faccio a sapere quante variabili fuori base ho? sono, per caso, tante quante le variabili slack?
bhe all'inizializzazione del problema sono le variabili slack.
Poi ad ogni iterazione sono sempre quelle a sinistra, che si mescolano con quelle non-di-base che originariamente erano di base.
- Le variabili in base possono assumere valore negativo o nullo?
No! il vincolo di non-nagatività a che servirà mai?? (Sì per il valore nullo, con riserva mi hai fatto venire un dubbio...)
la regola di Bland in pratica dice che entra in base la variabile non di base con indice più piccolo tra quelle con coeff. di costo ridotto positivo ed esce quella con indice più piccolo..
mi pare di sì. Ma è solo un consiglio usarla, era solo per darti una regola fissa
Io tipo se massimizzo, scelgo quella che mi aumenta il valore obbiettivo (variabile entrante), e il valore più piccole che diminuisce lo scarto.
Quindi le variabili con coeff nullo non le considero minimamente?
per la verità non ho in mente casi che ci sia un coefficiente nullo, ma per logica direi di Sì.
quindi se per esempio ho (ho messo numeri a caso):
[tex]max[/tex] [tex]z = 3 + 2x_1 - x_2 + 2x_5[/tex] e [tex]B^1 = (x_3, x_4)[/tex]
faccio entrare in base [tex]x_1[/tex] perchè sia [tex]x_1[/tex] che [tex]x_5[/tex] hanno coefficiente positivo ma [tex]x_1[/tex] ha indice minore.
faccio uscire la variabile [tex]x_3[/tex] perchè ha indice minore di [tex]x_4[/tex].
mi pare di sì.
Io comunque considererei anche i valori nei vincoli, cioè quanto si "toglie" dai termini noti, ma è una regola come un'altra.
e se avessi (sempre se è possibile) una funzione che mi richiede il minimo? prendo sempre come variabile entrante una con coeff positivo?
eh No!
Se minimizzi il fattore di terminazione del metodo è quando tutti i coefficienti sono positivi, e considererai solo i coefficienti negativi per la scelta di entrante/uscente (come dicevo (*) ragiona di conseguenza se massimizzi è un metodo, minimizzi è il contrario).
Devo dirti che mi hai fatto venire alcuni dubbi, con i tuoi dubbi
Se non ho scritto cose scorrette, questo è tutto, se hai domande...
PS: curisità, che libro hai utilizzato per studiare questo argomento?
Sei stato gentilissimo e chiarissimo!
è che non capendo la teoria facendo gli esercizi mi vengono 2 mila dubbi, non volevo farli venire pure a te!
Ho utilizzato delle dispense trovate su internet..
ora sto facendo un esercizio sempre di questo tipo ma mi sono bloccata -.- saresti così gentile da aiutarmi ancora? (si lo so che sono una palla)
è che non capendo la teoria facendo gli esercizi mi vengono 2 mila dubbi, non volevo farli venire pure a te!
Ho utilizzato delle dispense trovate su internet..
ora sto facendo un esercizio sempre di questo tipo ma mi sono bloccata -.- saresti così gentile da aiutarmi ancora? (si lo so che sono una palla
)
Io intanto lo posto poi vedi tu se hai tempo e voglia 
Sto cercando di risolvere sempre col metodo del Simplesso questo esercizio:
[tex][/tex]
[tex]min[/tex] [tex]3x_ + x_2 - 2x_3 - x_4[/tex]
vincoli
[tex]2x_1 + x_2 - x_3 + 3x_4 \le 8[/tex]
[tex]- x_1 + 2x_2 - 2x_3 + 2x_4 \le 4[/tex]
[tex]x_1 + x_3 \le 10[/tex]
[tex]x_1, ... , x_4 \geq 0[/tex]
in forma standard diventa (aggiungendo le variabili slack [tex]x_5, x_6, x_7[/tex]):
[tex]- max[/tex] [tex]- 3x_ - x_2 + 2x_3 + x_4[/tex]
vincoli
[tex]2x_1 + x_2 - x_3 + 3x_4 + x_5 = 8[/tex]
[tex]- x_1 + 2x_2 - 2x_3 + 2x_4 + x_6 = 4[/tex]
[tex]x_1 + x_3 + x_7 = 10[/tex]
[tex]x_1, ... , x_7 \geq 0[/tex]
Scelgo come basi [tex]B^0 = (x_5, x_6, x_7)[/tex] perchè sono le variabili slack e la matrice corrispondente diventa:
[tex]T(B^0) =[/tex] $((2,1,-1,3,1,0,0,|,8),(-1,2,-2,2,0,1,0,|,4),(1,0,1,0,0,0,1,|,10))$
e il sistema:
{ [tex]x_5 = 8 - 2x_1 - x_2 + x_3 -3x_4[/tex]
{ [tex]x_6 = 4 + x_1 - 2x_2 + 2x_3 - 2x_4[/tex]
{ [tex]x_7 = 10 - x_1 - x_3[/tex]
[tex]x_1, ... , x_7 \geq 0[/tex]
e la funzione obiettivo:
[tex]z = -3x_1 - x_2 + 2x_3 + x_4[/tex]
Ora siccome devo risolvere una funzione di massimo cerco il coeff positivo maggiore nella funzione obiettivo: [tex]x_3[/tex]. Perciò faccio entrare in base [tex]x_3[/tex] e faccio uscire cosa? io ho fatto uscire [tex]x_6[/tex] ma non chiedetemi il perchè
Quindi ora ho [tex]B^1 = (x_5, x_3, x_7)[/tex]
Sapendo che le colonne corrispondenti alle variabili in base [tex](x_5, x_3, x_7)[/tex] devono essere "ridotte", modifico la matrice [tex]T(B^0) =[/tex] in modo tale da ottenere questa (che non so se è giusta):
[tex]T(B^1) =[/tex] $((2,1,-1,3,1,0,0,|,8),(1/2,-1,1,-1,0,-1/2,0,|,-2),(1/2,-1,0,-1,0,-1/2,1,|,12))$
e il sistema corrispondente:
{ [tex]x_5 = 8 - 2x_1 - x_2 + x_3 -3x_4[/tex]
{ [tex]x_3 = -2 - 1/2x_1 + x_2 + x_4 + 1/2x_6[/tex]
{ [tex]x_7 = 12 - 1/2x_1 + x_2 + x_4 + 1/2x_6[/tex]
la funzione obbiettivo ottenuta sostituendo nella precedente funz.ob. il valore di [tex]x_3[/tex] appena ottenuto:
[tex]z = - 4x_1 + x_2 + 3x_4 + x_6 - 4[/tex]
Ora devo guardare se ci sono coeff positivi in [tex]z[/tex]. Ci sono e sono anche tanti quindi secondo me mi sto solo incasinando e non sto andando avanti. Comunque procederei in questo modo: la variabile con coeff positivo maggiore è [tex]x_4[/tex] quindi faccio entrare lei e faccio uscire quale?
E poi come scelgo ora il pivot?
Sto cercando di risolvere sempre col metodo del Simplesso questo esercizio:
[tex][/tex]
[tex]min[/tex] [tex]3x_ + x_2 - 2x_3 - x_4[/tex]
vincoli
[tex]2x_1 + x_2 - x_3 + 3x_4 \le 8[/tex]
[tex]- x_1 + 2x_2 - 2x_3 + 2x_4 \le 4[/tex]
[tex]x_1 + x_3 \le 10[/tex]
[tex]x_1, ... , x_4 \geq 0[/tex]
in forma standard diventa (aggiungendo le variabili slack [tex]x_5, x_6, x_7[/tex]):
[tex]- max[/tex] [tex]- 3x_ - x_2 + 2x_3 + x_4[/tex]
vincoli
[tex]2x_1 + x_2 - x_3 + 3x_4 + x_5 = 8[/tex]
[tex]- x_1 + 2x_2 - 2x_3 + 2x_4 + x_6 = 4[/tex]
[tex]x_1 + x_3 + x_7 = 10[/tex]
[tex]x_1, ... , x_7 \geq 0[/tex]
Scelgo come basi [tex]B^0 = (x_5, x_6, x_7)[/tex] perchè sono le variabili slack e la matrice corrispondente diventa:
[tex]T(B^0) =[/tex] $((2,1,-1,3,1,0,0,|,8),(-1,2,-2,2,0,1,0,|,4),(1,0,1,0,0,0,1,|,10))$
e il sistema:
{ [tex]x_5 = 8 - 2x_1 - x_2 + x_3 -3x_4[/tex]
{ [tex]x_6 = 4 + x_1 - 2x_2 + 2x_3 - 2x_4[/tex]
{ [tex]x_7 = 10 - x_1 - x_3[/tex]
[tex]x_1, ... , x_7 \geq 0[/tex]
e la funzione obiettivo:
[tex]z = -3x_1 - x_2 + 2x_3 + x_4[/tex]
Ora siccome devo risolvere una funzione di massimo cerco il coeff positivo maggiore nella funzione obiettivo: [tex]x_3[/tex]. Perciò faccio entrare in base [tex]x_3[/tex] e faccio uscire cosa? io ho fatto uscire [tex]x_6[/tex] ma non chiedetemi il perchè
Quindi ora ho [tex]B^1 = (x_5, x_3, x_7)[/tex]
Sapendo che le colonne corrispondenti alle variabili in base [tex](x_5, x_3, x_7)[/tex] devono essere "ridotte", modifico la matrice [tex]T(B^0) =[/tex] in modo tale da ottenere questa (che non so se è giusta):
[tex]T(B^1) =[/tex] $((2,1,-1,3,1,0,0,|,8),(1/2,-1,1,-1,0,-1/2,0,|,-2),(1/2,-1,0,-1,0,-1/2,1,|,12))$
e il sistema corrispondente:
{ [tex]x_5 = 8 - 2x_1 - x_2 + x_3 -3x_4[/tex]
{ [tex]x_3 = -2 - 1/2x_1 + x_2 + x_4 + 1/2x_6[/tex]
{ [tex]x_7 = 12 - 1/2x_1 + x_2 + x_4 + 1/2x_6[/tex]
la funzione obbiettivo ottenuta sostituendo nella precedente funz.ob. il valore di [tex]x_3[/tex] appena ottenuto:
[tex]z = - 4x_1 + x_2 + 3x_4 + x_6 - 4[/tex]
Ora devo guardare se ci sono coeff positivi in [tex]z[/tex]. Ci sono e sono anche tanti quindi secondo me mi sto solo incasinando e non sto andando avanti. Comunque procederei in questo modo: la variabile con coeff positivo maggiore è [tex]x_4[/tex] quindi faccio entrare lei e faccio uscire quale?
E poi come scelgo ora il pivot?
allora (ti dico che con il metodo che si utilizza di solito per schematizzare delle tableau/matriciale sono arrugginito (è da quando ho fatto l'esame che non pratico...) perciò al massimo utilizzo il sistema grezzo delle equazioni direttamente).
ok, ragioniamo per massimizzare il valore obbiettivo.
ok.
ok, più corretto dire di scegliere il coefficiente che fa crescere maggiormente il valore obbiettivo.
qua si basano le varie regole deterministiche (di Bland, ed altre). A caso è anche una possibilità, ma anche in questo frangente deve esserci una logica ed un controllo.
Questo controllo è l'incremento dello scarto ($4$) della variabile di base ($x_6$) da quella non di base ($x_3$).
Qua non c'è nessuno scarto, come vedi aumentando $x_4$ (c'è un $+$) crescera anche la variabile di base: il problema diverrebbe illimitato.
anche scegliendo $x_5$ stesso discorso. L'unica possibilità è $x_7$.
Perciò:
- considera solo le variabili entranti (non di base in questa iterazione) con coefficiente negativo
- considera quella dove lo scarto tra il termine noto ed il coefficiente è minimo.
Sì, per continuare il metodo.
Prova ora se ti è più chiaro, se hai domande...
"vfldj":
Sto cercando di risolvere sempre col metodo del Simplesso questo esercizio:
[tex][/tex]
[tex]min[/tex] [tex]3x_ + x_2 - 2x_3 - x_4[/tex]
vincoli
[tex]2x_1 + x_2 - x_3 + 3x_4 \le 8[/tex]
[tex]- x_1 + 2x_2 - 2x_3 + 2x_4 \le 4[/tex]
[tex]x_1 + x_3 \le 10[/tex]
[tex]x_1, ... , x_4 \geq 0[/tex]
in forma standard diventa (aggiungendo le variabili slack [tex]x_5, x_6, x_7[/tex]):
[tex]- max[/tex] [tex]- 3x_ - x_2 + 2x_3 + x_4[/tex]
vincoli
[tex]2x_1 + x_2 - x_3 + 3x_4 + x_5 = 8[/tex]
[tex]- x_1 + 2x_2 - 2x_3 + 2x_4 + x_6 = 4[/tex]
[tex]x_1 + x_3 + x_7 = 10[/tex]
[tex]x_1, ... , x_7 \geq 0[/tex]
ok, ragioniamo per massimizzare il valore obbiettivo.
Scelgo come basi [tex]B^0 = (x_5, x_6, x_7)[/tex] perchè sono le variabili slack e la matrice corrispondente diventa:
[tex]T(B^0) =[/tex] $((2,1,-1,3,1,0,0,|,8),(-1,2,-2,2,0,1,0,|,4),(1,0,1,0,0,0,1,|,10))$
e il sistema:
{ [tex]x_5 = 8 - 2x_1 - x_2 + x_3 -3x_4[/tex]
{ [tex]x_6 = 4 + x_1 - 2x_2 + 2x_3 - 2x_4[/tex]
{ [tex]x_7 = 10 - x_1 - x_3[/tex]
[tex]x_1, ... , x_7 \geq 0[/tex]
e la funzione obiettivo:
[tex]z = -3x_1 - x_2 + 2x_3 + x_4[/tex]
ok.
Ora siccome devo risolvere una funzione di massimo cerco il coeff positivo maggiore nella funzione obiettivo: [tex]x_3[/tex]. Perciò faccio entrare in base [tex]x_3[/tex]
ok, più corretto dire di scegliere il coefficiente che fa crescere maggiormente il valore obbiettivo.
e faccio uscire cosa? io ho fatto uscire [tex]x_6[/tex] ma non chiedetemi il perchè
qua si basano le varie regole deterministiche (di Bland, ed altre). A caso è anche una possibilità, ma anche in questo frangente deve esserci una logica ed un controllo.
Questo controllo è l'incremento dello scarto ($4$) della variabile di base ($x_6$) da quella non di base ($x_3$).
Qua non c'è nessuno scarto, come vedi aumentando $x_4$ (c'è un $+$) crescera anche la variabile di base: il problema diverrebbe illimitato.
anche scegliendo $x_5$ stesso discorso. L'unica possibilità è $x_7$.
Perciò:
- considera solo le variabili entranti (non di base in questa iterazione) con coefficiente negativo
- considera quella dove lo scarto tra il termine noto ed il coefficiente è minimo.
Ora devo guardare se ci sono coeff positivi in [tex]z[/tex].
Sì, per continuare il metodo.
Prova ora se ti è più chiaro, se hai domande...
la soluzione dell'esercizio dice che le basi finali sono [tex](x_4, x_6, x_3)[/tex] con [tex]x_3 = 10, x_4 = 6, x_6 = 12[/tex].
Le basi mi risultano ma le soluzioni no perchè mi vengono [tex]x_3 = 10, x_4 = 6, x_6 = -12[/tex] (e [tex]x_6[/tex] non può essere negativo perchè infrangerebbe i vincoli) quindi devo aver fatto qualche errore di calcolo stupido..comunque ti ringrazio infinitamente, grazie per la tua paienza
Le basi mi risultano ma le soluzioni no perchè mi vengono [tex]x_3 = 10, x_4 = 6, x_6 = -12[/tex] (e [tex]x_6[/tex] non può essere negativo perchè infrangerebbe i vincoli) quindi devo aver fatto qualche errore di calcolo stupido..comunque ti ringrazio infinitamente, grazie per la tua paienza
Per completezza allora ti riporto l'esercizio come lo ho risolto io, nella tua risposta manca la parte finale (devi ricordare che hai riscritto il problema).
$min{3x_1 + x_2 - 2x_3 - x_4}$
${(2x_1 + x_2 - x_3 + 3x_4 <= 8),(-x_1 + 2x_2 - 2x_3 + 2x_4 <= 4),(x_1 + x_3 <= 10),(x_i >= 0\ |\ i=1..4):}$
volendo convergerci alla formulazione standard dove si massimizza, convertiamo il problema moltiplicando la funzione per $-1$ e ricordandoci che anche il valore obbiettivo sarà negativo perciò:
$-max{-3x_1 - x_2 + 2x_3 + x_4}$
${(2x_1 + x_2 - x_3 + 3x_4 <= 8),(-x_1 + 2x_2 - 2x_3 + 2x_4 <= 4),(x_1 + x_3 <= 10),(x_i >= 0\ |\ i=1..4):}$
lo trasformiamo in forma slack, volendo risolverlo con il metodo algebrico, aggiungendo tre variabili slack uguale al numero di vincoli:
$z = -3x_1 - x_2 + 2x_3 + x_4$
${(x_5 = 8 - 2x_1 - x_2 + x_3 - 3x_4),(x_6 = 4 + x_1 - 2x_2 + 2x_3 - 2x_4),(x_7 = 10 - x_1 - x_3),(x_i >= 0\ |\ i=1..7):}$
Ora iniziamo le iterazioni:
$z = -3x_1 - x_2 + 2x_3 + x_4$
${(x_5 = 8 - 2x_1 - x_2 + x_3 - 3x_4),(x_6 = 4 + x_1 - 2x_2 + 2x_3 - 2x_4),(x_7 = 10 - x_1 - x_3),(x_i >= 0\ |\ i=1..7):}$
$B={x_5,x_6,x_7}$ e $N={x_1,x_2,x_3,x_4}$
soluzione di base: $(0,0,0,0,8,4,10)$ trovata azzerando le variabili non-di-base e $z=0$
valutando il passo successivo, scegliamo le variabili entrante $E$ ed uscente $L$:
- $E$: tra i coefficienti della f.obbiettivo scegliamo quello positivo più alto, così facendo siamo sicuri che il valore obbiettivo crescerà. In questo caso abbiamo $+2x_3$ e $+x_4$ ovviamente scegliamo $E={x_3}$
- $U$: tra i vari criteri, scegliamo quello che minimizza lo scarto per evitare che la variabile di base diventi inamissibile diventando negativa. Allora considerando $E={x_3}$:
$U={x_5}$
$x_5 = 8 + x_3\ |\ oo$ si nota che con l'aumentare di $x_3$ aumenterà anche lo scarto verso l'infinito ed oltre.
$U={x_6}$
$x_6 = 4 + 2x_3\ |\ oo$ si nota che con l'aumentare ....
$U={x_7}$
$x_7 = 10 - x_3\ |\ 10$ si nota che la variabile dieverrà negativa con $x_3>10$
Essendo l'unica scelta possibile scegliamo $x_7$.
sostituiamo e andiamo avanti:
$z = 20 - 6x_1 - x_2 + x_4 - 2x_7$
${(x_3 = 10 - x_1 - x_7),(x_5 = 18 - 3x_1 - x_2 - 3x_4 - x_7),(x_6 = 24 - x_1 - 2x_2 - 2x_4 - 2x_7),(x_i >= 0\ |\ i=1..7):}$
$B={x_3,x_5,x_6}$ e $N={x_1,x_2,x_4,x_7}$
soluzione di base: $(0,0,10,0,18,24,0)$ trovata azzerando le variabili non-di-base e $z=20$
$E={x_4}$ unisca scelta possibile.
$U={x_5}$
$x_5 = 18 - 3x_4\ |\ 9$
$U={x_6}$
$x_6 = 24 - 2x_4\ |\ 12$
nei due casi $x_6$ diverrà inamissibile con $x_4>12$ oppure $x_4>9$, scegliamo quello minore perciò: $U={x_5}$
$z = 26 - 7x_1 - 4/3x_2 - 1/3x_5 - 7/3x_7$
${(x_3 = 10 - x_1 - x_7),(x_4 = 6 - x_1 - 1/3x_2 - 1/3x_5 - 1/3x_7),(x_6 = 10 + x_1 - 4/3x_2 + 2/3x_5 - 4/3x_7),(x_i >= 0\ |\ i=1..7):}$
$B={x_3,x_4,x_6}$ e $N={x_1,x_2,x_5,x_7}$
soluzione di base: $(0,0,10,6,0,10,0)$ trovata azzerando le variabili non-di-base e $z=26$
Notando che l'equazione $z$ ha tutte le variabili negative siamo arrivati al fattore di terminazione, perciò:
$(0,0,10,6,0,10,0)$ è la soluzione ottima e il valore obbiettivo ottimo è $z=26$
Ricordandoci che abbiamo riscritto il problema da $min$ a $max$ dobbiamo moltiplicare il valore ob. per $-1$ così facendo abbiamo la soluzione del problema originale:
$x*=(0,0,10,6)$ e $z*=-26$
questo è tutto
$min{3x_1 + x_2 - 2x_3 - x_4}$
${(2x_1 + x_2 - x_3 + 3x_4 <= 8),(-x_1 + 2x_2 - 2x_3 + 2x_4 <= 4),(x_1 + x_3 <= 10),(x_i >= 0\ |\ i=1..4):}$
volendo convergerci alla formulazione standard dove si massimizza, convertiamo il problema moltiplicando la funzione per $-1$ e ricordandoci che anche il valore obbiettivo sarà negativo perciò:
$-max{-3x_1 - x_2 + 2x_3 + x_4}$
${(2x_1 + x_2 - x_3 + 3x_4 <= 8),(-x_1 + 2x_2 - 2x_3 + 2x_4 <= 4),(x_1 + x_3 <= 10),(x_i >= 0\ |\ i=1..4):}$
lo trasformiamo in forma slack, volendo risolverlo con il metodo algebrico, aggiungendo tre variabili slack uguale al numero di vincoli:
$z = -3x_1 - x_2 + 2x_3 + x_4$
${(x_5 = 8 - 2x_1 - x_2 + x_3 - 3x_4),(x_6 = 4 + x_1 - 2x_2 + 2x_3 - 2x_4),(x_7 = 10 - x_1 - x_3),(x_i >= 0\ |\ i=1..7):}$
Ora iniziamo le iterazioni:
$z = -3x_1 - x_2 + 2x_3 + x_4$
${(x_5 = 8 - 2x_1 - x_2 + x_3 - 3x_4),(x_6 = 4 + x_1 - 2x_2 + 2x_3 - 2x_4),(x_7 = 10 - x_1 - x_3),(x_i >= 0\ |\ i=1..7):}$
$B={x_5,x_6,x_7}$ e $N={x_1,x_2,x_3,x_4}$
soluzione di base: $(0,0,0,0,8,4,10)$ trovata azzerando le variabili non-di-base e $z=0$
valutando il passo successivo, scegliamo le variabili entrante $E$ ed uscente $L$:
- $E$: tra i coefficienti della f.obbiettivo scegliamo quello positivo più alto, così facendo siamo sicuri che il valore obbiettivo crescerà. In questo caso abbiamo $+2x_3$ e $+x_4$ ovviamente scegliamo $E={x_3}$
- $U$: tra i vari criteri, scegliamo quello che minimizza lo scarto per evitare che la variabile di base diventi inamissibile diventando negativa. Allora considerando $E={x_3}$:
$U={x_5}$
$x_5 = 8 + x_3\ |\ oo$ si nota che con l'aumentare di $x_3$ aumenterà anche lo scarto verso l'infinito ed oltre.
$U={x_6}$
$x_6 = 4 + 2x_3\ |\ oo$ si nota che con l'aumentare ....
$U={x_7}$
$x_7 = 10 - x_3\ |\ 10$ si nota che la variabile dieverrà negativa con $x_3>10$
Essendo l'unica scelta possibile scegliamo $x_7$.
sostituiamo e andiamo avanti:
$z = 20 - 6x_1 - x_2 + x_4 - 2x_7$
${(x_3 = 10 - x_1 - x_7),(x_5 = 18 - 3x_1 - x_2 - 3x_4 - x_7),(x_6 = 24 - x_1 - 2x_2 - 2x_4 - 2x_7),(x_i >= 0\ |\ i=1..7):}$
$B={x_3,x_5,x_6}$ e $N={x_1,x_2,x_4,x_7}$
soluzione di base: $(0,0,10,0,18,24,0)$ trovata azzerando le variabili non-di-base e $z=20$
$E={x_4}$ unisca scelta possibile.
$U={x_5}$
$x_5 = 18 - 3x_4\ |\ 9$
$U={x_6}$
$x_6 = 24 - 2x_4\ |\ 12$
nei due casi $x_6$ diverrà inamissibile con $x_4>12$ oppure $x_4>9$, scegliamo quello minore perciò: $U={x_5}$
$z = 26 - 7x_1 - 4/3x_2 - 1/3x_5 - 7/3x_7$
${(x_3 = 10 - x_1 - x_7),(x_4 = 6 - x_1 - 1/3x_2 - 1/3x_5 - 1/3x_7),(x_6 = 10 + x_1 - 4/3x_2 + 2/3x_5 - 4/3x_7),(x_i >= 0\ |\ i=1..7):}$
$B={x_3,x_4,x_6}$ e $N={x_1,x_2,x_5,x_7}$
soluzione di base: $(0,0,10,6,0,10,0)$ trovata azzerando le variabili non-di-base e $z=26$
Notando che l'equazione $z$ ha tutte le variabili negative siamo arrivati al fattore di terminazione, perciò:
$(0,0,10,6,0,10,0)$ è la soluzione ottima e il valore obbiettivo ottimo è $z=26$
Ricordandoci che abbiamo riscritto il problema da $min$ a $max$ dobbiamo moltiplicare il valore ob. per $-1$ così facendo abbiamo la soluzione del problema originale:
$x*=(0,0,10,6)$ e $z*=-26$
questo è tutto
"hamming_burst":
$U={x_5}$
$x_5 = 8 + x_3\ |\ oo$ si nota che con l'aumentare di $x_3$ aumenterà anche lo scarto verso l'infinito ed oltre.
$U={x_6}$
$x_6 = 4 + 2x_3\ |\ oo$ si nota che con l'aumentare ....
$U={x_7}$
$x_7 = 10 - x_3\ |\ 10$ si nota che la variabile dieverrà negativa con $x_3>10$
$U={x_5}$
$x_5 = 18 - 3x_4\ |\ 9$
$U={x_6}$
$x_6 = 24 - 2x_4\ |\ 12$
i valori 10 e 9 e 12 li hai ottenuti dividendo i valori delle variabili uscenti che stavi considerando con i coefficienti della variabile entrante [tex]E[/tex]. Ma perchè?
"vfldj":
i valori 10 e 9 e 12 li hai ottenuti dividendo i valori delle variabili uscenti che stavi considerando con i coefficienti della variabile entrante [tex]E[/tex]. Ma perchè?
E' un modo come un altro, ti ho ben scritto che ce ne sono alcuni, questo almento da una regola fissa con una "logica matematica" e un limite su cosa scegliere. Puoi andare anche a caso, è una regola anche quella... ma non si avrà la convergenza all'ottimo (non sono garantiti).
per la sostituzione è come hai detto ho riscritto l'equazione in funzione della variabile entrante. Non so se hai compreso cosa sia lo scarto (slack), si cerca di limitare questo la differenza con il termine noto, per evitare che le variabili diventino negative dopo qualche passo (per questo si sceglie il minore).
Avrei anche un'altra domanda:
se mi si chiede di risolvere un problema con il metodo del Simplesso e questo problema è già in forma standard (quindi non ho variabili slack), come faccio a sapere quante variabili di base ho? Sono tante quante il numero dei vincoli?
se mi si chiede di risolvere un problema con il metodo del Simplesso e questo problema è già in forma standard (quindi non ho variabili slack), come faccio a sapere quante variabili di base ho? Sono tante quante il numero dei vincoli?
"vfldj":
Avrei anche un'altra domanda:
se mi si chiede di risolvere un problema con il metodo del Simplesso e questo problema è già in forma standard (quindi non ho variabili slack), come faccio a sapere quante variabili di base ho? Sono tante quante il numero dei vincoli?
mmm mi sa che non hai compreso fino in fondo cosia sia sta forma slack...
dimmi, secondo te quante dovrebbero essere le variabili di base?
comunque se hai la forma standard, trasformarla in slack aggiungi variabili slack (che saranno definite "di base" alla prima iterazione del metodo) ad ogni vincolo mettendo l'uguaglianza (non contando i vincoli di non-negatività).
ah ok ok capito grazie grazie grazie
grazie grazie grazie
che sincronia 
ho modificato il post mentre hai risposto...
cmq di nulla, se hai compreso tutto, son contento.
Se avrai ancora dubbi basta postare
ho modificato il post mentre hai risposto...
cmq di nulla, se hai compreso tutto, son contento.
Se avrai ancora dubbi basta postare
grazie ancora, per ora non ho dubbi
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo