线性规划_运筹学.ppt

《线性规划_运筹学.ppt》由会员分享，可在线阅读，更多相关《线性规划_运筹学.ppt（129页珍藏版）》请在一课资料网上搜索。

1、 交通运输与物流工程专业运 筹 学 教 程同济大学交通运输工程学院2006 运筹学定义；运筹学定义；运筹学主要分支；运筹学主要分支；运筹学研究步骤；运筹学研究步骤；绪 论教学要求教学要求运筹学发展简介；运筹学发展简介；关键词：系统（研究对象）；决策优化（研究任务）；定量分析技术（研究方法）；1 1、运筹学定义、运筹学定义 系统优化技术系统优化技术;系统决策优化的定量分析技术系统决策优化的定量分析技术。系 统 指由相互关联、相互制约、相互作用的要素按照一定的结构组成的具有特定功能和性能特征的有机整体。决策优化 决策概念（方案选择）；决策民主化和科学化 （智囊与领导、定性与定量）；决策优化（绝对与

2、相对）；定量化分析技术 数学建模技术；（运筹学方法精髓）模型优化算法；（模型运算及分析）计算机数据库技术等；（大规模问题的计算机求解）运筹学运筹学/Operations Research，英文英文原意是原意是作作战研究、运用研究战研究、运用研究。起源于二次大战的起源于二次大战的军事军事领域领域，发扬于战后的发扬于战后的社会社会、经济、工程与管理经济、工程与管理 领域领域。2 2、运筹学发展简介、运筹学发展简介（英）希（英）希 尔：高射炮系统利用研究尔：高射炮系统利用研究；（英）莫尔斯：美海军大西洋护航方案研究；（英）莫尔斯：美海军大西洋护航方案研究；（英）空军（英）空军OR小组：雷达警报和控制

3、系统研究；小组：雷达警报和控制系统研究；1948年，美国年，美国MIT率先开设了运筹学课程；率先开设了运筹学课程；1950年，美国出版了第一份运筹学杂志；年，美国出版了第一份运筹学杂志；1951年，美国年，美国 与出版出版 了运筹学方法专著，全面总结了二次大战中了运筹学方法专著，全面总结了二次大战中 运筹学的军事应用。运筹学的军事应用。目前，运筹学已广泛应用到现代社会、经济、目前，运筹学已广泛应用到现代社会、经济、工程和管理等各个领域。工程和管理等各个领域。人口、库存、厂址定位、资源分配、能人口、库存、厂址定位、资源分配、能源建设源建设；设计、生产、可靠性、服务设计、生产、可靠性、服务；搜索、

4、控搜索、控制、比赛对抗和军事对抗等；制、比赛对抗和军事对抗等；在交通领域已广泛应用于交通规划、工在交通领域已广泛应用于交通规划、工程建设、运营管理、物流配送等各个阶段；程建设、运营管理、物流配送等各个阶段；。数学规划。数学规划 线性规划；非线性规划；线性规划；非线性规划；整数规划；目标规划；整数规划；目标规划；动态规划；组合规划；动态规划；组合规划；。网络优化技术；。网络优化技术；。排队论与库存论；。排队论与库存论；。对策论与决策论；。对策论与决策论；。搜索论与可靠性理论；。搜索论与可靠性理论；。系统模拟等；。系统模拟等；3 3、运筹学主要分支、运筹学主要分支（1）系统调查与分析，建立系统框架

5、；）系统调查与分析，建立系统框架；（2）构建数学模型，描述决策问题；）构建数学模型，描述决策问题；（3）探索模型求解的结构并导出系统）探索模型求解的结构并导出系统 的求解过程；的求解过程；（4）寻求系统最优解及信息，供决策参考。）寻求系统最优解及信息，供决策参考。4 4、运筹学研究步骤、运筹学研究步骤（1）掌握运筹学）掌握运筹学模型建立的基本技术模型建立的基本技术；（2）掌握运筹学）掌握运筹学模型求解的基本算法模型求解的基本算法；（3）熟练）熟练求解教材各章节的习题求解教材各章节的习题；（4）严禁无故旷课、迟到和早退严禁无故旷课、迟到和早退；（5）独立、按时完成练习与作业独立、按时完成练习与作

