 | |
Il progetto dsy.it è l'unofficial support site dei corsi di laurea del Dipartimento di Scienze dell'Informazione e del Dipartimento di Informatica e Comunicazione della Statale di Milano. E' un servizio degli studenti per gli studenti, curato in modo no-profit da un gruppo di essi. I nostri servizi comprendono aree di discussione per ogni Corso di Laurea, un'area download per lo scambio file, una raccolta di link e un motore di ricerca, il supporto agli studenti lavoratori, il forum hosting per Professori e studenti, i blog, e molto altro...
In questa sezione è indicizzato in textonly il contenuto del nostro forum |
Esercizi svolti
Clicca QUI per vedere il messaggio nel forum |
| DiMar |
Ciao a tutti!
Devo fare l'esame di FRC, purtroppo essendo studente lavoratore non posso seguire le lezioni. Sto cercando di prepararlo da solo ma mi scontro con la mancanza di esercizi e temi d'esame svolti.
Qualcuno mi può aiutare? :help:
Grazie!
DiMar
Ps: anche il libro consigliato da Trubian (M. Fischetti: Lezioni di Ricerca Operativa, Edizioni Libreria Progetto Padova, 1995) sembra essere introvabile... se qualcuno lo vendesse... ;) |
| Bulma |
Hai provato a chiedere alla libreria in via Celoria? Mi sembrava che ce l'avessero (ma non sono sicura, in effetti)...
Perchè non provi a postare gli esercizi su cui ti trovi in difficoltà? Magari trovi qualcuno che ti può dare una mano...
Potresti anche di andare a ricevimento (o sentire via mail) dal prof e farti spiegare i concetti più ostici (normalmente è molto disponibile :) ) |
| DiMar |
Originally posted by Bulma
Hai provato a chiedere alla libreria in via Celoria? Mi sembrava che ce l'avessero (ma non sono sicura, in effetti)...
Si ho chiamato, ma al momento non è disponibile! L'ho cercato anche in rete ma senza successo... :(
Perchè non provi a postare gli esercizi su cui ti trovi in difficoltà? Magari trovi qualcuno che ti può dare una mano...
Ok, proviamo. Primo esercizio dell'appello del 16.02.05:
E' dato un grafo non orientato G=(V,E1∪E2), dove ad ogni arco e∈ E = E1∪E2 ha associato un costo non negativo ce, e dove gli archi in E1 ed E2 sono colorati di rosso e di nero, rispettivamente.
Si fornisca un modello di programmazione lineare intera per il problema di determinare in G l'albero di copertura di peso minimo nel quale gli archi rossi sono almeno il doppio degli archi neri.
- Variabili e loro significato:
- Funzione obiettivo:
- Vincoli
Potresti anche di andare a ricevimento (o sentire via mail) dal prof e farti spiegare i concetti più ostici (normalmente è molto disponibile :) )
Lo so, purtroppo sono piuttosto incasinato durante il giorno! Vediamo che succede!
Grazie a tutti! :) |
| Bulma |
| Su che testi stai studiando nel frattempo? |
| DiMar |
Originally posted by Bulma
Su che testi stai studiando nel frattempo?
Baldacci, Dell'Amico - Fondamenti di Ricerca Operativa
Sono le slide del corso: coprono tutto il programma, ma sono abbastanza sintetiche (ovviamente!). Per il resto Google is my friend... ;) |
| Bulma |
Sulle slide dovrebbe esserci, nella parte relativa ai grafi, il modello di programmazione matematica per il problema dell'albero di copertura minimo, no?
Se a quello aggiungi un piccolo vincolo, hai la soluzione del problema che hai postato... ;) |
| DiMar |
Ok, credo di aver risolto! :cool:
Ora ho qualche dubbio sulla PL...
:: Per vedere se in un grafico sono presenti soluzioni degeneri, devo calcolare le coordinate dei rispettivi vertici e osservare se c'è qualche variabile in base nulla?
:: Come scelgo il primo pivot nel tableau iniziale?? Quasi tutti in rete scelgono la colonna sotto il minore dei coefficienti della funzione obiettivo. Sull'unico esempio delle dispense [pag. 29] no!!
Grazie ancora! :)
Ps: Bulma quando compi gli anni?! :D |
| Bulma |
Purtroppo i miei ricordi relativi a queste cose sono sbiaditi...
non vorrei darti una risposta sbagliata... ;) |
| DiMar |
Mi auto rispondo! :)
In entrambi casi ero sulla strada giusta, anche per quanto riguarda la scelta del primo pivot nel tableau iniziale. Infatti di solito si sceglie la colonna sotto il minore dei coefficienti della funzione obiettivo, ma non è obbligatorio: qualsiasi colonna sottostante un coefficiente negativo va bene!
But...
...in un tema d'esame, dopo aver risolto graficamente un problema di PL ed aver trovato le coordinate della soluzione ottima, il prof. chiede:
Si eliminino dal modello i vincoli non attivi in corrispondenza della soluzione ottima e si ricavi il tableau della forma canonica rispetto alla base ottima del problema ridotto. Non capisco, cosa devo fare? :?
Thanks! |
| Bulma |
Per vincolo non attivo si intende un vincolo che non è soddisfatto all'uguaglianza (per fare un esempio stupido, 3x <= 7, con x = 2, non è soddisfatto all'uguaglianza, 3x <= 6 lo è). Perciò cancelli dal problema i vincoli non attivi (ottieni in pratica un problema nuovo), trovi la base ottima in forma canonica e ne fai il tableau.
Ma devo dire che non ricordo proprio bene, quindi potrei aver detto una gran sciocchezza :D :P |
| DiMar |
E' giusto ciò che dici! In sostanza i vincoli non attivi sono quelli che non influiscono in alcun modo sulle coordinate del vertice ottimo.
Quindi nel mio caso, dove il vertice ottimo è l'intersezione tra i vincoli I e II, elimino gli altri due vincoli III e IV, ottenendo un problema ridotto.
Bene... e quindi?
Avendo già la soluzione ottima determinata nel problema originario, come trovo il tableau richiesto? :? :? |
| Bulma |
| Dovresti guardare nelle slide quando parla della forma canonica della base ottima... mi dispiace, non riesco a ricordare bene, ma so che c'erano più modi per ricavare il tableau... maledetta memoria!!! |
| DiMar |
Una sola domanda: all'esame è permesso portare qualcosa? Esercizi, calcolatrice, ... Sperem.... :)
Azie... |
| Bulma |
| Non mi pare, sai? Forse la calcolatrice sì, ma non gli esercizi... |
| DiMar |
Ultimo quesito... Gli esercizi su Ford-Fulkerson dei temi d'esame sono tutti uguali, non capisco però una parte del quesito:
Si trovi con l’algoritmo di Ford-Fulkerson un flusso di valore massimo da s a t a partire dal flusso ammissibile da inviare nella prima iterazione di 10 unità lungo il cammino s,1,2,4,3,t .
Si riportino tutti i cammini aumentanti come sequenze di nodi ed il corrispondente incremento di flusso. Cioè? L'algoritmo di solito parte da un flusso iniziale uguale a zero! Non capisco... :help: |
| DiMar |
Originally posted by DiMar
Non capisco... :help: Trovato... ora resta l'ultima parte: verificare se il flusso massimo è stato inviato a costo minimo o no, motivando la risposta per mezzo della rete incrementale..... :? :? |
|
|
|
|
