第二章运筹作业

2.2将下列线性规划问题模型化为标准型1231max23zxxx12354123363123101,20,3xxxxxxxxxxxx无约束解:对两个约束不等式分别加上一个松弛变量45,xx。并令333'''xxx则1233412312334512331233512334123312335123345max23'''50'''5103'''033'''10'''543'3''63'''10,,','',,0zxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx即1231231231234113331231233412312341232min224280,0,'minmax',','''max'222'2'2''82028'2'zxxxxxxxxxxxxzzzxxxxxxzxxxxxxxxxxxxxxxxxx无约束解：令z对约束不等式加上一个松弛变量并令34123312334123342''8''''4'2'2''8',,','',0xxxxxxxxxxxxxxxx即3max23,''',''',0'0,00,0'',,0'0,00,0'',0''','''''''''zxyxyxxyxxxyyyxxxxxxxxyyyyyyyyxxxyyyxxyy无约束解：对题中两个约束不等式分别引入一个松弛变量A,B并令即maxz=-0''''''''''''2'''3','',','',,0xxyyxxyyAxxBxxyyAB2.3找出下列线性规划问题的所有基本解，并指出其中的基本可行解和最优解123412112212341,,023812321,2,0,023472*13*24*07*081,32,445121381316331431345013xxxxxxxxxxzxxxxxxxxxxxxxx令为基变量，为非基变量且取值为则则基本解为令为基变量，为非基变量则则基本解为，12341214,013347117,0Z3554571630016161668700292968450,031311175,,02zxxxxxx，，不是基本可行解以此类推可得基本解为：，0，是基本可行解，=，，，是基本可行解，，，，-不是基本可行解，，不是基本可行解则最优解为maxz=（2）令为基变量，为非基变量且取值为则112217111300231133321143005552110,0660,2,1,010,0,1,13min3xxxxzzz则基本解为，，，，不是基本可行解以此类推可得基本解如下：，，，是基本可行解，z=，，不是基本可行解是基本可行解，是基本可行解，则最优解为2.5求解下列线性规划问题123451234125123451B123454(1)max20*0*2426,,,,0XBbXXXXX0xBzxxxxxxxxxxxxxxxxxC将该线性规划问题化为标准型单纯形表如下：-12100544211100x612001Z01-2-1000X12321011-32112X310022Z620-10131X10244111-2112X31002251Z700122031,X223因为检验数全都，所以此线性规划问题有最优解即最优解为X=。目标函数最优值为MAXZ=7123412312412341B12343MAXZ=30*0*236,,,0XBbXXXX0X2-11BxxxxxxxxxxxxxxC(2)化为标准型如下：3-100431100X63-101Z0-3100210X401333X2131234111-033Z600010,X44214xxxxx112345因为检验数全都，所以此线性规划问题有最优解且为多重最优解即最优解为X=2。目标函数最优值为MINZ=-6(3)化为标准型如下：MAXZ=3x+5x+x+0*x+x*x235123451B1234454,,,,0XBbXXXXX50X14-421100XBxxxxxxxxC35100424-11-101Z0-3-5-1000X6-2030-25X4-11-101Z20-80-605因为X1这一进基变量所对应的列全为负数，所以此题为无解，有无界解。2.6分别用二阶段法和大M法求解下列线性规划问题，并指出属于哪一类解1B1:maxz'=-2x1-5x2+0*x4+0*x521234662335791,2,3,4,5,6,70maxw=-x6-x7-1-1XBbXBxxxxxxxxxxxxxxxxC两阶段法化为标准型为：构造一个临时目标函数第一阶段：00000234567XXXXX6X7-1X6211-1010-1X90130-10631W-15-2-2-41100211-1X320-11-33310X30311110-033214W-3-2-01-03332111110X10--33262603111X3010-0333W00000011W=0,则原问题有可行解。-2-501B1234513XBbXXXXX2111-2X10-3326110X3010-33BC0053131Z-3001-330X9620-310X6211-1035Z02500006,X90因为检验数全都，所以此线性规划问题有最优解且为多重最优解即最优解为X=。目标函数最优值为MINZ=12671B12345M'=-2x-5x-Mx-Mx21234662335791,2,3,4,5,6,70-2-5-M-MXBbXXXXXBxxxxxxxxxxxxxxxxC大法:构造目标函数minz0006767XX-MX6211-1010-MX90130-101Z-15M632-2M5-2M-4MMM00211-MX320-11-333110X3010-3353103214Z-3M2-2M5-M0M-M0M3330X9620-113-10X6235111-0103Z025000MM0,X40因为检验数全都，所以此线性规划问题有最优解即最优解为X=2。目标函数最优值为MINZ=2.8写出下列线性规划问题的对偶问题12312312313123123123121231231231231231(1)maxz=2x+x+5x235237365,,0minw=2y+3y+5y232315765,,0(2)maxz=x+x+x2512276xxxxxxxxxxxyyyyyyyyyyyxxxxxxx对偶问题为：3123123123121231321231231312364,,0minw=12y+6y+4y212157610,0,25627462,0,0xxxxyyyyyyyyyyyxxxxxxxxxxx123对偶问题为：无约束（3）minz=4x+2x+3x无约束对偶问题12312312123132maxw=6y+4y+2y24225730,0,yyyyyyyyyyy为：无约束2.9试用对偶单纯形法求解下列线性规划问题1B12212417371,2021234173471,2,3,40XBbXXXBxxxxxxxxxxxxxxxxC（1）minz=x1+x2s.t.解：化为标准型为：maxz=-x1-x2单纯行法迭代表如下：-1-10034343X0X-4-2-1100X-7-1-701Z011000X-3-21213101-7711-1X110-7761Z-1007721131-1X10-137131-1X01201-1313133161Z-001313130211031,X2131313因为检验数全都，所以此线性规划问题有最优解即最优解为X1=。目标函数最优值为MINZ=123123123123123412351236123,562354934638,,02354934638,,4,,0xxxxxxxxxxxxxxxxxxxxxxxxxxxxxx123123（2）maxz=2x-x+x解：化为标准形为：maxz=2x-x+x此题的目标函数中的系数不全为正，所以不能用对偶单纯形法求解。利用两阶段法构造一个临时目标函数1B123456787-1-1XBbXXXXXXXX-1X42BC78maxw=-x-x单纯形表如下：000000863-5-10010-1X3-19-10-10010X8463700100W-7-1-126110007141-1X30--133326101-3111110X-1-0-0039999141120X60010333122-371414W-3-01-003333931310X10-2-0-77777100X261121201---013212121210X00013201-20W0000000110,W则原问题有可行解1B1234561XBbXXXXXX9312X10-2-0777BC2-110002610112-1X01---021321210X0001320144Z02112141780--032121911122X100-79171310121-1X010-2127321393121-1X0001013134425814Z000-21273213992X172414313900182718210121-1X01-0-21422142130X0001224=102443258221Z0002154621546091044,X,X0MAX721211因为检验数全都，所以此线性规划问题有最优解即最优解为X=。目标函数最优值为Z=2.12证明运输问题中，任何一个方程可以取作多余方程111111111A=111111111证明：产销平衡运输问题的系数矩阵为：1,mnijijjab由平衡条件可知产销平衡运输模型中有m+n个方程，只有m+n-1个方程独立。所以任何一个方程可以取作多余方程。2.13判别下3个表所给出的调运方案可否作为表上作业法求解时的初始解（a）销地产地B1B2B3B4B5B6产量A120525A2252055A31515401080A42020销量203045154030可作为初始方案，因为数格为9=m+n-1个(b)销地产地B1B2B3B4B5B6产量A13030A2102535A3152552065A42020销