运筹学第一二章习题.doc

1.11用单纯形法求解下列线性规划(1)【解】单纯形表：C(j)34100R. H. S.RatioBasisC(i)X1X2X3X4X5X402311011/3X501220133/2C(j)-Z(j)341000X242/311/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）；最优值Z3/2 (2) 【解】单纯形表：C(j)21-35000R. H. S.RatioBasisC(i)X1X2X3X4X5X6X7X50153-710030MX603-1110101010X702-6-14001205C(j)-Z(j)21-35000X509/2-11/25/40107/465MX605/21/25/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因为730并且ai70(i=1,2,3)，故原问题具有无界解，即无最优解。 (3)【解】C(j)32-0.125000R. H. S.RatioBasisC(i)X1X2X3X4X5X6X40-1231004MX5040-2010123X603840011010/3C(j)-Z(j)32-1/80000X40025/211/4073.5X1310-1/201/403MX600811/20-3/4111/8C(j)-Z(j)0211/80-3/409X40009/817/16-1/427/46X1310-1/201/403MX220111/160-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原问题具有多重解。基本最优解,最优解的通解可表示为即（4）【解】单纯形表：C(j)32100R. H. S.RatioBasisC(i)X1X2X3X4X5X4054610255X5086301243C(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）；最优值Z91.14已知线性规划的最优基为，试用矩阵公式求（1）最优解；(2)单纯形乘子；(3)(4)【解】则(1)(2)(3)(4)注：该题有多重解：X(1)=(0，5，0，5/2)X(2)=(0，10/3，10/3，0)X(3)=(10，0，0，0)，x2是基变量，X(3)是退化基本可行解Z501.15 已知某线性规划的单纯形表128, 求价值系数向量C及目标函数值Z表128Cjc1c2c3c4c5c6c7bCBXBx1x2x3x4x5x6x73x4012130244x1101020100x601404123/2j0110102【解】由有c21（31400（1）2c31（324（1）04）1c51（3（3）420（4）0则(4,2,1,3,0,0,0,)，Z=CBXB=12 1.16 已知线性规划的最优单纯形表如表129所示，求原线性规划矩阵C、A、及b，最优基B及表129Cjc1c2c3c4c5bCBXBx1x2x3x4x5c1x11041/61/156c2x201301/52j00123【解】，c4c50，仿照第15题方法可求出c112，c211，c314由 得 由 得 则有 ，1.17 已知线性规划的单纯形表130表130Cj3a11bCBXBx1x2x3x41x32210b11x43101b2j1234当=（ ）,=（ ）,a=（ ）时，为唯一最优解.当=（ ）,=（ ）,a=（ ）时，有多重解，此时（ ）【解】(1)b10,b20,a-3 (2)b10,b20,a=3, (2,0,0,0)2.3考虑线性规划(1)说明原问题与对偶问题都有最优解；(2)通过解对偶问题由最优表中观察出原问题的最优解；(3)利用公式CBB1求原问题的最优解；(4)利用互补松弛条件求原问题的最优解【解】(1)原问题的对偶问题为容易看出原问题和对偶问题都有可行解，如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)，Z42.4（3）CB=(7,4), (4)由y1、y3不等于零知原问题第一、三个约束是紧的，解等式得到原问题的最优解为X=(16/5，1/5)。2.4证明下列线性规划问题无最优解证明：首先看到该问题存在可行解，例如x=(2,1,1)，而上述问题的对偶问题为由约束条件知y10，由约束条件当y20知y11，对偶问题无可行解，因此原问题也无最优解(无界解)。2.5已知线性规划的最优解，求对偶问题的最优解【解】其对偶问题是：由原问题的最优解知，原问题约束的松弛变量不等于零()，x1、x3不等于零，则对偶问题的约束、约束为等式，又由于知y30；解方程得到对偶问题的最优解Y=(5/2,5/2,0)；w55/227.52.6用对偶单纯形法求解下列线性规划 【解】将模型化为对偶单纯形表：cj34500CBXBX1X2X3X4X5b00X4X51222311001810C(j)-Z(j)34500003X4X101115/21/2101/21/235C(j)-Z(j)017/203/2053X2X101105/22111/2132C(j)-Z(j)00111b列全为非负，最优解为x(2，3，0)；Z18 【解】将模型化为3400 b XB CB X1 X2 X3 X4 X30-1-110-4 X4021012CjZj3400 X1311-104 X400-121-6CjZj0130 X131011-2 X2401-2-16CjZj0051出基行系数全部非负，最小比值失效，原问题无可行解。7某工厂利用原材料甲、乙、丙生产产品A、B、C，有关资料见表2-23表2-23产品材料消耗材料 产品材料消耗原材料ABC每月可供原材料（Kg）甲乙丙211200123500221600每件产品利润413（1）怎样安排生产，使利润最大（2）若增加1kg原材料甲，总利润增加多少（3）设原材料乙的市场价格为1.2元/Kg，若要转卖原材料乙，工厂应至少叫价多少，为什么？（4）单位产品利润分别在什么范围内变化时，原生产计划不变（5）原材料分别单独在什么范围内波动时，仍只生产A和C两种产品（6）由于市场的变化，产品B、C的单件利润变为3元和2元，这时应如何调整生产计划（7）工厂计划生产新产品D，每件产品D消耗原材料甲、乙、丙分别为2kg，2kg及1kg，每件产品D应获利多少时才有利于投产【解】（1）设 x1、x2、x3分别为产品A、B、C的月生产量，数学模型为最优单纯形表：C(j)413000R.H.S.Ratio XB CBX1X2X3X4X5X6X1411/503/5-1/5020X3303/51-1/52/50160X60000-101400C(j)-Z(j)0-8/50-9/5-2/50Z=560最优解X=（20，0，160），Z=560。工厂应生产产品A20件，产品C160种，总利润为560元。（2）由最优表可知，影子价格为,故增加利润1.8元。（3）因为y2=0.4，所以叫价应不少于1.6元。（4）依据最优表计算得（5）依据最优表计算得（6）变化后的检验数为2=1,4=-2,5=0。故x2进基x1出基,得到最最优解X=(0,200,0)，即只生产产品B 200件,总利润为600元。C(j)432000R.H.S.Ratio XB CBX1X2X3X4X5X6X1411/503/5-1/5020100X3203/51-1/52/50160800/3X60000-101400MC(j)-