《车辆调度问题》由会员分享，可在线阅读，更多相关《车辆调度问题（11页珍藏版）》请在金锄头文库上搜索。
1、车辆调度问题设某车队有8辆车，存放在不同的地点，队长要派出其中5辆到5个工地去运货。各车从存放处调到装货地点所需费用列于下页表，问应选哪5辆车调到何处去运货，才能使各车从车所在地点调到装货地点所需的总费用最少？车地点123456781302518322719222622931191821203019328293019192223264293019242519182152120181716141618functionsumw=kuhngong(A)n=size(A,1);w=A;l=zeros(n,2);fori=1:nforj=1:nifl(i,1)tempal=temp;ifufprintf
2、(1,二部图最大权匹配运行结果n);fprintf(1,nn求得最大权匹配M=);sumw=0;fori=1:nforj=1:nifM(j,2)=ifprintf(1,x%dy%d,i,j);sumw=sumw+w(i,j);break;endendendfprintf(1,n);fprintf(1,最大权W(M)=%gn,sumw);returnelseFLAG_S=zeros(1,n);FLAG_T=zeros(1,n);FLAG_S(u)=1;f=zeros(n,2);FLAG_NGLS=zeros(1,n);endFLAG4=1;fori=1:nifFLAG_S(i)l(i,1)=l(
3、i,1)-al;end,endforj=1:nifFLAG_T(j)l(j,2)=l(j,2)+al;end,endFLAG_AGL=zeros(n,n);fori=1:nforj=1:nifl(i,1)+l(j,2)=w(i,j)FLAG_AGL(i,j)=i;end,end,end,endforx=1:nfory=1:nif(FLAG_S(x)&(FLAG_T(y)&(FLAG_AGL(x,y)=x)f(y,2)=x;if M(y,2)%1startforz=1:nif(FLAG_AGL(z,y)=z)&(M(y,2)=z)FLAG_S(z)=1;FLAG_T(y)=1;f(z,1)=y;
4、FLAG4=1;break;end,endelse%1endstop=0;searched=zeros(n,2);whilestopfori=1:nif(f(y,2)=i)M(y,2)=i;M(i,1)=i;ifi=ustop=1;break;endfork=1:nif(f(i,1)=k)M(k,2)=0;y=k;break;end,endifstop=0breakend,end,end,endFLAG3=1;break;end%2endifFLAG4break;endendendifFLAG4break;endifFLAG3break;endend%FLAG_S,FLAG_T,MifFLAG
5、3break;end引例的求解：车辆调度问题end, end该问题是求一个最小权最大匹配的问题，可以用一个大数（大于所有费用）减每一个费用，把问题转化为了新的费用矩阵下求最大权匹配问题。求解步骤：1）求新的费用矩阵：用一个大数（大于所有费用）减每一个费用；2）调用函数maxmatch（）求最大权匹配；3）求该匹配对应的总费用。求出的匹配对应的车与地点的配对即为所求，其费用为第3步所得总费用。程序：求解的MATLAB程序（调用maxmatch）：D=30,25,18,32,27,19,22,26;29,31,19,18,21,20,30,19;?28,29,30,19,19,22,23,26;2
6、9,30,19,24,25,19,18,21;?21,20,18,17,16,14,16,18;D1=40*ones（5,8）-D;cost0=maxmatch（D1）;Cost=5*40-cost0输出：求得最大权匹配M=x1y3,x2y4,x3y5,x4y7,x5y6,Cost最大权W（M）=11387因此，最小费用的调度方案是：地点1派3号车，地点2派4号车，地点3派5号车，地点4派7号车，地点5派6号车。总费用为87。本文节选的是原论文中模型的分析与建立以及之前的准备工作部分;该部分通过单位钢管的最小运购费K建立了问题求解的二次规划模型K特点是思路U表述简明U清晰K尤其是第!问的模型具
7、有较强的一般性K适用于树形结构的通常情形;值得注意的是K模型中有关铺设费的假设和表达式与常见情形略有不同;摘要Q在铺设管道为一条线的情况下K我们建立了解决钢管订购和运输问题的非线性规划模型;由于变量较少K约束条件大都为线性的K目标函数为二次函数K所以利用PA:J4软件K可以很快求得比较满意的订购和运输方案;我们利用%9?59V软件K对所得到的数据进行拟合K得到相应的反映销价变化对总费用影响的曲线K然后比较各个钢厂钢管销价变化对总费用影响的大小;对于钢厂钢管产量上限变化对总费用和购运计划的影响K我们也作了类似的处理;如果要铺设的管道是树形图K我们对树形图的每条边定向K建立了与铺设管道为一条线时类
8、似的数学模型K从而大大拓广了模型的使用范围;在论文中K我们还对所建立的模型的优缺点和需要改进的方向进行了讨论1符号说明2基本假设根据题目的要求，弁为达到简化问题的目的，我们有以下假设：3模型建立该文建立了用于天燃气管道铺设的钢管订购和运输总费用最省的二次规划模型；总费用作为目标函数，钢管生产厂的产量限制等作为约束条件.所建模型通过定性分析与使用Lingo软件求解获得了满意的方案,弁且计算量大大减少了.整篇文章理由描述充分,层次清楚，洞察力强而篇幅较短.摘要：本文研究铺设天燃气钢管的最优方案问题.我们建立了一个以总费用为目标函数的二次规划模型.1问题的重述与分析2模型的假设与符号说明1）基本假设
9、：2）符号说明3模型的建立某厂向用户提供发动机，合同规定，第一、二、三季度末分别交货40台、60台、80台,每季度的生产费用为（元），其中x是该季生产的台数.若交货后有剩余，可用于下季度交货，但需支付存储费，每台每季度c元.已知工厂每季度最大生产能力为100台，第一季度开始时无存货，设a=50、b=0.2、c=4,问工厂应如何安排生产计划，才能既满足合同又使总费用最低,讨论a、b、c变化对计划的影响，并作出合理的解释.问题的分析和假设：若每季度的生产费用为f（x）=ax+bxA2（元）设三季度分别生产量为x,y,180-x-y台。且应满足Lf40x0Fyy0即为F的极小值点。在通过和边界值的比
10、较知其是定义域上的最小值点。对以上问题加以整理分析，用matlab实现，m文件为：a=50;b=0.2;c=4;H=diag(2*b*ones(1,3);C=a+2*c,a+c,a;A1=-1,0,0;-1,-1,0;b1=-40,-100;A2=111;b2=180;v1=000;v2=100100100;x,faval,exitflag,output,lambada=quadprog(H,C,A1,b1,A2,b2,v1,v2,)y=x*H*x/2+C*x-140*c求解的Matlab程序代码：a=50;b=0.2;c=4;H=diag(2*b*ones(1,3);C=a+2*c,a+c,
11、a;A1=-1,0,0;-1,-1,0;b1=-40,-100;A2=111;b2=180;v1=000;v2=100100100;x,faval,exitflag,output,lambada=quadprog(H,C,A1,b1,A2,b2,v1,v2,)y=x*H*x/2+C*x-140*c输出结果x=50.000060.000070.0000faval=11840exitflag=1output=iterations:1algorithm:medium-scale:active-setfirstorderopt:cgiterations:message:Optimizationterminated.lambada=lower:3x1doubleupper:3x1doubleeqlin:-78ineqlin:2x1doubley=11280
