12-13运筹学练习.doc

1.填空 ；1，在将任意线性规划化为标准形时，若某个变量xj无符号限制，则应作替换 .（xj=xj-xj, xj,xj0）2，若线性规划的最优单纯形表中某个非基变量的检验数为0，说明该线性规划解的情况是 无穷多最优解 .3，线性规划问题中基解与基可行解的区别是 基可行解中每个分量均0 。4，设有线性规划问题，有一可行基B，记相应基变量为XB ，非基变量为XN，则可行解的定义为 满足的解 ，基本可行解的定义为 满足的解 ，B为最优基的条件是 满足且使达最大的解 5，在线性规划模型中，松弛变量的经济意义是 剩余的资源 ，它在目标函数中的系数是 0 。（）6，线性规划模型的可行域的顶点与基本可行解的个数 相同 ，若其有最优解，必能在 可行域的顶点 上获得。因此，单纯型法是在 基可行解 ，中寻优。7，标准形线性规划的可行域中的点是D的顶点的充分必要条件是 , X是一个基本可行解 8，某工程公司拟从四个项目中选择若干项目，若令用的线性表达式表示从1，2，3项目中至少选2个 ： , ；只有项目2被选中，项目4才能被选中： 。9.标准形线性规划目标函数的矩阵形式是_ maxZ=CBB1b+(CNCBB1N)XN 。10.在用图解法求解线性规划问题时，如果取得极值的等值线与可行域的一段边界重合，则这段边界上的一切点都是最优解。11.对于求目标函数最小值的线性规划，直接利用单纯形方法求解时，基可行解为最优的标准是 所有检验数均0 。12，若线性规划的最优单纯形表中某个非基变量的检验数为0，说明该线性规划解的情况是 无穷多最优解 .13，在线性规划标准形中，所有约束条件都是用等号连接的，等号右侧必须是 非负 ，而且每个变量都 0 .14，在求线性规划最优解的每一张单纯形表中，每个基变量所对应的列向量都是 单位列向量 ，每个非基变量的值都 等于零 .15，在用单纯形法求线性规划问题最优解的进行迭代过程中，应先确定 进基 变量，再确定 出基 变量.16.在求解线性规划的两阶段方法中， 第一步要求解一个目标仅 人工 变量，且为极 小 化的线性规划问题。17. 若用大M法给出线性规划的第一个基可行解, 则在求得最优解时，如有某个人工变量是基变量，说明原线性规划解的可行域是 是空集 .18. 在对偶单纯形法迭代中，若某bi0，且所有的aij0(j=1，2，n)，则原问题_无解。19线性规划问题的最优基为B，基变量的目标系数为CB，则其对偶问题的最优解Y= CBB1。20若X和Y分别是线性规划的原问题和对偶问题的最优解，则有 CX=Yb 。21设、分别是标准形式的原问题与对偶问题的可行解,则 CX Yb 。22，线性规划模型的数据经常会发生变化，在求得线性规划最优解时要对这种变化进行分析，这种分析称为 灵敏度分析 .23，若在线性规划模型中，约束条件右边的数据即向量b发生变化，那么它只能对已求最优单纯形表中的 基变量的解 产生影响.24当cj是非基变量的某个价值系数时，它的变化在单纯形表中 只影响一个检验数 。25. 影子价格实际上是与原问题各约束条件相联系的对偶变量的数量表现。26. 如果某种资源的影子价格大于其市场价格，则说明_该资源稀缺 .27. 影子价格是对偶最优解，其经济意义为 约束资源的供应限制 .28、供大于求的、供不应求的不平衡运输问题，分别是指_的运输问题、_的运输问题。29在表上作业法所得到的调运方案中，从某空格出发的闭回路的转角点所对应的变量必为基变量。30在某运输问题的调运方案中，点(2，2)的检验数为负值，(调运方案为表所示)则相应的调整量应为300_。IA300100300B400C60030031.在编制初始方案调运方案及调整中，如出现退化，则某一个或多个点处应填入数字032.在运输问题中，单位运价为Cij位势分别用ui，Vj表示，则在基变量处有cij Cij=ui+Vj 。33. .运输问题中，每一行或列若有闭回路的顶点，则必有两个。34. 运输问题的模型中，含有的方程个数为n+M个。35表上作业法中，每一次调整，“出基变量”的个数为1个。2.计算1.将下列线性规划化为标准形. 解:设z=-z, x1=-x11, x2=x21-x22 , x21 ,x220,添加松弛变量x4剩余变量x5, .得标准形: maxz =7x11-4x21+4x22+3x3s.t. 4 x11+2x21-2x22-6x3+x4 =24 3 x11-6x21+6x22-4x3 -x5 =15 5x21-5x22+3x3 =30 xj0, j=3.4,5; x1 ,x21 ,x220 2.某工厂可生产甲、乙两种产品，需消耗煤、电、油三种资源。现将有关数据列表如下： 资源单耗 产品资源甲 乙资源限量煤电油9 44 53 10360200300单位产品价格7 12 .试拟订使总收入最大的生产方案，并求出最优解。 解：设安排甲、乙产量分别 为 ,总收入为 Z ， 则模型为： 标准化模型为 单纯形终表如下： 0 X3 847 X1 2012 X2 240 0 1 -3.12 1.161 0 0 0.4 -0.20 1 0 -0.12 0.16Z*=4280 0 0 -1.36 -0.523-1. 两步单纯形表如下，试在第二张表中填空，并写出主要计算公式，分析是否为最优表，说明理由cj20121153CB基bx1x2x3x4x5x61x4246401021x361210035x51-110011cj-zj181000-720x1-1/21/4012x26/8-1/805x5-5/43/81cj-zj解：20x1310-1/21/40-112x23/2016/8-1/8025x55/200-5/43/81-2cj-zj0033/4-35/809计算公式为 由于检验数有大于零的情况，故此表非最优表。 3-2.已知某两步单纯形表如下，试在第二张表中填空，并写出主要计算公式，分析是否为最优表，说明理由cj354000CB基bx1x2x3x4x5x65x28/32/3101/3000x514/3 -4/305 -2/3100x620/35/304-2/301cj-zj -1/304-5/300x215/418/41-10/41x3-6/415/414/41x1-2/41-12/4115/41cj-zj解:5x280/4101015/418/41-10/414x350/41001-6/415/414/413x144/41100-2/41-12/4115/41cj-zj000-45/41-24/41-11/41计算公式为 由于检验数全小于等于零，故此表最优。 4.分别用图解法和单纯形法求解下列线性规划，指出单纯形法迭代的每一步的基可行解对应于图形上的那一个极点 (1)【解】图解法单纯形法：C(j)1300bRatioC(i)BasisX1X2X3X40X3-2110220X42301124C(j)-Z(j)130003X2-21102M0X480-3160.75C(j)-Z(j)70-3063X2010.250.257/21X110-0.3750.1253/4C(j)-Z(j)00-0.375-0.87511.25对应的顶点：基可行解可行域的顶点X(1)=（0，0，2，12）、X(2)=（0，2，0，6，）、X(3)=（、（0，0）（0，2）最优解5. 已知线性规划的最优单纯形表如表126所示，求原线性规划矩阵C、A、及b，最优基B及表126Cjc1c2c3c4c5bCBXBx1x2x3x4x5c1x11041/61/156c2x201301/52j00123【解】，c4c50，由可求出c112，c211，c314由 得 由 得 则有 ，6. 已知线性规划的最优基为，试用矩阵公式求（1）最优解；(2)； (3)【解】则(1)(2)(3)注：该题有多重解：X(1)=(0，5，0，5/2)X(2)=(0，10/3，10/3，0)X(3)=(10，0，0，0)，x2是基变量，X(3)是退化基本可行解Z50 7. 某人根据医嘱，每天需补充A、B、C三种营养，A不少于80单位，B不少于150单位，C不少于180单位此人准备每天从六种食物中摄取这三种营养成分已知六种食物每百克的营养成分含量及食物价格如表2-22所示（1）试建立此人在满足健康需要的基础上花费最少的数学模型；（2）假定有一个厂商计划生产一中药丸，售给此人服用，药丸中包含有A，B，C三种营养成分试为厂商制定一个药丸的合理价格，既使此人愿意购买，又使厂商能获得最大利益，建立数学模型表2-22含量 食物营养成分一二三四五六需要量A1325144081180B24930251215150C1872134100180食物单价（元/100g）0.50.40.80.90.30.2【解】（1）设xj为每天第j种食物的用量，数学模型为（2）设yi为第i种单位营养的价格，则数学模型为8. 分别用大M法和两阶段法求解下列线性规划： (1) 【解】大M法。数学模型为C(j)10-510-MR. H. S.BasisC(i)X1X2X3X4X5X5-M5310110X40-51-101015C(j)-Z(j)10-51000X11013/51/501/52X4004-91125C(j)-Z(j)0-11-10-220最优解X(2,0,0)；Z=20两阶段法。第一阶段：数学模型为C(j)00001R. H. S.BasisC(i)X1X2X3X4X5X515310110X40-51-101015C(j)-Z(j)-5-3-100X1013/51/501/52X4004-91125C(j)-Z(j)00001第二阶段C(j)10-510R. H. S.BasisC(i)X1X2X3X4X11013/51/502X4004-9125C(j)-Z(j)0-11-10最优解X=(2,0,0)；Z=20(2) 【解】大M法。数学模型为C(j)5-6-700MMR.H.S.BasisC(i)X1X2X3S1S2A1A3A1M15-3-101015S205-610010020A3M11100015C(j)-Z(j)5-6-70000X2-61/51-3/5-1/501/503S2031/5032/5-6/516/5038A3M4/508/51/50-1/512C(j)-Z(j)31/50-53/5-6/506/50X2-61/210-1/801/83/815/4S20300-212-430X3-71/2011/80-1/85/85/4C(j)-Z(j)23/2001/80-1/853/8两阶段法。第一阶段：数学模型为C(j)0000011R.H.S.BasisC(i)X1X2X3S1S2A1A3A1115-3-101015S205-610010020A3111100015C(j)-Z(j)-2-621000X201/51-3/5-1/501/503S2031/5032/5-6/516/5038A314/508/51/50-1/512C(j)-Z(j)-0.80-1.6-0.201.20X201/210-1/801/83/815/4S20300-212-430X301/2011/80-1/85/85/4C(j)-Z(j)0000011第二阶段：C(j)5-6-700R.H.S.RatioBasisC(i)X1X2X3S1S2X2-61/210-1/8015/4S20300-2130X3-71/2011/805/4C(j)-Z(j)23/2001/80最优解：X=(0，3.75，1.25)；Z=31.25 即 9.10. 考虑线性规划 对偶问题由最优表如下：C(j)42700by1y2y3y4y5y370-1/514/5-1/528/5y1417/50-3/52/54/5C(j)-Z(j)0-11/50-16/5-1/5w=42.4(1)通过解对偶问题由最优表中观察出原问题的最优解；(2) 利用互补松弛条件求原问题的最优解【解】原问题的对偶问题为 (1)对偶问题最优单纯形表为对偶问题的最优解Y(4/5,0,28/5)，原问题的最优解为X=(16/5，1/5)，Z42.4（2）由y1、y3不等于零知原问题第一、三个约束是紧的，解等式得到原问题的最优解为X=(16/5，1/5)。11. 已知线性规划问题。（1）写出其对偶问题；（2）已知原问题的最优解为 试用对偶理论，直接求对偶问题的最优解。解: (1)设对偶变量为, 所求对偶规划为 (2) 运用对偶理论，将最优解代入原问题的约束条件，得，且有：, 解方程可得 即 12. 用对偶单纯形法求解下列线性规划 【解】将模型化为对偶单纯形表：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出基行系数全部非负，最小比值失效，原问题无可行解。【解】将模型化为 cj24000 b XBCB X1 X2 X3 X4 X5 X302310024 X40-1-2010-10 X50-1-3001-15CjZj24000 X30101019 X40-1/3001 2/30 X241/3100 1/35CjZj2/30004/3最优解X=(0，5)；Z20【解】将模型化为Cj235600 b XB CB X1 X2 X3 X4 X5 X6 X50-1-2-3-410-2 X60-21-1301-3CjZj235600 X231/213/22-1/201 X60-5/20-5/211/21-4CjZj1/201/203/20 X23-11013/5-1/53/5-7/5 X35101-2/5-1/5-2/58/5CjZj0001/58/51/5 X121-10-13/51/5-3/57/5 X3501111/5-2/51/51/5CjZj0001/58/51/5 X12101-2/5-1/5-2/58/5 X2301111/5-2/51/51/5CjZj0001/58/51/5原问题有多重解：X(1)(7/5，0，1/5，)；最优解X(2)(8/5，1/5，0)；Z19/5如果第一张表X6出基，则有Cj235600 b XB CB X1 X2 X3 X4 X5 X6 X50 -1-2-3-410-2 X60 -21-1301-3 CjZj235600 X500-5/2-5/2-11/21-1/2-1/2 X121-1/21/2-3/20-1/23/2CjZj024901 X2301111/5-2/51/51/5 X12101-7/5-1/5-2/58/5CjZj00223/54/53/512某工厂利用原材料甲、乙、丙生产产品A、B、C，有关资料见表表产品材料消耗材料 产品材料消耗原材料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)-Z(j)010-200560X225103-10100MX33-301-210100100X60000-101400MC(j)-Z(j)-500-510X22211100200X50-301-210100X60000-101400C(j)-Z(j)-20-1-300(7)设产品D的产量为x7, 单件产品利润为c7，只有当时才有利于投产。则当单位产品D的利润超过4.4元时才有利于投产。13. 已知线性规划问题的最优单纯形表如下： 2 -7 1 0 0b2611110010031110-9-1-20 在下述每一种情况下，进行灵敏度分析并求出最优解。1 目标函数变为；2 约束条件右端项由(6,4)T变为(3,5)T；3 增加一个约束条件。解：1. x2的价值系数由-7变为3。 cj2 3 1 0 0 CB XB b 2 60 101 1 1 1 00 3 1 1 1610/3cj-zj0 1 -1 -2 02 8/33 10/31 0 2/3 2/3 -1/30 1 1/3 1/3 1/3cj-zj0 0 -4/3 -2 -1/3此时最优解为 2. 此时不影响解的最优性，只改变解的值及目标函数值 （3） 最优解不满足新增加的约束条件 最优解要发生改变, 将约束条件改写为,加入最优表中继续迭代cj2 -7 1 0 0 。 0CB XB b 2 60 100 -81 1 1 1 0 00 3 1 1 1 00 -1 -3 -1 0 1cj-zj0 -9 -1 -2 0 02 0 1 10/322/38/31 2/3 0 2/3 0 1/30 8/3 0 2/3 1 4/30 1/3 1 1/3 0 -1/3cj-zj0 -26/3 0 -5/3 0 -1/3故变化后的最优解为 14. 设有A1，A2，A3三个产地生产某种物资，其产量分别为7t、5t、7t，有B1，B2，B3，B4四个销地需要该种物资，销量分别为2t、3t、4t、6t，又知各产销地之间的单位运价表如下销地产地B1 B2 B3 B4A1A2A32 11 3 410 3 5 97 8 1 2（1）化为产销平衡问题，列出平衡问题的单位运价表。（2）用最小元素法给出初始方案。用位势法验证是否为最优方案，若不是，试进行一次调整。解:（1）单位运价表销地产地B1 B2 B3 B4 B5A1A2A32 11 3 4 010 3 5 9 07 8 1 2 0（2）初始方案及对应的检验数表初始方案销地产地B1 B2 B3 B4 B5产量A1A2A32 1 4 3 2 4 3 757销量2 3 4 6 4销地产地B1 B2 B3 B4 B5产量A1A2A313 08 -3 -5 7 12 2757销量2 3 4 6 4由表可知，检验数不都大于等于0，故非最优方案，一次调整可得：销地产地B1 B2 B3 B4 B5产量A1A2A32 3 2 3 2 4 3 757销量2 3 4 6 415某地区有两个粮库A1，A2，三个粮店B1，B2，B3。粮库可发运的粮食数量(吨)，粮店所需粮食数量（吨）及地区间单位运价cij (10元/吨)