6、业；5 5、教学要求、教学要求第一章 线性规划（LP）线性规划问题及其模型建立；两元线性规划问题图解法；线性规划代数解的概念；线性规划问题的几何特征；线性规划单纯形算法；第第1 1节节 线性规划问题及其数学模型线性规划问题及其数学模型1、线性规划问题2、线性规划建模范例3、线性规划数学模型引例引例11：资源配置问题资源配置问题 现有甲、乙两种产品要在车间现有甲、乙两种产品要在车间A A和车间和车间B B加工，加工，有关资料如下表。问：如何组织甲乙两种产品的生有关资料如下表。问：如何组织甲乙两种产品的生产，使利润最大？产，使利润最大？产品在A车间加工时数在B车间加工时数单位产品利润市场容量限制甲

7、216/乙114=7车间可用工时108 1 1、线性规划问题、线性规划问题引例引例22：成本优化问题成本优化问题 某养鸡厂的混合饲料由某养鸡厂的混合饲料由A A、B B、C C三种配料组成三种配料组成，主要包括，主要包括D D、E E、F F三种营养成分，有关资料如下三种营养成分，有关资料如下表。问：如何配置混合饲料，以使总成本最低？表。问：如何配置混合饲料，以使总成本最低？配料/营养DEF单位成本单位成本A11/226B11/213C11/412每份饲料营养标准20610 引例引例33：运输优化问题运输优化问题 运输问题有关资料如下表，在满足各电厂发电用运输问题有关资料如下表，在满足各电厂发

8、电用煤的条件下，如何确定配送方案，使总运费最小？煤的条件下，如何确定配送方案，使总运费最小？单位运价单位运价（Cij）B1B2B3供应量供应量 A1 21350A2 22430需求量 401525 基本概念：基本概念：（1）决策变量；（2）目标函数；（3）约束条件；（4）非负约束。线性规划的基本特征线性规划的基本特征:（1）问题的目标函数可以表示为一组决策 变量的线性函数；（2）问题的约束条件，可以用线性等式或 不等式表示。具有上述特征的优化问题，称之为线性具有上述特征的优化问题，称之为线性规划问题（规划问题（Linear Programing Linear Programing：LP LP）

9、概念总结概念总结例例1 1 合理利用线材问题合理利用线材问题 现在要做现在要做100100套钢架，套钢架，每套用长每套用长2.92.9m m，2.1m2.1m，和和1.51.5m m的圆钢。已知原料为的圆钢。已知原料为长长7.47.4m m的圆钢，问如何合理利用的圆钢，问如何合理利用7.47.4m m的圆钢原料，的圆钢原料，可以使原料最省？可以使原料最省？长度（长度（m)m)(1)(2)(3)(4)(5)(6)(7)(8)(1)(2)(3)(4)(5)(6)(7)(8)2.9 2 1 1 1 0 0 0 02.9 2 1 1 1 0 0 0 0 2.1 0 2 1 0 3 2 1 0 2.1

10、0 2 1 0 3 2 1 0 1.5 1 0 1 3 0 2 3 4 1.5 1 0 1 3 0 2 3 4 剩料剩料(m)0.1 0.3 0.9 0 1.1 0.2 0.8m)0.1 0.3 0.9 0 1.1 0.2 0.8 1 1.4.4 套裁方案套裁方案2 2、线性规划建模范例、线性规划建模范例 设按第设按第i i套方案下料的原材料根数为套方案下料的原材料根数为X Xi i，i=1,5;i=1,5;则线性规划模型如下则线性规划模型如下：S.T.2XS.T.2X1 1+X+X2 2+X+X3 3+X+X4 4 =100 =100 2X 2X2 2+X+X3 3 +3X+3X5 5+2X

11、+2X6 6+X+X7 7 =100=100 X X1 1 +X+X3 3+3X+3X4 4 +2X +2X6 6+3X+3X7 7+4X+4X8 8=100=100 X X1 1,X,X2 2,X,X3 3,X,X4 4,X,X5 5,X,X6 6,X,X7 7,X,X8 8=0=0Min Z=0XMin Z=0X1 1+0.3X+0.3X2 2+0.9X+0.9X3 3+1.1X+1.1X5 5+0.2X+0.2X6 6+0.8X0.8X7 7+1.4X+1.4X8 8Min Z=XMin Z=X1 1 +X+X2 2 +X+X3 3 +X+X4 4 +X+X5 5+X+X6 6 +X+X

