prova scritta del 30 giugno 1998

1. Con riferimento al problema precedente nella versione priva di capacità, si definisca un oracolo in grado individuare in corrispondenza della generica iterazione del simplesso una colonna il cui costo ridotto abbia valore minimo tra tutte le colonne del problema.
2. Qual è la complessità dell’oracolo così sviluppato?
3. Supponiamo che le quantità di energia da inviare siano vincolate ad assumere valori interi. Come andrebbe in questo caso modificata la formulazione? (Motivare la risposta)
4. Come si modifica la formulazione nel caso in cui vi siano n tipi distinti di flussi continui ma non miscelabili, supponendo che il generico tratto dall’origine i alla destinazione j abbia capacità c_ij? E come si modifica in tal caso l’oracolo di cui al punto 1?