第5章指派问题PPT课件.ppt

《第5章指派问题PPT课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、运筹学(OperationsResearch).运筹帷幄之中决胜千里之外整数规划IntegerProgramming第五章.一、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+

2、22x2+23x390－1整数规划.（1）两个约束中，只有一个起作用。例：a11x1+a12x20（3）若a个约束条

3、件中只能有b个起作用。则令0－1变量之和为a-b。注意：可用统一M，但M的取值必须足够的大。0－1整数规划.例5.10固定费用问题解：设Xj是第j种产品的产量。Yj是0－1变量，表示是（Yj=1）否（Yj=0）生产第j种产品。单耗量产品资源IIIIII资源量A248500B234300C123100单件可变费用456固定费用100150200单件售价810120－1整数规划.maxZ=4X1+5X2+6X3–100Y1–150Y2–200Y32X1+4X2+8X35002X1+3X2+4X3300X1+2X2+3X3100X1M1Y1X2M2Y2X3M3Y3

4、X1,X2,X30整数Y1,Y2,Y3为0－1变量。s.t.0－1整数规划.用4台机床加工3件产品。各产品的机床加工顺序，以及产品I在机床j上加工工时aij见表。例5.11工件排序问题由于某种原因，产品2的加工总时间不得超过d，现要求确定各件产品在机床上的加工方案，使在最短的时间内加工完全部产品。产品1产品2产品3a11机床1a21机床1a13机床3a22机床2a23机床2a33机床3a14机床4a24机床40－1整数规划.机床1：x11+a11x21+My1及x21+a21x11+M(1-y1)机床2：x22+a22x32+My2及x32+a32x22+M(

5、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x330－1整数规划.（4）目标函数的建立x24+a24-x21d（3）产品2的加工时间总约束wx14+a14wx24+a24wx33+a33

6、minz=wminz=max(x14+a14,x24+a24,x33+a33)0－1整数规划.0－1整数规划隐枚举法(max)原则：1、用试探法，求出一个可行解，以它的目标值作为当前最好值Z02、增加过滤条件ZZ03、将xi按ci由小大排列（min大小）0－1整数规划是一种特殊形式的整数规划，这时的决策变量xi只取两个值0或1，一般的解法为隐枚举法。.0－1整数规划例5.12：maxz=3x1-2x2+5x3x1+2x2-x32①x1+4x2+x34②x1+x23③4x2+x36④x1,x2,x3为0或1解：观察得解(x1,x2,x3)T=(1,0,0)T

7、Z0=3过滤条件：3x1-2x2+5x33将(x1，x2，x3)T(x2，x1，x3)T.0－1整数规划解(x2x1x3)目标值Z0①②③④当前最好值(0,0,0)0<3(0,0,1)5>√√√√5(0,1,0)3<(0,1,1)8>√√√√8(1,0,0)-2<(1,0,1)3<(1,1,0)1<(1,1,1)6<最优解x=(1,0,1)TZ=8.指派问题一、指派问题的数学模型的标准形式：设n个人被分配去做n件工作，规定每个人只做一件工作，每件工作只有一个人去做。已知第i个人去做第j件工作的效率（时间或费用）为Cij(i=1.2…n