运筹学-9整数规划和0-1变量.ppt

整数规划 0 – 1 规划 整数规划 在线性规划中，变量整数时称整数规划 0 – 1 规划的定义 整数规划中变量仅取 0 或 1多 的特殊情况,称为 0 – 1 规划 0 – 1 变量在数学模型中的作用 1. 表示两者选一 例: 某公司拟在东,西两个区设立门市部,拟议中有五个位置A1,A2,A3,A4,A5可供选用,规定在东区A1,A2,A3中至多选两点;在西区A4,A5中至少选一点.又根据需求和预测各点的设备投资,年利润及投资金额如下表.问选哪几个点可使总年利润最大? 解：设用 xj = 1 表示 A j 被选用. x j = 0 表示 A j 没被选用. 目标合适选点，使总利润最大 max Z = 10x1+25x2+20x3+ 25x4+30x5 s.t. 20x1+30x2+25x3+ 40x4+45x5 ?100 （投资额不超过总投资金额100） x1 + x2 + x3 ? 2 （东区A1,A2,A3中至多选两点） x4 + x5 ? 1 （西区A4,A5中至少选一点） x j = 1或 0 (j = 1,2,…,5) 2. 表示有选择的约束 (1)两个约束中选一个的问题 例：某油田拟在10个油气的构造中选若干个钻探采油，每油井开采投资，投产后预计收入，油田投资限额及油田开采时每天耗电量，电量限制见表。如不用电网的电，用自备柴油机发电，每度耗油0.3公斤，限额为10公斤。问应选择开采哪几个油田最为有利? s.t. 20x1+25x2+30x3+25x4+40x5 +45x6+35x7+35x8+40x9+25x10 ? 200 ? （投资额不超过总投资金额200万元） 2x1+3x2+3x3+4x4+5x5+2x6+3x7+5x8+4x9+3x10? 20 ? （表示耗电不超过20公斤） 0.6x1+0.9x2+0.9x3+1.2x4+1.5x5+0.6x6+0.9x7+1.5x8+1.2x9+0.93x10?10 ? （表示耗油不超过10公斤） x j = 1或 0 (j = 1,2,…,10) 问题？ 耗电约束条件（2） 耗油约束条件（3） 两者必取其一，如何处理？ ? ?两个约束条件满足其中之一就可以了，故引进另一逻辑变量y = 1 或 y = 0 改写成： 2x1+3x2+3x3+4x4+5x5+2x6+3x7+5x8+4x9+3x10? 20+My ?’ 0.6x1+0.9x2+0.9x3+1.2x4+1.5x5+0.6x6+0.9x7+1.5x8+1.2x9 +0.93x10?10+M(1-y) ?‘ Y=0 ?等价?’,而?等于没有约束 Y=1 ?等价?’,而?等于没有约束 (2) N个约束中选择K个约束的问题 设N个约束可能的约束条件是: f1(x1, x2,…, xn) ? d1, f2(x1, x2,…, xn) ? d2, ……………………. fN(x1, x2,…, xn) ? dN, 建立数学模型 设逻辑变量yj=1或yj=0: j=1,2,…, N f1(x1, x2,…, xn) ? d1+ M y1, f2(x1, x2,…, xn) ? d2 + M y2, ……………………. fN(x1, x2,…, xn) ? dN +M yN, y1+ y2 +…+ yN =N-K 注意: y1 =1即第一个约束失效 使N? K个约束条件失效,即选择了K个约束条件 数学模型 3. 表示条件约束 (1)若开采A8油井,必须同时开采A6油井 x8 =0 x6 =0 允许 x8 =0 x6 =1 允许 x8 =1 x6 =1 允许 x8 =1 x6 =0 不允许 用约束条件 x8 ? x6 数学模型 (2)若开采A5油井,就不允许开采A3油井 x5 =0 x3 =0 允许 x5 =1 x3 =0 允许 x5 =0 x3 =1 允许 x5 =1 x3 = 1 不允许 用约束条件 x5 + x3 ? 1 建立数学模型 (3)或者开采A1和A7,或开采A8. x1 =1, x7 =1, x8 =0 ? x1 =1, x7 =0, x8 =0 ? x1 =0, x7 =1, x8 =0 ? x1 =0, x7 =0, x8 =1