Ottimizzazione

ESERCIZIO (MEKO)

La Meko è una multinazionale specializzata nella produzione di due tipi di biocarburanti: il biometanolo e il biodimetiletere. Il processo produttivo richiede la lavorazione nei tre stabilimenti di preparazione, purificazione ed estrazione. I tempi necessari per la lavorazione di una tonnellata dei due biocarburanti sono riportati nella Tabella unitamente alla capacità produttiva giornaliera dei tre stabilimenti. Il responsabile del marketing aziendale ha confermato che ogni tonnellata prodotta di biometanolo e di biodimetiletere può essere venduta, realizzando un profitto (in €) pari a 540 e 590, rispettivamente. Definire il piano di produzione ottimale. Ottobre Pagina 68 N.B. Default UI -> WinUi (In desktop IDE) Ricorda il vincolo di non negatività nelle variabili. Ottobre Pagina 69 La funzione obiettivo può essere scritta come una variabile senza vincoli di segno. Ottobre Pagina 70 Scegliamo il modello matematico risolutore: Ottobre Pagina71Compiliamo e runniamo:
Possiamo far vedere i risultati utilizzando un file:
Ottobre Pagina 72
Ottobre Pagina 73
Creiamo una nuova pagina dal page manager: Ottobre Pagina 74
Creiamo un nuovo ambiente da cui visualizzare i risultati:
Impostazione del bottone:
Soluzione problema: Ottobre Pagina 75
PROBLEMA DI TRASPORTO
Il «problema di trasporto» è un classico problema di flusso su rete particolarmente utilizzato nell’ambito dell’logistica distributiva.
Siano date origini (ad esempio, stabilimenti di produzione) presso le quali è disponibile un certo prodotto in quantità pari a , e destinazioni (ad esempio, punti vendita), ciascuna delle quali caratterizzata da un valore di domanda , di prodotto (vedi figura successiva, 2.4), il costo unitario di trasporto del prodotto dall’origine i alla destinazione.
Il problema di trasporto consiste nel determinare il quantitativo di prodotto da inviare da ciascuna origine verso ciascuna destinazione in modo tale daminimizzare il costo complessivo di trasporto, rispettando i vincoli sulla quantità di prodotto disponibile presso ciascuna origine e garantendo il soddisfacimento delle domande da parte di ogni destinazione. Ottobre Pagina 76 Le variabili di decisione si possono indicare con Xij, ciascuna delle quali rappresenta la quantità di prodotto che occorre inviare dall'origine i alla destinazione j. Supponendo che sia possibile rifornire ogni destinazione da ogni origine, il problema di trasporto si può formulare nel modo seguente: ESERCIZIO Ges Group è un rivenditore umbro specializzato nella distribuzione di carni. L'azienda è titolare di due magazzini refrigerati per lo stoccaggio di tale prodotto a Gubbio e Spoleto e di quattro punti vendita all'ingrosso localizzati, oltre che presso i magazzini stessi, a Perugia e Terni. Le distanze chilometriche tra i magazzini refrigerati e i punti vendita sono riportate nella Tabella successiva (2.5). La

quantità media giornaliera di prodotto disponibile presso i magazzini di Gubbio e Spoleto risulta pari, rispettivamente, a 1350 kg e 1700 kg.

La richiesta media giornaliera (in kg) da parte dei punti vendita all’ingrosso di Gubbio, Spoleto, Perugia e Terni risulta pari a 450, 820, 500, 600, rispettivamente.

L’eventuale eccedenza di prodotto presso i due magazzini viene utilizzata per soddisfare la domanda di altri mercati.

Ottobre Pagina 77

Si assume che il trasporto sia realizzato tramite collegamenti diretti e con furgoni refrigerati di proprietà, a un costo chilometrico pari a 0,06 € per ogni kg di prodotto trasportato.

Il problema di trasporto può essere formulato utilizzando le variabili di decisione, ciascuna delle quali rappresentante la quantità media di prodotto trasportata giornalmente dal magazzino refrigerato al punto vendita all’ingrosso.

