-运筹学第五章整数规划-PPT.ppt

1、Page:1wxj浙江理工大学 经济管理学院管理运筹学管管理理运运筹筹学学 整整数数规规划划Page:2wxj浙江理工大学 经济管理学院管理运筹学第五章第五章 整数规划整数规划5.1 整数规划问题的提出整数规划问题的提出例例5-1 某厂拟用集装箱托运甲、乙两种货物。每箱的体积、重量、可获利润以及托运所受限制如下表所示：货物 体积（m3/箱）重量（kg/箱）利润（百元/箱）甲 5 2 20 乙 4 5 10托运限制 24 13问两种货物各托运多少箱，可使获得的利润最大？解：解：设x1,x2 分别为甲、乙两种货物的托运箱数，则模型为：Max z=20 x1+10 x2 St.5x1+4x2 242

2、x1+5 x2 13 x1，x2 0 x1，x2 整数暂不考虑整数约束，求得最优解为x1=4.8，x2=0，Max z=96Page:3wxj浙江理工大学 经济管理学院管理运筹学 Max z=20 x1+10 x2 St.5x1+4x2 242x1+5 x2 13 x1，x2 0 x1，x2 整数（1）若 x1=4.8，x2=0 x1=5，x2=0不是可行解；（2）若x1=4.8，x2=0 x1=4，x2=0是可行解，但不是最优解因为 x1=4，x2=0时，z=80而可行解x1=4，x2=1时，z=90Page:4wxj浙江理工大学 经济管理学院管理运筹学5.2 整数规划的类型整数规划的类型整

