Modelli di PL: trasporti I Problema dei trasporti: un esempio I Caso generale Trasporto di acque minerali I Un’industria di acque minerali ha due stabilimenti per il trattamento delle acque (Viterbo, Latina) e tre impianti di imbottigliamento (Napoli, Roma, Avezzano) I gli impianti devono essere riforniti giornalmente di 30, 40, 35 ettolitri risp. I gli stabilimenti trattano giornalmente 50 e 55 ettolitri risp. I il costo (Euro) per il trasporto di un ettolitro di acqua da ciascuno stabilimento a ciascun impianto `e il seguente Viterbo Latina Napoli 250 120 Roma 100 80 Avezzano 85 150 Formulare il problema di PL che permetta di determinare la quantit` a di acqua da trasportare da ciascuno stabilimento a ciascun impianto in modo da soddisfare le esigenze degli impianti, non lasciare giacenze negli stabilimenti e minimizzando il costo di trasporto Formulazione I variabili decisionali: xij ettolitri da trasportare dall’origine i alla destinazione j, con i ∈ [V, L], j ∈ [N, R, A] I funzione obiettivo: costo del trasporto min 250xV N + 100xV R + 85xV A + 120xLN + 80xLR + 150xLA I vincoli sull’assenza di giacenze xV N + xV R + xV A = 50 xLN + xLR + xLA = 55 I vincoli di domanda xV N + xLN = 30 xV R + xLR = 40 xV A + xLA = 35 I vincoli di non negativit` a xV N , xV R , xV A , xLN , xLR , xLA ≥ 0 Formulazione generale di un problema di trasporti I O1 , . . . , Om localit` a origine, ciascuna caratterizzata da un’offerta ai di bene I D1 , . . . , Dn localit` a destinazione, ciascuna caratterizzata da una richiesta bj di bene I costo cij di trasporto di una unit` a di bene dall’origine i alla destinazione j I vincoli sulla offerta/domanda I ipotesi: m X i=1 I I ai = n X bj j=1 tutto il bene disponibile in ciascuna origine deve essere trasportato (no giacenze) tutta la richiesta di bene in ciascuna destinazione deve essere soddisfatta esattamente (no eccessi) I determinare un modello di PL che corrisponda a minimizzare il costo complessivo di trasporto Formulazione I variabili decisionali: xij quantit` a di bene da trasportare dall’ origine Oi , i = 1, . . . , m alla destinazione Dj , j = 1, . . . , n I funzione obiettivo: min m X n X cij xij i=1 j=1 I vincoli sull’offerta: n X xij = ai , i = 1, . . . , m xij = bj , j = 1, . . . , n j=1 I vincoli sulla domanda: m X i=1 I vincoli di non-negativit` a: xij ≥ 0 i = 1, . . . m, j = 1, . . . , n Analisi Problema dei trasporti: min m X n X cij xij i=1 j=1 subject to n X xij = ai , i = 1, . . . , m j=1 m X xij = bj , j = 1, . . . , n i=1 xij ≥ 0 i = 1, . . . m, j = 1, . . . , n Teorema Il problema dei trasporti ammette una soluzione ammissibile se e solo se Pm Pn i=1 ai = j=1 bj Dimostrazione Necessit`a. Affinche una soluzione x ¯ij sia ammissibile deve essere: Pm Pn ¯ij j=1 x i=1 Pn j=1 Pm ¯ij i=1 x = Pm (somma dei vincoli offerta) = Pn (somma dei vincoli domanda) i=1 ai j=1 bj quindi: m X i=1 ai − n X j=1 bj = 0 Dimostrazione P Pn Sufficienza. Supponiamo che m i=1 ai = j=1 bj = A e dimostriamo che esiste una sol. ammissibile. Si scelga la soluzione x ¯ij = ai bj , A i = 1, . . . m, j = 1, . . . , n Si ha: •¯ xij ≥ 0 per la non-negativit` a degli ai , bj • Pn x ¯ij = Pn ai bj A = ai A Pn bj = ai • Pm x ¯ij = Pm ai bj A = bj A Pm aj = bj j=1 i=1 j=1 i=1 j=1 i=1 quindi x ¯ij `e soluzione ammissibile per il problema dei trasporti Analisi: interezza delle soluzioni Teorema Se nel problema dei trasporti le ai , i = 1, . . . , m e le bj , j = 1, . . . , n sono intere e se il problema ammette soluzione ottima, allora ha una soluzione ottima intera. Questo risultato ci consente di eliminare i vincoli di interezza e di utilizzare un algoritmo di PL anche in presenza di beni indivisibili Varianti del problema I alcune coppie O/D possono non essere collegate I il collegamento fra certe coppie O/D pu` o avere capacit`a limitata P Pn pu`o esserci eccesso di offerta: m i=1 ai ≥ j=1 bj ; in questo caso i vincoli diventano I I I I Pn xij ≤ ai , Pj=1 m x i=1 ij ≥ bj , i = 1, . . . , m j = 1, . . . , n per ricondurlo alla formulazione con vincoli di uguaglianza, si pu`o introdurre una fittizia che abbia una richiesta P Pdestinazione n pari a m a − b ed un costo di trasporto nullo da i j i=1 j=1 ogni origine
© Copyright 2024 ExpyDoc