Il modello corrispondente è il seguente: Ottobre Pagina 78

Creiamo due insiemi di indici,

uno per le origini (i) e l'altro per le destinazioni (j):

Le variabili saranno a doppio indice:

Creiamo la matrice dei costi di trasporto:

Utilizziamo i current data per inserire i dati della matrice. Se utilizzassimo la definizione, tali dati non potrebbero essere cambiati in seguito. Ottobre Pagina 79

Creiamo i vettori offerta(i) e domanda(j): Ottobre Pagina 80

Creiamo i vettori offerta(i) e domanda(j): Ottobre Pagina 81

Definiamo i vincoli di domanda e offerta:

Funzione obiettivo: Ottobre Pagina 82

Modello matematico:

MainExecution: Ottobre Pagina 83

Attiviamo il main da una pagina a parte: impostiamo quindi le tabelle e il bottone.

Soluzione ottimale

Si osservi che esiste una capacità residua per i due magazzini refrigerati pari a 400 kg e 280 kg, rispettivamente, dal momento che la domanda complessiva media giornaliera è pari a 2370 kg, mentre la disponibilità di prodotto è di 3050 kg. Ottobre Pagina 84

3 Novembre 2020 (prof.ssa Bruni)

martedì 3 novembre 2020

10:57

Rendiamo il problema in forma standard:

Scriviamo il tableau rispetto alla base iniziale per verificare che il problema sia scritto in forma canonica:

Di fatto, non abbiamo limitazioni sul valore che x1 può assumere, in quanto la suddetta disequazione risulta sempre essere verificata per ogni x1 non negativa. Potremo quindi far entrare in base x1 con qualsivoglia valore.

La funzione obiettivo migliorerà quindi di 2 volte il valore x1 in modo indefinito.

È il caso di un problema inferiormente illimitato, in quanto possiamo continuamente migliorare il valore di funzione obiettivo semplicemente facendo crescere il valore di x1. Esiste dunque una successione infinita di valori di x1 che portano all'infinito il valore di funzione obiettivo. È un problema che viene risolto per ispezione.

La condizione sufficiente è che la colonna s presenti tutti elementi non positivi.

Novembre Pagina 85

Scriviamo il problema in forma standard:

Partendo da vincoli di <=

siccome aggiungiamo una variabile di slack in ogni vincolo e questa variabile compare solo in quel vincolo, è chiaro che il problema sarà in forma canonica rispetto alle nuove variabili introdotte. Scriviamo il tableau della base iniziale:

Base	x1	x2	x3	x4	x5	x6	x7	x8	x9	x10	x11	x12	x13	x14	x15	x16	x17	x18	x19	x20	x21	x22	x23	x24	x25	x26	x27	x28	x29	x30	x31	x32	x33	x34	x35	x36	x37	x38	x39	x40	x41	x42	x43	x44	x45	x46	x47	x48	x49	x50
z	-1	-1	-1	-1	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0
x5	1	0	0	0	1	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0
x6	0	1	0	0	0	1	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0

Essendo m=3 ed n=5, ci aspettiamo almeno n-m=2 componenti nulle e le rimanenti m non negative. Questa soluzione presenta però una componente in base (x5) nulla. È il caso di soluzione di base degenere. Potrebbe diventare un problema applicando il metodo del complesso, ovvero potremmo ciclare su diversi indici di base che corrispondono allo stesso vertice. Proviamo ad applicare il metodo del simplesso:

Base	x1	x2	x3	x4	x5	x6	x7	x8	x9	x10	x11	x12	x13	x14	x15	x16	x17	x18	x19	x20	x21	x22	x23	x24	x25	x26	x27	x28	x29	x30	x31	x32	x33	x34	x35	x36	x37	x38	x39	x40	x41	x42	x43	x44	x45	x46	x47	x48	x49	x50
z	-1	-1	-1	-1	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0
x5	1	0	0	0	1	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0
x6	0	1	0	0	0	1	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0

