Расположение объекта

Для заданного значения параметра масштабирования $$N$$предположим, что существуют следующие значения:

Эти средства находятся на отдельных целочисленных точках сетки между 1 и $$N$$ в $$$$$$$$направлениях x и y. Для того, чтобы объекты имели отдельные местоположения, требуется этот $$\mathrm{f+w+s\le 1}$$. В этом примере принимают $$N\mathrm{=}\mathrm{}$$20$$,\mathrm{f}\mathrm{=}\mathrm{}$$$$0,05\mathrm{,}\mathrm{w}\mathrm{}$$= 0,05 $$\mathrm{}\mathrm{и}$$s = 0,1.

Производство и распределение

Есть $$$$продукты P, изготовленные фабриками. Принять $$P\mathrm{=}\mathrm{}$$20.

Спрос на каждый продукт $$p$$ в торговой точке $$s$$ равен $$d(s,$$p). Потребность - это количество, которое может быть продано в интервале времени. Одним из ограничений модели является удовлетворение потребности, что означает, что система производит и распределяет именно те количества потребности.

На каждом заводе и на каждом складе существуют ограничения по мощности.

Предположим, что каждая торговая точка получает свои поставки только с одного склада. Отчасти проблема заключается в определении наиболее дешевого картирования торговых точек на склады.

Затраты

Стоимость транспортировки продукции с завода на склад и со склада на торговую точку зависит от расстояния между объектами и от конкретного продукта. Если $$\mathrm{dist}(a,$$b) - расстояние между $$\mathrm{объектами}$$ a $$и$$b, то стоимость транспортировки $$\mathrm{продукта}$$ p между этими объектами является расстоянием, умноженным на стоимость транспортировки $$\mathrm{tcost}$$(p):

Расстояние в этом примере - это расстояние сетки, также называемое $${}_{\mathrm{L1}}$$ расстоянием. Это сумма абсолютных разностей координат $$x$$ и $$y$$.

Стоимость изготовления единицы продукта $$p$$ на заводе $$f$$ составляет $$\mathrm{pcost}(f,$$p).

Проблема оптимизации

Учитывая набор местоположений объекта, а также требования и ограничения по мощности, найдите:

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

Переменные и уравнения для задачи оптимизации

Управляющие переменные, то есть переменные, которые можно изменить при оптимизации:

Целевой функцией для минимизации является

Ограничения:

$$\underset{}{}\mathrm{\sum wx}(p,f,w)\mathrm{\le pcap}$$(f, p) (производительность завода).

$$\underset{}{}\mathrm{\sum fx}(p,f,\underset{)}{w}\mathrm{=\sum s}(d(s,p)$$⋅y (s, w)) (спрос удовлетворяется).

$$\underset{}{}\underset{}{}\frac{\mathrm{\sum p\sum sd}(s,}{p)поворот}(p)\cdot y(s,w)$$≤wcap (w) (вместимость склада).

$$\underset{}{}\mathrm{\sum wy}(ы,w\mathrm{)}$$ = 1 (каждая торговая точка связана с одним складом).

$$x(p,f,\mathrm{w}$$) ≥0 (неотрицательное производство).

$$y(s,w)\mathrm{}\mathrm{}$$ϵ{0,1} ($$$$двоичный y).

Переменные $$x$$ и $$y$$ отображаются в функциях цели и ограничения линейно. Поскольку $$y$$ ограничен целочисленными значениями, проблема заключается в смешанно-целочисленной линейной программе (MILP).

Создать случайную проблему: Расположение объекта

Задайте значения $$$$$$$$$$$$$$$$параметров N, f, w и s и создайте местоположения оборудования.

rng(1) % for reproducibility
N = 20; % N from 10 to 30 seems to work. Choose large values with caution.
N2 = N*N;
f = 0.05; % density of factories
w = 0.05; % density of warehouses
s = 0.1; % density of sales outlets

F = floor(f*N2); % number of factories
W = floor(w*N2); % number of warehouses
S = floor(s*N2); % number of sales outlets

xyloc = randperm(N2,F+W+S); % unique locations of facilities
[xloc,yloc] = ind2sub([N N],xyloc);

Конечно, нереально брать случайные места для объектов. Этот пример предназначен для демонстрации методов решения, а не способов создания хороших местоположений объекта.

Постройте график объектов. Объекты 1 - F - заводы, F + 1 - F + W - склады, а F + W + 1 - F + W + S - торговые точки.

h = figure;
plot(xloc(1:F),yloc(1:F),'rs',xloc(F+1:F+W),yloc(F+1:F+W),'k*',...
    xloc(F+W+1:F+W+S),yloc(F+W+1:F+W+S),'bo');
lgnd = legend('Factory','Warehouse','Sales outlet','Location','EastOutside');
lgnd.AutoUpdate = 'off';
xlim([0 N+1]);ylim([0 N+1])

Создание случайных мощностей, затрат и потребностей

Создание случайных производственных затрат, мощностей, оборотов и потребностей.

P = 20; % 20 products

% Production costs between 20 and 100
pcost = 80*rand(F,P) + 20;

% Production capacity between 500 and 1500 for each product/factory
pcap = 1000*rand(F,P) + 500;

% Warehouse capacity between P*400 and P*800 for each product/warehouse
wcap = P*400*rand(W,1) + P*400;

