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.

Problema de stock de corte: basado en problemas

Este ejemplo muestra cómo resolver una programación lineal Using con una subrutina de programación lineal de enteros.problema de stock de corte El ejemplo utiliza el enfoque.Configuración de optimización basada en problemas Para el enfoque basado en el solucionador, consulte.Problema de stock de corte: basado en Solver

Descripción del problema

Un molino de madera comienza con árboles que han sido recortados a troncos de longitud fija. Especifique la longitud de registro fija.

logLength = 40;

A continuación, el molino corta los troncos en longitudes fijas adecuadas para su posterior procesamiento. El problema es cómo hacer los cortes para que el molino satisfaga un conjunto de órdenes con el menor número de registros.

Especifique estas longitudes fijas y las cantidades de pedido para las longitudes.

lengthlist = [8; 12; 16; 20]; quantity = [90; 111; 55; 30]; nLengths = length(lengthlist);

Supongamos que no hay pérdida material en la fabricación de cortes, y ningún costo para el corte.

Formulación de programación lineal

Varios autores, incluyendo Ford y Fulkerson [1] y Gilmore y Gomory [2], sugieren el siguiente procedimiento, que se implementa en la siguiente sección. Un patrón de corte es un conjunto de longitudes a las que se puede cortar un solo registro.

En lugar de generar cada posible patrón de corte, es más eficiente generar patrones de corte como la solución de un subproblema. A partir de un conjunto base de patrones de corte, resuelva el problema de programación lineal de minimizar el número de registros utilizados sujetos a la restricción de que los cortes, utilizando los patrones existentes, satisfacen las demandas.

Después de resolver el problema, genere un nuevo patrón resolviendo un subproblema de programación lineal de enteros. El subproblema es encontrar el mejor patrón nuevo, es decir, el número de cortes de cada longitud en el que suman no más que la longitud total posible.lengthlistlogLength La cantidad a optimizar es el coste reducido del nuevo patrón, que es uno menos la suma de los multiplicadores de Lagrange para la solución actual multiplicado por el nuevo patrón de corte. Si esta cantidad es negativa, la incorporación de ese patrón en el programa lineal mejorará su objetivo. Si no, entonces no existe un mejor patrón de corte, y los patrones utilizados hasta ahora dan la solución de programación lineal óptima. La razón de esta conclusión es exactamente paralela a la razón de Cuándo detener el método Simplex primitivo: el método finaliza cuando no hay ninguna variable con un costo reducido negativo. El problema en este ejemplo termina cuando no hay patrón con coste reducido negativo. Para obtener más información y un ejemplo, consulte y sus referencias.Algoritmos de generación de columnas

Después de resolver el problema de programación lineal de esta manera, puede tener soluciones que no sean de enteros. Por lo tanto, resuelva el problema una vez más, utilizando los patrones generados y restringiendo las variables para que tengan valores enteros.

La formulación basada en problemas de MATLAB

Un patrón, en esta formulación, es un vector de enteros que contiene el número de cortes de cada longitud en.lengthlist Organice una matriz denominada para almacenar los patrones, donde cada columna de la matriz proporciona un patrón.patterns Por ejemplo,

<math display="block">
<mrow>
<mi mathvariant="normal">patterns</mi>
<mo>=</mo>
<mrow>
<mo>[</mo>
<mtable>
<mtr>
<mtd>
<mrow>
<mn>2</mn>
</mrow>
</mtd>
<mtd>
<mrow>
<mn>0</mn>
</mrow>
</mtd>
</mtr>
<mtr>
<mtd>
<mrow>
<mn>0</mn>
</mrow>
</mtd>
<mtd>
<mrow>
<mn>2</mn>
</mrow>
</mtd>
</mtr>
<mtr>
<mtd>
<mrow>
<mn>0</mn>
</mrow>
</mtd>
<mtd>
<mrow>
<mn>1</mn>
</mrow>
</mtd>
</mtr>
<mtr>
<mtd>
<mrow>
<mn>1</mn>
</mrow>
</mtd>
<mtd>
<mrow>
<mn>0</mn>
</mrow>
</mtd>
</mtr>
</mtable>
<mo>]</mo>
</mrow>
<mo>.</mo>
</mrow>
</math>

