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.

Cree un punto inicial para la optimización con variables de índice guardadas

En este ejemplo se muestra cómo crear un punto inicial para un problema de optimización que tiene las variables de índice con nombre. Para las variables de índice con nombre, a menudo la manera más fácil de especificar un punto inicial es usar la función.findindex

El problema es un problema de inventario de varios períodos que implica mezclar aceites crudos y refinados. El objetivo es maximizar el beneficio sujeto a diversas limitaciones en la producción y las capacidades de inventario y en la "dureza" de las mezclas de petróleo. Este problema se toma de Williams [1].

Descripción del problema

El problema involucra dos tipos de aceite vegetal crudo y tres tipos de aceite no vegetal crudo que un fabricante puede refinar en aceite comestible. El fabricante puede refinar hasta 200 toneladas de aceites vegetales, y hasta 250 toneladas de aceites no vegetales al mes. El fabricante puede almacenar 1000 toneladas de cada aceite crudo, lo que es beneficioso porque el costo de la compra de aceites crudos depende del mes, así como el tipo de aceite. Una cualidad llamada "dureza" se asocia con cada aceite. La dureza del aceite mezclado es la dureza ponderada linealmente de los aceites constituyentes.

Debido a las limitaciones de procesamiento, el fabricante restringe el número de aceites refinados en un mes a no más de tres. Además, si un aceite se refina en un mes, al menos 20 toneladas de ese aceite deben ser refinados. Por último, si se refina un aceite vegetal en un mes, también se debe refinar el aceite no vegetal 3.

Los ingresos son una constante para cada tonelada de petróleo vendido. Los costos son el costo de la compra de los aceites, que varía según el aceite y el mes, y hay un costo fijo por tonelada de almacenamiento de cada aceite para cada mes. No hay costo para refinar un aceite, pero el fabricante no puede almacenar aceite refinado (debe ser vendido).

Introduzca los datos del problema

Cree variables de índice con nombre para los períodos de planificación y los aceites.

months = {'January','February','March','April','May','June'}; oils = {'veg1','veg2','non1','non2','non3'}; vegoils = {'veg1','veg2'}; nonveg = {'non1','non2','non3'};

Cree variables con parámetros de almacenamiento y uso.

maxstore = 1000; % Maximum storage of each type of oil maxuseveg = 200; % Maximum vegetable oil use maxusenon = 250; % Maximum nonvegetable oil use minuseraw = 20; % Minimum raw oil use maxnraw = 3; % Maximum number of raw oils in a blend saleprice = 150; % Sale price of refined and blended oil storecost = 5; % Storage cost per period per oil quantity stockend = 500; % Stock at beginning and end of problem hmin = 3; % Minimum hardness of refined oil hmax = 6; % Maximum hardness of refined oil

Especifique la dureza de los aceites crudos como este vector.

h = [8.8,6.1,2,4.2,5.0];

Especifique los costes de los aceites crudos como esta matriz. Cada fila de la matriz representa el costo de los aceites crudos en un mes. La primera fila representa los costos en enero y la última fila representa los costos en junio.

costdata = [... 110 120 130 110 115 130 130 110  90 115 110 140 130 100  95 120 110 120 120 125 100 120 150 110 105  90 100 140  80 135];

Crear variables

Cree estas variables problemáticas:

  • vender, la cantidad de cada aceite vendido cada mes

  • , la cantidad de cada aceite almacenado al final de cada messtore

  • , la cantidad de cada aceite comprado cada mesbuy

Además, para tener en cuenta las restricciones en el número de aceites refinados y vendidos cada mes y la cantidad mínima producida, crear una variable binaria auxiliar que es 1 exactamente cuando se vende un aceite en un mes.induse

sell = optimvar('sell', months, oils, 'LowerBound', 0); buy = optimvar('buy', months, oils, 'LowerBound', 0); store = optimvar('store', months, oils, 'LowerBound', 0, 'UpperBound', maxstore);  induse = optimvar('induse', months, oils, 'Type', 'integer', ...     'LowerBound', 0, 'UpperBound', 1);

Asigne un nombre a la cantidad total de aceite vendido cada mes.produce

produce = sum(sell,2);

Crear objetivo

Para crear la función objetiva para el problema, calcule los ingresos y reste los costos de compra y almacenamiento de aceites.

Cree un problema de optimización para la maximización e incluya la función objetiva como la propiedad.Objective

prob = optimproblem('ObjectiveSense', 'maximize'); prob.Objective = sum(saleprice*produce) - sum(sum(costdata.*buy)) - sum(sum(storecost*store));

La expresión objetiva es bastante larga. Si lo desea, puede verlo mediante el comando.showexpr(prob.Objective)

Crear restricciones

