算出最优值线性规划问题求解的几种可能结果ppt课件.ppt

《算出最优值线性规划问题求解的几种可能结果ppt课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、课程网站：exp.vanpersie.cc/operations继续返回图解法线性规划问题求解的几种可能结果由图解法得到的启示回顾线性规划的图解法继续返回例1的数学模型目标函数MaxZ=2x1+3x2约束条件x1+2x284x1164x212x1、x20x1x29—8—7—6—5—4—3—2—1—0

2、

3、

4、

5、

6、

7、

8、

9、

10、123456789x1x2x1+2x28(0,4)(8,0)目标函数MaxZ=2x1+3x2约束条件x1+2x284x1164x212x1、x204x1164x216图解法9

11、—8—7—6—5—4—3—2—1—0x2目标函数MaxZ=2x1+3x2约束条件x1+2x284x1164x212x1、x20

12、

13、

14、

15、

16、

17、

18、

19、

20、123456789x1x1+2x284x1164x216可行域图解法9—8—7—6—5—4—3—2—1—0

21、

22、

23、

24、

25、

26、

27、

28、

29、123456789x1x2目标函数MaxZ=2x1+3x2约束条件x1+2x284x1164x212x1、x20x1+2x284x1164x216可行域BCDEA图解法9—8—7—6—5—4—3—2—1—0x2目标函数

30、MaxZ=2x1+3x2约束条件x1+2x284x1164x212x1、x20

31、

32、

33、

34、

35、

36、

37、

38、

39、123456789x1x1+2x284x1164x216BCDEA2x1+3x2=6图解法9—8—7—6—5—4—3—2—1—0x2目标函数MaxZ=2x1+3x2约束条件x1+2x284x1164x212x1、x20

40、

41、

42、

43、

44、

45、

46、

47、

48、123456789x1x1+2x284x1164x216BCDEAx1+2x2=84x1=16最优解(4,2)图解法图解法求解步骤由全部约束条件作图求出可

49、行域；作目标函数等值线，确定使目标函数最优的移动方向；平移目标函数的等值线，找出最优点，算出最优值。线性规划问题求解的几种可能结果(a)唯一最优解x26—5—4—3—2—1—0

50、

51、

52、

53、

54、

55、

56、

57、

58、123456789x1(b)无穷多最优解6—5—4—3—2—1—0x2

59、

60、

61、

62、

63、

64、

65、

66、

67、123456789x1线性规划问题求解的几种可能结果(c)无界解MaxZ=x1+x2-2x1+x24x1-x22x1、x20x2x1线性规划问题求解的几种可能结果(d)无可行解MaxZ=2x1+3x2x1+2x284x

68、1164x212-2x1+x24x1、x20可行域为空集线性规划问题求解的几种可能结果图解法的几点结论:（由图解法得到的启示）可行域是有界或无界的凸多边形。若线性规划问题存在最优解，它一定可以在可行域的顶点得到。若两个顶点同时得到最优解，则其连线上的所有点都是最优解。解题思路：找出凸集的顶点，计算其目标函数值，比较即得。2.2.2线性规划解的性质线性规划解的概念线性规划问题的几何意义（单纯形法原理）继续返回线性规划问题解的概念线性规划问题解的概念引例（上一章例）线性规划问题解的概念线性规划问题解的概

69、念线性规划问题解的概念标准型可行解:满足Ax=b,x≥0的解X称为线性规划问题的可行解。最优解：使z=CX达到最大值的可行解称为最优解。基：若B是矩阵A中m×m阶非奇异子矩阵（

70、B

71、≠0），则B是线性规划问题的一个基。不妨设：,j=1，2，…,m——基向量。，j=1，2，…,m——基变量。,j=m+1,…,n——非基变量。线性规划问题解的概念求解线性规划问题解的概念基解：称上面求出的x解为基解。基可行解：非负的基解x称为基可行解可行基：对应基可行解的基称为可行基线性规划问题解的概念T基变量令可求出：线性规划解

72、的关系图非可行解可行解基可行解基解线性规划问题解的概念最优解？2.3单纯形法原理本节通过一个引例，可以了解利用单纯形法求解线性规划问题的思路，并将每一次的结果与图解法作一对比，其几何意义更为清楚。求解线性规划问题的基本思路1、构造初始可行基；2、求出一个基可行解（顶点）3、最优性检验：判断是否最优解；4、基变化，转2。要保证目标函数值比原来更优。从线性规划解的性质可知求解线性规划问题的基本思路。引例（上一章例）第1步确定初始基可行解根据显然，可构成初等可行基B。为基变量第2步求出基可行解基变量用非基变量表示，

73、并令非基变量为0时对应的解是否是最优解？第3步最优性检验分析目标函数检验数<=0时，最优解>0时，无解换基，继续只要取x1>0或x2>0,z的值可能增大。换入？基变量换出？基变量考虑将或换入为基变量第4步基变换换入基变量：换入变量均可换入。（即选最大非负检验数对应的变量）一般选取对应的变量换出变量使换入的变量越大越好同时，新的解要可行。选非负的最小者对应的变量换出为换入变量，应换出？变量。因此，基由