12、7 7 +X+X8 8X X*=(30,10,0,50,0,0,0,0)=(30,10,0,50,0,0,0,0)T T Z Z*=90=90S.T.2XS.T.2X1 1+X+X2 2+X+X3 3+X+X4 4 =100 =100 2X 2X2 2+X+X3 3 +3X+3X5 5+2X+2X6 6+X+X7 7 =100=100 X X1 1 +X+X3 3+3X+3X4 4 +2X +2X6 6+3X+3X7 7+4X+4X8 8=100=100 X X1 1,X,X2 2,X,X3 3,X,X4 4,X,X5 5,X,X6 6,X,X7 7,X,X8 8=0=0例例2 2 连续投资问

13、题连续投资问题 某部门在今后某部门在今后5 5年内考虑投资以下年内考虑投资以下A A，B B，C C，D D项目项目。项目项目A A：从第一年到第四年每年年初需要投资，从第一年到第四年每年年初需要投资，并于次年末收回本利并于次年末收回本利115%115%；项目项目B B：从第三年初需要投资，到第五年末收回从第三年初需要投资，到第五年末收回本利本利125%125%，但规定最大投资额不超过，但规定最大投资额不超过4 4万元；万元；项目项目C C：第二年初需要投资，到第五年末收回本第二年初需要投资，到第五年末收回本利利140%140%，但规定最大投资额不超过，但规定最大投资额不超过3 3万元；万元；

14、项目项目D D：五年内每年年初可购买公债，于当年末五年内每年年初可购买公债，于当年末归还，加息归还，加息6%6%；该部门现有资金该部门现有资金1010万元，问如何确定投资方案，万元，问如何确定投资方案，使到第五年末拥有的资金总额最大使到第五年末拥有的资金总额最大？设设X Xijij第第i i年初分配给给项目年初分配给给项目j j的投资额，的投资额，i=1,5;i=1,5;j=A,B,C,Dj=A,B,C,D，则投资方案表示如下如下则投资方案表示如下如下：项目项目 （1 1）（2 2）（3 3）（4 4）（5 5）A XA X1A1A X X2A2A X X3A3A X X4A4A B X B

15、X3B3B C X C X2C2C D X D X1D 1D X X2D 2D X X3D 3D X X4D4D X X5D5D 年初年初S.T.XS.T.X1A 1A+X+X1D1D =100000 =100000 -1.06 X -1.06 X1D 1D +X X2A 2A +X X2C 2C +X X2D 2D =0=0 -1.15 X -1.15 X1A 1A -1.06X-1.06X2D2D+X X3A 3A+X+X3B3B+X X3D3D =0 =0 -1.15 X -1.15 X2A2A-1.06X-1.06X3D3D+X X4A 4A+X X4D4D=0=0 -1.15 X -

16、1.15 X3A3A-1.06X-1.06X4D4D+X X5D5D=0=0 X X2C2C =3000 =3000 X X3B 3B =4000 =0=0，i=1,5;j=A,B,C,Di=1,5;j=A,B,C,D，Max Z=1.15 XMax Z=1.15 X1A 1A+1.40 X+1.40 X2C 2C+1.25 X+1.25 X3B 3B+1.06X+1.06X5D5DX X1A1A*=34783,=34783,X X1D1D*=65217;=65217;X X2A2A*=39130,=39130,X X2C2C*=30000,=30000,X X2D2D*=0;=0;X X3A

