Problema di ottimizzazione discreta
Ciao a tutti, vorrei chiedervi aiuto riguardo un esercizio d'esame che non riesco assolutamente ad impostare, sò che il testo è un pò lunghetto e spero che qualcuno abbia voglia di perdere un pò di tempo. Sò che è una formulazione di BIN PACKING manon riesco ad avere l'intuizione per sbloccare il processo per la soluzione del problema. Il problema è il seguente:
Un azienda si deve rifornire di m = 8 diverse materie prime da un certo insieme di n = 7 fornitori.
Ogni fornitore è in grado di rifornire numerose materie prime all’azienda; il generico elemento qij di una matrice Q data indica il numero di casse di materia j che il fornitore DEVE fornire all’azienda;
scrivere una formulazione per determinare il minimo numero di camion necessari per rifornire l’azienda di tutte le materie prime di cui ha bisogno sapendo che qij ≤ 26 per ogni i e per ogni j, e che:
Tutte le qij casse di una materia prima j di un fornitore i devono viaggiare su uno stesso camion;
Tutte le materie prime di uno stesso fornitore devono essere assegnate a non più di due camion;
In ogni camion non entrano più di 26 casse;
La materia prima 2 e la materia prima 5 (qualunque sia il fornitore) non possono stare su uno stesso camion;
Se la materia prima 6 del fornitore 3 viene assegnata al camion 2, allora la materia prima 4 del fornitore 2 deve essere assegnata al camion 1.
Grazie mille in anticipo!!
Un azienda si deve rifornire di m = 8 diverse materie prime da un certo insieme di n = 7 fornitori.
Ogni fornitore è in grado di rifornire numerose materie prime all’azienda; il generico elemento qij di una matrice Q data indica il numero di casse di materia j che il fornitore DEVE fornire all’azienda;
scrivere una formulazione per determinare il minimo numero di camion necessari per rifornire l’azienda di tutte le materie prime di cui ha bisogno sapendo che qij ≤ 26 per ogni i e per ogni j, e che:
Tutte le qij casse di una materia prima j di un fornitore i devono viaggiare su uno stesso camion;
Tutte le materie prime di uno stesso fornitore devono essere assegnate a non più di due camion;
In ogni camion non entrano più di 26 casse;
La materia prima 2 e la materia prima 5 (qualunque sia il fornitore) non possono stare su uno stesso camion;
Se la materia prima 6 del fornitore 3 viene assegnata al camion 2, allora la materia prima 4 del fornitore 2 deve essere assegnata al camion 1.
Grazie mille in anticipo!!
Risposte
Ho provato a risolverlo, però dagli una occhiata e dimmi se qualcosa non ti torna. Magari ho fatto qualche errore!
Lascia perdere gli indici che ti da il testo e prova a ragionare così.
Raggruppa le merci di ogni fornitore e disegna un grafo bipartito. Avrai dalla parte sinistra del tuo grafo tutte le Materie Prime (MP) e sul lato destro tutti i camion a disposizione. L'indice delle materie prime sarà $i$, quello dei camion sarà $j$.
Immagina di aver ordinato le materie prime in base al fornitore. Quindi le MP per $i=1,2,3,4,5,6,7,8$ saranno del primo fornitore, le MP $i=9,10,11,12,13,14,15,16$ saranno del secondo, le MP $i=17,18,19,20,21,22,23,24$ saranno del terzo, le MP $i=25,26,27,28,29,30,31,32$ del quarto, le MP $i=33,34,35,36,37,38,39,40$ del quinto, le MP $i=41,42,43,44,45,46,47,48$ del sesto, le MP $i=49,50,51,52,53,54,55,56$ del settimo. Ovviamente essendo messe in ordine le prime di ogni gruppo sono lo stesso tipo di materia prima[nota]Ovvero prima quella che ora è $x_1$ era $x_(1,1)$, quella che ora è $x_9$ era $ x_(2,1)$, quella che ora è $x_17$ era $x_(3,1)$ e così via per tutte le MP di tipo 1 e per quelle di ogni altro tipo[/nota], stessa cosa per le seconde, per le terze, per le quarte, per le quinte, per le seste e per le settime.
Posta questa notazione il vecchio peso $q_(i,j)=p_i$ [nota]I significati del pedice $i$ sono diversi. Prima i era il fornitore, ora è una materia prima. Prima $i=1,...,8$ ora $i=1,...,56$[/nota]
Ti anticipo le due variabili che userò:
$x_(i,j)=\{(=1 text( se MP i sta in camion j)), (=0 text( se MP i non sta in camion j)):}$
$y_j = \{(=1 text( se il camion j è scelto)), (=0 text( se il camion j non è scelto)):}$
Detto questo possiamo provare a scrivere i vari vincoli:
1° Vincolo (MP dello stesso tipo e dello stesso fornitore vanno nello stesso camion)
$\sum_{j=1}^14 x_(i,j)<=1 text( i=1,...56)$
2° Vincolo (Tutte le MP dello stesso fornitore vanno al max in due camion)
$\sum_{i=1}^8 x_(i,j)<= 2 text( j=1,...,14)$
$\sum_{i=9}^16 x_(i,j)<= 2 text( j=1,...,14)$
$\sum_{i=17}^24 x_(i,j)<= 2 text( j=1,...,14)$
$\sum_{i=25}^32 x_(i,j)<= 2 text( j=1,...,14)$
$\sum_{i=33}^40 x_(i,j)<= 2 text( j=1,...,14)$
$\sum_{i=41}^48 x_(i,j)<= 2 text( j=1,...,14)$
$\sum_{i=49}^56 x_(i,j)<= 2 text( j=1,...,14)$
Sono i vincoli, nell'ordine, per il 1°,2°,3°,4°,5°,6°,7° fornitore.
3°Vincolo (capacità max camion pari a 26)
$\sum_{i=1}^56 p_i x_(i,j)<=26 text( j=1,...,14)$
4° Vincolo (MP tipo 2 e MP tipo 5 non possono stare sullo stesso camion)
$x_(h,j)+x_(k,j)<=1 text ( con h=2,10,18,26,34,42,50 e con k=5,13,21,29,37,45,53 e j=1,...,14)$
5° Vincolo (MP 6 del fornitore 3 e MP4 del fornitore 2)
$x_(22,2)<=x_(12,1)$
Altri Vincoli necessari al funzionamento della formulazione
$M sum_{j=1}^14 x_(i,j)>=p_i text( i=1,...,56)$ [nota]Dice che se la materia $i$ è spedita allora deve essere caricato su un camion. Il fatto che sia uno solo sta nei precedenti vincoli[/nota]
$\sum_{i=1}^56 x_(i,j)<=My_j text( j=1,...,14)$
$M$ è un numero molto grande utile solo a far si che quando $x_(i,j)=1$ sia verificato il vincolo nel primo caso oppure $y_j$ sia costretto ad essere attivo nel secondo caso.
La funzione obiettivo è quindi:
$min \sum_{j=1}^14 y_j$
Spero di non aver fatto errori e soprattutto di essere stato chiaro...
Lascia perdere gli indici che ti da il testo e prova a ragionare così.
Raggruppa le merci di ogni fornitore e disegna un grafo bipartito. Avrai dalla parte sinistra del tuo grafo tutte le Materie Prime (MP) e sul lato destro tutti i camion a disposizione. L'indice delle materie prime sarà $i$, quello dei camion sarà $j$.
Immagina di aver ordinato le materie prime in base al fornitore. Quindi le MP per $i=1,2,3,4,5,6,7,8$ saranno del primo fornitore, le MP $i=9,10,11,12,13,14,15,16$ saranno del secondo, le MP $i=17,18,19,20,21,22,23,24$ saranno del terzo, le MP $i=25,26,27,28,29,30,31,32$ del quarto, le MP $i=33,34,35,36,37,38,39,40$ del quinto, le MP $i=41,42,43,44,45,46,47,48$ del sesto, le MP $i=49,50,51,52,53,54,55,56$ del settimo. Ovviamente essendo messe in ordine le prime di ogni gruppo sono lo stesso tipo di materia prima[nota]Ovvero prima quella che ora è $x_1$ era $x_(1,1)$, quella che ora è $x_9$ era $ x_(2,1)$, quella che ora è $x_17$ era $x_(3,1)$ e così via per tutte le MP di tipo 1 e per quelle di ogni altro tipo[/nota], stessa cosa per le seconde, per le terze, per le quarte, per le quinte, per le seste e per le settime.
Posta questa notazione il vecchio peso $q_(i,j)=p_i$ [nota]I significati del pedice $i$ sono diversi. Prima i era il fornitore, ora è una materia prima. Prima $i=1,...,8$ ora $i=1,...,56$[/nota]
Ti anticipo le due variabili che userò:
$x_(i,j)=\{(=1 text( se MP i sta in camion j)), (=0 text( se MP i non sta in camion j)):}$
$y_j = \{(=1 text( se il camion j è scelto)), (=0 text( se il camion j non è scelto)):}$
Detto questo possiamo provare a scrivere i vari vincoli:
1° Vincolo (MP dello stesso tipo e dello stesso fornitore vanno nello stesso camion)
$\sum_{j=1}^14 x_(i,j)<=1 text( i=1,...56)$
2° Vincolo (Tutte le MP dello stesso fornitore vanno al max in due camion)
$\sum_{i=1}^8 x_(i,j)<= 2 text( j=1,...,14)$
$\sum_{i=9}^16 x_(i,j)<= 2 text( j=1,...,14)$
$\sum_{i=17}^24 x_(i,j)<= 2 text( j=1,...,14)$
$\sum_{i=25}^32 x_(i,j)<= 2 text( j=1,...,14)$
$\sum_{i=33}^40 x_(i,j)<= 2 text( j=1,...,14)$
$\sum_{i=41}^48 x_(i,j)<= 2 text( j=1,...,14)$
$\sum_{i=49}^56 x_(i,j)<= 2 text( j=1,...,14)$
Sono i vincoli, nell'ordine, per il 1°,2°,3°,4°,5°,6°,7° fornitore.
3°Vincolo (capacità max camion pari a 26)
$\sum_{i=1}^56 p_i x_(i,j)<=26 text( j=1,...,14)$
4° Vincolo (MP tipo 2 e MP tipo 5 non possono stare sullo stesso camion)
$x_(h,j)+x_(k,j)<=1 text ( con h=2,10,18,26,34,42,50 e con k=5,13,21,29,37,45,53 e j=1,...,14)$
5° Vincolo (MP 6 del fornitore 3 e MP4 del fornitore 2)
$x_(22,2)<=x_(12,1)$
Altri Vincoli necessari al funzionamento della formulazione
$M sum_{j=1}^14 x_(i,j)>=p_i text( i=1,...,56)$ [nota]Dice che se la materia $i$ è spedita allora deve essere caricato su un camion. Il fatto che sia uno solo sta nei precedenti vincoli[/nota]
$\sum_{i=1}^56 x_(i,j)<=My_j text( j=1,...,14)$
$M$ è un numero molto grande utile solo a far si che quando $x_(i,j)=1$ sia verificato il vincolo nel primo caso oppure $y_j$ sia costretto ad essere attivo nel secondo caso.
La funzione obiettivo è quindi:
$min \sum_{j=1}^14 y_j$
Spero di non aver fatto errori e soprattutto di essere stato chiaro...
Ciao
prima di tutto ti ringrazio per avermi risposto, sono totalmente daccordo con l'impostazione delle variabili iniziali purtroppo non riesco a comprendere bene il secondo vincolo:
nella tua impostazione sembra che nel j-esimo camion non vadano più di due materie prime mentre il testo sembra voler indicare che tutte le MP del singolo fornitore non vadano su più di 2 camion, forse è poco chiaro il testo o non ho ben compreso io.
Ti ringrazio nuovamente !!
prima di tutto ti ringrazio per avermi risposto, sono totalmente daccordo con l'impostazione delle variabili iniziali purtroppo non riesco a comprendere bene il secondo vincolo:
nella tua impostazione sembra che nel j-esimo camion non vadano più di due materie prime mentre il testo sembra voler indicare che tutte le MP del singolo fornitore non vadano su più di 2 camion, forse è poco chiaro il testo o non ho ben compreso io.
Ti ringrazio nuovamente !!
Hai ragione. Quando ho fatto l'esercizio ho letto male. Il bello è che quando, per spiegare i vincoli, ho riletto il testo non me ne sono accorto... ](/datas/uploads/forum/emoji/eusa_wall.gif "Brick wall")
Che ne pensi se scrivo:
$\sum_{i=1}^8 x_(i,j)<= Mz_(1,j) text( j=1,...,14)$
$\sum_{j=1}^14 z_(1,j)<= 2 $
$\sum_{i=9}^16 x_(i,j)<= Mz_(2,j) text( j=1,...,14)$
$\sum_{j=1}^14 z_(1,j)<= 2 $
$\sum_{i=17}^24 x_(i,j)<= Mz_(3,j) text( j=1,...,14)$
$\sum_{j=1}^14 z_(1,j)<= 2 $
$\sum_{i=25}^32 x_(i,j)<= Mz_(4,j) text( j=1,...,14)$
$\sum_{j=1}^14 z_(1,j)<= 2 $
$\sum_{i=33}^40 x_(i,j)<= Mz_(5,j) text( j=1,...,14)$
$\sum_{j=1}^14 z_(1,j)<= 2 $
$\sum_{i=41}^48 x_(i,j)<= Mz_(6,j) text( j=1,...,14)$
$\sum_{j=1}^14 z_(1,j)<= 2 $
$\sum_{i=49}^56 x_(i,j)<= Mz_(7,j) text( j=1,...,14)$
$\sum_{j=1}^14 z_(1,j)<= 2 $
Come hai visto ho aggiunto una variabile:
$z_(p,j)=\{(1 text( se almeno una MP del p-esimo fornitore è nel j-esimo camion)),(0 text( se nessuna MP del p-esimo fornitore è nel j-esimo camion)):}$
Il pedice $p$ serve solo per differenziare le variabili che mi dicono se il camion $j$ è stato caricato con almeno una MP del fornitore j-esimo.
Dovrebbe funzionare, se non sbaglio.
$\sum_{i=1}^8 x_(i,j)<= Mz_(1,j) text( j=1,...,14)$
$\sum_{j=1}^14 z_(1,j)<= 2 $
$\sum_{i=9}^16 x_(i,j)<= Mz_(2,j) text( j=1,...,14)$
$\sum_{j=1}^14 z_(1,j)<= 2 $
$\sum_{i=17}^24 x_(i,j)<= Mz_(3,j) text( j=1,...,14)$
$\sum_{j=1}^14 z_(1,j)<= 2 $
$\sum_{i=25}^32 x_(i,j)<= Mz_(4,j) text( j=1,...,14)$
$\sum_{j=1}^14 z_(1,j)<= 2 $
$\sum_{i=33}^40 x_(i,j)<= Mz_(5,j) text( j=1,...,14)$
$\sum_{j=1}^14 z_(1,j)<= 2 $
$\sum_{i=41}^48 x_(i,j)<= Mz_(6,j) text( j=1,...,14)$
$\sum_{j=1}^14 z_(1,j)<= 2 $
$\sum_{i=49}^56 x_(i,j)<= Mz_(7,j) text( j=1,...,14)$
$\sum_{j=1}^14 z_(1,j)<= 2 $
Come hai visto ho aggiunto una variabile:
$z_(p,j)=\{(1 text( se almeno una MP del p-esimo fornitore è nel j-esimo camion)),(0 text( se nessuna MP del p-esimo fornitore è nel j-esimo camion)):}$
Il pedice $p$ serve solo per differenziare le variabili che mi dicono se il camion $j$ è stato caricato con almeno una MP del fornitore j-esimo.
Dovrebbe funzionare, se non sbaglio.
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo