Appunti sul linguaggio di programmazione MPL · 1 2 3 123 Appunti sul linguaggio di programmazione...

1

2

3

1 2 3

Appunti sul linguaggio diprogrammazione MPL

Lorenzo Brunetta , Michele D�Amico e Ivan Luzzi

Milano, Agosto 2000

Dipartimento di Elettronica e Informazione, Politecnico of Milano, Piazza L.da Vinci 32, 20133 Milano, e-mail: [email protected]

Dipartimento di Matematica Pura e Applicata, Università di Padova, ViaBelzoni 7, 35131 Padova � ITALY, e-mail:[email protected]

Dipartimento di Matematica Pura e Applicata, Università di Padova, ViaBelzoni 7, 35131 Padova � ITALY, e-mail:[email protected]

Indice

1 Introduzione 1

2 Programmazione con il linguaggio MPL 3MPL

MPLMPL

MPL

3 Un modello di bilanciamento della produzione 16

4 Esempi di risoluzione di problemi classici della Programma-zione Lineare 21

5 Un Modello di Piani�cazione della Produzione a Multi-Pe-riodo 32

2.1 Scrivere e risolvere un Modello con . . . . . . . . . . . 32.1.1 La Prima Sessione in . . . . . . . . . . . . . . . 32.1.2 Utilizzare il Sistema di Aiuto in . . . . . . . . . 6

2.2 Caratteristiche generali . . . . . . . . . . . . . . . . . . . . . 62.3 Struttura di un programma . . . . . . . . . . . . . . . 8

2.3.1 TITLE . . . . . . . . . . . . . . . . . . . . . . . . . . . 82.3.2 INDEX . . . . . . . . . . . . . . . . . . . . . . . . . . 82.3.3 DATA . . . . . . . . . . . . . . . . . . . . . . . . . . . 102.3.4 DECISION . . . . . . . . . . . . . . . . . . . . . . . . 112.3.5 MACROS . . . . . . . . . . . . . . . . . . . . . . . . . 122.3.6 MODEL . . . . . . . . . . . . . . . . . . . . . . . . . . 122.3.7 SUBJECT TO . . . . . . . . . . . . . . . . . . . . . . 132.3.8 BOUNDS . . . . . . . . . . . . . . . . . . . . . . . . . 142.3.9 FREE . . . . . . . . . . . . . . . . . . . . . . . . . . . 152.3.10 INTEGER e BINARY . . . . . . . . . . . . . . . . . 15

3.1 Formulazione del Modello . . . . . . . . . . . . . . . . . . . . 163.2 Vedere e Analizzare la Soluzione . . . . . . . . . . . . . . . . 17

4.1 Un problema di assegnamento . . . . . . . . . . . . . . . . . . 214.2 Un primo problema dei trasporti . . . . . . . . . . . . . . . . 234.3 Un problema della dieta . . . . . . . . . . . . . . . . . . . . . 254.4 Un problema di produzione più complesso . . . . . . . . . . . 28

5.1 Formulazione del Modello . . . . . . . . . . . . . . . . . . . . 335.2 Risolvere il Modello e Analizzare la Soluzione . . . . . . . . . 34

I

6 Un Modello di Piani�cazione con più Impianti di Produzio-ne 39

7 Modelli di Trasporto 44

8 Un Modello con Più Macchinari 51


7.1 Usare la Condizione Where sui Vettori di Variabili . . . . . . 447.2 Vincoli di Bilanciamento degli Impianti . . . . . . . . . . . . 457.3 Un Modello di trasporto tra impianti di produzione . . . . . . 467.4 Formulazione del modello . . . . . . . . . . . . . . . . . . . . 477.5 Risolvere il Modello e Analizzare la Soluzione . . . . . . . . . 48


II

MPL

MPLMPL

MPL

MPL

�generatori algebrici di modelli�

Tutorial

http://www.maximal-usa.com

L�obiettivo di queste dispensa è quello di fornire una guida in italiano uti-le per apprendere le idee di base di uno dei software di ottimizzazione piùdiffusi. Gli argomenti trattati sono di livello elementare e, leggendo que-ste pagine, chiunque abbia un minimo di dimestichezza con un qualsiasilinguaggio di programmazione dovrebbe poter apprendere velocemente lametodologia necessaria per creare e risolvere problemi di ottimizzazione li-neare. Le pagine che seguono hanno quindi uno scopo puramente didatticoe speriamo possano essere uno strumento utile a chi si avvicina per la primavolta a questo programma di ottimizzazione.Nel primo capitolo viene spiegata la �loso�a di base sulla quale si fondano isoftware detti . Nel secondo capitolo vieneintrodotta la forma di base di un modello in . Si è volutamente datauna struttura più rigida di quella effettivamente necessaria per aiutare chisi trova per la prima volta ad affrontare questo metodo di programmazionea individuare i vari passi necessari per tradurre un problema di ottimiz-zazione in un modello . Nel terzo, quinto, sesto, settimo ed ottavocapitolo sono discussi i modelli contenuti nel di . Nel quartocapitolo sono discussi e tradotti in modelli alcuni classici problemi diprogrammazione lineare.

È possibile ottenere la versione studenti del software con licenzad�uso semestrale al sito .

III

MPL( ) ( )

MPL

MPL

�

�

�

↔ ↔↑

↑

Capitolo 1

Introduzione

utente programma es. solutore es.CPLEX

dati

database

Ai sostanziali progressi ottenuti nella programmazione matematica dagli an-ni �50 agli anni �70 non è corrisposto un adeguato utilizzo applicativo deglistumenti matematici sviluppati. Questo è dovuto, in gran parte, alle diffi-coltà computazionali ed informatiche insite nella stesura del modello, nellaraccolta ed organizzazione dei dati, nella programmazione degli algoritmisolutori e nell�analisi dei risultati ottenuti. Quindi, gli sforzi ottenuti incampo matematico, risultavano inutilizzabili a livello applicativo poiché l�ef-fettivo incremento nella velocità e potenza dei solutori si scontrava con lanecessità di creare software che interrogasse questi solutori e che gestissemodelli e dati appartenenti al modo reale. (e in generale i programmidetti �generatori algebrici di modelli�) nasce proprio per ovviare a questadifficoltà e si pongono come obiettivi:

fornire un linguaggio di programmazione ad alto livello che permettadi descrivere in modo semplice modelli reali anche molto complessi;

creare modelli indipendenti dal solutore utilizzato, in modo da potersfruttare sempre i solutori più potenti presenti sul mercato;

descrivere modelli nei quali la struttura logica del problema e i datiutilizzati possano essere considerati come entità diverse.

Uno schema formale per la situazione descritta può essere il seguente:

Utilizzando l�utente non deve più occuparsi direttamente dell�inter-rogazione del solutore, ma può concentrarsi sulla stesura del modello pro-grammando in un linguaggio di alto livello con il quale può descrivere molto

1

MPL

�

�

�

�

�

�

�

semplicemente problemi reali anche molto complessi. Inoltre il solutore puòessere sostituito senza dover modi�care la forma con la quale sono descrittii modelli. In�ne la possibilità di trattare in modo diverso i dati e struttu-ra logica dei problemi fa si che piccole modi�che nei dati o nella strutturadel modello siano gestibili senza dover riprogrammare completamente molterighe di codice. In�ne, la distinzione dati-modello permette di importare iparametri che caratterizzano l�istanza di un problema da un database ester-no lasciando libero l�utente di occuparsi solo della formulazione logica delmodello.Le principali caratteristiche di questi generatori algebrici di modelli sono leseguenti:

il linguaggio di programmazione utilizzato è semplice da imparare (ècomposto da poche parole chiave);

i codici che si realizzano sono essi stessi una rappresentazione concisaed elegante del modello;

è possibile inserire commenti o �de�nizioni linguistiche� che rendonosia l�input che l�output comprensibili anche da �non-programmatori�;

la maggior parte dei programmi creati sta in un unico documento ilche facilita il controllo e la creazione dei modelli;

nell�output vengono rappresentate, in modo comprensibile, tutte leoperazioni svolte dal solutore;

i programmi vengono scritti con un semplice editor di testo e sonoindipendenti dalla piattaforma sulla quale vengono eseguiti sia il pro-gramma, sia il solutore (anche se Windows è la piattaforma su cui èpiù usato);

ha circa 5 anni possiede una piccola libreria di esempi di modelliche comprende sia problemi lineari, che problemi non lineari, e untutorial.

2

Capitolo 2

2.1.1 La Prima Sessione in MPL

Programmazione con illinguaggio MPL

2.1 Scrivere e risolvere un Modello con MPL

Model Development Environment

Programmi Avvio Mpl for

MPL

MPL

MPLMPL

MPL

MPL

MPL

Eseguire l�applicazione MPL. MPLMPL

è l�acronimo di , cioè Ambientedi Sviluppo di Modelli; si tratta di un linguaggio di programmazione ad altolivello che permette di descrivere in modo semplice e intuitivo dei modelli diProgrammazione Lineare.

Si possono de�nire modelli speci�ci con dati assegnati, oppure modellipiù generali, che vengono associati di volta in volta con i dati letti da un �leesterno.

In questo capitolo, dopo una prima introduzione generale, verrannoanalizzate le diverse sezione che compongono un programma .

In questa sezione impareremo, attraverso una serie di passi elementari,come scrivere e risolvere un modello con . Alla �ne della sezione,saremo in grado di far partire , caricare e risolvere il modello, vedere lasoluzione. A questo punto, impareremo come si possano cambiare le opzionidi settaggio di attraverso le �nestre di dialogo. Inoltre, nell�ultimaparte di questa sezione, forniremo una breve descrizione del sistema di aiutodi .

Ci sono quattro semplici passi che devono diventarci familiari se inten-diamo risolvere modelli usando :

Eseguire in Windows 95 è moltosemplice. Quando abbiamo installato , il programma di installazioneha creato una voce in nel menù di dal nome

3

→MPL

Caricare il �le del modello nell�ambiente MPL.MPL

MPLMPL

MPL

Risolvere il modello. CPLEX300

MPLMPL MPL

MPL

MPLMPL

WindowsAvvio Programmi Mpl for Windows

Mplwin4.mpl

Model1.mpl

Tutorial

Open File Open

TutorialModel1.mpl

OpenTutorial

Model1.mpl Open

RunSolve

No SolversRun Setting

up Solvers forCPLEX

Solve CPLEX Run Model1

. Per eseguire , se non lo abbiamo ancora fatto, è sufficientecliccare sul menù e selezionare

Dopo che si è avviatoe ci si trova nell�ambiente di sviluppo di modelli, il prossimo passo

è quello di caricare il �le del modello nell�editor di modelli. L�applicazioneviene fornita con diversi modelli di esempio che sono collocati nella

cartella (directory) . I �les con i modelli di sono registraticome dei �le di testo standard e, tipicamente, hanno l�estensione � �.Il modello che useremo in questa sezione si chiama � � e si trova,insieme a tutti i modelli utilizzati in questo tutorial, in una cartella separatadal nome .

1. Scegliamo nel menù per aprire la �nestra di dialogo .

2. Doppio click sulla cartella dal nome per entrare nella cartelladove è conservato il �le del modello � �.

3. La �nestra di dialogo ora mostrerà una lista di �les di modelliche sono conservati nella cartella . Clicchiamo sul �le

dal nome � � per selezionarlo e premete il tasto peraprire il �le. Alternativamente, possiamo aprirlo semplicemente conun doppio click sul �le stesso nella lista.

