Aspectos básicos de la programación lineal de enteros mixtos: Basado en solvers
Este ejemplo muestra cómo resolver un problema lineal de enteros mixtos. Aunque no es complejo, el ejemplo muestra los pasos típicos para formular un problema utilizando la sintaxis para intlinprog
.
Si desea ver el enfoque basado en problemas para este problema, consulte Aspectos básicos de la programación lineal de enteros mixtos: Basada en problemas.
Descripción del problema
Desea mezclar aceros de diferentes composiciones químicas para obtener 25 toneladas de acero con una composición química específica. El resultado debería contener un 5% de carbono y un 5% de molibdeno en el peso total, es decir, 25 toneladas*5% = 1,25 toneladas de carbono y 1,25 toneladas de molibdeno. El objetivo consiste en minimizar el coste de mezclar el acero.
Este problema se ha tomado de Carl-Henrik Westerberg, Bengt Bjorklund y Eskil Hultman, "An Application of Mixed Integer Programming in a Swedish Steel Mill". Interfaces February 1977 Vol. 7, No. 2 pp. 39-43, cuyo resumen se encuentra en https://doi.org/10.1287/inte.7.2.39.
Hay disponibles cuatro lingotes de acero para su compra. Solo hay disponible un lingote de cada tipo.
Hay disponibles tres grados de acero aleado y un grado de chatarra de acero para su compra. Los aceros aleados y la chatarra de acero pueden adquirirse en cantidades fraccionarias.
Para formular el problema se deben decidir primero las variables de control. Utilice la variable x(1) = 1
para indicar que compra el lingote 1 y x(1) = 0
para indicar que no compra el lingote. De forma similar, las variables x(2)
a x(4)
son variables binarias que indican si compra los lingotes 2 a 4.
Las variables x(5)
a x(7)
son las toneladas de acero aleado 1, 2 y 3 que se compran, y x(8)
es la cantidad de chatarra de acero que se compra.
Formulación de MATLAB®
Formule el problema especificando las entradas para intlinprog
. La sintaxis de intlinprog
relevante es:
[x,fval] = intlinprog(f,intcon,A,b,Aeq,beq,lb,ub)
Cree las entradas para intlinprog
desde el primero (f
) hasta el último (ub
).
f
es el vector de los coeficientes del coste. Los coeficientes que representan los costes de los lingotes son los pesos de los lingotes multiplicados por su coste por tonelada.
f = [350*5,330*3,310*4,280*6,500,450,400,100];
Las variables de enteros son las primeras cuatro.
intcon = 1:4;
Consejo: Para especificar valores binarios, establezca que las variables sean enteros en intcon
y proporcióneles un límite inferior de 0
y un límite superior de 1
.
El problema no tiene restricciones de desigualdad lineales, así que A
y b
son matrices vacías ([]
).
A = []; b = [];
El problema tiene tres restricciones de igualdad. La primera es que el peso total sea 25 toneladas.
5*x(1) + 3*x(2) + 4*x(3) + 6*x(4) + x(5) + x(6) + x(7) + x(8) = 25
La segunda restricción es que el peso del carbono sea el 5% de 25 toneladas, es decir, 1,25 toneladas.
5*0.05*x(1) + 3*0.04*x(2) + 4*0.05*x(3) + 6*0.03*x(4)
+ 0.08*x(5) + 0.07*x(6) + 0.06*x(7) + 0.03*x(8) = 1.25
La tercera restricción es que el peso del molibdeno sea 1,25 toneladas.
5*0.03*x(1) + 3*0.03*x(2) + 4*0.04*x(3) + 6*0.04*x(4)
+ 0.06*x(5) + 0.07*x(6) + 0.08*x(7) + 0.09*x(8) = 1.25
Especifique las restricciones, que son Aeq*x = beq en forma de matriz.
Aeq = [5,3,4,6,1,1,1,1; 5*0.05,3*0.04,4*0.05,6*0.03,0.08,0.07,0.06,0.03; 5*0.03,3*0.03,4*0.04,6*0.04,0.06,0.07,0.08,0.09]; beq = [25;1.25;1.25];
Cada variable está acotada debajo en cero. Las variables de enteros están acotadas encima en uno.
lb = zeros(8,1);
ub = ones(8,1);
ub(5:end) = Inf; % No upper bound on noninteger variables
Resolver el problema
Ahora que cuenta con todos los datos, llame al solver.
[x,fval] = intlinprog(f,intcon,A,b,Aeq,beq,lb,ub);
LP: Optimal objective value is 8125.600000. Cut Generation: Applied 3 mir cuts. Lower bound is 8495.000000. 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 intcon variables are integer within tolerance, options.IntegerTolerance = 1e-05.
Visualice la solución.
x,fval
x = 8×1
1.0000
1.0000
0
1.0000
7.0000
0.5000
0
3.5000
fval = 8495
La compra óptima cuesta 8.495 USD. Compre los lingotes 1, 2 y 4, pero no el 3, y compre 7,25 toneladas de acero aleado 1, 0,25 toneladas de acero aleado 3 y 3,5 toneladas de chatarra de acero.
Establezca intcon = []
para ver el efecto de resolver el problema sin restricciones de enteros. La solución es diferente, y no es realista, dado que no puede comprar una fracción de un lingote.