车辆调度问题 设某车队有8辆车，存放在不同的地点，队长要派出其中5辆到5个工地去运货。各车从存放处调到装货地点所需费用列于下页表，问应选哪5辆车调到何处去运货，才能使各车从车所在地点调到装货地点所需的总费用最少？
1 2 3 4 5 6 7 8 1 30 25 18 32 27 19 22 26 2 29 31 19 18 21 20 30 19 3 28 29 30 19 19 22 23 26 4 29 30 19 24 25 19 18 21 5 21 20 18 17 16 14 16 18
MATLAB程序——Kuhn-munkras算法 function sumw=kuhngong(A) n=size(A,1); w=A; l=zeros(n,2); for i=1:n for j=1:n if l(i,1)l(i,1)=w(i,j); end end end FLAG_AGL=zeros(n,n); FLAG_S=zeros(1,n); FLAG_T=zeros(1,n); FLAG_NGLS=zeros(1,n);f=zeros(n,2); for i=1:n for j=1:n if l(i,1)+l(j,2)==w(i,j) FLAG_AGL(i,j)=i; end
车 地点
x5 y1 y2 y3 y4 y5 x1 x2 x3 x4
y6 y7 y8 end end
M=zeros(n,2); for i=1:n for j=1:n if (FLAG_AGL(i,j)==i)&(~M(j,2)) &(~M(i,1)) M(i,1)=i; M(j,2)=i; end end end FLAG3=1; while FLAG3 FLAG3=0; u=0; for i=1:n if ~M(i,1) u=i; break; end end end while FLAG4 for i=1:n if FLAG_S(i) for j=1:n if FLAG_AGL(i,j)==i FLAG_NGLS(j)=1; end, end, end, end FLAG_EQU=1; for i=1:n if FLAG_NGLS(i)~=FLAGT(i) FLAG_EQU=0; break; end, end FLAG4=0; al=inf; if FLAG_EQU for i=1:n for j=1:n if (FLAG_S(i))&(~FLAG_T(j)) temp=l(i,1)+l(j,2)-w(i,j); if al>temp al=temp; end, end, end, end if ~u fprintf(1,‘二部图最大权匹配运行结果\n'); fprintf(1,‘\n\n求得最大权匹配M={'); sumw=0; for i=1:n for j=1:n if M(j,2)==i fprintf(1,'x%dy%d,',i,j); sumw=sumw+w(i,j); break; end end end fprintf(1,'}\n'); fprintf(1,‘最大权W(M)=%g\n',sumw); return else FLAG_S=zeros(1,n); FLAG_T=zeros(1,n); FLAG_S(u)=1;f=zeros(n,2); FLAG_NGLS=zeros(1,n); end FLAG4=1; for i=1:n if FLAG_S(i) l(i,1)=l(i,1)-al; end, end for j=1:n if FLAG_T(j) l(j,2)=l(j,2)+al; end, end FLAG_AGL=zeros(n,n); for i=1:n for j=1:n if l(i,1)+l(j,2)==w(i,j) FLAG_AGL(i,j)=i; end, end, end, end for x=1:n for y=1:n if (FLAG_S(x))&(~FLAG_T(y)) &(FLAG_AGL(x,y)==x) f(y,2)=x; if M(y,2) %%1start for z=1:n if (FLAG_AGL(z,y)==z) &(M(y,2)==z) FLAG_S(z)=1; FLAG_T(y)=1; f(z,1)=y; FLAG4=1; break; end, end else %%1end stop=0; searched=zeros(n,2); while ~stop for i=1:n if (f(y,2)==i) M(y,2)=i;M(i,1)=i; if i==u stop=1; break; end for k=1:n if (f(i,1)==k) M(k,2)=0; y=k; break; end, end if stop==0 break end, end, end, end FLAG3=1; break; end %%2end if FLAG4 break; end end end if FLAG4 break; end if FLAG3 break; end end %FLAG_S,FLAG_T,M if FLAG3 break; 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;29,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,} 最大权W(M)=113 Cost = 87 因此，最小费用的调度方案是：地点1派3号车，地点2派4号车，地点3派5号车，地点4派7号车，地点5派6号车。总费用为87。
本文节选的是原论文中模型的分析与建立以及之前的准备工作部分;该部分通过单位钢管的最 小运购费K建立了问题求解的二次规划模型K特点是思路U表述简明U清晰K尤其是第 !问的模型具有较强的一 般性K适用于树形结构的通常情形;值得注意的是K模型中有关铺设费的假设和表达式与常见情形略有不同; 摘要Q 在铺设管道为一条线的情况下K我们建立了解决钢管订购和运输问题的非线性规划模型;由于变 量较少K约束条件大都为线性的K目标函数为二次函数K所以利用 PA:J4软件K可以很快求得比较满意的订购 和运输方案;我们利用 %9?59V软件K对所得到的数据进行拟合K得到相应的反映销价变化对总费用影响的 曲线K然后比较各个钢厂钢管销价变化对总费用影响的大小;对于钢厂钢管产量上限变化对总费用和购运 计划的影响K我们也作了类似的处理;如果要铺设的管道是树形图K我们对树形图的每条边定向K建立了与 铺设管道为一条线时类似的数学模型K从而大大拓广了模型的使用范围;在论文中K我们还对所建立的模型 的优缺点和需要改进的方向进行了讨论; 1 符号说明 2 基本假设 根据题目的要求，并为达到简化问题的目的，我们有以下假设： 3 模型建立
该文建立了用于天燃气管道铺设的钢管订购和运输总费用最省的二次规划模型;总费用作为目标函数，钢管生产厂的产量限制等作为约束条件.所建模型通过定性分析与使用Lingo软件求解获得了满意的方案,并且计算量大大减少了.整篇文章理由描述充分,层次清楚,洞察力强而篇幅较短. 摘要： 本文研究铺设天燃气钢管的最优方案问题.我们建立了一个以总费用为目标函数的二次规划模型.
1 问题的重述与分析 2 模型的假设与符号说明 1)基本假设: 2)符号说明 3 模型的建立
某厂向用户提供发动机，合同规定，第一、二、三季度末分别交货40台、60台、80台．每季度的生产费用为 （元），其中x是该季生产的台数．若交货后有剩余，可用于下季度交货，但需支付存储费，每台每季度c元．已知工厂每季度最大生产能力为100台，第一季度开始时无存货，设a=50、b=0.2、c=4，问工厂应如何安排生产计划，才能既满足合同又使总费用最低．讨论a、b、c变化对计划的影响，并作出合理的解释．.
问题的分析和假设：
若每季度的生产费用为 f(x) = ax + bx^2（元） 设三季度分别生产量为x , y , 180-x-y台。
且应满足 40≤x≤100，