September 2017
A company has to schedule a set of jobs $J=\{1,\ldots,n\}$ in the next $m$ days. The execution of each job requires a complete day, but more jobs can be carried out provided that there are enough resources. The resources have $q$ different types. Each job $j$, in order to be executed, needs $r_{ij}$ units of resource of type $i$, and in each day the availability of resource $i$ is $R_i$, $i=1,\ldots,q$. The company can quantify the profit of executing job $j$ in day $t$ as $g_{jt}$.
Formulate the problem of assigning jobs to days, so that the limit on the available resources is met and maximizing the overall profit with a linear model. Describe the variables and the meaning of the constraints.

 Variant: Let us suppose that the company obtains a fixed reward $F$ for each day that it can execute at least $k$ jobs. How does the model change?

February 2017
The soap opera ``A place in the fog" director has to plan the shooting of the next $D$ episodes. The shooting of an episode takes place in the morning and it is broadcasted in the evening of the planned day. In the soap opera there are $K$ interleaved plots. In each episode, whose fixed duration is $p$ minutes, more than one plot may be present. Each plot $k$ has an overall duration of $l_k (>p)$ minutes so it has to be split in more than one episode, and it involves a subset of the cast $A_k$. Each plot, if present in an episode, can have at most $M$ minutes and at least $m$ minutes. The director knows in which days each actor $i$ is present: let $b_{id}$ be a constant that equals 1 if actor $i$ is available in day $d$, and 0 otherwise.
In addition the director knows  the advertisement income $g_{kd}$ if plot $k$ is present in day $d$.

Formulate the problem of planning the shooting of the $D$ episodes so as to maximize the overall income satisfying the constraints on the duration and the availability of the actors.


February 2015
Consider a telecommunication network represented by a directed graph $G=(N,A)$. Root node $r$ has to broadcast a message to every other node in $N$. At any one unit interval of time $t$ a node can either receive or send a message to ONLY ONE of its neighboring nodes. Sending (or receiving) the message along an arc $(i,j) \in A$ takes 1 unit of time.  A node can send the message only after it has received it. Find the routing operations  during the time that minimize the time for broadcasting the message to all the nodes. Write a suitable linear optimization model. Explain the meaning of variables and constraints.

July 2015
Consider the problem of designing a telecommunication network. Given an undirected graph $G=(N,A)$, the arcs in $A$ represent the potential links of the network that can be selected in the design. In each internal node of the resulting network a signal regenerator device has to be installed. The resulting network has to be connected (and minimal) and the number of external nodes (leaves) has to be maximized, so as to minimize the cost of regenerators. Formulate the problem with a  linear optimization model, explaining the meaning of variables.

Variant: Suppose that the subnetwork involving the internal nodes must be resilient to one link failure. How does the formulation change?

October 2014
The administrators of the nicest city in the world want to install a sensor system on the city center streets in order to monitor the traffic flow in real time. The street network is represented by a directed graph  $G=(N,A)$, where the node set $N$ represents the intersections and the arc set the streets. Sensors can be located on the streets (i.e., on the arcs). The administrators know also the set of paths used by the citizens to move from a given origin to a given destination. Let $D=\{(s_d,t_d): d=1,\ldots r\}$ be the set of possible origin/destination pairs, and $P_d$ the set of all possible paths from $s_d$ to $t_d$, $d=1,\ldots,r$, the problem consists in determining the set of directed arcs where to place a sensor so that the flows on all possible paths $p \in P_d, d=1,\ldots,r $ are intercepted at least once. The objective is to minimize the number of sensors. Formulate the problem as a mathematical optimization problem.

Variant Suppose that the available budget allows the administrators to place at most $k$ sensors. Knowing an estimate of the traffic flow $f_p$ on each path $p\in P_d, d=1,\ldots,r$, the problem becomes the determination of the arcs where to place the sensors so that the maximum overall amount of flow is intercepted. How does the formulation modifies?

February 2014
A factory produces $n$ types of product and has $m$ different robots used in the processing. One unit of product $i$ requires $a_{ij}\geq 0$ units of time of robot $j$ ($i=1,\ldots,n, j=1,\ldots,m$). The maximum available time of robot $j$ is $b_j, j=1,\ldots,m$). The revenue for producing good of type $i$ is $r_i$ per unit ($i=1,\ldots,n$). In addition the factory incurs in costs for setting up robots: $c_{ij}$ for setting up robot $j$ for producing good $i$. The costs are fixed and are payed only if that particular type of good is produced.
Formulate the problem of planning the production maximizing the difference between gains and costs as an integer linear program.

Additional question
If good of type $k$ is produced the cost of setting up robots for goods $h$ and $h'$ are halved. How does the formulation change?

January 2013
The Ministry of Research of the optimism country has to select among $n$ research proposals which has to be financed.
Each research proposal $i$ has a  funding request of $R_i$. However, due to budget restrictions, each research proposal indicates also what is the minimum funding $r_i (<R_i)$ required to carry out the research and below which no results are provided. Let the total budget of the Ministry be $B$.
Formulate the problem of selecting among projects those to be financed and for each selected problem decide the amount of funding so that the minimum-maximum requirements are met and the Ministry budget is reached. The objective is to maximize the number of founded projects. Propose a linear model and explain the meaning of variables and constraints.

Variant: Let us assume that project are ranked by decreasing order of index. If project is  funded then the ratio between the actual funding and the maximum require one ($R_i$) must be greater or equal of the ratio of any other project $j >i$. How can you express this additional set of constraints.

June 2012

In order to reduce the expenses, the government of the optimism country has to cluster the current $n$ provinces into new bigger ones. Let $n$ be the current set of provinces. Each province $i\in N$ has $c_i$ towns, an area $s_i$ and a population $p_i$. The government decides that the new provinces must have at least $C$ towns, $S$ total area, and  population $P$. Obviously a current province must be assigned to exactly one new province. The objective of the government is to determine the clustering so that the number of new provinces is maximized. Formulate the problem in terms of Integer Linear Programming.

 Variant: After analyzing the results the government realizes that without further constraints the new provinces may be composed by old provinces that are far away. Knowing the set $A$ of adjacent provinces, add the constraint that imposes that any new province must be composed by old provinces that are all pairwise adjacent.

April 2012
The administration of a  county has to decide about the authorization for the installation of some biogas power plants. The set of received requests, each for a single plant is $R=\{1,\ldots,n\}$.
Each request $i$ is characterized by the annual production  $p_i$ and a site.The administration has to decide which requests to accept. Knowing the distance $d_{ij}$ between any two sites $i,j \in R$, the selection of the plants to be authorized must be such that the distance between any to active plants is at least $D$. The objective is to maximize the total annual production.

Variant: Let the number of plants to be activated be given and equal to $k$. The objective is to maximize the distance between the pair closest plants.

February 2010

A humanitarian association has to send some help in Haiti. The association collected n items to be sent and has to make a selection for the first shipment. Each item $i$ has a utility $g_i$, a weight $w_i$ (in kg) and a volume $v_i$ (in dm3). The container used for the shipment has a maximum capacity of $W$ kg and of $V$ dm3. Formulate the problem of selecting the subset of objects maximizing the total utility and not exceeding the two capacity limits.

Variant: Suppose that the constraint on the weight capacity is ``soft''. This means that we can exceed it of $W_1$ additional units, provided that the volume capacity constraint is fulfilled with respect to a tighter value $V_1 < V$. How can we modify the formulation to take into account this soft constraint?


November 2009 [H]

A factory produces three goods (1, 2, 3) over a time horizon of T days (1,..., T). For each unit of product i the profit is pi, i=1,..., 3. Two resources are used to produce the goods: workforce (w) and raw material (r) whose availability is Wt and Rt, respectively, for t=1,... , T. The workforce has a cost of cwt per unit and the raw material has a cost of crt per unit, depending on the day. In order to produce one unit of good i, Awi, and Ari units of resources are needed, i=1,...,3.

Unused workforce cannot be cumulated for the next day, while raw material can, with the limit of the inventory capacity B. This means that in planning the production we may think of buying more raw material than that required by the production of the day, storing it in the inventory. Let us assume that the inventory at the beginning is empty. The presence of the inventory allows us to exploit profitable costs, or tackle possible raw material shortages.

Plan the production so that the total profit (given by the difference of the gain due to the production and the costs due to the resources) is maximized.

Formulate the problem as a Linear Programming model (specify the meaning of variables, the objective function and the constraints).

Variant Suppose that when the production of a good (1, 2 or 3) is started, a fixed amount of raw material F has to be discarded to start up the machines, and this quantity does not depend on the actual production. How does the model has to be modified?


September 2009

Dr. Guildon, orthopaedic surgeon, has to schedule the operations of the day, that is he has to fix the order in which they have to be executed. The operations are I={1,…,n}. For the sake of simplicity, assume that operation 1 and operation n are conventional activities as the medical team briefing and debriefing and they have to be placed in first and last position, respectively. Dr. Guildon estimated, for each pair of operations (i,j), i,j in I, the switching time tij needed to dismiss patient i from the operating room and to prepare everything for patient j. This time varies from pair to pair and depends on the type of operations. The order of the operations has to be determined in such a way that the sum of the switching times is minimized.

Formulate the problem in terms of integer linear programming.


November 2008

In an Integer Linear Programming problem with logical variables x1, x2 and x3 formulate the implication (x1 & x2) -> x3 with a suitable inequality.


November 2008

A train with compulsory seats reservation travels on a line and stops in stations 1,2,...,n. The train has q coaches each having p seats. The reservation office receives b_{ij} seats requests for traveling from station i to station j (i<j) and has to distribute requests to coaches, assuming that the train capacity is enough, and that once assigned to a coach, passengers do not move. In order to maximize the travel comfort, in distributing requests to coaches the objective is to minimize the sum over all trip legs (i,i+1) of the number of passengers in the fullest coach. Formulate the problem as an Integer Linear Programming problem (specify variables, constraints and objective function).


July 2008

The parents of the happiest baby of the world have to visit n relatives to introduce the newborn. Let us assume that the n relatives reside in different sites, that the tour starts from relative 1 and must end at relative 1, and that n is even. The travel time between any two sites i and j is t(ij)=t(ji). Besides the travel time the parents have to consider the time spent in changing the diaper which varies from site to site depending on the available equipment. Let c(i) denote the changing time at site i, i=1,...,n. The constraint in changing the diaper is that it must be changed once every two consecutive visits.

Formulate the problem of finding the minimum time visit tour (travel time + changing time).


February 2008

Lowflax, the governor of an Italian region, has to dispose of the waste generated in a set of sites I. Each site i in I has a production of t(i) tons of undifferentiated waste. The possibilities are two: send the waste as it is in some existing dumps (D denotes the set of dumps), or install some classifying plants where the waste is divided according to the material, and then send the waste to the recycling center. Let us assume there is only one recycling center (denoted by r) able to receive all types of material (paper, glass, plastic, etc.). Let H denote the set of candidate sites that can host a classifying center. Each dump j in D has a capacity of d(i) tons. Each classifying center h in H has the capacity of treating q(h) tons of waste. A classifying center, for each ton of waste in input, produces 800 kg of classified material that can be sent to the recycling center and 200 kg of undifferentiated waste that has to be sent to the dumps. The service incurs in costs: transportation costs: c(ij), c(ih), c(hj), c(hr) per ton for each i in I, j in D, h in H, processing costs p(h) per ton for each h in H, installation cost f(h) for each h in H, dumping costs b(j) per ton for each j in D. Moreover the system benefits of a gain for selling the recycled materials: g per ton.
Formulate the problem of governor Lowflax of optimally disposing of all the waste.

November 2007

An important oil producer have to plan the production and selling strategy for the next n months. The maximum amount of oil that can be extracted in each month is Q barrels, the extraction cost is e(i) dollars per barrel extracted in month i=1,...,n. The producers' association sets the minimum l(i) and maximum u(i) number of barrels that can be extracted in each month, and the selling price per barrel is p(i) dollars. The producer can use a warehouse of capacity D barrels that is empty at the beginning of the period. The cost of storing in the warehouse an oil barrel for month i is c(i) dollars.
Model the problem of planning the oil extraction and selling for maximizing the producer's profit.

The oil field has a maximum extraction of M barrels. Besides, after that M/2 barrels are extracted, the extraction cost doubles. In one month it is not possible to estract both in the first part (the first M/2 barrels) and in the second part (the last M/2 barrels).


October 2007

