《5014518632第二章线性规划习题附答案》由会员分享，可在线阅读，更多相关《5014518632第二章线性规划习题附答案（24页珍藏版）》请在金锄头文库上搜索。
1、习题2-1 判断下列说法是否正确：（1） 任何线性规划问题存在并具有惟一的对偶问题；P（2） 对偶问题的对偶问题一定是原问题；P（3） 根据对偶问题的性质，当原问题为无界解时，其对偶问题无可行解，反之，当对偶问题无可行解时，其原问题具有无界解；O（4） 若线性规划的原问题有无穷多最优解，则其对偶问题也一定具有无穷多最优解；O（5） 若线性规划问题中的bi，cj值同时发生变化，反映到最终单纯形表中，不会出现原问题与对偶问题均为非可行解的情况；O（6） 应用对偶单纯形法计算时，若单纯形表中某一基变量xi0，说明在最优生产计划中第i种资源已经完全耗尽；若yi=0，说明在最优生产计划中的第i种资源一定
2、有剩余。O2-2将下述线性规划问题化成标准形式。解：(1)令，增加松弛变量，剩余变量，则该问题的标准形式如下所示： (2)令，增加松弛变量，则该问题的标准形式如下所示：2-3分别用图解法和单纯形法求解下述线性规划问题，并对照指出单纯形表中的各基可行解对应图解法中可行域的哪一顶点。解：(1)图解法 最优点为B点，最优解为x1=1,x2=3/2，最优值为35/2。 单纯形表计算过程：j初始单纯形表（对应O点）zx1x2x3x4RHSz1-10-5000x30341099/3x40520188/5k第一次迭代（对应A点）zx1x2x3x4RHSz10-10216x30014/51-3/521/521
3、/5/14/5x11012/501/58/58/5/4/5l第二次迭代（对应B点，即最优解）zx1x2x3x4RHSz1005/1425/1435/2x25015/14-3/143/2x11010-1/72/71(2)图解法最优点为B点，最优解为x1=15/4,x2=3/4，最优值为33/4。 单纯形表计算过程：j初始单纯形表（对应O点）zx1x2x3x4RHSz1-2-1000x3035101515/3x4062012424/6k第一次迭代（对应A点）zx1x2x3x4RHSz10-1/301/38x30041-1/233/4x1211/301/644/1/3l第二次迭代（对应B点，即最优解
4、）zx1x2x3x4RHSz1001/127/2433/4x21011/4-1/83/4x1210-1/125/2415/42-4已知线性规划问题，写出其对偶问题：（1） (2)解：(1)原问题的对偶问题为：(2)原问题的对偶问题为：2-5运用对偶理论求解以下各问题：（1）已知线性规划问题：其最优解为（a）求k的值；（b）写出并求出其对偶问题的最优解。解：原问题的对偶问题为：设该对偶问题的三个人工变量为，由于原问题的最优解中的，则根据互补松弛性，所增加的人工变量，则：，。另外，原问题的最优值，也为对偶问题的最优值，即：。结合上述三式可得：（2）已知线性规划问题：其对偶问题的最优解为， 。试根据
5、对偶理论求出原问题的最优解。解：首先写出原问题的对偶问题如下：由于该对偶问题的最优解为，代入对偶问题的约束条件中可得，即对偶问题中的松弛变量。则根据互补松弛性可知，原问题中的决策变量必为0。将=0代入原问题中的约束条件，可得：。又因为均不为0，则同样根据互补松弛性可知，。则有：。求解该方程组可得：。（3）已知线性规划问题:试根据对偶问题性质证明上述线性规划问题目标函数值无界。解：首先写出原问题的对偶问题如下：由于该对偶问题中前两个约束条件所确定的可行域为空集，可知该对偶问题无解。则根据对偶性质可知，原问题无解可无界。另外，必为原问题的解之一，则可证原问题无界。2-6已知某求极大值线性规划问题用
6、单纯形法求解时的初始单纯形表及最终单纯形表如表2-44所示，求表中各括弧内未知数的值。表2-44 初始单纯形表及最终单纯形表zx1x2x3x4x5x6RHSz1-3-2-20000x40111100（b）x50(a)1201015x602(c)100120：zx1x2x3x4x5x6RHSz10（k）（g）05/4（j）95/4x4000（d）(l)-1/4-1/45/4x1310（e）03/4（i）25/4x2201（f）0（h）1/25/2解：由初始单纯形表中的基变量为可知，为最终单纯形表中所对应的消耗系数矩阵，即：则有：，可求得：。另外：，可求得。再由检验数计算公式可求得；而基变量的检验
7、数必为零，所以。即。2-7用对偶单纯形法求解下列线性规划问题。解：(1) 令z，=- z引进松弛变量x4，x50，标准化列出初始单纯形表z，x1x2x3x4x5RHSz，141218000x40-10-310-3x500-2-201-5-12/-2-18/-2选取x2进基。即选取a22=-2为主元，进行旋转运算，得到以下单纯形表。z，x1x2x3x4x5RHSz，140606-30x40-10-310-3x2-120110-1/25/2-4/-1-6/-3选取x4出基，a13=-3为主元进行旋转运算。z，x1x2x3x4x5RHSz，120026-36x3-181/301-1/301x2-12
8、-1/3101/3-1/23/2当前基既是原始可行基，又是对偶可行基，因而是最优基。最优解为x1=0，x2=3/2，x3=1，max z，=-36，即min z=36(2) 令z，=- z引进松弛变量x4，x50，标准化 列出初始单纯形表z，x1x2x3x4x5RHSz，1523000x40-3-1-210-4x50-6-3-501-10-2/-3-3/-5选取x3进基。即选取a23=-5为主元，进行旋转运算，得到以下单纯形表。z，x1x2x3x4x5RHSz，17/51/5003/5-6x40-3/51/501-2/50x3-36/53/510-1/52当前基既是原始可行基，又是对偶可行基，
9、因而是最优基。最优解为x1=0，x2=0，x3=2，max z，=-6，即min z=6 2-8已知2-45表为求解某线性规划问题的最终单纯形表，表中x4 , x5为松弛变量，问题的约束为形式。表2-45 最终单纯形表zx1x2x3x4x5RHSz104042X301/211/205/2X11-1/20-1/61/35/2（1）写出原线性规划问题；（2）写出原问题的对偶问题；（3）直接由原问题的最终单纯形表写出对偶问题的最优解。解：（1）由于x4 , x5为松弛变量，则从表2-45可知，。设原问题模型为： 则由初始单纯形表和最终单纯形表之间的关系可得：，则可得到，。，则可得，。另外，由最终单纯
10、形表中检验数的计算公式可知，则可得，。综上，原线性规划模型为：（2）该模型的对偶问题为：（3）由原问题的最终单纯形表可以得出，单纯形表中的检验数行是对偶问题决策变量的值。其中，对应对偶问题松弛变量的值，对应对偶问题决策变量的值。则对偶问题的最优解为：，。2-9已知线性规划问题：先用单纯形法求出最优解，再分析在下列条件单独变化的情况下最优解的变化。（1）目标函数变为（2）约束右端项由变为;（3）增添一个新的约束条件。解：首先用单纯形法得到原问题的最优单纯形表。 zx1x2x3x4x5RHSz10312012x12111106x500311110且可得到，最终单纯形表中。（1）由于x2在最优单纯形表中是非基变量，因此只影响它本身的检验数。计算：得到时问题的最优解不变。但由于由-1变为3，此时必然造成检验数的符号发生变化，相应的单纯形表如下：zx1x2x3x4x5RHSz10-112012x12111106x500311110以为主元，对该单纯形表进一步迭代可得：zx1x2x3x4x5RHSz1004/37/31/346/3x12102/32/3-1/38/3x23011/31/31/310/3此