Queste semplici operazioni ci permetteranno di aprire una nuova �nestra dieditor dei modelli che contiene la formulazione del modello.

In questo tutorial usiamo come ri-solutore (solver); ma, se siamo in possesso di altri risolutori supportati da

, possiamo usarli.Quando eseguiamo per la prima volta dopo averlo installato,

proverà automaticamente a localizzare tutti i risolutori che abbiamo a di-sposizione. Potremo controllare quali risolutori sono stati trovati daandando nel menù . Ogni risolutore trovato verrà indicizato nel menùpreceduto dalla parola .

Se non disponiamo di nessun risolutore verrà visualizzato nelmenù . In questo caso, possiamo consultare il Capitolo 2.4:

per trovare le informazioni su come aggiungere riso-lutori a . D� ora in poi assumeremo che sia stato installatocon successo, oppure che qualsiasi altro risolutore sia stato correttamenteinstallato.

Il prossimo passo sarà quello di risolvere il modello che è stato caricatonell�editor di modelli. Per risolvere il modello basta seguire i seguenti passi:

1. Scegliere nel menù per risolvere il modello .

4

Vedere la soluzione. MPL

Usare la �nestra dell�albero delle de�nizioni del modello (). MPL

MPLMPL

Status Window

Status Window

.solModel1.sol

View Status Window

View Window

ModelDe�nition Window

Model De�nitions Windows

Model De�ni-tions View



ModelDe�nitions View

2. Durante la risoluzione del modello, viene mostrata la �nestra di stato( ) che ci fornisce informazioni su come progredisce lasoluzione.

La fornisce informazioni come il numero di linee lette,il numero delle variabi e dei vincoli del modello, quanta memoria è statausata. Mentre l�ottimizatore risolve il modello, vengono inoltre mostrati ilnumero delle iterazioni e il valore corrente della funzione obbiettivo.

registra automaticamente la soluzione in un�le con lo stesso nome del �le del modello, ma con l�estensione � �. Usiamoi seguenti passi per visualizzare il �le di soluzione � � che è statogenerato per il modello che abbiamo già risolto.

1. Premiamo il tasto sul fondo della che è apparsasul video durante il processo di risoluzione. Questa operazione apriràuna che contiene il �le di soluzione.

2. Possiamo scorrere il �le della soluzione semplicemente utilizzando lebarre di scorrimento posizionate sulla destra. Notiamo che i detta-gli della soluzione includono il valore ottimale della soluzione per lafunzione obbiettivo, i valori delle variabili decisionali e dei vincoli.

3. Quando abbiamo �nito di vedere il �le di soluzione, possiamo chiuderela �nestra semplicemente premendo il tasto (X) che si trova nell�angoloin alto a destra della �nestra stessa.

ci permette inoltre di vedere tutti gli oggettide�niti nella formulazione del modello in una �nestra con una struttura adalbero chiamata . Ogni ramo corrisponde ad unasezione del modello.

Se la �nestra non è visibile, possiamo aprirla scegliendonel menù . Normalmente è una buona idea lavorare con

mantenendo la sempre aperta. provvede-rà automaticamente a mantenere aggiornato il contenuto di questa �nestratutte le volte che risolveremo i vostro modello.

La provvede ad un facile accesso a differentiparti del modello e ci permette di selezionare e vedere velocemente le partidella soluzione del modello che ci interessano. Per utilizzare l�albero bastaeseguire:

1. Accertiamoci che la �nestra con l�albero sia aperta scegliendodal menù .

5

�

�

�

2.2 Caratteristiche generali

2.1.2 Utilizzare il Sistema di Aiuto in MPL

MPL

Accesso agli argomenti di aiuto per MPL.MPL

MPL MPL

MPL

Lunghezza delle righe

MPL

VARIABLESProduce Inventory Sales

Produce ViewView Window

Produce

Help Topics

HelpTopics dialog box Contents Index

Find

Contents

Index

Find

Find Setup WizardFind

2. Sotto l�intestazione nella �nestra potremo osservare ilnome delle variabili in una lista: , e , che sono levariabili del modello. Davanti all�intestazione di ogni sezione, troviamoun quadratino che contiene o un segno più (+) o un segno meno (-).Questo quadratino ci permette di espandere o comprimere velocementeogni ramo dell�albero.

3. Ora selezioniamo la variabile e premiamo il tasto che sitrova sul fondo della �nestra. Verrà aperta una nuovacon il valore della soluzione per la sola variabile .

offre agli utenti un sistema di aiuto che contiene informazioni utilisu come usare questo software.

Per aprire la �nestra prin-cipale di aiuto per , andiamo nel menù e scegliamo . Civerrà mostrata una �nestra di aiuto, dove potremo selezionare l�argomentoche ci interessa.

La �nestra di dialogo degli argomenti di aiuto di () contiene tre bottoni; il bottone , il bottone

e il bottone ; fornendoci strade differenti per accedere agli aiuti.

Il bottone mostra tutti gli argomenti disponibili in una strut-tura ad albero.

Il bottone ci permette di accedere alla lista di tutte le parolechiave contenute nel �le di aiuto, oppure ci permette di eseguire dellericerche per speci�che parole chiave.

Il bottone ci permette di ricercare negli argomenti di aiuto parolespeci�che o frasi nel testo. Il database di ricerca viene costruito au-tomaticamente dal la prima volta che selezionate

.

Vengono qui spiegate alcune caratterisctiche generali del linguaggio .

Ogni riga non può superare i 255 caratteri. I rimanenti verranno ignoratida .

6

Commenti

MPL

Separatori

Range di un insieme

{Commento...

}

x[foods] ! dollars of food to be purchased daily

i = 1..5 ;j = 1..12 ;

nutrients = (Calorie,Protein,Calcium,Iron,Vitamin);

Required[nutrients] = ( 3 ! Calories70 ! Protein0.8 ! Calcium

12 ! Iron75 ) ; ! Vitamin

[indice = min .. max][indice > val]

["val"]

In ci sono due tipi di commenti: le parentesi grafe { ...} rac-chiudono commenti in blocco, cioè che possono estendersi anche su piùrighe

il punto esclamativo �!� delimita invece l�inizio di un commento chetermina a �ne riga

I diversi statement all�interno di una sezione (indici, vincoli, etc...) de-vono essere separati dal carattere �;�

Gli elementi di una lista di valori devono essere separati dalla virgola �,�o da un �a capo� (questo permette di introdurre dei commenti esplicativiaccanto ad ogni valore).

Si può esprimere un insieme di valori con l�uso di caratteri speciali:

oppure selezionare un singolo indice di valore speci�cato

7

Formule

MPL

Cost = SUM(foods: x);

2.3.1 TITLE

2.3.2 INDEX

2.3 Struttura di un programma MPL

sqr, sqrt,sin, cos, log, ext, power ...

Si possono scrivere espressioni che comprendono le normali operazioniaritmetiche +, -, *, / nonché diverse altre funzioni matematiche:

.Esiste inoltre la funzione sommatoria che richiede come primo parametro

il nome dell�indice su cui iterare e come secondo l�espressione da valutarecon l�indice speci�co:

La struttura di un �le è divisa in due parti fondamentali, ognunadelle quali è a sua volta suddivisa in diverse sezioni.

La prima parte è di de�nizione e comprende:

TITLE - Il nome del modelloINDEX - Gli indici del problemaDATA - I dati (scalari, vettori e matrici multidimensionali)DECISION - Le variabili del problemaMACRO - Macro riutilizzabili nelle varie espressioni

La seconda parte invece descrive il modello ed è formata dalle seguentisezioni:

MODEL - Descrizione del problemaMAX o MIN - Funzione obiettivoSUBJECT TO - VincoliBOUNDS - Estremi superiori ed inferiori delle variabiliFREE - Variabili libereINTEGER - Variabili intereBINARY - Variabili binarie (0/1)END - Fine del modello

Il titolo del modello non è obbligatiorio, ma è buona norma assegnareun titolo ad ogni problema e terminare la riga con il carattere �;�

Gli indici de�niscono il dominio del problema e la sua dimensione. De-vono essere dichiarati con il carattere �:=� e possono essere sia numerici chealfabetici. Per i primi è sufficiente speci�care i due valori estremi separatidal carattere �..�.

8

�

�

�

�

Stock[month-1]

Indici alias

MPL

Indici circolari

MPL

Sottoinsiemi di indici

month := 1..12;

nutrients := (Calorie,Protein,Calcium,Iron,Vitamin);

i := 1..4;j := i;

day := (mon, tue, wed, thu, fri, sat, sun) CIRCULAR;month := 1..12 CIRCULAR;

holiday[day] := (sat, sun);summer[month] := (7..9);

Gli indici alfabetici invece, vengono dichiarati come lista di nomi, se-parati dalla virgola e racchiusi tra parentesi tonde. Questo secondo tipo èpreferibile a primo in quanto rende molto più chiara la lettura di vincoli edaltre espressioni in cui essi vengono usati.

In è possibile assegnare un nuovo nome ad uno stesso indice senzadover ripeterne la de�nizione:

Per alcuni tipi di indice, in particolare quelli temporali, si ha la neces-sità di de�nire un offset sull�indice, ad esempio . Se l�indi-ce esce dal range assegnato ignora quel particolare valore. Si puòinvece forzarlo a ripartire dalla parte opposta del range rendendo la listacircolare. Basta aggiungere alla dichiarazione dell�indice la parola riservataCIRCULAR.

Se si vuole dichiarare un nuovo indice composto da un sottoinsieme divalori di un altro basta usare la seguente sintassi:

dove tra parentesi quadre viene speci�cato l�insieme di origine.

Si possono anche eseguire le normali operazioni sugli insiemi:

Differenza con il simbolo: -

Negazione con il simbolo: NOT

Unione con uno dei simboli: +, OR, UNION

Intersezione con uno dei simboli: AND, INTERSECTION

9

2.3.3 DATA

NumberOfYears

Indici da �le esterno

INDEXplants := (NewYork, Chicago, London, Paris);OpenPlants[plants] := (NewYork, London);EuropePlants[plants] := (London, Paris);

! DifferenzaClosedPlants[plants] := plants - OpenPlants;

! := (Chicago, Paris)! Negazione

USPlants[plants] := NOT EuropePlants;! := (NewYork, Chicago)

! UnioneOpenOrEurope[plants] := OpenPlants OR EuropePlants;

! := (NewYork, London, Paris)! Intersezione

OpenAndEurope[plants] := OpenPlants AND EuropePlants;! := (London)

product := INDEXFILE("product.dat", 1);

NumberOfMonths = 12;NumberOfYears = 4?;

La lista di valori di un indice può anche essere letta da un �le esterno incui i dati sono separati dalla virgola o da uno spazio. Se poi oltre all�indiceil �le contiene anche altri dati, si può speci�care quale colonna contiene ivalori dell�indice.

NB: Se i dati sono su un foglio elettronico o un database esterno si puòaccedere anche direttamente ai dati con opportuni comandi.

In questa sezione vengono speci�cati i valori dei dati da usare nel mo-dello. Anche in questo caso essi possono essere dichiarati direttamente oessere caricati da un �le esterno, da un foglio elettronico o da un database,con il comando DATAFILE. I dati possono essere scalari, vettori o matricimultidimensionali.

Nel caso scalare il valore assegnato risulta una costante per tutta larisoluzione del modello. Il carattere speciale �?� serve per chiedere confermaall�utente del valore prede�nito.

