1、 安阳师范学院数学与统计学院安阳师范学院数学与统计学院运筹学实验运筹学实验LINGO模型实例与求解模型实例与求解下料问题下料问题背包问题背包问题选址问题选址问题指派问题指派问题 安阳师范学院数学与统计学院安阳师范学院数学与统计学院运筹学实验运筹学实验问题问题1. 如何下料最节省如何下料最节省 ? 下料问题下料问题 问题问题2. 客户增加需求：客户增加需求：原料钢管原料钢管: :每根每根19米米 4米米50根根 6米米20根根 8米米15根根 客户需求客户需求节省的标准是什么？节省的标准是什么？由于采用不同切割模式太多，会增加生产和管理成本，由于采用不同切割模式太多，会增加生产和管理成本，规定切
2、割模式不能超过规定切割模式不能超过3种。如何下料最节省？种。如何下料最节省？5米米10根根 安阳师范学院数学与统计学院安阳师范学院数学与统计学院运筹学实验运筹学实验按照客户需要在一根原料钢管上安排切割的一种组合。按照客户需要在一根原料钢管上安排切割的一种组合。 切割模式切割模式余料余料1 1米米 4米米1根根 6米米1根根 8米米1根根 余料余料3米米 4米米1根根 6米米1根根 6米米1根根 合理切割模式合理切割模式的余料应小于客户需要钢管的最小尺寸的余料应小于客户需要钢管的最小尺寸余料余料3米米 8米米1根根 8米米1根根 钢管下料钢管下料 安阳师范学院数学与统计学院安阳师范学院数学与统计
3、学院运筹学实验运筹学实验为满足客户需要，按照哪些种合理模式，每种模式为满足客户需要，按照哪些种合理模式，每种模式切割多少根原料钢管，最为节省？切割多少根原料钢管，最为节省？合理切割模式合理切割模式2. 所用原料钢管总根数最少所用原料钢管总根数最少 模式模式 4米钢管根数米钢管根数6米钢管根数米钢管根数8米钢管根数米钢管根数余料余料(米米)14003231013201341203511116030170023钢管下料问题钢管下料问题1 1 两种两种标准标准1. 原料钢管剩余总余量最小原料钢管剩余总余量最小 安阳师范学院数学与统计学院安阳师范学院数学与统计学院运筹学实验运筹学实验xi 按第i 种模
4、式切割的原料钢管根数(i=1,2,7) 约束约束满足需求满足需求 决策变量决策变量 目标目标1（总余量）（总余量）765432113333xxxxxxxZMin5023454321xxxxx20326542xxxx152753xxx按模式按模式2切割切割12根根, ,按模式按模式5切割切割15根，余料根，余料27米米 模模式式4米米根数根数6米米根数根数8米米根数根数余余料料14003231013201341203511116030170023需需求求502015最优解：最优解：x2=12, x5=15, 其余为其余为0；最优值：最优值：27整数约束：整数约束： xi 为整数为整数 安阳师范学
5、院数学与统计学院安阳师范学院数学与统计学院运筹学实验运筹学实验当余料没有用处时，当余料没有用处时，通常以总根数最少为目标通常以总根数最少为目标 76543212xxxxxxxZMin目标目标2（总根数）（总根数）约束条约束条件不变件不变 最优解：最优解：x2=15, x5=5, x7=5, 其余为其余为0；最优值：最优值：25。5023454321xxxxx20326542xxxx152753xxxxi 为整数按模式按模式2切割切割15根，根，按模式按模式5切割切割5根，根，按模式按模式7切割切割5根，根，共共25根，余料根，余料35米米 虽余料增加虽余料增加8米，但减少了米，但减少了2根根
6、与与目标目标1的结果的结果“共切割共切割27根，余料根，余料27米米” 相比相比 安阳师范学院数学与统计学院安阳师范学院数学与统计学院运筹学实验运筹学实验钢管下料问题钢管下料问题2 2对大规模问题，用模型的约束条件界定合理模式对大规模问题，用模型的约束条件界定合理模式增加一种需求：增加一种需求：5米米10根；切割根；切割模式不超过模式不超过3种。种。现有现有4种种需求：需求：4米米50根，根，5米米10根，根，6米米20根，根，8米米15根，用枚举法确定合理切割模式，过于复杂。根，用枚举法确定合理切割模式，过于复杂。决策变量决策变量 (15维)xi 按第按第i 种模式切割的原料钢管根数种模式切
7、割的原料钢管根数( (i= =1,2,3) ) r1i, r2i, r3i, r4i 第第i 种切割模式下，每根原料钢管种切割模式下，每根原料钢管生产生产4米、米、5米、米、6米和米和8米长的钢管的数量米长的钢管的数量 安阳师范学院数学与统计学院安阳师范学院数学与统计学院运筹学实验运筹学实验满足需求满足需求50313212111xrxrxr10323222121xrxrxr20333232131xrxrxr15343242141xrxrxr模式合理：每根模式合理：每根余料不超过余料不超过3米米1986541641312111rrrr1986541642322212rrrr19865416433
8、32313rrrr整数非线性规划模型整数非线性规划模型钢管下料问题钢管下料问题2 2目标函数（目标函数（总根数）总根数）321xxxMin约束约束条件条件整数约束：整数约束： xi ,r1i, r2i, r3i, r4i ( (i= =1,2,3) )为整数为整数 安阳师范学院数学与统计学院安阳师范学院数学与统计学院运筹学实验运筹学实验增加约束，缩小可行域，便于求解增加约束，缩小可行域，便于求解321xxx原料钢管总根数下界：原料钢管总根数下界：( (最佳切割方式最佳切割方式) ) 2619158206105504特殊生产计划特殊生产计划(简单切割方式简单切割方式)：对每根原料钢管：对每根原料
9、钢管模式模式1：切割成：切割成4根根4米钢管，需米钢管，需13根；根；模式模式2：切割成：切割成1根根5米和米和2根根6米钢管，需米钢管，需10根；根；模式模式3：切割成：切割成2根根8米钢管，需米钢管，需8根。根。原料钢管总根数上界：原料钢管总根数上界：31 3126321xxx模式排列顺序可任定模式排列顺序可任定 需求：需求：4米米50根，根，5米米10根，根，6米米20根，根，8米米15根根每根原料钢管长每根原料钢管长19米米 安阳师范学院数学与统计学院安阳师范学院数学与统计学院运筹学实验运筹学实验LINGOLINGO求解整数非线性规划模型求解整数非线性规划模型Local optimal
10、 solution found at iteration: 12211 Objective value: 28.00000Variable Value Reduced CostX1 10.00000 0.000000X2 10.00000 2.000000X3 8.000000 1.000000R11 3.000000 0.000000R12 2.000000 0.000000R13 0.000000 0.000000R21 0.000000 0.000000R22 1.000000 0.000000 R23 0.000000 0.000000 R31 1.000000 0.000000 R3
11、2 1.000000 0.000000 R33 0.000000 0.000000 R41 0.000000 0.000000 R42 0.000000 0.000000 R43 2.000000 0.000000 模式模式1：每根原料钢管切割成：每根原料钢管切割成3根根4米和米和1根根6米钢管，共米钢管，共10根；根；模式模式2：每根原料钢管切割成：每根原料钢管切割成2根根4米、米、1根根5米和米和1根根6米钢管，米钢管，共共10根；根；模式模式3：每根原料钢管切割成：每根原料钢管切割成2根根8米钢管，共米钢管，共8根。根。原料钢管总根数为原料钢管总根数为28根。根。 安阳师范学院数学与统计
12、学院安阳师范学院数学与统计学院运筹学实验运筹学实验 某人打算外出旅游并登山，路程比较远，途中要坐火车和飞机，考虑要带许多必要的旅游和生活用品，例如照相机、摄像机、食品、衣服、雨具、书籍等等，共n件物品，重量分别为ai，而受航空行李重量限制，以及个人体力所限，能带的行李总重量为b，n件物品的总重量超过了b，需要裁减，该旅行者为了决策带哪些物品，对这些物品的重要性进行了量化，用ci表示，试建立该问题的数学模型这个问题称为背包问题(Knapsack Problem)背包问题背包问题 安阳师范学院数学与统计学院安阳师范学院数学与统计学院运筹学实验运筹学实验.,2 , 1,0或1,s.t.,max1ni
13、xbxaxcziiiniii 解：解：若引入0-1型决策变量xi，xi=1表示物品i放入背包中，否则不放，则背包问题等价于如下0-1线性规划： 假设现有8件物品，它们的重量分别为1,3,4,3,3,1,5,10(kg)，价值分别为2,9,3,8,10,6,4,10(元)，假如总重量限制不超过15kg，试决策带哪些物品，使所带物品的总价值最大 安阳师范学院数学与统计学院安阳师范学院数学与统计学院运筹学实验运筹学实验 编写LINGO程序如下： MODEL: SETS: WP/W1.W8/:A,C,X; ENDSETS DATA: A=1 3 4 3 3 1 5 10; C=2 9 3 8 10 6
14、 4 10; ENDDATA MAX=SUM(WP:C*X); !目标函数; FOR(WP:BIN(X); !限制X为0-1变量; SUM(WP:A*X)=15; END 求解得到结果：带16号物品，总价值为38 安阳师范学院数学与统计学院安阳师范学院数学与统计学院运筹学实验运筹学实验 选址问题选址问题 某公司有某公司有6个建筑工地，位置坐标为个建筑工地，位置坐标为(ai, bi) (单位：单位：公里公里),水泥日用量水泥日用量di (单位：吨）单位：吨）假设：假设：料场料场和工地之间和工地之间有直线道路有直线道路 安阳师范学院数学与统计学院安阳师范学院数学与统计学院运筹学实验运筹学实验用例中
15、数据计算，最优解为i1234561ic（料料场场 A）3507012ic（料料场场 B）00406102 , 1,6,.,1,. .)()(min612121612/122jecidctsbyaxcjijiiijjjiijijij线性规划模型线性规划模型决策变量：决策变量：ci j (料场料场j到到工地工地i的的运量）运量）12维维 安阳师范学院数学与统计学院安阳师范学院数学与统计学院运筹学实验运筹学实验选址问题：选址问题：NLPNLP2）改建两个新料场，需要确定新料场位置）改建两个新料场，需要确定新料场位置(xj,yj)和和运量运量cij ，在其它条件不变下使总吨公里数最小。，在其它条件不变
16、下使总吨公里数最小。2 , 1,6,.,1,. .)()(min612121612/ 122jecidctsbyaxcjijiiijjjiijijij决策变量：决策变量：ci j，(xj,yj)16维维非线性规划模型非线性规划模型 安阳师范学院数学与统计学院安阳师范学院数学与统计学院运筹学实验运筹学实验LINGO模型的构成：模型的构成：4个段个段集合段（集合段（SETS ENDSETS）数据段（数据段（DATA ENDDATA）初始段（初始段（INIT ENDINIT） 目标与目标与约束段约束段 局部最优：局部最优：89.8835(吨公里吨公里 ) LP：移到数据段：移到数据段 安阳师范学院数
17、学与统计学院安阳师范学院数学与统计学院运筹学实验运筹学实验边界 安阳师范学院数学与统计学院安阳师范学院数学与统计学院运筹学实验运筹学实验例例: : 某班某班8名同学准备分成名同学准备分成4个调查队个调查队(每队两人每队两人)前往前往4个地区个地区进行社会调查进行社会调查,假设这假设这8名同学两两之间组队的效率如下表名同学两两之间组队的效率如下表,问问:如何组队可以使总效率最高如何组队可以使总效率最高? 学生学生 S1 S2 S3 S4 S5 S6 S7 S8S19342156S2173521S344292S41552S5876S623S74S888,()1188,11max. .1,1()01
18、i ji jijjii ji ji jijB Ms tMMijM或指派问题指派问题 安阳师范学院数学与统计学院安阳师范学院数学与统计学院运筹学实验运筹学实验model:sets: students/s1.s8/; pairs(students, students)|2#gt# 1, BENEFIT, MATCH;EndsetsData BENEFIT= 9 3 4 2 1 5 6 1 7 3 5 2 1 4 4 2 9 2 1 5 5 2 8 7 6 2 3 4enddata 安阳师范学院数学与统计学院安阳师范学院数学与统计学院运筹学实验运筹学实验objective MAX = SUM( PAIRS( I, J): BENEFIT( I, J) * MATCH( I, J);constraints FOR(STUDENTS(I): SUM( PAIRS( J, K) | J #EQ# I #OR# K #EQ# I: MATCH( J, K) =1); FOR(PAIRS( I, J): BIN( MATCH( I, J);