In the optimism country every year the enological fair ``Vinoptimism'' is held where main wine producers meet main distributors (restaurants, wine shops, enophiles, etc.). The organizer of the fair wants to help the producers and the distributors to meet their respective requests. Each producer i=1,...,n gives to the organizer for each type of wine j=1,...,v the availability in number of cases d(ij) and the selling price per case p(ij). Each distributor h=1,...,m, for each type of wine j=1,...,v specifies the request in number of cases r(hj), the prices that he could accept to spend for a case (interval [l(hj, u(hj)]). Moreover the distributor specifies also for each type of wine j the minimum percentage a(hj) that his/her order has to satisfied in order to go back home happy (e.g. at least 35% of the bought wine has to be Bordeaux).
The objective of the organizer is to allocate the orders between producers and distributors so that overall money spent in purchase is maximized.

The transportation between each producer and distributor is made by means of trucks whose capacity is U cases. The cost of sending one truck between producer i and distributor h is D(ih), independently from the number of transported cases.
The objective is that of maximizing the overall money spent in purchase minus the transportation expenses.


September 2007

The best Italian teacher of the world has a new class N with n pupils. In order to improve friendly relations between pupils and get them acquainted with team work, the teacher starts a research work partitioning the class into teams. Some pupils met before arriving in the new class. Let A the set of pairs of pupils that are already friends (A={(i,j): i and j know each other}).
In making the partition the teacher wants that in each group there are no former friends. The objective is to minimize the number of groups. Formulate the problem with an Integer Linear Programming model.

The teacher wants also to balance the composition of the groups between males and females. Therefore the objective changes into the minimizing the maximum difference between males and females in each group. Extend the notation by considering the set of pupils N partitioned into two subsets M (males) and F (females). How does changes the formulation?


July 2007

The Mayor of the nicest city in the world wants to decrease the phenomenon of ``saturday night massacres'' on the roads. In order to avoid that young people of the city will go on saturday nights on the close Disco Coast, the Mayor decides to activate some ``street bar'' licenses in the city center. The municipal demographic office estimates the number of potential customers for each age (A: teen agers, B: twenty years old people, C: thirty and more years old people): U_A, U_B and U_C.
The set of candidate sites that can host a street bar is given by S={1,...,n} and for each site i in S, the maximum number of customers q_i that can be served is known.
The mayor has to activate the minimum number of licenses, distinguishing the type (A, B or C), in such a way that all potential customers of each type can be satisfied. Notice that a street bar can have only one type of license. Formunate the problem in terms of Integer Linear Programming.


Since the street bars are known to be noisy and to produce a lot of litter in the nearby streets, the Mayor wants to guarantee the downtown inhabitants.
In order to minimize population inconvenience, the objective of the Mayor is to activate the licenses so that the street bar are as far as possible each other. Let d_ij denote the distance between each pair of sites i,j in S. Formulate the problem where the objective function is the maximization of the shortest distance between the closest street bars.


March 2007*

A narco has to send a given quantity of cocaine (D kg) to the optimism land. To send the drug n containers are available, each with a capacity of U kg. The cost of sending a container (independently from the content) is g euro. In order to evade the police checkpoints the containers, besides the drug, must carry also other goods (coffee, pepper, smashed bananas, etc.). There are m types of accessory goods: for each good i, b_i kg are available, and the unitary cost is of c_i euro per kg. In order to successfully elude the police the percentage of accessory goods contained into each sent container must be at least 90%.
Formulate the problem of planning the shipment of the required drug quantity minimizing the shipment cost (cost of containers plus the cost of accessory goods).

Variant: How does the formulation changes if we impose the additional constraint that in each container theme must be at least two types of accessory goods?

This exercise was inspired by newspapers. It does not intend to be an encouragement to drug commerce nor an help to drug dealers.

February 2007

A high school manager must plan complementary courses for the next year. He can choose among a set of available courses C, for each of which an activation cost c(j) is given. Each student of the school i selects a subset of favorite courses f(i) and a subset of second choices s(i), such that f(i) intersection s(i) is empty. The school manager wants that for each student at least one course (favorite or second choice) is activated. Formulate the problem of planning the courses at a minimum cost.

Optional: Formulate the model if it is required that for at least 50% of the students there is at least one favorite course activated.

Settembre 2006

Un noto imprenditore marchigiano deve pianificare l'attivita' della propria fabbrica di scarpe Delli Calli. I modelli che possono essere messi in produzione sono M={1,...,n}. La catena di montaggio prevede il coinvolgimento degli operai O={1,...,m}. Per la produzione di un paio di scarpe del modello j, l'operaio i impiega p(ij) minuti. Considerato che per ogni operaio i in O e' noto il massimo tempo di lavoro q(i), che il guadagno per ogni paio di scarpe del modello j in M e' g(j) e che la massima produzione per ogni modello j in M e' R(j), formulare il problema di massimizzare il guadagno complessivo utilizzando la programmazione lineare.

Variante Ogni volta che viene avviata la produzione di un nuovo modello ogni operaio impiega t(ij) minuti per apprendere la proceduta. Come varia la formulazione?


Febbrazio 2006/2

Un pattinatore artistico deve decidere quali salti inserire nel suo programma libero per le Olimpiadi. Il programma è composto da due parti (A e B) e può contenere complessivamente al massimo 8 salti. I tipi di salto sono indicati con S={1,...,n}. Ogni tipo di salto può essere ripetuto. Ogni tipo di salto è caratterizzato da un coefficiente di difficoltà, di. Il coefficiente di difficoltà aumenta del 10% se viene eseguito nella parte B del programma. Il pattinatore conosce i suoi limiti e sa quali salti gli riescono con maggior difficoltà: ha assegnato a ciascun salto un coefficiente di rischio ri. Il pattinatore vuole massimizzare il coefficiente di difficoltà del suo programma mantenendo il rischio complessivo al di sotto di una soglia R. Formulare il problema utilizzando un modello di Programmazione Lineare Intera, indicando chiaramente il significato delle variabili e dei vincoli.


Febbraio 2006

The emergency calls manager has to allocate k ambulances on the Milan metropolitan area so that they can rapidly arrive where necessary. A set of points C={1,,n} representing potential emergency calls are given, as well as a set of candidate sites P={1,,m} where the ambulances can stay waiting for the calls. The times tij to move from a candidate site i in P to a potential call point j in C are known. Formulate the problem of determining in which candidate sites an ambulance has to be allocated. The objective is to minimize the maximum response time.

Variant. Modify the formulation so that each point is covered by at least two ambulances, the objective is to minimize the second best response time.



Marzo 2005

Sia data una rete di telecomunicazione descritta da un grafo orientato G=(N,A). Nell'insieme N sono dati un nodo origine s e un nodo t destinazione tra i quali si deve stabilire una comunicazione protetta. Il livello di protezione della comunicazione permette di far fronte ad un singolo guasto su un link, questo significa che è necessario individuare due cammini da s a t (un cammino nominale e uno di back-up) che non condividano archi in modo che di fronte al guasto di un arco del cammino nominale sia possibile utilizzare il cammino di back-up. A ciascun arco (i,j) di A sono associati due coefficienti di costo: c(1,ij) relativo al costo di trasmissione se l'arco appartiene al cammino nominale da s a t, c(2,ij) relativo al costo dovuto alla richiesta di disponibilità dell'arco (i,j) nel cammino di back-up.
Formulare il problema di determinare la linea di comunicazione protetta di costo complessivo minimo.

Come modificare il modello per tener conto anche di un possibile guasto su un nodo della rete?


Febbraio 2005 [INF]

Nel paese dell'ottimismo, il ministro delle nevicate deve far fronte a una improvvisa catastrofe meteorologica che ha completamente bloccato la rete stradale. La rete stradale è rappresentata da un grafo orientato $G=(N,A)$, e per ciascun arco $(i,j)\in A$ è noto il tempo di percorrenza da parte di uno spazzaneve. Per semplicità si assume che il tempo di percorrenza da parte dello spazzaneve sia uguale sia che la strada sia innevata o che sia gia' stata pulita. Lo spazzaneve deve far rientro alla base, situata in corrispondenza del nodo 0.
Formulare il problema di individuare l'itinerario dello spazzaneve che minimizza il tempo complessivo necessario a percorrere tutte le strade almeno una volta (equivalente a minimizzare il tempo impiegato a percorrere le strade piu' di una volta).

Variante. Come cambia la formulazione se il tempo di percorrenza di una strada sgombra è la metà rispetto al tempo di percorrenza della stessa strada innevata?

Compitino dicembre 2004 [INF]

Un trasportatore asiatico ha al suo servizio $n$ facchini dotati di risciò. Ogni facchino con il proprio mezzo è in grado di trasportare al massimo $P$ unità di peso e $V$ unità di volume. Il trasportatore riceve l'ordine di trasportare m sacchi. Ogni sacco $j$ ha un peso di $p_j$ e un volume di $v_j$ unità. Il problema consiste nell'assegnare il carico ai vari facchini in modo da minimizzare il numero di facchini. Formulare il problema illustrando il significato delle variabili decisionali.
Variante: Il sindacato dei facchini in risciò chiede al trasportatore di bilanciare il carico (in peso) tra i vari lavoratori. Questo significa che la differenza di peso tra il risciò più carico e quello più scarico deve essere minima. La versione "socialista" di questo vincolo implica che vengano considerati tutti gli $n$ facchini (compresi quelli che non trasportano nulla). La versione "liberista" limita il vincolo ai facchini a cui è effettivamente assegnato un carico. Formulare entrambe le varianti.


Compitino novembre 2004 [TLC]

Il gestore di un sistema di telecomunicazioni deve scegliere in un insieme di richieste R={1,...,n} quali inviare su un canale in fibra ottica con capacità complessiva B. Ogni richiesta i è caratterizzata da una occupazione di banda bi e un guadagno gi per il gestore, in caso la richiesta i venisse accettata. Formulare il problema di scegliere le richieste in modo da massimizzare il guadagno totale, rispettando i vincoli di capacità: si individuino le variabili decisionali, la funzione obiettivo e i vincoli.

Variante: Nella realtà pratica le richieste di comunicazione sono caratterizzate da una occupazione media di banda b'i(< bi) da garantire in ogni momento, se la richiesta viene accettata, e da un picco pi che viene raggiunto saltuariamente e non necessariamente in contemporanea con le altre richieste. In questo caso l'occupazione di capacità è misurata dalla somma delle bande medie più il massimo dei picchi delle richieste scelte. Formulare la variante del vincolo di capacità che tenga conto dei picchi utilizzando funzioni lineari (quindi non utilizzare la funzione max).


Esercizio Luglio 2004

Un rivenditore di computer vuole lanciare sul mercato 2 nuovi prodotti: A, B. Ha due canali per la vendita: il negozio o la vendita per corrispondenza. Deve pianificare gli acquisti, le vendite e l'immagazzinamento in due periodi. La seguente tabella riassume i prezzi di vendita e quelli di acquisto in euro:

 modello  primo periodo  secondo periodo
   negozio  corrispondenza  acquisto negozio corrispondenza acquisto
 A  529  499  300  499  459  250
 B  649  599  350  579  539  300

Il rivenditore dispone di un magazzino capace di ospitare 300 computer, inizialmente vuoto. Il costo di immagazzinamento è di 10 euro per pezzo. Il costo di trasporto al negozio e di esposizione è di 20 euro al pezzo (mentre nel caso di vendita per corrispondenza è a carico del cliente). La richiesta del mercato e la disponibilità presso il produttore sono riportate nella seguente tabella:

 modello   primo periodo   secondo periodo
 A  1000 900 500 700
 B  700 400 400 900

Formulare il problema di pianificare gli acquisti, le vendite e il magazzino in modo da massimizzare il guadagno (specificare variabili decisionali, vincoli e funzione obiettivo).


Esercizio 2003

Un trasportatore truffaldino viene incaricato di trasportare dei pacchi tra un ufficio di Milano e uno di Brescia. L'insieme dei pacchi è $P=\{1,\ldots,n\}$ e ciascun pacco i ha un dato peso $w_i$. Il camion utilizzabile per il trasporto ha una capacità massima $W$. L'intento del trasportatore è quallo di massimizzare il numero di viaggi per rallentare l'operazione. Nel caricare il camion deve premurare di salvare l'apparenza, pertanto il carico di ciascun viaggio deve essere tale che non sia possibile aggiungere nessun altro pacco a quelli già presenti, in particolare quindi non deve rimanere capacità sufficiente a caricare il più leggero (di peso $w_min$). Formulare il problema in termini di PLI.

Domanda opzionale: modificare la formulazione in modo che a ciascun carico non sia possibile aggiungere il pacco più leggero tra quelli rimasti da trasportare.


Esame luglio 2002 [L.I.T, L.I.E]

Un imprenditore deve preparare alcuni pacchi omaggio per premiare i propri aiutanti quando riescono a portare a termine i compiti a loro assegnati. Per confezionare i premi sono a disposizione $n$ oggetti diversi, l'oggetto $i$ ha valore $v_i (i=1,\ldots,n)$; un pacco omaggio per essere un regalo non offensivo deve avere un valore complessivo (ottenuto sommando il valore di tutti gli oggetti nel pacco) di almeno $V$. Il problema consiste nel determinare la ripartizione degli oggetti, in modo da massimizzare il numero di pacchi omaggio. Formulare il problema in termini di programmazione lineare intera.

Compitino giugno 2002 [L.I.T]

