Ricerca Operativa I

prova scritta del 25 febbraio 1998

Boh?

Si consideri il seguente problema di programmazione lineare in forma standard:

min x1 + 2x2 + x3 + 5x4 + x5 + 2x6 + x7 + x8 + 3x9 (1)

x1 + x2 = 1

x1 – x3 – x4 = 0

x2 + x3 – x5 – x6 = 0

x4 + x5 – x7 – x8 = 0

–x6 – x7 + x9 = 0

x1, x2, x3, x4, x5, x6, x7, x8, x9 > 0.

Dati gli insiemi A = {1, 3, 5, 6, 8}, B = {2, 3, 4, 6, 7}, C = {1, 3, 5, 8, 9}, si dica quali di essi individuano una base per il problema (1). Se poi tra questi vi sono effettivamente delle basi,

  1. si individuino i vertici associati a ciascuna di esse,

  2. se ne calcoli il valore,

  3. se ne verifichi l’eventuale ottimalità,

  4. si distinguano eventuali basi degeneri

tutto ciò, possibilmente, senza applicare il metodo del simplesso ma ricorrendo alle sole definizioni fondamentali e alla Teoria della Dualità.