% Product turnover rate between 1 and 3 for each product
turn = 2*rand(1,P) + 1;

% Product transport cost per distance between 5 and 10 for each product
tcost = 5*rand(1,P) + 5;

% Product demand by sales outlet between 200 and 500 for each
% product/outlet
d = 300*rand(S,P) + 200;

Эти случайные потребности и возможности могут привести к неосуществимым проблемам. Другими словами, иногда спрос превышает производственные и складские ограничения. Если изменить некоторые параметры и получить неосуществимую проблему, во время решения вы получите exitflag -2.

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

Чтобы начать определение проблемы, создайте массивы расстояний distfw(i,j) и distsw(i,j).

distfw = zeros(F,W); % Allocate matrix for factory-warehouse distances
for ii = 1:F
    for jj = 1:W
        distfw(ii,jj) = abs(xloc(ii) - xloc(F + jj)) + abs(yloc(ii) ...
            - yloc(F + jj));
    end
end

distsw = zeros(S,W); % Allocate matrix for sales outlet-warehouse distances
for ii = 1:S
    for jj = 1:W
        distsw(ii,jj) = abs(xloc(F + W + ii) - xloc(F + jj)) ...
            + abs(yloc(F + W + ii) - yloc(F + jj));
    end
end

Создайте переменные для задачи оптимизации. x представляет производство, непрерывную переменную, с измерением Pоколо-Fоколо-W. y представляет двоичное распределение торговой точки на склад, Sоколо-W переменная.

x = optimvar('x',P,F,W,'LowerBound',0);
y = optimvar('y',S,W,'Type','integer','LowerBound',0,'UpperBound',1);

Теперь создайте зависимости. Первое ограничение - это ограничение мощности для производства.

capconstr = sum(x,3) <= pcap';

Следующим ограничением является удовлетворение спроса в каждой торговой точке.

demconstr = squeeze(sum(x,2)) == d'*y;

На каждом складе существует ограничение мощности.

warecap = sum(diag(1./turn)*(d'*y),1) <= wcap';

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

salesware = sum(y,2) == ones(S,1);

Создание проблемы и цели

Создайте проблему оптимизации.

factoryprob = optimproblem;

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

objfun1 = sum(sum(sum(x,3).*(pcost'),2),1);

Вторая часть - сумма транспортных расходов с заводов на склады.

objfun2 = 0;
for p = 1:P
    objfun2 = objfun2 + tcost(p)*sum(sum(squeeze(x(p,:,:)).*distfw));
end

Третья часть - это сумма транспортных затрат от складов до торговых точек.

r = sum(distsw.*y,2); % r is a length s vector
v = d*(tcost(:));
objfun3 = sum(v.*r);

Целевой функцией для минимизации является сумма трех частей.

factoryprob.Objective = objfun1 + objfun2 + objfun3;

Включите в проблему ограничения.

factoryprob.Constraints.capconstr = capconstr;
factoryprob.Constraints.demconstr = demconstr;
factoryprob.Constraints.warecap = warecap;
factoryprob.Constraints.salesware = salesware;

Решить проблему

Отключите итеративное отображение, чтобы не получать сотни строк выходных данных. Включите функцию графика для контроля выполнения решения.

opts = optimoptions('intlinprog','Display','off','PlotFcn',@optimplotmilp);

Вызовите решатель, чтобы найти решение.

[sol,fval,exitflag,output] = solve(factoryprob,'options',opts);

if isempty(sol) % If the problem is infeasible or you stopped early with no solution
    disp('The solver did not return a solution.')
    return % Stop the script because there is nothing to examine
end

Анализ решения

Проверьте флаг выхода и несходимость решения.

exitflag

exitflag = 
    OptimalSolution

infeas1 = max(max(infeasibility(capconstr,sol)))

infeas1 = 9.0949e-13

infeas2 = max(max(infeasibility(demconstr,sol)))

infeas2 = 8.0718e-12

infeas3 = max(infeasibility(warecap,sol))

infeas3 = 0

infeas4 = max(infeasibility(salesware,sol))

infeas4 = 2.4425e-15

Круглый y часть решения должна быть в точности целочисленной. Чтобы понять, почему эти переменные могут быть не совсем целыми числами, см. Некоторые «целочисленные» решения не целые числа.

sol.y = round(sol.y); % get integer solutions

Сколько торговых точек связано с каждым складом? Обратите внимание, что в этом случае некоторые склады имеют 0 связанных торговых точек, что означает, что склады не используются в оптимальном решении.

outlets = sum(sol.y,1)

outlets = 1×20

     2     0     3     2     2     2     3     2     3     2     1     0     0     3     4     3     2     3     2     1

Постройте график соединения между каждой торговой точкой и ее складом.

figure(h);
hold on
for ii = 1:S
    jj = find(sol.y(ii,:)); % Index of warehouse associated with ii
    xsales = xloc(F+W+ii); ysales = yloc(F+W+ii);
    xwarehouse = xloc(F+jj); ywarehouse = yloc(F+jj);
    if rand(1) < .5 % Draw y direction first half the time
        plot([xsales,xsales,xwarehouse],[ysales,ywarehouse,ywarehouse],'g--')
    else % Draw x direction first the rest of the time
        plot([xsales,xwarehouse,xwarehouse],[ysales,ysales,ywarehouse],'g--')
    end
end
hold off

title('Mapping of sales outlets to warehouses')

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