Autore Topic: Temi d'esame  (Letto 1062 volte)

0 Utenti e 1 Visitatore stanno visualizzando questo topic.

Offline Cosmos

  • Signore dei Geek
  • *
  • *
  • *
  • Post: 1.493
  • Reputazione: 48
  • Sesso: Maschio
  • Is this the end?
Temi d'esame
« il: 08 Febbraio 2011, 19:00:36 »
Poiché mi ero stufato di vedere per l'ennesima volta ASE, ho ripreso la teoria di Metodi e ho svolto un paio di temi d'esami di quelli proposti (alcuni li avevo già fatti).
Dato che sono/sarebbero lunghi da scrivere qui sul forum, li ho resi pdf e caricati nella sezione file.
Ci sono alcune sviste che mi sono sfuggite, per cui controllate anche le note in questo topic (perché i pdf non saranno aggiornati... :whistle:)

Soluzioni esami



(11/02/2010) Aggiunti gli ultimi due esami.



Varianti/Imprecisioni/Errori:

17/02/2010:
Ho dichiarato mu e u come dei vettori. In realtà i vincoli sono soltanto due, quindi sono due scalari semplicemente (e vanno posti fuori dalla sommatoria!).
Nel riportare la f.o. del L, inoltre, ho dimenticato di aggiungere i coefficienti b dei due vincoli.
La versione corretta è:
L(\bar x,u,\mu) = \sum_{i\in I}c_ix_i - \mu\left\(\sum_{i\in I}a_i^1x_i - b_1\right\) - u\left\(\sum_{i\in I}a_i^2x_i - b_2\right\)



03/02/2010:
Nella domanda sulla riconducibilità da SS a KP, nella soluzione ho proposto la versione che è stata discussa in classe con il KP nella forma classica.
Sul libro invece è fornito in versione decisionale, e l'analisi del problema diventa quindi la seguente:

KP0/1 decisionale:

\\\sum_{i\in I}p_ix_i \geq P\\\sum_{i\in I}w_ix_i \leq W

Ci si chiede se esista una soluzione che determini in profitto maggiore o uguale di P, nei limiti di capacità W.
La trasformazione in SS coincide con quella proposta su carta, ma in questo caso anche P viene fissato al valore di b.

Avremo quindi che devo valere due condizioni:

\\\sum_{i\in I}a_ix_i \geq b\\\sum_{i\in I}a_ix_i \leq b

Ne deriva che KP ammette risposta sì solamente nel caso in cui SS sia risolubile.

Personalmente, nel caso questo fosse capitato in sede d'esame, avrei chiesto chiarimenti su quale versione indicare.
Spero possa servire a chi sta preparando questa materia.



15/09/2010 e 03/02/2010:
Negli esercizi sul B&B, al momento di discutere la chiusura, è riportata una considerazione completamente errata.
È vero che non sono fornite soluzioni dall'esterno, ma occorre anche ricordare che UB e LB sono soluzioni ammissibili per un problema di minimo e massimo rispettivamente, e quindi in effetti dei valori per le soluzioni del problema si hanno.
In entrambi i casi risulta possibile chiudere un nodo.
Nello specifico il (5) per 15/09 e il (3) per 03/02.
« Ultima modifica: 03 Marzo 2011, 23:22:40 da Cosmos »
Spoiler: XKCD (click to show/hide)



Regola Aurea: Qualsiasi calcolo ridicolmente complesso a vedersi, ed ancor più complesso a farsi, porterà certamente ad un risultato nullo...

Corollario: Se il risultato non si annulla, sarà 2\pi

Se X è un insieme non vuoto su cui è definita una relazione d'ordine parziale tale che ogni sua catena possiede un maggiorante, allora contiene almeno un elemento massimale. Chiaro no?

In trepidante attesa della pubblicazione di "Orchi, Antilopi e Calamari - Vol. I"

Offline alexic

  • Utente
  • *
  • Post: 67
  • Reputazione: 6
Re:Temi d'esame
« Risposta #1 il: 14 Luglio 2011, 11:46:16 »
Nel compito 12/09/08, esercizio B&B, al punto 2 io rispondo differentemente.
Dato che è un problema di massimo,  e non abbiamo altri dati, possiamo assumere come migliore soluzione corrente il max tra i vari LB, ovvero 12. Quindi essendo z = 12 posso chiudere quei nodi il cui UB <= z cioè il nodo 3 (UB = 11 < z = 12)

Fonte: videolez di Perboli.

Confermate?

Offline Raptor

  • Utente Fidato
  • *
  • *
  • *
  • Post: 489
  • Reputazione: 11
  • Sesso: Maschio
    • rpt@altervista
Re:Temi d'esame
« Risposta #2 il: 14 Luglio 2011, 12:10:03 »
Nel compito 12/09/08, esercizio B&B, al punto 2 io rispondo differentemente.
Dato che è un problema di massimo
ho cercato il testo e la funzione obiettivo è di minimo  :si:

Offline alexic

  • Utente
  • *
  • Post: 67
  • Reputazione: 6
Re:Temi d'esame
« Risposta #3 il: 14 Luglio 2011, 15:45:19 »
doh!

Offline PL3

  • Utente Senior
  • *
  • Post: 179
  • Reputazione: 0
Re:Temi d'esame
« Risposta #4 il: 17 Gennaio 2012, 18:40:44 »
Ciao Cosmos. Ho visto che i temi risolti riguardano solo ricerca operativa. La parte di ottimizzazione è da qualche parte? Ci sono temi ufficiali di Metodi e Algoritmi di ottimizzazione e non solo di Ricerca operativa?
Comunque materiale utilissimo ;)

Altra domanda, all'esame hai avuto problemi legati alla diversa difficoltà degli esercizi rispetto a quelli fatti?

Offline Cosmos

  • Signore dei Geek
  • *
  • *
  • *
  • Post: 1.493
  • Reputazione: 48
  • Sesso: Maschio
  • Is this the end?
Re:Temi d'esame
« Risposta #5 il: 17 Gennaio 2012, 19:02:40 »
I temi qui risolti sono quelli che fino all'anno scorso erano usati come riferimento dal prof. Tadei (sono stati forniti da lui stesso), ma non ho altro materiale da fornirti.
Per quanto riguarda la parte di ottimizzazione, euristiche & co. anche noi siamo andati un po' alla cieca lo scorso anno, ma gli esercizi si sono rivelati in linea con quelli (molo pochi) fatti ad esercitazione.
Dipende un po' da cosa sono riusciti a fare a lezione.

Nei topic dedicati agli appelli del 2011 c'è una sorta di traccia dei testi, per cui quello è il riferimento più affidabile a cui io possa rimandarti.

In genere sin ora gli esercizi d'esame si sono quasi sempre rivelati molto in linea con quello visto a lezione, ma non vorrei darti false speranze.
A volte si tratta di compiti semplici teoricamente, ma che richiedono molto tempo, o sono possibili a soggettiva interpretazione del testo, oppure può essere il completo opposto, con esercizio all'apparenza immediato, ma che in realtà richiede un background di nozioni non indifferente.
Spoiler: XKCD (click to show/hide)



Regola Aurea: Qualsiasi calcolo ridicolmente complesso a vedersi, ed ancor più complesso a farsi, porterà certamente ad un risultato nullo...

Corollario: Se il risultato non si annulla, sarà 2\pi

Se X è un insieme non vuoto su cui è definita una relazione d'ordine parziale tale che ogni sua catena possiede un maggiorante, allora contiene almeno un elemento massimale. Chiaro no?

In trepidante attesa della pubblicazione di "Orchi, Antilopi e Calamari - Vol. I"