运筹学习题集01.docx

12、已知线性规划 的最优解为，试利用互补松弛定理，求对偶问题的最优解。 解：原问题的对偶问题为： 將代入原问题的约束条件，可得： （1） 又由 （2） 将结论（1）和（2）结合起来，可解得。 13、已知线性规划问题 其对偶问题的最优解为、，试用对偶理论求解原问题的最优解。 解：原问题的对偶问题为： 将对偶问题的最优解代入约束条件，可得： （1） 又由 （2） 将结论（1）和（2）结合起来，可得： ，解得 即原问题的最优解为。 14、用对偶单纯形法求解 解：先将原问题改写为： 建立单纯形表计算如下： －2 －3 －4 0 0 0 －3 －1 －2 －1 1 0 0 －4 [－2] 1 －3 0 1 －2 －3 －4 0 0 0 －1 0 [－5/2] 1/2 1 －1/2 －2 2 1 －1/2 3/2 0 －1/2 0 －4 －1 0 －1 －3 2/5 0 1 －1/5 －2/5 1/5 －2 11/5 1 0 7/5 －1/5 －2/5 0 0 －9/5 －8/5 －1/5 故，原问题的最优解为，。 例2.6 有线性规划如下： 先用单纯形法求出最优解，再分析以下各种条件下，最优解分别有什么变化： （1）约束条件①的右端常数由20变为30； （2）约束条件②的右端常数由90变为85； （3）目标函数中的系数由13变为8； （4）的系数列向量由[-1, 12]T变为[0, 5]T； （5）和的系数列向量由[-1, 12]T 、[1, 4]T变为[0, 5]T 、[2, 1]T； （6）增加一个约束条件③； （7）将约束条件②改变为。 解：分别在约束条件①和②中引入松弛变量和，列单纯形表计算如下： －5 5 13 0 0 0 20 －1 1 [3] 1 0 20/3 0 90 12 4 10 0 1 9 －5 5 13 0 0 13 30/3 －1/3 [1/3] 1 1/3 0 20 0 70/3 46/3 2/3 0 －10/3 1 35 －2/3 2/3 0 －13/3 0 5 20 －1 1 3 1 0 0 10 16 0 －2 －4 1 0 0 －2 －5 0 由此可得，原问题的最优解为，。 由单纯形表可知，原问题中。 （1）约束条件右端常数此时为，由 可知，单纯形表应变为： －5 5 13 0 0 5 30 －1 1 3 1 0 0 －30 16 0 [－2] －4 1 0 0 －2 －5 0 5 －15 23 1 0 [－5] 3/2 13 15 －8 0 1 2 －1/2 －16 0 0 －1 －1 0 3 －23/5 －1/5 0 1 －3/10 13 9 6/5 2/5 1 0 1/10 －103/5 －1/5 0 0 －13/10 由此可得，最优解变为，。 （2）约束条件右端常数此时为，由 可知，最优基不变，最优解为，。 （3）若变为8，则的检验数变为 故最优解不变。 （4）在原最优解中为非基变量，若的系数列变为，由 可知，检验数由0变为－5，故最优解不变。 （5）在原最优解中为基变量，若和的系数列变为，则 在约束①中引入人工变量，单纯形表变为： －5 5 13 0 0 －M －M 20 0 2 [3] 1 0 1 20/3 0 10 5 －7 －2 －4 1 0 －5 5+2M 13+3M M 0 0 13 20/3 0 2/3 1 1/3 0 1/3 0 70/3 5 -17/3 0 -10/3 1 2/3 -5 -11/3 0 -13/3 0 -M-13/3 故，最优解为，。 （6）若引入一个约束③，单纯形表将增加一行。在约束③中引入松弛变量，单纯形表变为： －5 5 13 0 0 0 5 20 －1 1 3 1 0 0 0 10 16 0 －2 －4 1 0 0 50 2 3 5 0 0 1 5 20 －1 1 3 1 0 0 0 10 16 0 －2 －4 1 0 0 －10 5 0 [－4] －3 0 1 0 0 －2 －5 0 0 5 25/2 11/4 1 0 －5/4 0 3/4 0 15 27/2 0 0 －5/2 1 －1/2 0 5/2 －5/4 0 1 3/4 0 －1/4 －5/2 0 0 －7/2 0 －1/2 由此可得，最优解为，。 （7）若约束条件②变为，即、的系数分别变为、，b列变为，则 由于基变量的系数发生变化，故在约束条件①中引入人工变量，单纯形表变为： －5 5 13 0 0 －M -M 20 -1 1 [3] 1 0 1 20/3 0 20 14 1 －2 －4 1 0 -5-M 5+M 13+3M M 0 0 13 20/3 -1/3 1/3 1 1/3 0 1/3 20 0 100/3 40