运筹学清华大学第三版习题集.doc

求解下述LP问题解：依据单纯形理论，有以下计算：（1）令为基变量、为非基变量，可得， 解得，代入目标函数，得。此时得到的解为，。由、可知，取正值可使z增大。若令取正值且仍为0，由，可得，这说明最大可以达到3，此时将变为0，成为非变量。（2）令为基变量、为非基变量，可得，解得，目标函数变为。此时得到的解为，。由可知，取正值可使z增大。若令取正值且仍为0，由，可得，这说明最大可以达到2，此时将变为0，成为非基本变量。（3）令为基变量、为非基变量，可得解，。此时，可知此时应让取正值，即进入基变量。经过类似检查，可知应让变成非基变量。（4）令为基变量，为非基变量，可得解，。此时，达到最优点。上述过程可以编制表格计算，这就是单纯形法。例1.9 分别用图解法、单纯形法求解例1.8的LP问题，并指出单纯形法迭代的每一步相当于图形上的哪个顶点。解：原问题可等价转化为：图解如下：可知，目标函数在B(4, 2)处取得最大值，故原问题的最优解为，目标函数最大值为。用单纯形法求解原问题时，单纯形表如下：230000812100401640010012040013230000210101/220164001043301001/420003/42210101/2080041243301001/41200201/4241001/40040021/2132011/21/80003/21/80原问题的最优解为，目标函数最大值为。单纯形法的寻找路径为： 与图解法对照，寻找相当于O(0, 0) D(0, 3) C(2, 3) B(4, 2)。例1： 用单纯形法求解下述LP问题。， 解：首先将原问题转化为线性规划的标准型，引入松弛变量、，可得：构造单纯形表，计算如下：340004021104003013011034000305/301-1/3184101/3101/3305/300-4/3318103/5-1/54401-1/52/500-1-1由此可得，最优解为，目标函数值为。例2：用单纯形法求解下述LP问题。解：引入松弛变量、，化为标准形式：构造单纯形表，计算如下：2.510001535105010520122.510009019/513/545/192.5212/501/550001/2145/19015/193/192.520/19102/195/190001/2由单纯形表，可得两个最优解、，所以两点之间的所有解都是最优解，即最优解集合为：，其中。例2b 用单纯形法求解下述线性规划解：引入松弛变量、和，列单纯形表计算如下：1230000821810010413100101/308114001123000024/5-14/517/501-4/5032/51/10-3/10101/1004048/57/5-11/5002/5148/77/10-11/1000-3/1000160-528120141-3100100402-140-1101-70-1002600-71-1/25/211010-110-1/23/22201-70-1/21/20000-1/2-1/2故，原问题的最优解为， ，其中。例3：用单纯形法求解下述LP问题。解：构造单纯形表计算如下：340004021104003013011034000305/3011/3184101/3101/3305/3004/3318103/51/544011/52/50011故，最优解为，目标函数值为。例4：某个求解最大值的线性规划问题用单纯形法计算时得到下表：f2c10e02-1501103a30041bd0030其中，a, b, c, d, e, f是未知数，原问题中要求各变量为非负。问a, b, c, d, e, f满足什么条件时，有下面各解成立？（1）不是基可行解；（2）是唯一最优解；（3）有无穷多最优解；（4）是退化的基本可行解；（5）无界解；（6）是可行解但非最优解，只有可以进基且出基变量必为第3个基变量。解：（1）f=0, b0, d=0, b=0, d=0, b=0, d=0（4）f=0, b=0, d=0, d0, c=0, b0, d3/a例1.10 用大M法求解下述LP问题解：先将原问题化为标准型，引入松弛变量，得：再引入人工变量、，得：构造单纯形表计算如下：2350MMM71110107M1025110153M+23-4M2M-5-M00M207/21/21/211/24/72515/21/21/201/207M/2+8M/2-6M/2+10-3M/2-134/7011/71/72/7-1/7245/7106/7-1/75/71/700-50/7-1/7-M-16/7-M+1/7由此得，原问题的最优解为，目标函数最优值为102/7。例1.11 用两阶段法求解下述LP问题解：先将原问题化为标准型，引入松弛变量，得：再引入人工变量、，得第一阶段的模型为：构造单纯形表，计算如下：00001117111010711025110153421001207/21/21/211/24/70515/21/21/201/207/21/21/203/234/7011/71/72/7-1/7245/7106/7-1/75/71/7000011由此可得第一阶段的最优解，转入第二阶段，单纯形表如下：235034/7011/71/7245/7106/7-1/700-50/7-1/7由此得，原问题的最优解为，目标函数最优值为102/7。例5：求解下述LP问题 解：用大M法求解。将原问题化为标准型，可得：在第三个等式约束中引入一个人工变量，可得：用单纯形表求解，可得：101512000M0953110009/501556150100-M521100-115/22M+10M+15M+1200-M0109/513/51/51/50009024091611003/2M7/50-1/53/5-2/50-117/309-M/53M/5+10-2M/5-20-M0103/2139/8003/16-1/8000123/209/1611/161/1600-M1/20-43/800-7/16-3/80-11027/8-43M/800-21/8-7M/16-5/8-3M/8-M0所有变量的检验数均为负数或零，单纯形表计算完毕，但人工变量仍在基变量中，故原问题无可行解。例6：求解下述LP问题解：用两阶段法求解。先将原问题化为标准型，可得： 引入人工变量，可得第一阶段的问题为：构造单纯形表，计算如下：0000001111611110010061220101001010021001001013111100016103/2101/2101/2412201010010200011/2001/2001/2105/2111/2003/21340013/21/213/21/23/4022010100100111001/21/201/21/240013/21/205/23/203/41001/43/81/81/43/81/807/20011/21/41/41/21/41/407/40101/41/83/81/41/83/8000000111故，第一阶段的最优解为第二阶段的单纯形表如下：21200003/41001/43/81/807/20011/21/41/407/40101/41/83/80005/43/89/8非基变量的检验数为正，但其系数向量为负，故原问题为无界解。例7：已知下述线性规划的最优基为，求其最优单纯形表。解：由，可知：故由单纯形表的行变换过程可知：原问题的最优单纯形表为：23000241001/40040021/2132011/21/80003/21/80例8：已知某线性规划的最优单纯形表为：23000241001/40040021/2132011/21/80003/21/80其中，为松弛变量，求该线性规划的初始单纯形表。解：由为松弛变量，可知它们在约束条件中的系数矩阵为单位矩阵，故在最优单纯形表中，它们的系数矩阵为，即：，可得由：可知最初单纯形表为：230000812100016400100120400123000例2.3 已知线性规划的最优解为，试利用互补松弛定理，求对偶问题的最优解。解：原问题的对偶问题为：將代入原问题的约束条件，可得： （1）又由 （2）将结论（1）和（2）结合起来，可解得。例2.3 已知线性规划问题其对偶问题的最优解为、，试用对偶理论求解原问题的最优解。解：原问题的对偶问题为：将对偶问题的最优解代入约束条件，可得： （1）又由 （2）将结论（1）和（2）结合起来，可得： ，解得 即原问题的最优解为。例2.5用对偶单纯形法求解解：先将原问题改写为：建立单纯形表计算如下：2340003121100421301234000105/21/211/22211/23/201/20410132/5011/52/51/5211/5107/51/52/5009/58/51/5故，原问题的最优解为，。例2.6 有线性规划如下：先用单纯形法求出最优解，再分析以下各种条件下，最优解分别有什么变化：（1）约束条件的右端常数由20变为30；（2）约束条件的右端常数由90变为85；（3）目标函数中的系数由13变为8；（4）的系数列向量由-1, 12T变为0, 5T；（5）和的系数列向量由-1, 12T 、1, 4T变为0, 5T 、2, 1T；（6）增加一个约束条件；（7）将约束条件改变为。解：分别在约束条件和中引入松弛变量和，列单纯形表计算如下：5513000201131020/3090124100195513001330/31/31/311/3020070/346/32/3010/31352/32/3013/305201131001016024100250由此可得，原问题的最优解为，。由单纯形表可知，原问题中。（1）约束条件右端常数此时为，由可知，单纯形表应变为：5513005301131003016024100250515231053/2131580121/21600110323/51/5013/101396/52/5101/10103/51/50013/10由此可得，最优解变为，。（2）约束条件右端常数此时为，由可知，最优基不变，最优解为，。（3）若变为8，则的检验数变为故最优解不变。（4）在原最优解中为非基变量，若的系数列变为，由可知，检验数由0变为5，故最优解不变。（5）在原最优解中为基变量，若和的系数列变为，则在约束中引入人工变量，单纯形表变为：551300MM2002310120/301057241055+2M13+3MM001320/302/311/301/3070/35-17/30-10/312/3-5-11/30-13/30-M-13/3故，最优解为，。（6）若引入一个约束，单纯形表将增加一行。在约束中引入松弛变量，单纯形表变为：551300052011310001016024100502350015201131000101602410010504301002500525/211/4105/403/401527/2005/211/205/25/4013/401/45/2007/201/2由此可得，最优解为，。（7）若约束条件变为，即、的系数分别变为、，b列变为，则由于基变量的系数发生变化，故在约束条件中引入人工变量，单纯形表变为：551300M-M20-11310120/30201412410-5-M5+M13+3MM001320/3-1/31/311/301/3200100/340/35/30-10/312/320-2/32/30-13/30-M-13/3130-3011-1/51/5520810-23/52/5-600-3-2/5-M23/5故，最优解为，。例2.7 试分析当参数变化时，的变化，其中是下述线性规划的最优目标函数值。 解：引入松弛变量、和，令，列单纯形表计算，可得：35000020011/31/3560101/20321001/31/30003/21将代入，可得：3+2t5-t000020011/31/35-t60101/203+2t21001/31/3000-3/2+7t/6-1-2t/3由，可知当参数t从0开始增大到9/7，即时，检验数都保持为非正，故此时最优解保持为，。当参数t开始超过9/7，即时，检验数，但其他检验数仍为非正，此时选择为换入变量，用单纯形表迭代计算可得：3+2t5-t000060031-15-t3013/201/23+2t410100009/2-7t/20-5/2+t/2由，可知当参数时，最优解为，。当参数t开始超过5，即时，检验数，但其他检验数仍为非正，此时选择为换入变量，用单纯形表迭代计算可得：3+2t5-t000012020100602-3013+2t41010005-t-3-2t00由，可知当时，最优解为，。综述所述，可知：例 某个求最大值的线性规划问题的最优单纯形表如下，其中、为松弛变量。20113141101003031（1）写出该问题的最优解；（2）当为何值时，其对偶问题无解？解：（1）最优解为。（2）由最优单纯形表的检验数，可得方程组：，可得。若其对偶问题无解，则原问题为无解或无界解。当变化时，原最优单纯形表中只有检验数将变化，故总是原问题的可行解。因此，要使对偶问题无解，原问题必为无界解。由原最优单纯形表可知，的最终列向量为负，故当，即时，原问题有无界解，其对偶问题无解。例1 已知线性规划的最优单纯形表为250101/21/21310001030011/23/200012（1）写出最优基矩阵及其逆矩阵（2）写出其对偶问题；（3）给出对偶问题的最优解；解：（1）由最优单纯形表，可知，（2）原问题的对偶问题为（3）由原问题变量与对偶问题变量之间的对应关系，以及对偶理论，可知：，即对偶问题的最优解为。例2 已知线性规划的最优单纯形表为6212001284/31/311/300625011102040其中，、分别为第1、2个约束的松弛变量。（1）求出最优基不变的变化范围；（2）求出最优解不变的变化范围；（3）在原问题中增加约束条件，求最优解。解：由原问题的最优单纯形表，可知。（1）记，则由可知，要使最优基不变，只需，即。（2）要使最优解不变，只需保证所有检验数仍保持非正，即，可得，即。（3）在新约束条件中引入松弛变量，在原最优单纯形表中增加一行，可得：62120001284/31/311/300062501100121220011284/31/311/30006250110045/34/30-2/30110204001261/311001/2012-1/23001-3/2065/2-2010-3/20-10000-6故，最优解变为，。例1. 用表上作业法求解下述运输问题。甲乙丙丁产量A1067124B1610599C5410104销量5246解：这是一个产销平衡问题，可用表上作业法求解。用最小元素法求得初始解：甲乙丙丁产量A314B459C224销量5246用位势法计算u和v：甲乙丙丁uiA(10)(12)0B(5)(9)-3C(5)(4)-5vj109812计算非基本变量的检验数：甲乙丙丁uiA-3(6)-1(7)0B9(16)4(10)-3C7(10)3(10)-5vj109812以(A乙)作为调入格，用闭回路调整法计算(A乙)的新运量：甲乙丙丁产量A1214B459C44销量5246用位势法计算非基变量的检验数：甲乙丙丁uiA(10)(6)-1(7)(12)0B9(16)7(10)(5)(9)-3C(5)3(4)7(10)3(10)-5vj106812以(A丙)作为调入格，用闭回路调整法计算(A丙)的新运量：甲乙丙丁产量A1214B369C44销量5246用位势法计算非基变量的检验数：甲乙丙丁uiA1(12)0B8(16)6(10)-2C3(4)8(10)4(10)-5vj106711所有非基变量检验均为正数，故已得到最优解，运输成本最小值为118.例2. 用表上作业法求解下述运输问题。甲乙丙丁产量A1067124B1610599C5410104销量5246解：用Vogel法求出初始解，如下：甲乙丙丁产量A1214B369C44销量5246用位势法计算u和v：甲乙丙丁uiA(10)(6)(7)0B(5)(9)-2C(5)-5vj106711非基变量检验数为：甲乙丙丁uiA1(12)0B8(16)6(10)-2C3(4)8(10)4(10)-5vj106711所有非基变量检验均为正数，故已得到最优解，运输成本最小值为118.例3. 用表上作业法求解下述运输问题。甲乙丙丁产量A37645B24322C43853销量3322解：先用Vogel法求得初始解：甲乙丙丁产量A325B202C033销量3322用位势法计算u和v：甲乙丙丁uiA340B32-2C431vj3254非基变量检验数为：甲乙丙丁uiA5(7)1(6)0B1(2)4(4)-2C2(8)0(5)1vj3254所有检验数均为正数或零，故已得到最优解，最小运输成本为32。因为非基变量检验数中有0，故原问题有无穷多最优解。例4. 已知某运输问题的产销平衡表、单位运价表及最优调运方案如下：产销平衡表及最优调运方案B1B2B3B4产量A151015A20101525A355销量5151510单位运价表B1B2B3B4A11012011A2127920A32141618试回答：（1）从A2B2的运价c22在什么范围变化时，上述最优调运方案不变？（2）从A2B4的单位运价c24变为何值时，有无穷多最优调运方案？除表中所示最优方案之外，再写出两个。解：（1）设c22未知，用位势法计算ui和vj：B1B2B3B4uiA1(1)(11)0A2(12)(c22)(9)c22-1A3(2)c22-11vj13- c22110- c2211计算非基变量的检验数，可得：B1B2B3B4uiA1c22- 3(10)c22 +10(20)0A210- c22(20)c22-1A324-c22(14)17(16)18- c22(18)c22-11vj13- c22110- c2210要使原最优方案保持最优，只需所有非基变量的检验数为非负，故：，解得。（2）设c24为未知，用位势法计算ui和vj可得：B1B2B3B4uiA1(1)(11)0A2(12)(7)(9)6A3(2)-4vj61311计算非基变量的检验数可得：B1B2B3B4uiA14(10)17(20)0A2c24-17 (c24)6A317(14)17(16)11(18)-4vj61311要使原问题有无穷多最优解，需要至少有一个非基变量的检验数为0，故必有c24=17。以（A2，B4）作为调入格，用闭回路调整可得另一个最优解：B1B2B3B4产量A11515A200151025A355销量5151510至此，已得到两个最优的基解，两者的凸组合都是最优解，即：B1B2B3B4产量A11515A201525A355销量5151510其中，分别令取两个不同的值即可得到两个不同最优解。例4.4 用单纯形法求解例4.2的问题，即解：在第一个约束中引入松弛变量，构造单纯形表计算如下：0000001121111001111101211556810115.61122-8-101063/211/21/24053/2111/21/210/3051/211/21/2106355116/31113551031221/21/260211331/21/240414/34/31/61/6240215/35/31/31/31111011111104226611010/311/31/31/31/3010/312/32/31/31/31111由单纯形表，可知有两个最优顶点、，故原问题的最优解为，其中。例1. 考虑下述规划问题：其中，。模型的约束约束条件为： 或者，或者 下列各不等式至少有一个成立： 或5或10； ，试建立此问题的整数线性规划模型。解：整数线性规划模型为：例2. 用分枝定界法求解解：用分枝定界法求解原问题的过程如下：例3：用割平面法求解解：引入松弛变量，用单纯形法求解原问题的松弛问题，可得110006211030204501511001311/21/2060803218/301/21/2015/3105/61/618/3012/31/3001/61/6松弛问题的最优解为。的解为非整数，我们以它所在行构造切割方程。由最优单纯形表，可知：即：，可得切割方程，化简得。将切割方程加入松弛问题，代入单纯形表可得：1100015/3105/61/6018/3012/31/300-200-1-1100-1/6-1/6010100-15/6140101-2/3020011-10000-1/6得到最优解为，是整数解，故原问题的最优解为、，最优值为。例. 用Fibonacci法求解在上的极小点，要求最终区间长度不超过的0.08倍。解：求解，得，取。（1），由知：下一步应取，。（2），由知：下一步应取，。（3），由知：下一步应取，（3），由知：下一步应取，。（4），由可知，应取作为近似极小点，近似极小值为1.751。原问题的极小点所属区间为。例. 试以为初始点，用最速下降法求的极小点。解：由可得：，由正定，可知为凸函数，存在唯一极大点。用梯度法列表计算如下：步骤0012134例. 试以为初始点，用变尺度法求的极小点。解：由可得：，由正定，可知为凸函数，存在唯一极大点。用变尺度法计算如下：步骤0010.52例. 用K-T条件解非线性规划解：原问题写为标准形式为：， 故分别向两个约束条件引入广义Lagrange乘子和，则K-T条件可写为：先不考虑，和的取值有4种情况：（1）且，则K-T条件无解。（2）且，解得、，不符合，故不是K-T点。（3）且，解得、，不符合，故不是K-T点。（4）且，解得，满足所有K-T条件，故是K-T点。由于原规划中目标函数为凸函数、可行域也为凸集，故有唯一极小点，即所求得的K-T点。例. 求解二次规划解：可知，原问题为凸规划，存在唯一的极小点，也是最小点。令，则，分别向三个约束引入广义Lagrange乘子，则KT条件可写为：向引入松弛变量，则上述条件可化为：先不考虑最后一行约束，为求解前三个约束，分别在前两个约束引入人工变量和，可得：取初始解为，其它变量为0，用单纯形法求解（注意求解时应满足），可得：，故原二次规划的最优解为：、，。例. 求解二次规划解：可知，原问题为凸规划，存在唯一的极小点，也是最小点。令，将原问题转化为标准形式：各函数的梯度分别为：，分别向四个约束引入广义Lagrange乘子，则KT条件可写为：分别向和引入松弛变量和，则KT条件化为：先不考虑最后一行约束，为求解前四个约束，分别在前两个约束引入人工变量和，可得：取初始解为，其它变量为0，用单纯形法求解（注意求解时应满足），可得：，故原问题的最优解为：，。例. 用可行方向法求解：解：先化为非线性规划的标准形式：则，。取初始可行点。（1），故，而，所以不是近似极小点。取搜索方向。求解：，其中。解得：，故。（2），故。求解线性规划：，即：解得：。求解：其中，。解得：，故。（3）由此继续迭代，可得最优解为：，。例. 用外点法求解：解：构造罚函数：由此可得： 从外部点开始考虑，此时有且，故： 由，可得：当时，故原问题的最优解为。例. 试用内点法求解解：采用对数形式构造障碍项，