17、3A*=0,=0,X X3B3B*=40000,=40000,X X3D3D*=0;X=0;X4A4A*=45000,X=45000,X4D4D*=0;X=0;X5D5D*=0.=0.练习与习题练习与习题目标函数：max，min约束条件：,=,变量符号：0,=0,0,unr3 3、线性规划数学模型、线性规划数学模型线性规划一般型线性规划一般型Max(Min)z=cMax(Min)z=c1 1x x1 1+c+c2 2x x2 2+c+cj jx xj j+c+cn nx xn n a a1111x x1 1+a+a1212x x2 2+a+a1j1jx xj j+a+a1n1nx xn n(=

18、,=,)b b1 1 a ai1i1x x1 1+a+ai2i2x x2 2+a+aijijx xj j+a+aininx xn n(=,=,)b bi i a am1m1x x1 1+a+am2m2x x2 2+a+amjmjx xj j+a+amnmnx xn n(=,=,)b bm m x xj j(=,=,)0,j=1,2,n0,j=1,2,nx xj j(=,=,)0,j=1,2,n0,j=1,2,n1njjjC xMax(Min)z=Max(Min)z=1(,)nijjija xb i=1,2,mi=1,2,m若令：若令：A A.j.j=(a=(a1j1j,a,a2j2j,a,am

19、jmj)T T，b=(b b=(b1 1,b,b2 2,b,bm m)T Tx xj j(=,=,)0,j=1,2,n0,j=1,2,n1njjjC xMax(Min)z=Max(Min)z=1.(,)njjjAxb unr0，Xb(=)AX.t.sXCzmax(min)T(=)令令 C=(cC=(c1 1,c,c2 2,c,cj j,c,cn n)T T;X=(x;X=(x1 1,x,x2 2,x,xj j,x,xn n)T T a a1111 a a1212 a a1j1j a a1n1n A A=a=a2121 a a2222 a a2j2j a a2n 2n ;a am1m1 a am

20、2m2 a amjmj a amnmn目标函数：min约束条件：=变量符号：0右边常数：b0线性规划的标准型线性规划的标准型Min z=cMin z=c1 1x x1 1+c+c2 2x x2 2+c+cj jx xj j+c+cn nx xn n a a1111x x1 1+a+a1212x x2 2+a+a1j1jx xj j+a+a1n1nx xn n=b=b1 1 a ai1i1x x1 1+a+ai2i2x x2 2+a+aijijx xj j+a+aininx xn n=b=bi i a am1m1x x1 1+a+am2m2x x2 2+a+amjmjx xj j+a+amnmn

21、x xn n=b=bm m x xj j 0,j=1,2,n0,j=1,2,n0XbAX.t.sXCzminTx xj j 0,j=1,2,n0,j=1,2,n1njjjC xMin z=Min z=1nijjija xbi=1,2,mi=1,2,mx xj j 0,j=1,2,n0,j=1,2,n1njjjC xMin z=Min z=1.njjjAxb线性规划模型的标准化线性规划模型的标准化 （1 1）MaxMin;MaxMin;(2)(2)约束：松弛变量；约束：松弛变量；(3)(3)约束：剩余变量；约束：剩余变量；(4)(4)自由变量：非负变量；自由变量：非负变量；练习练习1 1 Max

22、 Z=-2XMax Z=-2X1 1+X+X2 2-X-X3 3 s.t.X s.t.X1 1+3X+3X2 2-X-X3 3=30=12=12 X X1 1-4X-4X2 2-4X-4X3 3=2=2 X X1 1=0,X=0,X2 2=0,XB)BB)=进基变量离基变量目标函数约束条件右边常数=目标函数约束条件新的基矩阵右边常数=进基变量离基变量目标函数约束条件基矩阵=目标函数约束条件新的基矩阵右边常数=第第4 4节节 线性规划的几何特征线性规划的几何特征定理定理1 1：(LP)LP)问题的可行域问题的可行域K=X|AX=b,X=0K=X|AX=b,X=0为为凸集凸集；定理定理2 2：若若

23、(LP)LP)问题的可行域问题的可行域K K非空，则必有非空，则必有极点极点；定理定理3 3：(LP)LP)问题的基本可行解问题的基本可行解X X对应于可行域对应于可行域K K的的 极点；极点；定理定理4 4：(LP)LP)问题若有最优解问题若有最优解X X*，则一定可以在可行则一定可以在可行 域域K K的极点上找到。的极点上找到。max z=x1+3x2Ds.t.x1+x2+x3=6 B-x1+2x2 +x4=8 x4=0 C x3=0 x1,x2,x3,x40 x1=0 E O x2=0 AOABCDE基变量x3 x4x1 x4x1 x2x2 x3x2 x4x1 x3非基变量x1 x2x2

24、 x3x3 x4x1 x4x1 x3x2 x4xj0-x4x1基本可行解是是是是否否线性规划的几何特征线性规划的几何特征代数解之间的关系：代数解之间的关系：满足一个不等式约束的解满足一组不等式约束的解：可行解的集合几何概念代数概念约束直线满足一个等式约束的解约束半平面约束半平面的交集：凸多边形约束直线的交点基本解可行域的极点基本可行解目标函数等值线：一组平行线 目标函数值等于一个常数的解基变换 可行域相邻极点之间的变换 第第5 5节节 线性规划的单纯形算法（线性规划的单纯形算法（1 1）算法思想算法思想初始基本可行解求法初始基本可行解求法关于关于X XB B的典式与单纯形表的典式与单纯形表算法

