Problema trasporti - simplesso
Ciao, ho 3 pozzi petroliferi:
Texas -> produzione annua di petrolio di 80 milioni di barili l'anno
California -> produzione annua di petrolio di 60 milioni di barili l'anno
Alaska -> produzione annua di petrolio di 100 milioni di barili l'anno
Da qui il petrolio estratto và alle 3 raffinerie con capacità di raffinazione:
New Orl -> 100 milioni di barili annui
Charleston -> 60 milioni di barili annui
Seatle -> 80 milioni di barili annui.
La compagnia petrolifera decide di aumentare la produzione finale di 120 milioni di barili l'anno che verranno importati da un nuovo pozzo del medio oriente. Avendo una tabella dei costi del trasporto dai pozzi alle raffinerie come faccio a sapere di quanto aumentare la capacità di raffinazione in CIASCUNA raffineria????
Non so come impostare i vincoli per ciascuna raffineria!!help!!
se la tabella costi (per ogni milione di barili ) è
Texas:
NewOrleans->2 Charleston->4 Seatle ->5
California:
NewOrleans->5 Charleston->5 Seatle ->3
Alaska :
NewOrleans->5 Charleston->7 Seatle ->3
m:oriente:
NewOrleans->2 Charleston->3 Seatle ->5
io tipo per new Orleans ho messo:
min z=2x1+5x2+5x3+2x4
x1<=80
x2<=60
x3<=100
x4<=120
x1+x2+x3+x4>=100 (perchè 100 è la capacità di raffinazione prima dell'inserimento del medio oriente)
Fatto ciò non capisco come ottenere in matlab di quanto aumenta la capacità di raffinazione in ciascuna raffineria . Magari è sbagliata la mia impostazione del problema...
Per maggiore chiarezza ecco il link col testo del programma http://www.scribd.com/doc/72250252/Pro-Get-To
Texas -> produzione annua di petrolio di 80 milioni di barili l'anno
California -> produzione annua di petrolio di 60 milioni di barili l'anno
Alaska -> produzione annua di petrolio di 100 milioni di barili l'anno
Da qui il petrolio estratto và alle 3 raffinerie con capacità di raffinazione:
New Orl -> 100 milioni di barili annui
Charleston -> 60 milioni di barili annui
Seatle -> 80 milioni di barili annui.
La compagnia petrolifera decide di aumentare la produzione finale di 120 milioni di barili l'anno che verranno importati da un nuovo pozzo del medio oriente. Avendo una tabella dei costi del trasporto dai pozzi alle raffinerie come faccio a sapere di quanto aumentare la capacità di raffinazione in CIASCUNA raffineria????
Non so come impostare i vincoli per ciascuna raffineria!!help!!
se la tabella costi (per ogni milione di barili ) è
Texas:
NewOrleans->2 Charleston->4 Seatle ->5
California:
NewOrleans->5 Charleston->5 Seatle ->3
Alaska :
NewOrleans->5 Charleston->7 Seatle ->3
m:oriente:
NewOrleans->2 Charleston->3 Seatle ->5
io tipo per new Orleans ho messo:
min z=2x1+5x2+5x3+2x4
x1<=80
x2<=60
x3<=100
x4<=120
x1+x2+x3+x4>=100 (perchè 100 è la capacità di raffinazione prima dell'inserimento del medio oriente)
Fatto ciò non capisco come ottenere in matlab di quanto aumenta la capacità di raffinazione in ciascuna raffineria . Magari è sbagliata la mia impostazione del problema...

Per maggiore chiarezza ecco il link col testo del programma http://www.scribd.com/doc/72250252/Pro-Get-To
Risposte
Ciao,
classico problema di ottimizzazione dei trasporti. La tua impostazione non mi convince.
Io lo ho pensato così.
Sia
$P = \text{#pozzi}$
$R = \text{#raffinerie}$
le variabili di decisione sono $x_{i,j}$ dove rappresenta il numero di barili per milione, trasportati dal pozzo $i$ alla raffineria $j$
I costi di trasporto $c(p,r)$ dal pozzo $p$ alla raffineria $r$ li rappresentiamo con $c_{i,j}$
L'estrazione di petrolio per ogni pozzo lo rappresentiamo con $E_i$
La capacità attuale delle raffinerie lo rappresentiamo con $D_j$
Quello che dobbiamo minimizzare sono i costi di trasporto, dove implica il calcolo dei barili trasportati calcolati nelle variabili. Perciò:
\[\min_{{x_{i,j}}}\ \sum_{i=1}^{P} \sum_{j=1}^{R} c_{i,j}*x_{i,j}\]
vincolo per uguagliare i barili estratti per ogni pozzo (non ci sono ammortamenti in magazzini vari, ma ogni trasporto è unico)
\[\forall i,\ \sum_{j=1}^{R} x_{i,j} = E_i\ |\ i=1,...,P\]
vincolo per uguagliare la capacità di raffinamento attuale, si aggiorna con il vincolo sopra.
\[\forall j,\ \sum_{i=1}^{P-1} x_{i,j} = D_j\ |\ j=1,...,R\]
notare che il vincolo utilizza SOLO i pozzi antecedenti all'aggiunta, segnato con $P-1$
non negatività ...
vedi se ti va bene
a te lascio capire come ricostruire la tua soluzione, così vediamo se ti è chiaro cosa si è fatto
EDIT:
modificato alcune cose per risolvere effettivamente il problema.
classico problema di ottimizzazione dei trasporti. La tua impostazione non mi convince.
Io lo ho pensato così.
Sia
$P = \text{#pozzi}$
$R = \text{#raffinerie}$
le variabili di decisione sono $x_{i,j}$ dove rappresenta il numero di barili per milione, trasportati dal pozzo $i$ alla raffineria $j$
I costi di trasporto $c(p,r)$ dal pozzo $p$ alla raffineria $r$ li rappresentiamo con $c_{i,j}$
L'estrazione di petrolio per ogni pozzo lo rappresentiamo con $E_i$
La capacità attuale delle raffinerie lo rappresentiamo con $D_j$
Quello che dobbiamo minimizzare sono i costi di trasporto, dove implica il calcolo dei barili trasportati calcolati nelle variabili. Perciò:
\[\min_{{x_{i,j}}}\ \sum_{i=1}^{P} \sum_{j=1}^{R} c_{i,j}*x_{i,j}\]
vincolo per uguagliare i barili estratti per ogni pozzo (non ci sono ammortamenti in magazzini vari, ma ogni trasporto è unico)
\[\forall i,\ \sum_{j=1}^{R} x_{i,j} = E_i\ |\ i=1,...,P\]
vincolo per uguagliare la capacità di raffinamento attuale, si aggiorna con il vincolo sopra.
\[\forall j,\ \sum_{i=1}^{P-1} x_{i,j} = D_j\ |\ j=1,...,R\]
notare che il vincolo utilizza SOLO i pozzi antecedenti all'aggiunta, segnato con $P-1$
non negatività ...
vedi se ti va bene

a te lascio capire come ricostruire la tua soluzione, così vediamo se ti è chiaro cosa si è fatto

EDIT:
modificato alcune cose per risolvere effettivamente il problema.
Per risolvere il secondo problema, bisogna considerare la stessa formulazione e le stesse idee fatte per il primo problema.
Si cerca ancora di minimizzare i costi. Visto che è l'azienda deve ottimizzare i costi globalmente, il problema si riduce alla somma del problema di minimo del trasporto pozzi-raffinerie, più il problema di minimo del trasporto raffinerie-distributori.
Modifico la notazione del primo post per semplificare il tutto ed aggiungo delle varibili di decisione per risolvere il secondo problema.
Siano $P,R,D$ insiemi ordinati (secondo la tabella):
$P= \{\text{i | i=produzione massima singoli pozzi}\}$
$R= \{\text{j | j=capacità di raffinamento attuale}\}$
$D= \{\text{t | t=richieste distributori}\}$
le variabili di decisione per il secondo problema sono $y_{j,t}$ dove rappresenta il numero di barili per milione, trasportati dalla raffineria $j$ al distributore $t$
I costi di trasporto $d(r,d)$ dalla raffineria $r$ al distributore $t$ li rappresentiamo con $d_{j,t}$
Quello che dobbiamo minimizzare sono i costi di trasporto in aggiunta al primo problema avremo:
\[\min_{{x_{i,j},y_{j,t}}}\ \sum_{i=1}^{|P|} \sum_{j=1}^{|R|} c_{i,j}*x_{i,j} \ +\ \sum_{j=1}^{|R|} \sum_{t=1}^{|D|} d_{j,t}*y_{j,t}\]
vincoli per il primo problama:
- \(\forall i,\ \sum_{j=1}^{|R|} x_{i,j} = P_i\ |\ i=1,...,|P|\)
- \(\forall j,\ \sum_{i=1}^{|P-1|} x_{i,j} = R_j\ |\ j=1,...,|R|\)
- vincolo per limitare (ugugliare) cioè che viene trasportato dalla raffinera al distributore. I barili richiesti non devono essere minori, ne devono essere maggiori (non c'è magazzino al distributore), perciò:
\[\forall t,\ \sum_{j=1}^{|R|} y_{i,j} = D_t\ |\ t=1,...,|D|\]
- vincolo per uguagliare ciò che viene prodotto dalla raffineria con l'aggiunta del nuovo pozzo e ciò che viene richiesto dai distributori. Ciò che viene prodotto deve essere uguale a ciò che viene distribuito, bisogna ricorda che non c'è magazzino.
\[\forall j,\ \sum_{i=1}^{|P|} x_{i,j} = \forall t,\ \sum_{j=1}^{|R|} y_{j,t}\ |\ j=1,...,|R|\; \ t=1,...,|D|\]
- non negatività ...
la soluzione del problema, cioè di quanto aumenterà singolarmente la capcità di produzione delle raffinerie, saranno nelle varibili ${x_10,x_11,x_12}$
Si cerca ancora di minimizzare i costi. Visto che è l'azienda deve ottimizzare i costi globalmente, il problema si riduce alla somma del problema di minimo del trasporto pozzi-raffinerie, più il problema di minimo del trasporto raffinerie-distributori.
Modifico la notazione del primo post per semplificare il tutto ed aggiungo delle varibili di decisione per risolvere il secondo problema.
Siano $P,R,D$ insiemi ordinati (secondo la tabella):
$P= \{\text{i | i=produzione massima singoli pozzi}\}$
$R= \{\text{j | j=capacità di raffinamento attuale}\}$
$D= \{\text{t | t=richieste distributori}\}$
le variabili di decisione per il secondo problema sono $y_{j,t}$ dove rappresenta il numero di barili per milione, trasportati dalla raffineria $j$ al distributore $t$
I costi di trasporto $d(r,d)$ dalla raffineria $r$ al distributore $t$ li rappresentiamo con $d_{j,t}$
Quello che dobbiamo minimizzare sono i costi di trasporto in aggiunta al primo problema avremo:
\[\min_{{x_{i,j},y_{j,t}}}\ \sum_{i=1}^{|P|} \sum_{j=1}^{|R|} c_{i,j}*x_{i,j} \ +\ \sum_{j=1}^{|R|} \sum_{t=1}^{|D|} d_{j,t}*y_{j,t}\]
vincoli per il primo problama:
- \(\forall i,\ \sum_{j=1}^{|R|} x_{i,j} = P_i\ |\ i=1,...,|P|\)
- \(\forall j,\ \sum_{i=1}^{|P-1|} x_{i,j} = R_j\ |\ j=1,...,|R|\)
- vincolo per limitare (ugugliare) cioè che viene trasportato dalla raffinera al distributore. I barili richiesti non devono essere minori, ne devono essere maggiori (non c'è magazzino al distributore), perciò:
\[\forall t,\ \sum_{j=1}^{|R|} y_{i,j} = D_t\ |\ t=1,...,|D|\]
- vincolo per uguagliare ciò che viene prodotto dalla raffineria con l'aggiunta del nuovo pozzo e ciò che viene richiesto dai distributori. Ciò che viene prodotto deve essere uguale a ciò che viene distribuito, bisogna ricorda che non c'è magazzino.
\[\forall j,\ \sum_{i=1}^{|P|} x_{i,j} = \forall t,\ \sum_{j=1}^{|R|} y_{j,t}\ |\ j=1,...,|R|\; \ t=1,...,|D|\]
- non negatività ...
la soluzione del problema, cioè di quanto aumenterà singolarmente la capcità di produzione delle raffinerie, saranno nelle varibili ${x_10,x_11,x_12}$
