教案2标准型及解的几何意义(改)

《教案2标准型及解的几何意义(改)》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、11．3线性规划问题的标准形式为了求解LP问题，必须统一其模型，本课程选用标准型式为（1)目标函数为求最大对于目标函数是求最小怎么办？minZ=1000x1+800x2令：z’=-z,则minz=maxz’maxZ’=-1000x1-800x22（2)约束条件均用线性等式方程来表示，且右边常数项均非负。实际情形约束条件显然不可能都是等式关系。当表达式中含“≤”时可在约束条件左边加上一个非负的变量——松弛变量，使原来的“≥”变为“＝”；maxz=2x1+3x2s.t.x1+2x2+x3=84x1+x4=164x2+x5=12x1，x2，x3，x4，x50maxz=2x1+3x2s.t.x

2、1+2x284x1164x212x1，x203当表达式中含“≥”时，可以在约束条件左边减去一个非负变量——剩余变量，使原来的“≥”变为“＝”。目标：minf=1000x1+800x2约束条件：x1≥10.8x1+x2≥1.6x1≤2x2≤1.4x1、x2≥0maxz'＝–minz＝－1000x1－800x2＋0·x3＋0·x4＋0·x5＋0·x6s．t．x1－x3＝10.8x1+x2－x4＝1.6x1＋x5＝2x2＋x6＝1.4x1、x2、x3、x4、x5、x6≥04（3）所有变量要求非负现实中，有些变量可能从物理意义或经济意义上讲没有非负要求minz=x1－x2＋4x3s．t．3

3、x2－4x3≥－9－x1+x2≥65x2＋2x3≤16x1≤0，x2≥0，x3无符号限制解：令x1’=－x1，x1’≥0，x3=x3’－x3’’,x3’、x3’’≥0将第一个约束条件两端乘“－1”并加入松弛变量x4，第二个约束减剩余变量x5，第三个约束加入松弛变量x6，代入整理后得：maxz’=x1’＋x2－4x3’＋4x3’’s．t．－3x2＋4x3’－4x3’’＋x4＝9x1’+x2－x5=65x2＋2x3’－2x3’’+x6=16x1’，x2，x3’、x3’’，x4，x5，x6≥05练习：minz=2x1－x2＋2x3s．t．－x1＋x2＋x3＝4－x1+x2－x3≤6x1≤0，x2

4、≥3，x3无符号限制maxz=2x1+x2＋3x3＋x4s．t．x1+x2＋x3＋x4≤72x1-3x2＋x3＝-8－x1-2x2＋2x4≥1x1,x3≥0,x2≤0，x4无符号限制再思考：如果x有区间限制怎么办？6经过上述过程，可得到线性规划问题数学模型的标准形式为：maxz=c1x1+c2x2+···+cnxn(1.1)s.t.a11x1+a12x2+···+a1nxn=b1a21x1+a22x2+···+a2nxn=b2······(1.2)am1x1+am2x2+···+amnxn=bmx1，x2，···，xn0(1.3)其中bi0，（i=1，2，···，m）一般m

5、>0。7标准型的简写形式:maxz=c1x1+c2x2+···+cnxn(1.1)s.t.a11x1+a12x2+···+a1nxn=b1a21x1+a22x2+···+a2nxn=b2······(1.2)am1x1+am2x2+···+amnxn=bmx1，x2，···，xn0(1.3)用求和符号表示8用矩阵描述为：maxz=CXAX=bX0=(P1，P2，···，Pn)；a11…a12…a1na21…a22…a2n……am1…am2…amnA=称A为约束条件的m×n阶系数矩阵，一般A的秩为m。0=00…09用向量表示：X=x1x2…xnPj=a1ja2j…amjb=b1b2…bm

6、向量Pj对应的决策变量为xj。10b1b2bm(p1,p2,…,pn)ΣPjxj=ba11a12…a1na21a22…a2n………am1am2…amnx1x2xn=xj≥0j=1,…,nx1x2xnMaxz=x1x2xn(c1,c2,…,cn)=Σcjxj=CX=Σaijxj=bii=1,…,mAX=bX≥0b111．4线性规划问题的解的概念maxz=2x1+3x2s.t.x1+2x2+x3=84x1+x4=164x2+x5=12x1，x2，x3，x4，x5012基A中的m×m阶非奇异矩阵B；（意味着A的秩为m，

7、B

8、≠0，B的各列线性无关）·基向量B中的列向量；·基变量B中的

9、列向量对应的变量；·非基变量非B中的列向量对应的变量；例如，若A的前m列线性无关，则a11…a12…a1ma21…a22…a2m……am1…am2…amm=(P1，P2，…，Pm)B=是个基。P1，P2，…，Pm是基向量；x1，x2，…，xm是基变量；xm+1，…，xn是非基变量；若Am×n，m