25、规则算法规则基本算法步骤基本算法步骤算法思想算法思想可行域可行域K K相邻顶点迭代搜索相邻顶点迭代搜索X X*确立初始基本可行解确立初始基本可行解：X0X 最优？X0 X，YNX迭代至相邻顶点迭代至相邻顶点X|Z(X)=Z(X)X*结束XX0初始基本可行解求法初始基本可行解求法1 1：“=”=”型约束（型约束（LPLP）问题；问题；Min z=cMin z=c1 1x x1 1+c+c2 2x x2 2+c+cn nx xn ns.t.as.t.a1111x x1 1+a+a1212x x2 2+a+a1n1nx xn n=b b1 1 a a2121x x1 1+a+a2222x x2 2+

26、a+a2n2nx xn n=b b2 2 a am1m1x x1 1+a+am2m2x x2 2+a+amnmnx xn n=0=0 Min z=c Min z=c1 1x x1 1+c+c2 2x x2 2+c+cn nx xn ns.t.as.t.a1111x x1 1+a+a1212x x2 2+a+a1n1nx xn n+x xn+1n+1 =b=b1 1 a a2121x x1 1+a+a2222x x2 2+a+a2n2nx xn n +x xn+2n+2 =b=b2 2 a am1m1x x1 1+a+am2m2x x2 2+.+a+.+amnmnx xn n +x xn+mn+

27、m=b=bm m x x1 1,x,x2 2,x,xn,n,x xn+1,n+1,x xn+2,n+2,x xn+mn+m=0=0取取X XB B=（X Xn+1n+1,X,Xn+2n+2,X,Xn+mn+m)T T，令令X XD D=（X X1 1,x,xn n）T T=0=0 则则X=X=（b b1 1,b,b2 2,b,bm m,0,0,0),0,0,0)T T 为初始基本可行解为初始基本可行解X X0 0初始基本可行解求法初始基本可行解求法2 2：“=”“=”“或或=”=”型约束（型约束（LPLP）问题；问题；见后续的大见后续的大M M法和两阶段法法和两阶段法初始基本可行解求法初始基本

28、可行解求法（LPLP）关于关于X XB B的典式与单纯形表的典式与单纯形表典式典式考察标准型（考察标准型（LPLP）问题问题：0XbAX.t.sXCzminT设设 X XB B=（X XB1B1,X,XBiBi,X,XBmBm)T T X XD D=（X XD1D1,X,Xj j,X,XDn-mDn-m)T T A=(B D)CA=(B D)CT T=(C=(CB BT T C CD DT T)考察约束方程组：考察约束方程组：AX=b AX=b (B D|b)(B D|b)B B-1-1(B D|b)(B D|b)(E B (E B-1-1 D D|B|B-1-1 b)b)取取:B B-1-1

29、 D D =Y=Y,B B-1-1 b=bb=b (E Y|b)(E Y|b)EX EXB B+YX+YXD D=b =b i.e.Xi.e.XB B+YX+YXD D=b=b等价变换后的约束方程组展开如下：等价变换后的约束方程组展开如下：X XB1 B1 +y+y1D11D1X XD1 D1+y+y1j1jX Xj j+y+y1Dn-m1Dn-mX XDn-mDn-m=b=b1 1 X XBi Bi +y+yiD1iD1X XD1 D1+y+yijijX Xj j+y+yiDn-miDn-mX XDn-mDn-m=b=bi i X XBm Bm +y+ymD1mD1X XD1 D1+y+ym

30、jmjX Xj j+y+ymDn-mmDn-mX XDn-mDn-m=b=bm m（LPLP）关于关于X XB B的典式与单纯形表的典式与单纯形表典式典式 令：令：Z Z0 0=C=CB BT T B B-1-1 b b，r rD D=C=CD DT T-C-CB BT T B B-1-1 D D 则：则：Z =ZZ =Z0 0+r+rD DT T X XD D等价变换后的目标函数展开如下：等价变换后的目标函数展开如下：Z =ZZ =Z0 0+r+rD1 D1 X XD1D1+r rj jX Xj j+r rDn-m Dn-m X XDn-mDn-m （LPLP）关于关于X XB B的典式与单

31、纯形表的典式与单纯形表典式典式考察目标函数的等价变换：考察目标函数的等价变换：因：因：Z=CZ=CT TX=CX=CB BT TX XB B+C+CD DT TX XD D；X XB B=B B-1-1 b Bb B-1-1 D D X XD D 所：所：Z=CZ=CB BT T B B-1-1 b+b+（C CD DT T-C-CB BT T B B-1-1 D D ）X XD D（LPLP）标准型关于标准型关于X XB B等价变换如下：等价变换如下：Min Min Z=ZZ=Z0 0+r+rD1 D1 X XD1D1+r rj jX Xj j+r rDn-m Dn-m X XDn-mDn-

32、m X XB1 B1 +y+y1D11D1X XD1 D1+y+y1j1jX Xj j+y+y1Dn-m1Dn-mX XDn-mDn-m=b=b1 1 X XBi Bi +y+yiD1iD1X XD1 D1+y+yijijX Xj j+y+yiDn-miDn-mX XDn-mDn-m=b=bi i X XBm Bm +y+ymD1mD1X XD1 D1+y+ymjmjX Xj j+y+ymDn-mmDn-mX XDn-mDn-m=b=bm m x xB1B1,x,xB2B2,x,xBm,Bm,x xD1D1,x,xD2D2,x,xDn-m,Dn-m,=0=0（LPLP）关于关于X XB B的典

33、式与单纯形表的典式与单纯形表典式典式i.e.i.e.Min Min Z=ZZ=Z0 0+s.t.s.t.X XBi Bi +=b+=bi i i=1,2,m X Xj j=0|=0|称为（称为（LPLP）关于关于X XB B的典式。的典式。Dijjj Iy XDjJj Ir XDj I特征：特征：X X/Z Z均可由非基本变量均可由非基本变量X XD D线性表示。线性表示。功能：功能：X X/Z Z均可依据典式令均可依据典式令X XD D=0=0直接写出。直接写出。令：令：W=-ZW=-Z，典式目标函数方程如下：典式目标函数方程如下：W+=-Z W+=-Z0 0 则则：（：（LPLP）的上述的

34、上述典式可直观表示如下表典式可直观表示如下表T T（B B）。）。（LPLP）关于关于X XB B的典式与单纯形表的典式与单纯形表单纯形表单纯形表DjJj Ir XX XB B X XB B1 1 X XBi Bi X XBmBm X XD1 D1 X Xj j X XDn-mDn-m bbX XB B1 1 1 1 0 0 0 0 y y1D1D1 1 y y1j1j y y1Dn-m1Dn-m b b1 1X XBi Bi 0 0 1 1 0 0 y yiDiD1 1 y yijij y yiDn-miDn-m b bi iX XBm Bm 0 0 0 0 1 1 y ymDmD1 1 y

35、 ymjmj y y1Dn-m1Dn-m b bm m r r 0 0 0 0 0 0 r rD D1 1 r rj j r rDn-mDn-m-Z-Z0 0（Y Y）（r rD D ）（E E）（O O）算法规则算法规则最优判别准则最优判别准则定理定理1 1：若若T T（B B）中中 r rj j=0|=0|，则则X XB B对应的对应的基本可行解基本可行解X X*=（b b1 1,b,b2 2,b,bm m,0,0,0),0,0,0)T T一定是基本最优解。一定是基本最优解。证：证：设设 X=X=（x x1 1，x x2 2，x xn n）T T为（为（LPLP）问题问题 的任意可行解，由

36、典式可知其目标函数值的任意可行解，由典式可知其目标函数值 Z Z（X X）=Z=Z0 0+；X X*=（b b1 1,b,b2 2,b,bm m,0,0,0),0,0,0)T T对对应的应的 目标函数值目标函数值Z Z（X X*）=Z=Z0 0 ；Z Z（X X）-Z Z（X X*）=0=0 Z Z（X X）=Z=Z（X X*），），X X*为最优。为最优。DjIDjJj Ir XDjJj Ir X算法规则算法规则最优判别准则最优判别准则定理定理2 2：若若T T（B B）中中 存在存在r rt t0|0|，而且而且y yt t=（y y1t1t,y,y2t2t,y,ymtmt)T T=0,0