El primer patrón (columna) representa dos cortes de longitud 8 y un corte de longitud 20. El segundo patrón representa dos cortes de longitud 12 y un corte de longitud 16. Cada uno es un patrón factible porque el total de los cortes no es más de = 40.logLength

En esta formulación, si es un vector de columna de enteros que contiene el número de veces que se utiliza cada patrón, entonces es un vector de columna que da el número de cortes de cada tipo.xpatterns*x La restricción de la demanda de reunión es.patterns*x >= quantity Por ejemplo, utilizando la matriz anterior, supongamos quepatterns

<math display="inline">
<mrow>
<mi mathvariant="italic">x</mi>
<mo>=</mo>
<mrow>
<mo>[</mo>
<mtable>
<mtr>
<mtd>
<mrow>
<mn>45</mn>
</mrow>
</mtd>
</mtr>
<mtr>
<mtd>
<mrow>
<mn>56</mn>
</mrow>
</mtd>
</mtr>
</mtable>
<mo>]</mo>
</mrow>
</mrow>
</math>
. (Esto utiliza 101 registros.)x Entonces

<math display="block">
<mrow>
<mi mathvariant="normal">patterns</mi>
<mo>*</mo>
<mi mathvariant="italic">x</mi>
<mo>=</mo>
<mrow>
<mo>[</mo>
<mtable>
<mtr>
<mtd>
<mrow>
<mn>90</mn>
</mrow>
</mtd>
</mtr>
<mtr>
<mtd>
<mrow>
<mn>112</mn>
</mrow>
</mtd>
</mtr>
<mtr>
<mtd>
<mrow>
<mn>56</mn>
</mrow>
</mtd>
</mtr>
<mtr>
<mtd>
<mrow>
<mn>45</mn>
</mrow>
</mtd>
</mtr>
</mtable>
<mo>]</mo>
</mrow>
<mo>,</mo>
</mrow>
</math>

que representa una solución factible porque el resultado excede la demanda

<math display="block">
<mrow>
<mi mathvariant="normal">quantity</mi>
<mo>=</mo>
<mrow>
<mo>[</mo>
<mtable>
<mtr>
<mtd>
<mrow>
<mn>90</mn>
</mrow>
</mtd>
</mtr>
<mtr>
<mtd>
<mrow>
<mn>111</mn>
</mrow>
</mtd>
</mtr>
<mtr>
<mtd>
<mrow>
<mn>55</mn>
</mrow>
</mtd>
</mtr>
<mtr>
<mtd>
<mrow>
<mn>30</mn>
</mrow>
</mtd>
</mtr>
</mtable>
<mo>]</mo>
</mrow>
<mo>.</mo>
</mrow>
</math>

Para tener un patrón de corte factible inicial, utilice los patrones más simples, que tienen sólo una longitud de corte. Utilice tantos cortes de esa longitud como sea factible para el registro.

patterns = diag(floor(logLength./lengthlist)); nPatterns = size(patterns,2);

Para generar nuevos patrones a partir de los existentes basados en los multiplicadores de Lagrange actuales, resuelve un subproblema. Llame al subproblema en un bucle para generar patrones hasta que no se encuentra ninguna mejora. El objetivo del subproblema sólo depende de los multiplicadores de Lagrange actuales. Las variables son enteros no negativos que representan el número de cortes de cada longitud. La única restricción es que la suma de las longitudes de los cortes en un patrón no es más que la longitud del registro.

subproblem = optimproblem(); cuts = optimvar('cuts', nLengths, 1, 'Type','integer','LowerBound',zeros(nLengths,1)); subproblem.Constraints = dot(lengthlist,cuts) <= logLength;

Para evitar la retroalimentación innecesaria de los solucionadores, establezca la opción para el bucle externo y la solución de subproblema interno.Display'off'

lpopts = optimoptions('linprog','Display','off'); ipopts = optimoptions('intlinprog',lpopts);

Inicializar las variables para el bucle.

reducedCost = -inf; reducedCostTolerance = -0.0001; exitflag = 1;

Llama al loop.

while reducedCost < reducedCostTolerance && exitflag > 0     logprob = optimproblem('Description','Cut Logs');          % Create variables representing the number of each pattern used     x = optimvar('x', nPatterns, 1, 'LowerBound', 0);     % The objective is the number of logs used     logprob.Objective.logsUsed = sum(x);     % The constraint is that the cuts satisfy the demand     logprob.Constraints.Demand = patterns*x >= quantity;          [values,nLogs,exitflag,~,lambda] = solve(logprob,'options',lpopts);          if exitflag > 0         fprintf('Using %g logs\n',nLogs);         % Now generate a new pattern, if possible         subproblem.Objective = 1.0 - dot(lambda.Constraints.Demand,cuts);         [values,reducedCost,pexitflag] = solve(subproblem,'options',ipopts);         newpattern = round(values.cuts);         if double(pexitflag) > 0 && reducedCost < reducedCostTolerance             patterns = [patterns newpattern];             nPatterns = nPatterns + 1;         end     end end
Using 97.5 logs Using 92 logs Using 89.9167 logs Using 88.3 logs 

Ahora tiene la solución del problema de programación lineal. Para completar la solución, resuelva el problema de nuevo con los patrones finales, cambiando la variable de la solución al tipo entero.x Además, calcule los desechos, que es la cantidad de registros no utilizados (en pies) para cada patrón y para el problema como un todo.

if exitflag <= 0      disp('Error in column generation phase') else     x.Type = 'integer';     [values,logsUsed,exitflag] = solve(logprob,'options',ipopts);     if double(exitflag) > 0         values.x = round(values.x); % in case some values were not exactly integers         logsUsed = sum(values.x);         fprintf('Optimal solution uses %g logs\n', logsUsed);         totalwaste = sum((patterns*values.x - quantity).*lengthlist); % waste due to overproduction         for j = 1:size(values.x)             if values.x(j) > 0                 fprintf('Cut %g logs with pattern\n',values.x(j));                 for w = 1:size(patterns,1)                     if patterns(w,j) > 0                         fprintf('    %g cut(s) of length %d\n', patterns(w,j),lengthlist(w));                     end                 end                 wastej = logLength - dot(patterns(:,j),lengthlist); % waste due to pattern inefficiency                 totalwaste = totalwaste + wastej;             fprintf('    Waste of this pattern is %g\n',wastej);             end         end         fprintf('Total waste in this problem is %g.\n',totalwaste);     else          disp('Error in final optimization')     end end
Optimal solution uses 89 logs Cut 1 logs with pattern     3 cut(s) of length 12     Waste of this pattern is 4 Cut 15 logs with pattern     2 cut(s) of length 20     Waste of this pattern is 0 Cut 18 logs with pattern     1 cut(s) of length 8     2 cut(s) of length 16     Waste of this pattern is 0 Cut 36 logs with pattern     2 cut(s) of length 8     2 cut(s) of length 12     Waste of this pattern is 0 Cut 19 logs with pattern     2 cut(s) of length 12     1 cut(s) of length 16     Waste of this pattern is 0 Total waste in this problem is 28. 

Parte de los desechos se debe a la sobreproducción, porque el molino corta un registro en piezas de 3 12 pies, pero utiliza sólo uno. Parte de los desechos se debe a la ineficiencia del patrón, porque las piezas de 3 12 pies son de 4 pies de longitud total de 40 pies.

Referencias

[1] Ford, l. r., Jr. y d. r. Fulkerson. Ciencias de la gestión 5, 1958, PP. 97-101.A Suggested Computation for Maximal Multi-Commodity Network Flows.

[2] Gilmore, p. c., y r. e. Gomory. Investigación de operaciones 11, nº 6, 1963, PP. 863-888.A Linear Programming Approach to the Cutting Stock Problem--Part II.

Temas relacionados