管理运筹学课后答案.doc

PAGE 1 2.2 将下列线性规划模型化为标准形式并列出初始单纯形表。 （1） 解：（1）令，则得到标准型为（其中M为一个任意大的正数） 初始单纯形表如表2-1所示： 表2-1 cj -2 2 4 -4 0 0 -M -M ? CB XB b x2 x4 x5 x6 x7 0 x4 19 3 2 2 -2 1 0 0 0 19/3 -M x6 14 [ 4 ] 3 4 -4 0 -1 1 0 14/4 -M x7 26 5 2 4 -4 0 0 0 1 26/5 -z -2+9M 2+5M 4+8M -4-8M 0 -M 0 0 2.3 用单纯形法求解下列线性规划问题。 （1） （2） 解：（1）最优解为。 最优解为。 2.4 分别用大M法和两阶段法求解下列线性规划问题。 （1） （2） 解：（1）最优解为。 （2）最优解为。 2.6 已知线性规划问题 其对偶问题最优解为。试用对偶理论找出原问题最优解。 解：先写出它的对偶问题 将代入约束条件可知，第2、3、4个约束为严格不等式，因此，由互补松弛性得。又因为，所以原问题的两个约束条件应取等式，因此有 ? 故原问题最优解为。 2.12 现有线性规划问题 ①② ① ② 先用单纯形法求出最优解，然后分析在下列各种条件下，最优解分别有什么变化？ （1）约束条件①的右端项系数由20变为30； （2）约束条件②的右端项系数由90变为70； （3）目标函数中的系数由13变为8； （4）的系数列向量由变为； （5）将原约束条件②改变为； （6）增加一个约束条件。 解：在上述LP问题的第①、②个约束条件中分别加入松弛变量x4,x5得 列出此问题的初始单纯形表并进行迭代运算，过程如表2-11所示。 由表2-11中的计算结果可知，LP问题的最优解X*=(0,20,0,0,10)T，z*=5*20=100。 （1）约束条件①的右端项系数由20变为30，则有 列出单纯形表，并利用对偶单纯形法求解，过程如表2-12所示。 表2-11 cj -5 5 13 0 0 θi CB XB b x1 x2 x3 x4 x5 0 x4 20 -1 1 [ 3 ] 1 0 20/3 0 x5 90 12 4 10 0 1 9 cj-zj -5 5 13 0 0 13 x3 20/3 -1/3 [ 1/3 ] 1 1/3 0 20 0 x5 70/3 46/3 2/3 0 -10/3 1 35 cj-zj -2/3 2/3 0 -13/3 0 5 x2 20 -1 1 3 1 0 0 x5 10 16 0 -2 -4 1 cj-zj 0 0 -2 -5 0 表2-12 cj -5 5 13 0 0 CB XB b x1 x2 x3 x4 x5 5 x2 30 -1 1 3 1 0 0 X5 -30 16 0 [ -2 ] -4 1 cj-zj 0 0 -2 -5 0 5 x2 -15 23 1 0 [ -5 ] 3/2 13 x3 15 -8 0 1 2 -1/2 cj-zj -16 0 0 -1 -1 0 x4 3 -23/5 -1/5 0 1 -3/10 13 x3 9 6/5 2/5 1 0 1/10 cj-zj -103/5 -1/5 0 0 -13/10 由表2-12中计算结果可知，LP问题的最优解变为。 （2）约束条件②的右端常数由90变为70，则有 列出单纯形表，并利用对偶单纯形法求解，结果如表2-13所示。 表2-13 cj -5 5 13 0 0 CB XB b x1 x2 x3 x4 x5 5 x2 20 -1 1 3 1 0 0 X5 -10 16 0 [ -2 ] -4 1 cj-zj 0 0 -2 -5 0 5 x2 5 23 1 0 -5 3/2 13 x3 5 -8 0 1 2 -1/2 cj-zj -16 0 0 -1 -1 由表2-13结果知，LP问题的最优解变为。 （3）目标函数中x3的系数由13变为8，由于x3是非基变量，其检验数变为 所以LP问题的最优解不变。 （4）x1的系数列向量由(-1,12)T变为(0,5) T，则x1在最终单纯形表中的系数列向量变为 从而x1在最终单纯形表中的检验数变为 所以LP问题的最优解保持不变。 （5）将原约束条件②改变为10x1+5x2+10x3≤100，则x1在最终单纯形表中系数列向量变为，检验数 x2在最终单纯形表中系数列向量变为，检验数。 又因的各分量均大于0，故LP问题的最优解不变。 （6）增加一个约束条件2x1+3x2+5x3≤50，则在此约束条件中加入松弛变量x6，并将此约束加入到最终单纯