Ancora Ricerca Operativa
Perdonatemi ma lunedì ho l'esame...
Si descriva il seguente tableau e in base alla descrizione dire se è possibile operare
ulteriormente sul tableau, se possibile indicare la soluzione ottima.
Dunque... La mia descrizione è questa. Dal tableau si evince che le variabili attualmente
in base sono $x_1$ e $x_2$ (i coefficienti a loro associati costituiscono una
matrice identità, ed essendo il tableau a tre righe (inclusa la riga 0, cioè quella della
funzione obiettivo) non potrebbe essere in base anche $x_4$ che ha costo 0 nella funzione obiettivo),
mentre $x_3,x_4,x_5$ sono non in base. In particolare la presenza del costo nullo di $x_4$,
variabile non in base, fa sì che il problema ammetta ottimi multipli. Nel caso di un problema di minimo,
una soluzione ottima è già data dal tableau così com'è, infatti le variabili nella funzione
obiettivo non hanno costi negativi, e la soluzione è: $x_1=2,x_2=3,x_3=x_4=x_5=0,z=-6$.
Nel caso di un problema di massimo, ci si riconduce ad un problema di minimo
determinando l'opposto del minimo dell'opposto della funzione obiettivo. Seguendo
questa procedura (attraverso il metodo del simplesso, ovviamente) mi trovo
che una soluzione ottima del problema di massimo è: $z=2,x_1=x_2=x_5=0,x_3=8/3,x_4=1/3$.
Anche qui, nell'ultimo tableau corrispondente all'ultima iterazione del simplesso si vede che il coefficiente
della variabile non in base $x_5$ nella funzione obiettivo (ovvero il suo costo) è 0, e
questo di nuovo mostra che esistono ottimi multipli.
Vi torna tutto?
Si descriva il seguente tableau e in base alla descrizione dire se è possibile operare
ulteriormente sul tableau, se possibile indicare la soluzione ottima.
Dunque... La mia descrizione è questa. Dal tableau si evince che le variabili attualmente
in base sono $x_1$ e $x_2$ (i coefficienti a loro associati costituiscono una
matrice identità, ed essendo il tableau a tre righe (inclusa la riga 0, cioè quella della
funzione obiettivo) non potrebbe essere in base anche $x_4$ che ha costo 0 nella funzione obiettivo),
mentre $x_3,x_4,x_5$ sono non in base. In particolare la presenza del costo nullo di $x_4$,
variabile non in base, fa sì che il problema ammetta ottimi multipli. Nel caso di un problema di minimo,
una soluzione ottima è già data dal tableau così com'è, infatti le variabili nella funzione
obiettivo non hanno costi negativi, e la soluzione è: $x_1=2,x_2=3,x_3=x_4=x_5=0,z=-6$.
Nel caso di un problema di massimo, ci si riconduce ad un problema di minimo
determinando l'opposto del minimo dell'opposto della funzione obiettivo. Seguendo
questa procedura (attraverso il metodo del simplesso, ovviamente) mi trovo
che una soluzione ottima del problema di massimo è: $z=2,x_1=x_2=x_5=0,x_3=8/3,x_4=1/3$.
Anche qui, nell'ultimo tableau corrispondente all'ultima iterazione del simplesso si vede che il coefficiente
della variabile non in base $x_5$ nella funzione obiettivo (ovvero il suo costo) è 0, e
questo di nuovo mostra che esistono ottimi multipli.
Vi torna tutto?
Risposte
Si, ok.
Hai già fatto la dualità?
Hai già fatto la dualità?
No, ma ha cominciato a spiegarla, è argomento
del secondo esonero... Come hai fatto a correggere
il mio esercizio, con un programma al PC? Lindo per esempio?
del secondo esonero... Come hai fatto a correggere
il mio esercizio, con un programma al PC? Lindo per esempio?
No, mi sono fidato dei tuoi calcoli.
Il procedimento è formalmente corretto.
Esistono comunque decine di programmi per risolvere i problemi di PL.
Lindo va bene, ma è proprio "scolastico".
Esiste Lingo, che è Lindo ma che consente di risolvere anche problemi con funzione obiettivo non lineare.
Inoltre esistono diversi "solver", tra cui Cplex, che hanno raggiunto prestazioni elevate.
Il procedimento è formalmente corretto.
Esistono comunque decine di programmi per risolvere i problemi di PL.
Lindo va bene, ma è proprio "scolastico".
Esiste Lingo, che è Lindo ma che consente di risolvere anche problemi con funzione obiettivo non lineare.
Inoltre esistono diversi "solver", tra cui Cplex, che hanno raggiunto prestazioni elevate.
Ok Silvio, grazie di tutto. Dopo magari ne posto
un altro simile di tableau, solo un po' più grande...
un altro simile di tableau, solo un po' più grande...
Se ti capita, metti un paio di etichette...
Sì sì, il fatto è che all'esame il prof. ha disegnato
il tableau sul foglio senza neanche una lettera,
proprio come una pura e semplice tabella di numeri...
il tableau sul foglio senza neanche una lettera,
proprio come una pura e semplice tabella di numeri...
Magari perchè voi siete abituati a vederle così.
Io ad esempio, mettevo la funzione obiettivo sull'ultima riga e i risultati delle variabili sull'ultima colonna...
Comunque non cambia nulla, basta saperlo.
Io ad esempio, mettevo la funzione obiettivo sull'ultima riga e i risultati delle variabili sull'ultima colonna...
Comunque non cambia nulla, basta saperlo.
Ecco le mie risposte:
a) Sia $x_4$ la variabile ausiliaria e $y_1,y_2,y_3$ le variabili artificiali.
Analizzando il tableau si osserva che le variabili che sono in base nell'iterazione
finale della prima fase del simplesso sono $x_1,x_2,y_3,x_3$ in ordine dall'alto
verso il basso, dalla riga 1 del tableau (cioè la seconda riga, dato che la prima
è la riga 0) alla riga 4. Si osserva che la variabile artificiale $y_3$ è ancora
in base e per di più con valore 0; inoltre, sulla riga 3 tutti i coefficienti $a_(3k)$
per $k=1,2,3,4$ sono nulli. Questo vuol dire che si può eliminare immediatamente
dalla base la variabile $y_3$; infatti, se eliminiamo la colonna delle variabili
artificiali (operazione comunque lecita), ci resta il problema scritto sotto forma
di tableau nelle variabili originali, ma con la riga 3 interamente nulla: però
questo vuol dire che il rango della matrice costituita dai coefficienti
delle variabili $x_1,x_2,x_3,x_4$ non è più 4, cioè la riga 3 è linearmente
dipendente dalle altre, quindi possiamo eliminarla.
b) A questo punto ci resta il problema senza variabili artificiali e non
ancora scritto in forma canonica. Dopo averlo ridotto in forma canonica
ed aver operato la seconda fase del simplesso si perviene alla
soluzione ottima: $z=-3,x_1=6,x_2=3,x_3=0,x_4=2$.
Tutto corretto?
Argh, è arrivato il bilancio dell'Egitto...
Per un po' sono busy for all...
Per un po' sono busy for all...
Potete darmi una risposta? Quando volete,
ma basta che me la diate... Sono curioso di sapere se ho sbagliato o no...
ma basta che me la diate... Sono curioso di sapere se ho sbagliato o no...
La parte a è corretta.
La parte b dovrei fare i conti, ma penso che non ci siano problemi nello svolgere un passo del simplesso.
La parte b dovrei fare i conti, ma penso che non ci siano problemi nello svolgere un passo del simplesso.
Grazie di tutto Silvio.
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo