规划建模培训2

1、线性规划一一整数规划一.概念如果一个数学规划的某些决策变量或全部决策变量要求必须取整数，则 这样的问题称为整数规划问题，其模型称为整数规划模型。如果一个整数规划的目标函数和约束都是线性的，则称此问题为整数线性规划问题，其一般形式为nmax(min) zcjxjj is.tnaijXj ( , )bi(i 1,2,L , m)jiXj 0,Xj 为整数(j 1,2,L ,n)二.求解举例例1max x1 x2s.t2x, x2 6 TOC o 1-5 h z HYPERLINK l bookmark18 o Current Document 4x1 5x220 x1，x2 0,并且x取整数其LI

2、NGO 语句如下：略三.线性整数规划(IP)实例 求解IP用的是分支定界法例1某部门一周中每天需要不同数目的雇员：周一到周四每天至少需要50人，周五至少需要80人，周六周日每天至少需要 90人，现规定应 聘者需连续工作5天，试确定聘用方案，即周一到周日每天聘用多少人，使在满足需要的条件下聘用总人数最少。优化模型X1+x4+x5+x6+x7=50inin 二=3 + 小 + * + a4 +- a % + Xyst.Vj + x + x5 + / + 力-50Xj + x3 + 汗6 + X?2 50工+工2 +式3 + 丁4 +工7之50M + A j + Xj + 工4 + As SO.V%

3、 + x3 4- .v4 + x6 9013 + .v 90 xt 0(7 = L27)xi都是整数“Best IP : 94”表示当前得到的最好的整数解的目标函数值为94 （人）.“IP Bound: 93.5 ”表示该整数规划目标值的下界为93.5 （人）.“Branches: 1 ”表示分支数为1 （即在第1个分支中就找到了最优解）.我们前面说过，LINDO求解IP用的是分支定界法.显然，上面第二条“整数规划目标值的下界为 93.5 （人）”表明至少 要 聘用93.5名员工，由于人数只能是整数，所以至少要聘用94 （人）.而第一条说明目前得到的解就是聘用 94 （人），所以已经是最优的了

4、 .报告窗口 中前两行告诉我们，在8次迭代后找到对应的线性规划 （LP）问题的最优 解，最优值等于93.3333359.LINDO 求解IP用的是分支定界法， 紧接着 几行显示的是分支定界的信息，在第 1个分支中设定 X2=4,并在 该分支 中找到了整数解，而且就是全局整数最优解，所以算法停止.旋转迭代（PIVOTS）共18次.后面显示的是最后的最优解X= （0, 4, 40, 2, 34, 10,4).松弛和剩余变量(SLACK OR SUPLUS仍然可以表示约束的松紧程度， 但目前IP尚无相应完善的敏感性分析理论，因此REDUCED COS而DUALPRICES的结果在整数规划中的意义不大

5、.备注：尽管LINDO对整数规划问题很有威力，但要想有效地使用，有时还是需要一定的技巧的。 这是因为，人们很容易将一个本质上很简单的问题列 成一个不太好的输入模型，从而有可能导致一个冗长的分支定界计算。遗憾的是，我们往往难以预先估计什么样的模型才能避免冗长的分支定界计算，也难以判别什么样的模型是“不太好”的输入模型。当然这 时LINDO会主动砍去一些计算过程，以缩短计算时间，而且越是高版本的LINDO软件，这种自动处理的“智能”越强 .我们的建议是：如果分支 定界计算时间很长 仍得不到最优解，你可以试试对输入模型进行一些等价交换：如交换变量的次序，交换约束的顺序等。 有时也许会对减少求解的所需

6、的时间有所帮助.整数规划在lingo 中的求解：以例1为例，输入模型见图4-3 ,注意 以下几点：1) 语句的顺序不重要；2)限定变量取整数的语句“ GIN(X1)和“ GIN(X2);3)在lingo 中，以“开头的都是函数调用，lingo中的函数一律需要 以“开头。如约束中gin(x1)表示xi为整数，用 bin(x1)表示Xi 为0-1整数。T.TWGQ - LINGO lodel - LOGOIFdft idit u tfiiiiow图4召例1的Eng。输入模型例2:钢管下料问题某钢管零售商从钢管厂进货，将钢管按照顾客要求的长度进行切割，称为下料。假定进货时得到的原料钢管长度都是19m

