实验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 > sj