In questo caso all�utente viene chiesto di confermare o modi�care il valoreprede�nito dello scalare .

10

2.3.4 DECISION

Required[nutrients] = ( 3, 70, 0.8, 12, 5, 2.7, 18, 75 );A[foods,nutrients] = DATAFILE(nutri.dat)

! Nutritive values of foods per dollar expenditure.

A[i] := (2, -4+3, 2*SQR(3)+2, 1/(2+1), last(i))

A[i] := [2: 4.0, 5: 3.0, 6: -4.0] ;

ProdCost[plant, machine, product] := [p1, m11, A1, 73.30,p1, m11, A2, 52.90,p1, m12, A3, 65.40,p1, m13, A3, 47.60,

p2, m21, A1, 79.00,p2, m21, A3, 66.80,p2, m22, A2, 52.00,

p3, m31, A1, 75.80,p3, m31, A3, 50.90,p3, m32, A1, 79.90,p3, m32, A2, 52.10,

p4, m41, A1, 82.70,p4, m41, A2, 63.30,p4, m41, A3, 53.80];

Per i vettori e le matrici, gli indici sono racchiusi tra parentesi quadre,e separati dalla virgola, mentre i relativi valori, sono racchiusi da parentesitonde e separati da virgola o a capo.

Nel caso di una matrice, la lista corrisponde alla scansione per riga dellamatrice stessa. Lo stesso concetto si estende al caso di matrici multidimen-sionali.

I dati possono essere valori semplici o il risultato di espressioni matema-tiche.

Se si utilizzano vettori e matrici sparse, si possono inserire solo i valorinon nulli; basta sostituire alle normali parentesi tonde quelle quadrate e farprecedere ai singoli valori i relativi indici.

Nella sezione DECISION vengono dichiarate le variabili del problemache possono essere scalari, vettori o matrici. Il nome completo della sezione

11

2.3.5 MACROS

2.3.6 MODEL

MPL

Condizioni sulle variabili

MPL

MODEL

MPL

Production[product,month]

Production[product,month] WHERE (Demand[product,month] > 0);

TotalRevenue := SUM(product,month: price * Sales) ;

MAX 3x1 + 5x2 ;

MIN Cost = SUM(products,months : InventoryCost) ;

è DECISION VARIABLES, ma accetta indifferentemente uno delletre seguenti dichiarazioni:DECISION VARIABLESDECISIONVARIABLES

Nel caso di vettori o matrici, i relativi indici vanno racchiusi tra parentesiquadre e separati dalla virgola.

A volte è necessario limitare le variabili al veri�carsi di determinate con-dizioni. La clausola WHERE seguita dalla condizione, permette di selezio-nare solo alcune variabili.

Le macro sono una caratteristica importante di . Esse permettonodi de�nire delle espressioni a cui assegnare un nome speci�co da usare poinella de�nizione della funzione obiettivo e dei vincoli. In questo modo sisempli�ca il modello rendendolo allo stesso tempo più leggibile.

La macro si de�nisce con un nome seguito dal simbolo �:=� e dalla suaespressione. Non si possono dichiarare macro indicizzate, ma si possonousare vettori e formule nel calcolo della sua espressione.

La parola chiave indica l�inizio della descrizione del modellovero e proprio. La funzione obiettivo richiede come primo elemento il sen-so di ottimizzazione: MAXIMIZE o MINIMIZE, che può essere abbreviatoin MAX o MIN; segue il nome, il segno di uguaglianza �=� ed in�ne l�e-spressione da valutare. Se non viene indicato alcun nome assegna perde�nizione il nome �z� alla funzione obietttivo.

12

i

2.3.7 SUBJECT TO

MPL

MPL

Vincoli semplici

Vincoli vettoriali

MPL

3 (Sb1 + Co1 + So1) = 2 (Sb2 + Co2 + So2) ;Overtime : Over < 50\% * 170 Workforce ;Production : SUM(shifts: Prod[shifts]) < 3750 ;

Questa è la sezione che descrive i vincoli del problema. È buona abitudineassegnare un nome ad ogni vincolo, ed anteporlo alla sua de�nizione. Ilnome non può contenere spazi vuoti ed altri caratteri riservati e deve essereseguito dal simbolo �:�. Se non viene dichiarato alcun nome per il vincoloi-esimo assegna il generico nome �c �. Un�equazione è composta dadue membri separati da uno dei seguenti segni di comparazione:

minore o uguale < <=uguale =maggiore o uguale > >=

I simboli < e > vengono interpretati come minore o uguale e maggiore ouguale. Per comodità e facilità di lettura sia le variabili che le costantipossono essere scritte in entrambi i lati della relazione. Le variabili possonoanche essere ripetute nella stessa formula o nei due lati dello stesso vincolo.Ci pensa poi ad accorpare i coefficienti e spostare tutte le variabili asinistra e a sommare le costanti in un unico valore da porre sul lato destradella relazione.

Ogni vincolo può estendersi anche su più righe e deve essere terminatocon il simbolo �;� per separarlo dal successivo.

Ci sono due tipi di vincoli: semplici e vettoriali.

I vincoli semplici sono quelli de�niti senza indici; sono formati dalla com-binazione di variabili semplici, vettori costanti ed eventualmente sommatoriesu vettori di variabili purchè tutte le variabili del vettore siano utilizzate.

I vincoli vettoriali sono quelli indicizzati, cioè vincoli che vengono ripe-tuti cambiando il valore dell�indice ogni volta. Si dichiarano aggiungendoil nome dell�indice racchiuso tra parentesi quadre subito dopo il nome delvincolo e prima del simbolo �:�. Ovviamente l�indice del vincolo deve esserecompatibile con quello dei vettori di variabili usati nella de�nizione del vin-colo stesso. poi espande questo singolo vincolo in una serie di vincolisemplici basati sui relativi indici.

La de�nizione del vincolo avviene nello stesso modo dei vincoli semplici.Si costruiscono equazioni composte da variabili, vettori di variabili, somma-torie e costanti. Non occorre dichiarare l�indice dopo ogni variabile, purchèquesto sia compatibile con l�indice principale del vincolo.

13

2.3.8 BOUNDS

Limitare i vincoli vettoriali

limiteinferiore < variabile < limitesuperiore

InventoryBalance[product,period]:Inventory = Inventory[period-1] + Production - Sales ;

ProdCap[machine,time] :SUM(tire: ProdRates * Prod) < ProdHours ;

InventoryBalance[month=Jan..Nov] : ...InventoryBalance[month<=Jun] : ...InventoryBalance[month=Dec] : ...

InventoryBalance[product,month]WHERE (month > Jan)

x < 4*12 ;z_bounds : 2 < z < 8 ;CloseInv : Inventory[December] = 20000 ;

MaxInv[month<=Nov] : Inventory <= 90000 ;Inventory[month=Dec] = 90000 ;Sales <= Demand ;

Si può limitare il range di un indice per un vincolo vettoriale direttamentenella de�nizione stessa del vicnolo.

Oppure si può de�nire un vincolo al veri�carsi di determinate condizioni

In questa sezione vengono de�niti i limiti inferiori e superiori alle va-riabili. La maggior parte dei risolutori LP prevede la possibilità di de�nirebounds sulle variabili, migliorando l�efficienza della loro gestione internarispetto alla dichiarazione di vincoli espliciti.

La de�nizione dei bounds ri�ette esatamente quella dei vincoli. Il limitepuò andare sul lato sinistro o destro della relazione e si possono anche de�nirevincoli composti del tipo:

Come per i vincoli anche i bounds possono essere semplici o vettoriali(indicizzati su uno o più indici).

Il limite inferiore è per de�nizione 0.

14

MPL

2.3.9 FREE

2.3.10 INTEGER e BINARY

FREETemperature ;Inventory[month] ;

INTEGERProduction[month,product] ;

BINARYShopOpen ;

Questa e le due successive sezioni servono per de�nire il tipo di variabiliusate e possono essere poste in qualsiasi ordine purchè dopo la sezione didichiarazione dei vincoli (SUBJECT TO).

come la maggior parte dei risolutori LP, assume che le variabilidecisionali siano positive o nulle. Per permettere ad una variabile sempli-ce o ad un vettore di variabili di assumere anche valori negativi bisognadichiararli come liberi.

Allo stesso modo si possono forzare delle variabili ad assumere solamentevalori interi; basta anteporre la porola INTEGER alla lista di variabili e/ovettori di variabili.

Si possono anche forzare alcune variabili ad assumere solamente i valoriinteri 0 e 1.

In entrambi i casi questa forzatura ha effetto soltatno se il pacchettorisolutore supporta questa caratteristica, ossia risolve problemi MIP (MixedInteger Programming).

15

MPL MPL

Capitolo 3

Planning3.mpl

{ Planning3.mpl }

3.1 Formulazione del Modello

Un modello di bilanciamentodella produzione

In questo capitolo costruiremo un modello di produzione con tre prodottiche verranno chiamati A1, A2 e A3. Per questi prodotti creeremo un indicee, quindi, de�niremo un vettore di variabili che rappresenta la necessità diproduzione di ogni prodotto.

Data la de�nizione di questi nuovi termini, indici e vettori, ora dovremoapplicarla a un modello di prova. Il modello di bilanciamento della produ-zione è un problema di distribuzione della forza produttiva tra i prodotti,con lo scopo di determinare il livello di produzione di ogni singolo prodottoper soddisfare una data domanda.

Il prezzo di vendita di ogni prodotto è �ssato: $120.00 per A1, $100.00per A2 e $115.00 per A3. Per ogni prodotto, esiste anche un limite massimodi domanda: 4300 per A1, 4500 per A2 e 5400 per A3.

La quota di produzione di un prodotto è misurata in quanti pezzi vengonoprodotti ogni giorno. In questo problema abbiamo un totale di 22 giorni diproduzione disponibili in un mese. Nella tabella seguente sono indicati laquota e il costo di produzione di ogni prodotto.

Produzione A1 A2 A3Costo di Produzione $73.30 $52.90 $65.40Quota di Produzione 500 450 550

Il prossimo passo è quello di prendere il problema appena descritto eformularne un modello per . Qui di seguito riportiamo il codicedel modello (�le ).

16

MPL

Planning3.sol�

3.2 Vedere e Analizzare la Soluzione

Dopo aver risolto il modello, crea automaticamente un �le checontiene in un formato standard vari elementi della soluzione del modello.Questo �le include, tra le altre cose, il valore ottimo della funzione obbiet-tivo, le attività dei costi ridotti delle variabili, i valori di slack e i costinascosti (�shadow price�) per i vincoli. Il �le della soluzione viene creatocon lo stesso nome del �le del modello, ma con l�estensione �.sol�. Nel nostrocaso il �le si chiamerà � .

17

TITLEProducton_Planning3;

INDEXproduct := (A1, A2, A3);

DATAPrice[product] := (120.00, 100.00, 115.00);Demand[product] := (4300, 4500, 5400);ProdCost[product] := (73.30, 52.90, 65.40);ProdRate[product] := (500, 450, 550);ProdDaysAvail := 22;

VARIABLESProduce[product] -> Prod;

MACROSTotalRevenue := SUM(product: Price * Produce);TotalCost := SUM(product: ProdCost * Produce);

MODEL

MAX Profit = TotalRevenue - TotalCost;

SUBJECT TOProdCapacity -> PCap:

SUM(product: Produce / ProdRate) <= ProdDaysAvail;

