1.2 线性规划的图解法

《1.2 线性规划的图解法》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、管理运筹学--管理科学方法李军桂林电子科技大学商学院第二节线性规划的图解法图解法学习要点123456图解法图解步解的有解的可图解几解与可定义骤关概念能结果何意义行域2一、图解法的定义图解法就是用几何作图求LP的最优解的方法。前提条件变量个数不能超过两个。图解法的①利用它来说明LP问题求解的可能结局。目的②在LP问题最优解存在时，求出最优解。③为寻求LP问题的一般算法提供依据。3二、图解法的步骤图解法的步骤Step4寻找最优解Step3图示目标函数，确定优化方向Step2图示约束条件，找出可行域Step1在平面上建立直角坐标系

2、4x2MaxZ3x5x9122x1=162x161D5C2x=1022x102ts..3x4x323B12x0x012x1048A103x1+4x22=3282x1=16例1：图解法DC52x2=10X*=(4,5)3BZ=37Z=30*Z=15Z=37x1048A1053x1+4x2=32三、有关线性规划的概念最优解:使目标函数达到最x2优的可行解82x1=16可行解：满DC足全部约束条52x2=10件的x取值（点对）。3BZ=37Z=30Z=15x1048A103x1+4x2=32可行域：满足全部约

3、束条件的点集6MaxZ2x3x图解法例2124x161x24x2129—st..x2x88—127—x1,x206—4x1165—(0,4)4—4x2123—x1+2x282—1—(8,0)0

4、

5、

6、

7、

8、

9、

10、

11、

12、x11234567897图解法例2MaxZ2x3x124x161x24x129—2st..8—x2x8127—x,x0126—4x1165—1、可行域：满4—足所有约束条件的3—4x216解的集合，即所有x1+2x28约束条件共同围城2—可行域的区域（或称可行1

13、—解集）,记做RR。0

14、

15、

16、

17、

18、

19、

20、

21、

22、x11234567898图解法例2MaxZ2x3x124x161x24x129—2st..8—x12x287—x1,x206—4x1165—4—B2、可行解：C4x2163—满足全部约Dx1+2x282—束条件的某1—可行域一点。E0

23、

24、

25、

26、

27、

28、

29、

30、

31、x1A1234567899MaxZ2x3x12图解法例24x116x24x129—2ts..8—x12x287—x,x0126—4x1165—4—B4x216C3—22xx+3xx=

32、6D11222—x1+2x281—E0

33、

34、

35、

36、

37、

38、

39、

40、

41、x1A12345678910MaxZ2x3x图解法例2124x161最优解：4x122x2x1=4，x2=2ts..9—x2x812目标函数：8—x,x0Z*=14127—6—x1+2x2=84x1165—4x1=164—B4x216C3—最优解(4,2)3.最优解：使目D标函数达到最优极2—x1+2x28值的可行解；1—4.最优值：最优E0

42、

43、

44、

45、

46、

47、

48、

49、

50、x解代入目标函数后1A123456789的目标函数值。11四、LP求解的几种可能结果M

51、axZ2x3x(a)唯一最优解124x116x4x2122ts..x2x8126—x,x05—124—3—2—1—

52、

53、

54、

55、

56、

57、

58、

59、

60、0x112345678912四、LP求解的几种可能结果(b)无穷多最优解MaxZ2x14x24x116x24x212ts..x2x86—12X*=X+（1-5—x1,x201）X24—X1=(4,2),X2=(2,3)3—2—1—

61、

62、

63、

64、

65、

66、

67、

68、

69、0x112345678913四、LP求解的几种可能结果(c)无界解x2MaxZ2xx122x

70、x412ts..x1x22x,x012x114四、LP求解的几种可能结果(d)无可行解MaxZ2x3x12x2x12x286—4x1615—ts..4x2124—2xx4123—x1,x202—1—

71、

72、

73、

74、

75、

76、

77、

78、

79、没有可行域0x1123456789-2-115四、LP求解的几种可能结果xx22x1x1唯一最优解无界解x2x2x1x1无穷多最优解无可行解16五、图解法的几何意义凸集如果一个非空集合中任意两点的连线段上所有点仍属于该集合，则称该集合为凸集。顶点若凸集中的一个点不是任

80、何另外两点连线段上的点，则称该点为这个凸集的顶点。凸集顶点不是凸集17五、图解法的几何意义启示1启示2启示3可行域是有界若线性规划问若两个顶点同或无界的凸多题存在最优解时得到最优解边形。，它一定可以，则其连线上在可行域的