www.gusucode.com > optim 案例源码 matlab代码程序 > optim/officeassign.m

    %% Office Assignments by Binary Integer Programming
% This example shows how to solve an assignment problem by binary integer
% programming using the |intlinprog| function.

%   Copyright 1990-2014 The MathWorks, Inc. 

%% Office Assignment Problem
% You want to assign six people, Marcelo, Rakesh, Peter, Tom, Marjorie, and
% Mary Ann, to seven offices. Each office can have no more than one person,
% and each person gets exactly one office. So there will be one empty
% office. People can give preferences for the offices, and their
% preferences are considered based on their seniority. The longer they have
% been at the MathWorks, the higher the seniority. Some offices have
% windows, some do not, and one window is smaller than others.
% Additionally, Peter and Tom often work together, so should be in adjacent
% offices. Marcelo and Rakesh often work together, and should be in
% adjacent offices.

%% Office Layout
% Offices 1, 2, 3, and 4 are inside offices (no windows). Offices 5, 6, and
% 7 have windows, but the window in office 5 is smaller than the other two.
% Here is how the offices are arranged.

name = {'Office 1','Office 2','Office 3','Office 4','Office 5','Office 6','Office 7'};
printofficeassign(name)

%% Problem Formulation
% You need to formulate the problem mathematically. First, choose what each
% element of your solution variable |x| represents in the problem. Since
% this is a binary integer problem, a good choice is that each element
% represents a person assigned to an office. If the person is assigned to
% the office, the variable has value 1. If the person is not assigned to
% the office, the variable has value 0. Number people as follows:

%%
%  1. Mary Ann
%  2. Marjorie
%  3. Tom
%  4. Peter
%  5. Marcelo
%  6. Rakesh

%%
% |x| is a vector. The elements |x(1)| to |x(7)| correspond to Mary Ann
% being assigned to office 1, office 2, etc., to office 7. The next seven
% elements correspond to Marjorie being assigned to the seven offices, etc.
% In all, the |x| vector has 42 elements, since six people are assigned to
% seven offices.

%% Seniority
% You want to weight the preferences based on seniority so that the longer
% you have been at MathWorks, the more your preferences count. The
% seniority is as follows: Mary Ann 9 years, Marjorie 10 years, Tom 5
% years, Peter 3 years, Marcelo 1.5 years, and Rakesh 2 years. Create a
% normalized weight vector based on seniority.

seniority = [9 10 5 3 1.5 2];
weightvector = seniority/sum(seniority);

%% People's Office Preferences
% Set up a preference matrix where the rows correspond to offices and the
% columns correspond to people. Ask each person to give values for each
% office so that the sum of all their choices, i.e., their column, sums to
% 100.  A higher number means the person prefers the office. Each person's
% preferences are listed in a column vector.

MaryAnn = [0; 0; 0; 0; 10; 40; 50];
Marjorie = [0; 0; 0; 0; 20; 40; 40];
Tom = [0; 0; 0; 0; 30; 40; 30];
Peter = [1; 3; 3; 3; 10; 40; 40];
Marcelo = [3; 4; 1; 2; 10; 40; 40];
Rakesh = [10; 10; 10; 10; 20; 20; 20];

%% 
% The ith element of a person's preference vector is how highly they value
% the ith office. Thus, the combined preference matrix is as follows.

prefmatrix = [MaryAnn Marjorie Tom Peter Marcelo Rakesh];

%%
% Weight the preferences matrix by |weightvector| to scale the columns by
% seniority.  Also, it's more convenient to reshape this matrix as a vector
% in column order so that it corresponds to the |x| vector.
PM = prefmatrix * diag(weightvector);
c = PM(:);

%% Objective Function
% The objective is to maximize the satisfaction of the preferences weighted
% by seniority. This is a linear objective function
%%
%       max c'*x
%%
% or equivalently
%%
%       min -c'*x.

%% Constraints
% The first set of constraints requires that each person gets exactly one
% office, that is for each person, the sum of the |x| values corresponding
% to that person is exactly one. For example, since Marjorie is the second
% person, this means that |sum(x(8:14))=1|. Represent these linear
% constraints in an equality matrix |Aeq| and vector |beq|, where |Aeq*x =
% beq|, by building the appropriate matrices.  The matrix |Aeq| consists of
% ones and zeros. For example, the second row of |Aeq| will correspond to
% Marjorie getting one office, so the row looks like this:
%%
%       0 0 0 0 0 0 0 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 ... 0 0 0
%%
% There are seven 1s in columns 8 through 14 and 0s elsewhere. Then
% |Aeq(2,:)*x = 1| is equivalent to |sum(x(8:14)) = 1|.
numOffices = 7;
numPeople = 6;
numDim = numOffices * numPeople;
onesvector = ones(1,numOffices);
% Each row of Aeq corresponds to one person. 
Aeq = blkdiag(onesvector,onesvector,onesvector,onesvector, ...
    onesvector,onesvector);
beq = ones(numPeople,1);

