整数规划问题剖析.ppt

设 xj= 10 --- 决策j问题的答案是“是” --- 决策j问题的答案是“否” max z = 18x1 + 10x2 + 12x3+8x4 12x1 +6 x2 +10x3+ 4x4 ≤ 20 x3+ x4 ≤ 1 （建1个配送中心） x3 ≤ x1 x4 ≤ x2 xj = 0或1(j=1,2,3,4) 最优解 x1 =1，x2=1 案例练习 例1：某油田在10个有油气构造处要选择若干个钻探采油，设第j个构造开采时需投资aj元，投产后预计年收净益为cj元，若该油田投资的总限额为b元，问：应选择哪几个构造开采最为有利？ 设 xj= 10 --- 选择开采第j个构造 ---不选择开采第j个构造 max z=Σcjxj j=1 10 ∑ajxj? b xj＝0或1 (j=1,2,---,10) j=1 10 -----年总收益 ----投资额限制 1、表示选择性决策 若在开采时还需满足下述条件： （a）若开采8号，则必须同时开采6号； （b）若开采5号，则不许开采3号； （c） 2 号和4号至少开采一个； （d） 8 号与7号必须同时开采； （e）1号、4号、6号、9号开采时不能超过两个，试表示上述约束条件。 设 xj= 10 --- 选择开采第j个构造 ---不选择开采第j个构造 max z=Σcjxj j=1 10 ∑ajxj? b xj＝0或1 (j=1,2,---,10) j=1 10 -----年总收益 ----投资额限制 （a）当x8=1 x6=1，x6≠0 当x8=0 x6=1，x6=0 ∴ x8 ? x6　 （b）当x5 =1 x3=0， x3 ≠1 当x5 =0 x3=0， x3 =1 ∴　x5 + x3 ? 1 （c） x2 + x4 ? 1 （d） x8 = x7 （e） x1 + x4 + x6 + x9 ? 2 在生产或经营过程中，某一个业务活动开展通常伴随着固定成本的发生，比如添置或起用设备，新采购材料时产生的差旅费，对工人必要培训的费用等，这些构成产品的固定成本。这时，业务活动的总成本就包括与活动数量大小相关的变动成本和起动活动的固定成本。 二 固定费用（成本）问题 案例 某工厂近期接到一批订单，要安排生产甲、乙、丙、丁四种产品，每件产品分别需要原料A、B、C中的一种或几种中的若干单位，合同规定要在15天内完成，但数量不限。由于四种产品都在同一种设备上生产，且一台设备同一时间只能加工一件产品。目前，工厂只有一台正使用中的这种设备（设备1），合同期内可挤出3天来生产订单，但会产生150元的机会成本损失；还有一台长期未用的设备（设备2）可以启用，启用时要做必要的检查和修理，费用1000元；公司还考虑向邻厂租用2台（设备3，4），由于对方也在统筹使用，租期分别只能7和12天，租金分别2000和3100，工厂可以决定租一台或两台，也可以一台不租。另外，每种产品如果生产会有固定成本和变动成本，具体如下表，假设每天工作8小时，工厂最多使用3台设备，问：工厂如何生产和利用设备，利润最大 产品 资源限制 甲 乙 丙 丁 原料 设备1 2 3 4 原料A 4 6 9 0 156 94 183 B 2 0 4 1 C 3 8 0 5 设备台时（小时） 5 7 3 8 固定成本（元） 350 400 180 310 变动成本（元） 12 14 16 11 单位产品价格（元） 120 160 135 95 24 120 56 96 150 1000 2000 3100 例 应用 0-1 变量解决含互斥约束条件问题 设：工序 B 有两种方式完成 方式（1 ）的工时约束为 0.3X1 + 0.5X2 ≤ 150 方式（2 ）的工时约束为 0.2X1 + 0.4X2 ≤ 120 问题是完成工序 B 只能从两种方式中任选一种，如何将这两个互斥的约束条件统一在一个线性规划模型中呢？ 三 互相排斥问题 * 例 7 应用 0-1 变量解决含互斥约束条件问题 引入 0-1 变量 y1 = 0 若工序 B 采用方式（1 ）完成 1 若工序 B 不采用方式（1 ）完成 y2