Фабрика, склад, модель выделения продаж: основанный на проблеме

В этом примере показано, как настроить и решить смешано-целочисленную задачу линейного программирования. Проблема состоит в том, чтобы найти оптимальные уровни производства и распределения среди набора фабрик, складов и торговых точек. Для основанного на решателе подхода смотрите Фабрику, Склад, Модель Выделения Продаж: основанный на решателе.

Пример сначала генерирует случайные местоположения для фабрик, склады и торговые точки. Не стесняйтесь изменять масштабный коэффициент N, который масштабирует и размер сетки, в которой находятся производственные объекты и распределительные сети, но также и масштабирует количество этих средств так, чтобы плотность средств каждого типа на область сетки была независима от N.

Местоположения средства

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

  • fN2 фабрики

  • wN2 склады

  • sN2 торговые точки

Эти средства находятся на отдельных целочисленных узлах решетки между 1 и N в x и y направления. Чтобы средства имели отдельные местоположения, вы требуете этого f+w+s1. В этом примере взять N=20, f=0.05, w=0.05, и s=0.1.

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

Существуют P продукты сделаны фабриками. Взять P=20.

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

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

  • Производство продукта p на фабрике f меньше pcap(f,p).

  • Способность склада w wcap(w).

  • Сумма продукта p это может быть транспортировано со склада w к торговой точке во временном интервале меньше turn(p)*wcap(w), где turn(p) текучесть кадров продукта p.

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

Затраты

Стоимость переноса продуктов от фабрики до склада, и от склада до торговой точки, зависит от расстояния между средствами, и на конкретном продукте. Если dist(a,b) расстояние между средствами a и b, затем стоимость поставки продукта p между этими средствами времена расстояния стоимость транспортировки tcost(p):

dist(a,b)*tcost(p).

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

Стоимость создания модуля продукта p на фабрике f pcost(f,p).

Задача оптимизации

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

  • Производственный уровень каждого продукта на каждой фабрике

  • Расписание распределения для продуктов от фабрик до складов

  • Расписание распределения для продуктов от складов до торговых точек

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

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

Контрольные переменные, означая тех, которых можно изменить в оптимизации,

  • x(p,f,w) = сумма продукта p это транспортируется от фабрики f в склад w

  • y(s,w) = бинарное переменное принимающее значение 1, когда торговая точка s сопоставлен со складом w

Целевая функция, чтобы минимизировать

fpwx(p,f,w)(pcost(f,p)+tcost(p)dist(f,w))

+swp(d(s,p)tcost(p)dist(s,w)y(s,w)).

Ограничения

wx(p,f,w)pcap(f,p) (способность фабрики).

fx(p,f,w)=s(d(s,p)y(s,w)) (требование соблюдается).

psd(s,p)turn(p)y(s,w)wcap(w) (способность склада).

wy(s,w)=1 (каждая торговая точка сопоставляет в один склад).

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

y(s,w)ϵ{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])

Figure contains an axes. The axes contains 3 objects of type line. These objects represent Factory, Warehouse, Sales outlet.

Сгенерируйте случайные мощности, затраты и требования

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

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- WY представляет бинарное выделение торговой точки в склад, 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);

Figure Optimization Plot Function contains an axes. The axes with title Best objective: 3.0952e+07, Relative gap: 0. contains 4 objects of type line. These objects represent Root LB, Cuts LB, Heuristics UB, New Solution.

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

Figure contains an axes. The axes with title Mapping of sales outlets to warehouses contains 43 objects of type line. These objects represent Factory, Warehouse, Sales outlet.

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

Похожие темы

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