Main Content

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 Mixed-Integer Linear Programming Basics: Solver-Based.

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.

IngotWeightinTons%Carbon%MolybdenumCostTon1553$3502343$3303454$3104634$280

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.

Alloy%Carbon%MolybdenumCostTon186$500277$450368$400Scrap39$100

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 default
value). The intcon variables are integer within tolerance,
options.IntegerTolerance = 1e-05 (the default value).

Visualice la solución.

sol.ingots
ans = 4×1

    1.0000
    1.0000
         0
    1.0000

sol.alloys
ans = 3×1

    7.2500
         0
    0.2500

sol.scrap
ans = 3.5000
fval
fval = 8.4950e+03

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.

Temas relacionados