第六章 整数规划.docx

《第六章 整数规划.docx》由会员分享，可在线阅读，更多相关《第六章 整数规划.docx（23页珍藏版）》请在优知文库上搜索。

1、第六章整数规划6.1用图形将一下列线性规划问题的可行域转换为纯整数问题的可行域（在图上用“X”标出）。1、maxz=3x2x2S.T.2x+3x2122xi+X29x.M20解：X28-A62、mini=10xi+9x2S.T.5x+3m245Xi28X210x.M206.2求解下列整数规划问题1、minf=4x3x22x3S.T.2x-5x23x344xi+m+3x323x2+x3.1x1.x2.x3=0或1解：将模型代入求解模板求解0-1整数规划模板返回首页我总荥IW结果妁虫备件*孰暴漕然幽一，可高足所有的妁束及最忧约栗条村为束约束条件冬际的美系窠利通O恢复为网的(Q)I睚i【IBifl1

2、|供存方案0).I硒()J即：最优解(0,0,1),最优值：22、minf=2x+5M+3x3+4x3S.T.-4+x2+x3+x4.2-2x+4x2+224x224x+x2-x2+x23XLX2、X3、X3=0或1解：此模型没有可行解。3、maxZ=2x+3x2+5%3+4S.T.5x+3x2+3%3+X4302x+5X2-X23X220-XI+345111I26I14-0*03k90100biOE0Gbll1204bl21304t)131404bl41120bl5160b!60t17180bl8190t)19200一 L妁条件或，约束条件约束约束条件实际值美系客数吸最优解：(0,0,0,1

3、,1,1,1,1,0,1,1,0,1,0)最优值：19.4。即：B4,B5,B6,B7,B8,B10,BlbB13选中,建店的最低费用19.4万元。6.4有四个工人（甲、乙、丙、丁），要分别指派他们完成四项不同的工作（A、B、C、D）,请按以下要求求解指派问题。1、每人做各项工作所消耗的时间如下表所示，问应如何分配工作，才能使总的消耗时间为最少？每人完成各项工作的所需时间小时是工作工作A工作B工作C工作D甲1816-19乙-201620丙19181721T121520-2、每人做各项工作所创的利润如下表所示，问应如何指派工作，才能使总的创利为最多？所工作创工作A工作B工作C工作D甲4579乙7

4、568丙3435T7688解：1、消耗时间为最少问题（1）确定决策变量设0-1变量如下表，各变量表示是否分配给工作，0为不分配，1为分配。所工作需工人工作A工作B工作C工作D甲XiXi-X3乙-XaX5X6丙Xj即X9-VioT-VllX2.5-(2)确定目标函数本问题的目标是所用总的时间为最少，而总时间为：18x+16x219-3+20416xs+2Ch+19力+18+17x92Lvo12,i+15x220xi3所以目标函数为：minJ=18x+l6x2+193+2x4+16x5+2(h+19幻+18+17x9+2lxo12xn+15x2+20x3(3)确定约束条件因为每人只能分配一项工作所

5、以对于每人而言X+42+X3=1x4+5+x6=1X7+X8+X9+X1O=1Xll+X12+X13=l又每项工作只能分配给一个人人，所以对于每项工作X+X7X11=1X2+-V4+X8+X2=lx5+x9+x13=1x3+x6+x0=1为20且为为01变量，Z=1,2,3,，13。即得本问题的线性规划数学模型：minj=18x+16x2+19冷+2(1口+16x5+2x6+19&+18刖+17刈+2lxo+12x+15x2+2x3S.T.x+x2+x3X4+X5+X6=lX7+X8+X9+x0=l)X2+X13=x+x7+x=IM+X4+X8+X12=1x5+x9+x13=1力+北+处0=1

6、Xix)且Xj为O-I变量，/=1,2,3,，13。代入求解模板得结果：0-1整改规划模板Jp】1Qla11。101UU01UmII1取日Im杼方*0.II帝勒3I拗片解掂到一解可观足用有的虻施及ttC伎直力”值Q)最优解：(0,1,0,0,1,0,0,0,0,1,1,0,0,),最优值：65O即：给甲分配工作B,给乙分配工作C,给丙分配工作D,给丁分配工作A,所用最少的时间为65小时。2、总的创利为最多问题(1)确定决策变量设0-1变量如下表，各变量表示是否分配给工作，0为不分配，I为分配。是工作工作A工作B工作C工作D甲XiX2X3.V4乙玲AXlX8丙X9由。孙X12T13XI4X5XlS(2)确定目标函数本问题的目标是所得总的创利为最多，