第3章 线性规划扩展(2012.09).ppt

1、管理定量方法与技术,1,管理定量方法与技术 管理运筹学,四川大学 工商管理学院 汪 贤 裕 2010.09,管理定量方法与技术,2,第3章 规划扩展 3.1 整数规划 3.2 非线性规划 3.3 目标规划,管理定量方法与技术,3,3.1整数规划 3.1.1整数规划概念 1. 纯整数规划：所有决策变量取整数值； 2. 混合整数规划：部分决策变量取整数值； 3. 01 整数规划：决策变量只能取 0 或 1 ； 01 整数规划又可分为01纯整数规划和 01 混合整数规划。 注：在LI N DO软件中,可在 end 后加： g i n 变量名 非负整数 i n t 变量名01变量,管理定量方法与技术,

2、4,3.1.2 一般整数规划案例,例3.1 工业原科的合理利用 要制作100套钢管架子，每套有长2.9米、2.1米、1.5米钢管各一根。原料钢管长7.4米。问应如何切割，使原料最省。,管理定量方法与技术,5,解：设第i个方案用原料xi 根。 则有下列线性规划模型： Min z = x1+ x2 + x3 + x4 + x5 + x6 + x7 + x8 s.t. 2x1+ x2 + x3 + x4 + 0 x5 + 0 x6 +0 x7 +0 x8 100 0 x1+ 2x2 + 1x3 + 0 x4 + 3x5 +2 x6 +x7+ 0 x8 100 . 1 x1+ 0 x2 +1x3+3

3、x4 + 0 x5 + 2x6+3x7 +4x8 100 xi 0 ，且取整数，i =1，2，8。 求解得最优解为：x*=（10,50, 0,30,0,0,0,0）,管理定量方法与技术,6,解2：设第i个方案用原料xi 根。 则有下列线性规划模型： Min z=0.1x1+0.3x2+0.9x3+0 x4+1.1x5+0.2x6+0.8x7+1.4x8 s.t. 2x1+ 1x2 + 1x3 +1 x4 + 0 x5 + 0 x6 +0 x7 +0 x8 100 0 x1+ 2x2 + 1x3 +0 x4 + 3x5 +2 x6 +1x7+ 0 x8 100 . 1 x1+ 0 x2 + 1x

4、3 + 3x4 + 0 x5 + 2x6+3x7 +4x8 100 xi 0 ，且取整数，i =1，2，8。 求解得最优解为：x*=（？，？，？） （解2和解1有什么不同，那一个正确？为什么？）,管理定量方法与技术,7,01整数规划案例,例3.2 匹配问题 某公司有甲乙丙三个销售员，需分别派到A、B、C三地工作。已知不同销售员在不同地点的收益预测为： 现要求每个地点只能派 1名销售员，且一名销售员只能到一个地点。问应如何安排工作，使总收益最大。,管理定量方法与技术,8,匹配问题（续）,解：设地点：A,B,C分别为：1，2，3； 设人员：甲，乙，丙分别为：1，2，3； 设：,管理定量方法与技术,

5、9,例3.3选址问题 某集团公司有1400万资金，拟在西藏自治区内进行藏药厂的投资建设。现有7个藏药厂项目通过初评，可以作为预选方案。各项目的年收益及所需投资额如下表： 由于2、4、5三项目生产产品相同，只能建其中一个；5、6、7三项目在同一地区，最多只能建两个。问该团公司应如何安排投资项目，使年收益最大。,管理定量方法与技术,10,解：设 x I 为对第 i 个项目投资（i = 1,2,7.）。 x i = 0 表示对第 i 个项目不投资， x i = 1 表示对第 i 个项目投资。 我们可以建立如下01整数规划模型： Max z = 30 x1100 x2200 x390 x4110 x5

