Aspectos básicos de la programación lineal de enteros mixtos: basado 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 ilustra 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.
Running HiGHS 1.7.1: Copyright (c) 2024 HiGHS under MIT licence terms
Coefficient ranges:
Matrix [3e-02, 6e+00]
Cost [1e+02, 2e+03]
Bound [1e+00, 1e+00]
RHS [1e+00, 2e+01]
Presolving model
3 rows, 8 cols, 24 nonzeros 0s
3 rows, 8 cols, 18 nonzeros 0s
Solving MIP model with:
3 rows
8 cols (4 binary, 0 integer, 0 implied int., 4 continuous)
18 nonzeros
Nodes | B&B Tree | Objective Bounds | Dynamic Constraints | Work
Proc. InQueue | Leaves Expl. | BestBound BestSol Gap | Cuts InLp Confl. | LpIters Time
0 0 0 0.00% 0 inf inf 0 0 0 0 0.0s
0 0 0 0.00% 8125.6 inf inf 0 0 0 4 0.0s
R 0 0 0 0.00% 8495 8495 0.00% 5 0 0 5 0.0s
Solving report
Status Optimal
Primal bound 8495
Dual bound 8495
Gap 0% (tolerance: 0.01%)
Solution status feasible
8495 (objective)
0 (bound viol.)
0 (int. viol.)
0 (row viol.)
Timing 0.02 (total)
0.00 (presolve)
0.00 (postsolve)
Nodes 1
LP iterations 5 (total)
0 (strong br.)
1 (separation)
0 (heuristics)
Optimal solution found.
Intlinprog stopped at the root node because the objective value is within a gap tolerance of the optimal value, options.AbsoluteGapTolerance = 1e-06. The intcon variables are integer within tolerance, options.ConstraintTolerance = 1e-06.
Visualice la solución.
sol.ingots
ans = 4×1
1
1
0
1
sol.alloys
ans = 3×1
7.2500
0
0.2500
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.