3、数规划按变量取值的不同，可以分为以下几类：1.纯整数规划：所有的变量都取整数值；2.混合整数规划：部分变量取整数值；3.01规划：所有变量只取0，1两个值；4.01混合规划：部分变量只取0，1两个值。Page:5wxj浙江理工大学 经济管理学院管理运筹学整数规划（整数规划（Integer ProgrammingInteger Programming）问题的一般形式问题的一般形式max(min)zc xc xc xnn1122mnmnmmnnnnbxaxaxabxaxaxabxaxaxats).().().(.22112222212111212111中部分或全部取整数nxxx,11Page:6w

4、xj浙江理工大学 经济管理学院管理运筹学整数规划与其松弛问题整数规划与其松弛问题当放弃整数约束时得到的线性规当放弃整数约束时得到的线性规划称为整数规划的松弛问题。划称为整数规划的松弛问题。整数规划的可行域是松弛问题的整数规划的可行域是松弛问题的可行域，反之不成立。可行域，反之不成立。Page:7wxj浙江理工大学 经济管理学院管理运筹学5.3.1 混合整数规划的求解混合整数规划的求解-分枝定界方法分枝定界方法分枝：分枝：当当 不符合整数要求时，构造不符合整数要求时，构造两个约束条件：两个约束条件：iibx 1 iiiibxbx和加入松弛问题分别形成两个子问题（分枝）加入松弛问题分别形成两个子问

5、题（分枝）定界：定界：当子问题获得整数规划的一个可行当子问题获得整数规划的一个可行解，则它的目标函数值就构成一个界限解，则它的目标函数值就构成一个界限5.3 整数规划的解法整数规划的解法Page:8wxj浙江理工大学 经济管理学院管理运筹学分枝定界法基本思想：分枝定界法基本思想：首先不考虑变量的整数约束，求解相应的线性规划问题：Max z=CX AX=b X 0OACDxr IrIr+1Max z=CX AX=b xr Ir X 0Max z=CX AX=b xr Ir+1 X 0.分枝分枝每一次分枝得到的子问题的最优目标函数值都要比上一层问题的最优目标函数值小，或者相等。z0z11z12z2

6、1z22z23z24整数解下界若z21 z11，z22 z11，则无须继续分枝定界定界利用定界，可以终止许多不必要的分枝过程。如果在分枝过程中得到新的整数解且该整数解的目标函数值大于已如果在分枝过程中得到新的整数解且该整数解的目标函数值大于已记录的下界，则应将较大的整数解的目标函数值代替原来的下界。记录的下界，则应将较大的整数解的目标函数值代替原来的下界。Page:9wxj浙江理工大学 经济管理学院管理运筹学当所有最低一层子问题出现以下三种情况时，分枝定界法终止：1.子问题无可行解；2.子问题已获得整数解；3.子问题的目标函数值未达到下界。Page:10wxj浙江理工大学 经济管理学院管理运筹

7、学例例取整数2121212121,0,3121451149x.xz maxxxxxxxxtsx132X254X1 231)310,23(AS解解S得：得：629 310,23 :21zxxAPage:11wxj浙江理工大学 经济管理学院管理运筹学132X254X1 231)310,23(AS2对对S分枝：分枝：构造约束：构造约束：21x和和11x形成分枝问题形成分枝问题S1和和S2，得解，得解B和和CS1)37,1(C)923,2(B941923);(2,:zB31037);(1,:zCPage:12wxj浙江理工大学 经济管理学院管理运筹学SA:x1=3/2,x2=10/3Z=29/6S2C

8、:x1=1,x2=7/3Z=10/3S1B:x1=2,x2=23/9Z=41/911x21x4629zz4941zzPage:13wxj浙江理工大学 经济管理学院管理运筹学132X254X1 231)310,23(AS2对对S1分枝：分枝：构造约束：构造约束：32x和和22x形成分枝问题形成分枝问题S11和和S12，得解，得解DS12)2,(1433D14611433);,2(:zDS11无可行解无可行解Page:14wxj浙江理工大学 经济管理学院管理运筹学SA:x1=3/2,x2=10/3Z=29/6S2C:x1=1,x2=7/3Z=10/3S1B:x1=2,x2=23/9Z=41/9S1

9、1无可行解无可行解S12D:x1=33/14,x2=2Z=61/1411x32x22x21x4941zz4629zz41461zzPage:15wxj浙江理工大学 经济管理学院管理运筹学132X254X1 231)310,23(AS2对对S12分枝：分枝：构造约束：构造约束：31x和和21x形成分枝问题形成分枝问题S121和和S122，得解，得解E和和FS121)1,3(E4);(3,1:zES122)2,2(F4);(2,2:zFPage:16wxj浙江理工大学 经济管理学院管理运筹学SA:x1=3/2,x2=10/3Z=29/6S2C:x1=1,x2=7/3Z=10/3S1B:x1=2,x

10、2=23/9Z=41/9S11无可行解无可行解S12D:x1=33/14,x2=2Z=61/1411x32x22x21xS122F:x1=2,x2=2Z=4S121E:x1=3,x2=1Z=431x21x4z629z4z941z4z1461z4z4zPage:17wxj浙江理工大学 经济管理学院管理运筹学 首先求解整数规划（IP）对应的松弛问题（LP），如果（LP）的最优解不是整数解，则逐次增加一个新约束（即割平面），它能割去松弛问题可行域中不含整数解的区域.逐次切割，直到得到一个整数最优极点（即整数解）为止。5.3.2 纯整数规划的求解纯整数规划的求解-Gomory-Gomory割平面方法割

11、平面方法基本思想：基本思想：（1）首先放弃变量的整数要求，求得线性规划的最优解；（2）如果最优解是一个非整数解，则构造一个新的约束，对线性规划问题的可行域进行切割，切除已得到的最优解，但保留原可行域中所有的整数解，求解新的线性规划问题；（3）如果最优解仍不是整数解，再以增加附加约束的方法将其切除，但仍保持最初可行域中所有的整数解，直至求得一个整数最优解为止。Page:18wxj浙江理工大学 经济管理学院管理运筹学整数规划的求解整数规划的求解-GomoryGomory割平面方法割平面方法为整数x,x 0 x,x 5x2x104x5x 3x23x .x3xzmax 212121212121ts13

12、2X2X1 22.5154整数点整数点松弛问题最优解松弛问题最优解Page:19wxj浙江理工大学 经济管理学院管理运筹学松弛问题的最优解松弛问题的最优解Page:20wxj浙江理工大学 经济管理学院管理运筹学GomoryGomory定理定理000,ijjiibxax在松弛问题的最优单纯形表中，假如有一常数在松弛问题的最优单纯形表中，假如有一常数项项 不是整数，且对应的方程为：不是整数，且对应的方程为：0ib000000,iiijijijifNbfNa分解分解 和和 成成最大整数与正分数之和最大整数与正分数之和：jia,00ibPage:21wxj浙江理工大学 经济管理学院管理运筹学000,i

13、jjiibxax00000)(,iijjijiifNxfNxjjiiijjiixffNxNx,000000,00jjiixff则则包含了整数规划的所有整数可行解，但不包括包含了整数规划的所有整数可行解，但不包括松弛问题的最优解。松弛问题的最优解。Page:22wxj浙江理工大学 经济管理学院管理运筹学例题求解例题求解选择第一个方程：选择第一个方程：7137271531xxx分解为：分解为：5317271761xxx为整数x,x 0 x,x 5x2x104x5x 3x23x .x3xzmax 212121212121tsPage:23wxj浙江理工大学 经济管理学院管理运筹学072717653x

14、x在原松弛问题中加入约束：在原松弛问题中加入约束：767271653xxx即即形成松弛问题形成松弛问题2Page:24wxj浙江理工大学 经济管理学院管理运筹学Page:25wxj浙江理工大学 经济管理学院管理运筹学132X2X1 22.5154整数点整数点松弛问题松弛问题2的最优解的最优解010727176153xxx或：割平面割平面Page:26wxj浙江理工大学 经济管理学院管理运筹学选择第四个方程（具有最大分数部分）：选择第四个方程（具有最大分数部分）：474341645xxx分解为：分解为：64654141431xxxxPage:27wxj浙江理工大学 经济管理学院管理运筹学在松弛问

15、题在松弛问题2中加入约束：中加入约束：即即形成松弛问题形成松弛问题3041414364xx434141764xxxPage:28wxj浙江理工大学 经济管理学院管理运筹学得到最优解得到最优解Page:29wxj浙江理工大学 经济管理学院管理运筹学割平面：割平面：52 1045 323767271 43414152142132165364xxxxxxxxxxxxxx3221 xx132X2X1 22.5154松弛问题松弛问题3的最优解的最优解松弛问题松弛问题2的最优解的最优解Page:30wxj浙江理工大学 经济管理学院管理运筹学如果选择第二个方程：如果选择第二个方程：454541642xxx分

16、解为：分解为：6464243434112xxxxxPage:31wxj浙江理工大学 经济管理学院管理运筹学在松弛问题在松弛问题2中加入约束：中加入约束：即即形成松弛问题形成松弛问题3043434164xx414343764xxxPage:32wxj浙江理工大学 经济管理学院管理运筹学3-100000 x1x2x3x4x5x6x7RHS310000101-101000-104/3000100-508/3000001-105/30 00 000101-4/31/300000-40 x3x1x2检验数检验数x5x4没有找到整数解，没有找到整数解，继续做下去继续做下去Page:33wxj浙江理工大学

17、经济管理学院管理运筹学5.3.3 整数规划的图解法整数规划的图解法 Max z=20 x1+10 x2 St.5x1+4x2 242x1+5 x2 13 x1，x2 0 x1，x2 整数x1x264.82.66.5*Page:34wxj浙江理工大学 经济管理学院管理运筹学5.3.4 整数规划的计算机求解整数规划的计算机求解LP OPTIMUM FOUND AT STEP 1 OBJECTIVE VALUE=96.0000000 NEW INTEGER SOLUTION OF 90.0000076 AT BRANCH 0 PIVOT 3 BOUND ON OPTIMUM:90.00001 ENU

18、MERATION COMPLETE.BRANCHES=0 PIVOTS=3 LAST INTEGER SOLUTION IS THE BEST FOUND RE-INSTALLING BEST SOLUTION.OBJECTIVE FUNCTION VALUE 1)90.00000 VARIABLE VALUE REDUCED COST X1 4.000000 -16.000000 X2 1.000000 0.000000 ROW SLACK OR SURPLUS DUAL PRICES 2)0.000000 0.000000 3)0.000000 2.000000 NO.ITERATIONS

