Formulazione di un problema di programmazione lineare
Ho delle difficoltà riguardo la formulazione di un problema di programmazione lineare.Il problema in questione è il n.2 nell'immagine seguente (cliccare per ingrandire):
Io ho provato a svolgerlo nel seguente modo:
come funzione obiettivo ho individuato $ min Z = 200X_1 + 180X_2 $
200 è dato dal costo singolo di una notte per 2 (durata dell'evento a barcellona)
180 è dato dal costo singolo di una notte per 3 (durata dell'evento a milano)
per i vincoli invece:
$ 400X_1 + 400X_2 >= 1600 $ il valore 400 è dato dal costo complessivo per inviare un dipendente,mentre 1600 è la somma dei costi per l'invio di 4 dipendenti
$ 580X_1 + 280X_2 >= 1400 $
purtroppo tutto ciò non credo sia corretto,per i valori di $ X_1,X_2$ che mi escono,come va svolto l'esercizio? Grazie anticipatamente
Io ho provato a svolgerlo nel seguente modo:
come funzione obiettivo ho individuato $ min Z = 200X_1 + 180X_2 $
200 è dato dal costo singolo di una notte per 2 (durata dell'evento a barcellona)
180 è dato dal costo singolo di una notte per 3 (durata dell'evento a milano)
per i vincoli invece:
$ 400X_1 + 400X_2 >= 1600 $ il valore 400 è dato dal costo complessivo per inviare un dipendente,mentre 1600 è la somma dei costi per l'invio di 4 dipendenti
$ 580X_1 + 280X_2 >= 1400 $
purtroppo tutto ciò non credo sia corretto,per i valori di $ X_1,X_2$ che mi escono,come va svolto l'esercizio? Grazie anticipatamente
Risposte
Avrei un dubbio sul testo quando dice "almeno due giorni" riferito alla durata di Barcellona. Non capisco se voglia contare anche i giorni oppure no.
Comunque io proverei così:
$min \sum_{i=1}^12 sum_{j=1}^2 cf_(i,j) x_(i,j) +\sum_{i=1}^12 sum_{j=1}^2 cv_(i,j) x_(i,j)$
$text (s.t.)$
$\sum_{j=1}^2 x_(i,j)<=1 text( con i=1,....,12)$
$\sum_{i=1}^12 x_(i,1)>=5$
$\sum_{i=1}^12 x_(i,2)>=4$
$x_(i,j) in {0,1}^(12xx2)$
Il vettore dei costi fissi è:
$cf=(400,400,400,400,400,400,200,200,200,200,200,200,100,100,100,100,100,100,200,200,200,200,200,200)$
Mentre per i costi variabili:
$cv=(180,180,180,180,180,180,200,200,200,200,200,200,180,180,180,180,180,180,200,200,200,200,200,200)$
Il vettore $x_(i,j)$ mi dice se l'i-esimo dipendente è andato nella j-esima città. Quindi evidentemente $i$ va da uno a dodici (che sono i 6+6 dipendenti disponibili e $j$ può essere o uno o due (ovvero Milano o Barcellona).
Comunque io proverei così:
$min \sum_{i=1}^12 sum_{j=1}^2 cf_(i,j) x_(i,j) +\sum_{i=1}^12 sum_{j=1}^2 cv_(i,j) x_(i,j)$
$text (s.t.)$
$\sum_{j=1}^2 x_(i,j)<=1 text( con i=1,....,12)$
$\sum_{i=1}^12 x_(i,1)>=5$
$\sum_{i=1}^12 x_(i,2)>=4$
$x_(i,j) in {0,1}^(12xx2)$
Il vettore dei costi fissi è:
$cf=(400,400,400,400,400,400,200,200,200,200,200,200,100,100,100,100,100,100,200,200,200,200,200,200)$
Mentre per i costi variabili:
$cv=(180,180,180,180,180,180,200,200,200,200,200,200,180,180,180,180,180,180,200,200,200,200,200,200)$
Il vettore $x_(i,j)$ mi dice se l'i-esimo dipendente è andato nella j-esima città. Quindi evidentemente $i$ va da uno a dodici (che sono i 6+6 dipendenti disponibili e $j$ può essere o uno o due (ovvero Milano o Barcellona).
"Intermat":Per l'evento di Milano sono 3 giorni e basta,per Barcellona dice almeno 2,però penso ne vadano contati solamente 2 visto che non si conosce la durata dell'intero evento.Comunque sia,non è possibile esprimere il problema nella forma standard similmente a quanto ho scritto sopra? anche perchè di esercizi in questa forma,in classe non ne abbiamo mai fatto uno...
Avrei un dubbio sul testo quando dice "almeno due giorni" riferito alla durata di Barcellona. Non capisco se voglia contare anche i giorni oppure no.
Comunque io proverei così:
$min \sum_{i=1}^12 sum_{j=1}^2 cf_(i,j) x_(i,j) +\sum_{i=1}^12 sum_{j=1}^2 cv_(i,j) x_(i,j)$
$text (s.t.)$
$\sum_{j=1}^2 x_(i,j)<=1 text( con i=1,....,12)$
$\sum_{i=1}^12 x_(i,1)>=5$
$\sum_{i=1}^12 x_(i,2)>=4$
$x_(i,j) in {0,1}^(12xx2)$
Il vettore dei costi fissi è:
$cf=(400,400,400,400,400,400,200,200,200,200,200,200,100,100,100,100,100,100,200,200,200,200,200,200)$
Mentre per i costi variabili:
$cv=(180,180,180,180,180,180,200,200,200,200,200,200,180,180,180,180,180,180,200,200,200,200,200,200)$
Il vettore $x_(i,j)$ mi dice se l'i-esimo dipendente è andato nella j-esima città. Quindi evidentemente $i$ va da uno a dodici (che sono i 6+6 dipendenti disponibili e $j$ può essere o uno o due (ovvero Milano o Barcellona).
Probabilmente lo puoi anche scrivere nella forma che hai proposto tu, però devi mettere, in ogni caso, il vincolo di interezza. Non è possibile mandare 1,5 persone o cose simili.
"Intermat":Mettiamo caso che il problema formulato in quel modo sia corretto,ma così come faccio a rappresentarlo graficamente e a risolverlo? L'esercizio a detta del prof era breve e veloce,per risolverlo in quel modo come dovrei fare?
Probabilmente lo puoi anche scrivere nella forma che hai proposto tu, però devi mettere, in ogni caso, il vincolo di interezza. Non è possibile mandare 1,5 persone o cose simili.
Ipotizzando che sia giusta la tua formulazione (cosa di cui non sono proprio convinto) potresti riscrivere il problema così:
$20* min 10x_1 + 9x_2$
$s.t$
$x_1+x_2>=4$
$29x_1+14x_2>=7$
$x>=0 text( e intero)$
Evidentemente il secondo vincolo è inutile, poichè dice che sono ammissibili tutte le coppie $(x_1,x_2)!=(0,0)$ il che era già implicito nel primo vincolo.
A questo punto puoi risolverlo per via grafica sapendo che l'ottimo si trova sempre sulla poligonale che delimita il problema. Evidentemente l'ottimo lo trovi in $(x_1,x_2)=(0,4)$, il che è evidente dalla f.o dato che $x_2$ ha un coefficiente minore rispetto ad $x_1$.
$20* min 10x_1 + 9x_2$
$s.t$
$x_1+x_2>=4$
$29x_1+14x_2>=7$
$x>=0 text( e intero)$
Evidentemente il secondo vincolo è inutile, poichè dice che sono ammissibili tutte le coppie $(x_1,x_2)!=(0,0)$ il che era già implicito nel primo vincolo.
A questo punto puoi risolverlo per via grafica sapendo che l'ottimo si trova sempre sulla poligonale che delimita il problema. Evidentemente l'ottimo lo trovi in $(x_1,x_2)=(0,4)$, il che è evidente dalla f.o dato che $x_2$ ha un coefficiente minore rispetto ad $x_1$.
"Intermat":No no,sicuramente la mia formulazione è sbagliata,io intendevo solo dire che per risolvere graficamente il problema avevo bisogno che il problema fosse formulato in quel modo.Comunque sia,non sono convinto della soluzione,mi spiego,se la soluzione è (0,4) significherebbe che l'azienda invia solo 4 dipendenti da una delle due sedi,dunque non verrebbe rispettato il vincolo del numero minimo di dipendenti alle convention,ovvero almeno 5 a Milano e almeno 4 a Barcellona,dico bene? o sto sbagliando io?
Ipotizzando che sia giusta la tua formulazione (cosa di cui non sono proprio convinto) potresti riscrivere il problema così:
$20* min 10x_1 + 9x_2$
$s.t$
$x_1+x_2>=4$
$29x_1+14x_2>=7$
$x>=0 text( e intero)$
Evidentemente il secondo vincolo è inutile, poichè dice che sono ammissibili tutte le coppie $(x_1,x_2)!=(0,0)$ il che era già implicito nel primo vincolo.
A questo punto puoi risolverlo per via grafica sapendo che l'ottimo si trova sempre sulla poligonale che delimita il problema. Evidentemente l'ottimo lo trovi in $(x_1,x_2)=(0,4)$, il che è evidente dalla f.o dato che $x_2$ ha un coefficiente minore rispetto ad $x_1$.
Infatti la tua formulazione è sbagliata. Io ti ho solo spiegato come risolvere graficamente il problema nella forma da te scritta. Poi è ovvio che sia sbagliata la soluzione rispetto al problema originario dato che non hai tenuto in considerazione i vincoli che imponevano che almeno quattro dipendenti fossero inviati da una parte e almeno quattro fossero inviati dall'altra.
"Intermat":Forse c'è stato un equivoco,che la mia formulazione fosse sbagliata ne ero certo,ed inoltre so risolvere graficamente un problema formulato in quel modo,la mia richiesta era "come posso formulare la soluzione scritta da te nel modo che mi consentirebbe di risolvere il problema graficamente su due assi?"
Infatti la tua formulazione è sbagliata. Io ti ho solo spiegato come risolvere graficamente il problema nella forma da te scritta. Poi è ovvio che sia sbagliata la soluzione rispetto al problema originario dato che non hai tenuto in considerazione i vincoli che imponevano che almeno quattro dipendenti fossero inviati da una parte e almeno quattro fossero inviati dall'altra.
Formulata nel modo che ti ho proposto non puoi usare il metodo grafico. Dovresti usare il Branch and Bound e risolvere i vari problemi figli rilassando il vincolo di interezza.
"Intermat":Purtroppo non è un argomento che fa parte del programma del corso di modelli e ottimizzazione che ho frequentato,quindi ti chiedo un ultima cosa,saresti così gentile da aiutarmi a formulare il problema in modo da risolverlo graficamente? Poi se non riesci ad aiutarmi non è un problema,cercherò un altro modo o aspetterò che mi risponda qualcun'altro,comunque sia ti ringrazio lo stesso delle delucidazioni.
Formulata nel modo che ti ho proposto non puoi usare il metodo grafico. Dovresti usare il Branch and Bound e risolvere i vari problemi figli rilassando il vincolo di interezza.
Per risolverlo con il metodo grafico devi avere solo due incognite. Sinceramente non riesco a capire come si possa formulare tale problema con due sole incognite. Infatti si dovrebbe tenere conto della città di arrivo e di partenza in entrambi i casi. Il che vuol dire avere 4 variabili.
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo