北京航空航天大学：《运筹学》PPT课件_第2章 线性规划 2.1 线性规划的基本定理

第2章线性规划 §2.1线性规划的基本定理 §2.2单纯形算法 §2.3线性规划的内点算法 C 2007 Fang Weiguo School of economics and management

第2章 线性规划 • §2.1 线性规划的基本定理 • §2.2 单纯形算法 • §2.3 线性规划的内点算法 © 2007 Fang Weiguo School of Economics and Management

§2.1线性规划的基本定理 21.0线性规划发展简史 21.1基本定理与标准形式 212极点的代数特征 C 2007 Fang Weiguo School of economics and management

§2.1 线性规划的基本定理 • 2.1.0 线性规划发展简史 • 2.1.1 基本定理与标准形式 • 2.1.2 极点的代数特征 © 2007 Fang Weiguo School of Economics and Management

21.0线性规划发展简史 19世纪末,康特罗维奇和F.L. Hitchcock等研究运 输问题,但其工作长期未被人们所知。由于战争的需要, TC. Koopmans重新独立研究了运输问题。 ·1947年,GB. Dantzig发表单纯形法,应用于与国 防有关的问题。该法实用而有效。单纯形法被认为是20 世纪10大算法之一(其中还有快速 Fourier变换算法等)。 ·但1972年,V.Ke和 G. Minty给出病态例子,用 单纯形法求解可能要检査遍所有的顶点才能得到最优解, 所用时间为O(2").故单纯形法为指数时间算法。 ◎2007 Fang Weiguo School of economics and management

© 2007 Fang Weiguo School of Economics and Management

21.0线性规划发展简史 1979年,前苏联数学家提出了一种求解LP的椭球 算法,计算复杂性为O(n°L2)(L为输入长度)。该算法在理 论上很重要,但计算效率远不如单纯形法有效 ·能否找到有效的多项式时间算法?在此背景下, 1984年,在美国贝尔实验室工作的印度数学家 Karmarkar 给出了一个求解线性规划的新的多项式时间算法,计算复 杂性为O(n312)。通过例题试算,收敛到较好效果,人们 希望借助这种算法解决一些领域中的大规模问题的计算。 ◎2007 Fang Weiguo School of economics and management

© 2007 Fang Weiguo School of Economics and Management

21.0线性规划发展简史 ·对于现实生活中的大多数实际问题,单纯形法仍然 有效.基于单纯形法可以方便地讨论线性规划的对偶理 论,而基于对偶理论可以设计求解LP的对偶单纯形法和 原始一对偶算法及其它算法,因此单纯形法是目前应用最 广泛的算法之 LP之所以重要有以下方面的原因: ■理论算法发展较完善 ■现实生活中许多问题可用LP近似建模 ■在非线性规划的求解中,将问题局部线性化处理 C 2007 Fang Weiguo School of economics and management

© 2007 Fang Weiguo School of Economics and Management

211线性规划标准形式与基本定理 LP标准形: min Cx+c2x2+…+cnxn s t a1X+…+ax 12 b,i=1, LP向量形式: min cx s t Ax=b x≥0 其中A∈Rm",c,x∈R",b∈R" 约定:x,为决策变量,c,为费用(价格)系数,c′x为 目标函数,a为技术系数,b为右端项 ◎2007 Fang Weiguo School of economics and management

© 2007 Fang Weiguo School of Economics and Management

211线性规划标准形式与基本定理 各种形式的线性规划都可以化为标准形: (1) max cx→min(c)x i)a1x+a2x2+…+anxn≤b→>(引入松弛变量) a1x+a12x2+…+amxn+x}=b,x}≥0 i)anx1+a2x2+…+anxn≥b-→(引入剩余变量) 1x1+a12x2+…+anxn-x’=b,x}≥0 i)x,无非负限制,令x=yy",y≥0,y"≥0 (v)x1≥b(h,≠0),令y=x-h,y1≥0(平移变换) ◎2007 Fang Weiguo School of economics and management

© 2007 Fang Weiguo School of Economics and Management

211线性规划标准形式与基本定理 例 max+x min st.2x1+3x2≤6,+ ≥0 7x,≥4 4 4 ≥0 2 3 ≥0 令x2=y2-y2",y2≥0,y2"≥0 标准形:min-x1-y2+y2 st.2x1+3y2-3y2"+x3=6, x1+7y2-7 x1≥0,y2≥0,y2"≥20,x3≥0,x4≥0 ◎2007 Fang Weiguo School of economics and management

© 2007 Fang Weiguo School of Economics and Management

211线性规划标准形式与基本定理 图解法 例max2x1+5 st.x1+2x,≤8 x1≤4 2S3 4 x1≥0,x2≥0 唯一最优解(2,3) C 2007 Fang Weiguo School of economics and management

© 2007 Fang Weiguo School of Economics and Management

211线性规划标准形式与基本定理 max x+2x, St.x1+2x,≤8 x1≤4 x,≤3 x1≥0,x200 有无穷个最优解 C 2007 Fang Weiguo School of economics and management

© 2007 Fang Weiguo School of Economics and Management