规划问题

1规划问题方加晔2优化模型在研究与解决具体问题中，经常遇到有关优化问题，下面介绍几个简单的优化模型。线性规划是运筹学的一个重要分支，它起源于工业生产组织管理的决策问题。在数学上它用来确定多变量线性函数在变量满足线性约束条件下的最优值；随着计算机的发展，出现了如单纯形法等有效算法，它在工农业、军事、交通运输、决策管理与规划等领域中有广泛的应用。3问题一：任务分配问题：某车间有甲、乙两台机床，可用于加工三种工件。假定这两台车床的可工作时间分别为800和900，三种工件的数量分别为400、600和500，且已知车床甲加工单位数量三种工件所需的时间和加工费分别为0.4、1.1、1和13、9、10，车床乙加工单位数量三种工件所需的时间和加工费分别为0.5、1.2、1.3和11、12、8。问怎样分配车床的加工任务，才能既满足加工工件的要求，又使加工费用最低？46543218121110913minxxxxxxz6,,2,1,09003.12.15.08001.14.0500600400x..654321635241ixxxxxxxxxxxxtsi解设在甲车床上加工工件1、2、3的数量分别为x1、x2、x3，在乙车床上加工工件1、2、3的数量分别为x4、x5、x6。可建立以下线性规划模型：5问题二：某厂每日8小时的产量不低于1800件。为了进行质量控制，计划聘请两种不同水平的检验员。一级检验员的标准为：速度25件/小时，正确率98%，计时工资4元/小时；二级检验员的标准为：速度15件/小时，正确率95%，计时工资3元/小时。检验员每错检一次，工厂要损失2元。为使总检验费用最省，该工厂应聘一级、二级检验员各几名？121284833224xxxx解设需要一级和二级检验员的人数分别为x1、x2人,则应付检验员的工资为：因检验员错检而造成的损失为：1212(8252%8155%)2812xxxx121212min(3224)(812)4036zxxxxxx故目标函数为：61212128258151800825180081518000,0xxxxxx约束条件为：线性规划模型：12min4036zxx12121253459..150,0xxxstxxx7丁的蛙泳成绩退步到1’15”2；戊的自由泳成绩进步到57”5,组成接力队的方案是否应该调整？如何选拔队员组成4100米混合泳接力队?问题三混合泳接力队的选拔甲乙丙丁戊蝶泳1’06”857”21’18”1’10”1’07”4仰泳1’15”61’06”1’07”81’14”21’11”蛙泳1’27”1’06”41’24”61’09”61’23”8自由泳58”653”59”457”21’02”45名候选人的百米成绩穷举法：组成接力队的方案共有5!=120种。8目标函数若选择队员i参加泳姿j的比赛，记xij=1,否则记xij=00-1规划模型cij(秒)~队员i第j种泳姿的百米成绩约束条件每人最多入选泳姿之一ciji=1i=2i=3i=4i=5j=166.857.2787067.4j=275.66667.874.271j=38766.484.669.683.8j=458.65359.457.262.44151jiijijxcZMin每种泳姿有且只有1人5,1,141ixjij4,1,151jxiij9模型求解最优解：x14=x21=x32=x43=1,其它变量为0;成绩为253.2(秒)=4’13”2MIN66.8x11+75.6x12+87x13+58.6x14+……+67.4x51+71x52+83.8x53+62.4x54SUBJECTTOx11+x12+x13+x14=1……x41+x42+x43+x44=1x11+x21+x31+x41+x51=1……x14+x24+x34+x44+x54=1ENDINT20输入LINDO求解甲乙丙丁戊蝶泳1’06”857”21’18”1’10”1’07”4仰泳1’15”61’06”1’07”81’14”21’11”蛙泳1’27”1’06”41’24”61’09”61’23”8自由泳58”653”59”457”21’02”4甲~自由泳、乙~蝶泳、丙~仰泳、丁~蛙泳.10丁蛙泳c43=69.675.2，戊自由泳c54=62.457.5,方案是否调整？乙~蝶泳、丙~仰泳、丁~蛙泳、戊~自由泳最优解：x21=x32=x43=x51=1,成绩为4’17”7c43,c54的新数据重新输入模型，用LINDO求解讨论甲~自由泳、乙~蝶泳、丙~仰泳、丁~蛙泳.原方案11校数摸规划问题某手机运营商准备在一个目前尚未覆盖的区域开展业务，计划投资5000万元来建设中继站。该区域由15个社区组成，有7个位置可以建设中继站，每个中继站只能覆盖有限个社区。图1是该区域的示意图，每个社区简化为一个多边形，每个可以建设中继站的位置已用黑点标出。由于地理位置等各种条件的不同，每个位置建设中继站的费用也不同，且覆盖范围也不同。表1中列出了每个位置建设中继站的费用以及能够覆盖的社区，表2列出了每个社区的人口数。12图1123456789101112131415123456713问题一：在不超过5000万建设费用的情况下，在何处建设中继站，能够覆盖尽可能多的人口；14•问题二：考虑到中继站出现故障维修的时候可能会出现所覆盖的社区信号中断等问题，为此对通讯资费进行了调整，规定，仅有一个中继站信号覆盖的小区通讯资费按正常资费的70%收取，有两个或两个以上中继站信号覆盖的小区的通讯资费按正常收取，针对于5000万元的预算，应该如何建设中继站，才能够使得资费的收入达到最大。15约束条件目标函数0-1规划模型Lingo求解隐枚举算法数学模型1（线性规划）约束条件目标函数三值规划模型Lingo求解遗传算法数学模型2（三值规划）重要要找到两个函数找到每个区域重复多余覆函数k和的确定确定单位区域利润函数d16目标函数•目标1•目标271511max()iiiiiiQxbka151iiiWad17约束条件与重要函数7150iiixcmax(1,0)iikxi-(x-2)iidmin1,x,0.718•model:•k1=@smax(0,(x1-1));•k2=@smax(0,(x1+x2-1));•k3=@smax(0,(x2-1));•k4=@smax(0,(x1+x3-1));•k5=@smax(0,(x2+x4-1));•k6=@smax(0,(x4-1));•k7=@smax(0,(x3+x6-1));•k8=@smax(0,(x3+x4+x5-1));•k9=@smax(0,(x4+x5-1));•k10=@smax(0,(x3+x6-1));•k11=@smax(0,(x6-1));•k12=@smax(0,(x5+x6+x7-1));•k13=@smax(0,(x7-1));•k14=@smax(0,(x7-1));•k15=@smax(0,(x6+x7-1));•data:•a1=2;a2=4;a3=13;a4=6;a5=9;a6=4;a7=8;a8=12;a9=10;a10=11;a11=6;a12=14;a13=9;a14=3;a15=6;•enddata•max=(x1*(a1+a2+a4)+x2*(a2+a3+a5)+x3*(a4+a7+a8+a10)+x4*(a5+a6+a8+a9)+x5*(a8+a9+a12)+x6*(a7+a10+a11+a12+a15)+x7*(a12+a13+a14+a15))-k1*a1-k2*a2-k3*a3-k4*a4-k5*a5-k6*a6-k7*a7-k8*a8-k9*a9-k10*a10-k11*a11-k12*a12-k13*a13-k14*a14-k15*a15;•@bin(x1);@bin(x2);@bin(x3);@bin(x4);@bin(x5);@bin(x6);@bin(x7);•x1*9+x2*6.5+x3*20+x4*14.5+x5*19+x6*13+x7*10.5=50;•end最后一题具体的求法见论文！19