BOUNDSProduce <= Demand;

END

View Window

Dopo aver risolto il modello possiamo visualizzare la soluzione in una�nestra cliccando il tasto View che si trova sul fondo della �nestra di stato.Questa operazione mostrerà in una �nestra (� �) i dati che quiriportiamo.

18

MPL Modeling System - Copyright (c) 1988-2000, Maximal Software, Inc.-------------------------------------------------------------------------------MODEL STATISTICS

Problem name: Producton_Planning3

Filename: Planning3.mplDate: July 8, 2000Time: 13:53Parsing time: 0.33 sec

Solver: CPLEX 300Objective value: 544566.636364Iterations: 3Solution time: 0.60 sec

Constraints: 1Variables: 3Nonzeros: 3Density: 100 %

SOLUTION RESULT

Optimal solution found

MAX Profit = 544566.6364

MACROS

Macro Name Values-----------------------------------------------

TotalRevenue 1298181.8182TotalCost 753615.1818

-----------------------------------------------

DECISION VARIABLES

VARIABLE Produce[product] :

product Activity Reduced Cost---------------------------------------------A1 4300.0000 4.3100A2 1611.8182 0.0000A3 5400.0000 11.0636

---------------------------------------------

CONSTRAINTS

PLAIN CONSTRAINTS

Constraint Name Slack Shadow Price------------------------------------------------------ProdCapacity 0.0000 21195.0000

------------------------------------------------------

END

La prima parte del �le della soluzione contiene diversi dati statisticidel modello come il nome del �le, la data e l�ora in cui il modello è statorisolto, quale risolutore è stato usato, il valore della funzione obbiettivoe la dimensione del modello. La parte successiva contiene i risultati dellasoluzione. In questa parte possiamo vedere se la soluzione trovata è ottimale,illimitata oppure impossibile. Inoltre viene mostrato il nome e il valoredella funzione obbiettivo. Nella sezione MACROS del �le della soluzionepossiamo avere la lista di tutte le macros del modello de�nite insieme al loro

19

ProdCapacity

valore. Per esempio, nel nostro modello Planning3 le entrate totali sono di1,298 milioni di dollari, mentre le spese sono circa 754.000 dollari. Questocorrisponde ad un pro�tto di circa $545.000, che è il valore della funzioneobbiettivo.

Nella sezione DECISION VARIABLES possiamo trovare la lista di tuttele variabili del modello: vettore di variabili e variabili semplici. Nel nostrocaso abbiamo un solo vettore di variabili produzione (Produce) de�nito sul�indice prodotti. Potremo osservare che per i prodotti A1 e A3 la soluzio-ne suggerisce di produrre rispettivamente 4300 e 5400 pezzi. Questi valoricorrispondono alla domanda per questi prodotti. D�altro canto per A2 vie-ne suggerito di produrre non più di 1611 pezzi, questo corrisponde ad unaproduzione inferiore alla domanda. Chiaramente non abbiamo la possibilitàdi produrre abbastanza da coprire la domanda di tutti i prodotti e il mo-dello scelto consiglia di scegliere la produzione di A1 e A3 �no a coprirne ladomanda, sacri�cando la produzione di A2.

Nella sezione CONSTRAINTS è contenuta la lista dei vincoli compresinel modello: vettori di vincoli e vincoli semplici. Nel nostro modello abbiamosolo un vincolo di tipo semplice chiamato . Siccome lo slack delvincolo vale zero risulta che la nostra produzione funziona a pieno regime. Icosti nascosti ci informano a quanto ammonterebbe il mancato guadagno seci trovassimo nella necessità di ridurre i limiti dei vincoli di una unità. Datoche la capacità di produzione è espressa in giorni di produzione, la riduzionedei giorni disponibili per la produzione diminuisce i pro�tti di $21.195 algiorno.

20

�

∑

MPL

=1

0

x

x

t x

Capitolo 4

ij

ij

i,j

ij ij

4.1 Un problema di assegnamento

Esempi di risoluzione diproblemi classici dellaProgrammazione Lineare

In questo capitolo vengono analizzati alcuni problemi classici di Pro-grammazione Lineare e ne viene fornita la descrizione del modello con illinguaggio .

Un�azienda deve eseguire N lavori diversi avendo a disposizione N per-sone. Ognuna impiega un determinato tempo a svolgere un certo incaricosecondo la tabella riportata sotto. Sapendo che la ditta paga i suoi di-pendenti ad un determinato prezzo orario, come devono essere assegnati gliincarichi alle diverse persone per minimizzare il costo complessivo?

Lavoro Bianchi Verdi Rossi Ferrarilavoro A 12 15 9 5lavoro B 13 16 11 6lavoro C 6 8 5 3lavoro D 5 7 4 3

Poichè il costo è direttamente proporzionale al tempo impiegato, è suffi-ciente minimizzare il tempo totale.

Introduciamo le variabili binarie con il seguente signi�cato:

se il lavoro i-esimo viene assegnato alla j-esima personaaltrimenti

La funzione da minimizzare sarà quindi:

21

∑

∑MPL

i

ij

j

ij

= 1 = 1

= 1 = 1

x j .. N

x i .. N

soggetta ai vincoli che ogni persona può svolgere esattamente un lavoro:

e che ogni lavoro può essere assegnato solamente ad una persona:

Vediamo ora come si traduce questo modello in .

Se si risolve questo modello si avra il seguente assegnamento ottimo:

lavoro A ==> Rossi

22

TITLEProblema_di_Assegnamento;

INDEXpersone = (Bianchi, Verdi, Rossi, Ferrari);incarichi = (lavoroA, lavoroB, lavoroC, lavoroD);

DATA! tempo impiegato dalla persona j a svolgere il lavoro itempi[persone, incarichi] = ( 12, 15, 9, 5,

13, 16, 11, 6,6, 8, 5, 3,5, 7, 4, 3 );

DECISIONx[incarichi, persone] ! persona che svolge l�incarico

MODELMIN tempoTotale = Sum(persone, incarichi: tempi * x);

SUBJECT TOvincolo_incarichi[persone] : Sum(incarichi: x) = 1;vincolo_persone[incarichi] : Sum(persone: x) = 1;

BINARYx[persone, incarichi];

END

∑

∑

� �

� = 1 6

ij

ij

i,j

ij ij

j

ij i

4.2 Un primo problema dei trasporti

xx i j

distanze x costo unitario

x disp i ..

lavoro B ==> Ferrarilavoro C ==> Bianchilavoro D ==> Verdi

di tempo totale minimo = 28.

Una ditta di trasporto deve trasferire container vuoti dai propri ma-gazzini ai principali porti nazionali. Le disponibilità di container vuoti aimagazzini e le richieste ai porti sono le seguenti:

Verona 10 Genova 20Perugia 12 Venezia 15Roma 20 Ancona 25Pescara 24 Napoli 33Taranto 18 Bari 21Lamezia 40

I costi di trasporto sono proporzionali al numero di container ed aichilometri percorsi dai camion, secondo la seguente tabella:

Genova Venezia Ancona Napoli BariVerona 290 115 355 715 810Perugia 380 340 165 380 610Roma 505 530 285 220 450

Pescara 655 450 155 240 315Taranto 1010 840 550 305 95Lamezia 1072 1097 747 372 333

Si vuole determinare la politica di trasporto di costo complessivo minimo.

Cominciamo col de�nire le variabili intere come segue:= numero di container trasferiti dal magazzino al porto

La funzione obiettivo da minimizzare è il costo complessivo di trasporto:

soggetta ai vincoli che ogni magazzino di partenza può spedire tanti contai-ner quant�è la sua disponibilità:

23

�∑

MPL

= 1 5i

ij jx rich j ..

Distan-ze.dat

e che ogni porto di distinazione deve soddisfare la propria richiesta:

Vediamo come tradurre questo modello in

Per come abbiamo de�niti gli INDEX, magazzini e porti, il �lecontiene la tabella dei chilometri percorsi esattamente così come è

riportata nella pagina precedente.

24

TITLEProblema_di_Trasporto;

INDEXmagazzini = ( Verona, Perugia, Roma, Pescara, Taranto, Lamezia );porti = ( Genova, Venezia, Ancona, Napoli, Bari );

DATAdisponibilita[magazzini] = ( 10, 12, 20, 24, 18, 40 );richiesta[porti] = ( 20, 15, 25, 33, 21 );

distanze[magazzini, porti] = DATAFILE ("Distanze.dat");

costo_unitario = 300; ! costo per chilometro

DECISION! numero di containter spediti dal magazzino i al porto jx[magazzini, porti]

MODEL! funzione obiettivoMIN costoTotale = Sum(magazzini, porti: distanze * x * costo_unitario);

SUBJECT TOvincolo_disponibilita[magazzini] : Sum(porti: x) <= disponibilita;vincolo_richiesta[porti] : Sum(magazzini: x) >= richiesta;

INTEGERx[magazzini, porti];

END

MPL

4.3 Un problema della dieta

{ Datafile per TRASPORTI.MPL }

Genova Venezia Ancona Napoli Bari \\

Verona 290 115 355 715 810 \\Perugia 380 340 165 380 610 \\Roma 505 530 285 220 450 \\Pescara 655 450 155 240 315 \\Taranto 1010 840 550 305 95 \\Lamezia 1072 1097 747 372 333 \\

Risolvendo questo modello con si avrà la seguente con�gurazionedi trasporto ottimo:

Genova Venezia Ancona Napoli BariVerona - 10 - - -Perugia 7 5 - - -Roma 13 - 1 6 -

Pescara - - 24 - -Taranto - - - - 18Lamezia - - - 27 3

di costo minimo = £ 9.045.900.

Una mensa deve piani�care gli acquisti di alimenti per la sua attività.Nella formulazione della dieta deve obbedire a requisiti nutrizionali minimi,nonché vincolare le porzioni massime di ogni elemento entro certi limiti.Conoscendo i costi unitari dei vari alimenti, trovare la dieta ottima cheminimizzi il costo complessivo rispettando i vincoli imposti.

Alimento Costo unitario Quantità massimaPane 2 4Latte 3 8Uova 4 3Carne 19 2Dolce 20 2

Requisiti nutrizionali minimi

Nutrimento requisitoCalorie 200 calProteine 50gCalcio 700 mg

25

∈

∑

∑

MPL

�

� ∀ ∈

� ∀ ∈

i

i

i i

i alimenti

ij j

i i

x

costo x

apporto richieste j nutrimenti

x maxPorz i alimenti

TITLEDieta_ottima

INDEXnutrimenti = (Calorie,Proteine,Calcio) : 10

alimenti = (Pane, Latte, Uova, Carne, Dolce) : 10

DATArichieste[nutrimenti] = ( 2000 ! Calorie []

50 ! Proteine [grammi]700) ; ! Calcio [milligrammi]

costo[alimenti] = ( 2 ! Pane3 ! Latte4 ! Uova

Dalle tabelle dietetiche si ricavano i seguenti contenuti di calorie, proteinee calcio per ogni singola porzione di ciascun alimento.

Calorie Proteine CalcioPane 110 4 2Latte 160 8 285Uova 180 13 54Carne 260 14 80Dolce 420 4 22

Le variabili di questo problema sono le quantità di ogni alimento dainserire nella dieta.La funzione obiettivo da minimizzare è il costo complessivo:

Un primo vincolo è quello dell�apporto nutrizionale:

Esiste poi un limite massimo alle quantità dei singoli alimenti.

Questo limite può essere imposto introducendo dei nuovi vincoli oppure, inmodo più efficiente, utilizzando degli upper bound.

Vediamo come convertire questo modello nel linguaggio .

26

Nutrimen.datSegue il �le .

27

19 ! Carne20 ) ; ! Dolce

maxPorz[alimenti] = ( 4 ! Pane Massimo numero di porzioni8 ! Latte tollerato giornalmente3 ! Uova2 ! Carne2 ) ; ! Dolce

apporto[alimenti,nutrimenti] = DATAFILE(nutrimen.dat)! Contenuti di nutrimenti nei diversi alimenti

DECISIONx[alimenti] -> "" ! porzioni di ogni alimento

MODEL

MIN Cost = SUM(alimenti: costo*x) ;

SUBJECT TO

NutrBal[nutrimenti] : SUM(alimenti: apporto*x) > richieste[nutrimenti];

BOUNDS

MaxPorzioni : x < maxPorz ;

END

{ Datafile per DIETA.MPL }

! Valori Nutritivi degli alimenti

Calorie Proteine Calcio! (cal) (grams) (migrams)

Pane 110 4 2Latte 160 8 285Uova 180 13 54Carne 260 14 80

MPL

Dolce 420 4 22

INTEGERx; ! variabili intere

4.4 Un problema di produzione più complesso

Risolvendo questo modello con si avrà la seguente dieta ottima:

Alimento quantitáPane 4Latte 8Uova 1.5556Carne 0Dolce 0

di costo minimo = 38.222. Come si può notare la soluzione ottima prevedeun valore non intero per l�alimento Uova. Se vogliamo forzare la soluzione adassumere solo valori interi basterà aggiungere il seguente vincolo di interezzaal modello subito dopo gli altri vincoli:

La nuova soluzione intera risulta essere ora:

Alimento quantitáPane 4Latte 8Uova 2Carne 0Dolce 0

di costo minimo = 40. Il fatto che la soluzione intera sia semplicementequella lineare con l�unica variabili non intera arrotondata per eccesso è pu-ramente casuale. Spesso la soluzione intera e la sua versione rilassata sonoassai diverse.

Un�azienda produce 5 diversi tipi di gomma (PVC1, PVC2, PVC3, Gom-ma1 e Gomma2) con i seguenti costi e ricavi unitari.

Prodotto Costo RicavoPVC1 30 130PVC2 45 200PVC3 20 120

Gomma1 10 115Gomma2 25 165

28

MPL

∑ ∑ ∑

∑

( ) ( ) 3600� � � � �

� ∀ ∈

i

i

i i i

j

j

i

ij i

i

ij i j

x

Ricavo Costo x Costo orario tempo x /

tempo x < Offerta j macchina

{ Produz.mpl }{ Mix ottimale della produzione }

TITLEOpt_Mix__Produzione;

INDEXprodotto := (PVC1, PVC2, PVC3, Gomma1, Gomma2);

Sapendo che i costi orari e la disponibilità di ogni macchina è:

Macchina Costo orario DisponibilitàmacPVC 90 60

macGomma 100 90Tagliom 50 130Pallets 40 70

Avvolgimento 30 40

e che i tempi di lavorazione in ore di ciascuna machina per ottenere un�unitàdi prodotto �nita sono i seguenti:

macchina / prodotto PVC1 PVC2 PVC3 GOMMA1 GOMMA2macPVC 2 1 1 0 0

macGomma 0 0 0 3 4Taglio 1 3 1 1 0.5Pallets 0.5 1 1 0 0Avvolgi 0 0 0 0.2 0.1

calcolare la quantità ottimale da produrre per ogni prodotto in modo damassimizzare i guadagni.

De�niamo per prima cosa le variabili del problema: siano le quantitàda produrre di ogni prodotto.La funzione obiettivo da massimizzare è il guadagno netto, dato dalla diffe-renza tra ricavi e costi unitari dei singoli prodotti e costi di produzione diogni macchina in base al loro utilizzo:

L�unico vincolo è che non si superi la disponibilità di utilizzo di ogni mac-china:

Vediamo come convertire questo modello nel linguaggio .

29

30

macchina := (macPVC, macGomma, Taglio, Pallets, Avvolgi);

DATACosto_mat[prodotto] = ( 30 ! PVC1 (in lire)

45 ! PVC220 ! PVC310 ! GOMMA125 ) ; ! GOMMA2

Ricavo[prodotto] = ( 130 ! PVC1 (in lire)200 ! PVC2120 ! PVC3115 ! GOMMA1165 ) ; ! GOMMA2

Offerta[macchina] = 3600 * ( 60 ! macPVC90 ! macGomma

130 ! Taglio70 ! Pallets40 ) ; ! Avvolgimento

Costo_orario[macchina] = 1000 * ( 90 ! macPVC100 ! macGomma50 ! Taglio40 ! Pallets30 ) ; ! Avvolgimento

tempo[macchina,prodotto] = DATAFILE(mixprod.dat)! tempi di ciascuna machina per ottenere un�unita� di prodotto

DECISIONx[prodotto] -> "" ! quantita� di prodotti che conviene produrre

MACRORicavi := SUM(prodotto: Ricavo * x - Costo_mat * x);

TotaleCosto := SUM(prodotto, macchina : Costo_orario * tempo * x / 3600 );

MODEL

Max Guadagno = Ricavi - TotaleCosto ;

SUBJECT TO

mixprod.datSegue il �le .

La soluzione ottima per la produzione risulta:

Prodotto quantitàPVC1 105.750PVC2 110.250PVC3 0

Gomma1 81.000Gomma2 0

per un guadagno complessivo di L. 15.388.750.

31

N[macchina] -> "" : SUM(prodotto: tempo * x) < Offerta[macchina];

END

{ Datafile per Produz.MPL }

! Tempi di lavorazione in ore di ciascuna machina per ottenere! una unità di prodotto finita

PVC1 PVC2 PVC3 GOMMA1 GOMMA2

macPVC 2 1 1 0 0macGomma 0 0 0 3 4Taglio 1 3 1 1 0.5Pallets 0.5 1 1 0 0Avvolgi 0 0 0 0.2 0.1

Capitolo 5

Un Modello diPiani�cazione dellaProduzione a Multi-Periodo

In questo capitolo creeremo una formulazione di un modello di piani�ca-zione della produzione a multi-periodo. Partiamo dal modello che abbiamocreato nel capitolo 3 facendo le opportune modi�che.

In questo nuovo problema abbiamo un periodo di quattro mesi da pia-ni�care, da Gennaio a Aprile. Per prima cosa dobbiamo creare un nuovoindice che contiene i quattro mesi in esame, quindi aggiornare il resto delmodello aggiungendo gli indici ai vettori già de�niti.

Come nel problema del capitolo 3, il prezzo di vendita per i prodotti èancora rispettivamente $120.00, $100.00 e $115.00. Ora, oltre ad avere unadomanda diversa per ogni prodotto, abbiamo una domanda differenziata perogni prodotto e ogni mese. Nella tabella seguente riportiamo i valori.

Domanda di Produzione Gen Feb Mar AprA1 4300 4200 6400 5300A2 4500 5400 6500 7200A3 5400 6700 7800 8200

Le quote di produzione e i costi di produzione resteranno gli stessi che sonostati forniti nella tabella del capitolo 3 a pag. 16. Inoltre i giorni di produ-zione disponibili in un mese varieranno ogni mese: 23 giorni a Gennaio, 20a Febbraio, 23 a Marzo e 22 a Aprile.

Inoltre dovremo introdurre un magazzino nel modello; questo comportal�introduzione di un costo di magazzino per ogni prodotto: A1-$3.50/mese,A2-$4.00/mese e A3-$3.00/mese. Ogni prodotto occupa lo stesso spazio, malo spazio totale disponibile nel magazzino è di 800 unità.

32


Il listato seguente è la formulazione del modello di Planning4. Come sipuò osservare il modello è un�estensione di quello presentato nel capitolo 3a pag. 16.

33

{ Planning4.mpl }

TITLEProduction_Planning4;

INDEXproduct := (A1, A2, A3);month := (Jan, Feb, Mar, Apr);

DATAPrice[product] := (120.00, 100.00, 115.00);Demand[product, month] := (4300, 4200, 6400, 5300,

4500, 5400, 6500, 7200,5400, 6700, 7800, 8200);

ProdCost[product] := (73.30, 52.90, 65.40);ProdRate[product] := (500, 450, 550);ProdDaysAvail[month] := (23, 20, 23, 22);InvtCost[product] := (3.50, 4.00, 3.00);InvtCapacity := 800;

VARIABLESProduce[product, month] -> Prod;Inventory[product, month] -> Invt;Sales[product, month] -> Sale;

MACROSTotalRevenue := SUM(product, month: Price * Sales);TotalProdCost := SUM(product, month: ProdCost * Produce);TotalInvtCost := SUM(product, month: InvtCost * Inventory);TotalCost := TotalProdCost + TotalInvtCost;

MODEL


SUBJECT TOProdCapacity[month] -> PCap:


MPL

MPL

5.2 Risolvere il Modello e Analizzare la Soluzione

Solve CPLEX Run

Optimal Solution Found

Planning4.sol

View

InvtBal[product, month] -> IBal:Produce + Inventory[month-1] = Sales + Inventory;

MaxInventory[month] -> MaxI:SUM(product: Inventory) <= InvtCapacity;

BOUNDSSales <= Demand;

END

MPL Modeling System - Copyright (c) 1988-2000, Maximal Software, Inc.-----------------------------------------------------------------------------

MODEL STATISTICS

Problem name: Production_Planning4

Filename: Planning4.mplDate: July 8, 2000Time: 20:13Parsing time: 0.22 sec

Solver: CPLEX 300Objective value: 2246007.27273Iterations: 0Solution time: 0.06 sec

Il prossimo passo è quello di risolvere il modello Planning4: basta sce-gliere la voce nel menù . Se i dati sono stati inseriticorrettamente, mosterà il messaggio che la soluzione ottimale è statatrovata ( ). Se si presenta un messaggio di errore inuna �nestra, indicazione di un errore di sintassi, ricontrolliamo la formula-zione del modello che abbiamo inserito confrontandola con quella fornita apag. 33.

Dopo aver risolto il modello, crea automaticamente un �le chia-mato nel formato standard contenente la soluzione. Possiamovisualizzare il �le della soluzione in una �nestra con la pressione del tasto

che si trova sul fondo della �nestra di stato. Riportiamo qui il listatocompleto del �le della soluzione:

34

35

Constraints: 20Variables: 36Nonzeros: 69Density: 10 %

SOLUTION RESULT

Optimal solution found

MAX Profit = 2246007.2727

MACROS

Macro Name Values-----------------------------------------------TotalRevenue 5386045.4545TotalProdCost 3139078.1818TotalInvtCost 960.0000TotalCost 3140038.1818

-----------------------------------------------

DECISION VARIABLES

VARIABLE Produce[product,month] :

product month Activity Reduced Cost----------------------------------------------------A1 Jan 4300.0000 0.0000A1 Feb 4200.0000 0.0000A1 Mar 4409.0909 0.0000A1 Apr 3545.4545 0.0000A2 Jan 1800.0000 0.0000

36

A2 Feb 0.0000 -3.6667A2 Mar 0.0000 -4.7889A2 Apr 0.0000 -0.7889A3 Jan 5720.0000 0.0000A3 Feb 6380.0000 0.0000A3 Mar 7800.0000 0.0000A3 Apr 8200.0000 0.0000

----------------------------------------------------

VARIABLE Inventory[product,month] :

product month Activity Reduced Cost----------------------------------------------------A1 Jan 0.0000 -0.2000A1 Feb 0.0000 -2.4900A1 Mar 0.0000 -3.5000A1 Apr 0.0000 -123.5000A2 Jan 0.0000 -4.0000A2 Feb 0.0000 -4.0000A2 Mar 0.0000 0.0000A2 Apr 0.0000 -108.0000A3 Jan 320.0000 0.0000A3 Feb 0.0000 -2.0818A3 Mar 0.0000 -3.0000A3 Apr 0.0000 -110.8545

----------------------------------------------------

VARIABLE Sales[product,month] :

product month Activity Reduced Cost----------------------------------------------------A1 Jan 4300.0000 4.3100A1 Feb 4200.0000 1.0100A1 Mar 4409.0909 0.0000A1 Apr 3545.4545 0.0000A2 Jan 1800.0000 0.0000A2 Feb 0.0000 0.0000A2 Mar 0.0000 0.0000A2 Apr 0.0000 -4.0000A3 Jan 5400.0000 11.0636

37

A3 Feb 6700.0000 8.0636A3 Mar 7800.0000 7.1455A3 Apr 8200.0000 7.1455

----------------------------------------------------

CONSTRAINTS

CONSTRAINT ProdCapacity[month] :

month Slack Shadow Price-------------------------------------------Jan 0.0000 21195.0000Feb 0.0000 22845.0000Mar 0.0000 23350.0000Apr 0.0000 23350.0000

-------------------------------------------

CONSTRAINT InvtBal[product,month] :

product month Slack Shadow Price----------------------------------------------------A1 Jan 0.0000 -115.6900A1 Feb 0.0000 -118.9900A1 Mar 0.0000 -120.0000A1 Apr 0.0000 -120.0000A2 Jan 0.0000 -100.0000A2 Feb 0.0000 -100.0000A2 Mar 0.0000 -100.0000A2 Apr 0.0000 -104.0000A3 Jan 0.0000 -103.9364A3 Feb 0.0000 -106.9364A3 Mar 0.0000 -107.8545A3 Apr 0.0000 -107.8545

----------------------------------------------------

Produce

CONSTRAINT MaxInventory[month] :

month Slack Shadow Price-------------------------------------------Jan 480.0000 0.0000Feb 800.0000 0.0000Mar 800.0000 0.0000Apr 800.0000 0.0000

-------------------------------------------

END

Il pro�tto ora risulta di 2,2 milioni di dollari che è considerevolmete piùalto di quello calcolato per il modello Planning3; questo è naturale dato cheora lavoriamo su un periodo di quattro mesi. Il pro�tto è il risultato di unintroito pari a 5,4 milioni di dollari e un importo dei costi pari a 3,1 milionidi dollari, la maggior parte dei quali è dato dal costo di produzione, dato chequello che viene conservato in magazzino è poco già a partire da Gennaio.

Se si osserva nella soluzione la variabile (produzione) notiamoche abbiamo prodotto A1 e A3 per l�intero periodo piani�cato, ma non èsempre stato possibile soddisfare la domanda. D�altro canto del prodottoA2 sono stati prodotte solo 1800 unità in Gennaio, questo signi�ca che nonabbiamo la capacità di produrre tutti e tre i prodotti.

In Gennaio il modello ha deciso di produrre, oltre alla domanda, 320unità di A3, con lo scopo di immagazinarli per soddisfare la domanda diFebbraio.

38

plants

Capitolo 6

Un Modello diPiani�cazione con piùImpianti di Produzione

In questo capitolo creeremo una nuovo modello per la piani�cazione dellaproduzione che include la presenza di più impianti oltre a considerare periodidifferenziati come nel capitolo 5. Quello che dobbiamo decidere è quantobisogna produrre di ogni prodotto per ogni mese, in ogni impianto, cercandodi ottimizare, per ogni mese e per ogni impianto, la vendita e il deposito nelmagazzino.

In questo nuovo problema avremo quattro differenti impianti p1, p2, p3e p4. Ognuno di questi impianti produce tutti e tre i prodotti. Creiamo unindice chiamato (impianti) che contiene i quattro differenti impiantie quindi aggiorniamo il modello con l�aggiunta dell�indice ai vettori che nenecessitano.

Come nelle sezioni precedenti, il prezzo di vendita per ogni prodotto èrispettivamente $120.00, $100.00 e $150.00. La domanda dei vari prodot-ti rimane la stessa del capitolo precedente; ci riferiamo alla tabella delladomanda del capitolo 5 a pag. 32.

Ora abbiamo più di un impianto di produzione e il costo di produzionedi ogni prodotto è diverso per ogni impianto. Riportiamo questi dati nellatabella seguente.

Costi di Produzione A1 A2 A3impianto 1 73.30 52.90 65.40impianto 2 79.00 52.00 66.80impianto 3 75.80 52.10 50.90impianto 4 82.70 63.30 53.80

Anche la quota di produzione di ogni prodotto è diversi�cata a secondadell�impianto come riportiamo nella seguente tabella.

39


Quota di Produzione A1 A2 A3impianto 1 500 450 450impianto 2 550 450 300impianto 3 450 350 300impianto 4 550 400 350

Il listato seguente è la formulazione del modello per Planning5.

40

{ Planning5.mpl }


INDEXproduct := (A1, A2, A3);month := (Jan, Feb, Mar, Apr);plant := (p1, p2, p3, p4);

DATAPrice[product] := (120.00, 100.00, 115.00);Demand[product, month] := DATAFILE("Demand.dat");ProdCost[plant, product] := DATAFILE("ProdCost.dat");ProdRate[plant, product] := DATAFILE("ProdRate.dat");ProdDaysAvail[month] := (23, 20, 23, 22);InvtCost[product] := (3.50, 4.00, 3.00);InvtCapacity := 800;

VARIABLESProduce[plant, product, month] -> Prod;Inventory[product, month] -> Invt;Sales[product, month] -> Sale;

MACROSTotalRevenue := SUM(product, month: Price * Sales);TotalProdCost := SUM(plant, product, month: ProdCost * Produce);TotalInvtCost := SUM(product, month: InvtCost * Inventory);TotalCost := TotalProdCost + TotalInvtCost;

MODEL


MPL

MPL


OptionsOptions

Options Solution FileOptions Dialog Box

Nonzero Values Only

OK

SolveCPLEX Run

SUBJECT TOProdCapacity[plant, month] -> PCap:


InvtBal[product, month] -> IBal:SUM(plant: Produce) + Inventory[month-1] = Sales + Inventory;

MaxInventory[month] -> MaxI:SUM(product: Inventory) <= InvtCapacity;


END

Dato che abbiamo aggiunto diversi indici al modello, il numero delle va-riabili è cresciuto in maniera considerevole. Tipicamente, quando si lavoracon grandi modelli, il creatore del modello preferisce includere solo le varia-bili diverse da zero. ha diverse opzioni che possono essere impostatetramite il menù ; mediante queste opzioni possiamo cambiare il com-portamento del programma. Una delle possibilità nel menù è quelladi aprire la �nestra di dialogo delle opzioni relative al �le della soluzione; inquesta �nestra di dialogo possiamo scegliere a vostro piacere cosa includere ecosa escludere nel �le della soluzione. Per cambiare i valori standard e quin-di includere solo i valori diversi da zero nel �le della soluzione, è sufficientefare i seguenti passi:

1. Nel menù scegliere per aprire la �nestra di dia-logo ( ).

2. Attivare l�opzione cliccando sul quadratino rela-tivo.

3. Chiudere la �nestra di dialogo premendo il tasto .

Dopo aver effettuato il cambiamento che permette di non scrivere i valo-ri nulli, il prossimo passo è quello di risolvere il modello scegliendo

nel menù . Se tutto ha funzionato a dovere mostrerà ilmessaggio �Optimal solution Found�. Se si presenta un messaggio di errorein una �nestra, indicazione di un errore di sintassi, ricontrolliamo la formu-lazione del modello che abbiamo inserito confrontandola con quella fornitaa pag. 40.

41

MPLMPL


Model De�nitions View

View

VARIABLE Produce[plant,product,month] :

plant product month Activity Reduced Cost-----------------------------------------------------------p1 A1 Jan 4300.0000 0.0000p1 A1 Feb 4200.0000 0.0000p1 A1 Mar 6400.0000 0.0000p1 A1 Apr 5300.0000 0.0000p2 A2 Jan 4500.0000 0.0000p2 A2 Feb 5400.0000 0.0000p2 A2 Mar 6500.0000 0.0000p2 A2 Apr 7200.0000 0.0000p3 A3 Jan 5400.0000 0.0000p3 A3 Feb 6000.0000 0.0000p3 A3 Mar 6900.0000 0.0000p3 A3 Apr 6600.0000 0.0000p4 A3 Feb 700.0000 0.0000p4 A3 Mar 900.0000 0.0000p4 A3 Apr 1600.0000 0.0000

-----------------------------------------------------------

Dato che il modello su cui stiamo lavorando sta diventando piuttostogrande ci occuperemo solo di guardare determinate parti della soluzioneinvece che la soluzione completa. A questo punto, useremo l�albero dellede�nizioni del modello per visualizzare solo le parti della soluzione alle qualisiamo interessati.

La �nestra delle de�nizioni del modello ( ) cipermette di vedere tutte le istanze de�nite nella formulazione del modello inuna struttura ad albero dove ad ogni ramo corrisponde una sezione del mo-dello. Nell�uso di è normalmente una buona idea lasciare la �nestracon l�albero delle de�nizioni sempre visibile. provvede all�aggiorna-mento automatico del contenuto della �nestra delle de�nizioni ogni voltache risolviamo un modello. Per visualizzare la �nestra delle de�nizioni delmodello scegliamo nel menù .

Nella �nestra con l�albero delle de�nizioni possiamo selezionare una qual-siasi delle istanze de�nite nel modello per osservarne i valori. Per esem-pio, per vedere il valore della variabile Produce basta un doppio click sullascritta Produce nell�albero, oppure, alternativamente, selezionando la scrit-ta e premendo il tasto . Questa operazione visualizzerà in una �nestracontenente solo i valori della variabile Produce.

Se osserviamo i valori dell�attività per la variabile Produce ci accorgere cheora siamo in grado di saturare completamente la domanda per ogni prodotto.Per esempio, l�impianto p1 è usato per produrre A1, l�impianto p2 è usatoper produrre A2, gli impianti p3 e p4 sono usati per produrre A3.

42

CONSTRAINT ProdCapacity[plant,month] :

plant month Slack Shadow Price--------------------------------------------------p1 Jan 14.4000 0.0000p1 Feb 11.6000 0.0000p1 Mar 10.2000 0.0000p1 Apr 11.4000 0.0000p2 Jan 13.0000 0.0000p2 Feb 8.0000 0.0000p2 Mar 8.5556 0.0000p2 Apr 6.0000 0.0000p3 Jan 5.0000 0.0000p4 Jan 23.0000 0.0000p4 Feb 18.0000 0.0000p4 Mar 20.4286 0.0000p4 Apr 17.4286 0.0000

--------------------------------------------------

Torniamo ora alla �nestra con l�albero delle de�nizioni per visualizzareuna �nestra contenente i vincoli ProdCapacity; avremo i seguenti valori perla soluzione:

Questi dati suggeriscono una grossa inefficienza di tutti gli impianti neivari mesi dovuto ai vincoli di capacità di produzione. Questo può essereinterpretato con il fatto che possiamo produrre molto di più di quello cheproduciamo, ma non è necessario dato che abbiamo già soddisfatto tuttala domanda. Dato che l�unità di misura della capacità di produzione è ingiorni di produzione, i valori di slack rappresentano quanti giorni al mese gliimpianti possono fermare la produzione.

43

Capitolo 7

Transhipment Models

Modelli di Trasporto

7.1 Usare la Condizione Where sui Vettori diVariabili

VARIABLESShip[fromplant,toplant]

WHERE(fromplant<>toplant);

(fromplant<>toplant)

Si tratta di modelli nei quali sono previsti dei viaggi tra varie località,spesso tali modelli sono detti di trasporto o di distribuzione. Tipicamente,in un modello del trasporto, si dispone di centri sorgente con determinatedisponibilità (risorse) e di destinazioni con determinate richieste, quindi siha la necessità di far viaggiare i prodotti dalle sorgenti alle destinazioni.In alcuni casi si trattano modelli del trasporto a più livelli. Per esempio, sideve trasportare dagli impianti ai depositi e, successivamente, dai depositi aicentri di vendita. Un�altro gruppo di modelli di distribuzione sono i modellidi distribuzione ( ). Questo tipo di modelli si adattano acasi nei quali si hanno diversi centri nei quali sussiste sia la produzione che lavendita. Quindi non ci sono degli speci�ci centri di risorse e di destinazione,si può trasportare i prodotti tra tutti i centri.

Diverse volte, lavorando con vettori multi-dimensionali, ci troveremo anon voler considerare tutti le variabili del vettore dato che alcuni casi posso-no non essere validi oppure non aver signi�cato. Per esempio, in un modellodi distribuzione non ha senso trasportare i prodotti da un determinato im-pianto all�impianto stesso. In questi casi possiamo usare la condizione wheresulle variabili per rimuovere gli elementi non necessari. Per esempio, nel mo-dello di distribuzione possiamo eliminare la possibilità di trasportare da unimpianto in se stesso mediante la seguente dichiarazione:

In questo caso, la condizione rimuove tutti gli ele-menti del vettore dove l�impianto sorgente è lo stesso dell�impianto di desti-

44

7.2 Vincoli di Bilanciamento degli Impianti

VARIABLESShip[fromplant,toplant]

WHERE(ShipCost[fromplant,toplant]>0);

PlantBal[plant,product,month]Produce+Inventory[month-1] +SUM(fromplant: Ship[fromplant,toplant:=plant])

=Sales + Inventory +SUM(fromplant: Ship[fromplant:=plant,toplant]);

toplant:=plant

fromplant:=plant

nazione. In alcuni casi le condizioni decisionali non sono basate sul valoredell�indice. Queste condizioni possono essere determinate dai vettori di datidel modello. Tipicamente, si ha un vettore assegnato che contiene i costidi trasporto tra gli impianti. Se il trasporto tra due impianti non è pos-sibile, si può assegnare a questo trasporto un valore speciale, come zero, eusarlo per identi�carlo. Quindi, possiamo usare i valori dei vettori di datinella de�nizione delle variabili per escludere i percorsi che non hanno senso.Riportiamo un esempio:

Quando lavoriamo con un modello di distribuzione abbiamo la necessitàdi garantire che la quantità di prodotti arrivati da altri impianti sommataalla produzione e a quanto è stato preso dal magazzino, deve essere ugualea quanto è stato trasportato fuori dall�impianto sommato a quello che èstato venduto e alla quantità immagazinata. In poche parole, quello cheentra nell�impianto deve essere uguale a quello che esce. Questo tipo divincolo è tipicamente chiamato vincolo di bilanciamento dell�impianto. Quiriportiamo un semplice esempio di vincolo di bilanciamento dell�impianto:

Si noti che questo vincolo è simile al vincolo di bilanciamento del magazzinoche è stato introdotto precedentemente. L�unica differenza è che ora bisognaconsiderare che trasportiamo in e da un impianto utilizzando un sommatoriasu ogni impianto per la variabile Ship.

L�assegnamento dell�indice nella prima sommatoria, cipermette di speci�care che l�impianto di arrivo (toplant) utilizzato deve es-sere l�impianto per il quale stiamo de�nendo il vincolo PlantBal. In questavincolo sono sommati tutti i beni trasportati all�impianto al quale il vin-colo stesso si riferisce da qualsiasi impianto. In maniera analoga l�assegna-mento nella seconda sommatoria speci�ca che l�impiantodi partenza (fromplant) deve essere l�impianto (plant) per il quale stiamode�nendo il vincolo.

45

7.3 Un Modello di trasporto tra impianti di pro-duzione

In questa sezione dovremo creare un nuovo modello dove ogni impiantoha una sua domanda interna di prodotti e, inoltre, dispone di un magaz-zino. Useremo il modello creato nella precedente sezione con le opportunemodi�che. Dato che ogni impianto può vendere i prodotti, ma adesso ladomanda è differenziata in ogni impianto, per ogni prodotto e per ognimese. Riportiamo qui di seguito la tabella con i dati della domanda:

Impianto Prodotto Gen Feb Mar AprA1 4300 4200 6400 5300

p1 A2 4500 5400 6500 7200A3 5400 6700 7800 8200A1 5100 6200 5400 7600

p2 A2 6300 7100 5200 6300A3 4800 6500 5000 7200A1 4100 6100 4700 5800

p3 A2 5300 5200 5700 4100A3 4200 4100 5200 6300A1 4300 4100 5300 4500

p4 A2 5300 6400 4200 6200A3 5600 5200 3800 4100

Questi dati sono in tre dimensioni: impianti, prodotti e mesi. Nei modellidi programmazione lineare è abbastanza tipico avere dati multidimensiona-li, a volte anche di dimensione maggiore di otto. Nella prossima sezioneaumenteremo ancora la dimensione dei dati includendo un�altra dimensio-ne; inseriremo la dimensione dei macchinari creando un vettore a quattrodimensioni.

La capacità del magazzino ora è diversi�cata tra i vari impianti. Abbia-mo quattro valori, uno per ogni impianto: 800, 400, 500 e 400. Inoltre, datoche abbiamo diversi impianti, ognuno con il suo magazzino, avremo dei costidiversi per ogni magazzino per ogni impianto e per ogni prodotto. I costidel magazzino sono riportati nella seguente tabella:

Costi del magazzino A1 A2 A3p1 $8.50 $7.00 $6.50p2 $9.80 $9.80 $9.80p3 $7.50 $7.50 $7.50p4 $9.30 $8.00 $6.50

In�ne, dato che permettiamo il trasporto tra gli impianti dei prodotti, abbia-mo dei costi legati a questo trasporto; la tabella seguente riporta il riassuntodei costi di trasporto:

46

7.4 Formulazione del modello

Costi di trasporto p1 p2 p3 p4p1 - $15.00 $21.00 $13.00p2 $16.00 - $12.00 $12.00p3 $14.00 $17.00 - $15.00p4 $21.00 $13.00 $10.00 -

Si noti come non sia associato nessun costo quando l�impianto di partenzaè uguale a quello di destinazione.

Quello che segue è il codice della formulazione del modello Planning6.Come vedremo è una estensione del modello Planning5.

47

{ Planning6.mpl }


INDEXproduct := (A1, A2, A3);month := (Jan, Feb, Mar, Apr);plant := (p1, p2, p3, p4);toplant := plant;fromplant := plant;

DATAPrice[product] := (120.00, 100.00, 115.00);Demand[plant,product,month] := DATAFILE("Demand6.dat");ProdCost[plant,product] := DATAFILE("ProdCost.dat");ProdRate[plant,product] := DATAFILE("ProdRate.dat");ProdDaysAvail[month] := (23, 20, 23, 22);InvtCost[plant,product] := DATAFILE("InvtCost.dat");InvtCapacity[plant] := (800, 400, 500, 400);ShipCost[fromplant,toplant] := DATAFILE("ShipCost.dat");

VARIABLESProduce[plant,product,month] -> Prod;Inventory[plant, product,month] -> Invt;Sales[plant, product, month] -> Sale;Ship[product, month, fromplant, toplant]

WHERE (fromplant <> toplant);

MPL


Sol-ve CPLEX Run

Model De�nition Windows

Model De�nitionsView

Produce

Il prossimo passo è quello di risolvere il modello Planning6 scegliendonel menù . Se tutto si è svolto correttamente mostrerà

il messaggi �Optimal Solution Found�. Se viene visualizzato un messaggiodi errore ricontrolliamo il codice inserito confrontandolo con quello riportatoin precedenza in questa sezione. Ora useremo la �nestra con la formulazionedel modello ( ) come nel capitolo 6 per vedere solole parti della soluzione che ci interessano. Per aprire la �nestra con le de-�nizioni del modello per il modello Planning6 scegliamonel menù .

Per vedere i valori della variabile Produce, eseguire un doppio click sullascritta nell�albero o, alternativamente, selezionatela e premiamo

48

MACROSTotalRevenue := SUM(plant, product, month: Price * Sales);TotalProdCost := SUM(plant, product, month: ProdCost * Produce);TotalInvtCost := SUM(plant, product, month: InvtCost * Inventory);TotalShipCost := SUM(product, month, fromplant, toplant: ShipCost * Ship);TotalCost := TotalProdCost + TotalInvtCost + TotalShipCost;

MODEL


SUBJECT TOProdCapacity[plant, month] -> PCap:


PlantBal[plant, product, month] -> PBal:Produce + Inventory[month-1]

+ SUM(fromplant: Ship[fromplant, toplant:=plant])=

Sales + Inventory+ SUM(toplant: Ship[fromplant:=plant, toplant]);

MaxInventory[plant, month] -> MaxI:SUM(product: Inventory) <= InvtCapacity;


END

Viewil tasto . Questo mostrerà una �nestra contenente solo i valori dellavariabile Produce.

Come possiamo vedere la produzione ora è distribuita tra i vari impianticon una gestione più efficiente dei costi. È chiaro che è meglio produrredeterminati prodotti in determinati impianti e mettere in conto le spese di

49

VARIABLE Produce[plant,product,month] :plant product month Activity Reduced Cost

-----------------------------------------------------------p1 A1 Jan 4300.0000 0.0000p1 A1 Feb 4200.0000 0.0000p1 A1 Mar 6400.0000 0.0000p1 A1 Apr 5300.0000 0.0000p1 A2 Jan 1080.0000 0.0000p1 A3 Jan 5400.0000 0.0000p1 A3 Feb 5220.0000 0.0000p1 A3 Mar 4590.0000 0.0000p1 A3 Apr 5130.0000 0.0000p2 A1 Jan 5100.0000 0.0000p2 A1 Feb 6200.0000 0.0000p2 A1 Mar 5400.0000 0.0000p2 A1 Apr 7600.0000 0.0000p2 A2 Jan 6177.2727 0.0000p2 A2 Feb 3927.2727 0.0000p2 A2 Mar 5931.8182 0.0000p2 A2 Apr 3681.8182 0.0000p3 A1 Jan 4100.0000 0.0000p3 A1 Feb 6100.0000 0.0000p3 A1 Mar 4700.0000 0.0000p3 A1 Apr 5800.0000 0.0000p3 A3 Jan 4166.6667 0.0000p3 A3 Feb 1933.3333 0.0000p3 A3 Mar 3766.6667 0.0000p3 A3 Apr 2733.3333 0.0000p4 A1 Jan 3850.0000 0.0000p4 A1 Feb 2828.5714 0.0000p4 A1 Mar 5300.0000 0.0000p4 A1 Apr 4500.0000 0.0000p4 A3 Jan 5600.0000 0.0000p4 A3 Feb 5200.0000 0.0000p4 A3 Mar 4677.2727 0.0000p4 A3 Apr 4836.3636 0.0000

-----------------------------------------------------------

VARIABLE Ship[product,month,fromplant,toplant] :

product month fromplant toplant Activity Reduced Cost------------------------------------------------------------------------A2 Mar p2 p4 331.8182 0.0000A3 Mar p4 p3 877.2727 0.0000A3 Apr p4 p3 736.3636 0.0000

------------------------------------------------------------------------

spedizione. Per esempio, A1 è prodotto negli impianti p1, p2 e p3, ma nonnell�impianto p4; A2 è prodotto in p1 e p2, A3 è prodotto in p1, p2 e p4.

Se ritorniamo nella �nestra con l�albero e apriamo una �nestra con lavariabile Ship avremo i seguenti valori per la soluzione:

Come possiamo vedere il modello propone di trasportare A2 dall�im-pianto p2 all�impianto p4. Analogamente A3 viene trasportato da p4 a p3.Chiaramente perché gli impianti p2 e p4 hanno una capacità extra e un bas-so costo di produzione e quindi possono essere usati per produrre quello dicui necessitano p4 e p3 rispettivamente.

50

Capitolo 8

Un Modello con PiùMacchinari

In questo capitolo dovremo aggiornare il precedente modello inserendodei macchinari distribuiti tra gli impianti. Basterà apportare le opportunemodi�che al modello creato nel capitolo 7 per aggiornarlo.

Dato che ora abbiamo dei macchinari differenti nei vari impianti, i costie le quote di produzione saranno ora diversi per ogni macchina. La seguen-te tabella riassume i dati di produzione dove ogni riga corrisponde a unamacchina che produce un prodotto in un dato impianto.

Impianto Macchinario Prodotto Costo di Produzione Quota di Produzionem11 A1 $73.30 500

p1 m11 A2 $52.90 450m12 A3 $65.40 550m13 A3 $47.60 350m21 A1 $79.00 550

p2 m21 A3 $66.80 450m22 A2 $52.00 300m31 A1 $75.80 450

p3 m31 A3 $50.90 300m32 A1 $79.90 400m32 A2 $52.10 350m41 A1 $82.70 550

p4 m41 A2 $63.30 400m41 A3 $53.80 350

Il processo di valutazione della produzione, quanto dobbiamo produrre diciascuno prodotto, necessita di tenere in considerazione la presenza di diver-se macchine. Perciò, dovremo aggiornare la variabile Produce includendol�indice delle macchine e, quindi, usare la condizione where per escludere gli

51


elementi non necessari; ad esempio: impianto p1, macchina m11 e prodottoA3.

Il listato che segue è il codice della formulazione di Planning7.

52

{ Planning7.mpl }


INDEXproduct := (A1, A2, A3);month := (Jan, Feb, Mar, Apr);plant := (p1, p2, p3, p4);toplant := plant;fromplant := plant;machine := (m11, m12, m13, m21, m22, m31, m32, m41);

DATAPrice[product] := (120.00, 100.00, 115.00);Demand[plant, product, month] := DATAFILE("Demand6.dat");ProdCost[plant, machine, product] := SPARSEFILE("Produce.dat", 4);ProdRate[plant, machine, product] := SPARSEFILE("Produce.dat", 5);ProdDaysAvail[month] := (23, 20, 23, 22);InvtCost[plant, product] := DATAFILE("InvtCost.dat");InvtCapacity[plant] := (800, 400, 500, 400);ShipCost[fromplant, toplant] := DATAFILE("ShipCost.dat");

VARIABLESProduce[plant, machine, product, month] -> Prod

WHERE (ProdCost > 0);Inventory[plant, product, month] -> Invt;Sales[plant, product, month] -> Sale;Ship[product, month, fromplant, toplant]

WHERE (fromplant <> toplant);

MACROSTotalRevenue := SUM(plant, product, month: Price * Sales);TotalProdCost := SUM(plant, machine, product, month: ProdCost * Produce);TotalInvtCost := SUM(plant, product, month: InvtCost * Inventory);TotalShipCost := SUM(product, month, fromplant, toplant: ShipCost * Ship);


Solve CPLEXRun

Model De�ni-tions Model

Model De�nitions ViewProduce

View

TotalCost := TotalProdCost + TotalInvtCost + TotalShipCost;

MODEL


SUBJECT TOProdCapacity[plant, machine, month] -> PCap:


PlantBal[plant, product, month] -> PBal:SUM(machine: Produce) + Inventory[month-1]

+ SUM(fromplant: Ship[fromplant, toplant:=plant])=

Sales + Inventory[month]+ SUM(toplant: Ship[fromplant:=plant, toplant]);

MaxInventory[plant, month] ->MaxI:SUM(product: Inventory) <= InvtCapacity;


END

VARIABLE Produce[plant,machine,product,month] :

Il prossimo passo è quello di risolvere il modello scegliendonel menù . Se tutto è stato fatto correttamente verrà visualizzato il mes-saggio �Optimal Solution Found�. Altrimenti, se viene visualizzato un mes-saggio di errore, controlliamo il codice che abbiamo scritto confrontandolocon quello riportato in precedenza in questa sezione.

Useremo ancora la �nestra delle de�nizioni del modello (), come nel capitolo 7, per osservare solo le parti della soluzione

alle quali siamo interessati. Per aprire la �nestra con le de�nizioni del mo-dello per il modello Planning7 scegliendo nel menù .Per vedere il valore della variabile fare un doppio click sulla scrit-ta Produce che si trova nell�albero delle de�nizioni oppure selezioniamo lascritta e premiamo . Questa operazioni visualizzeranno una �nestracon i valori della soluzione solo per la variabile Produce; riportiamo qui nelseguito questi valori.

53

54

plant machine product month Activity Reduced Cost--------------------------------------------------------------------p1 m11 A1 Jan 4300.0000 0.0000p1 m11 A1 Feb 4200.0000 0.0000p1 m11 A1 Mar 5487.5000 0.0000p1 m11 A1 Apr 5300.0000 0.0000p1 m11 A2 Jan 6480.0000 0.0000p1 m11 A2 Feb 5220.0000 0.0000p1 m11 A2 Mar 5411.2500 0.0000p1 m11 A2 Apr 5130.0000 0.0000p1 m12 A3 Feb 9049.3506 0.0000p1 m12 A3 Mar 916.1616 0.0000p1 m12 A3 Apr 10803.1169 0.0000p1 m13 A3 Jan 8050.0000 0.0000p1 m13 A3 Feb 7000.0000 0.0000p1 m13 A3 Mar 8050.0000 0.0000p1 m13 A3 Apr 7700.0000 0.0000p2 m21 A1 Jan 5100.0000 0.0000p2 m21 A1 Feb 6200.0000 0.0000p2 m21 A1 Mar 6538.8889 0.0000p2 m21 A1 Apr 7600.0000 0.0000p2 m21 A3 Jan 4422.6136 0.0000p2 m21 A3 Feb 3927.2727 0.0000p2 m21 A3 Mar 5000.0000 0.0000p2 m21 A3 Apr 3681.8182 0.0000p2 m22 A2 Jan 6900.0000 0.0000p2 m22 A2 Feb 6000.0000 0.0000p2 m22 A2 Mar 6900.0000 0.0000p2 m22 A2 Apr 6600.0000 0.0000p3 m31 A1 Jan 3300.0000 0.0000p3 m31 A1 Feb 5964.9351 0.0000p3 m31 A1 Mar 2550.0000 0.0000p3 m31 A1 Apr 4477.4026 0.0000p3 m31 A3 Jan 4700.0000 0.0000p3 m31 A3 Feb 2023.3766 0.0000p3 m31 A3 Mar 5200.0000 0.0000p3 m31 A3 Apr 3615.0649 0.0000p3 m32 A1 Jan 800.0000 0.0000p3 m32 A1 Feb 135.0649 0.0000p3 m32 A1 Mar 2150.0000 0.0000p3 m32 A1 Apr 1322.5974 0.0000p3 m32 A2 Jan 7350.0000 0.0000p3 m32 A2 Feb 6881.8182 0.0000p3 m32 A2 Mar 6168.7500 0.0000

Produce

Inventory

ProdCapacity

La variabile ora è de�nita su quattro indici: impianto, macchinario,prodotto e mese. Per ogni impianto il modello ha deciso quali macchinari so-no più efficienti per produrre un prodotto in un particolare impianto. Questatabella potrà essere usata come per programmare la produzione dell�interaazienda.

Un�altra variabile interessante in questo modello è (magazzi-no). Se ritorniamo nell�albero delle de�nizioni e apriamo una nuova �nestracon i valori della soluzione per la variabile Inventory visualizzeremo i seguentivalori:

Possiamo osservare che il modello ha deciso di produrre una eccedenzadei prodotti A2 e A3 in Gennaio per aumentare la disponibilità in Febbraio.

La maggior parte degli impianti ora funzionano a pieno regime. Riutiliz-zare la �nestra con l�albero delle de�nizioni apriamo una nuova �nestra conil vincolo per visualizzare i seguenti valori:

55

p3 m32 A2 Apr 6542.7273 0.0000p4 m41 A1 Jan 4300.0000 0.0000p4 m41 A1 Feb 4100.0000 0.0000p4 m41 A1 Mar 5073.6111 0.0000p4 m41 A1 Apr 4500.0000 0.0000p4 m41 A2 Jan 2270.0000 0.0000p4 m41 A2 Feb 5018.1818 0.0000p4 m41 A2 Mar 2500.0000 0.0000p4 m41 A2 Apr 5527.2727 0.0000p4 m41 A3 Jan 3327.3864 0.0000p4 m41 A3 Mar 2633.8384 0.0000

--------------------------------------------------------------------

VARIABLE Inventory[plant,product,month] :

plant product month Activity Reduced Cost-----------------------------------------------------------p1 A2 Jan 800.0000 0.0000p1 A2 Feb 620.0000 0.0000p2 A2 Jan 400.0000 0.0000p3 A3 Jan 500.0000 0.0000p4 A2 Jan 400.0000 0.0000

-----------------------------------------------------------

CONSTRAINT ProdCapacity[plant,machine,month] :

plant machine month Slack Shadow Price-----------------------------------------------------------p1 m12 Jan 23.0000 0.0000

p1 m12 Feb 3.5466 0.0000p1 m12 Mar 21.3343 0.0000p1 m12 Apr 2.3580 0.0000p2 m21 Jan 3.8992 0.0000

-----------------------------------------------------------

Come possiamo vedere l�impianti p1 e p2 hanno una capacità di produzionenon sfruttata per le machine m12 e m21 rispettivamente. Del resto tuttele altre macchine degli altri impianti lavorano a pieno regime per coprirecompletamente la domanda.

56

Appunti sul linguaggio di programmazione MPL · 1 2 3 123 Appunti sul linguaggio di programmazione...

Documents

Transcript of Appunti sul linguaggio di programmazione MPL · 1 2 3 123 Appunti sul linguaggio di programmazione...