Esta página aún no se ha traducido para esta versión. Puede ver la versión más reciente de esta página en inglés.

Asignaciones de Office por programación de enteros binarios: basado en Solver

En este ejemplo se muestra cómo resolver un problema de asignación mediante la programación de enteros binarios mediante la función.intlinprog Para conocer el enfoque basado en problemas de este problema, consulte.Asignaciones de Office por programación de enteros binarios: basado en problemas

Problema de asignación de oficina

Usted quiere asignar a seis personas, Marcelo, Rakesh, Peter, Tom, Marjorie y Mary Ann, a siete oficinas. Cada oficina no puede tener más de una persona, y cada persona obtiene exactamente una oficina. Así que habrá una oficina vacía. Las personas pueden dar preferencias para las oficinas, y sus preferencias se consideran en función de su antigüedad. Cuanto más tiempo hayan estado en el MathWorks, mayor será la antigüedad. Algunas oficinas tienen ventanas, otras no, y una ventana es más pequeña que otras. Además, Peter y Tom a menudo trabajan juntos, por lo que deben estar en las oficinas adyacentes. Marcelo y Rakesh a menudo trabajan juntos, y deben estar en las oficinas adyacentes.

Office layout

Las oficinas 1, 2, 3 y 4 están dentro de las oficinas (sin ventanas). Las oficinas 5, 6 y 7 tienen ventanas, pero la ventana en la oficina 5 es más pequeña que las otras dos. Así es como se organizan las oficinas.

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

Formulación problemática

Es necesario formular el problema matemáticamente. En primer lugar, elija lo que representa cada elemento de la variable de solución en el problema.x Puesto que se trata de un problema de enteros binarios, una buena opción es que cada elemento represente a una persona asignada a una oficina. Si la persona está asignada a la oficina, la variable tiene el valor 1. Si la persona no está asignada a la oficina, la variable tiene el valor 0. Número de personas de la siguiente manera:

  1. Mary Ann

  2. Marjorie

  3. Tom

  4. Peter

  5. Marcelo

  6. Rakesh

es un vector.x Los elementos que corresponden a Mary Ann se asignan a la oficina 1, oficina 2, etc., a la oficina 7.x(1)x(7) Los siguientes siete elementos corresponden a Marjorie siendo asignada a las siete oficinas, etc. En absoluto, el vector tiene 42 elementos, ya que seis personas son asignadas a siete oficinas.x

Antigüedad

Desea ponderar las preferencias basadas en la antigüedad para que cuanto más tiempo haya estado en MathWorks, más contarán sus preferencias. La antigüedad es la siguiente: Mary Ann 9 años, Marjorie 10 años, Tom 5 años, Peter 3 años, Marcelo 1,5 años, y Rakesh 2 años. Cree un vector de peso normalizado basado en la antigüedad.

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

Preferencias de la oficina del pueblo

Configurar una matriz de preferencias donde las filas corresponden a las oficinas y las columnas corresponden a las personas. Pida a cada persona que dé valores para cada oficina para que la suma de todas sus opciones, es decir, su columna, sume a 100. Un número más alto significa que la persona prefiere la oficina. Las preferencias de cada persona se enumeran en un vector de columna.

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];

El elemento iésimo del vector de preferencia de una persona es cuán alto valoran la iésima oficina. Por lo tanto, la matriz de preferencia combinada es la siguiente.

prefmatrix = [MaryAnn Marjorie Tom Peter Marcelo Rakesh];

Pesa la matriz de preferencias para escalar las columnas por antigüedad.weightvector Además, es más conveniente remodelar esta matriz como un vector en orden de columnas para que corresponda al vector.x

PM = prefmatrix * diag(weightvector); c = PM(:);

Función objetivo

El objetivo es maximizar la satisfacción de las preferencias ponderadas por la antigüedad. Esta es una función objetiva lineal

max c'*x

o equivalentemente

.min -c'*x

Restricciones

El primer conjunto de restricciones requiere que cada persona obtiene exactamente una oficina, es decir, para cada persona, la suma de los valores correspondientes a esa persona es exactamente una.x Por ejemplo, como Marjorie es la segunda persona, esto significa que.sum(x(8:14))=1 Representan estas restricciones lineales en una matriz de igualdad y un vector, donde, mediante la creación de las matrices apropiadas.AeqbeqAeq*x = beq La matriz consta de unos y ceros.Aeq Por ejemplo, la segunda fila de Will corresponde a Marjorie obteniendo una oficina, por lo que la fila se ve así:Aeq

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

Hay siete 1s en las columnas 8 a 14 y 0s en otro lugar. Entonces equivale a.Aeq(2,:)*x = 1sum(x(8:14)) = 1

numOffices = 7; numPeople = 6; numDim = numOffices * numPeople; onesvector = ones(1,numOffices);

Cada fila de corresponde a una persona.Aeq

Aeq = blkdiag(onesvector,onesvector,onesvector,onesvector, ...     onesvector,onesvector); beq = ones(numPeople,1);