7、。1）现有一客户需要 50根长4m、20根长6m和15根长8m的钢管。应 如何下料最节省？2）零售商如果采用的不同切割模式太多，将会导致生产过程的复杂化，从而增加生产和管理成本。所以该零售商规定采用的不同切割模式不能超过 3种。此外。该客户除需要 1）中的3种钢管外，还要10根长5m的钢管。 应如何下料最节省？问题分析：对于下料问题首先要确定采用哪些切割模式。所谓切割模式，是指按照顾客要求的长度在原料钢管上安排切割的一种组合。例如，我们可以将19m的钢管切割成3根长4m的钢管，余料为7m；或者将长19m的钢 管切割成长4m、6m和8m的钢管各1根，余料为1m。显然，可行的切割 模式是很多的。其

8、次，应当明确哪些切割模式是合理的。合理的切割模式通常还假设余料不应大于或等于客户需要钢管的最小尺寸。例如，可以将长19m的钢管切割成3根4m的钢管是可行的，但余料为7m,可进一步将7m的余料切割成4m钢管（余料为3m）,或者将7m的余料切割成6m钢管（余料为1m）。 经过简单的计算可知，问题1）的合理切割模式一共有 7种，如表1所示：于是问题转化为在满足客户需要的条件下，按照哪几种合理的模式， 每种模式切割多少根原料钢管最为节省。 而所谓节省，可以有两种标准，一是 切割后剩余的总余料量最小，二是切割原料钢管的总根数最少。 下面将对这 两个目标分别讨论。问题1） 用Xi表示按照表1第i种模式（i

9、=1,2,7）切割的原料钢管的根数，若以切割后剩余的总余料量最小为目标，则按照表1最后一列可得minZ1 = 3x1+x2+3x3+3x4+x5+x6+3x7若以切割原料钢管的总根数最少为目标，则有表1钢管下料问题1）的合理切割模式模式4m钢管根数6m钢管根数8m钢管根数余料/m14003231013201341203511116030170022MinZ 2 = X1+X2+X3+X4+X5+X6+X7约束条件为客户的需求，按照表1应有4X1+3X2+2X3+X4+X 5 50X2+2X4+X5 + 3X6 20X3+X5+2X7 15最后，切割的原料钢管的根数Xi显然应当是非负整数（用 Z

10、表示整数集合，Z+表示非负整数集合）：xi Z+ ,i=1,2, ,7于是，问题1）归结为在约束条件下，使目标达到最小。显然这是线性 整数规划模型。钢管下料问题1)的求解以切割后剩余的总余料量最小为目标，建立LINGO模型:min= 3*x 1+x2+3*x 3+3*x 4+x5+x6+3*x 7；4*X 1+3*x 2+2*x 3+x4+x5 =50;x2+2*x4+x5+3*x6 = 20;x3+x5+2*x 7 = 15;gin(x1);gin(x2);gin(x3);求解可以得到最优解如下：OBJECTIVE FUNCTION V ALUE1)27.00000VARIABLEVALUE

11、REDUCED COSTX10.0000003.000000X212.0000001.000000X30.0000003.000000X40.0000003.000000X515.0000001.000000X60.0000001.000000X70.0000003.000000即按照模式2切割12根原料钢管，按照模式5切割15根原料钢管，共 27根，总余料量27m。显然，在总余料量最小的目标下，最优解将是使用 余料尽可能小的切割模式 （模式2和模式5的余料为1m）,这会导致切割原 料钢管的总根数较多。以切割原料钢管的总根数最少为目标，建立LINGO模型：min= x1+x2+x3+x4+x5