19、=3 BRANCHES=0 DETERM.=1.000E 0 Max z=20 x1+10 x2 St.5x1+4x2 242x1+5 x2 13 x1，x2 0 x1，x2 整数Max 20 x1+10 x2 st 5x1+4x2 24 2x1+5x2 0 0 当不生产第 i 种容器，即 xi=0 目标函数：为扣除了固定费用后的利润约束条件：金属板、劳动力、机器设备的限制为避免出现某种容器不投入固定费用就生产这样一种不合理情况，必须加上如下约束：x1 y1 Mx2 y2 Mx3 y3 MM是充分大的数，例如，此问题中，M可取200 x1 200y1 x2 200y2 x3 200y3 Pag

20、e:40wxj浙江理工大学 经济管理学院管理运筹学线性规划模型为：目标函数Max z=4x1+5x2+6x3 100y1 150y2 200y3 金属板限制2x1+4x2+8x3 500劳动力限制2x1+3x2+4x3 300机器设备限制x1+2x2+3x3 100 x1 y1 Mx2 y2 Mx3 y3 Mx1，x2，x3 0y1，y2，y3 为01变量求解得：x1=100，x2=0，x3=0y1=1，y2=0，y3=0Page:41wxj浙江理工大学 经济管理学院管理运筹学 例例5-5 分布系统设计分布系统设计某企业在A1 地已有一个工厂，其产品的生产能力为30千箱。为了扩大生产，打算在A