In vista dei festeggiamenti per la fine dei mondiali, il capo della polizia coreana deve organizzare un servizio di sicurezza per preservare l'incolumità dei tifosi locali, degli arbitri e dei dirigenti FIFA. La città deve quindi essere divisa in una zona sorvegliata (zona rossa) a cui hanno accesso solo i tifosi locali, i giocatori coreani e gli arbitri e in una zona di libera circolazione (zona verde) dove possono andare i turisti e i tifosi delle altre nazioni. È necessario predisporre dei posti di blocco per l'accesso alla zona rossa proveniendo dalla zona verde. Rappresentando la città come un grafo in cui i nodi corrispondono agli incroci e gli archi alle strade, vi sono alcuni nodi certamente off limits (nodi rossi) poiché direttamente interessati dalle delegazioni ufficiali (per esempio gli alberghi degli arbitri e i luoghi interessati dalle feste), e altri nodi certamente lasciati alla libera circolazione (nodi verdi). Inoltre vi sono altri nodi per i quali non è ancora stato stabilito un colore (nodi bianchi). Supponiamo che l'insieme dei nodi rossi definisca un sottografo connesso così come l'insieme dei nodi verdi. La zona rossa viene isolata dalla zona verde tramite posti di blocco sulle strade (archi). Si vuole determinare la colorazione dei nodi bianchi (in verde o in rosso) in modo da minimizzare il numero di posti di blocco.
Formire una formulazione di Programmazione Lineare Intera.
Domanda opzionale: Fornire un algoritmo efficiente per la soluzione del problema (utilizzare un grafo orientato e uno degli algoritmi noti).

traccia di soluzione

Compitino aprile 2001 [L. I. E.]

Un progetto è decomponibile nelle seguenti 7 attività la cui durata in giorni è indicata tra parentesi: A (4), B (3), C (5), D (2), E (10), F (10), G (1). Nello svolgere le attività devono venire rispettate le seguenti precedenze: A->G,D; E,G->F; D,F->C; F->B. Ogni giorno di lavoro comporta un costo di 1000 euro, inoltre dall'inizio dell'attività A alla fine dell'attività B deve venire affittata una apparecchiatura il cui costo è di 5000 euro al giorno. Formulare il problema in termini di programmazione lineare (individuare variabili decisionali, vincoli e funzione obiettivo).
Domanda opzionale: descrivere brevemente un algoritmo per risolvere il problema.

Compitino gennaio 2001 [D.I.L, D.I.I.]

Il panificio industriale "Michet" deve pianificare l'attività della propria linea di produzione per il prossimo mese. Viene prodotto un unico tipo di pane. La domanda del mercato è di $d_t$ quintali per ogni giorno $t=1,\ldots,30$. Per soddisfare la domanda si può ricorrere alla produzione o al magazzino (inizialmente vuoto). Se la linea produttiva viene attivata, la produzione giornaliera deve essere compresa tra un minimo di q quintali e un massimo di $Q$ quintali. Il costo di produzione è di $c_t$ euro per quintale $(t=1,\ldots, 30)$. Il costo di immagazzinamento è di $g$ euro per quintale (indipendentemente dal giorno). Vi è inoltre un costo fisso $S$ dovuto alla attivazione della linea produttiva da pagare ogni giorno in cui viene avviata la produzione. Formulare il problema in termini di programmazione lineare intera.
Domanda aggiuntiva: Supponiamo che il ciclo di produzione sia continuo (senza interruzione nell'arco delle 24 ore). Mantenendo il costo $S$ da pagare ogni attivazione della linea, come varia la formulazione?

Esame del 22/2/2000 [D.I.L, D.I.I.]

Due amici Massimo e Silvio vogliono organizzare le vacanze in comune. Ognuno dei due propone un insieme di possibili attività da svolgere assieme, rispettivamente AM e AS, e sia A=AM U AS. Alcune attività proposte sono incompatibili tra loro cioè non possono venire svolte entrambe durante il periodo di vacanza (per esempio prendere parte a una regata di altura non è compatibile con la partecipazione a un ritiro di una squadra di calcio, mentre entrambe le attvità sono compatibili con una sfida a braccio di ferro). Sia I l'insieme delle coppie di attività incompatibili (I sottoinsieme del prodotto cartesiano AXA, I={(i,j): i, j A incompatibili}). Il problema consiste nello scegliere il sottoinsieme di attività S compatibili tra loro di cardinalità massima. Inoltre i due amici per evitare litigi, nello scegliere le attività vogliono che |S intersezione AM| = |S intersezione AS|.
a) Si formuli il problema in termini di programmazione lineare intera.
b) Si suggerisca un algoritmo euristico per risolverlo.

Compitino gennaio 2000 [D.I.L]

