运筹学第一章作业课件.ppt

将上述解列表如下，表中所有解都是基解，其中打△是基可行解，有*者为最优解。 30 △ 6 0 4 6 0 45 0 -6 4 9 0 18 0 12 -2 0 6 12 △ 6 12 0 0 4 42 -6 0 0 6 4 27 △ 6 6 0 3 4 36 △* 0 0 2 6 2 0 △ 8 12 4 0 0 Z 解的性质 x5 x4 x3 x2 x1 将上述LP问题的解列表如下，其中打△是基可行解，有*者为最优解。 0 -5 -3 0 0 0 18 -3 0 1 0 0 45 △ 0 9/2 5/2 0 0 30 0 -3 0 5/2 0 36 △* 0 0 1 3/2 0 12 -5 0 0 0 3 27 0 0 5/2 0 -9/2 42 △ 0 0 0 5/2 3 Z 解的性质 x5 x4 x3 x2 x1 1.8 已知LP问题 下表所列的解（a）～（f）均满足条件①②③，试指出表中哪些解是可行解，哪些是基解，哪些是基可行解。 0 2 5 4 0 （f） 2 6 5 2 0 （e） -0.5 0 4 4.5 1 （d） 4 7 2 0 3 （c） 4 0 -5 0 10 （b） 0 0 3 4 2 （a） x5 x4 x3 x2 x1 序号 解：根据可行解定义，只有同时满足约束条件①②③④的解，才是可行解，在上表中（a）（c）（e）（f）是可行解； 因为本问题的基变量个数为3，非基变量个数为2，根据基解定义，非基变量为零的解有（a）（b）（f），即（a）（b）（f） 是基解；（b）中x2和x4的系数为零，（f）中x1和x5的系数为零。 根据基可行解定义，只有满足非负约束条件的基解才是基可行解，因此，（a）（f） 是基可行解； 1.9 分别用图解法和单纯形法求解下列LP问题，并对照指出单纯形法迭代的每一步相当于图解法可行域中的哪一个顶点。 1 3 4 1 2 3 4 Q3(0,9/4) Q2(1,3/2) Q1(8/5,0) x1 x2 解：⑴以x1为横坐标，x2为纵坐标，按比例作图，如右图所示： O(0,0) ⑵用单纯形法计算如下表所示，其与图解法的对应关系见本表和上图 相当O点 -25/14 -5/14 0 0 σj=cj－zj 2/7 -1/7 0 1 1 x1 10 相当Q2点 -3/14 5/14 1 0 3/2 x2 5 -2 0 1 0 σj=cj－zj 1/5 0 2/5 1 8/5 x1 10 相当Q1点 -3/5 1 14/5 0 21/5 x3 0 0 0 5 10 σj=cj－zj 1 0 2 5 8 x4 0 0 1 4 3 9 x3 0 x4 x3 x2 x1 b XB CB 对应关系 0 0 5 10 cj 100 300 400 Q3(0,200) Q2(200,800/6) Q1(200,0) x1 x2 解：⑴以x1为横坐标，x2为纵坐标，按比例作图，如右图所示： 500 600 200 100 200 300 400 500 O(0,0) x1+x2＝500 x1＝200 2x1+6x2＝1200 ⑵用单纯形法计算如下表所示，其与图解法的对应关系见本表和上图 0 1 0 0 1 200 x1 100 0 1 0 0 1 200 x4 0 0 1 0 0 1 200 x4 0 0 1 0 0 1 0 200 6 1 x2 200 相当O点 -200/6 -200/6 0 0 σj=cj－zj 1/6 -2/6 0 0 800/6 x2 200 相当Q2点 -1/6 -4/6 1 0 1000/6 x3 0 -200/6 0 0 200/6 σj=cj－zj 1/6 0 0 2/6 200 x2 200 相当Q3点 -1/6 0 1 4/6 300 x3 0 0 0 0 100 σj=cj－zj 1 0 0 2 1200 x5 0 0 0 1 1 500 x3 0 x5 x4 x3 x1 b XB CB 对应关系 0 0 0 100 cj * 际 恩 陆 运筹学作业 主讲：陆际恩 TelEmail：lujien@163.com 运筹帷幄之中 决胜千里之外 教材P431.1 用图解法求解下列LP问题，并指出问题具有惟一最优解、无穷多最优解、无界解还是无可行解。 从右图可看出,当(x1,x2)=(1.2,0.2)到(x1,x2)=(1.5,0)时,具有无穷多最优解,Z=3。 1 2 2 1 1.5 3x1+2x2=4 4x1+6x2=6 Z=2x1+3x2 从右图可看出,此题无可行解。 2 4 4 2 3x1+4x2=12 2x1+x2=2 1 3 1.