21、2、A3、A4、A5 地中再选择几个地方建厂。已知在A2、A3、A4、A5 地建厂的固定成本分别为175、300、375、500千元，各产地的产量及各销地的销量及从产地到销地的单位运价如下表所示。销地单位运价产地B1 B2 B3 产量（千箱）A1 8 4 3 30A2 5 2 3 10A3 4 3 4 20A4 9 7 5 30A5 10 4 2 40销量（千箱）30 20 20（1）问应该在哪几个地方建厂，在满足销量的前提下，使得总固定成本和总运输费用之和最小；（2）如果由于政策要求必须在A2、A3 建一个厂，应在哪几个地方建厂？Page:42wxj浙江理工大学 经济管理学院管理运筹学解：设

22、 xij 为从Ai 到Bj 的运输量；yi=1 当Ai 厂址被选中；0 当Ai 厂址没被选中Min z=175y2+300y3+375y4+500y5+8x11+4x12+3x13+5x21+2x22+3x23 +4x31+3x32+4x33+9x41+7x42+5x43+10 x51+4x52+2x53 A1 厂的产量限制x11+x12+x13 30对于A2、A3、A4、A5，只有厂址被选中，才会有生产量x21+x22+x23 10 y2 x31+x32+x33 20 y3 x41+x42+x43 30 y4 x51+x52+x53 40 y5 各销地的销量限制x11+x21+x31+x41

23、+x51 =30 x12+x22+x32+x42+x52 =20 x13+x23+x33+x43+x53 =20 xij 0，为整数，yi 为01变量（1）Page:43wxj浙江理工大学 经济管理学院管理运筹学求解得：y5=1，x52 =20，x53 =20，x11 =30，其余为0，最优目标函数值=860（2）在上述模型上加上约束条件：y2+y3=1求解得：y2=1，y4=1，x22 =10，x41 =30，x12 =10，x13 =20，其余为0，最优目标函数值=940Page:44wxj浙江理工大学 经济管理学院管理运筹学0-10-1规划的求解规划的求解隐枚举方法隐枚举方法10,x6

24、4 3 x44x22x .523xz max3213221321321321或xxxxxxxxxtsxxPage:45wxj浙江理工大学 经济管理学院管理运筹学(x1,x2,x3)z值值过滤条件过滤条件（1）（2）（3）（4）（0，0，0）0z0（0，0，1）5z5（0，1，0）-2（0，1，1）3（1，0，0）3（1，0，1）8z8（1，1，0）1（1，1，1）6约束条件约束条件最优解（最优解（x1,x2,x3)=(1,0,1);z=8隐枚举方法求解过程隐枚举方法求解过程Page:46wxj浙江理工大学 经济管理学院管理运筹学 n个员工分配做个员工分配做n项工作，已知项工作，已知第第i个员工

25、做第个员工做第j项工作的成本为项工作的成本为cij，i=1,n;j=1,n。求最佳分配方。求最佳分配方案。案。4.5 指派问题与匈亚利法指派问题与匈亚利法Page:47wxj浙江理工大学 经济管理学院管理运筹学指派问题的数学模型指派问题的数学模型 0 1否则项工作员工分配做第第jixijn1in1jijijc=zMin xn,1,2,=i 1xn1jijn ,1,2,=j 1xn1iijn,1,=jn;,1,2,=i 1,0 xij或s.t.Page:48wxj浙江理工大学 经济管理学院管理运筹学nnnnnnnnccccccccccccccccC321333323122322211131211

