Этот пример показывает, как настроить и решить смешано-целочисленную задачу линейного программирования. Задача состоит в том, чтобы найти оптимальные уровни производства и распределения между набором фабрик, складов и торговых точек. Для основанного на решателе подхода смотрите Фабрика, Склад, Модель распределения продаж: Основанная на решателе.
Сначала пример создает случайные местоположения для заводов, складов и торговых точек. Не стесняйтесь изменять параметр масштабирования , который масштабирует как размер сетки, в которой находятся производственные, так и распределительные сооружения, но также масштабирует количество этих объектов так, чтобы плотность объектов каждого типа на зону сетки была независимой от .
Для заданного значения параметра масштабирования , предположим, что существуют следующие:
фабрики
склады
торговые точки
Эти средства находятся на отдельных целочисленных точках сетки между 1 и в и направления. В порядок, что объекты имеют отдельные местоположения, вы требуете, чтобы . В этом примере примите , , , и .
Есть продукты, произведенная заводами. Бери .
Потребность в каждом продукте в торговой точке является . Потребность является количеством, которое может быть продано за определенный временной интервал. Одно из ограничений модели заключается в том, что потребность удовлетворяется, что означает, что система производит и распределяет именно количества в потребности.
На каждом заводе и на каждом складе существуют ограничения по емкости.
Производство продукта на заводе меньше, чем .
Вместимость склада является .
Количество продукта которые можно транспортировать со склада для торговой точки в интервале времени меньше, чем , где - скорость оборота продукта .
Предположим, что каждая торговая точка получает свои поставки всего с одного склада. Часть задачи заключается в определении самого дешевого отображения торговых точек на склады.
Стоимость транспортировки продуктов от завода до склада и от склада до торговой точки зависит от расстояния между объектами и от конкретного продукта. Если - расстояние между объектами и , затем стоимость доставки продукта между этими объектами находится расстояние, умноженное на стоимость транспортировки :
Расстояние в этом примере является расстоянием сетки, также известным как расстояние. Это сумма абсолютного различия в координаты и координаты.
Стоимость изготовления модуля продукта на заводе является .
Учитывая набор мест расположения объектов, а также требования и ограничения пропускной способности, найдите:
Уровень производства каждого продукта на каждом заводе
График распределения продуктов от заводов до складов
График распределения продуктов от складов до торговых точек
Эти количества должны обеспечивать удовлетворение спроса и минимизацию общих затрат. Кроме того, каждая торговая точка должна получать все свои продукты только с одного склада.
Переменные управления, означающие те, которые вы можете изменить в оптимизации,
= количество продукта который транспортируется с завода в склад
= двоичная переменная, принимающая значение 1, когда торговая точка связана со складом
Целевая функция для минимизации
Ограничения:
(мощность завода).
(спрос удовлетворяется).
(вместимость склада).
(каждая торговая точка связана с одним складом).
(неотрицательная продукция).
(двоичный ).
Переменные и появляются в функциях цели и ограничения линейно. Поскольку ограничивается целочисленными значениями, задачей является смешано-целочисленная линейная программа (MILP).
Установите значения , , , и параметры и сгенерируйте местоположения объектов.
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
-by- F
-by- W
. y
представляет двоичное распределение торговой точки на склад, S
-by- 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')
Черные * без зеленых линий представляют собой неиспользованные склады.