« Previous « Start » Next »
30 Public Services
30.1 Water conveyance
% function Result = waterconveyanceEx(PriLev)
%
% Creates a TOMLAB MILP problem for water conveyance
%
% WATER CONVEYANCE / WATER SUPPLY MANAGEMENT
%
% The graph in the figure below shows a water transport network. The
% nodes, numbered from 1 to 10, represent the cities, the reservoirs,
% and the pumping stations connected by a network of pipes. The three
% cities Gotham City, Metropolis, and Spider Ville are supplied from
% two reservoirs. The availabilities of water from these reservoirs
% in thousands of m3/h are 35 for reservoir 1 and 25 for reservoir 2.
% The capacity of each pipe connection is indicated in thousands of
% m3/h in the graph.
%
% A study is undertaken to find out whether the existing network will
% be able to satisfy the demands of the cities in ten years time,
% that is 18, 15, and 20 thousand m3/h. Determine the maximum flow in
% the current network. Will it be sufficient in ten years from now?
%
% Water transport network
%
%
% 35 20 15 7 18
% Reservoir-1 ----> 3 -------> 4 -------> 8-Gotham city
% ^
% | \15 | \ ---+
% | \ |10 ----\ /
% 12| \ | X
% \ \ | 10 / \10
% \ V V --------------/ ---+
% 25 \ / 15 V 15
% Reservoir-2 --+-> 5 -------------------> 9-Metropolis
% | 6 \ 15 ^
% \ \ ----------- -------+
% \ \ \ / 10
% \ \12 X
% 22 \ \ / \
% V V / -----+
% 22 10 V 20
% 6 -------> 7 -------> 10-Spider Ville
%
%
% VARIABLES
%
% arcs_out/in For an arc i arcs_out(i) is its target node
% and arcs_in(i) its starting node
% capacity Capacity of an arc
% source Artificial node acting as a source
% sink Artificial node acting as a sink
%
% RESULTS
%
% For an interpretation of the results, run:
% Result = waterconveyanceEx(2);
%
% REFERENCES
%
% Applications of optimization... Gueret, Prins, Seveaux
% http://web.univ-ubs.fr/lester/~sevaux/pl/index.php
%
% INPUT PARAMETERS
% PriLev Print Level
%
% OUTPUT PARAMETERS
% Result Result structure
% Marcus Edvall, Tomlab Optimization Inc, E-mail: tomlab@tomopt.com
% Copyright (c) 2005-2005 by Tomlab Optimization Inc., $Release: 5.0.0$
% Written Dec 5, 2005. Last modified Dec 5, 2005.
function Result = waterconveyanceEx(PriLev)
if nargin < 1
PriLev = 1;
end
arcs_in = [ 1 1 1 2 2 3 3 4 4 5 5 5 6 7 7 8 9 10 11 11]';
arcs_out = [ 3 5 6 5 6 4 5 8 9 8 9 10 7 9 10 12 12 12 1 2]';
capacity = [20 15 12 6 22 15 10 7 10 10 15 15 22 10 10 18 15 20 35 25]';
source = 11;
sink = 12;
Prob = waterconveyance(arcs_in, arcs_out, capacity, source, sink);
Result = tomRun('cplex', Prob, PriLev);
if PriLev > 1,
x = Result.x_k;
names = ['Reservoir 1 '; ...
'Reservoir 2 '; ...
'Node 3 '; ...
'Node 4 '; ...
'Node 5 '; ...
'Node 6 '; ...
'Node 7 '; ...
'Gotham City '; ...
'Metropolis '; ...
'Spider Ville'; ...
'Production '; ... % this is the source node
'Consumption ']; % this is the sink node
disp('Maximum flow of the network is as follows:')
for i = 1:length(arcs_in),
if x(i) ~= 0,
disp([names(arcs_in(i),:) ' -> ' names(arcs_out(i),:) ': ' num2str(x(i)) ])
end
end
end
% MODIFICATION LOG
%
% 051205 med Created.
% 060117 per Added documentation.
% 060125 per Moved disp to end
30.2 CCTV surveillance
% function Result = cctvsurveillanceEx(PriLev)
%
% Creates a TOMLAB MILP problem for cctv surveillance
%
% CCTV SURVEILLANCE
%
% In the course of the last few months, the industrial zone of
% Billston has suffered from a series of break-ins and thefts during
% the night. The zone is watched by security men but there are too
% few of them. The town council in charge of security in this zone
% decides to install surveillance cameras to aid the security men
% with their task. These cameras can be directed and pivot through
% 360 degrees. By installing a camera at the intersection of several
% streets, it is possible to survey all adjoining streets. The map in
% the figure below shows the industrial zone with the limits of the
% zone to be covered by closed circuit TV (CCTV) surveillance and the
% 49 possible locations where to install the cameras. What is the
% minimum number of cameras that have to be installed to survey all
% the streets of this zone and where should they be placed?
%
% The industrial zone in Billston
%
% 13 -- 14 -- 18 -- 17 28 -- 29 35 -- 36
%
% | | | | |
% | | | | |
% |
% | 15 -- 19 26 -- 27 34 48
% |
% | / | | | | |
% | / | | | | |
%
% 12 16 -- 20 24 -- 25 -- 30 33 47 -- 45 -- 46
%
% | / | / | / | |
% | / | / | / | |
%
% 3 -- 11 -- 21 -- 22 31 37 -- 43 -- 44 -- 49
%
% | \ \ | |
% | \ \ | |
% |
% | 4 -- 9 -- 10 23 -- 32 -- 38
% |
% | | \ | |
% | | \ | |
% |
% | 6 5 39 -- 40 -- 41 -- 42
% |
% | | \ | /
% | | \ | /
% | | /
% | 8 7 | /
% | | /
% | | /
% | | /
% | | /
%
% 1 --------------------------- 2
%
% VARIABLES
%
% arcs_out/in These variables describe the network
% of streets
%
% RESULTS
%
% For an interpretation of the results, run:
% Result = cctvsurveillanceEx(2);
%
% REFERENCES
%
% Applications of optimization... Gueret, Prins, Seveaux
% http://web.univ-ubs.fr/lester/~sevaux/pl/index.php
%
% INPUT PARAMETERS
% PriLev Print Level
%
% OUTPUT PARAMETERS
% Result Result structure
% Marcus Edvall, Tomlab Optimization Inc, E-mail: tomlab@tomopt.com
% Copyright (c) 2005-2005 by Tomlab Optimization Inc., $Release: 5.0.0$
% Written Dec 5, 2005. Last modified Dec 5, 2005.
function Result = cctvsurveillanceEx(PriLev)
if nargin < 1
PriLev = 1;
end
arcs_in = [1 1 2 2 3 3 3 3 4 4 4 6 6 9 11 12 12 13 14 14 15 15 16 ...
17 18 19 20 21 22 22 23 24 25 25 26 26 28 30 31 31 32 32 ...
33 33 34 35 37 37 38 39 40 41 43 44 44 45 45 47]';
arcs_out = [2 3 39 41 4 11 12 16 5 6 9 7 8 10 21 13 15 14 15 18 16 ...
19 20 18 19 20 21 22 23 25 32 25 26 30 27 28 29 31 32 33 ...
38 39 34 37 35 36 38 43 40 40 41 42 44 49 45 46 47 48]';
Prob = cctvsurveillance(arcs_in, arcs_out);
Result = tomRun('cplex', Prob, PriLev);
if PriLev > 1,
disp('Put cameras in nodes ')
disp(num2str(find(Result.x_k)'))
end
% MODIFICATION LOG
%
% 051205 med Created.
% 060118 per Added documentation.
% 060125 per Moved disp to end
30.3 Rigging elections
% function Result = riggingelectionsEx(PriLev)
%
% Creates a TOMLAB MILP problem for rigging elections
%
% RIGGING ELECTIONS
%
% In a country not very far away, the party of the duke Sark Mevo has
% finally beaten the ruling coalition headed by the princess Reguel
% Tekris. Mevo wishes to consolidate his position in the capital, the
% fourteen quarters of which need to be grouped to electoral
% districts. A schematic map of the capital is given in the figure
% below. The quarters are numbered from 1 to 14. The two other
% numbers are the forecast number of favorable votes for Mevo and the
% total number of electors per quarter. All electors must vote and
% the winner needs to have the absolute majority. A valid electoral
% district is formed by several adjacent quarters and must have
% between 30,000 and 100,000 voters. Two quarters that touch each
% other just at a point like 12 and 13 are not considered adjacent.
% Electoral districts consisting of a single quarter are permitted if
% it has at least 50,000 voters. Nevertheless, Mevo may not decently
% define an electoral district solely with quarter 10, since this
% contains his residence. Determine a partitioning into five
% electoral districts that maximizes the number of seats for Mevo.
% Should this cause any difficulties, try a partitioning into six
% districts. Snirp, the mathematical jester, suggests Mevo uses
% Mathematical Programming...
%
% +-------------+--+------+-------------------------------+
% | 1 | | 6 | 7 12000/30000 |
% | 17500/30000 | | 9000/+---------------+---------------+
% +-------------+ |40000 | 8 | |
% | 2 | | | 10000/30000 | 9 |
% | 15000/50000 | +------+-------+-------+ 26000/40000 |
% +-------------+ 5 | | 11 | |
% | 3 | 18000/ | 10 | 2500/ +---------------+
% | 14200/20000 | 20000 | 34000/| 10000 | 12 27000/60000|
% +-------------+---------+ 60000 +-------+---------------+
% | 4 | | 13 | 14 |
% | 42000/70000 | | 29000/| 15000/40000 |
% + | | 40000 | |
% +-----------------------+-------+-------+---------------+
%
% Map of the capital and its quarters.
% Legend: quarter number, supporters/electorate
%
% VARIABLES
%
% in/out Quarter in(i) borders to quarter out(i)
% population Population of each quarter
% votes Supporters er quarter
% minpop Min size of an electoral district
% maxpop Max size of an electoral district
% minsingle Min size of a quarter to be a district
% districtsnum Number of districts wanted
% illegalsingle This quarter may not be single
% districts The possible partition of the quarters
% into desired number of districts.
%
% RESULTS
%
% For an interpretation of the results, run:
% Result = riggingelectionsEx(2);
%
% REFERENCES
%
% Applications of optimization... Gueret, Prins, Seveaux
% http://web.univ-ubs.fr/lester/~sevaux/pl/index.php
%
% INPUT PARAMETERS
% PriLev Print Level
%
% OUTPUT PARAMETERS
% Result Result structure
% Marcus Edvall, Tomlab Optimization Inc, E-mail: tomlab@tomopt.com
% Copyright (c) 2005-2005 by Tomlab Optimization Inc., $Release: 5.0.0$
% Written Dec 5, 2005. Last modified Dec 5, 2005.
function Result = riggingelectionsEx(PriLev)
if nargin < 1
PriLev = 1;
end
in = [1 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 8 9 9 10 10 11 11 12 13]';
out = [2 5 3 5 4 5 5 10 6 10 7 8 8 9 9 10 11 11 12 11 13 12 13 14 14]';
population = [30 50 20 70 20 40 30 30 40 60 10 60 40 40]';
votes = [17.5 15 14.2 42 18 9 12 10 26 34 2.5 27 29 15]';
minpop = 30;
maxpop = 100;
minsingle = 50;
districtsnum = 6;
illegalsingle = 10;
districts = [];
rowlen = length(population);
maxq = rowlen;
for q=1:maxq
if (population(q) >= minsingle & q ~= illegalsingle)
districts = [districts; zeros(1,maxq)];
districts(end, q) = 1;
end
idx = find(in == q);
for i = 1:length(idx)
p = out(idx(i));
if (population(q) + population(p) <= maxpop)
if (population(q) + population(p) >= minpop)
districts = addNeighbor(districts, q, p, rowlen);
idx2 = find(in == p);
for j = 1:length(idx2)
r = out(idx2(j));
if (population(q) + population(p) + population(r) <= maxpop)
if (population(q) + population(p) + population(r) >= minpop)
districts = addNeighbor(districts, q, p, rowlen, r);
end
end
end
end
end
end
end
Prob = riggingelections(districts, votes, population, districtsnum);
Result = tomRun('cplex', Prob, PriLev);
Result.districts = districts;
if PriLev > 1,
temp = Result.districts(find(Result.x_k),:);
disp('to rig the elections:')
for d = 1:size(temp,1),
qs = find(temp(d,:));
disp([' merge the quarters ' num2str(qs) ' into a district.'])
end
end
function districts = addNeighbor(districts, q, p, rowlen, r)
if nargin <5
districts = [districts; zeros(1,rowlen)];
districts(end, [q, p]) = [1 1];
else
districts = [districts; zeros(1,rowlen)];
districts(end, [q, p, r]) = [1 1 1];
end
% MODIFICATION LOG
%
% 051205 med Created.
% 060118 per Added documentation.
% 060125 per Moved disp to end
30.4 Gritting roads
% function Result = grittingroadsEx(PriLev)
%
% Creates a TOMLAB MILP problem for gritting roads
%
% GRITTING ROADS
%
% In the case of ice, all the streets of a village need to be
% gritted. A schematic map of the streets is given in the figure
% below. The nodes correspond to street intersections, the arcs to
% the streets that need to be gritted. The arcs are labeled with the
% length of the street in meters.
%
% Graph of the village streets
%
% --150-> --130-> --100->
% 1 2 3 4
% <-140-- <-100--
% | ^ /| ^ ^ | ^
% | 165 / | 170 | | 180
% | | / | | 200 | |
% 165| 230 160| | 190|
% | | / | | | | |
% | | / | | | | |
% V |V V | | V |
% --144-> --128->
% 5 6 7 --109-> 8
% <-144-- <-122--
% ^ /| ^ ^| ^ / |
% 194 / |174 / | | / |
% | / | | / 185|185 / |
% | 218 174| 233 | | / 190
% | / | | / | | 140 |
% | / | | / | | / |
% | V V |/ V |V V
%
% 9 --148-> 10 <-135- 11 -110-> 12
%
% The highway maintenance depot with the gritting truck is located at
% intersection number 1. The truck has a sufficiently large capacity
% to grit all the streets during a single tour. Due to the one-way
% streets, it may be forced to pass several times through the same
% street that has already been gritted. Determine a tour for the
% gritting truck of minimum total length that passes through all
% streets. For bidirectional streets, both directions need to be
% gritted separately.
%
% VARIABLES
%
% in/out Road i starts in in(i) and
% goes out to out(i)
% lengths Lengths of the roads
%
% RESULTS
%
% For an interpretation of the results, run:
% Result = grittingroadsEx(2);
%
% REFERENCES
%
% Applications of optimization... Gueret, Prins, Seveaux
% http://web.univ-ubs.fr/lester/~sevaux/pl/index.php
%
% INPUT PARAMETERS
% PriLev Print Level
%
% OUTPUT PARAMETERS
% Result Result structure
% Marcus Edvall, Tomlab Optimization Inc, E-mail: tomlab@tomopt.com
% Copyright (c) 2005-2005 by Tomlab Optimization Inc., $Release: 5.0.0$
% Written Dec 6, 2005. Last modified Dec 6, 2005.
function Result = grittingroadsEx(PriLev)
if nargin < 1
PriLev = 1;
end
in = [1 1 2 2 2 3 3 4 4 5 5 6 6 6 6 6 7 7 7 7 8 8 8 9 9 10 10 11 11 12]';
out = [2 5 3 5 6 2 4 3 8 1 6 2 5 7 9 10 3 6 8 11 4 11 12 5 10 6 7 7 10 11]';
lengths = [150 165 130 230 160 140 100 100 190 165 144 170 144 128 218 174 ...
200 122 109 185 180 141 190 194 148 174 233 185 135 110]';
Prob = grittingroads(in, out, lengths);
Result = tomRun('cplex', Prob, PriLev);
if PriLev > 1,
twice = find(Result.x_k > 1);
disp('all roads travelled once, except:')
for i = 1:length(twice),
idx = twice(i);
disp([' road from ' num2str(in(idx)) ' to ' num2str(out(idx)) ...
' ( that is travelled ' num2str(Result.x_k(idx)) ' times)'])
end
end
% MODIFICATION LOG
%
% 051206 med Created.
% 060118 per Added documentation.
% 060125 per Moved disp to end
30.5 Location of income tax offices
% function Result = locationofincometaxofficesEx(PriLev)
%
% Creates a TOMLAB MILP problem for location of income tax offices
%
% LOCATION OF INCOME TAX OFFICES
%
% The income tax administration is planning to restructure the
% network of income tax offices in a region. The graph in the figure
% below shows the cities in the region and the major roads. The
% numbers within () close to the cities indicate the population in
% thousands of inhabitants. The arcs are labeled with the distances
% in kilometers. The income tax administration has determined that
% offices should be established in three cities to provide sufficient
% coverage. Where should these offices be located to minimize the
% average distance per inhabitant to the closest income tax office?
%
% Graph of towns and roads of the region
%
%
% (15) (10) (12) (18)
% 1 -15- 2 -22- 3 -18- 4
%
% | \ / | |
% | 24 16 | |
% 18 \ / | |
% | 20 12
% | 5(5) | |
% | | |
% | | \ | |
% | 12 24 | |
% | | \ | |
%
% 7 -15- 8 -30- 9 -12- 6 (24)
% (11) (16) (13)
% | | / | /
% 22 25 19 19 22
% | | / | /
%
% 10 -19- 11 -21- 12 (20)
% (22) (19)
%
% VARIABLES
%
% population Population of each town
% numloc Number of offices to start
% lengths The length of the roads
% in/out A road i goes between towns
% in(i) and out(i)
%
% RESULTS
%
% For an interpretation of the results, run:
% Result = locationofincometaxofficesEx(2);
%
% REFERENCES
%
% Applications of optimization... Gueret, Prins, Seveaux
% http://web.univ-ubs.fr/lester/~sevaux/pl/index.php
%
% INPUT PARAMETERS
% PriLev Print Level
%
% OUTPUT PARAMETERS
% Result Result structure
% Marcus Edvall, Tomlab Optimization Inc, E-mail: tomlab@tomopt.com
% Copyright (c) 2005-2005 by Tomlab Optimization Inc., $Release: 5.0.0$
% Written Dec 6, 2005. Last modified Dec 6, 2005.
function Result = locationofincometaxofficesEx(PriLev)
if nargin < 1
PriLev = 1;
end
population = [15 10 12 18 5 24 11 16 13 22 19 20]';
numloc = 3;
in = [1 1 1 2 3 3 3 4 5 5 6 6 7 7 8 8 9 9 10 11]';
out = [2 5 7 3 4 5 9 6 8 9 9 12 8 10 9 11 11 12 11 12]';
lengths = [15 24 18 22 18 16 20 12 12 24 12 22 15 22 30 ...
25 19 19 19 21]';
Prob = locationofincometaxoffices(population, numloc, in, out, lengths);
Result = tomRun('cplex', Prob, PriLev);
if PriLev > 1,
cities = length(population);
temp = Result.x_k(1:cities);
build = find(temp);
goto = reshape(Result.x_k(1+cities:end),cities,cities);
disp(['Build the offices in towns ' num2str(build') ' and let'])
for i = 1:length(build),
disp([' people from ' num2str(find(goto(build(i),:))) ...
' travel to ' num2str(build(i)) ])
end
end
% MODIFICATION LOG
%
% 051206 med Created.
% 060118 per Added documentation.
% 060125 per Moved disp to end
30.6 Efficiency of hospitals
% function Result = efficiencyofhospitalsEx(PriLev)
%
% Creates a TOMLAB MILP problem for efficiency of hospitals
%
% EFFICIENCY OF HOSPITALS
%
% The administration of the hospitals in Paris decides to measure the
% efficiency of the surgery departments in four major hospitals with
% a desire to improve the service to the public. To keep this study
% anonymous, the hospitals are named H1 to H4. The method suggested
% to measure the efficiency is DEA (Data Envelopment Analysis). This
% method compares the performance of a fictitious hospital with the
% performances of the four hospitals.
%
% Three initial indicators (resources) are taken into account: the
% number of non-medical personnel, the general expenses, and the
% available number of beds. In addition, four final indicators
% (services) are analyzed: the number of hospital admissions per day,
% the number of consultations in the outpatients’ clinic, the number
% of nurses on duty every day, and the number of interns and doctors
% on duty every day. The corresponding data have been analyzed over a
% period of two years and the numbers representing a day of average
% activity in every hospital are given in the following two tables.
%
% Resource indicators
%
% +---------------------+-----+------+-----+-----+
% | | H1 | H2 | H3 | H4 |
% +---------------------+-----+------+-----+-----+
% |Non-medical personnel| 90 | 87 | 51 | 66 |
% |General expenses (k$)|38.89|109.48|40.43|48.41|
% |Number of beds | 34 | 33 | 20 | 33 |
% +---------------------+-----+------+-----+-----+
%
% Service indicators
%
% +-------------------+-----+-----+-----+-----+
% | | H1 | H2 | H3 | H4 |
% +-------------------+-----+-----+-----+-----+
% |Admissions |30.12|18.54|20.88|10.42|
% |Consultations |13.54|14.45| 8.52|17.74|
% |Interns and doctors| 13 | 7 | 8 | 26 |
% |Nurses on duty | 79 | 55 | 47 | 50 |
% +-------------------+-----+-----+-----+-----+
%
% Justify through the DEA method how hospital H2 is performing
% compared to the others.
%
% VARIABLES
%
% resources A matrix describing the resources
% services A matrix describing the services
%
% RESULTS
%
% For an interpretation of the results, run:
% Result = efficiencyofhospitalsEx(2);
%
% REFERENCES
%
% Applications of optimization... Gueret, Prins, Seveaux
% http://web.univ-ubs.fr/lester/~sevaux/pl/index.php
%
% INPUT PARAMETERS
% PriLev Print Level
%
% OUTPUT PARAMETERS
% Result Result structure
% Marcus Edvall, Tomlab Optimization Inc, E-mail: tomlab@tomopt.com
% Copyright (c) 2005-2005 by Tomlab Optimization Inc., $Release: 5.0.0$
% Written Dec 6, 2005. Last modified Dec 6, 2005.
function Result = efficiencyofhospitalsEx(PriLev)
if nargin < 1
PriLev = 1;
end
resources = [90 87 51 66;...
38.89 109.48 40.43 48.41;...
34 33 20 33];
services = [30.12 18.54 20.88 10.42;...
13.54 14.45 8.52 17.74;...
13 7 8 26;...
79 55 47 50];
indices = zeros(size(resources,2),1);
for i=1:size(resources,2)
Prob = efficiencyofhospitals(resources, services, i);
Result = tomRun('cplex', Prob, PriLev);
indices(i,1) = Result.x_k(end,1);
Result.indices = indices;
end
if PriLev > 1,
temp = Result.indices;
for i = 1:length(temp),
disp(['H' num2str(i) ' is ' num2str(100*temp(i)) '% efficient'])
end
end
% MODIFICATION LOG
%
% 051206 med Created.
% 060118 per Added documentation.
% 060125 per Moved disp to end
« Previous « Start » Next »
TOMLAB
