11 per il corso di Ricerca Operativa

Esercitazione n

11 per il corso di Ricerca Operativa

Coppie di problemi primale-duale TRASPORTO

Si consideri il problema di trasporto dell’Esercitazione 4 di cui si riporta la formu- lazione.

min 10x₁₁ +8x₁₂ +21x₁₃ +12x₂₁ +20x₂₂ +14x₂₃

x₁₁ +x₁₂ +x₁₃ = 130

x₂₁ +x₂₂ +x₂₃ = 200

x₁₁ +x₂₁ = 80

x₁₂ +x₂₂ = 100

x₁₃ +x₂₃ = 150

x_ij ≥ 0, i = 1, 2, j = 1, 2, 3.

Le variabili x_ij rappresentano le quantit`a (in tonnellate) di minerale da trasportare giornalmente da ciascuna miniera M_i a ciascun impianto di produzione P_j.

Si tratta di un porblema nella forma

min c^Tx Ax = b x ≥ 0 con A matrice 5 × 6

A =









1 1 1 0 0 0 0 0 0 1 1 1 1 0 0 1 0 0 0 1 0 0 1 0 0 0 1 0 0 1









Il punto di vista di una compagnia di trasporto

Supponiamo ora che una compagnia specializzata in trasporto (esterna all’industria) voglia proporsi all’industria per effettuare il trasporto del minerale dalle miniere agli impianti di produzione. La compagnia di trasporti, per convincere l’industria ad avvalersi del servizio di trasporto esterno, dovr`a proporre dei prezzi di trasporto non svantaggiosi. A tale scopo la compagnia dei trasporti propone all’industria di prelevare una tonnellata di minerale da ciascuna miniera per un prezzo unitario rispettivamente pari a u1 e u2 e di consegnare una tonnellata di minerale a ciascuno dei tre impianti per un prezzo unitario rispettivamente pari a v<sub>1</sub>, v<sub>2</sub> e v<sub>3</sub>. Quindi la compagnia dei trasporti vorr`a massimizzare la funzione che fornisce il suo profitto complessivo che `e data da

130u₁+ 200u₂+ 80v₁+ 100v₂+ 150v₃.

1

Tuttavia affinch´e l’offerta della compagnia dei trasporti risulti vantaggiosa per l’industria i prezzi del trasporto proposti dovranno risultare non superiori a quelli che l’industria avrebbe effettuando in proprio i trasporti stessi. Quindi dovr`a risultare

u₁ +v₁ ≤ 10

u₁ +v₂ ≤ 8

u1 +v3 ≤ 21

u₂ +v₁ ≤ 12

u₂ +v₂ ≤ 20

u2 +v3 ≤ 140.

Quindi, la compagnia dei trasporti dovr`a risolvere il problema max (130u₁ + 200u₂ + 80v₁ + 100v₂ + 150v₃)

u₁ +v₁ ≤ 10

u1 +v2 ≤ 8

u₁ +v₃ ≤ 21

u₂ +v₁ ≤ 12

u2 +v2 ≤ 20

u₂ +v₃ ≤ 140

che si verifica immediatamente essere il problema duale del problema dei trasporti asseg- nato.

2