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 problemas

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

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 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.

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

Formulación problemática

Es necesario formular el problema matemáticamente. Cree variables binarias que indiquen si una persona ocupa una oficina. La lista de nombres de personas es

namelist = {'Mary Ann','Marjorie','Tom','Peter','Marcelo','Rakesh'};

Crear variables binarias indexadas por número de oficina y nombre.

occupy = optimvar('occupy',namelist,officelist,...     'Type','integer','LowerBound',0,'Upperbound',1);

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

PM = diag(weightvector) * prefmatrix;

Función objetivo

El objetivo es maximizar la satisfacción de las preferencias ponderadas por la antigüedad. Esta es la función de objetivo lineal.sum(sum(occupy.*PM))

Cree un problema de optimización e incluya la función objetiva.

peopleprob = optimproblem('ObjectiveSense','maximize','Objective',sum(sum(occupy.*PM)));

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.occupy

peopleprob.Constraints.constr1 = sum(occupy,2) == 1;

El segundo conjunto de restricciones son las desigualdades. Estas restricciones especifican que cada oficina no tiene más de una persona en ella.

peopleprob.Constraints.constr2 = sum(occupy,1) <= 1;

Usted quiere que Tom y Peter no más de una oficina lejos el uno del otro, y lo mismo con Marcelo y Rakesh.

Establecer restricciones que Tom y Peter no están más de 1 de distancia entre sí.

peopleprob.Constraints.constrpt1 = occupy('Tom','Office 1') + sum(occupy('Peter',:)) - occupy('Peter','Office 2') <= 1; peopleprob.Constraints.constrpt2 = occupy('Tom','Office 2') + sum(occupy('Peter',:)) - occupy('Peter','Office 1') ...     - occupy('Peter','Office 3') - occupy('Peter','Office 5') <= 1; peopleprob.Constraints.constrpt3 = occupy('Tom','Office 3') + sum(occupy('Peter',:)) - occupy('Peter','Office 2') ...     - occupy('Peter','Office 4') - occupy('Peter','Office 6') <= 1; peopleprob.Constraints.constrpt4 = occupy('Tom','Office 4') + sum(occupy('Peter',:)) - occupy('Peter','Office 3') ...     - occupy('Peter','Office 7') <= 1; peopleprob.Constraints.constrpt5 = occupy('Tom','Office 5') + sum(occupy('Peter',:)) - occupy('Peter','Office 2') ...     - occupy('Peter','Office 6') <= 1; peopleprob.Constraints.constrpt6 = occupy('Tom','Office 6') + sum(occupy('Peter',:)) - occupy('Peter','Office 3') ...     - occupy('Peter','Office 5') - occupy('Peter','Office 7') <= 1; peopleprob.Constraints.constrpt7 = occupy('Tom','Office 7') + sum(occupy('Peter',:)) - occupy('Peter','Office 4') ...     - occupy('Peter','Office 6') <= 1;

Ahora crea restricciones que Marcelo y Rakesh no están a más de 1 distancia entre sí.

peopleprob.Constraints.constmr1 = occupy('Marcelo','Office 1') + sum(occupy('Rakesh',:)) - occupy('Rakesh','Office 2') <= 1; peopleprob.Constraints.constmr2 = occupy('Marcelo','Office 2') + sum(occupy('Rakesh',:)) - occupy('Rakesh','Office 1') ...     - occupy('Rakesh','Office 3') - occupy('Rakesh','Office 5') <= 1; peopleprob.Constraints.constmr3 = occupy('Marcelo','Office 3') + sum(occupy('Rakesh',:)) - occupy('Rakesh','Office 2') ...     - occupy('Rakesh','Office 4') - occupy('Rakesh','Office 6') <= 1; peopleprob.Constraints.constmr4 = occupy('Marcelo','Office 4') + sum(occupy('Rakesh',:)) - occupy('Rakesh','Office 3') ...     - occupy('Rakesh','Office 7') <= 1; peopleprob.Constraints.constmr5 = occupy('Marcelo','Office 5') + sum(occupy('Rakesh',:)) - occupy('Rakesh','Office 2') ...     - occupy('Rakesh','Office 6') <= 1; peopleprob.Constraints.constmr6 = occupy('Marcelo','Office 6') + sum(occupy('Rakesh',:)) - occupy('Rakesh','Office 3') ...     - occupy('Rakesh','Office 5') - occupy('Rakesh','Office 7') <= 1; peopleprob.Constraints.constmr7 = occupy('Marcelo','Office 7') + sum(occupy('Rakesh',:)) - occupy('Rakesh','Office 4') ...     - occupy('Rakesh','Office 6') <= 1;

Resolver problema de asignación

Llame para resolver el problema.solve

[soln,fval,exitflag,output] = solve(peopleprob);
LP:                Optimal objective value is -33.836066.                                              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?

numOffices = length(officelist); office = cell(numOffices,1); for i=1:numOffices     office{i} = find(soln.occupy(:,i)); % people index in office end  whoinoffice = officelist; % allocate for i=1:numOffices     if isempty(office{i})         whoinoffice{i} = ' empty  ';     else         whoinoffice{i} = namelist(office{i});     end end  printofficeassign(whoinoffice); 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.fval El valor de indica que convergió a una solución óptima.exitflagsolve 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 absoluta 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).'
             solver: 'intlinprog'

Temas relacionados