%%
% The second set of constraints are inequalities. These constraints specify
% that each office has no more than one person in it, i.e., each office has
% one person in it, or is empty. Build the matrix |A| and the vector |b|
% such that |A*x <= b| to capture these constraints. Each row of |A| and
% |b| corresponds to an office and so row 1 corresponds to people assigned
% to office 1.  This time, the rows have this type of pattern, for row 1:
%%
%      1 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 ... 1 0 0 0 0 0 0
%%
% Each row after this is similar but shifted (circularly) to the right by
% one spot. For example, row 3 corresponds to office 3 and says that
% |A(3,:)*x <= 1|, i.e., office 3 cannot have more than one person in it.
A = repmat(eye(numOffices),1,numPeople);
b = ones(numOffices,1);

%%
% The next set of constraints are also inequalities, so add them to the
% matrix |A| and vector |b|, which already contain the inequalities from
% above. You want Tom and Peter no more than one office away from each
% other, and the same with Marcelo and Rakesh. First, build the distance
% matrix of the offices based on their physical locations and using
% approximate Manhattan distances. This is a symmetric matrix.
D = zeros(numOffices);
%   Set up the top right half of the matrix.
D(1,2:end) = [1 2 3 2 3 4];
D(2,3:end) = [1 2 1 2 3];
D(3,4:end) = [1 2 1 2];
D(4,5:end) = [3 2 1];
D(5,6:end) = [1 2];
D(6,end)   = 1;
% The lower left half is the same as the upper right.
D = triu(D)' + D;

% Find the offices that are more than one distance unit away.
[officeA,officeB] = find(D > 1);
numPairs = length(officeA)

%%
% This finds |numPairs| pairs of offices that are not adjacent. For these
% pairs, if Tom occupies one office in the pair, then Peter cannot occupy
% the other office in the pair. If he did, they would not be adjacent. The
% same is true for Marcelo and Rakesh. This gives |2*numPairs| more
% inequality constraints that you add to |A| and |b|.

% Add enough rows to A to accommodate these constraints.
numrows = 2*numPairs + numOffices; 
A((numOffices+1):numrows, 1:numDim) = zeros(2*numPairs,numDim);

%%
% For each pair of offices in |numPairs|, for the |x(i)| that corresponds to
% Tom in |officeA| and for the |x(j)| that corresponds to Peter in
% |OfficeB|, 
%%
%   x(i) + x(j) <= 1.
%%
% This means that either Tom or Peter can occupy one of these offices, but
% they both cannot.
%
% Tom is person 3 and Peter is person 4.
tom = 3;
peter = 4;
%%
% Marcelo is person 5 and Rakesh is person 6.
marcelo = 5;
rakesh = 6;
%%
% The following anonymous functions return the index in x 
% corresponding to Tom, Peter, Marcelo and Rakesh respectively
% in office i.
tom_index=@(officenum) (tom-1)*numOffices+officenum;
peter_index=@(officenum) (peter-1)*numOffices+officenum;
marcelo_index=@(officenum) (marcelo-1)*numOffices+officenum;
rakesh_index=@(officenum) (rakesh-1)*numOffices+officenum;

for i = 1:numPairs    
    tomInOfficeA = tom_index(officeA(i));
    peterInOfficeB = peter_index(officeB(i));
    A(i+numOffices, [tomInOfficeA, peterInOfficeB]) = 1;
   
    % Repeat for Marcelo and Rakesh, adding more rows to A and b.
    marceloInOfficeA = marcelo_index(officeA(i));
    rakeshInOfficeB = rakesh_index(officeB(i));
    A(i+numPairs+numOffices, [marceloInOfficeA, rakeshInOfficeB]) = 1;
end
b(numOffices+1:numOffices+2*numPairs) = ones(2*numPairs,1);

%% Solve Using intlinprog
% The problem formulation consists of a linear objective function
%%
%     min -c'*x
%%
% subject to the linear constraints
%%
%     Aeq*x = beq
%     A*x <= b
%     all variables binary
%%
% You already made the |A|, |b|, |Aeq|, and |beq| entries. Now set the
% objective function.
f = -c;
%%
% To ensure that the variables are binary, put lower bounds of 0, upper
% bounds of 1, and set |intvars| to represent all variables.
lb = zeros(size(f));
ub = lb + 1;
intvars = 1:length(f);
%%
% Call |intlinprog| to solve the problem.

[x,fval,exitflag,output] = intlinprog(f,intvars,A,b,Aeq,beq,lb,ub);

%% View the Solution -- Who Got Each Office?
numPeople = 7; office = cell(numPeople,1);
for i=1:numPeople
    office{i} = find(x(i:numPeople:end)); % people index in office
end

people = {'Mary Ann', 'Marjorie','  Tom   ',' Peter  ','Marcelo ',' Rakesh '};
for i=1:numPeople
    if isempty(office{i})
        name{i} = ' empty  ';
    else
        name{i} = people(office{i});
    end
end

printofficeassign(name);
title('Solution of the Office Assignment Problem');

%% Solution Quality
% For this problem, the satisfaction of the preferences by seniority is
% maximized to the value of |-fval|. |exitflag| = 1 tells you that
% |intlinprog| converged to an optimal solution. The output structure gives
% information about the solution process, such as how many nodes were
% explored, and the gap between the lower and upper bounds in the branching
% calculation. In this case, no branch-and-bound nodes were generated,
% meaning the problem was solved without a branch-and-bound step. The gap
% is 0, meaning the solution is optimal, with no difference between the
% internally calculated lower and upper bounds on the objective function.

fval,exitflag,output