26、指派问题的解应对应于成本矩阵的不同指派问题的解应对应于成本矩阵的不同行与不同列，且总成本最小行与不同列，且总成本最小Page:49wxj浙江理工大学 经济管理学院管理运筹学Page:50wxj浙江理工大学 经济管理学院管理运筹学对于每个指派问题，需要有效率矩阵（cij）（cij）=c11 c12 c1nc21 c22 c2n cn1 cn2 cnn 引入变量 xij=1 当指派第i 个人完成第j项任务0 当不指派第i 个人完成第j项任务则每人的效率及目标为c11 x11 +c12 x12 +.+c1n x1n c21 x21 +c22 x22 +.+c2n x2n .cn1 xn1 +cn2

27、xn2 +.+cnn xnn jnjjxc111jnjjxc212.njnjnjxc1ninjijijxc11 Z=Min n项任务，恰好有n个人承担去完成。由于每人的专长不同，各人完成不同的任务效率也不同。于是就产生了应指派哪个人去完成哪项任务，使完成n项任务的总效率最高。Page:51wxj浙江理工大学 经济管理学院管理运筹学 第1项任务只能由1人完成 x11+x21+.xn1=1 第2项任务只能由1人完成 x12+x22+.xn2=1.第j项任务只能由1人完成 x1j+x2j+.xnj=1.第n项任务只能由1人完成 x1n+x2n+.xnn=111iix12iix.1iijx.1iinx

28、.1iijx(j=1,2,n)第1个人只能完成1项任务x11+x12+.x1n=1第2个人只能完成1项任务x21+x22+.x2n=1.第i个人只能完成1项任务xi1+xi2+.xin=1.第n个人只能完成1项任务xn1+xn2+.xnn=111jjx12jjx.1jijx.1jnjx1jijx(i=1,2,n)Page:52wxj浙江理工大学 经济管理学院管理运筹学故模型为ijijijxczMin 1iijx(j=1,2,n)第j项任务只能由1人完成1jijx(i=1,2,n)第i个人只能完成1项任务 xij=0或1 满足上述约束条件的可行解xij 可写成矩阵形式，称为解矩阵（xij）=0

29、1 0 0 0 0 1 0 1 0 0 0 0 0 0 1Page:53wxj浙江理工大学 经济管理学院管理运筹学指派问题的求解方法指派问题的求解方法（1）计算机求解（2）匈牙利法（3）隐枚举法Page:54wxj浙江理工大学 经济管理学院管理运筹学指派问题的性质指派问题的性质定理：定理：对于指派问题，成本矩阵的任一对于指派问题，成本矩阵的任一行行(或列或列)减去减去(或加上或加上)一个相同的数得到一个相同的数得到的新指派问题与原问题同解。的新指派问题与原问题同解。定理：定理：系数矩阵中独立系数矩阵中独立0元素的最多个数等于能元素的最多个数等于能覆盖所有覆盖所有0元素的最少直线数。元素的最少直

