Solutions Operations Research L. each vertex i ∈ V we associate a variable ti (the starting time of the activities represented by arcs in
δ (i). The mathematical programming formulation of the problem is:
Instructions for Handing In Homework
min t7 − t1 + 5000(t4 − t2)
Copyright By PowCoder代写 加微信 powcoder
Exercises Operations Research L. the following problems in GAMS and solve them. Please follow the instructions given
ti+dij ≤tj ∀(i,j)∈A,
in the problems and on canvas closely. Submit this assignment electronically to the drop box. You
should hand in a single zip file containing files with the following names: hw7-1.gms,hw7-2.gms, wDh,eFre→d Ci;sFth→e cBos.tEoafcthedayrco(fi,wjo)r.k costs 1000 euros; furthermore a special machinery must be rented
hw7-3.gms, hw7-1.lst, hw7-2.lst, hw7-3.lst
from the beginning of activity A to the end of activity B at a daily cost of 5000 euros. Formulate this as an LP problem and suggest an algorithm for solving it. [Fà Malucelli, Politecnico di Milano]
1àMàusMeumseugmuagrudasrds:Solution
A4mààuseumMduirescetourmusgt udeacirdde show many guards should be employed to control a new wing. Budget
The problem can be formalized by representing each museum room by a vertex v ∈ V of an undirected cuts have forced him to station guards at each door, guarding two rooms at once.
graph G = (V,E). There is an edge between two vertices if there is a door leading from one room to tAhemoutsheeurm; tdhirsewctaoyr, medugsetsdreecpidreshenowt tmheanpyosgsuibairlditsyshoof uthlderbeebeeminpgloayegdutaordcontraoldaoonre.wWweinwga. nBtutdogcehtocoustes
1.1 Problem
thaevesmfoarlclesdt hsiumbsteot sFta⊆tioEn ogfuaerddgsesatcoevaecrhindgoaolrl, vgeuratricdeisn,gi.tew. osurcohomthsaattforncaell. vFo∈rmVutlahteereaismwath∈eVmawtiictahl Formulate a mathematical program to minimize the number of guards. Solve the problem on the
{pvr,owgr}am∈ Fto. minimize the number of guards. Solve the problem on the map below using AMPL. map (or equivalent graph) below:
To each {i, j} ∈ E we associated a binary variable x 1.2 Problem ij
dAolosor rseoplvrestehnetepdrobbylemdgoen{it,hje}foalnlodw0inogthmerawpi.se. Also solve for the data given as
• Objective function
• Constraints. (Vertex cover): xij ≥ 1 ∀i ∈ V . YZ BF
ààà Formulation S R Q N L M H • Parameters. G = (V, A): graph description of the museum topology.
• Variables. x : 1 if edge {i,jT} ∈ E is to be included in F, 0 otherwise.
is assigned the value 1 if there is a guard on the
U min xij C E
jV: i,j E ààà2 AMPL model, data, run
[Pà Belotti, University]
For this second set of data only, report your solution as a two dimensional set stations that indicates
which doors the guards are placed at.
# museumàmod
p4arà8am n I=nàh,eirntietgaernàce
set V := àànà
set E within V,V à
A rich aristocrat passes away, leaving the following legacy:
var x E binaryà
2 DNA sequencing
One practical problem encountered during the DNA mapping process is that of compactly storing extremely long DNA sequences of the same length which do not differ greatly. We consider here a simplified version of the problem with sequences of 2 symbols only (0 and 1). The Hamming distance between two sequences a,b ∈ {0, 1}n is defined as ni=1 |ai − bi |, i.e. the number of bits which should be flipped to transform a into b. For example, on the following set of 6 sequences below, the distance matrix is as follows:
1. 011100011101 2. 101101011001 3. 110100111001 4. 101001111101 5. 100100111101 6. 010101011100
123456 1044543 2-04345 3–0525 4—036 5—-05 6—–0
As long as the Hamming distances are not too large, a compact storage scheme can be envisaged where we only store one complete sequence and all the differences which allow the reconstruction of the other sequences.
2.1 Problem
Show how this problem can be solved by finding a minimum weight spanning tree for a relevant graph. (A tree is a subgraph (of a given graph) with no cycles, spanning means it includes all the nodes of the original graph, minimum weight corresponds to the weights assigned to each edge). Solve the problem for the instance given above. Note that you might want to form a directed graph, and apply the Miller Tucker Zemlin approach to suppress cycles. Ensure your code prints out the tree found using the set tree defined below:
set tree(V,V);
option tree:0:0:2; display tree;
Problem 2 Page 2
3 Plane arrivals
10 planes are due to arrive at an airport with a single runway. Every plane has an earliest arrival time (time when the plane arrives above the zone if traveling at maximum speed) and a latest arrival time (influenced among other things by its fuel supplies). Within this time window the airlines choose a target time, communicated to the public as the flight arrival time. The early or late arrival of an aircraft with respect to its target time leads to disruption at the airport and causes costs to be incurred. To take into account these costs and to compare them more easily, a penalty per minute of
early arrival and a second penalty per minute time windows (in minutes from the start of the
of late arrival are associated with every plane. The day) and the penalties per plane are given below:
1 2 129 195 155 258 559 744
interval has to separate any two landings. An entry in line p of column q in the following table denotes the minimum time interval (in minutes) that has to lie between the landings of planes p and q, even if they are not consecutive.
3.1 Problem
2 3 4 5 6 7 8 9 10 3 15 15 15 15 15 15 15 16 0 15 15 15 15 15 15 15 15
15 0 8 8 8 8 8 8 8 15 8 0 8 8 8 8 8 8 15 8 8 0 8 8 8 8 8 15 8 8 8 0 8 8 8 8 15 8 8 8 8 0 8 8 8 15 8 8 8 8 8 0 8 8 15 8 8 8 8 8 8 0 8 15 8 8 8 8 8 8 8 0
Earliest arrival Earliness penalty Lateness penalty
6 7 120 124 135 138 576 577
8 9 10 126 135 160 140 150 180 573 591 657
plane is on the runway, a security
Due to turbulence and the duration of
30 30 the time during which a
Generate a model that determines a landing schedule that minimizes the total penalty subject to arrivals within the given time windows and the required intervals separating any two landings. If you use a big M formulation, ensure that you choose an appropriate value that is as tight as possible (including having a different one for each pair (p,q)). Display the values of M and the times of your landings of each plane using:
option M:2:1:1; option land:2:0:1;
display M, land.l;
Problem 3 Page 3
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com