6、50 x620 x7 s.t. 200 x1500 x2700 x3400 x4500 x5300 x6150 x71400 x2x4x51 x5x6x72 xi 取 0 或 1，i =1,2,7.,管理定量方法与技术,11,3.1.3 特殊约束的处理,1.互斥约束 （1）矛盾约束两个相互矛盾的约束，只要求其中一个起作用。 例：f 1（x）=5 （1） f 2（x）=0 （2） 引入一个01整数变量y和一个相当大的正常数M。构造： f 1 （x）5 = M（1y） （3） f 2 （x） =M y （4） 则y=0时（4）式表示（2）成立，而（1）不成立； y=1时，(3）式表示（1）成立，而

7、（2）不成立。,管理定量方法与技术,12,（2）多中选一的约束 例：f i（x）=0 i =1,2, ,n 其中n个约束中只有一个生效。 引入n个01整数变量yi yi，i =1,2, ,n和一个相当大的正常数M，构造： f i （x）=（1 yi ）M i=1,2, ,n y1 y2 yn =1 则yi =1时，第 i个约束起作用，而其它 n1个约束不起作用。,管理定量方法与技术,13,2.逻辑关系,逻辑关系：如果f（x）=M(1y) （1） f(x)My (2) g(x)=My (3) 若y=0, 必有：M= f(x) 0,则g(x)=0必然成立。 若y=1, 必有：0 =f(x) M,即

8、f（x）0不成立，g(x)=M必然成立，即g(x)无限制。,管理定量方法与技术,14,3.1.4 整数规划应用举例,例3.5 (背包问题) 一登山运动员要携带的物品如下表,各种物品的重量和重要性包含于表中。该运动员可携带的重量不能超过25公斤，且每种物品只能携带一件。问应如何携带。,管理定量方法与技术,15,例：3.6 华美公司有5个项目，投资额与投资收益见下表。,该公司只有600万元可用于投资，并受到如下约束： （1）在项目1、2和3中必须有一项被选中； （2）在项目3和4中只能选中一项； （3）项目5被选中的前提是项目1必须被选中。 如何设计一个好的投资方案，使投资收益最大。,管理定量方法

9、与技术,16,设x i为项目i是否投资。 x i =1表示要投资， 而x i =0表示不投资。i = 1,2, ,5. 下面主要就约束方程讨论： （1）在项目1、2和3中必须有一项被选中； x 1 + x 2 + x 3 1 （2）在项目3和4中只能选中一项； x 3 + x 4 1 （3）项目5被选中的前提是项目1必须被选中。 x 5 x 1 （4）资金约束 x 1 + x 2 + x 3 + x 4 + x 5 600,管理定量方法与技术,17,例3.7 集合覆盖和布点问题,解决某市人消防站的布点问题。该城市有六个区，每个区都可以建消防站。市政府希望设置消防站最少，但必须满足在发生火警时，

10、消防车要在15分钟内赶到现场。设各区之间消防车行驶时间如下表。请帮助设计一个最节省的计划。,管理定量方法与技术,18,设第 i 地区设消防站为x i ， x i =1表示没消防站， 而x i =0表示不设消防站。i =1，2，6。 Min z = x1+ x2+ x3+ x4+ x5+ x6 s.t. x1 + x2 1 x1 + x2 + x6 1 x3 + x4 1 x3 + x4 + x5 1 x4 + x5 + x6 1 x2 + x5 + x6 1 x i =1 或 x i =0 该问题的最优解为： x2 = x4 =1，其余为0。最优值z=2,管理定量方法与技术,19,例3.8 固

11、定费用问题,红光服装厂可生产三种服装：西服、衬衫和羽绒服。生产不同种类的服装需租赁使用不同的设备。设备租赁和其它经济参数见下表。假定市场需求不成问题，服装厂每月可用人工工时为2000小时，该厂如何安排生产可使每月利润最大？,管理定量方法与技术,20,设三种服装西服、衬衫、羽绒服的编号分别为1、2、3。 设备租赁变量为y i ， y i =1表示要租赁， y i =0表示不租赁。 i = 1, 2, 3. 生产产品数量为x i ， x i 0 。i = 1, 2, 3. Max z=120 x 1 +10 x 2 +100 x 35000 y 12000 y 21000 y3 s.t. 5 x

12、1 + x 2 +4 x 3 2000 3 x 1 300 y 1 0.5 x 2 300 y 2 2 x 3 300 y 3 x i 0 且为整数， y i = 0 或 1， i=1，2，3。,管理定量方法与技术,21,3.1.4 分段线性化的处理,x,(b,f(b),f (b1),f (b2),f ( b3 ),f (b4),f(x),0,b1,b2,b3,b4,f (b0),b0,管理定量方法与技术,22,满足：,并有：,可验证：y1=1时， y2=1时， y3=1时， y4=1时，,管理定量方法与技术,23,例3.10 某石油化工厂生产石油液化气。每公升可售0.6元。液化气的产量随操作

13、温度的升高而增加，具体情况且下图： 温度 0 200 400 600 800 产量 假设生产费用与操作温度成正比，每升高摄氏1度增加7.5元。问为获得最大利润，该厂应生产多少液化气。,10,20,30,40,管理定量方法与技术,24,设生产过程中温度为x，产量为f（x）。 （1）. 利润为： = 0.6 f（x）7.5x （2）.温度：0 x 40 b 0 =0， b 1 =10， b 2 =20， b 3 =40 （3）.产量：0 f（x） 800 f（ b 0 )=0， f( b 1 )=400，f ( b 2 )=600， f( b 3 )=800， （4）.取y i 表示x i在 b

14、i1, b i 内，此时y i =1；否则y i =0。且有： y 1 + y 2 + y 3 =1 （5）.由f（x）是x的分段线性函数，则： x =0 0+10 1 +20 2 +40 3 f（x）=0 0 +400 1 +600 2 +800 3 且有： 0 + 1 + 2 + 3=1,管理定量方法与技术,25,原问题的线性规划模型为： Max =0.6f（x）7.5x =0.60 0+400 1 +600 2 +800 3 7.5 0 0+10 1 +20 2 +40 3 s.t. 0 0 y 1 0 1 y 1 + y 2 0 2 y 2 + y 3 0 3 y 3 y 1 + y

15、2 + y 3 =1 0 + 1 + 2 + 3=1 y i =1 或0， i =1，2，3.,管理定量方法与技术,26,思考题：选址问题 一个公司考虑在北京、上海、广州和武汉设立库房，这些库房负责向华北、华南和华东地区发运货物，每个库房每月可处理货物1000件。在北京设立库房每月的成本方4.5万元，上海为5万元，广州为7万元，武汉为4万元。每个地区平均需求量为：华北地区每月600件，华东地区每月700件，华南地区每月600件。发运货物的费用见下表（单位：元/件）： 公司希望在满足地区需求的前提下使平均月成本最小，且还要满足以下条件： （1）若在上海设库房，则必需地在武汉设库房； （2）最多设

16、立两个库房； （3）武汉和广州不能同时设库房。 请建立满足上述要求的整数规划模型（不求解）。,管理定量方法与技术,27,3.2 非线性规划（略）,对上述非线性规划，可用LINGO软件进行数值计算。其操作方法类似LINDO软件。,管理定量方法与技术,28,3.3 目标规划,线性规划的延伸。 求解实际问题的满意解。,管理定量方法与技术,29,例：10 某一公司可生产三种产品，其生产要素及贡献如下表给出： 其它生产资源、市场需求等约束要素暂不考察。,管理定量方法与技术,30,该公司上层领导在讨论生产计划时，提出在满足资源约束、市场需求等前提下应考虑以下原则：（1）实施低成本战略；（2）保障现有职工的

17、就业，以实现社会稳定（3）确保基本的利润水平。 为实现上述原则，提出实现以下目标，依次为： 1.资本投入必须控制在55（百万元）之内； 2.确保雇佣职工在现有40（百人）基础上不变； 3.长期利润要超过125（百万元）。 问，该公司应计划部门如何制定满足以上目标的满意的生产计划。,管理定量方法与技术,31,目标规划的基本思想： 1.目标可以软化，尽可能地去实现； 目标转化为有一定“软性”的约束；原有的约束保持不变，称为：“刚性”约束； 2.按问题的要求建立新的以减少偏差为目的的新目标，新的目标应体现： （1）目标的层次， （2）同层次目标的不同权重。,管理定量方法与技术,32,目标规划的编制：

18、 1. 问题的目标和约束 （1）刚性约束：原所有的“刚性”约束不变； （2）目标转化为“软性”约束 问题的目标在加上下述两个偏差变量后，变为等式约束。 增加两个偏差变量d和d 。 d为正偏差变量， d为负偏差变量。满足： d 0， d 0， d d = 0 例如在此例中有：,管理定量方法与技术,33,长期利润，希望“”125（百万元） 12x19x2+15x3+ d1 d1= 125 雇佣水平，希望“=”40（百人） 5x1+3x2+4x3+ d2 d2 = 40 资本投入，希望“” ，目标为：min d1 希望“=” ，目标为：min （d2 d2 ） 希望“” ，目标为：min d3 按目

19、标的层次和相对权重设计新的目标。 以本题为例，新目标函数为： Min P1 d3 + P2 （d2 d2 ） + P3 d1,管理定量方法与技术,34,此例的最后线性目标规划为： Min P1 d3 + P2 （d2 d2 ） + P3 d1 s.t. 12x1 + 9x2 + 15x3 + d1 d1= 125 5x1 + 3x2 + 4x3 + d2 d2 = 40 5x1+7x2+8x3 + d3 d3 = 55 x1 0， x2 0， x3 0， d1 0， d1 0， d2 0， d2 0， d3 0， d3 0。 在目标规划中规定： P1 P2 P n 1.目标规划的计算是按目标层

20、次逐步计算。 2.当P1、P2、Pn给出具体数值，则是按标准的线性规划计算。 对目标规划可用WinQSB软件中的GPIGP程序求解。,管理定量方法与技术,35,例：11 . 某企业生产I、II两种产品，两种产品都需在A、B、C、D四种设备上加工。单位产品加工生产所需时间（h）、利润、设备可用加工时间（h）都见下表： 企业在生产计划中，C和D为贵重设备，严禁超时使用；其余各层次目标依次为： 第一目标：利润不低于12元； 第二目标：考虑到市场需求，I、II两种产品的比例保持在1 : 1； 第三目标：设备B必要时可以加班，加班要控制；设备A一旦工作，将连续进行，希望A的工时充分利用。这两者的重要比为

21、1: 3。,管理定量方法与技术,36,企业生产I、II两种产品分别为x 1, x 2 。 一般利润最大化线性规划：,线性目标规划：,管理定量方法与技术,37,例12：某企业生产A、B两种产品，其单位产品对劳动力的消耗和产生的利润见下表： 现产品A、B每月的市埸需求分别是不超出3000件和2500件。 企业领导的决策思想是： P1：每月对劳动力的雇用工时不得突破2000小时； P2：每月对利润要求要大于5000万元。 请制成该企业在当月的生产计划。,管理定量方法与技术,38,例3.13：某单位领导在考虑本单位职工的升级调资方案时，依次遵守以下规定： (1）不超过年工资总额600000元； (2）每级的人数不超过定编规定的人数； (3）II、III级的升级面尽可能在现有人数的20%,尽可能多提； (4）III级不足编制的人数可录用新职工，又I级的职工中有10%要退休。 有关资料汇总于下表，问该领导应如何拟定一个满意的方案。,管理定量方法与技术,39,例3.14 已知三个工厂生产的产品供应四个用户需要，各工厂的产量、用户需求量及从各个工厂到用户的单位产品的运费如江下表所示。按最少运费优化，总运费为2950元。