第四章-整数规划.pptVIP

运用Excel求解 产品互斥问题 在实际生产过程中，为了防止产品的过度多元化，有时需要限制产品生产的种类，这种就是产品互斥问题 处理产品互斥问题时，采用处理固定成本问题的方法，引入隐性0-1变量；第 i 种产品是否生产 yi（1表示生产，0表示不生产） 因此，在n种产品中，最多只能生产k种的约束为： 以及产量 xi 与是否生产 yi 之间的关系 包含互斥产品的例1.1。假设将例1.1的问题作如下的变形：两种新产品门和窗具有相同的用户，是互相竞争的。因此，管理层决定不同时生产两种产品，而是只能选择其中的一种进行生产。 问题分析 问题分析 决策变量 1. 设 、 分别表示门和窗的每周产量 目标函数 两种新产品的总利润最大，即 2. 设 、 分别表示是否生产门和窗（1表示生产，0表示不生产） 问题分析 约束条件 1. 原有的三个车间每周可用工时限制 2. 只能生产一种产品（产品互斥） 以及产量 与是否生产 之间的关系： 3. 产量 非负，是否生产 为0-1变量 混合0-1规划模型 规划求解 Excel规划求解 3 最少产量问题 在实际生产生活中，经常会碰到最少产量、最少订购量问题 处理最少产量问题时，采用处理固定成本问题的方法，引入隐性0-1变量；第 i 种产品是否生产 yi（1表示生产，0表示不生产） 因此，对于第i种产品，如果生产，最少生产Si的约束为： 以及产量 xi 与是否生产 yi 之间的关系 某公司需要购买5000个灯泡。公司已经收到三个供应商的投标，供应商1提供的灯泡，每个3元，一次最少订购2000个，最多3000个；供应商2提供的灯泡，每个5元，一次最少要订购1000个，多购不限；供应商3可供应3000个以内任意数量的灯泡，每个1元，另加固定费用5000元。公司决定从一家或两家购买。该公司正在考虑采取什么样的订购方案，可以使其所花的费用最少。 问题分析 决策变量 1. 设 、 、 分别表示从供应商1、2、3购买灯泡的数量 目标函数 公司所花的总费用最少，即 2. 设 、 、 分别表示是否从供应商1、2、3购买灯泡（1表示生产，0表示不生产） 问题分析——约束条件 1. 需要购买5000个灯泡： 2. 供应商1，一次最少订购2000个，最多订购3000个 3. 供应商2，一次最少订购1000个，多购不限 4. 供应商3可供应3000个以内任意数量的灯泡，另加固定费用5000元 问题分析——约束条件 5. 公司决定从一家或两家购买： 6. 购买灯泡数 非负，是否 购买为0-1变量 混合0-1规划模型： Excel规划求解 两个约束中选一个约束的问题 管理决策时，经常会遇到在两个约束中选一个的问题。 例如：某个投资方案有两个约束，但只要其中有一个成立就可以了，另外一个约束则不作要求 可以把这种问题转化为有0-1变量的混合整数规划问题。这样，需要引入一个0-1变量，来决定满足两个约束条件中的哪一个，这样的问题也是一个隐性0-1变量问题，用 y 表示： 也就是说，隐性0-1变量y取值为0时，受约束条件1的限制；y取值为1时，受约束条件2的限制 加入二选一约束的例1.1 假设将例1.1的问题作如下变形：公司最近建了一个与车间3类似的新车间（车间4），因此，新车间也可以参与两种新产品的生产。但是，由于管理上的原因，管理层决定只允许车间3和车间4中的一个车间参与新产品的生产，同时要选取能获得产品组合利润最大的那一个车间。相关数据如下表。 每个产品所需工时 每周可用工时 门 窗 车间1 1 0 4 车间2 0 2 12 车间3 3 2 18 车间4 2 4 28 单位利润（元） 300 500 问题分析 决策变量 1.设 、 分别表示门和窗的每周产量 目标函数 两种新产品的总利润最大，即 2. 隐性0-1变量：设 表示选择车间3， 表示选择车间4 问题分析——约束条件 1. 车间1和车间2的约束： 2. 选择车间3还是车间4： 为了强化这一定义，引入一个相对极大值M，然后模型中作如下变动 3. 产量xi非负，选择变量y为0-1变量，即 混合0-1规划模型 Excel规划求解 有时会遇到在一个规划问题中，有N个约束条件的情况，但只要求其中的K个约束条件成立，另外的N-K个约束条件则可以不要求成立（K≤N）。 N个约束中选K个约束的问题 特殊情况：当K=1，N=2时，这个问题便等价于前面所述的两个约束中选一个约束的问题。 假设N个可能的约束是： N个约束中选K个约束的问题 然后，采用同样的方法，引入一个相对极大值M，要使得这N个约束中只有K个成立