12、+x6+x7;4*x 1+3*x 2+2*x 3+x4+x5 =50;x2+2*x4+x5+3*x6 = 20;x3+x5+2*x 7 = 15;gin（x1）;gin(x2)；gin(x3)；gin(x4)；gin(x5)；gin(x6)；gin(x7);求解可以得到最优解如下:OBJECTIVE FUNCTION VALUE1)25.00000VARIABLEVALUEREDUCED COSTXi0.0000001.000000X215.0000001.000000X30.0000001.000000X40.0000001.000000X55.0000001.000000X60.00000

13、01.000000X75.0000001.000000即按照模式2切割15根原料钢管，按照模式 5切割5根原料钢管，按 照模式7切割5根原料钢管，共25根，总余料量35m。与上面得到的结果 相比，总余料量增加了 8m,但是所用的原料钢管的总根数减少了2根，在余料没有什么用途的情况下，通常选择总根数最少为目标。问题2)如果按照问题1)的办法处理，首先要通过枚举法确定哪些切割模式是合理的，并从中选出不超过 3种模式。而由于需求的钢管规格增 加到4种，所以枚举法的工作量较大。下面介绍一种带有普遍性的方法，可以同时确定切割模式和切割数量。同问题1) 一样，只使用合理的切割模式，其余料不应大于3m (因

14、为客户需要的钢管最小尺寸为4m,而本题中参数都是整数)。由于不同切割模式不能超过 3种，可以用用 xi表示按照第i种模式 (i=1,2,3)切割的原料钢管的根数。又设使用第i种切割模式下每根原料钢管生产长4m、5m、6m和8m的钢管数量分别为 卬，r3i, r4i。仅以使用的原料总根数最少为目标，即min xi+x2+x3满足客户需求的约束条件为riixi+ri2x2+ri3x3 50r21Xl + r22X2+r23X3 i0r3iXi + r32X2+r33X3 20r4iXi + r42X2+r43X3 i5每一种切割模式必须可行、合理，所以每根原料钢管的成品量不能超过i9m,也不能少于

15、 16m （余料不能大于 3mj）,于是160 4ri+5r2i+6r3i+8r4i i9i6 4r2+5r22+6r32+8r42 i9i6 4i3+5r23+6r33+8r43 X2 X3又如，注意到所需原料钢管的总根数有明显的上界和下界。首先，原料钢管的根数不可能少于4 50 5 i0 6 20 8 i5 26 （根）。其次，i9考虑一种非常特殊的生产计划：第一种切割模式下只生产4m钢管，一根原料钢管切割成4根4m钢管，为满足50根4m钢管的需求，需要 i3根原料 钢管；第二种切割模式下只生产5m, 6m钢管，一根原料钢管切割成i根5m钢管和2根6m钢管，为满足i0根5m和20根6m钢管

16、的需求，需要 i0根原料钢管；第三种切割模式下只生产8m钢管，一根原料钢管切割成 2根8m钢管，为满足i5根8m钢管的需求，需要8根原料钢管。于是满足要 求的这种生产计划共需要 i3+i0+8=3i根原料钢管，这就得到了最优解的一个上界，所以可增加以下约束:26=50; *x i+r 22*x 2+r23*x 3=i0；r3i *x i+r 32*x 2+r33*x 3 =20;r4i *x i+r42*x 2+r43*x 3=i5;4*rii+5*r 2i+6*r 3i+8*r 4i=i9;4*ri2+5*r 22+6*r 32+8*r 42=i9;4*ri3+5*r 23+6*r 33+8

17、*r 43=i6;4*ri2+5*r 22+6*r 32+8*r 42=i6;4*ri3+5*r 23+6*r 33+8*r 43=i6;xi+x2+x3=26;xi+x2+x3=x2;x2=x3;gin(xi);gin(x2);gin(x3);gin(门1);gin(门2);gin(门3);gin(r2i);gin(r22);gin(r23);gin(r3i);gin(r32);gin(r33);gin(r4i);gin(r42);gin(r43);i22ii得到输出如下：i22iiLocal optimal solution found at iteration:Objective val

