Создайте начальную точку для оптимизации с именованными индексными переменными

В этом примере показано, как создать начальную точку для задачи оптимизации, которая назвала индексные переменные. Для именованных индексных переменных часто самый легкий способ задать начальную точку состоит в том, чтобы использовать findindex функция.

Проблемой является проблема материально-технических ресурсов мультипериода, которая включает смешивающиеся сырые данные и усовершенствованные масла. Цель состоит в том, чтобы максимизировать прибыль, удовлетворяющую различным ограничениям на производство и мощности материально-технических ресурсов и на "твердость" нефтяных смешений. Эта проблема взята от Уильямса [1].

Описание проблемы

Проблема включает два типа нефти сырых овощей и три типа необработанной неовощной нефти, которую производитель может совершенствовать в пищевое масло. Производитель может совершенствовать до 200 тонн растительных масел и до 250 тонн неовощных масел в месяц. Производитель может сохранить 1 000 тонн каждой необработанной нефти, которая выгодна, потому что стоимость покупательных необработанных масел зависит от месяца, а также типа нефти. Названная "твердость" качества сопоставлена с каждой нефтью. Твердость смешанной нефти является линейно взвешенной твердостью составляющих масел.

Из-за обработки ограничений производитель ограничивает количество масел, усовершенствованных в любом месяце к не больше, чем три. Кроме того, если нефть усовершенствована за месяц, по крайней мере 20 тонн той нефти должны быть усовершенствованы. Наконец, если растительное масло усовершенствовано за месяц, то неовощная нефть 3 должна также быть усовершенствована.

Доход является константой для каждой тонны проданной нефти. Затраты являются стоимостью покупки масел, который варьируется нефтью и месяц, и существуют фиксированные затраты на тонну хранения каждой нефти в течение каждого месяца. Нет никакой стоимости для совершенствования нефти, но производитель не может сохранить очищенную нефть (это должно быть продано).

Введите проблемные данные

Создайте названные индексные переменные в течение периодов планирования и масел.

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

Создайте переменные параметрами использования и устройством хранения данных.

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

Задайте твердость необработанных масел как этот вектор.

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

Задайте затраты на необработанные масла как этот массив. Каждая строка массива представляет стоимость необработанных масел за месяц. Первая строка представляет затраты в январе, и последняя строка представляет затраты в июне.

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];

Создание переменных

Создайте эти переменные задачи:

  • продайте, количество каждой нефти, продаваемой каждый месяц

  • store, количество каждой нефти сохранено в конце каждого месяца

  • buy, количество каждой нефти покупается каждый месяц

Кроме того, чтобы составлять ограничения на количество масел, усовершенствованных и продаваемых каждый месяц и минимальное произведенное количество, создайте вспомогательную бинарную переменную induse это равняется 1 точно, когда нефть продается за месяц.

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);

Назовите общее количество нефти продаваемым каждый месяц produce.

produce = sum(sell,2);

Создайте цель

Чтобы создать целевую функцию для проблемы, вычислите доход и вычтите затраты на покупку и хранение масел.

Создайте задачу оптимизации для максимизации и включайте целевую функцию как Objective свойство.

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

Выражение цели довольно длинно. Если вам нравится, вы видите, что он использует showexpr(prob.Objective) команда.

Создайте ограничения

Проблема имеет несколько ограничений, которые необходимо установить.

Количество каждой нефти, сохраненной в июне, 500. Установите это ограничение при помощи нижних и верхних границ.

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

Производитель не может совершенствовать больше, чем maxuseveg растительное масло в любом месяце. Установите это и все последующие ограничения при помощи Выражений для Ограничений и уравнений.

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

Производитель не может совершенствовать больше, чем maxusenon неовощная нефть любой месяц.

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

Твердость смешанной нефти должна быть от hmin through hmax.

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

Количество каждой нефти, сохраненной в конце месяца, равно сумме в начале месяца, плюс купленная сумма, минус проданная сумма.

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

Если нефть усовершенствована вообще за месяц, по крайней мере, minuseraw из нефти должен быть усовершенствован и продан.

minuse = sell >= minuseraw*induse;

Убедитесь, что induse переменная равняется 1 точно, когда соответствующая нефть усовершенствована.

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

Производитель может продать не больше, чем maxnraw масла каждый месяц.

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

Если растительное масло усовершенствовано, нефтяной non3 должен также быть усовершенствован и продан.

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

Включайте ограничительные выражения в задаче.

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;

Решите задачу

Чтобы показать возможное различие между использованием начальной точки и не использованием того, установите опции не использовать эвристику. Затем решите задачу.

opts = optimoptions('intlinprog','Heuristics','none');
[sol1,fval1,exitstatus1,output1] = solve(prob,'options',opts)
Solving problem using intlinprog.
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.047522e+05.                                                    

Branch and Bound:

   nodes     total   num int        integer       relative                                          
explored  time (s)  solution           fval        gap (%)                                         
      19      0.10         1  -7.190185e+04   4.535003e+01                                          
      25      0.11         2  -7.205000e+04   4.505117e+01                                          
      25      0.11         3  -8.290000e+04   2.606702e+01                                          
      29      0.11         4  -8.775370e+04   1.909426e+01                                          
      40      0.12         5  -9.937870e+04   5.163142e+00                                          
      91      0.14         6  -9.987222e+04   4.643483e+00                                          
     105      0.15         7  -1.002139e+05   4.286718e+00                                          
     630      0.30         8  -1.002787e+05   2.283810e+00                                          
    1112      0.41         8  -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: 8
           numnodes: 1112
    constrviolation: 1.1867e-11
            message: 'Optimal solution found....'
             solver: 'intlinprog'

Используйте начальную точку

Для этой проблемы, с помощью начальной точки может сохранить итерации метода ветвей и границ. Создайте начальную точку правильных размерностей.

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

Установите начальную точку продавать только растительному маслу veg2 и неовощная нефть non3. Чтобы установить эту начальную точку соответственно, используйте findindex функция.

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

Удовлетворите максимальным овощным и неовощным ограничениям нефти.

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

Установите начальную точку не покупать нефть первый месяц.

x0.buy(1,:) = 0;

Удовлетворите initstockbal ограничение в течение первого месяца на основе начального хранилища 500 для каждого нефтяного типа и никакой покупки первый месяц и постоянное использование veg2 и non3.

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

Удовлетворите остающимся ограничениям баланса запаса stockbal при помощи 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];

Проверяйте, что начальная точка выполнима. Поскольку ограничения имеют различные размерности, устанавливают cellfun UniformOutput пара "имя-значение" к false при проверке infeasibilities.

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

Все infeasibilities являются нулем, который показывает, что начальная точка выполнима.

Повторно выполните проблему с помощью начальной точки.

[sol2,fval2,exitstatus2,output2] = solve(prob,x0,'options',opts)
Solving problem using intlinprog.
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.047522e+05.                                                    
                   Relative gap is 166.88%.                                                        

Branch and Bound:

   nodes     total   num int        integer       relative                                          
explored  time (s)  solution           fval        gap (%)                                         
      15      0.09         2  -7.190185e+04   4.535003e+01                                          
      21      0.11         3  -8.290000e+04   2.606702e+01                                          
      25      0.11         4  -8.775370e+04   1.909426e+01                                          
      30      0.11         5  -9.953889e+04   4.993907e+00                                          
      56      0.13         6  -9.982870e+04   4.689100e+00                                          
     138      0.16         7  -1.002787e+05   3.851839e+00                                          
    1114      0.40         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: 1114
    constrviolation: 1.7580e-12
            message: 'Optimal solution found....'
             solver: 'intlinprog'

На этот раз, 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 1114 branch-and-bound steps,
but using no initial point took 1112 steps.

Ссылка

[1] Уильямс, Х. Пол. Построение моделей в Математическом программировании. Четвертый выпуск. Дж. Вайли, Чичестер, Англия. Проблема 12.1, "Еда Manufacture1". 1999.

Смотрите также

|

Похожие темы

Для просмотра документации необходимо авторизоваться на сайте