Ricerca operativa - esercizi

QUESITO 1

Dato un problema del trasporto con m origini e n destinazioni:

(A)Quanti sono i vincoli del problema?Quanti di essi sono indipendenti?Quante sono le

variabili del problema?

(B)Cosa e come funziona il metodo dell’angolo nord-ovest?

(C)Cosa è e come funziona il metodo dello stepping stone?

QUESITO 2

Un azienda agricola produce due prodotti indicati con A e B.E’ disponibile manodopera in

numero pari al massimo a 96 unità.Per produrre una tonnellata di prodotto A sono richieste

6 unità di personale.Per produrre una tonnellata di prodotto B sono richieste 8 unità di

personale.Stime sulla domanda dei due prodotti suggeriscono di produrre al massimo 10

tonnellate del prodotto A e 8 tonnellate di b.Si ritiene inoltre che la produzione complessiva

dei due prodotti debba essere pari almeno a 6 tonnellate.Il profitto unitario del prodotto A è

pari a 600 euro/tonnellate.Il profitto unitario del prodotto B è pari a 400 euro/tonnellate.Si

vuole determinare la quantità A e B da produrre che consentono di massimizzare il profitto.

Con riferimento al problema descritto:

(A)si formuli e si illustri il modello in programmazione lineare

(B)si disegni il dominio di ammissibilità del problema ed il gradiente della funzione obiettivo

z.

(C)si effettui l’analisi grafica,individuando il vertice ottimo e i vincoli saturi,si calcolino i

valori delle variabili all’ottimo.

(D)si indichino le soluzioni basiche ammissibili del problema e la relativa composizione;

(E)si risolva il modello analiticamente con uno degli algoritmi noti:

(F)si indichi,sul grafico,il percorso ,cioè la sequenza di soluzioni ,individuate ,dell’algoritmo:

(G)si scrivano le matrici B e B-1 relative alla tabella finale.

QUESITO 3

Si effettui l’analisi di stabilità della soluzione ottima del modello dell’esercizio n.1(in

incremento e decremento) del termine noto del vincolo relativo alla disponibilità di

manodopera.Si indichino sul grafico le posizioni limite del vincolo.Si indichi inoltre la

successione di soluzioni ottime all’aumentare del coefficiente di profitto unitario del prodotto

B

QUESITO 4

Assumendo come primale il modello sviluppato al quesito 1 si costruisca il corrispondente

modello duale,illustrando le relazioni tra i due modelli ed il significato delle varibili duali.

QUESITO 5

Si consideri il grafo in figura con i relativi costi di spostamento sugli archi.

(A) ìSi determini l’aborescenza dei minimi percorsi relativa al nodo origine 1 utilizzando

un algoritmo a piacere;

(B) si illustrino i passi della procedura

(C) Ipotizzando che il grafo considerato rappresenti il reticolo delle attività di un progetto

e che i costi sugli archi siano le durate delle attività,si determini la durata del progetto

ed il percorso critico.