18、ue:28.00000VariableValueReduced CostXii0.000000.000000X2i0.000002.000000X38.000000i.000000rii3.0000000.000000ri22.0000000.000000r130.0000000.000000r210.0000000.000000r221.0000000.000000r230.0000000.000000r311.0000000.000000r321.0000000.000000r330.0000000.000000r410.0000000.000000r420.0000000.000000r

19、432.0000000.000000即按照模式1, 2, 3分别切割10根，10根，8根原料钢管，使用原料钢管总根数为28根。第一种切割模式下一根原料钢管切割成 3根4m钢管 和1根6m钢管；第二种切割模式下一根原料钢管切割成2根4m钢管，1根5m钢管和1根6m钢管；第三种切割模式下一根原料钢管切割成 2根8m 钢管。10例3、飞行计划问题这个问题是以第二次世界大战中的一个实际问题为背景，经过简化而提出来的。在甲、乙双方的一场战争中，一部分甲方部队被乙方部队包围长达 4个月。由于乙方封锁了所有水陆交通通道，被包围的甲方部队只能依靠空 中交通维持供给。运送 4个月的供给分别需要 2, 3, 3,

20、 4次飞行，每次飞 行编队由50架飞机组成（每架飞机需要 3名飞行员），可以运送10万t物 质。每架飞机每个月只能飞行一次，每名飞行员每个月也只能飞行一次。在执行完运输任务后的返回途中有20%的飞机会被乙方部队击落，相应的飞行员也因此牺牲或失踪。在第1个月开始时，甲方拥有 110架飞机和330名熟练的飞行员。在每个月开始时，甲方可以招聘新飞行员和购买新飞机。 新飞机必须经过一个月的检查后才可以投入使用，新飞行员必须在熟练飞行员的指导下经过一个月的训练才能投入飞行。每名熟练飞行员可以作为教练每个月指导20名飞行员（包括他自己在内）进行训练。每名飞行员在完成 一个月的飞行任务后， 必须有一个月的带

21、薪假期， 假期结束后才能再投入飞 行。已知各项费用（单位略去）如下表所示，请为甲方安排一个飞行计划。第1个月第2个月第3个月第4个月新飞机价格200. 0195. 0190. 0185. 0闲置的熟练 飞行员报酬7. 06. 96. 86. 7教练和新飞 行员报酬（包 括培训费用）10. 09. 99. 89. 7执行飞行任 务的熟练飞 行员报酬9. 08. 99. 89. 7休假期间的 熟练飞行员 报酬5. 04. 94. 84. 7飞行计划的原始数据如果每名熟练飞行员可以作为教练每个月指导不超过20名飞行员（包括他自己在内）进行训练，模型和结果有那些改变？11A1A2A3B13015181

22、B2204050习题习题4-21.用机床A1、A2、A3加工零件B1和B2,零件数相等。日产量（个 /日） 如下表，如何生产使总产量最多？max =x11+x12+x21+x22+x31+x32;x11=30;x12=20;x21=15;x22=40;x31=18;x32=50;x11+x21+x31=x12+x22+x32;gin (x11); gin (x12); gin (x21); gin (x22); gin (x31); gin (x32); Global optimal solution found.Objective value:126.0000Extended solver

23、steps:0Total solver iterations:0VariableValueReducedCostX1130.00000-1.000000X1220.00000-1.000000X2115.00000-1.000000X220.000000-1.000000X3118.00000-1.000000X3243.00000-1.000000Row Slack or Surplus DualPrice1126.00001.00000020.0000000.000000121230,0000000.00000040,0000000.000000540.000000.00000060,00

24、00000.00000077,0000000.00000080,0000000.0000002. 一家24小时自助餐厅在 24小时内需要的服务员人数如下表：起止时间2-66-1010-1414-1818-2222-2最少人数48107124每个服务员每天连续工作 8小时。问：（1）该餐厅最少需要招聘几个服务员？（2）劳动法规定，每个工作人员每星期至少休息1天。加上此限制，最少应该招聘几个服务员？3,某军用与民用计算机硬件制造商目前正在生产民用器件E-1200、E-1500,每个纯利分别为$50、$40。加工时间与日加工能力如下表：车间E-1200E-1500车间能力（每天小时数）1203002