37、)|,Xj=0|=M(M0)|,Xj=0|则由典式可知（则由典式可知（LPLP）问题的一个可行解：问题的一个可行解：X Xb bi i=b=bi i-y-yitit*M(=0_,I=1,2,mM(=0_,I=1,2,m X Xt t=M(0)=M(0)X Xj j=0,=0,对应的目标函数值对应的目标函数值Z Z（X X）=Z=Z0 0+r rt t*M M 显然，显然，M M无穷大时，无穷大时，Z Z（X X）无穷小，无下界。无穷小，无下界。DtIDtI,DjIjt,DjIjt算法规则算法规则基变换迭代准则基变换迭代准则定理定理3 3：若若T T（B B）中中 存在存在r rt t=0|=0

38、|，而且而且 y yt t=（y y1t1t,y,y2t2t,y,ymtmt)T T中中存在存在y yktkt0|10|1 k k m,m,则则（LPLP）问题存在另一个问题存在另一个相邻相邻的基本可行基的基本可行基X XB B，且且 Z Z（X XB B）=Z=Z（X XB B）。证证：（一）构造相邻的基本可行基（一）构造相邻的基本可行基X XB B；（1 1）选择进基变量；）选择进基变量；因为因为 r rt t=0|=0|Z=ZZ=Z0 0+X Xt t进基，进基，Z Z值减小值减小可选择可选择X Xt t作为进基变量；作为进基变量；DtIDtIDjJj Ir X算法规则算法规则基变换迭代

39、准则基变换迭代准则X Xt t|r rt t=Minr=Minrj j|,r|,rj j00 或或X Xt t|t=Minj|,rt=Minj|,rj j00)|,X 0)|,Xj j=0|=0|则由典式可知（则由典式可知（LPLP）问题的等价形式：问题的等价形式：Min ZMin Z（X X）=Z=Z0 0+r rt t*X Xb bi i=b=bi i-y-yitit*,i=1,2,m,i=1,2,m X Xt t=(0)(0)X Xj j=0,=0,显然，显然，Z Z（X X）但但 必须满足以下可行必须满足以下可行 性要求：性要求：X Xb bi i=b=bi i-y-yitit*=0=

40、0 i=1,2,mi=1,2,m,DjIjt（2 2）选择出基变量；）选择出基变量；,DjIjt算法规则算法规则基变换迭代准则基变换迭代准则=Minb=Minbi i/y/yitit|y|yitit0,0,i=1,2,m=bi=1,2,m=bk k/y/yktkt；若令若令=b bk k/y/yktkt，则则 X XBkBk=b=bk k-y-yktkt*b bk k/y/yktkt=0,=0,基本基本变量变量X XBkBk出基成为非基本变量。出基成为非基本变量。i.e.i.e.=b=bi i/y/yitit|y|yitit0,0,i=1,2,mi=1,2,mX XBkBk|b bk k/y/

41、yktkt =Minb=Minbi i/y/yitit|y|yitit0,0,i=1,2,m,i=1,2,m,出基规则：最小比值准则出基规则：最小比值准则若若 b bk k/y/yktkt=b bl l/y/ylt=lt=b bp p/y/yptpt=Min,Min,则取下标则取下标最小者出基。最小者出基。出基规则：下标最小准则出基规则：下标最小准则（二）目标函数值比较（二）目标函数值比较 Z Z（X XB B）=Z=Z0 0 Z Z（X XB B）=Z=Z0 0+r rt t*b bk k/y/yktkt Z Z（X XB B）-Z-Z（X XB B）=r=rt t*bk/ybk/yktkt

42、=0=0 Z Z（X XB B）=Z=Z（X XB B）证毕。证毕。算法规则算法规则基变换迭代准则基变换迭代准则相关概念相关概念 r rj j检验数；检验数；X Xt t 进基变量；进基变量；X XBkBk 出基变量；出基变量；y yt t=（y y1t1t,y,y2t2t,y,ymtmt)T T枢轴列；枢轴列；X XBkBk所在第所在第k k行行枢轴行；枢轴行；y ykt kt 枢轴元素；枢轴元素；转轴运算转轴运算由由T T（B B）至至T T（BB）所进行的方所进行的方程程 组的等价变换。组的等价变换。算法规则算法规则基变换迭代准则基变换迭代准则算法规则算法规则转轴运算准则转轴运算准则X

43、XB B X XB B1 1 X XBiBi X XBk Bk XXBmBm X Xt t X Xj j bbX XB B1 1 1 1 0 00 0 0 0 y y1t 1t y y1j1j b b1 1X XBi Bi 0 0 1 01 0 0 0 y yit it y yijij b bi iX XBk Bk 0 0 0 10 1 0 0 y ykt kt y ykjkj b bk kX XBm Bm 0 0 0 00 0 1 1 y ymt mt y ymjmj b bm m r r 0 0 0 00 0 0 0 r rt t r rj j -Z-Z0 0()()kktby(1)(1)

