资源描述:
《1.2 线性规划的图解法》由会员上传分享,免费在线阅读,更多相关内容在行业资料-天天文库。
1、管理运筹学--管理科学方法李军桂林电子科技大学商学院第二节线性规划的图解法图解法学习要点123456图解法图解步解的有解的可图解几解与可定义骤关概念能结果何意义行域2一、图解法的定义图解法就是用几何作图求LP的最优解的方法。前提条件变量个数不能超过两个。图解法的①利用它来说明LP问题求解的可能结局。目的②在LP问题最优解存在时,求出最优解。③为寻求LP问题的一般算法提供依据。3二、图解法的步骤图解法的步骤Step4寻找最优解Step3图示目标函数,确定优化方向Step2图示约束条件,找出可行域Step1在平面上建立直角坐标系
2、4x2MaxZ3x5x9122x1=162x161D5C2x=1022x102ts..3x4x323B12x0 x012x1048A103x1+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、束条件的点集6MaxZ2x3x图解法例2124x161x24x2129—st..x2x88—127—x1,x206—4x1165—(0,4)4—4x2123—x1+2x282—1—(8,0)0
4、
5、
6、
7、
8、
9、
10、
11、
12、x11234567897图解法例2MaxZ2x3x124x161x24x129—2st..8—x2x8127—x,x0126—4x1165—1、可行域:满4—足所有约束条件的3—4x216解的集合,即所有x1+2x28约束条件共同围城2—可行域的区域(或称可行1
13、—解集),记做RR。0
14、
15、
16、
17、
18、
19、
20、
21、
22、x11234567898图解法例2MaxZ2x3x124x161x24x129—2st..8—x12x287—x1,x206—4x1165—4—B2、可行解:C4x2163—满足全部约Dx1+2x282—束条件的某1—可行域一点。E0
23、
24、
25、
26、
27、
28、
29、
30、
31、x1A1234567899MaxZ2x3x12图解法例24x116x24x129—2ts..8—x12x287—x,x0126—4x1165—4—B4x216C3—22xx+3xx=
32、6D11222—x1+2x281—E0
33、
34、
35、
36、
37、
38、
39、
40、
41、x1A12345678910MaxZ2x3x图解法例2124x161最优解:4x122x2x1=4,x2=2ts..9—x2x812目标函数:8—x,x0Z*=14127—6—x1+2x2=84x1165—4x1=164—B4x216C3—最优解(4,2)3.最优解:使目D标函数达到最优极2—x1+2x28值的可行解;1—4.最优值:最优E0
42、
43、
44、
45、
46、
47、
48、
49、
50、x解代入目标函数后1A123456789的目标函数值。11四、LP求解的几种可能结果M
51、axZ2x3x(a)唯一最优解124x116x4x2122ts..x2x8126—x,x05—124—3—2—1—
52、
53、
54、
55、
56、
57、
58、
59、
60、0x112345678912四、LP求解的几种可能结果(b)无穷多最优解MaxZ2x14x24x116x24x212ts..x2x86—12X*=X+(1-5—x1,x201)X24—X1=(4,2),X2=(2,3)3—2—1—
61、
62、
63、
64、
65、
66、
67、
68、
69、0x112345678913四、LP求解的几种可能结果(c)无界解x2MaxZ2xx122x
70、x412ts..x1x22x,x012x114四、LP求解的几种可能结果(d)无可行解MaxZ2x3x12x2x12x286—4x1615—ts..4x2124—2xx4123—x1,x202—1—
71、
72、
73、
74、
75、
76、
77、
78、
79、没有可行域0x1123456789-2-115四、LP求解的几种可能结果xx22x1x1唯一最优解无界解x2x2x1x1无穷多最优解无可行解16五、图解法的几何意义凸集如果一个非空集合中任意两点的连线段上所有点仍属于该集合,则称该集合为凸集。顶点若凸集中的一个点不是任
80、何另外两点连线段上的点,则称该点为这个凸集的顶点。凸集顶点不是凸集17五、图解法的几何意义启示1启示2启示3可行域是有界若线性规划问若两个顶点同或无界的凸多题存在最优解时得到最优解边形。,它一定可以,则其连线上在可行域的