运筹学第一二章习题

1.11用单纯形法求解下列线性规划(1)123123123max342312230,1,2,3jZxxxxxxxxxxj【解】单纯形表：C(j)34100R.H.S.RatioBasisC(i)X1X2X3X4X5X402[3]11011/3X501220133/2C(j)-Z(j)341000X24[2/3]11/31/301/31/2X50-1/304/3-2/317/3MC(j)-Z(j)1/30-1/3-4/30-4/3X1313/21/21/201/2X5001/23/2-1/215/2C(j)-Z(j)0-1/2-1/2-3/20-3/2最优解：X=（1/2，0，0，0，5/2）；最优值Z＝3/2(2)1234123412341234max23553730310264200,1,,4jZxxxxxxxxxxxxxxxxxj【解】单纯形表：C(j)21-35000R.H.S.RatioBasisC(i)X1X2X3X4X5X6X7X50153-710030MX603-1[1]10101010X702-6-1[4]001205C(j)-Z(j)21-35000X509/2-11/25/40107/465MX605/2[1/2]5/4001-1/4510X451/2-3/2-1/41001/45MC(j)-Z(j)-1/217/2-7/4000-5/4X50320150111-1120MX21515/2002-1/21010X45807/2103-1/220MC(j)-Z(j)-430-2300-173因为λ7＝30并且ai70(i=1,2,3)，故原问题具有无界解，即无最优解。(3)1123812313123123max32234421238410,,0Zxxxxxxxxxxxxxx【解】C(j)32-0.125000R.H.S.RatioBasisC(i)X1X2X3X4X5X6X40-1231004MX50[4]0-2010123X603840011010/3C(j)-Z(j)32-1/80000X40025/211/4073.5X1310-1/201/403MX600[8]11/20-3/4111/8C(j)-Z(j)0211/80-3/409X40009/817/16-1/427/46X1310-1/201/403MX2201[11/16]0-3/321/81/80.181818C(j)-Z(j)0000-9/16-1/437/4X3进基、X2出基，得到另一个基本最优解。C(j)32-0.125000R.H.S.RatioBasisX1X2X3X4X5X6X400-18/110113/22-5/1172/116X1318/11002/111/1134/11MX3-0.125016/1110-3/222/112/110.1818C(j)-Z(j)0000-9/16-1/437/4原问题具有多重解。基本最优解(1)(2)1273427237(3,,0,,0)(,0,,,0);841111114TXXZ及,最优解的通解可表示为)2()1()1(XaaXX即3411227272(,,,,0),(01)1111811111111TXaaaaa（4）123123123max3254625863240,1,2,3jZxxxxxxxxxxj【解】单纯形表：C(j)32100R.H.S.RatioBasisC(i)X1X2X3X4X5X4054610255X50[8]6301243C(j)-Z(j)321000X4001/433/81-5/810X1313/43/801/83C(j)-Z(j)0-1/4-1/80-3/89最优解：X=（3，0，0，10，0）；最优值Z＝91.14已知线性规划123412341234max58742332203542300,1,,4jzxxxxxxxxxxxxxj的最优基为B2325，试用矩阵公式求（1）最优解；(2)单纯形乘子；(3)NN13及；(4)13和。【解】1425344,(,)(4,8,),1122BBCcc则(1)14255(,)(,5)(0,5,0,),5022TTTBXxxBbXZ,最优解(2))1,1(1BCB(3)1111335312444113122253334441141222NBPNBP(4)111333145(4,8)55012347(4,8)77012BBcCNcCN注：该题有多重解：X(1)=(0，5，0，5/2)X(2)=(0，10/3，10/3，0)X(3)=(10，0，0，0)，x2是基变量，X(3)是退化基本可行解Z＝501.15已知某线性规划的单纯形表1－28,求价值系数向量C及目标函数值Z．表1－28Cjc1c2c3c4c5c6c7bCBXBx1x2x3x4x5x6x73x40121－30244x110－1020－100x60－140－4123/2λj0－1－1010－2【解】由jjiijicca有jjiijiccac2＝－1＋（3×1＋4×0＋0×（－1））＝2c3＝－1＋（3×2＋4×（－1）＋0×4）＝1c5＝1＋（3×（－3）＋4×2＋0×（－4））＝0则λ＝(4,2,1,3,0,0,0,)，Z=CBXB=121.16已知线性规划332211maxxcxcxcZ0,,32123232221211313212111xxxbxaxaxabxaxaxa的最优单纯形表如表1－29所示，求原线性规划矩阵C、A、及b，最优基B及B1．表1－29Cjc1c2c3c4c5bCBXBx1x2x3x4x5c1x11041/61/156c2x201－301/52λj00－1－2－3【解】11162615,05105BB，c4＝c5＝0，仿照第15题方法可求出c1＝12，c2＝11，c3＝14由1ABA得621046230050130515ABA由1bBb得6263205210bBb则有623032(12,11,14),,051510CAb，11162615,05105BB1.17已知线性规划的单纯形表1－30．表1－30Cj－3a－1－1bCBXBx1x2x3x4－1x3－2210b1－1x43101b2λjλ1λ2λ3λ4当b1=（）,b2=（）,a=（）时，),,0,0(21bbX＝为唯一最优解.当b1=（）,b2=（）,a=（）时，有多重解，此时λ＝（）【解】(1)b1≥0,b2≥0,a-3(2)b1≥0,b2≥0,a=－3,λ＝(－2,0,0,0)2.3考虑线性规划0,73225442012min2121212121xxxxxxxxxxZ(1)说明原问题与对偶问题都有最优解；(2)通过解对偶问题由最优表中观察出原问题的最优解；(3)利用公式CBB－1求原问题的最优解；(4)利用互补松弛条件求原问题的最优解．【解】(1)原问题的对偶问题为123123123max427212453200,1,2,3jwyyyyyyyyyyj容易看出原问题和对偶问题都有可行解，如X＝(2，1)、Y＝(1，0，1)，由定理2.4知都有最优解。(2)对偶问题最优单纯形表为C(j)42700R.H.S.BasisC(i)y1y2y3y4y5y370-1/514/5-1/528/5y1417/50-3/52/54/5C(j)-Z(j)0-11/50-16/5-1/5w=42.4对偶问题的最优解Y＝(4/5,0,28/5)，由定理2.6，原问题的最优解为X=(16/5，1/5)，Z＝42.4（3）CB=(7,4),141553255B,4155(7,4)(16/5,1/5)3255X(4)由y1、y3不等于零知原问题第一、三个约束是紧的，解等式121244237xxxx得到原问题的最优解为X=(16/5，1/5)。2.4证明下列线性规划问题无最优解无约束321321321321,0,23232222minxxxxxxxxxxxxZ证明：首先看到该问题存在可行解，例如x=(2,1,1)，而上述问题的对偶问题为1212121221max3221222320,wyyyyyyyyyy无约束由约束条件①②知y1≤0，由约束条件③当y2≥0知y1≥1，对偶问题无可行解，因此原问题也无最优解(无界解)。2.5已知线性规划123123123123123max152055556631070,0,Zxxxxxxxxxxxxxxx无约束的最优解119(,0,)44TX，求对偶问题的最优解．【解】其对偶问题是：123123123123123min56753155610205,,0wyyyyyyyyyyyyyyy由原问题的最优解知，原问题约束③的松弛变量不等于零(30sx)，x1、x3不等于零，则对偶问题的约束①、约束③为等式，又由于30sx知y3＝0；解方程12125155yyyy得到对偶问题的最优解Y=(5/2,5/2,0)；w＝55/2＝27.52.6用对偶单纯形法求解下列线性规划0,,1022832543min1321321321321xxxxxxxxxxxxZ）（【解】将模型化为12312341235min34523822100,1,2,3,4,5jZxxxxxxxxxxxxj对偶单纯形表：cj34500CBXBX1X2X3X4X5b00X4X5－1[－2]－2－2－3－11001－8－10C(j)-Z(j)34500003X4X101[－1]1－5/21/210－1/2－1/2－35C(j)-Z(j)017/203/2053X2X101105/2－2－111/2－132C(j)-Z(j)00111b列全为非负，最优解为x＝(2，3，0)；Z＝180,022443min221212121xxxxxxxxZ）（【解】将模型化为12123124min344220,1,2,3,4jZxxxxxxxxxj3400bXBCBX1X2X3X4X30[-1]-110-4X4021012Cj－Zj3400X1311-104X400[-1]21-6Cj－Zj0130X131011-2X2401-2-16Cj－Zj0051出基行系数全部非负，最小比值失效，原问题无可行解。7．某工厂利用原材料甲、乙、丙生产产品A、B、C，有关资料见表2-23．表2-23产品材料消耗原材料ABC每月可供原材料（Kg）甲乙丙211200123500221600每件产品利润413（1）怎样安排生产，使利润最大．（2）若增加1kg原材料甲，总利润增加多少．（3）设原材料乙的市场价格为1.2元/Kg，若要转卖原材料乙，工