RICERCA OPERATIVA Tema d’esame del 17/03/2008

RICERCA OPERATIVA Tema d’esame del 17/03/2008

COGNOME:

NOME:

MATRICOLA:

1. Un’azienda agricola deve pianificare le assunzioni di lavoratori stagionali per la raccolta di po- modori e zucchine in due tenute distinte. I raccoglitori sono di tre categorie: esperti, normali e apprendisti. Ciascun lavoratore sar`a impiegato nella raccolta di un solo tipo di ortaggi: i lavo- ratori esperti sono in grado di raccogliere 2 ettari se impiegati per i pomodori oppure 1,9 ettari se impiegati per le zucchine; i raccoglitori normali raccolgono 1,6 ettari di pomodori oppure 1,2 ettari di zucchine; gli apprendisti raccolgono 1 ettaro di pomodori oppure 0,5 ettari di zucchine.

Il costo di un lavoratore per l’intera stagione `e di 5700 euro, se esperto, 3500 euro, se normale, e 2500 euro se apprendista. Per motivi organizzativi, almeno un quarto di tutti i lavoratori impiegati devono essere esperti. Inoltre, la tenuta a pomodori deve avere almeno un quinto di raccoglitori esperti, mentre nella tenuta a zucchine il numero di esperti deve essere almeno la met`a del totale. L’impiego di apprendisti in una tenuta comporta l’invio di supervisori nella tenuta stessa: per la prossima stagione, l’azienda pu`o inviare supervisori solo in una delle due tenute. L’azienda vuole anche valutare la convenienza a usufruire di un contributo statale di 20000 euro, ottenibile se il numero di apprendisti supera il 30% del totale dei lavoratori sta- gionali impiegati. L’azienda dispone di 200 ettari coltivati a pomodori e 100 ettari coltivati a zucchine e ne vuole completare la raccolta. Scrivere un modello di programmazione lineare che permetta all’azienda di decidere le assunzioni in modo da minimizzare i costi complessivi, al netto dell’eventuale contributo statale di incentivo all’impiego di apprendisti.

2. Trovare la soluzione ottima per il seguente problema di Programmazione Lineare

max −3x1+ x₂− 6x3+ 2x₄ s.t. 2x1+ 3x2− x3+ 2x4= 3

2x₁− 2x₂− 2x₃− 4x₄= 4 x1, x2, x3≥ 0

x4≤ 0 applicando la regola di Bland.

3. Risolvere con il Branch and Bound il seguente problema di knapsack 0 − 1

max z = 3x₁+ 5x₂+ 2x₃+ 6x₄+ 7x₅ s.t. 8x1+ 10x2+ 5x3+ 3x4+ 4x5≤ 15

x_i∈ {0, 1} ∀i = 1...5

Utilizzare una strategia best bound first (numerare i nodi nell’ordine di valutazione).

...ALTRE DOMANDE SUL RETRO...

1

4. Come si riconoscono su un tableau le due condizioni di arresto del metodo del simplesso primale?

Giustificare la risposta.

5. Si consideri il seguente problema di Programmazione Lineare, la cui soluzione ottima `e: x^∗₁= 7/2, x^∗₂= −5/2, con z^∗= −6:

min z = −x1+ x2

s.t. x1≤ 4 x2≥ −3 x₁− x2≤ 6 x1≥ 0, x2≤ 0

Scrivere il modello duale e utilizzare le condizioni di complementariet`a primale-duale per calco- lare una soluzione ottima duale.

6. Si consideri il metodo del simplesso duale in forma tableau, applicato ad un problema min c^Tx : Ax = b, x ≥ 0. Consideriamo il tableau relativo a una iterazione e indichiamo con ¯a_ij l’elemento del tableau in riga i e colonna j. Sia valore della soluzione corrente (super-)ottimo e non ammissibile: i valori correnti dei costi ridotti ¯c_j sono tutti positivi o nulli e sia il valore della variabile corrispondente alla riga h negativo. Si fissi tale variabile come variabile che esce dalla base. Cosa succede se si sceglie, come variabile entrante, la variabile x_k con ¯a_hk < 0, ma con rapporto ¯ck/|¯ahk| non minimo? Giustificare la risposta.

2

TRACCIA DELLE SOLUZIONI 1. Il modello in AMPL:

var xep >= 0 integer; #numero esperti per pomodori var xez >= 0 integer; #numero esperti per zucchine var xnp >= 0 integer; #numero normali per pomodori var xnz >= 0 integer; #numero normali per zucchine var xap >= 0 integer; #numero apprendisti per pomodori var xaz >= 0 integer; #numero apprendisti per zucchine

var yc binary; #vale 1 se si usufruisce del contributo, 0 altrimenti