Una azienda logistica raccoglie merci da n clienti sparsi sul territorio. Il cliente i movimenta merce per un volume globale annuo pari a vi, i=1,...,n. Le merci devono venire raccolte dalle filiali della azienda sparse sul territorio e convogliate verso le destinazioni finali. Le filiali non sono ancora installate, ma sono a disposizione solo p siti che possono ospitarle. Il problema che si pone è quello di determinare quante filiali aprire e in che siti. Per ogni sito j il costo di attivazione della filiale è di gj, j=1,...,p. È noto anche il costo per la raccolta della merce da ogni cliente i verso la filiale j: il costo per ogni unità di volume raccolto è dato da cij, i=1,n, j=1,...,p.
Formulare in termini di programmazione lineare intera il problema della determinazione delle filiali da aprire e della assegnazione dei clienti alle filiali che minimizzi il costo di attivazione delle filiali e di movimentazione della merce.

Esame giugno 1999 [D.I.L]

Siano dati un insieme di persone $E$ e un insieme di associazioni culturali $F$ (una associazione culturale è di fatto definita da sottoinsieme di $E$). Ogni associazione richiede un finanziamento per il proprio funzionamento alla locale cassa di risparmio: $f(a)$ è il finanziamento richiesto dalla associazione $a$ appartenente a $F$. La cassa di risparmio ha la possibilità di soddisfare completamente la richiesta di finanziamento oppure di rifiutarla. Per ragioni di equità, il presidente della cassa di risparmio desidera che ogni persona veda finanziata almeno una associazione alla quale appartiene. Ovviamente tra tutte le soluzioni di questo tipo si vuole trovare quella che minimizza l'impegno finanziario della cassa di risparmio. Formulare il problem in termini di Programmazione Lineare Intera. Supponendo di considerare il criterio di minimizzare il massimo contributo che riceve ogni singola persona, come si modifica la formulazione del problema?

Esame febbraio 1999 [D.I.L]

Un Internet provider ha a disposizione G Mbyte di memoria nel suo computer in cui memorizzare le pagine più frequentemente consultate dai propri clienti, scaricandole durante i periodi di minor utilizzo della rete, per poter avere tempi di risposta migliore durante i picchi di utenza. L'insieme delle pagine più frequentemente consultate è P={1,...,n}; ogni pagina i in P ha una dimensione di Mbyte e una frequenza di fi contatti giornalieri. Le pagine non presenti in memoria locale vengono scaricate dalla rete alla velocità di V Mbyte al secondo. Formulare il problema di stabilire quali pagine caricare in memoria locale per minimizzare i tempi di risposta usando la programmazione lineare intera.

Esame gennaio 1999 [D.I.L]

Una fabbrica di giocattoli ha una unica linea di produzione con capacità produttiva di q giocattoli per unità di tempo; l'orizzonte temporale [0,T] è diviso in m intervalli unitari t1, t2,...,tm. Per ogni intervallo temporale tj, j = 1,..., m, si conosce il numero bj di giocattoli che devono essere inviati ai negozi. La fabbrica è dotata di un magazzino che può contenere al più u giocattoli; inizialmente nel magazzino vi sono p(0) giocattoli. La direzione della fabbrica valuta in c lire il costo di immobilizzo di capitale per tenere in magazzino un giocattolo per ciascuna unità di tempo. Formulare in termini di PLI il problema di pianificare la produzione, cioè stabilire per ogni intervallo di tempo quanti giocattoli produrre, in modo tale che i costi di magazzino siano minimi.

Compitino gennaio 1999 [D.I.L]

Il Ministro per l'ambiente dispone la depurazione delle acque del Lario rimuovendo almeno 80 tonnellate di inquinante 1 e almeno 50 tonnellate di inquinante 2. Vengono individuati 4 siti (A, B, C, D) idonei alla costruzione delle centrali di depurazione. I costi di installazione, di trattamento per tonnellata di acqua, e la capacità di estrazione degli inquinanti per tonnellata di acqua sono riassunti nella seguente tabella:
sito     costo costruz. costo dep. (per ton.) inquinante 1 (%rimossa) inquinante 2 (% rimossa)
1          100.000            20                                    0.4%                            0.35%
2           70.000             30                                    0.25%                          0.25%
3           80.000             30                                    0.30%                          0.20%
4           40.000             35                                    0.15%                          0.22%

Il Ministro impone anche alcuni vincoli paesaggistici: se viene costruita la centrale nel sito 1 non può venire costruita la centrale nel sito 2.
Formulare il problema di costruire le centrali di depurazione minimizzando la somma dei costi di installazione e di gestione.