第5章指派问题讲述.pptx

运 筹 学( Operations Research ) Integer Programming 第五章 一、0－1变量及其应用 0－1变量常被用来表示系统是否处于某个特定状态，或者决策时是否取某个特定方案。例如: 0－1 整数规划 当问题有多项要素，每项要素皆有两种选择时，可用一组0－1变量来描述。设问题有有限项要素E1， E2，┉，En,其中每项Ej有两种选择Aj和不选择Aj（j=1,2,┉,n）,则令 在应用中，有时会遇到变量可以取多个整数值的问题。如果用0－1变量来表示，也可以用一组0－1变量来取代。 如x取0－9之间的任意整数时。 x=20x0+ 21x1 + 22x2 + 23x3 ? 9 0－1 整数规划 （1）两个约束中，只有一个起作用。 例：a11x1+a12x2B1 a21x1+a22x2B2 例5.9 含有相互排斥的约束条件的问题 解：引入0-1变量Y1, Y2和足够大的正数M，则 a11x1+a12x2B1+M1Y1 a21x1+a22x2B2+M2Y2 Y1+Y2=1 0－1 整数规划 （2）互相排斥的多个约束中，只有一个起作用 ai1x1+ai2x2 +…+ainxn ? bi (i=1,…,m) 互相排斥m个约束，只有一个起作用: （3）若a个约束条件中只能有b个起作用。 则令0－1变量之和为a-b。 注意：可用统一M，但M的取值必须足够的大。 0－1 整数规划 例5.10 固定费用问题 解：设Xj是第j种产品的产量。Yj是0－1变量，表示是（Yj=1）否（Yj=0）生产第j种产品。 单耗量 产品 资源 I II III 资源量 A 2 4 8 500 B 2 3 4 300 C 1 2 3 100 单件可变费用 4 5 6 固定费用 100 150 200 单件售价 8 10 12 0－1 整数规划 0－1 整数规划 用4台机床加工3件产品。各产品的机床加工顺序，以及产品I在机床j上加工工时aij见表。 例5.11 工件排序问题 由于某种原因，产品2的加工总时间不得超过d，现要求确定各件产品在机床上的加工方案，使在最短的时间内加工完全部产品。 0－1 整数规划 机床1 ： x11+a11 ? x21+ My1 及 x21+a21? x11 + M(1-y1 ) 机床2 ： x22+a22 ? x32 + My2 及 x32+a32 ? x22 + M(1-y2) 机床3 ： x13+a13? x33 + My3 及 x33+a33 ? x13 + M(1-y3) 机床4： x14+a14 ? x24 + My4 及 x24+a24 ? x14 + M(1-y4) 解：设产品i在机床j上开始加工的时间为xij （1）同一件产品在不同机床上的加工顺序约束 （2）每一台机床对不同产品上的加工顺序约束 产品1 ： x11+a11 ? x13 及 x13+a13 ? x14 产品2 ： x21+a21 ? x22 及 x22+a22 ? x24 产品3 ： x32+a32 ? x33 0－1 整数规划 （4）目标函数的建立 x24+ a24 -x21 ? d （3）产品2的加工时间总约束 w ? x14+a14 w ? x24+a24 w ? x33+a33 min z=w min z=max(x14+a14 , x24+a24 , x33+a33) 0－1 整数规划 0－1 整数规划 隐枚举法(max) 原则： 1、用试探法，求出一个可行解，以它的目标值作为当前最好值Z0 2、增加过滤条件Z? Z0 3、将xi 按ci由小?大排列（min 大?小） 0－1 整数规划是一种特殊形式的整数规划，这时的决策变量xi 只取两个值0或1，一般的解法为隐枚举法。 0－1 整数规划 例5.12：max z = 3x1 -2x2+5x3 x1 +2x2 - x3? 2 ① x1 +4x2 +x3? 4 ② x1 + x2