25、0354032244041 . 21 . 5300假设所有产品都能卖掉，制定最佳生产方案；假设E-1200的纯利减少$10,制定最佳生产方案；假设此公司获准生产军用产品 Z-1800 ,其在四个车间的加工时间分别为 0.1 小时、3.6小时、2.2小日1.2小时，每个纯利为$55,民用产品的纯利同（1）, 制定最佳生产方案。4.（总运力问题）某卡车公司拨款 种运输工具可供选择：A的载重量10吨，平均时速B的载重量20吨，平均时速C的载重量18吨，平均时速800万元用于购买新的运输工具，有45千米，价格26万元；40千米，价格36万元；40千米，价格42万元。13其中，C是B的变种，新设了一个卧

26、铺，所以载重降低了、价格上升了。A需要1名司机，如果每天三班工作，每天可运行18小时.当地法律规定B和C均需要两名司机，如果三班工作，B每天可运行18小时，C可运行21小时.该公司目前每天有 150名司机可用，短期内无法招募到其他 训练有素的司机。当地工会禁止司机每天工作超过一个班次。此外，受维修保障能力的限制，公司最多能拥有30辆运输工具。请你建立数学模型，确定A、B、C的数量使得公司的总运力最大。5.（机票的销售策略）在四个城市A、B、C、H之间，有唯家航空公司提供三个航班，这三个航班的“出发地 一目的地”分别为 AH、HB、HC, 可搭载旅客的最大数量分别为120人、100人、110人，

27、机票的价格分头等舱和经济舱两类。经过市场调查，公司销售部得到了每天旅客的相关信息， 见下表。该公司应该在每条航线上分别分配多少张头等舱和经济舱的机票？出发地一目的 地头等舱需求/ 人头等舱价格/ 人经济舱需求/ 人经济舱价格/人AH331905690AB（经H转机）2424443193AC（经H转机）1226167199HB441406980HC16186171031、 一汽车厂生产小.中.大三种类型的汽车，已知各类型每辆车对钢材.劳动时间的需求，利润以及每月工厂钢材.劳动时间的现有量如表 2-3所示。由于各种条件限制，如果生产某一类型汽车，则至少要生产80辆，试制定月生产计划，使工厂的利润最

28、大。表2-3汽车生产数据小型中型大暨现有量钢楸1.535600劳动时间也2802504006000利泡万元234.两个汽车公司春运期间为三条线路增派汽车，甲公司可提供12辆，乙公14 司可提供20辆；A线路需9辆，B线路需15辆，C线路需8辆。已知甲公 司运营 A B C三线的距离依次为 10公里、5公里、6公里；乙公司运营 A B、C三线的距离依次为 4公里、8公里、15公里。若每辆每公里的运营费 为常数a元，则甲公司供应给 A B、C三线各多少辆，使总运营费用最省？.某机车厂在 A B两处分厂分别有库存机车 16台、12台，现要运往甲、 乙两地，其中甲地15台，乙地13台。已知从A地运一台

29、机车到甲地的运费 为5000元，到乙地的运费为 4000元；从B地运一台机车到甲地的运费为 3000元，到乙地的运费为 6000元。问应设计怎样的调运方案，才能使这些 机车的总运费最省？此时总运费是多少？. A市、B市和C市分别有某种机器 10台、10台和8台。现在决定把这些 机器支援给 D市18台、E市10台。已知从 A市调运一台机器到 D市、E市 的运费分别为200元和800元；从B市调运一台机器到 D市、E市的运费分 别为300元和700元；从C市调运一台机器到 D市、E市的运费分别为 400 元和500元。设从A市、B市各调x台机器到D市，当28台机器全部调运完毕后，求总 运费W（元）关于x（台）的函数式，并求W的最小值和最大值；设从A市调x台到