var yap binary; #vale 1 se si impiegano apprendisti per pomodori, 0 altrimenti var yaz binary; #vale 1 se si impiegano apprendisti per zucchine, 0 altrimenti

minimize costi: 5700 * (xep + xez) + 3500 * (xnp + xnz) + 2500 * (xap + xaz) - 20000

* yc;

s.t. tuttipomodori: 2.0 * xep + 1.6 * xnp + 1 * xap >= 200;

s.t. tuttezucchine: 1.9 * xez + 1.2 * xnz + 0.5 * xaz >= 100;

s.t. espertiminpom: xep >= 0.20 * (xep + xnp + xap);

s.t. espertiminzuc: xez >= 0.50 * (xez + xnz + xaz);

s.t. espertimin: xep + xez >= 0.25 * (xep + xnp + xap + xez + xnz + xaz);

s.t. logicoap: xap <= 99999 * yap;

s.t. logicoaz: xaz <= 99999 * yaz;

s.t. supervisori: yap + yaz <= 1;

s.t. attivacontributo: xap + xaz >= 0.3 * (xep + xez + xnp + xnz + xap + xaz) - 99999 * (1 - yc);

2. Per poter applicare il metodo del simplesso bisogna mettere in forma standard (funzione obiet- tivo di minimo, vincoli di uguaglianza, termini noti non negativi e variabili non negative). In particolare la variabile x₄`e ≤ 0 e la si sostituisce con una nuova variabile ˆx<sub>4</sub>= −x<sub>4</sub>, ˆx<sub>4</sub>≥ 0. La forma standard `e quindi:

min 3x1− x2+ 6x3+ 2ˆx4

s.t. 2x1+ 3x2− x3− 2ˆx4= 3 2x1− 2x2− 2x3+ 4ˆx4= 4 x₁, x₂, x₃≥ 0

ˆ x4≥ 0

Si applica quindi il metodo del simplesso a questo problema, eseguendo la Fase I (variabili artificiali y1 e y2) per trovare una soluzione ammissibile di base. Di seguito sono riportate, per la Fase I e la Fase II, le basi e il valore della funzione obiettivo ad ogni iterazione (`e stata applicata la regola di Bland).

Fase I: [y₁, y₂](−7) → [x₁, y₂](−1) → [x₁, ˆx₄](0) Fase II: [x₁, ˆx₄](−16/3) → [x₂, ˆx₄](−2)

Soluzione (problema di partenza): x^∗₁= 0, x^∗₂= 5/2, x^∗₃= 0, x^∗₄= −ˆx₄= −9/4, z_max^∗ = −2.

3. Soluzione ottima: z^∗= 16, x^∗₁= x^∗₄= x^∗₅= 1.

3

4. Si scrive il duale

max ω = 4u₁− 3u2+ 6u₃ s.t. u1+ u3≤ −1

u₂+ u₃≥ 1 u1≤ 0 u2≥ 0 u₃≤ 0

Si applicano quindi le condizioni di complementariet`a primale-duale, ottendo il sistema:



















x₁= 7/2 < 3 ⇒ u₁= 0 (primo vincolo primale lasco) x₂= −5/2 > −3 ⇒ u₂= 0 (secondo vincolo primale lasco)

x1− x2= 7/2 − (−5/2) = 6 ⇒ no info su u3 (terzo vincolo primale saturo) x1= 7/2 > 0 ⇒ u1+ u3= −1 (variabile primale x1 non nulla)

x2= −5/2 < 0 ⇒ u1− u3= 1 (variabile primale x2 non nulla)

⇒









 u₁= 0 u₂= 0 u₁+ u₃= −1 u1− u3= 1

Risolvendo il sistema in u₁, u₂e u₃si ottiene la soluzione ottima duale u^∗₁= 0, u^∗₂= 0, u^∗₃= −1.

Come verifica, per gli stessi valori delle variabili duali si ottiene ω^∗ = z^∗= −6.

5. Se tutti i costi ridotti sono positivi o nulli, la soluzione `e ottima (infatti non `e possibile migliorare ulteriormente la funzione obiettivo con un cambio base, per definizione di costo ridotto). Se una colonna `e tutta negativa o nulla, in corrispondenza di un costo ridotto negativo, il problema

`

e illimitato: infatti posso aumentare indefinitamente il valore della variabile corrispondente a questo costo ridotto, diminuendo indefinitamente il valore della funzione obiettivo, senza perdere l’ammissibilit`a della corrispondente soluzione (le variabili attualmente in base rimangono positive o nulle e le altre fuori base rimangono nulle).

6. La soluzione all’iterazione successiva sarebbe non ottimale (qualche costo ridotto assumerebbe valore negativo), rendendo non pi`u applicabile il metodo del simplesso duale.

4