管理运筹学教程习题解答(1.0版)doc.doc

管理运筹学教程习题参考答案第一章 线性规划1、解：设每天应生产A、B、C三种型号的产品分别为件。则线性规划模型为：2、解：设5种债劵的投资额分别为件。则线性规划模型为：3、（1）解：对原问题标准化，令，（2）解：对原问题标准化，令，（3）解：对原问题标准化，令4、（1）解：首先将线性规划模型标准化得：cj2-13000iXBbx1x2x3x4x5x6x46031110060x5101-120105x62011-2001-Z02-13000cj2-13000iXBbx1x2x3x4x5x6x4552.51.501-0.50x350.5-0.5100.50x630200011-Z-150.50.500-1.50cj2-13000iXBbx1x2x3x4x5x6x2110/35/3102/3-1/30x370/34/3011/31/30x630200011-Z-100/3-1/300-1/3-4/30最优解为x1 =0，x2 = 110/3 , x3 = 70/3。目标函数值： Z* = 100/3（2）解：首先将线性规划模型标准化得：cj-51-3-200iXBbx1x2x3x4x5x6x571234103.5x632212011.5-Z0-51-3-200cj-51-3-200iXBbx1x2x3x4x5x6x54-10221-1x21.5110.5100.5-Z-1.5-60-3.5-30-0.5最优解为x1 =0，x2 = 1.5, x3 = 0, x4=0。目标函数值： Z* = 1.55、(1)利用大M法。解:在上述问题中加入松弛变量和人工变量得：这里M是一个充分大的正数,取基变量为 x4 , x6 ，可得如下表cj23-5-M0-MiXBbx1x2x3x4x5x6x47111100x6102-510-11-Z023-5-M0-M由于x4 , x6为基变量，因此它们对应的检验数行的检验数应为0，经变换得初始单纯形表。cj23-5-M0-MiXBbx1x2x3x4x5x6x471111007x6102-510-115-Z17M2+3M3-4M-5+2M0-M0cj23-5-M0-MiXBbx1x2x3x4x5x6x4203.50.510.5-0.5x151-2.50.50-0.50.5-Z-10+2M08+3.5M-6+0.5M01+0.5M-1-1.5Mcj23-5-M0-MiXBbx1x2x3x4x5x6x24/7010.1428570.2857140.142857-0.14286x145/7100.8571430.714286-0.142860.142857-Z102/700-7.14286-2.28571-M-0.142860.142857-M最优解为x1 =45/7，x2 = 4/7, x3 = 0。目标函数值： Z* =102/7利用两阶段法。先在以上问题的约束条件中加入松弛变量、人工变量，给出第一阶段的线性规划问题：这里取基变量为 x4 , x6 ，可得如下表cj000-10-1iXBbx1x2x3x4x5x6x47111100x6102-510-11-Z0000-10-1由于x4 , x6为基变量，因此它们对应的检验数行的检验数应为0，经变换得初始单纯形表。cj000-10-1iXBbx1x2x3x4x5x6x471111007x6102-510-115-Z173-420-10cj000-10-1iXBbx1x2x3x4x5x6x4203.50.510.5-0.5x151-2.50.50-0.50.5-Z203.50.500.5-1.5cj000-10-1iXBbx1x2x3x4x5x6x24/7011/72/71/7-1/7x145/7100.8571430.714286-0.142860.142857-Z0000-10-1这里 x4、x6 是人工变量。第一阶段我们已求得 W = 0,因人工变量 x6 = x4 = 0，所以(45/7, 4/7, 0 ,0)T 是原问题的基本可行解。于是可以开始第二阶段的计算。将第一阶段的最终计算表中的人工变量列取消，并将目标函数系数换成原问题的目标函数系数，重新计算检验数行，可得如下第二阶段的初始单纯形表cj23-50iXBbx1x2x3x5x24/7011/71/7x145/7100.857143-0.14286-Z102/700-7.14286-0.14286所有检验数 sj 0，所以 x1 = 45/7，x2 = 4/7 , x3 = 0 是原线性规划问题的最优解。目标函数值： Z* = 102/7。(2)利用大M法。解:在线性规划中加入人工变量得：这里M是一个充分大的正数,取基变量为x5, x6, x7 ，可得如下表cj-4-100-M-M-MiXBbx1x2x3x4x5x6x7x533100100x6643-10010x741201001-Z0-4-100-M-M-M由于x5, x6, x7为基变量，因此它们对应的检验数行的检验数应为0，经变换得初始单纯形表。（红色为答案错误的）cj-4-100-M-M-MiXBbx1x2x3x4x5x6x7x5331001001x6643-100103/2x7412010014-Z13M-4+8M-1+6M-MM000cj-4-100-M-M-MiXBbx1x2x3x4x5x6x7x1111/3001/3003x6205/3-10-4/3106/5x7305/301-1/3019/5-Z4+5M01/3+10/3M-MM4/3-8/3M00cj-4-100-M-M-MiXBbx1x2x3x4x5x6x7x10.6100.201/15-0.203x21.201-0.60-0.80.60x7100111-111-Z3.6+M000.2+MM1.6-0.2-2M0cj-4-100-M-M-MiXBbx1x2x3x4x5x6x7x10.4100-0.20.40-0.23x21.80100.6-0.200.6x3100111-111-Z3.4000-0.21.4-M-M-0.2-M最优解为x1 =0.4，x2 = 1.8, x3 = 1。目标函数值： Z* = 3.4利用两阶段法。先在约束条件中加入人工变量，给出第一阶段的线性规划问题：取基变量为x5, x6, x7 ，可得如下表cj0000-1-1-1iXBbx1x2x3x4x5x6x7x533100100x6643-10010x741201001-w00000-1-1-1由于x5, x6, x7为基变量，因此它们对应的检验数行的检验数应为0，经变换得初始单纯形表。cj0000-1-1-1iXBbx1x2x3x4x5x6x7x5331001001x6643-100103/2x7412010014-w1386-11000cj0000-1-1-1iXBbx1x2x3x4x5x6x7x1111/3001/3003x6204/3-10-4/3103/2x7304/3011/3019/4-w5010/3-118/300cj0000-1-1-1iXBbx1x2x3x4x5x6x7x10.6100.200.6-0.203x21.201-0.60-0.80.60x7100111-111-w100110-20cj0000-1-1-1iXBbx1x2x3x4x5x6x7x10.4100-0.20.40-0.23x21.80100.6-0.200.6x3100111-111-w00000-1-1-1这里 x5, x6, x7是人工变量。第一阶段我们已求得 W = 0,因人工变量x5 x6 x7 = 0，所以(0.4,1.8 , 1 ,0)T 是原问题的基本可行解。于是可以开始第二阶段的计算。将第一阶段的最终计算表中的人工变量列取消，并将目标函数系数换成原问题的目标函数系数，重新计算检验数行，可得如下第二阶段的初始单纯形表cj-4-100iXBbx1x2x3x4x10.4100-0.2x21.80100.6x310011-Z3.4000-2最优解为x1 =0.4，x2 = 1.8, x3 = 1。目标函数值： Z* = 3.46、（1）解：将线性规划问题化为对偶问题（2）解：将线性规划问题化为对偶问题7、用对偶单纯形法求解线性规划问题。（1）解：将模型转化为cj-4-12-1800xBbx1x2x3x4x5x4-3-2-2-110x5-5-2-3-101-Z0-4-12-1800i2418cj-4-12-1800xBbx1x2x3x4x5x420101-1x12.511.50.50-0.5-Z100-6-160-2可得原问题最优解X*=（2.5，0，0）， Z*=10（2）解：将模型转化为进一步可以变为cj-40-6-2500xBby1y2y3y4y5y4-60-12-110y5-50-2-1-101-Z0-40-6-25004025cj-40-6-2500xBby1y2y3y4y5y4601-21-10y510-1-30-11-Z1500-15-560-250可得原问题最优解X*=（25，0）， Z*=15008、已知线性规划问题（1）求原问题和对偶问题的最优解；(2)在不改变最优基的条件下，确定的目标函数系数的变化范围；（3）在不改变最优基的条件下，确定右边常数项系数的变化范围。解：原问题的单纯形表cj41200iXBbx1x2x3x4x5x42831101/4x58611014/3-Z041200cj41200iXBbx1x2x3x4x5x11/413/81/81/802x56.50-5/41/4-3/4126-Z-10-0.51.5-0.50cj41200iXBbx1x2x3x4x5x3283110x56-2-20-11-Z-4-12-50-20（1） 可得原问题最优解X*=（0，0，2），最优值 Z*= 4对偶问题最优解（2，0），最优值 Z*= 4（2）如果系数的改变，使即 时，原最优方案不发生改变。如果系数的改变，使即 解得，这时原最优方案不发生改变。（3）如果改变，则 解得 即右边常数项系数在的范围内变化时并不影响最优方案。9、解：原问题的单纯形表cj-551300iXBbx1x2x3x4x5x420-1131020/3x59012410019-Z0-551300cj-551300iXBbx1x2x3x4x5x320/3-1/31/311/3020x570/346/32/30-10/3135-Z-260/3-2/32/30-13/30cj-551300iXBbx1x2x3x4x5x220-11310x510160-2-41-Z-10000-2-50可得原问题最优解X*=（0，20，0），最优值 Z*= 100(1) 如果改变，则cj-551300iXBbx1x2x3x4x5x230-11310x5-30160-2-41-Z-15000-2-50cj-551300iXBbx1x2x3x4x5x2-152310-51.5x315-8012-0.5-Z-120-1600-1-1cj-551300iXBbx1x2x3x4x5x43-4.6-0.201-0.3x391.20.4100.1-Z-117-20.6-0.200-1.3即第一个约束条件的右端的常数项由20变为30时，则最优方案调整为 X=(0,0,9)T,目标值为117。（2）如果改变，则cj-551300iXBbx1x2x3x4x5x220-11310x5-10160-2-41-Z-10000-2-50cj-551300iXBbx1x2x3x4x5x252310-51.5x35-8012-0.5-Z-90-1600-1-1即第二个约束条件的右端的常数项由90变为70时，则最优方案调整为 X=(0,5,5)T,目标值为90。(3)目标函数中的系数由13变为8，由于是非基变量，因此改变为8时，使这时原最优方案不发生改变。(4) 由于是非基变量，它对应的系数矩阵变化时，不会改变，它只影响单纯形表列，只是对检验数有影响，因此。这时原最优方案不发生改变。(5) 以x6为基变量，将上式反映到最终单纯形表中得到cj-5513000XBbx1x2x3x4x5x6x220-113100x510160-2-410x650235001-10000-2-500在上表中，x2、x5、x6为基变量，因此所对应的检验数应为0，因此经计算得下表。cj-5513000XBbx1x2x3x4x5x6x220-113100x510160-2-410x6-1050-4-301-10000-2-500利用对偶单纯形法计算得cj-5513000XBbx1x2x3x4x5x6x212.52.7510-1.2500.75x51513.500-2.51-0.5x32.5-1.25010.750-0.25-95-2.500-3.50-0.5增加约束后，最优方案调整为 X=(0,12.5,2.5)T,目标值为95。10、解：初始方案为：ABC日产量（供应量）甲矿100100200乙矿150100250日销量（需要量）100150200经过调整的最优方案为ABC日产量（供应量）甲矿50150200乙矿50200250日销量（需要量）100150200则运输量最少为509050801507020080=3500011、解：初始方案为：ABCD日产量（供应量）甲矿10060160乙矿8020100丙矿14080220日销量（需要量）80140120140经过调整的最优方案为ABCD日产量（供应量）甲矿12040160乙矿8020100丙矿14080220日销量（需要量）80140120140则运输量最少为2080140501201104011020908060=3280012、解：由于已知各面食加工厂制作单位面粉食品的利润及各面粉厂到各面食加工厂之间的单位运价，可得各面粉厂的面粉在不同面食加工厂制作单位面粉食品的利润，见下表 面食厂面粉厂ABC甲999乙853丙457由于要求的是利润最大化，再一点，该问题是产销不平衡问题，增加一个虚拟的面食厂D，他的需求量为10，各面粉厂到面食厂的运价为0。在伏格尔方法中从行差额和列差额中选出最大者，选择它所在的行或列中的最大元素进行分配运量。得初始方案为：ABCD面食厂需求量甲02020乙151530丙101020面食厂需求量15252010由于所求的是最大化，因此要求检验数全部小于等于零时为最优方案。经过计算知，上述方案为最优方案：ABCD面食厂需求量甲02020乙151530丙101020面食厂需求量15252010则最大利润为15806155105209100=42513、解：设为买第一种包装的袋数，为买第二种包装的袋数，则数学模型为14、解：设为第i辆平板车装类箱子的数量，。则箱数的约束为重量的约束为厚度的约束为特殊约束自然约束目标函数是使浪费的空间最小，也就是装的越多，空间浪费的越少。15、（1）解：求相应的线性规划（LP）得（LP）的最优解首先注意其中一个非整数变量的解，如，在松弛问题中的解，于是原问题增加两个约束条件，将两个约束分别并入原问题的松弛问题（LP）中，形成两个分支，即后继问题（LP1）和(LP2)，这并不影响原问题的可行域。解（LP1），得最优解为再解（LP2），得最优解为继续对（LP1）进行分解。对（LP1）增加两个约束条件，将两个约束分别并入（LP1）中，形成两个分支，即后继问题（LP11）和(LP12)，这并不影响（LP1）的可行域。解（LP11），得最优解为再解（LP12），无最优解。因此得原问题的最优解为。(2) 解：求相应的线性规划（LP）得（LP）的最优解首先注意其中一个非整数变量的解，如，在松弛问题中的解，于是原问题增加两个约束条件，将两个约束分别并入原问题的松弛问题（LP）中，形成两个分支，即后继问题（LP1）和(LP2)，这并不影响原问题的可行域。解（LP1），得最优解为再解（LP2），无最优解。继续对（LP1）进行分解。对（LP1）增加两个约束条件，将两个约束分别并入（LP1）中，形成两个分支，即后继问题（LP11）和(LP12)，这并不影响（LP1）的可行域。解（LP11），得最优解为再解（LP12），得最优解为。继续对（LP12）进行分解。对（LP12）增加两个约束条件，将两个约束分别并入（LP12）中，形成两个分支，即后继问题（LP121）和（LP122），这并不影响（LP12）的可行域。解（LP121），得最优解为再解（LP122），无最优解。继续对（LP121）进行分解。对（LP121）增加两个约束条件，将两个约束分别并入（LP121）中，形成两个分支，即后继问题（LP1211）和（LP1212）。解（LP1211），得最优解为。再解（LP1212），无最优解为。因此得原问题的最优解为。16、解：通过观察的方法找一个可行解，易得(x1 , x2 , x3 , x4)=(0 ,0 ,0，1)符合约束条件，计算出其目标函数值Z =4。对于极小化问题，当然希望z4，于是增加一个约束条件，后加的约束条件称为过滤条件。过滤条件为： 目标函数可以改写成：因为5，、4、3，2是递减的，变量(x2 ,x4 ,x3, x1 )也按下述顺序取值（0，0，0，0），（0，0，0，1），（0，0，1，0），（0，0，1，1）等. 点(x2 ,x4 ,x3, x1 )约束条件是否满足条件Z值（0，0，0，0）0不满足（0，0，0，1）2不满足（0，0，1，0）3不满足（0，0，1，1）5不满足（0，1，0，0）4满足（1，0，0，0）5不满足（0，1，0，1）6不满足（0，1，1，0）7不满足（1，0，0，1）7不满足（1，0，1，0）8不满足（1，1，0，0）9不满足（0，1，1，19不满足（1，0，1，110不满足（1，1，0，111不满足（1，1，1，012不满足（1，1，1，114不满足得最优解(x2 ,x4 ,x3, x1 )（0，1，0，0），最优值z4。（2）解：通过观察的方法找一个可行解，易得(x1 , x2 , x3)=(1 ,0 ,0)符合约束条件，计算出其目标函数值Z =2。对于极大化问题，当然希望z2，于是增加一个约束条件，后加的约束条件称为过滤条件。过滤条件为： 目标函数可以改写成：因为-1，1，2是递增的，变量(x3，x2 , x1)也按下述顺序取值（0，0，0），（0，0，1），（0，1，0），（0，1，1）等。 点(x3，x2 , x1)约束条件是否满足条件Z值（0，0，0）0不满足（0，0，1）2满足2（0，1，0）1不满足（0，1，1）3满足3改进过滤条件，用 代替过滤条件，再继续进行。点(x3，x2 , x1)约束条件是否满足条件Z值（1，0，0）-1不满足（1，0，1）1不满足（1，1，0）0不满足（1，1，1）2不满足至此，z值已不能再改进，即得到最优解。最优解为(x3，x2 , x1)（0，1，1）；最优值为z=3。17、有4个工人，要指派他们分别完成4项工作，每人做各项工作所消耗的时间如表2，问如何分配工作可使总的消耗时间为最少？表2 工作工人ABCD甲15182124乙19232218丙26171618丁19212317解：首先进行行、列变换，使每一行和每一列都出现0元素。在第一列减去15，第二列减去17，第三列减去16，第四列减去17，然后再从第二行中减去1。得首先进行行、列变换，使每一行和每一列都出现0元素。如上表中第一行减去7，第二行减去5，第三行减去4，第四行减去2，然后再从第四列中减去1。得01573550110014570进行试指派，寻找最优解。由有0元素最少的行开始，圈出一个0元素，用 表示，然后划去同行同列的其他0元素，这样依次进行，得157355111457由于独立的0元素个数少于矩阵的阶数，因此作最少的直线覆盖所有的0元素。在没有 的行打；对打的行上的所有0元素的列打号；再对打的列上有 的行上打 号。重复以上步骤，直到得不出新的打 号的行列为止。最后对没有打号的行画横线，将打有号的列画竖线。157355111457由于覆盖直线个数3少于矩阵阶数4，故进行变换，以增加0元素。在没有被直线覆盖的部分中找出最小元素3；然后对没有覆盖的行中各元素中减去这个最小元素3；被直线覆盖的列中各元素都加上这个最小元素3。这样在没有覆盖的元素中又增加了0元素。015100220110041240再进行试指派，寻找最优解。151022114124由于独立的0元素个数仍然少于矩阵的阶数，因此作最少的直线覆盖所有的0元素。151022111124004100110120051130再进行试指派，寻找最优解。410111251130100100000100001得到最优解的指派方案为：甲B，乙A，丙C，丁D；最少消耗时间为70。第二章 目标规划一、思考题1，答：因为在经营管理实际中，决策者不仅要考虑资源的最佳配置和有效利用，还要考虑到市场、竞争对手、替代品的政策法律环境等多方面的影响因素和指标要求，此时线性规划模型不能完全解决问题。2，答：一般目标规划是将多个目标函数写成一个由偏差变量构成的函数求最小值，并按多个目标的重要性，给定优先等级和权重，顺序求最小值。按决策者的意愿，对于事先给定的目标值，分为三种情况：（1） 当约束要求目标不超过目标值，目标函数求正偏差变量最小。（2） 当约束要求目标不低于目标值，目标函数求负偏差变量最小。（3） 当约束要求目标等于目标值，目标函数求正负偏差变量之和最小。3，答：（一）初始基变量的选择 首先选择所有的负偏差变量为初始基变量；如果负偏差变量数小于约束方程数，则增加选择不同约束条件的松弛变量；如果负偏差变量和松弛变量的总数还小于约束方程数时，则需要加入人工变量，此时引入的M将被视作最高优先级，即0级优先级：。 （二）满意解的判断 当所有非基变量的检验数大于等于零时，目标规划问题获得最优解。非基变量的检验数为：，由于，所以当非基变量检验数中的首项系数时，获得满意解。 （三）入基变量和出基变量的选择 入基变量的选择：选择检验数首项系数为负的非基变量入基，若有多个首项系数为负，则取其中检验数首项优先级最高系数最小的非基变量入基。如果首项优先级相同且系数相等，再比较第二个优先级的系数。若有两个及两个以上的非基变量检验数（的所有各项系数）都相等，这些非基变量中有决策变量时，则首先选择决策变量入基；若它们同时是决策变量或偏差变量，则可以选择其中下标最小的变量入基。 出基变量的选择：与单纯形法相同。4，答：序列解法不需要使用优先级系数，而是将单纯形法应用于不同目标层次的线性规划问题。 单纯形法适用于能给目标确定优先级的场合，序列解法适用于目标层次不需确定优先级的场合。5，答：第一个问题：看最优解是否唯一或是否为最后一个层次。如果是，则不再继续求解，已获得满意解；如果不是，则需要继续下一层次目标的求解。 第二个问题：如果z*0，则在加入第二层次目标约束后从约束条件中删去第一层次目标函数含有的偏差变量；如果z*0，则加入第二层次目标约束后，将第一层次的目标函数（令其等于z*）作为附加约束加入到第二层次约束条件中。 6， 判断以下各种说法的正确性1） 正偏差变量大于等于零，负偏差变量小于等于零。答：错，都大于等于零。2） 目标约束一定是等式约束。 答：对。3） 一对正负偏差变量至少一个大于零。 答：错。4） 一对正负偏差变量至少一个等于零。 答：对。5） 要求至少达到目标值的目标函数是。 答：对。6） 要求不超过目标值的目标函数是。 答：错。要求正偏差变量最小。二、选择题7，答：正确的是C、E。8. 答：应该选择D。9答：应该选择A。三、计算题10， x1x2120图1 图解法第1题（1） 解：对于，桔黄色内的部分满足要求，对于，蓝色内的部分满足要求，所以满意解是2，0，1，其它偏差变量都等于零。x22Cx101图2 图解法第2题（2） 解：对于，桔黄色内的部分满足要求，对于，蓝色内的部分满足要求，由图2知无法满足，所以满意解在点c取到，满意解是0，3，5，4，1，其它偏差变量都等于零。11，（1）解：初始基变量为三个负偏差变量，得到初始单纯形表如表1。表1 题2(1)的初始单纯形表00002001603040811422100-1000100-1000100-1203040-8-4010000-1-2000201非基变量的检验数分别为和，因此应当入基，用最小比值法确定应当出基。换基后，通过计算求得新的基本可行解，见表2。表2 题2(1)的第一次迭代单纯形表000020002010201001/23/23/21/8-1/8-1/8-1/81/81/80100-1000100-14020/340/3001000000-3/21/8-1/80201可得，入基，出基。换基后，通过计算求得新的基本可行解，见表3。表3 题2(1)的第二次迭代单纯形表0000200050/320/3101000101/6-1/120-1/61/120-1/32/3-11/3-2/3100100-10010000000001101此时所有变量的检验数的首项系数都已经大于等于零，因此获得了满意解如下：50/3，20/3，=10，其它偏差变量都等于零。（3） 解：初始基变量为四个负偏差变量，得到初始单纯