第六章 整数规划.docx
第六章整数规划6.1用图形将一下列线性规划问题的可行域转换为纯整数问题的可行域（在图上用“X”标出）。1、maxz=3x÷2x2S.T.2x+3x2122xi+X29x.M20解：X28-A62、mini=10xi+9x2S.T.5x+3m245Xi28X210x.M206.2求解下列整数规划问题1、minf=4x÷3x2÷2x3S.T.2x-5x2÷3x344xi+m+3x323x2+x3.1x1.x2.x3=0或1解：将模型代入求解模板求解0-1整数规划模板返回首页我总荥IW结果妁虫备件*孰暴漕然幽一，可高足所有的妁束及最忧约栗条村为束约束条件冬际的美系窠利通O恢复为网的(Q)I睚i【IBifl1|供存方案0).I硒()J即：最优解(0,0,1),最优值：22、minf=2x+5M+3x3+4x3S.T.-4+x2+x3+x4.2-2x+4x2+22÷4x224x+x2-x2+x23XLX2、X3、X3=0或1解：此模型没有可行解。3、maxZ=2x+3x2+5%3+4S.T.5x+3x2+3%3+X4302x+5X2-X2÷3X220-XI+3<v2+52+32403x-X2+3x2+5x225Xl.初、43、X3=正整数解：代入模板求解返回首页纯整数规划模板约束条件妁束约束条件I£_3_, 567 8 elonE且 H15J6171819204发组应252627282930E理空Sl即：最优解(0,3,4,3),最优值：474、minZ=8x+4刈+3X3÷5xa+2总+3抵+4为+3+4后+9Xlo+7XIl+5x2÷0x3÷4xi4÷2X15+175x6÷300x+375x+5009约束条件Xl+X2÷X330X4+X5÷X6-10x60X7+X8÷X9-20x7OXl+XiI÷2-30x80X13+X14+X15-40X190Xl+X+X7÷Xi0+XI3=30Xl+X5+Xg+Xll+X4=20Xy+x+X9+X12+X5=20为为非负数(i=l,28)H为非负整数(i=9,10.15)H为为01变量G=16,1719)解：代入模板求解正合整数规划模板33村严六si“'FJ直返回首页I即：最优解(30,0,0,0,0,0,0,0,0,0,0,0,0,20,20,0,0,0,1),最优值：8606.3一餐饮企业准备在全市范围内扩展业务，将从已拟定的14个点中确定8个点建立分店，由于地理位置、环境条件不同，建每个分店所用的费用将有所不同，现拟定的14个店的费用情况如下表：店名BiB2B3B4B5B6B7B8B9BioBnBl2B13Bi4费用（万元）1.21.51.72.13.31.22.82.51.93.02.42.42.11.6公司办公会决定选择原则如下：（I）B2、B3和B7只能选择一个°（2）选择了Bl或Bm就不能选B6。（3）B2、B6、BrBi2,最多只能选两个。（4）B5、B7、Bio、B8,最少要选两个。问应选择哪几个点，使总的建店费用为最低？解：1、确定决策变量设01变量Xi=1,当Bj点被选用；0,当Bj点没被选用。这里i=l,2142、确定目标函数这样我们可建立如下的数学模型：minf=1.2j+1.5x2+l7xj÷2.1A4+3.3X5+L2a+2.8x÷2.5's÷l.9乃+3xo+2.4x+2.4XI2+2.1x3+l.6x43、确定约束条件x+x2+x3+x4+x5+46+x7+x8+x9+x)+T+412+x13+x14=8共选8个%2÷X3+X7=1或选Bs和Ba»或选择B?Xl+X6=l选择了Bl或Bm就不能选BbX6÷Xi4=1选择了B或BM就不能选BbX2+.t6+Xl+,22B2、B6、Bl、BI2、最多只能选两个X5+M+X8+Xo22B5、B、Bn）、B8、最少要选两个minf=1.2x+1.5也+1.7幻+2.1&+3.3x5÷1.2抵+2.8x+2.5xs+1.9刈+3XlO+2.4x+2.4x2+2.lx3+l.6x4S.T.X+X2+X3+X4+X5+fe+X7+X8+X9+X+X!l+X12+X3÷X14=8x2+x3+x7=l工+X6=16÷X4=1X2+X6+Xh+X22X5+X7+X8+X02X1,0KXi为01变量，/=1,2,3,14o代入模板求解I19 4|×1x2«3x4x5x)x7×9xlxll 1x12x14×151x16I 12I J5173 32 5192 4| 2 41 6 I0-1整数规划模板返回首页I1111111118bl11111I 31111:111t>45111I26I14-0*03k90100biOE0Gbll1204bl21304t)131404bl41120bl5160b!60t>17180¼bl8190t)19200一 L妁条件或，约束条件约束约束条件实际值美系客数吸最优解：(0,0,0,1,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乙7568丙3435T7688解：1、消耗时间为最少问题（1）确定决策变量设0-1变量如下表，各变量表示是否分配给工作，0为不分配，1为分配。所工作需工人工作A工作B工作C工作D甲XiXi-X3乙-XaX5X6丙Xj即X9-VioT-VllX2.5-(2)确定目标函数本问题的目标是所用总的时间为最少，而总时间为：18x+16x2÷19-3+204÷16xs+2Ch+19力+18+17x9÷2Lvo÷12,i+15x2÷20xi3所以目标函数为：minJ=18x+l6x2+193+2x4+16x5+2(h+19幻+18+17x9+2lxo÷12xn+15x2+20x3(3)确定约束条件因为每人只能分配一项工作所以对于每人而言X+42+X3=1x4+5+x6=1X7+X8+X9+X1O=1Xll+X12+X13=l又每项工作只能分配给一个人人，所以对于每项工作X+X7÷X11=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=1Xix)且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)确定目标函数本问题的目标是所得总的创利为最多，