El problema tiene varias restricciones que debe establecer.

La cantidad de cada aceite almacenado en junio es de 500. Establezca esta restricción utilizando los límites inferior y superior.

store('June', :).LowerBound = 500; store('June', :).UpperBound = 500;

El fabricante no puede refinar más que el aceite vegetal en cualquier mes.maxuseveg Establezca esta y todas las restricciones subsiguientes mediante.Expresiones para restricciones

vegoiluse = sell(:, vegoils); vegused = sum(vegoiluse, 2) <= maxuseveg;

El fabricante no puede refinar más que el aceite no vegetal en cualquier mes.maxusenon

nonvegoiluse = sell(:,nonveg); nonvegused = sum(nonvegoiluse,2) <= maxusenon;

La dureza del aceite mezclado debe ser de.hmin through hmax

hardmin = sum(repmat(h, 6, 1).*sell, 2) >= hmin*produce; hardmax = sum(repmat(h, 6, 1).*sell, 2) <= hmax*produce;

La cantidad de cada aceite almacenado al final del mes es igual a la cantidad a principios de mes, más la cantidad comprada, menos la cantidad vendida.

initstockbal = 500 + buy(1, :) == sell(1, :) + store(1, :); stockbal = store(1:5, :) + buy(2:6, :) == sell(2:6, :) + store(2:6, :);

Si se refina un aceite en un mes, al menos el aceite debe ser refinado y vendido.minuseraw

minuse = sell >= minuseraw*induse;

Asegúrese de que la variable es 1 exactamente cuando se refina el aceite correspondiente.induse

maxusev = sell(:, vegoils) <= maxuseveg*induse(:, vegoils); maxusenv = sell(:, nonveg) <= maxusenon*induse(:, nonveg);

El fabricante no puede vender más que aceites cada mes.maxnraw

maxnuse = sum(induse, 2) <= maxnraw;

Si se refina un aceite vegetal, también se debe refinar y vender el aceite.non3

deflogic1 = sum(induse(:,vegoils), 2) <= induse(:,'non3')*numel(vegoils);

Incluya las expresiones de restricción en el problema.

prob.Constraints.vegused = vegused; prob.Constraints.nonvegused = nonvegused; prob.Constraints.hardmin = hardmin; prob.Constraints.hardmax = hardmax; prob.Constraints.initstockbal = initstockbal; prob.Constraints.stockbal = stockbal; prob.Constraints.minuse = minuse; prob.Constraints.maxusev = maxusev; prob.Constraints.maxusenv = maxusenv; prob.Constraints.maxnuse = maxnuse; prob.Constraints.deflogic1 = deflogic1;

Resuelve el problema

Para mostrar la diferencia final entre usar un punto inicial y no usar uno, establezca las opciones para no usar la heurística. A continuación, resuelva el problema.

opts = optimoptions('intlinprog','Heuristics','none'); [sol1,fval1,exitstatus1,output1] = solve(prob,'options',opts)
LP:                Optimal objective value is -1.075130e+05.                                          Cut Generation:    Applied 41 Gomory cuts, 2 cover cuts,                                                                1 mir cut, and 1 clique cut.                                                                         Lower bound is -1.046990e+05.                                                      Branch and Bound:     nodes     total   num int        integer       relative                                           explored  time (s)  solution           fval        gap (%)                                                28      0.28         1  -9.945833e+04   4.818992e+00                                                 70      0.32         2  -9.998889e+04   4.262813e+00                                                114      0.36         3  -1.002787e+05   3.891142e+00                                               1086      0.73         3  -1.002787e+05   0.000000e+00                                            Optimal solution found.  Intlinprog stopped 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). 
sol1 = struct with fields:
       buy: [6x5 double]
    induse: [6x5 double]
      sell: [6x5 double]
     store: [6x5 double]

fval1 = 1.0028e+05 
exitstatus1 =      OptimalSolution  
output1 = struct with fields:
        relativegap: 0
        absolutegap: 0
      numfeaspoints: 3
           numnodes: 1086
    constrviolation: 1.5111e-11
            message: 'Optimal solution found....'
             solver: 'intlinprog'

Utilice el punto inicial

Para este problema, el uso de un punto inicial puede guardar iteraciones ramifican y enlazadas. Cree un punto inicial de las cotas correctas.

x0.buy = zeros(size(buy)); x0.induse = zeros(size(induse)); x0.store = zeros(size(store)); x0.sell = zeros(size(sell));

Establecer el punto inicial para vender sólo aceite vegetal y aceite no vegetal.veg2non3 Para establecer este punto inicial apropiadamente, utilice la función.findindex

numMonths = size(induse,1); [idxMonths,idxOils] = findindex(induse,1:numMonths,{'veg2','non3'}); x0.induse(idxMonths,idxOils) = 1;

Satisfaga las restricciones máximas de aceite vegetal y no vegetal.

x0.sell(:,idxOils) = repmat([200,250],numMonths,1)
x0 = struct with fields:
       buy: [6x5 double]
    induse: [6x5 double]
     store: [6x5 double]
      sell: [6x5 double]

Establezca el punto inicial para no comprar aceite el primer mes.

x0.buy(1,:) = 0;

Satisfaga la restricción del primer mes basada en el almacén inicial de 500 para cada tipo de aceite, y no compre el primer mes, y el uso constante de y.initstockbalveg2non3

x0.store(1,:) = [500 300 500 500 250];

Satisfaga las restricciones de balance de existencias restantes utilizando la función.findindex

[idxMonths,idxOils] = findindex(store,2:6,{'veg2'}); x0.store(idxMonths,idxOils) = [100;0;0;0;500];  [idxMonths,idxOils] = findindex(store,2:6,{'veg1','non1','non2'}); x0.store(idxMonths,idxOils) =  500;  [idxMonths,idxOils] = findindex(store,2:6,{'non3'}); x0.store(idxMonths,idxOils) = [0;0;0;0;500];  [idxMonths,idxOils] = findindex(buy,2:6,{'veg2'}); x0.buy(idxMonths,idxOils) = [0;100;200;200;700];  [idxMonths,idxOils] = findindex(buy,2:6,{'non3'}); x0.buy(idxMonths,idxOils) = [0;250;250;250;750];

Compruebe que el punto inicial es factible. Dado que las restricciones tienen dimensiones diferentes, establezca el par nombre-valor en cuando se verificando las invalbilidades.cellfunUniformOutputfalse

inf{1} = infeasibility(vegused,x0); inf{2} = infeasibility(nonvegused,x0); inf{3} = infeasibility(hardmin,x0); inf{4} = infeasibility(hardmax,x0); inf{5} = infeasibility(initstockbal,x0); inf{6} = infeasibility(stockbal,x0); inf{7} = infeasibility(minuse,x0); inf{8} = infeasibility(maxusev,x0); inf{9} = infeasibility(maxusenv,x0); inf{10} = infeasibility(maxnuse,x0); inf{11} = infeasibility(deflogic1,x0); allinfeas = cellfun(@max,inf,'UniformOutput',false); anyinfeas = cellfun(@max,allinfeas); disp(anyinfeas)
     0     0     0     0     0     0     0     0     0     0     0 

Todas las infactibilidades son cero, lo que demuestra que el punto inicial es factible.

Vuelva a ejecutar el problema utilizando el punto inicial.

[sol2,fval2,exitstatus2,output2] = solve(prob,x0,'options',opts)
LP:                Optimal objective value is -1.075130e+05.                                          Cut Generation:    Applied 41 Gomory cuts, 2 cover cuts,                                                                1 mir cut, and 1 clique cut.                                                                         Lower bound is -1.046990e+05.                                                                        Relative gap is 166.74%.                                                          Branch and Bound:     nodes     total   num int        integer       relative                                           explored  time (s)  solution           fval        gap (%)                                                28      0.30         2  -9.945833e+04   4.818992e+00                                                 66      0.34         3  -9.987222e+04   4.384608e+00                                                159      0.41         4  -9.996667e+04   4.120028e+00                                                166      0.41         5  -1.001917e+05   3.886209e+00                                                249      0.44         6  -1.002139e+05   2.927655e+00                                                408      0.52         7  -1.002787e+05   2.538777e+00                                               1107      0.77         7  -1.002787e+05   0.000000e+00                                            Optimal solution found.  Intlinprog stopped 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). 
sol2 = struct with fields:
       buy: [6x5 double]
    induse: [6x5 double]
      sell: [6x5 double]
     store: [6x5 double]

fval2 = 1.0028e+05 
exitstatus2 =      OptimalSolution  
output2 = struct with fields:
        relativegap: 0
        absolutegap: 0
      numfeaspoints: 7
           numnodes: 1107
    constrviolation: 3.6096e-12
            message: 'Optimal solution found....'
             solver: 'intlinprog'

Esta vez, tomó menos pasos en rama y enlazado para encontrar la solución.solve

fprintf(['Using the initial point took %d branch-and-bound steps,\nbut ',...     'using no initial point took %d steps.'],output2.numnodes,output1.numnodes)
Using the initial point took 1107 branch-and-bound steps, but using no initial point took 1086 steps. 

Referencia

[1] Williams, H. Paul. Cuarta edición.Model Building in Mathematical Programming. J. Wiley, Chichester, Inglaterra. Problema 12,1, "Food Manufacture1." 1999.

Consulte también

|

Temas relacionados