实验10 整数规划.docx
数学实验(整数规划)郭明钊 2022022880 化21一、二次指派问题1、 问题分析：这个问题的情景是不同的员工之间有不同的通话时间，而员工又在不同 的城市之中，不同的城市之间的通话费率也不同，要求解出每一个员工所在的城市 序号，使得通话的总的费用至少。根据题目叙述，约束条件是每一个城市之中惟独 一人，目标函数是总的通话费用达到最小。2、建立模型：定义符号X ,其代表第i个员工在第a个城市，且规定 .a'x =L第i个员工真正在第a个城市 , t代表第i个员工与第j个员工的通话X =0.第i个员工没有在第a个城市ij时间，P代表a, b两城市之间的通话费率。 a Ja根据题目中的要求，目标函数为： MinZ=注迂5 5(X X t P )(取n=5进行计算) i,a j,b i,j a ,b i= j= a= b=根据以上的设定和题目中每一个城市中惟独一人的约束，可以得出约束条件：5× =1,(i = 1,2.5)(每一个人在所有城市中只浮现一次)i,a a=15× =1,(a = 1,2.5)(每一个城市中惟独一个人)i.a i=13、LingO编写实现：基于以上模型，在Ling。中输入以下内容SETS:num1.5;call(numznum)×Xp;ENDSETSDATA:t=0 5 3 7 950783370937890893 380;p=0 7 4 6 8708264 8 0 10 46 2 10 0 68 6 4 6 0;ENDDATAmin=sUm(CalI(i,j):SUm(CalI(a,b):x(i,a)*x(j,b)*p(a,b)*t(i,j);););for(num(i):sum(num(b):x(i,b)=l；)；for(num(a):SUm(num(j):x(j,a)=l;);for(call:bin(x););说明：当将原题中所有的数据输入运算时，即n=10的时候，软件总是提醒错 误而无法得出正确的结果，所以在本题中取前面的5组数据。所的结果为：Local optimal solution found.Objective value:682.0000Objective bound:682.0000Infeasibilities :0.000000Extended solver steps:94Total solver iterations:4453Model Class:PINLPTotal variables:25Nonlinear variables:25Integer variables:25Total constraints:11Nonlinear constraints:1Total nonzeros:75Nonlinear nonzeros:25VariableValueReduced CostX( 1, D0.00000075.99977X( 1, 2)0.0000000.000000X( 1, 3)0.0000000.000000X( 1, 4)1.00000047.99984X( 1, 5)0.00000031.99986X( 2, 1)1.000000127.9997X( 2, 2)0.00000054.00001X( 2, 3)0.0000000.000000X( 2, 4)0.00000083.99992X( 2, 5)0.0000000.000000X( 3, 1)0.00000031.99993X( 3z 2)0.00000012.00010X( 3, 3)1.000000-7.999896X( 3, 4)0.0000008.000012X( 3, 5)0.0000000.000000X( 4, 1)0.0000000.000000X( X( X( X( X( X( X( X( X( T( T( T( T( T( T( T( T( T( T( T( ( T( ( T( T( T( T( T( T( T( T( T( T( T( P( P( P( P( P( P( P( P( P( P(，2)0.0000000.000000,3)0.00000010.00002，4)0.00000033.99992，5)1.000000117.9998，D0.00000073.99985，2)1.00000020.00003，3)0.00000028.00002，4)0.0000000.000000，5)0.0000000.000000，D0.0000000.000000，2)5.0000000.000000，3)3.0000000.000000，4)7.0000000.000000,5)9.0000000.000000,D5.0000000.000000,2)0.0000000.000000，3)7.0000000.000000,4)8.0000000.000000，5)3.0000000.000000,D3.0000000.000000，2)7.0000000.000000,3)0.0000000.000000，4)9.0000000.000000,5)3.0000000.000000,D7.0000000.000000,2)8.0000000.000000,3)9.0000000.000000，4)0.0000000.000000，5)8.0000000.000000,D9.0000000.000000,2)3.0000000.000000，3)3.0000000.000000，4)8.0000000.000000,5)0.0000000.000000,D0.0000000.000000,2)7.0000000.000000,3)4.0000000.000000,4)6.0000000.000000,5)8.0000000.000000,1)7.0000000.000000,2)0.0000000.000000,3)8.0000000.000000,4)2.0000000.000000,5)6.0000000.00000044445555511111222223333344444555551111122222P(3, 1)4.0000000.000000P(3, 2)8.0000000.000000P(3, 3)0.0000000.000000P(3, 4)10.000000.000000P(3, 5)4.0000000.000000P(4, D6.0000000.000000P(4, 2)2.0000000.000000P(4, 3)10.000000.000000P(4, 4)0.0000000.000000P(4, 5)6.0000000.000000P(5, 1)8.0000000.000000P(5, 2)6.0000000.000000P(5, 3)4.0000000.000000P(5, 4)6.0000000.000000P(5, 5)0.0000000.000000RowSlack or SurplusDual Price1682.0000-1.00000020.00000081.9999530.000000110.000040.00000078.0000950.0000000.00000060.00000082.0000470.000000-268.000180.000000-284.000090.000000-322.0000100.000000-274.0001110.000000-262.0001在上面的模型中i员工j员工的通话费用和j员工i员工的通话费用都分别计入 了总费用，所以实际的费用应为上面所给结果的一L即总话费至少为341.0元，且2由 X （1,4）=1，X（2,1） =1, X （3,3） =1, X（4,5）=1, X（5,2）=1 可知，第 1 个人 在第4个城市，第2个人在第1个城市，第3个人在第3个城市，第4个人在第5 个城市，第5个人在第2个城市。4、问题小结：这道题目的难点就在于模型的正确建立，01变量的设立还是首次遇到， 这也是整数规划中很重要的思想，由于不很熟悉所以我在做题时大部份时间都花在 了模型的建立上面，而模型建立之后用Ling。求解还是很方便的。二、钢管下料问题1、 问题分析：根据题意可知，该问题是将一定长度的钢管原料切割成四种特定长度的 成品钢管，每种产品都有数量的要求。每一种切割模式都要符合客户的需求在原料钢管上安排切割的一种组合，模式的总数不能超过4种，而且每一根原料钢管最多 只能生产5根产品。而且还有约束条件为每种切割模式下的余料浪费不能超过 IOOmm,切割费用也与切割模式的使用频率有关，这里切割费用是以原料钢管计的， 而目标是使总的费用至少，总的费用即原料钢管成本费用和切割时的增加费用之和。 2、建立模型根据题目，由于不同的切割模式不能超过4种，可以用X表示按照第i种模式(i=L2, 3, 4)切割的原料钢管的根数，设使用第i种切割模式下每根原料钢管生产长290mm, 315mm, 35Omm和455mm的钢管数量分别是r , r , r , r ,设以上四种1,i 2,i 3,i 4,i产品长度为度(j = 1,234) , S指第j种产品的需求量,j=l,2,3,4° ji目标是总的费用最小，所以目标函数是MinZ = I.1x+1.2x +1.3x +1.4x 1234生产产品数量要满足客户需要f r X > sji i i=1每根原料钢管最多生产5根产品4r5,(i = 1,2,3, 4)j=1每根原料钢管有185Omm长，且余料不能超过100mm,所以有17504rl 1850,(i = 1,2,3, 4)N ji=1由于4种切割模式的罗列顺序是无关要紧的，所以不妨增加以下约束：X > X > X > X 1234注意到所需原料钢管的总根数有明显的上界和下界。因为15×290 +2I×35O+28×3I5+ 30×455 YC - =18.47IRSO所以下界是19根。其次，考虑一种非常特殊的生产计划：第一种切割模式下只生 产29Omm钢管，一根原料钢管切割成6根29Omm钢管，为满足15根29Omrn钢 管的需求，需要3根原料钢管；第二种切割模式下只生产315mm钢管，一根原料 钢管切割成5根315mm钢管为满足28根315mm的需求，需要6根原料钢管；第 三种切割模式下只生产35Omm钢管，一根原料钢管切割成5根350mm钢管，为满 足21根35Omm钢管的需求，需要5根原料钢管；第四种切割模式下只生产455mm 钢管，一根原料钢管切割成4根455mm钢管，为满足30根455mm钢管的需求， 需要8根原料钢管。于是满足要求的这种生产计划共需要3+6+5+8=22根原料钢管， 这就得到了最优解的一个上界，所以可增加以下约束：19 x + x ÷X + X <221234最后，以上所有的参数除了 Z,均为正整数3、Lingo编写实现 输入以下内容：min=l.l*xl + l.2*x2 + l.3*x3+l.4 *x4;rll*xl+rl2*x2+rl3*x3+rl4*x4>=15;r21*xl+r22*x2+r23*x3+r24*x4>=28;r31*xl+r32*x2+r33*x3+r34*x4>=21;r41*xl+r42*×2+r43*x3+r44*×4>=30;rll+r21+r31+r41<=5;rl2+r22+r32+r42<=5;rl3+r23+r33+r43<=5;rl4+r24+r34+r44<=5;290*rll+315*r21+350*r31+455*r41<=1850;290*rl2+315*r22+350*r32+455*r42<=1850;290*rl3+315*r23+350*r33+455*r43<=1850;290*rl4+315*r24+350*r34+455*r44<=1850;290*rll+315*r21+350*r31+455*r41>=1750;290*rl2+315*r22+350*r32+455*r42>=1750;290*rl3+315*r23+350*r33+455*r43>=1750;290*rl4+315*r24+350*r34+455*r44>=1750;xl+x2+x3+x4>=19;xl+x2+x3+x4<=22;xl>=x2;x2>=x3;x3>=x4;gin (xl);gin (x2);gin (x3);gin (x4);gin(rll);gin (rl2);gin (rl3);gin(rl4);gin(r21);gin (r22);gin (r23);gin(r24);gin(r31);gin (r32);gin (r33);gin(r34);Qgin(r41);gin (r42);gin (r43);gin(r44);End可以得到以下结果：Local optimal solution found.21.5000021.500000.00000021413607PINLPObjective value:Objective bound:Infeasibilities:Extended solver steps:Total solver iterations:Model Class:Total variables:20Nonlinear variables :2020Integer variables :Total constraints :Nonlinear constraints :22498Nonlinear nonzeros :32VariableValueReduced CostXl14.00000-0.1000000X24.0000000.000000X31.0000000.1000000X40.0000000.2000000Rll1.0000000.000000R120.0000000.000000Rl 32.0000000.000000Rl 42.0000000.000000R212.0000000.000000R220.0000000.000000R230.0000000.000000R240.0000000.000000R310.0000000.000000R325.0000000.000000R331.0000000.000000R341.0000000.000000R412.0000000.000000R420.0000000.000000R4 32.0000000.000000R4 42.0000000.000000RowSlack or SurplusDual Price121,50000-1.00000021.0000000.00000030.0000000.00000040.0000000.00000050.0000000.00000060.0000000.00000070.0000000.00000080.0000000.00000090.0000000.0000001020.000000.00000011100.00000.0000001210.000000.0000001310.000000.0000001480.000000.000000Total nonzeros :150.0000000.0000001690.000000.0000001790.000000.000000180.000000-1.200000193.0000000.0000002010.000000.000000213.0000000.000000221.0000000.000000以上的切割模式可以总结为下表切割模式钢管数29 Omm钢管315mm钢管35Omm钢管455mm钢管余料11412O22024OO5OIOO312O12104O2O1210最优解21.5由表可知，最优方案为用19根原料钢管，其中第一种模式（14根）是切割成290un, 315mm, 350mm, 455un钢管的数量为1,2,0,2;第二种模式（4根）是只切出5 根350mm的产品；第三种模式（1根）四种产品切割数量分别为2, 0,1,2.4、问题小结：这是一个整数规划问题，该模型的建立还是比较简单的，而且其结构也 比较分明，但是缺点就是该模型没有进行结构上的优化，过程显得有些繁琐也不利 于模型的推广。这道题和课本例题有很大的相似性，只是多了些约束条件，目标函 数也略有不同。通过这道题目我对整数规划有了更深的了解。
