LINGO模型实例及求解

安阳师范学院数学与统计学院运筹学实验LINGO模型实例与求解下料问题背包问题选址问题指派问题安阳师范学院数学与统计学院运筹学实验问题1.如何下料最节省?下料问题问题2.客户增加需求：原料钢管:每根19米4米50根6米20根8米15根客户需求节省的标准是什么？由于采用不同切割模式太多，会增加生产和管理成本，规定切割模式不能超过3种。如何下料最节省？5米10根安阳师范学院数学与统计学院运筹学实验按照客户需要在一根原料钢管上安排切割的一种组合。切割模式余料1米4米1根6米1根8米1根余料3米4米1根6米1根6米1根合理切割模式的余料应小于客户需要钢管的最小尺寸余料3米8米1根8米1根钢管下料安阳师范学院数学与统计学院运筹学实验为满足客户需要，按照哪些种合理模式，每种模式切割多少根原料钢管，最为节省？合理切割模式2.所用原料钢管总根数最少模式4米钢管根数6米钢管根数8米钢管根数余料(米)14003231013201341203511116030170023钢管下料问题1两种标准1.原料钢管剩余总余量最小安阳师范学院数学与统计学院运筹学实验xi~按第i种模式切割的原料钢管根数(i=1,2,…7)约束满足需求决策变量目标1（总余量）765432113333xxxxxxxZMin5023454321xxxxx20326542xxxx152753xxx按模式2切割12根,按模式5切割15根，余料27米模式4米根数6米根数8米根数余料14003231013201341203511116030170023需求502015最优解：x2=12,x5=15,其余为0；最优值：27整数约束：xi为整数安阳师范学院数学与统计学院运筹学实验当余料没有用处时，通常以总根数最少为目标76543212xxxxxxxZMin目标2（总根数）约束条件不变最优解：x2=15,x5=5,x7=5,其余为0；最优值：25。5023454321xxxxx20326542xxxx152753xxxxi为整数按模式2切割15根，按模式5切割5根，按模式7切割5根，共25根，余料35米虽余料增加8米，但减少了2根与目标1的结果“共切割27根，余料27米”相比安阳师范学院数学与统计学院运筹学实验钢管下料问题2对大规模问题，用模型的约束条件界定合理模式增加一种需求：5米10根；切割模式不超过3种。现有4种需求：4米50根，5米10根，6米20根，8米15根，用枚举法确定合理切割模式，过于复杂。决策变量(15维)xi~按第i种模式切割的原料钢管根数(i=1,2,3)r1i,r2i,r3i,r4i~第i种切割模式下，每根原料钢管生产4米、5米、6米和8米长的钢管的数量安阳师范学院数学与统计学院运筹学实验满足需求50313212111xrxrxr10323222121xrxrxr20333232131xrxrxr15343242141xrxrxr模式合理：每根余料不超过3米1986541641312111rrrr1986541642322212rrrr1986541643332313rrrr整数非线性规划模型钢管下料问题2目标函数（总根数）321xxxMin约束条件整数约束：xi,r1i,r2i,r3i,r4i(i=1,2,3)为整数安阳师范学院数学与统计学院运筹学实验增加约束，缩小可行域，便于求解321xxx原料钢管总根数下界：(最佳切割方式)2619158206105504特殊生产计划(简单切割方式)：对每根原料钢管模式1：切割成4根4米钢管，需13根；模式2：切割成1根5米和2根6米钢管，需10根；模式3：切割成2根8米钢管，需8根。原料钢管总根数上界：313126321xxx模式排列顺序可任定需求：4米50根，5米10根，6米20根，8米15根每根原料钢管长19米安阳师范学院数学与统计学院运筹学实验LINGO求解整数非线性规划模型Localoptimalsolutionfoundatiteration:12211Objectivevalue:28.00000VariableValueReducedCostX110.000000.000000X210.000002.000000X38.0000001.000000R113.0000000.000000R122.0000000.000000R130.0000000.000000R210.0000000.000000R221.0000000.000000R230.0000000.000000R311.0000000.000000R321.0000000.000000R330.0000000.000000R410.0000000.000000R420.0000000.000000R432.0000000.000000模式1：每根原料钢管切割成3根4米和1根6米钢管，共10根；模式2：每根原料钢管切割成2根4米、1根5米和1根6米钢管，共10根；模式3：每根原料钢管切割成2根8米钢管，共8根。原料钢管总根数为28根。安阳师范学院数学与统计学院运筹学实验某人打算外出旅游并登山，路程比较远，途中要坐火车和飞机，考虑要带许多必要的旅游和生活用品，例如照相机、摄像机、食品、衣服、雨具、书籍等等，共n件物品，重量分别为ai，而受航空行李重量限制，以及个人体力所限，能带的行李总重量为b，n件物品的总重量超过了b，需要裁减，该旅行者为了决策带哪些物品，对这些物品的重要性进行了量化，用ci表示，试建立该问题的数学模型．这个问题称为背包问题(KnapsackProblem)．背包问题安阳师范学院数学与统计学院运筹学实验.,,2,1,0或1,s.t.,max1nixbxaxcziiiniii•解：若引入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=134331510;•C=2938106410;•ENDDATA•MAX=@SUM(WP:C*X);!目标函数;•@FOR(WP:@BIN(X));!限制X为0-1变量;•@SUM(WP:A*X)=15;•END•求解得到结果：带1~6号物品，总价值为38．安阳师范学院数学与统计学院运筹学实验选址问题某公司有6个建筑工地，位置坐标为(ai,bi)(单位：公里),水泥日用量di(单位：吨）i１２３４５６a1.258.750.55.7537.25b1.250.754.7556.57.75d35476111)现有2料场，位于A(5,1),B(2,7),记(xj,yj),j=1,2,日储量ej各有20吨。假设：料场和工地之间有直线道路目标：制定每天的供应计划，即从A,B两料场分别向各工地运送多少吨水泥，使总的吨公里数最小。安阳师范学院数学与统计学院运筹学实验用例中数据计算，最优解为i1234561ic（料场A）3507012ic（料场B）0040610总吨公里数为136.22,1,6,...,1,..])()[(min612121612/122jecidctsbyaxcjijiiijjjiijijij线性规划模型决策变量：cij(料场j到工地i的运量）~12维安阳师范学院数学与统计学院运筹学实验选址问题：NLP2）改建两个新料场，需要确定新料场位置(xj,yj)和运量cij，在其它条件不变下使总吨公里数最小。2,1,6,...,1,..])()[(min612121612/122jecidctsbyaxcjijiiijjjiijijij决策变量：cij，(xj,yj)~16维非线性规划模型安阳师范学院数学与统计学院运筹学实验LINGO模型的构成：4个段集合段（SETSENDSETS）数据段（DATAENDDATA）初始段（INITENDINIT）目标与约束段局部最优：89.8835(吨公里)LP：移到数据段安阳师范学院数学与统计学院运筹学实验边界安阳师范学院数学与统计学院运筹学实验例:某班8名同学准备分成4个调查队(每队两人)前往4个地区进行社会调查,假设这8名同学两两之间组队的效率如下表,问:如何组队可以使总效率最高?学生S1S2S3S4S5S6S7S8S19342156S2173521S344292S41552S5876S623S74S888,,()1188,,,11max..1,1()01ijijijjiijijijijBMstMMijM或指派问题安阳师范学院数学与统计学院运筹学实验model:sets:students/s1..s8/;pairs(students,students)|＆2#gt#＆1,BENEFIT,MATCH;EndsetsDataBENEFIT=9342156173521442921552876234enddata安阳师范学院数学与统计学院运筹学实验[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)));