30、线数。Page:55wxj浙江理工大学 经济管理学院管理运筹学s)(s)(xcxc xs)(xcxc s)x(cxc=z n1jkjkjnki1in1jijijn1jkjn1jkjkjnki1in1jijijn1jkjkjnki1in1jijijzPage:56wxj浙江理工大学 经济管理学院管理运筹学匈牙利法的计算步骤为：第一步：使系数矩阵出现0元素。第二步：进行试指派，以寻求最优解。第三步：作最少的直线覆盖所有的0元素，以确定该系数矩阵中能找到最 多的独立元素数。第四步：变换矩阵增加0元素，再返回第二步。第四步说明：调整效益矩阵，使之增加一些零元素：(1)在没有被直线覆盖的元素中，找出最小

31、元素；(2)在没有被直线覆盖的元素中，减去最小元素；(3)在直线交叉处的元素中，加上最小元素；(4)被一条直线覆盖的元素不变.Page:57wxj浙江理工大学 经济管理学院管理运筹学 例例4-6 有一份中文说明书，需译成英、日、德、俄四种文字，分别记作E、J、G、R。现有甲、乙、丙、丁四人，他们将中文说明书翻译成不同语种的说明书所需的时间如下表所示：任务 E J G R人员 甲 2 15 13 4 乙 10 4 14 15 丙 9 14 16 13 丁 7 8 11 9问应指派何人去完成何工作，使所需总时间最少？解：解：用匈牙利法。第一步：使系数矩阵出现0元素。（cij）=2 15 13 4

32、10 4 14 15 9 14 16 13 7 8 11 9 2 4 9 7 0 13 11 2 6 0 10 110 5 7 40 1 4 24 2Page:58wxj浙江理工大学 经济管理学院管理运筹学 0 13 11 2 6 0 10 110 5 7 40 1 4 24 20 13 7 0 6 0 6 9 0 5 3 2 0 1 0 0=（bij）第二步：进行试指派。0 13 7 0 6 0 6 9 0 5 3 2 0 1 0 0可见，m=n=4，所以得最优解为（xij）=0 0 0 1 0 1 0 01 0 0 00 0 1 0即指定甲译俄文，乙译日文，丙译英文，丁译德文，所需总时间最

33、少。所需时间为ijijijccccxcz28min14432231Page:59wxj浙江理工大学 经济管理学院管理运筹学例例4-7 求下表所示效率矩阵的指派问题的最优解。任务 A B C D E 人员 甲 12 7 9 7 9 乙 8 9 6 6 6 丙 7 17 12 14 9 丁 15 14 6 6 10 戊 4 10 7 10 9解：解：第一轮第一步：使系数矩阵出现0元素。12 7 9 7 9 8 9 6 6 6 7 17 12 14 9 15 14 6 6 10 4 10 7 10 976764 5 0 2 0 2 2 3 0 0 0 0 10 5 7 2 9 8 0 0 4 0 6

34、 3 6 5Page:60wxj浙江理工大学 经济管理学院管理运筹学第二步：进行试指派。5 0 2 0 2 2 3 0 0 0 0 10 5 7 2 9 8 0 0 4 0 6 3 6 5由于m=4，n=5，解题没有完成。第三步：作最少的直线覆盖所有的0元素，以确定该系数矩阵中能找到最多的独立元素（不同行不同列的零元素）数。5 0 2 0 2 2 3 0 0 0 0 10 5 7 2 9 8 0 0 4 0 6 3 6 5 由于 l=4 n=5，转第四步。Page:61wxj浙江理工大学 经济管理学院管理运筹学第四步：变换矩阵增加0元素。5 0 2 0 2 2 3 0 0 0 0 10 5 7

35、 2 9 8 0 0 4 0 6 3 6 5最小元素为270202430000835011800404143第一轮结束。第二轮：按第二步，得70202430000835011800404143由于m=n=5，故得最优解，解矩阵为（xij）=0 1 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 1 0 1 0 0 0 0最优的任务指派为：甲B；乙C；丙E；丁D；戊A。Min z=7+6+9+6+4=32Page:62wxj浙江理工大学 经济管理学院管理运筹学第四步：调整效益矩阵，使之增加一些零元素：(1)在没有被直线覆盖的元素中，找出最小元素；(2)在没有被直线覆盖的元素中，减

36、去最小元素；(3)在直线交叉处的元素中，加上最小元素；(4)被一条直线覆盖的元素不变.Page:63wxj浙江理工大学 经济管理学院管理运筹学此问题还有一个最优解由第二步得：70202430000835011800404143由于m=n=5，故得最优解，解矩阵为（xij）=0 1 0 0 0 0 0 0 1 0 0 0 0 0 1 0 0 1 0 0 1 0 0 0 0最优的任务指派为：甲B；乙D；丙E；丁C；戊A。Min z=7+6+9+6+4=32Page:64wxj浙江理工大学 经济管理学院管理运筹学一般指派问题一般指派问题最大化指派问题最大化指派问题人数和工作数不等的指派问题人数和工作

37、数不等的指派问题一个人可做几项工作的指派问题一个人可做几项工作的指派问题某项工作一定不能由某人做的指派问题某项工作一定不能由某人做的指派问题Page:65wxj浙江理工大学 经济管理学院管理运筹学最大化指派问题最大化指派问题610129610617711781296101429121215784最大化指派问题最大化指派问题最大值最大值617101712179176171017617171771711177178171217917617101714172179171217121715177178174171175811711010610958117315855210913最最小小化化指指派派问问

38、题题Page:66wxj浙江理工大学 经济管理学院管理运筹学人数和工作数不等的指派问题人数和工作数不等的指派问题1012966177118129614291215784101296617711812961429121578400000Page:67wxj浙江理工大学 经济管理学院管理运筹学一个人可做几项工作的指派问题一个人可做几项工作的指派问题78329824763195232154321BBBBBAAA 31952319527832982476319525432111321BBBBBAAAAAA1可同时做可同时做三项工作三项工作Page:68wxj浙江理工大学 经济管理学院管理运筹学某项工作

39、一定不能由某人做的指派问题某项工作一定不能由某人做的指派问题452782946178298247639525432154321BBBBBAAAAA4 5 2 782 9 4 6178298247639525432154321MMAAAAABBBBBA1不能做不能做B4;A3不能做不能做B3Page:69wxj浙江理工大学 经济管理学院管理运筹学例题：例题：0-10-1规划的应用规划的应用-项目投资预算项目投资预算 资金需求资金需求(1000$)项项 目目 估计现值估计现值 第一年第一年 第二年第二年 第三年第三年 第四年第四年 工厂扩建工厂扩建 90 15 20 20 15 销售网点扩建销售网

40、点扩建 40 10 15 20 5 新生产流水线新生产流水线 10 10 0 0 4 新产品研究新产品研究 37 15 10 10 10 可用资金可用资金 40 50 40 35 Page:70wxj浙江理工大学 经济管理学院管理运筹学模型模型变量假设变量假设:项目没有选中如果第选中目项第果如iixi 0 1模型模型:Page:71wxj浙江理工大学 经济管理学院管理运筹学0-10-1规划的应用规划的应用-生产厂生产厂顾客需求顾客需求销售点销售点45DCBA7IIIII213IPage:72wxj浙江理工大学 经济管理学院管理运筹学工厂工厂-销售点配置问题销售点配置问题-问题描述问题描述III

41、III生产能力生产能力1 18008001,0001,0001,2001,20030030035,00035,0002 240040050050070070020020045,00045,0003 380080060060050050030030040,00040,0004 450050060060070070020020042,00042,0005 570070060060050050040040040,00040,000ABCDI404080809090505040,00040,000II707040406060808020,00020,000III808030305050606060,0

42、0060,000需求量需求量200200300300150150250250运输成本运输成本:工厂工厂-销售点销售点开设的固开设的固定成本定成本开设的固开设的固定成本定成本运输成本运输成本:销售点销售点-客户客户问题问题:为使经营成本最低为使经营成本最低,应开设那些工厂及销售点应开设那些工厂及销售点?Page:73wxj浙江理工大学 经济管理学院管理运筹学工厂工厂-销售点配置问题销售点配置问题-销售点不开设第销售点开设第厂不开设第厂开设第jjviiuji 0 1 0 1 客户运输量销售点到第第销售点运输量厂到第第客户需求量第厂供应能力第销售点开设成本第厂开设成本第客户运价销售点到第第销售点运价

43、厂到第第kjyjixkDiBjcickjcjicjkijkijijkij Page:74wxj浙江理工大学 经济管理学院管理运筹学工厂工厂-销售点配置问题销售点配置问题-KkDy,N,jvyxMiuBxStvcucycxcZMinkNjjkKkjjkMiijiiNjijjNjjiNjMiijkKkjkMiijNjij,2,1 ,21 ,)(,2,1 ,1111111111客户需求：供销平衡：供应能力：Page:75wxj浙江理工大学 经济管理学院管理运筹学指派问题实例指派问题实例B1B2B3B4B5A14871512A279171410A3691287A46714610A56912106cijPage:76wxj浙江理工大学 经济管理学院管理运筹学例题求解例题求解6101296106147678129610141797121578466674310463040810126303710208113400432040500123203771081103004320405001232037710811030Page:77wxj浙江理工大学 经济管理学院管理运筹学043204050012320377108110300432140501012102110081103104321405010121021100811031