第3章线性规划扩展0609

第 3章 规划扩展3.1 整数规划 3.2 非线性规划3.3 目标规划3.1整数规划3.1.1整数规划概念整数规划概念1. 纯整数规划：所有决策变量取整数值；纯整数规划：所有决策变量取整数值；2. 混合整数规划：部分决策变量取整数值；混合整数规划：部分决策变量取整数值；3. 0 1 整数规划：决策变量只能取整数规划：决策变量只能取 0 或或 1 ；0 1 整数规划又可分为整数规划又可分为 0 1纯整数规划和纯整数规划和0 1 混合整数规划。混合整数规划。注：注： 在在 LI N DO软件中软件中 ,可在可在 end 后加：后加：g i n 变量名变量名 非负整数非负整数 i n t 变量名变量名 0 1变量变量3.1.2 一般整数规划案例例例 3.1 工业原科的合理利用工业原科的合理利用要制作要制作 100套钢管架子，每套有长套钢管架子，每套有长 2.9米、米、2.1米、米、 1.5米钢管各一根。原料钢管长米钢管各一根。原料钢管长 7.4米米。问应如何切割，使原料最省。问应如何切割，使原料最省。切割方案 1 2 3 4 5 6 7 8 需求量2.9米 1 2 1 1 1002.1米 2 1 2 3 1 1001.5来 3 1 1 2 3 4 100有效用料 7.4 7.3 7.1 6.5 7.2 6.3 6.6 6用 原料数 x1 x2 x3 x4 x5 x6 x7 x8解：设第 i个 方案用原料 xi 根。则 有 下列线性规划模型 ：Min z=x1+ x2 + x3 + x4 + x5 + x6 + x7 + x8s.t. x1+ 2x2 + x3 + x4 + 0x5 + 0x6 +0 x7 +0x8 1000 x1+ 0x2 + 2x3 + x4 + 2x5 +3 x6 +x7+ 0x8 100. 3 x1+ x2 + 0x3 + x4 + 2x5 + 0 x6+3x7 +4x8 100xi 0 ，且 取整数 ， i =1， 2， ， 8。求解得最优解为： x*=（ 30,10,50,0,0,0,0,0）解解 2：设第：设第 i个方案用原料个方案用原料 xi 根。根。则有下列线性规划模型则有下列线性规划模型 ：Min z=0x1+0.1x2+0.3x3+0.9x4+0.2x5+1.1x6+0.8x7+1.4x8 s.t. x1+ 2x2 + x3 + x4 + 0x5 + 0x6 +0 x7 +0x8 1000 x1+ 0x2 + 2x3 + x4 + 2x5 +3 x6 +x7+ 0x8 100. 3 x1+ x2 + 0x3 + x4 + 2x5 + 0 x6+3x7 +4x8 100xi 0 ， 且取整数 ， i =1， 2， ， 8。求解得最优解为 ： x*=（ 100,0, 0,0,50,0,0,0）（解 2和解 1有什么不同，那一个正确？为什么 ？）0 1整数规划案例例例 3.2 匹配问题匹配问题某公司有甲乙丙三个销售员，需分别派到某公司有甲乙丙三个销售员，需分别派到 A、B、 C三地三地 工作工作 。 已知不同销售员在不同地点的已知不同销售员在不同地点的收益预测为收益预测为 ：现要求每个地点只能派现要求每个地点只能派 1名销售员名销售员 ，且一名，且一名 销销售员只能到一个地点售员只能到一个地点 。问。问 应如何安排工作应如何安排工作 ，使，使总总 收益最大收益最大 。人 员 地点 A B C甲 20 40 40乙 30 10 40丙 40 50 60例例 3.3选址问题选址问题某集团公司有某集团公司有 1400万资金，拟在西藏自治区内进行藏万资金，拟在西藏自治区内进行藏药厂的投资建设。现有药厂的投资建设。现有 7个藏厂项目通过初评，可以作为个藏厂项目通过初评，可以作为预选方案。各项目的年收益及所需投资额如下表：预选方案。各项目的年收益及所需投资额如下表：由于由于 2、 4、 5三项目生产产品相同，只能建其中一个；三项目生产产品相同，只能建其中一个； 5、 6、 7三项目在同一地区，最多只能建两个。问该团公司三项目在同一地区，最多只能建两个。问该团公司应如何安排投资项目，使年收益最大。应如何安排投资项目，使年收益最大。序号 1 2 3 4 5 6 7所需投 资额（万元）200 500 700 400 500 300 150预计 年收益（万元）30 100 200 90 110 50 20解：设解：设 x I 为对第为对第 i 个项目投资（个项目投资（ i = 1,2,7. ）。）。x i = 0 表示对第表示对第 i 个项目不投资，个项目不投资，x i = 1 表示对第表示对第 i 个项目投资。个项目投资。我们可以建立如下我们可以建立如下 0 1整数规划模型：整数规划模型：Max z = 30x1 100x2 200x3 90x4 110x5 50x6 20x7s.t. 200x1 500x2 700x3 400x4 500x5 300x6 150x71400x2 x4 x51x5 x6 x72xi 取取 0 或或 1， i =1,2,7.3.1.3 特殊约束的处理1.互斥约束（ 1）矛盾约束两个相互矛盾的约束，只要求其中一个起作用。例： f（ x） =5 （ 1）f（ x） = M(1 y) （ 1）f(x)My (2)g(x)=My (3)若 y=0, 必有： M= f(x) 0,则 g(x)=0必然成立。若 y=1, 必有： 0 =f(x) M,即 f（ x） 0不成立，g(x)=0必然成立，即 g(x)无限制 。3.1.3 整数规划应用举例例 背包问题例 3.5 一登山运动员要携带的物品如下表 ,各种物品的重量和重要性包含于表中。该运动员可携带的重量不能超过 25公斤，且每种物品只能携带一件。问应如何携带。序号 1 2 3 4 5 6 7物品 食品 氧气 冰 镐 绳索 帐篷 照相器材 通讯设备重量（公斤） 5 5 2 6 12 2 4重要系数 20 15 18 14 8 4 10例： 3.6 华美公司有 5个项目，投资额与投资收益见下表。 项 目 投 资额 （万元） 投 资 收益（万元）1 210 1502 300 2103 100 604 130 805 260 180该 公司只有 600万元可用于投资，并受到如下约束：（ 1）在项目 1、 2和 3中必须有一项被选中；（ 2）在项目 3和 4中只能选中一项；（ 3）项目 5被选中的前提是项目 1必须被选中。如何设计一个好的投资方案，使投资收益最大。设 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例 集合覆盖和布点问题例 3.7 解决某市人消防站的布点问题。该城市有六个区，每个区都可以建消防站。市政府希望设置消防站最少，但必须满足在发生火警时，消防车要在 15分钟内赶到现场。设各区之间消防车行驶时间如下表。请帮助设计一个最节省的计划。地区 1 地区 2 地区 3 地区 4 地区 5 地区 6地区 1 0 10 16 28 27 20地区 2 10 0 24 32 17 10地区 3 16 24 0 12 27 21地区 4 28 32 12 0 15 25地区 5 27 17 27 15 0 14地区 6 20 10 21 25 14 0设第 i地区设消防站为 x i ， x i =1表示没消防站 ，而x i =0表示不设消防站 。 i =1， 2， ， 6。Max z = x1+ x2+ x3+ x4+ x5+ x6s.t. x1 + x2 1x1 + x2 + x6 1x3 + x4 1x3 + x4 + x5 1x4 + x5 + x6 1x2 + x5 + x6 1x i =1 或 x i =0该问题的最优解为 ：x2 = x4 =1， 其余为 0。最优值 z=2例 固定费用问题例 3.8 红光服装厂可生产三种服装：西服、衬衫和羽绒服。生产不同种类的服装需租赁使用不同的设备。设备租赁和其它经济参数见下表。假定市场需求不成问题，服装厂每月可用人工工时为 2000小时，该厂如何安排生产可使每月利润最大？序号服装种 类设 置租金元生 产成本元 /件销 售价格元 /件人工工 时小 时 /件设备工 时小 时 /件设备 可用工 时1 西服 5000 280 400 5 3 3002 衬 衫 2000 30 40 1 0.5 3003 羽 绒 服 3000 200 300 4 2 300设三种 服装西服、衬衫、羽绒服的编号分别为 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 3 5000 y 1 2000 y 2 1000 y3 s.t. 5 x 1 + x 2 +4 x 3 20003 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。例 旅行推销商问题例： 3.9 假定有 n个 城市 ， d i， j 表示从城市 i 到 城市 j 的距离 ， 并进一步假定旅行者从城市 1出发 ，且 城市间的距离与旅行的方向无关，即 d i， j = d j， i 。求 一个访问 n个 城市的旅行路线 ， 每个城市必须被访问到 ， 而且只能访问一次 ，并使 旅行距离最小 。解：设 0 1整数变量 x i， j ， x i， j = 1表示选择 i城到 j 城的 路线 ， x i， j = 0表示不选 。其线性整数规划模型为 ：3.1.4 分段线性化的处理f(b)f(b)f (b1)f (b2)f ( b3 )f (b4)f(x)0b1 b2 b3 b4例 3.10 某石油化工厂生产石油液化气。每公升可售 0.6元。液化气的产量随操作温度的升高而增加，具体情况且下图：温度产量0 200 400 600 800假设生产费用与操作温度成正比，每升高摄氏 1度增加7.5元。问为获得最大利润，该厂应生产多少液化气。10203040n 设 生产过程中温度为 x， 产量为 f（ x）。（ 1） . 利润为 ： = 0.6 f（ x） 7.5x（ 2） .温度 ： 0 x 40b 0 =0， b 1 =10， b 2 =20， b 3 =40（ 3） .产量 ： 0 f（ x） 800f（ b 0 )=0， f（ b 1 )=400， f（ b 2 )=600， f（ b 3 )=800，（ 4） .取 y i 表示 x i在 b i 1, 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 3f（ x） =0 0 +400 1 +600 2 +800 3且有： 0 + 1 + 2 + 3=1原 问题的线性规划模型为：Max =0.6f（ x） 7.5x=0.6 0 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 2 + y 3 =1 0 + 1 + 2 + 3=1y i =1 或 0， i =1， 2， 3.3.2 非线性规划（略）3.3 目标规划n线性规划的延伸。n求解实际问题的满意解 。例： 11 某一公司可生产三种产品，其生产要素及贡献如下表给出：其它生产资源、市场需求等约束要素暂不考察。要素 单 位 产 品的 贡 献A B C长 期利 润 （百万元）12 9 15雇佣水平（百人） 5 3 4资 本投入（百万元） 0.5 0.7 0.8该公司上层领导在讨论生产计划时，提出在满足资源约束、市场需求等前提下应考虑以下原则：（ 1）实施低成本战略；（ 2）保障现有职工的就业，以实现社会稳定（ 3）确保基本的利润水平。为实现上述原则，提出实现以下目标，依次为：1.资本投入必须控制在 55（百万元）之内；2.确保雇佣职工在现有 40（百人）基础上不变；3.长期利润要超过 125（百万元）。问，该公司应计划部门如何制定满足以上目标的满意