Soluzione ammissibile non di base
"Dato il problema di PLC
$max(Z=-x+y)$
$x-2y<=4$
$-2x-y+z>=1$
$x+z<=2$
con $x,y,z$ non negative.
Si determini una soluzione ammissibile non di base."
Io so che le soluzioni ammissibili sono tutte quelle che soddisfano i vincoli, quelle di base sono quelle, tra le precedenti che coincidono con i vertici della regione di ammissibilità e che sono identificabili mediante l'algoritmo del simplesso. Un vertice è, per motivi geometrici, l'intersezione di tanti vincoli quante sono le variabili. Per risolvere il problema io potrei:
1)Andare per tentativi avendo cura che tutti i vincoli siano rispettati e al massimo 2 di loro siano soddisfatti come equazione
2)Inserire un quarto vincolo (e come sceglierlo in modo furbo? )che tagli la regione di ammissibilità aggiungendo 2 nuovi vertici che corrisponderebbero a 2 soluzioni non di base per il precedente problema e che potrei raggiungere (forse) con $n$ iterazioni del simplesso.
3)Utilizzare un metodo che non conosco
Qualche suggerimento?
$max(Z=-x+y)$
$x-2y<=4$
$-2x-y+z>=1$
$x+z<=2$
con $x,y,z$ non negative.
Si determini una soluzione ammissibile non di base."
Io so che le soluzioni ammissibili sono tutte quelle che soddisfano i vincoli, quelle di base sono quelle, tra le precedenti che coincidono con i vertici della regione di ammissibilità e che sono identificabili mediante l'algoritmo del simplesso. Un vertice è, per motivi geometrici, l'intersezione di tanti vincoli quante sono le variabili. Per risolvere il problema io potrei:
1)Andare per tentativi avendo cura che tutti i vincoli siano rispettati e al massimo 2 di loro siano soddisfatti come equazione
2)Inserire un quarto vincolo (e come sceglierlo in modo furbo? )che tagli la regione di ammissibilità aggiungendo 2 nuovi vertici che corrisponderebbero a 2 soluzioni non di base per il precedente problema e che potrei raggiungere (forse) con $n$ iterazioni del simplesso.
3)Utilizzare un metodo che non conosco
Qualche suggerimento?
Risposte
Scusami non mi torna qualcosa.
Nel problema, nella funzione obbiettivo, manca la variabile $z$. Come fà ad esserci nelle condizioni una variabile $z$ non presente nella funzione da massimizzare?
Non ho mai sentito parlare di una "soluzione ammissibile" di base e non di base. Forse si riferisce ad un qualunque vertice del simplesso che soddisfi i vincoli, senza che sia l'ottimo.
Poi vedo che il problema non è in forma standard, perciò forse la variabile $z$ si può farla saltar fuori tramite un valore slack.
Se mi dici qual'è la definizione esatta di soluzione di base e non di base, essendo un problema di PL normale, forse posso dare una mano
Nel problema, nella funzione obbiettivo, manca la variabile $z$. Come fà ad esserci nelle condizioni una variabile $z$ non presente nella funzione da massimizzare?
Non ho mai sentito parlare di una "soluzione ammissibile" di base e non di base. Forse si riferisce ad un qualunque vertice del simplesso che soddisfi i vincoli, senza che sia l'ottimo.
Poi vedo che il problema non è in forma standard, perciò forse la variabile $z$ si può farla saltar fuori tramite un valore slack.
Se mi dici qual'è la definizione esatta di soluzione di base e non di base, essendo un problema di PL normale, forse posso dare una mano
Grazie.
$z$ semplicemente influisce sui vincoli ma non sulla funzione obbiettivo. Come dicevo, la differenza tra una soluzione di base e una non di base, che io sappia, è data dal fatto che la prima coincide con un vertice, la seconda no.
$z$ semplicemente influisce sui vincoli ma non sulla funzione obbiettivo. Come dicevo, la differenza tra una soluzione di base e una non di base, che io sappia, è data dal fatto che la prima coincide con un vertice, la seconda no.
Una strada potrebbe essere questa.
Mi trovo due soluzioni ammissibili di base. Distinte. Sperando si possa.
Poi prendo il punto medio. Ho buone chance (su un pb così piccolo) che non sia di base. Che sia ammissibile, no pb: l'insieme dei punti che soddisfano il vincolo è un inseme convesso.
Sennò, provo un'altra combinazione convessa dei due punti troovati.
Mi trovo due soluzioni ammissibili di base. Distinte. Sperando si possa.
Poi prendo il punto medio. Ho buone chance (su un pb così piccolo) che non sia di base. Che sia ammissibile, no pb: l'insieme dei punti che soddisfano il vincolo è un inseme convesso.
Sennò, provo un'altra combinazione convessa dei due punti troovati.
Geniale! Credo sia un algoritmo perfetto nel mio caso, perchè con il metodo del simplesso un'iterazione conduce, geometricamente parlando, da un vertice (soluzione di base) ad un altro vertice adiacente, a meno di casi degeneri. Se questa operazione è possibile, il punto medio deve essere necessariamente una soluzione non di base!
Grazie mille
Grazie mille
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo