В этом примере показано, как создать начальную точку для задачи оптимизации, которая назвала индексные переменные. Для именованных индексных переменных часто самый легкий способ задать начальную точку состоит в том, чтобы использовать 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.