这个例子展示了如何建立和解决一个混合整数线性规划问题。问题是在一组工厂、仓库和销售网点之间找到最优的生产和分销水平。关于基于问题的方法,请参见工厂,仓库,销售分配模型:基于问题的.
该示例首先为工厂、仓库和销售网点生成随机位置。可以随意修改缩放参数 ,它既可以缩放生产和配送设施所在的网格的大小,也可以缩放这些设施的数量,以便每个网格区域内每种类型的设施密度是独立的 .
对于给定的缩放参数值 ,假设有以下情况:
工厂
仓库
销售网点
这些设施位于1和之间的单独整数网格点上 在 和 的方向。为了让这些设施有单独的位置,你需要这样做 .在本例中,取 , , , .
有 下载188bet金宝搏工厂生产的产品。取 .
每一种产品的需求 在销售部门 是 .需求是一段时间内可以出售的数量。模型的一个约束条件是需求得到满足,这意味着系统生产和分配的数量恰好满足需求。
每个工厂和每个仓库都有容量限制。
产品的生产 在工厂 小于 .
仓库容量 是 .
产品数量 可以从仓库运输 给一个销售网点的时间间隔小于 ,在那里 产品的周转率是多少 .
假设每个销售网点只从一个仓库接收供应品。问题的一部分是确定销售网点到仓库的最便宜映射。
从工厂到仓库以及从仓库到销售点运输产品的成本取决于下载188bet金宝搏设备之间的距离,以及具体的产品。如果 设施之间的距离如何 和 ,然后是产品的运输成本 这些设施之间的距离乘以运输成本 :
本例中的距离是网格距离,也称为 距离。它是绝对值差的和 坐标和 坐标。
生产一单位产品的成本 在工厂 是 .
给定一组设施位置,以及需求和能力限制,发现:
每个工厂每种产品的生产水平
产品从工厂到仓库的分配时间表下载188bet金宝搏
产品从仓库到销售点的分配时间表下载188bet金宝搏
这些数量必须确保满足需求和总成本最小化。而且,每个销售网点必须从一个仓库接收所有产品。下载188bet金宝搏
控制变量,也就是你可以在优化过程中改变的变量
产品的数量 那是从工厂运来的 到仓库
=一个值为1的二元变量 与仓库相关
最小化的目标函数为
的约束
(工厂)的能力。
(满足需求)。
(仓库)的能力。
(每个销售网点对应一个仓库)。
(非负生产)。
(二进制 ).
的变量 和 线性地出现在目标函数和约束函数中。因为 问题是一个混合整数线性规划(MILP)。
的值 , , , 参数,并生成设施位置。
rng (1)%的再现性N = 20;% N从10到30似乎有效。谨慎选择大的值。N2 = N * N;f = 0.05;工厂密度%w = 0.05;仓库密度%s = 0.1;销售网点密度%F =地板(F * N2);%工厂数量W =地板(W * N2);%仓库数量S =地板(S * N2);%销售网点数量xyloc = randperm (N2, F + W + S);独特的设施位置[xloc,yloc] = ind2sub([N N],xyloc);
当然,随机选择设施地点是不现实的。本示例旨在展示解决方案技术,而不是如何生成良好的设施位置。
情节的设施。设施1到F是工厂,F+1到F+W是仓库,F+W+1到F+W+S是销售网点。
h =图;情节(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),“波”);lgnd =传奇(“工厂”,“仓库”,“销售渠道”,“位置”,“EastOutside”);lgnd。自动更新=“关闭”;xlim ([0 N + 1]); ylim ([0 N + 1])
产生随机的生产成本、产能、周转率和需求。
P = 20;% 20产下载188bet金宝搏品%生产成本在20至100之间pcost = 80*rand(F,P) + 20;%每个产品/工厂的生产能力在500到1500之间pcap = 1000*rand(F,P) + 500;%每个产品/仓库在P*400和P*800之间的仓库容量wcap = P*400*rand(W,1) + P*400;%每个产品的周转率在1到3之间= 1 *rand(1,P) + 1;%每件产品的运输成本在5到10之间tcost = 5*rand(1,P) + 5;%各销售网点的产品需求在200 - 500之间%的产品/出口d = 300*rand(S,P) + 200;
这些随机的需求和能力可能导致不可行的问题。换句话说,有时需求超过了生产和仓库容量的限制。如果你改变一些参数,得到一个不可行的问题,在解决过程中,你将得到一个退出标志-2。
目标函数向量obj
在intlincon
由变量的系数组成
和
.所以很自然地F P * * W + S * W
系数obj
.
一种生成系数的方法是从a开始P-by-F-by-W
数组其中obj1
为
系数,S-by-W
数组methoda
为
系数。然后将这些数组转换为两个向量,并将它们组合成obj
通过调用
obj =[其中obj1 (:); methoda ()):;
其中obj1 = 0 (P, F, W);%分配数组methoda = 0 (S, W);
在生成目标和约束向量和矩阵的过程中,我们生成 数组或 数组,然后将结果转换为向量。
要开始生成输入,请生成距离数组distfw (i, j)
和distsw (i, j)
.
distfw = 0 (F, W);按工厂-仓库距离分配矩阵为2 = 1: F为jj = 1:W disfw (ii,jj) = abs(xloc(ii) - xloc(F + jj)) + abs(yloc(ii))...- yloc(F + jj);结束结束distsw = 0 (S, W);%分配销售网点-仓库距离矩阵为2 = 1: S为jj = 1:W dissw (ii,jj) = abs(xloc(F + W + ii) - xloc(F + jj))...+ abs(yloc(F + W + ii) - yloc(F + jj));结束结束
生成其中obj1
和methoda
.
为2 = 1: P为jj = 1: F为tcost(ii) = tcost(ii)* disfw (jj,kk);结束结束结束为2 = 1: S为jj = 1: W methoda (ii, jj) = distsw (ii, jj) *总和(d (ii):)。* tcost);结束结束
将这些元素合并成一个向量。
obj =[其中obj1 (:); methoda ()):;% obj是目标函数向量
现在创建约束矩阵。
每个线性约束矩阵的宽度就是矩阵的长度obj
向量。
matwid =长度(obj);
有两种类型的线性不等式:生产能力约束和仓库容量约束。
有F P *
生产能力的限制W
仓库容量约束。约束矩阵是非常稀疏的,在1%非零的阶上,所以使用稀疏矩阵可以节省内存。
Aineq = spalloc(P*F + W,matwid,P*F*W + S*W);%分配稀疏的Aeqbineq = 0 (P*F + W,1);%分配bineq为满方便大小的零矩阵:clearer1 = 0(大小(其中obj1));clearer12 = clearer1 (:);clearer2 = 0(大小(methoda));clearer22 = clearer2 (:);首先是生产能力的限制counter = 1;为2 = 1: F为jj = 1:P xtemp = clearer1;xtemp (jj,二世:)= 1;合计每个产品和工厂的仓库xtemp =稀疏([xtemp (:); clearer22]);转换为稀疏Aineq(柜台:)= xtemp ';%填写行bineq(柜台)= pcap (ii, jj);Counter = Counter + 1;结束结束现在仓库容量有限vj = 0(年代,1);%的乘数为jj = 1:S vj(jj) = sum(d(jj,:)./turn);% P个元素的和结束为ii = 1:W xtemp = clearer2;xtemp(:,(二)= vj;xtemp =稀疏([clearer12; xtemp (:)));转换为稀疏Aineq(柜台:)= xtemp ';%填写行bineq(柜台)= wcap (ii);Counter = Counter + 1;结束
有两种类型的线性等式约束:满足需求的约束和每个销售网点对应一个仓库的约束。
q = spalloc(P*W +S,matwid,P*W*(F+S) +S *W);%分配为稀疏q = 0 (P*W + S,1);%将vector分配为fullcounter = 1;%满足需求:为2 = 1: P为jj = 1:W xtemp = clearer1;xtemp(二世:jj) = 1;xtemp2 = clearer2;xtemp2 (:, jj) = - d(:,(二);xtemp =稀疏([xtemp (:); xtemp2()):”);%更改为稀疏行Aeq(计数器:)= xtemp;%填写行Counter = Counter + 1;结束结束%每个销售网点只有一个仓库:为ii = 1:S xtemp = clearer2;xtemp (ii):) = 1;xtemp =稀疏([clearer12; xtemp()):”);%更改为稀疏行Aeq(计数器:)= xtemp;%填写行说真的(柜台)= 1;Counter = Counter + 1;结束
整数变量是来自长度(其中obj1) + 1
到最后。
intcon F = P * * W + 1:长度(obj);
上界是长度(其中obj1) + 1
到最后也一样。
磅= 0(长度(obj), 1);乌兰巴托=正(长度(obj), 1);乌兰巴托(P F * * W + 1:结束)= 1;
关闭迭代显示,这样就不会得到几百行输出。包含一个绘图功能来监视解决方案的进度。
选择= optimoptions (“intlinprog”,“显示”,“关闭”,“PlotFcn”, @optimplotmilp);
你生成了所有的求解器输入。调用求解器来找到解决方案。
(解决方案,fval、exitflag、输出)= intlinprog (obj, intcon...Aineq、bineq Aeq,说真的,磅,乌兰巴托,选择);
如果isempty(解决方案)如果问题不可行,或者你因为没有解决方案而提前停止disp (“intlinprog没有返回一个解决方案。”)返回%停止脚本,因为没有要检查的内容结束
解决方案是可行的,在给定的公差范围内。
exitflag
exitflag = 1
infeas1 = max(Aineq*solution - bineq)
infeas1 = 8.2991 e-12
infeas2 =范数(Aeq*solution - beq,Inf)
infeas2 = 1.6428 e-11
检查整数部分是否真的是整数,或者是否足够接近,可以将它们四舍五入。要理解为什么这些变量可能不是整数,请参见一些“整数”解不是整数金宝搏官方网站.
diffint = norm(solution(intcon) - round(solution(intcon)),Inf)
diffint = 1.1990 e-13
有些整数变量不是精确的整数,但都非常接近。整型变量。
解决方案(intcon) =圆(解决方案(intcon));
检查四舍五入解的可行性,以及目标函数值的变化情况。
infeas1 = max(Aineq*solution - bineq)
infeas1 = 8.2991 e-12
infeas2 =范数(Aeq*solution - beq,Inf)
infeas2 = 5.8435 e-11
diff舍= norm(fval - obj(:)'*solution,Inf)
diffrounding = 1.8626 e-08
解决方案的四舍五入并没有明显改变其可行性。
您可以通过将解决方案重新塑造到其原始维度来最容易地检查解决方案。
solution1 =解决方案(1:F P * * W);%连续变量solution2 =解决方案(intcon);%整数变量solution1 =重塑(solution1 P F, W);solution2 =重塑(solution2 S W);
例如,每个仓库有多少销售网点?请注意,在本例中,有些仓库有0个关联出口,这意味着在最佳解决方案中没有使用这些仓库。
媒体=总和(solution2, 1)销售网点的总和
媒体=1×203 0 3 2 2 2 3 3 3 1 1 0 0 3 4 3 2 3 2 2 1
绘制每个销售网点与仓库之间的联系图。
图(h);持有在为ii = 1:S jj = find(solution2(ii,:));与ii相关的仓库指数%xsales = xloc (F + W + 2);ysales = yloc (F + W + 2);xwarehouse = xloc (F + jj);ywarehouse = yloc (F + jj);如果兰特(1)< 0。5前半段时间画y方向情节([xsales、xsales xwarehouse], [ysales、ywarehouse ywarehouse),“g——”)其他的%其余时间先画x方向情节([xsales、xwarehouse xwarehouse], [ysales、ysales ywarehouse),“g——”)结束结束持有从标题(“销售网点到仓库的映射”)
没有绿线的黑色*表示未使用的仓库。