Aspectos básicos de la programación lineal de enteros mixtos: Basada en problemas
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 mediante el enfoque basado en problemas. Si desea ver un vídeo que muestra este ejemplo, consulte Resolver un problema de programación lineal de enteros mixtos utilizando el modelado de optimización.
Si desea ver el enfoque basado en solvers para este problema, consulte Aspectos básicos de la programación lineal de enteros mixtos: Basado en solvers.
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.
Formular el problema
Para formular el problema se deben decidir primero las variables de control. Utilice la variable ingots(1) = 1
para indicar que compra el lingote 1 y ingots(1) = 0
para indicar que no compra el lingote. De forma similar, las variables ingots(2)
a ingots(4)
son variables binarias que indican si compra los lingotes 2 a 4.
Las variables alloys(1)
a alloys(3)
son las toneladas de acero aleado 1, 2 y 3 que se compran. scrap
es la cantidad de chatarra de acero que se compra.
steelprob = optimproblem; ingots = optimvar('ingots',4,'Type','integer','LowerBound',0,'UpperBound',1); alloys = optimvar('alloys',3,'LowerBound',0); scrap = optimvar('scrap','LowerBound',0);
Cree expresiones para los costes asociados a las variables.
weightIngots = [5,3,4,6]; costIngots = weightIngots.*[350,330,310,280]; costAlloys = [500,450,400]; costScrap = 100; cost = costIngots*ingots + costAlloys*alloys + costScrap*scrap;
Incluya el coste como función objetivo en el problema.
steelprob.Objective = cost;
El problema tiene tres restricciones de igualdad. La primera restricción es que el peso total sea 25 toneladas. Calcule el peso del acero.
totalWeight = weightIngots*ingots + sum(alloys) + scrap;
La segunda restricción es que el peso del carbono sea el 5% de 25 toneladas, es decir, 1,25 toneladas. Calcule el peso del carbono en el acero.
carbonIngots = [5,4,5,3]/100; carbonAlloys = [8,7,6]/100; carbonScrap = 3/100; totalCarbon = (weightIngots.*carbonIngots)*ingots + carbonAlloys*alloys + carbonScrap*scrap;
La tercera restricción es que el peso del molibdeno sea 1,25 toneladas. Calcule el peso del molibdeno en el acero.
molybIngots = [3,3,4,4]/100; molybAlloys = [6,7,8]/100; molybScrap = 9/100; totalMolyb = (weightIngots.*molybIngots)*ingots + molybAlloys*alloys + molybScrap*scrap;
Incluya las restricciones en el problema.
steelprob.Constraints.conswt = totalWeight == 25; steelprob.Constraints.conscarb = totalCarbon == 1.25; steelprob.Constraints.consmolyb = totalMolyb == 1.25;
Resolver el problema
Ahora que cuenta con todos los datos, llame al solver.
[sol,fval] = solve(steelprob);
Solving problem using intlinprog. 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.
sol.ingots
ans = 4×1
1
1
0
1
sol.alloys
ans = 3×1
7.0000
0.5000
0
sol.scrap
ans = 3.5000
fval
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.