Abbiamo ottenuto una nuova base ma la stessa soluzione di base di prima. Essendo tutti i coefficienti di costo non negativi, la soluzione di base degenere risulta essere la soluzione ottima del problema. Solo facendo il cambio degenere, però, ci siamo accorti che tale soluzione corrispondesse a quella di ottimo. Se la soluzione nonfosse stata di ottimo, avremmo potuto ciclare all'infinito senza accorgercene, rimanendo di fatto sempre sullo stesso vertice. Esistono diversi metodi per interrompere il loop computazionale, e tra questi citiamo la regola di Bland: in caso di soluzione degenere, piuttosto che prendere la colonna a cui corrisponde il minimo coefficiente di costo ridotto, consideriamo la colonna con l'indice minimo e che presenta un coefficiente di costo ridotto strettamente negativo. Ricordiamo infine che non esiste corrispondenza biunivoca tra vertici e indici di base nel caso di soluzioni di base degeneri. Supponiamo di essere all'ottimo e di avere una situazione del genere: Alla variabile fuori dalla base x5 il coefficiente di costo ridotto associato è esattamente uguale a zero. Ricordiamo che un coefficiente di costo ridotto rappresenta il miglioramento o il peggioramento che possiamo avere nella funzione obiettivo a seguito della introduzione in base.

dellacorrispondente variabile.

Facendo entrare in base la variabile x5, la funzione obiettivo non peggiorerà né migliorerà in quanto il costo di coefficiente ridotto associato è nullo.

È una situazione in cui la soluzione ottima non è unica, bensì esistono infinite soluzioni ottime, in quanto abbiamo un coefficiente di costo ridotto nullo associato a una variabile fuori dalla base.

Possiamo avere due situazioni:

- Segmento di ottimo

- Semiretta di ottimo

Se gli elementi della colonna corrispondente alla variabile entrante in base presentano tutti coefficienti non positivi, allora l'altro vertice si trova all'infinito.

Avendo una soluzione ottima non di base, per trovare la corrispondente soluzione ottima di base, potremmo applicare il teorema fondamentale della programmazione lineare.

Novembre

Pagina 87

MODELLI DI PROGRAMMAZIONE LINEARE

Principali classi di modelli di PL

Modelli di pianificazione della produzione

• Modelli di miscelazione
• Modelli di ottimizzazione su reti
• Modelli di pianificazione della produzione

I modelli di pianificazione della produzione consentono di formulare problemi per l'allocazione ottimale di "risorse" (materie prime, macchinari, manodopera), disponibili in quantità limitata e utilizzate per realizzare un numero finito di "prodotti".

Per ciascun prodotto è noto il processo produttivo, riassumibile nel consumo di un quantitativo noto di risorse.

La vendita di ciascuna unità di prodotto genera un profitto noto e la funzione obiettivo consiste nel massimizzare il profitto derivante dalla vendita di tutti i prodotti realizzati.

Template di riferimento per i modelli di pianificazione della produzione

Si supponga di disporre di un numero m di risorse disponibili per la produzione di n

lista non ordinata:

• Si indichi con:
  • a , i = 1,…,m, j = 1,…,n, la quantità di risorsa i necessaria per produrre una unità di prodotto j;
  • ij(Elemento della matrice dei coefficienti tecnologici)
  • b , i = 1,…,m, la disponibilità massima della risorsa i;
  • ip , j = 1,…,n, il profitto lordo unitario ricavabile dalla vendita del prodotto j;
  • jx , j = 1,…,n, variabili di decisione indicante il livello di produzione del prodotto j.
• In alcuni casi, la realizzazione di un prodotto richiede la scelta di risorse disponibili tra più alternative (ad esempio, un’operazione meccanica di tornitura può essere eseguita su uno qualsiasi dei torni disponibili nell’officina).
• In questo caso le variabili di decisione esprimono il livello produttivo per ogni prodotto utilizzando una