44、L Lk k=L=Lk k*1/y1/yktkt;(2)L(2)Li i=L=Li i+L+Lk k*(-y(-yitit)=L)=Li i+L+Lk k*(-y(-yitit/y/yktkt););(3)r=r+L(3)r=r+Lk k*(-r(-rt t)=r+L)=r+Lk k*(-r(-rt t/y/yktkt););算法规则算法规则转轴运算准则转轴运算准则X XB B X XB B1 1 X XBiBi X XBk Bk XXBmBm X Xt t X Xj j bbX XB B1 1 1 1 0 00 0 0 0 y y1t 1t y y1j1j b b1 1X XBi Bi 0

45、0 1 01 0 0 0 y yit it y yijij b bi iX XBk Bk 0 0 0 0 1/y1/yktkt0 0 y ykt kt y ykjkj b bk kX XBm Bm 0 0 0 00 0 1 1 y ymt mt y ymjmj b bm m r r 0 0 0 00 0 0 0 r rt t r rj j -Z-Z0 0(1)(1)L Lk k=L=Lk k*1/y1/yktkt;(2)L(2)Li i=L=Li i+L+Lk k*(-y(-yitit)=L)=Li i+L+Lk k*(-y(-yitit/y/yktkt););(3)r=r+L(3)r=r+L

46、k k*(-r(-rt t)=r+L)=r+Lk k*(-r(-rt t/y/yktkt););算法规则算法规则转轴运算准则转轴运算准则X XB B X XB B1 1 X XBiBi X XBk Bk XXBmBm X Xt t X Xj j bbX XB B1 1 1 1 0 00 0 0 0 y y1t 1t y y1j1j b b1 1X XBi Bi 0 0 1 01 0 0 0 y yit it y yijij b bi iX XBk Bk 0 0 0 0 1/y1/yktkt0 0 1 1 y ykjkj b bk kX XBm Bm 0 0 0 00 0 1 1 y ymt m

47、t y ymjmj b bm m r r 0 0 0 00 0 0 0 r rt t r rj j -Z-Z0 0(1)(1)L Lk k=L=Lk k*1/y1/yktkt;(2)L(2)Li i=L=Li i+L+Lk k*(-y(-yitit)=L)=Li i+L+Lk k*(-y(-yitit/y/yktkt););(3)r=r+L(3)r=r+Lk k*(-r(-rt t)=r+L)=r+Lk k*(-r(-rt t/y/yktkt););算法规则算法规则转轴运算准则转轴运算准则X XB B X XB B1 1 X XBiBi X XBk Bk XXBmBm X Xt t X Xj

48、j bbX XB B1 1 1 1 0 00 0 0 0 y y1t 1t y y1j1j b b1 1X XBi Bi 0 0 1 01 0 0 0 y yit it y yijij b bi iX XBk Bk 0 0 0 0 1/y1/yktkt0 0 1 1 y ykj/kj/y ykt kt b bk kX XBm Bm 0 0 0 00 0 1 1 y ymt mt y ymjmj b bm m r r 0 0 0 00 0 0 0 r rt t r rj j -Z-Z0 0(1)(1)L Lk k=L=Lk k*1/y1/yktkt;(2)L(2)Li i=L=Li i+L+Lk

49、 k*(-y(-yitit)=L)=Li i+L+Lk k*(-y(-yitit/y/yktkt););(3)r=r+L(3)r=r+Lk k*(-r(-rt t)=r+L)=r+Lk k*(-r(-rt t/y/yktkt););算法规则算法规则转轴运算准则转轴运算准则X XB B X XB B1 1 X XBiBi X XBk Bk XXBmBm X Xt t X Xj j bbX XB B1 1 1 1 0 00 0 0 0 y y1t 1t y y1j1j b b1 1X XBi Bi 0 0 1 01 0 0 0 y yit it y yijij b bi iX XBk Bk 0 0

50、 0 0 1/y1/yktkt0 0 1 1 y ykj/kj/y yktktb bk k/y ykt kt X XBm Bm 0 0 0 00 0 1 1 y ymt mt y ymjmj b bm m r r 0 0 0 00 0 0 0 r rt t r rj j -Z-Z0 0(1)(1)L Lk k=L=Lk k*1/y1/yktkt;(2)L(2)Li i=L=Li i+L+Lk k*(-y(-yitit)=L)=Li i+L+Lk k*(-y(-yitit/y/yktkt););(3)r=r+L(3)r=r+Lk k*(-r(-rt t)=r+L)=r+Lk k*(-r(-rt