Ricerca operativa - Esercitazione

Università degli Studi di Napoli “Federico II”

Facoltà di Ingegneria

Corso di Ricerca Operativa, A.A. 2004/2005 (Nuovo Ordinamento) Sessione estiva

Proff. Improta - De Rosa - Prova d’esame del 21.02.2005

Quesito 1

Con riferimento al problema del trasporto:

• Dato un problema del trasporto con 7 origini e 5 destinazioni, quanti sono i vincoli? Quanti di essi sono indipendenti? Quante sono le variabili del problema?
• A che serve e come funziona il metodo dell’angolo di Nord-Ovest?
• A che serve e come funziona il metodo dello Stepping Stone?

Quesito 2

Un’industria conciaria deve mettere in produzione due tipi di pellami, daino e camoscio, destinati alla realizzazione di calzature sportive. L’industria dispone, in quantità certamente sufficienti, di tutti i materiali e della manodopera necessari per la lavorazione. Tenendo conto dei risultati delle analisi di mercato disponibili, la direzione marketing ha fornito al settore produzione alcune indicazioni relative ai quantitativi di pelli da realizzare.

In particolare le analisi suggeriscono che il numero di pelli di camoscio sia almeno il doppio del numero di pelli di daino e che, tenendo conto degli ordini raccolti, la differenza tra il numero di pelli di camoscio ed il numero di pelli di daino sia inferiore a cinquanta. Il numero di pelli di camoscio dovrà, inoltre, essere almeno pari a sessanta unità.

Tenendo conto che il ricavo unitario ottenibile con la vendita di una pelle di daino è pari a 3 Euro, mentre quello ottenibile con la vendita di una pelle di camoscio è pari a 50 Euro, si determini il piano di produzione delle pelli dei due tipi che massimizza il ricavo complessivo.

La lavorazione di una pelle di daino richiede l’uso di 15 litri di acqua arricchita di sali di cromo, mentre la lavorazione di una pelle di camoscio ne richiede 25 litri. Si determini il piano di produzione che minimizza il quantitativo complessivo di acqua arricchita da utilizzare e, quindi, da smaltire.

• Si formuli il modello in programmazione lineare, illustrando le diverse componenti ed elencando i vincoli nell’ordine in cui sono stati presentati;
• Si disegni il dominio di ammissibilità, la direzione del grad;
• Si risolva graficamente il modello, individuando i vertici corrispondenti alle soluzioni ottime (e i vincoli saturi) nel caso di massimizzazione del ricavo e di minimizzazione dell’acqua arricchita ai cromo; si scriva l’espressione della generica soluzione di compromesso tra le due trovate;
• Si indichino le soluzioni basiche ammissibili corrispondenti ai vertici del dominio e la relativa composizione,
• Si risolva il modello in uno dei due casi (max ricavo o min acqua di cromo), motivando la scelta, con uno dei metodi di Simplesso noti;
• Si indichi su grafico la successione dei vertici, ammissibili e non ammissibili, individuati dall’algoritmo sul dominio di ammissibilità.

Quesito 2

• Qual è la definizione, in PL, di coefficiente di costo modificato c’? Quale è il suo significato geometrico?
• Quale criterio si segue nel determinare la variabile entrante nell’algoritmo del Simplesso?
• Con quale criterio si individua la variabile uscente nell’algoritmo del Simplesso?
• Perché per individuare la riga pivot, e, dunque la variabile uscente, si sceglie la riga in corrispondenza della quale si verifica il minimo dei rapporti bi/aij?

Quesito 3

• In quali casi e perché si aggiungono, in un modello P.L., le variabili artificiali?
• Da cosa è costituita la funzione di inammissibilità w nel metodo delle 2 fasi? Perché viene detta funzione di inammissibilità?
• Perché il minimo di w possa risultare, alla fine della prima fase, eguale a 0 come deve essere il problema che si vuole risolvere?
• Come e perché viene trasformata la funzione obiettivo nel metodo del Big M?

Quesito 4

• Perché si effettua l’analisi di stabilità della soluzione ottima?
• Quali sono i parametri del modello rispetto ai quali essa viene effettuata?
• Quali sono le espressioni che si utilizzano per calcolare Ω_i ± Ω γ? Come si ricavano?
• Allorché il termine noto bi assume i valori: [b_i + Ω b_i⁺; [b_i - Ω b_i^-; cosa si verifica?

Quesito 5

Assunto come primale (o diretto) il modello del quesito 2 si scriva il modello duale.

Tempo a disposizione 3 ore.

Utilizzare fogli a quadretti, segnando su ogni foglio utilizzato cognome, nome e matricola in alto a destra.