.dsy:it. - Ancora domande..

.dsy:it. (http://www.dsy.it/forum/)
- Ricerca operativa (http://www.dsy.it/forum/forumdisplay.php?forumid=228)
-- Ancora domande.. (http://www.dsy.it/forum/showthread.php?threadid=36226)

Posted by Simeon on 13-09-2008 00:55:

Ancora domande..

Scusate, ma non avendo materiale a sufficienza veramente non so dove sbattere la testa.

Se si ha un esercizio del tipo

"Dato il seguente tableau si aggiunga ad esso il vincolo xxx e si risolva il problema cosi' ottenuto" come bisogna procedere? Per esempio avendo:

code:
0  3  0  10    -10
6 -1  1  1      6
1  4  0  3      4

e dovendo aggiungere il vincolo x1 - x2 +2x3 <= 10

come si andrebbe avanti? (sugli appunti ho letto che ha a che fare con il simplesso duale, su un thred di qui invece aggiungevano una variabile di scarto, due ausiliarie e risolvevano il tableau. boh.)

E ancora, un esercizio del genere:

EDIT: risolta anche la questione del rilassamento surrogato, e lo sarebbe anche quella del lagrangiano se non fosse che non so come interpretare il lambda(Ax-b) da sommare alla funzione obiettivo. L' "Ax-b" nello specifico. Saro' ignorante ma come si interpreta? Si sottrae il termine noto b a tutti i coefficienti delle x di un dato vincolo? Si ricopia il vincolo e alla fine si lascia -b?

Stavolta e' un sacco di roba, ma spero comunque in una minima risposta. Dei tre esami che mi mancano questo e' l'unico di cui ho ZERO materiale e non so dove reperirlo. Il libro di testo non l'ho trovato.

Posted by Simeon on 13-09-2008 12:53:

E ancora:

"E’ dato un grafo non orientato G=(N,E) con pesi non negativi wi, con i ∈ N, sui nodi, e pesi non
negativi cij, con (i,j) ∈ E, sui lati. Si fornisca un modello di PLI per trovare in G un sottografo
G”=(S,E(S)) per il quale sia minima la differenza fra la somma dei pesi dei nodi in S e quella dei
lati in E(S), lati cioè che hanno entrambi gli estremi in S, e che contenga almeno tre nodi. Come
cambia il modello se si chiede che sia minima la differenza fra la somma dei pesi dei lati in E(S) e
quella dei lati in δ(S), lati cioè che hanno un solo estremo in S?"

Come si potrebbe realizzare il modello di un esercizio del genere? (non ho trovato un esempio coi grafi)

Infine, e qui mi potra' rispondere solo uno che ha frequentato quest'anno: gli algoritmi da sapere per eventuali di tipologie sono ford-fulkerson (per gli esercizi di flusso massimo) e dijkstra (cammino minimo) e basta?

Ecco, direi che a sapere ste cose arriverei all'esame discretamente preparato.

EDIT: rimossa la domanda flusso massimo a costo minimo, mi sono documentato :asd:

Posted by Simeon on 14-09-2008 00:13:

e ANCORA (pure il sabato sera mi devo dannare porc)

code:

    0  0 -1  1 0 0     1

x1  1  1  0  1 0 0     1   

x5  0 -1  1 -1 1 0     0

x6  0  1  1  0 0 1     1

Sto risolvendo un problema di massimo, per cui faccio pivot su x3 (il coefficiente di costo e' -1).

Perche' la variabile uscente in questo caso e' x5? E lo e' perche' sto esercizio non mi veniva e l'ho rifatto con 2 programmini che m'han dato entrambi lo stesso risultato.

Non capisco, non dovrebbe essere il minimo rapporto positivo e quindi tra (1/0,0/1,1/1) dovrebbe uscire x6?

:help:

EDIT: questa me la sono "risolta" da me arrivandoci un po' a naso, anche se mi sembra strano che si distingua tra "0 positivi" (0/num positivo) e "0 negativi" (0/numero negativo). O piu' probabilmente e' il pivot negativo che non e' ammesso, boh.

In ogni caso se qualcuno chiarisce e' meglio, se poi risponde a tutto quanto gli erigo una statua da qualche parte.

Bel sabato sera.

Posted by Simeon on 15-09-2008 15:34:

Vi prego l'esame e' dopodomani

All times are GMT. The time now is 03:26.

Show all 4 posts from this thread on one page