El segundo conjunto de restricciones son las desigualdades. Estas restricciones especifican que cada oficina no tiene más de una persona en ella, es decir, cada oficina tiene una persona en ella, o está vacía. Construya la matriz y el vector de tal que para capturar estas restricciones.AbA*x <= b Cada fila de y corresponde a una oficina y así la fila 1 corresponde a las personas asignadas a la oficina 1.Ab Esta vez, las filas tienen este tipo de patrón, para la fila 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

Cada fila después de esto es similar, pero desplazado (circularmente) a la derecha por un punto. Por ejemplo, la fila 3 corresponde a la Oficina 3 y dice que, es decir, la Oficina 3 no puede tener más de una persona en ella.A(3,:)*x <= 1

A = repmat(eye(numOffices),1,numPeople); b = ones(numOffices,1);

El siguiente conjunto de restricciones también son desigualdades, así que Agréguelos a la matriz y al vector, que ya contienen las desigualdades desde arriba.Ab Usted quiere que Tom y Peter no más de una oficina lejos el uno del otro, y lo mismo con Marcelo y Rakesh. En primer lugar, construir la matriz de distancia de las oficinas en función de sus ubicaciones físicas y el uso de distancias aproximadas de Manhattan. Esta es una matriz simétrica.

D = zeros(numOffices);

Configure la mitad superior derecha de la matriz.

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;

La mitad inferior izquierda es la misma que la parte superior derecha.

D = triu(D)' + D;

Encuentre las oficinas que están a más de una distancia de la unidad.

[officeA,officeB] = find(D > 1); numPairs = length(officeA)
numPairs = 26 

Esto encuentra pares de oficinas que no son adyacentes.numPairs Para estos pares, si Tom ocupa una oficina en el par, entonces Peter no puede ocupar la otra oficina en la pareja. Si lo hiciera, no serían adyacentes. Lo mismo es cierto para Marcelo y Rakesh. Esto proporciona más restricciones de desigualdad que se agregan a y.2*numPairsAb

Agregue suficientes filas para acomodar estas restricciones.A

numrows = 2*numPairs + numOffices;  A((numOffices+1):numrows, 1:numDim) = zeros(2*numPairs,numDim);

Para cada par de oficinas en, para el que corresponde a Tom en y para el que corresponde a Pedro en,numPairsx(i)officeAx(j)OfficeB

.x(i) + x(j) <= 1

Esto significa que Tom o Peter pueden ocupar una de estas oficinas, pero ambos no pueden.

Tom es la persona 3 y Peter es la persona 4.

tom = 3; peter = 4;

Marcelo es la persona 5 y Rakesh es la persona 6.

marcelo = 5; rakesh = 6;

Las siguientes funciones anónimas devuelven el índice en x correspondiente a Tom, Peter, Marcelo y Rakesh respectivamente en la oficina 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);

Resolver utilizandointlinprog

La formulación del problema consiste en una función objetiva lineal

min -c'*x

sujeta a las restricciones lineales

Aeq*x = beq

A*x <= b

todas las variables binarias

Ya hiciste las,, y las entradas.AbAeqbeq Ahora establece la función objetivo.

f = -c;

Para asegurarse de que las variables son binarias, coloque los límites inferiores de 0, los límites superiores de 1 y establezca para representar todas las variables.intvars

lb = zeros(size(f)); ub = lb + 1; intvars = 1:length(f);

Llame para resolver el problema.intlinprog

[x,fval,exitflag,output] = intlinprog(f,intvars,A,b,Aeq,beq,lb,ub);
LP:                Optimal objective value is -33.868852.                                             Cut Generation:    Applied 1 Gomory cut.                                                                                Lower bound is -33.836066.                                                                           Relative gap is 0.00%.                                                             Optimal solution found.  Intlinprog stopped at the root node because the objective value is within a gap tolerance of the optimal value, options.AbsoluteGapTolerance = 0 (the default value). The intcon variables are integer within tolerance, options.IntegerTolerance = 1e-05 (the default value). 

Vea la solución: ¿quién tiene cada oficina?

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');

Calidad de la solución

Para este problema, la satisfacción de las preferencias por antigüedad se maximiza al valor de. = 1 le indica que convergió a una solución óptima.-fvalexitflagintlinprog La estructura de salida proporciona información sobre el proceso de solución, como cuántos nodos se exploraron y la brecha entre los límites inferior y superior en el cálculo de bifurcación. En este caso, no se generaron nodos de bifurcación y enlazados, lo que significa que el problema se resolvió sin un paso de bifurcación y enlazado. La brecha es 0, lo que significa que la solución es óptima, sin ninguna diferencia entre los límites inferior y superior calculados internamente en la función objetiva.

fval,exitflag,output
fval = -33.8361 
exitflag = 1 
output = struct with fields:
        relativegap: 0
        absolutegap: 0
      numfeaspoints: 1
           numnodes: 0
    constrviolation: 0
            message: 'Optimal solution found.↵↵Intlinprog stopped at the root node because the objective value is within a gap tolerance of the optimal value, options.AbsoluteGapTolerance = 0 (the default value). The intcon variables are integer within tolerance, options.IntegerTolerance = 1e-05 (the default value).'

Temas relacionados