数学建模(整数规划)_图文

1、 整数规划模型 实际问题中x x x x f z Max Min Tn ",(,(1=或的优化模型mi x g t s i ",2,1,0(.=x 决策变量f (x 目标函数g i (x 0约束条件多元函数决策变量个数n 和数线性规划条件极值约束条件个数m 较大最优解在可行域学规非线性规划解的边界上取得划整数规划 Programming+Integer所有变量都取整数,称为纯整数规划;有一部分取整数,称为混合整数规划;限制取0,1称为01型整数规划。型整数规划 +整数线性规划max(min nz c x =1j jj n=1s.t. (, 1,2,ij j i j a x

2、b i m="12 ,0 (n x x x "且为整数或部分为整数 +例:假设有m 种不同的物品要装入航天飞机,它们的重量和体积分别为价值为w j 和v j ,价值为c j ,航天飞机的载重量和体积限制分别为W 和V ,如何装载使价值最大化?m11max j jj c y = 1 0j j y =被装载 s.t. mj j v y V0j 没被装载1j m=1j j j w y W= 0 or 1 1,2,j y j m=" (Chicago大学的Linus Schrage教授于1980年美国芝加哥(ChiLi S h前后开发, 后来成立LINDO系统公司(LIN

3、DO Systems Inc.,网址:I网址htt/li dLINDO: Interactive and Discrete Optimizer (V6.1 Linear(V61 LINGO: Linear Interactive General Optimizer (V8.0 LINDO解决线性规划LPLinear Programming,整数规划IPInteger Programming问题。LINGO解决线性规划LPLinear Programming,非线性规划NLPNonlinear Programming,整数规划IPInteger Programmingg g整划g g g 问题。

4、 1.“>”(或“<”号与“>=”(或“<=”功能相同2.甚至回车 但无运算变量与系数间可有空格(甚至车,但算符3.变量名以字母开头,不能超过变量名字母开头,不能超过8个字符 4.变量名不区分大小写(包括LINDO 中的关键字 5.目标函数所在行是第一行,第二行起为约束条件6.行号(行名自动产生或人为定义。行名以“”结束7.变量不能出现在一个约束条件的右端变量不能出现在个约束条件的右端8. 表达式中不接受括号“( ”和逗号“,”等任何符号, 例: 400(X1+X2需写为400X1+400X2 9.表达式应化简,如2X1+3X24X1应写成2X1+3X22X13X210

5、.缺省假定所有变量非负;可在模型的“END”语句后用“FREE name”将变量name的非负假定取消11.“END”后对01变量说明:INT n或INT name12.“END”后对整数变量说明:GIN n或GIN12后对整数变量说明name 汽车厂生产三种类型的汽车,已知各类型每辆车对钢材、劳动时间的需求,利润及工厂每月的现有量。材劳动时间的需求利润及工厂每月的现有量。小型中型大型现有量钢材(吨 1.5 3 5 600劳动时间(小时280 250 400 60000利润(万元2 3 4制订月生产计划,使工厂的利润最大。制订月生产计划使工厂的利润最大如果生产某一类型汽车,则至少要生产80辆,

6、那么最优的生产计划应作何改变?汽车厂生产计划汽车厂产计划模型建立小型中型大型现有量设每月生产小、中、大型模建中钢材 1.5 3 5 60060000汽车的数量分别为x 1,x 2,x 3时间280 250 400 利润2 3 4321432x x x zMax +=线性600535.1.321+x x x t s 60000400250280+x x x 线规划模型3210,321x x x (LP 模型OBJECTIVE FUNCTION VALUE 求解1632.2581VARIABLE VALUE REDUCED COST X164.5161290.000000X2167.7419280

7、.000000X30.0000000.946237结果为小数,ROW SLACK OR SURPLUS DUAL PRICES20.0000000.73118330.0000000.003226怎么办?1舍去小数:取x 1=64,x 2=167,算出目标函数值z =629,与LP 最优值632.2581相差不大。2试探:如取x 1=65,x 2=167;x 1=64,x 2=168等,计算函数值z ,通过比较可能得到更优的解。但必须检验它们是否满足约束条件。3模型中增加条件:x 1,x 2,x 3均为整数,重新求解。整数规划(Integer Programming ,简记IP IP 可用LIN

8、DO 直接求解max 321432x x x z Max +=模型求解2x1+3x2+4x3st600535.1.321+x x x t s 60000400250280321+x x x 1.5x1+3x2+5x3<600280x1+250x2+400x3<60000end为非负整数321,x x x “gin 3”表示“前3个变量为gin 3OBJECTIVE FUNCTION VALUE IP 结果输出整数”,等价于:gin x1i 21632.0000VARIABLE VALUE REDUCED COST X164.0000002.000000gin x2gin x3 的最

9、解6680最值632X2168.0000003.000000X3 0.000000 4.000000IP 的最优解x 1=64,x 2=168,x 3=0,最优值z =632 汽车厂生产计划汽车厂产计划若生产某类汽车,则至少生产80辆,求生产计划。M 80,0,0321=x x x 0,80,0321=x x x 321432x x x z Max +=600535.1.321+x x x t s 80,80,0321=x x x 60000400250280321+x x x x x x =0 80×0,0,80321=x x x 0,80,80321=x x x 方法1:分解为8

10、个LP 子模型1,2,3或其中3个子模型应去掉,然后逐一求解比较目标函数值80,0,80321=x x x 808080x x x ×逐求解,比较目标函数值,再加上整数约束,得最优解:,3210,321=x x x ×x 1=80,x 2= 150,x 3=0,最优值z =610若生产某类汽车,则至少生产80辆,求生产计划。方法2:引入01变量,化为整数规划产车产产计M 为大的正数,x 1=0 或8001,0,80,11111y y x My x 可取1000 x 2=0 或80x =0 或801,0,80,22222y y x My x 1,0,80,33333y y x

11、 My x LINDO 中对01OBJECTIVE FUNCTION VALUE 1610.00003变量的限定:int y1VARIABLE VALUE REDUCED COST X180.0000002.000000最优解同前int y2int y3 X2150.000000 3.000000X30.0000004.000000Y1 1.0000000.00000010000000000000解同前Y2 1.0000000.000000Y3 0.000000 0.000000 售价4800元/吨汽油甲库存500吨(A 50% 原油A汽油乙市场上可买到不超过售价5600元/吨库存1000吨原

12、油B (A 60%1500吨的原油A :购买量不超过500吨时的单价为10000元/吨;购买量超过500吨但不超过1000吨时,超过500吨的8000元/吨;该公司应如何安排原油的采购和加部分购买量超过1000吨时,超过1000吨的部分6000元/吨。该公司应如何安排原油的采购和加工?问题利润:销售汽油的收入A 分析利润销售汽油的收购买原油的支出难点:原油A 的购价与购买量的关系较复杂决策原油A 的购买量,原油A, B 生产汽油甲,乙的数量变量甲(A 50% A购买x x 11x 12x 214.8千元/吨目标B 乙(A 60% x 22 5.6千元/吨函数c (x 购买原油A 的支出利润(千

13、元(6.5(8.422122111x c x x x x z Max +=c (x 如何表述?目标x 500吨单价为10千元/吨;500吨x 1000吨,超过500吨的8千元/吨;吨超过吨函数1000吨x 1500吨,超过1000吨的6千元/吨。+=1000(500 1000 8500(0 10(x x x x x c 约束+5001(1000 30006x x 原油供应条件x x x +5001211购买x Ax 11x 500吨10002221+x x B 12x 21x 库存库存1000吨1500x 22汽油含原油约束A 的比例限制条件x 115.011+x x x 2111x x 甲(

14、A 50% Ax 12x 21211112x B 乙(A 60%x 22数中是线数是线划6.02212+x x 221232x x ¾目标函数中c (x 不是线性函数,是非线性规划;¾,一般的非线性规划软对于用分段函数定义的c (x ,般的非线性规划软件也难以输入和求解;想法将型简用成的软件求解¾想办法将模型化简,用现成的软件求解。x x x 以价格10, 8, 6(A 模型求解1 ,2 ,3 价格,(千元/吨采购的吨数=+x +x c =+8+6目标x x 1x 2x 3, (x 10x 18x 26x 3函数6810(6.5(8.432122122111x x

15、 x x x x x z Max += y 1, y 2 , y 3=1 以价格10, 8, 6(千元/吨采购A 增108加112500500y x y 223500500y x y x 1 , x 2 , x 3 以价格10, 8, 6(千元/吨采购A 的吨数y =0 x =0约束33500y x y 1,y 2,y 3 =0或1 x >0 y =1Max 4.8x11+4.8x21+5.6x12+5.6x2210x18x26x3stx11+x12x<500x21+x22<100005x1105x21>00.5x110.5x21>00.4x120.6x22>

16、;0x x1x2x3=0x1500y1<0x2500y2<0x3500y3<0500y2>0x1500y20x2500y3>0endint y1yint y2int y3 01线性规划模型,可用LINDO求解OBJECTIVE FUNCTION VALUE15000.000VARIABLE VALUE REDUCED COSTY1 1.0000000.000000Y2 1.0000002200.000000Y3 1.0000001200.000000X110.0000000.80000000000000800000X210.0000000.800000X12150

17、0.0000000.000000X221000.0000000.000000X1500.0000000.000000X2500.0000000.000000X30.0000000.400000X 1000.0000000.00000010000000000000000购买1000吨原油A,与库存的500吨原油A和1000吨原油B 一起,生产2500吨汽油乙,利润为5,000千元。 分派问题若干项任务分给一些候选人来完成,每人的专长不同,完成每项任务取得的效益或需要的资源就不同,如何分派任务使获得的总效益最大,或付出的总资源最少。选择问题若干种策略供选择,不同的策略得到的收益或付出的成本不同,各

18、个策略之间有相互制约关系,如何在满成本不同各个策略之间有相互制约关系如何在满足一定条件下作出决择,使得收益最大或成本最小。 5名候选人的百米成绩甲乙丙丁戊蝶泳106”857”2118”110”107”4仰泳115”6106”107”8114”2111”蛙泳127”106”4124”6109”6123”8自由泳58”653”59”457”2102”4如何选拔队员组成4×100米混合泳接力队?丁的蛙泳成绩退步到115”2;戊的自由泳成绩进步到57”5, 组成接力队的方案是否应该调整?穷举法:组成接力队的方案共有5!=120种。穷举法组成接力队的方案共有5!120种c ij (秒队员i 第

19、j 种泳姿的百米成绩 c ij i =1i =2i =3i =4i =51668572674j =166.857.2787067.4j =275.66667.874.271664846696838的比赛记j =38766.484.669.683.8j =458.65359.457.262.4目标若选择队员i 参加泳姿j 的比赛,记x ij =1, 否则记x ij =045函数约束=11j i ijij x c Z Min条件每人最多入选泳姿之一每种泳姿有且只有1人45"5,1,11"=i x j ij 4,1,11=j xi ij模型求解输求解输入LINDOMIN 66.8

20、x11+75.6x12+87x13+58.6x14+57.2x21+66x22+66.4x23+53x24+78x31+67.8x32+84.6x33+59.4x34+70x41+74.2x42+69.6x43+57.2x44+67.4x51+71x52+83.8x53+62.4x54 SUBJECT TOx11+x12+x13+x14 <=1x21+x22+x23+x24 <=1x31+x32+x33+x34 <=1x41+x42+x43+x44 <=1x51x52x53x54 1x51+x52+x53+x54<=1x11+x21+x31+x41+x51 =1x

21、12+x22+x32+x42+x52 =1x13+x23+x33+x43+x53 1=1x14+x24+x34+x44+x54 =1ENDINT20 OBJECTIVE FUNCTION VALUE1 253.2000最优解:VARIABLE VALUE REDUCED COSTX11 0.000000 66.800003X12 0.000000 75.599998最优解x 14=x 21=x 32=x 43=1,X13 0.000000 87.000000X14 1.00000058.599998X21 1.00000057.200001000000066000000其它变量为0;X22 0

22、.000000 66.000000X23 0.000000 66.400002X24 0.000000 53.000000000000078000000成绩为253.2(秒=413”2X31 0.000000 78.000000X32 1.00000067.800003X33 0.000000 84.599998000000059400002甲 自由泳X34 0.000000 59.400002X41 0.000000 70.000000X42 0.000000 74.199997乙 蝶泳X43 1.000000 69.599998X44 0.000000 57.200001X51 0.000

23、000 67.400002X52 0.000000 71.000000丙 仰泳50000000000000X53 0.000000 83.800003X54 0.000000 62.400002丁 蛙泳 甲乙丙丁戊蝶泳106”857”2118”110”107”4仰泳115”6106”107”8114”2111”蛙泳127”106”4124”6109”6123”8自由泳58”653”59”457”2102”4 丁蛙泳696752戊自由泳624讨论c 43=69.675.2,戊自由泳c 54=62.4 57.5, 方案是否调整?敏感性分析?IP 规划般没有与规划相类似的理论规划一般没有与LP 规划

24、相类似的理论,LINDO 输出的敏感性分析结果通常是没有意义的。的新数据重新输入模型用c 43, c 54的新数据重新输入模型,用LINDO 求解 模型求解输求解输入LINDOMIN 66.8x11+75.6x12+87x13+58.6x14+57.2x21+66x22+66.4x23+53x24+78x31+67.8x32+84.6x33+59.4x34+70x41+74.2x42+75.2x43+57.2x44+67.4x51+71x52+83.8x53+57.5x54 SUBJECT TOx11+x12+x13+x14 <=1x21+x22+x23+x24 <=1x31+x3

25、2+x33+x34 <=1x41+x42+x43+x44 <=1x51x52x53x54 1x51+x52+x53+x54<=1x11+x21+x31+x41+x51 =1x12+x22+x32+x42+x52 =1x13+x23+x33+x43+x53 1=1x14+x24+x34+x44+x54 =1ENDINT20 最优解:OBJECTIVE FUNCTION VALUE1 257.7000x =x =x =x =1VARIABLE VALUE REDUCED COSTX11 0.000000 66.800003X12 0.000000 75.5999980000000

26、8700000021324354成绩为417”7X13 0.000000 87.000000X14 0.000000 58.599998X21 1.000000 57.200001000000066000000X22 0.000000 66.000000X23 0.000000 66.400002X24 0.000000 53.000000000000078000000新方案乙 蝶泳原方案甲 自由泳X31 0.000000 78.000000X32 1.000000 67.800003X33 0.000000 84.599998丙 仰泳乙 蝶泳X34 0.000000 59.400002X41

27、 0.000000 70.000000X42 0.000000 74.199997X43 1.000000 75.199997丁 蛙泳丙 仰泳X44 0.000000 57.200001X51 0.000000 67.400002X52 0.000000 71.000000戊 自由泳丁 蛙泳.X53 0.000000 83.800003X54 1.000000 57.500000 甲乙丙丁戊蝶泳106”857”257”2118”110”107”4仰泳115”6106”107”8107”8114”2111”蛙泳127”106”4124”6109”6115”2123”81152自由泳58”653”

28、59”457”2102”457”5575 指派(Assignment问题:问题每项任务有且只有一人承担,每人只能承担一项,益怎样分派使总效益不同,怎样分派使总效益最大. 课号课名学分所属类别先修课要求1微积分5数学2线性代数4数学3最优化方法4数学;运筹学微积分;线性代数最优方学筹学积分线代4数据结构3数学;计算机计算机编程5应用统计4数学;运筹学微积分;线性代数6计算机模拟3计算机;运筹学计算机编程7计算机编程2计算机应用统计要求至少选两门数学课三门运筹学课和两门计算机课8预测理论2运筹学9数学实验3运筹学;计算机微积分;线性代数为了选修课程门数最少,应学习哪些课程?要求至少选两门数学课、三

29、门运筹学课和两门计算机课选修课程最少,且学分尽量多,应学习哪些课程?01规划模型决策变量x i =1 选修课号i 的课号课名所属类别1微积分数学课程(x i =0 不选2线性代数数学3最优化方法数学;运筹学目标函数选修课程总数最少最优方法学;筹学4数据结构数学;计算机5应用统计数学;运筹学=9x Z Min6计算机模拟计算机;运筹学7计算机编程计算机=1i i最少门数学2+x x x x x 8预测理论运筹学9数学实验运筹学;计算机约束条件2门数学课,3门运筹学课,54321398653+x x x x x 2门计算机课。29764+x x x x01规划模型约束条件先修课程要求有课号课名先修

30、课要求微积分x 3=1必有x 1 = x 2 =11(52线性代数(43最优化方法(4微积分;线性代数2x x x 2313,x x x x 最优方法(微积分;线性代4数据结构计算机编程5应用统计微积分;线性代数74x x 213074x x 6计算机模拟(3计算机编程7计算机编程(2应用统计02215x x x 模型求解(8预测理论9数学实验(3微积分;线性代数76x x 058x x 最优解:x 1 = x 2 = x 3 = x 6= x 7= x 9=1, LINDO 2219x x x 其它为0;6门课程,总学分21 FUNCTIONVALUEmin x1+x2+x3+x4+x5+x

31、6+x7+x8+x9stx1+x2+x3+x4+x5>2OBJECTIVE 1 6.000000x3+x5+x6+x8+x9>3x4+x6+x7+x9>22x3x1x2<0VARIABLE VALUE REDUCED COSTX1 1.000000 1.00000010000001000000x4x7<02x5x1x2<0x6x7<0X2 1.000000 1.000000X3 1.000000 1.000000X4 0.000000 1.000000x8x5<02x9x1x2<0end i t X5 0.000000 1.000000X6

32、 1.000000 1.000000X7 1.000000 1.000000X8 0.000000 1.000000int9X9 1.000000 1.000000 讨论:选修课程最少,学分尽量多,应学习哪些课程?学分最多修最课程最少5432143445x x x x x W Max +=9ix Z Min两目标(多目标规划98763223x x x x +,W Z Min =1i 多目标优化的处理方法:化成单目标优化。以课程最少为目标,不管学分多少。最优解如上,6门课程,总学分21 。以学分最多为目标,最优解显然是选修所不管课程多少。有9门课程。多目标规划在课程最少的前提下增加约束,69=i

33、 x 以学分最多为目标。以学分最多为目标求解。1=i 最优解:x 1 = x 2 = x 3 = x 5= x = x =1, 其它为0;总学课号课名学分1微积分579分由21增至22。意解唯2线性代数43最优化方法44注意:最优解不唯一!数据结构35应用统计46计算机模拟3=1=17计算机编程28预测理论2LINDO 无法告诉优化可将x 91 易为x 619数学实验3问题的解是否唯一。 max FUNCTIONVALUE5x1+4x2+4x3+3x4+4x5+3x6+2x7+2x8+3x9stx1+x2+x3+x4+x5>2x3+x5+x6+x8+x9>3OBJECTIVE 1 22.00000x3x5x6x8x9>3x4+x6+x7+x9>22x3x1x2<0x4x