Simeon

User info:

Registered: Aug 2004
Posts: 984 (0.13 al dì)
Location: Milano
Corso: Informatica
Anno: IT IS OVER!
Time Online: 14 Days, 19:29:42 [...]
Status: Offline

Post actions:

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

Last edited by Simeon on 15-09-2008 at 22:05

Simeon

User info:

Registered: Aug 2004
Posts: 984 (0.13 al dì)
Location: Milano
Corso: Informatica
Anno: IT IS OVER!
Time Online: 14 Days, 19:29:42 [...]
Status: Offline

Post actions:

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

Last edited by Simeon on 15-09-2008 at 01:21

Simeon

User info:

Registered: Aug 2004
Posts: 984 (0.13 al dì)
Location: Milano
Corso: Informatica
Anno: IT IS OVER!
Time Online: 14 Days, 19:29:42 [...]
Status: Offline

Post actions:

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?



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.

Last edited by Simeon on 14-09-2008 at 01:48

Simeon

User info:

Registered: Aug 2004
Posts: 984 (0.13 al dì)
Location: Milano
Corso: Informatica
Anno: IT IS OVER!
Time Online: 14 Days, 19:29:42 [...]
Status: Offline

Post actions:

Vi prego l'esame e' dopodomani