运筹学PPT精品课程课件全册课件汇总.ppt

1、授课人：XX XX XX学院 XX 专业【全套课件全套课件】第第1 1章章 运筹学思想与运筹学建模运筹学思想与运筹学建模 第第2 2章章 基本概念和理论基础基本概念和理论基础 第第3 3章章 线性规划线性规划 第第4 4章章 最优化搜索算法的结构与一维搜索最优化搜索算法的结构与一维搜索 第第5 5章章 无约束最优化方法无约束最优化方法 第第6 6章章 约束最优化方法约束最优化方法 第第7 7章章 目标规划目标规划 第第8 8章章 整数规划整数规划 第第9 9章章 网络计划网络计划 第第1010章章 层次分析法层次分析法 第第1111章章 智能优化计算简介智能优化计算简介第第 1 1 章章运筹学

2、简称运筹学简称 OR（美）（美）Operations Research（英）（英）Operational Research“运筹于帷幄之中，决胜于千里之外运筹于帷幄之中，决胜于千里之外”三个来源：军事、管理、经济三个来源：军事、管理、经济 三个组成部分：三个组成部分：运用分析理论、竞争理论、随机服务理论运用分析理论、竞争理论、随机服务理论 运筹学是为决策机构在对其控制下的业运筹学是为决策机构在对其控制下的业务活动进行决策时，提供一门以量化为务活动进行决策时，提供一门以量化为基础的科学方法。基础的科学方法。运筹学是一门应用科学，它广泛应用现运筹学是一门应用科学，它广泛应用现有的科学技术知识和数学

3、方法，解决实有的科学技术知识和数学方法，解决实际中提出的专门问题，为决策者选择最际中提出的专门问题，为决策者选择最优决策提供定量依据。优决策提供定量依据。运筹学是一种给出问题坏的答案的艺术，运筹学是一种给出问题坏的答案的艺术，否则的话，问题的结果会更坏。否则的话，问题的结果会更坏。(1)合伙原则：应善于同各有关人员合作。合伙原则：应善于同各有关人员合作。(2)催化原则：善于引导人们改变一些常规看催化原则：善于引导人们改变一些常规看法。法。(3)互相渗透原则：多部门彼此渗透地考虑。互相渗透原则：多部门彼此渗透地考虑。(4)独立原则：不应受某些特殊情况所左右。独立原则：不应受某些特殊情况所左右。(

4、5)宽容原则：思路宽、方法多，不局限在某宽容原则：思路宽、方法多，不局限在某一特定方法上。一特定方法上。(6)平衡原则：考虑各种矛盾的平衡、关系的平衡原则：考虑各种矛盾的平衡、关系的平衡。平衡。(1)(1)提出问题：目标、约束、决策变量、参数。提出问题：目标、约束、决策变量、参数。(2)(2)建立模型：变量、参数、目标之间的关系表建立模型：变量、参数、目标之间的关系表 示。示。(3)(3)模型求解：数学方法及其他方法。模型求解：数学方法及其他方法。(4)(4)解的检验：制定检验准则、讨论与现实的一解的检验：制定检验准则、讨论与现实的一致性。致性。(5)(5)灵敏性分析：参数扰动对解的影响情况。

5、灵敏性分析：参数扰动对解的影响情况。(6)(6)解的实施：回到实践中。解的实施：回到实践中。(7)(7)后评估：考察问题是否得到完满解决。后评估：考察问题是否得到完满解决。1.直直 接接 分分 析析 法法2.类类 比比 方方 法法3.模模 拟拟 方方 法法4.数数 据据 分分 析析 法法5.试试 验验 分分 析析 法法6.构构 想想 法法模型评价模型评价:易于理解、易于探查错误、易于计算等易于理解、易于探查错误、易于计算等opt.f(xi,yj,k)s.t.gh(xi,yj,k),0 h=1,2,m其中，其中，xi 为决策变量（可控制）为决策变量（可控制）yj 为已知参数为已知参数 k 为随机

6、因素为随机因素 f,gh 为（一般或广义）函数为（一般或广义）函数建模举例（略）建模举例（略）自看自看1.1.向量和子空间投影定理向量和子空间投影定理(1)(1)n维欧氏空间：维欧氏空间：R Rn 点（向量）点（向量）：x R Rn,x=(x1,x2,xn)T 分量分量 xi R R(实数集实数集)方向（自由向量）方向（自由向量）：d R Rn,d 0 d=(d1,d2,dn)T 表示从表示从0 0指向指向d 的方的方向向 实用中，常用实用中，常用 x+d 表示从表示从x 点出发沿点出发沿d 方方向移动向移动d 长度得到的点。长度得到的点。d0 xx+(1/2)d(2)(2)向量运算：向量运算

7、：x,y R Rn n x,y 的内积：的内积：xTy=xi yi=x1y1+x2y2+xn yn i=1 x,y 的距离：的距离：xy=(x y)T(x y)(1/2)x 的长度：的长度：x=xTx(1/2)三角不等式三角不等式：x+y xy 点列的收敛：点列的收敛：设点列设点列x(k)R Rn ,x R Rn 点列点列x(k)收敛到收敛到 x，记记lim x(k)=x limx(k)x=0 lim xi(k)=xi,ik k kx+yyx(3)(3)子空间：子空间：设设 d(1),d(2),d(m)R Rn,d(k)0，记记 m L(d(1),d(2),d(m)=x=j d(j)j R j

8、=1为由向量为由向量d(1),d(2),d(m)生成的子空间，简记为生成的子空间，简记为L L。正交子空间：设正交子空间：设 L 为为R Rn的的子空间，其正交子空间为子空间，其正交子空间为 L x R Rn xTy=0,y L 子空间投影定理：子空间投影定理：设设 L 为为R Rn n的的子空间，那么子空间，那么 z R Rn，唯一唯一 x L,y L,使使 z=x+y,且且 x 为问题为问题 min z u s.t.u L 的唯一解，最优值为的唯一解，最优值为y。特别地，特别地，L R Rn n 时，正交子空间时，正交子空间 L 0（零空间零空间）。规定：规定：x,y R Rn，x y x

9、i yi，i；类似地规定类似地规定 x y，x=y，x y。一个有用的定理一个有用的定理 设设 x R Rn，R R，L L为为R Rn 的线性子空间。的线性子空间。若若 xTy ,y R Rn 且且 y 0，则则 x 0，0 若若 xTy ,y L R Rn，则则 x L L，0(特别特别地地,当当L LR Rn n时时,x=0=0)定理的其他形式：定理的其他形式：若若 xTy ,y R Rn 且且 y 0，则则 x 0，0。若若 xTy ,y R Rn 且且 y 0，则则 x 0，0。若若 xTy ,y R Rn 且且 y 0，则则 x 0，0。若若 xTy ,y L L R Rn，则则

10、x L L，0。2.2.多元函数及其导数多元函数及其导数(1)(1)n元函数：元函数：f(x):):R Rn R R 线性函数线性函数：f(x)=cTx+b=ci xi+b 二次函数二次函数：f(x)=(1/2)xTQx+cTx+b =(1/2)aij xi xj +ci xi +b 向量值线性函数：向量值线性函数：F(x)=Ax+d R Rm其中，其中，A为为 mn矩阵，矩阵，d为为m维向量维向量 F(x)=(f1(x),f2(x),fm(x)T 记记 aiT为为A的第的第i行向量，行向量，f(x)=aiTx(2)(2)梯度（一阶偏导数向量）：梯度（一阶偏导数向量）：f(x)(f/x1,f/

11、x2,f/xn)T R Rn 线性函数线性函数：f(x)=cTx+b,f(x)=c 二次函数二次函数：f(x)=(1/2)xTQx+cTx+b f(x)=Qx+c 向量值线性函数：向量值线性函数：F(x)=Ax+d R Rm F/x=AT(3)Hesse(3)Hesse 矩阵（二阶偏导数矩阵）：矩阵（二阶偏导数矩阵）：2f/x1 2 2f/x2 x1 2f/xn x1 2f(x)=2f/x1 x2 2f/x22 2f/xn x2 2f/x1 xn 2f/x2 xn 2f/xn2 线性函数线性函数：f(x)=cTx+b,2f(x)=0 二次函数二次函数：f(x)=(1/2)xTQx+cTx+b,

12、2f(x)=Q(4)(4)n元函数的元函数的TaylorTaylor展开式及中值公式展开式及中值公式 设设 f(x):):R Rn R R，二阶可导。在二阶可导。在x*的邻域内的邻域内,有有 一阶一阶TaylorTaylor展开式：展开式：f(x)=f(x*)+f T(x*)(xx*)+ox x*二阶二阶TaylorTaylor展开式：展开式：f(x)=f(x*)+f T(x)(x x*)+(1/2)(x x*)T 2f(x*)(x x*)+ox x*2 一阶中值公式：对一阶中值公式：对x,使使 f(x)=f(x*)+f(x*+(x x*)T(x x*)Lagrange余项：余项：对对x,记记

13、x x*+(x x*)f(x)=f(x*)+f T(x)(x x*)+(1/2)(x x*)T 2f(x)(x x*)复习下列知识：复习下列知识：线性代数的有关概念：向量与矩线性代数的有关概念：向量与矩阵的运算，向量的线性相关和线阵的运算，向量的线性相关和线性无关，矩阵的秩，正定、半正性无关，矩阵的秩，正定、半正定矩阵，线性空间等。集合的有定矩阵，线性空间等。集合的有关概念：开集、闭集，集合运算，关概念：开集、闭集，集合运算，内点、边界点等。内点、边界点等。基本概念基本概念和和 理论基础理论基础1.11.1数学规划模型的一般形式数学规划模型的一般形式 Min Min f(x)目标函数目标函数

14、s.t.s.t.x S 约束集合，可行集约束集合，可行集其中，其中，S Rn，f:S R R，xS称称（f S)的可行解的可行解 最优解最优解:x*S，满足满足f(x*)f(x),x S，则称则称 x*为为(f S)的全局最优解的全局最优解(最优解最优解),),记为记为 g.opt.(global optimum),),简记简记 为为opt.。最优值最优值:x*为为(f S)的最优解的最优解,则称则称 f*=f(x*)为为 (f S)的最优值的最优值(最优目标函数值最优目标函数值)。(f S)局部最优解局部最优解:x*S，x*的邻域的邻域 N(x*)，使满足，使满足 f(x*)f(x),x S

15、 N(x*),则称则称 x*为为(f S)的局的局部最优解部最优解,记记 为为l.opt.(local optimum)。在上述定义中，当在上述定义中，当x x*时有严格不等式成立，时有严格不等式成立，则则分别称分别称 x*为为(f S)的严格全局最优解和严格局部最的严格全局最优解和严格局部最优解。优解。严格严格l.opt.严格严格g.opt.l.opt.函数形式函数形式:f (x),gi(x),hj(x):RnR Min f (x)(fgh)s.t.gi(x)0 ,i=1,2,m hj(x)=0 ,j=1,2,l 矩阵形式矩阵形式:Min f(x)，f(x):RnR(fgh)s.t.g(x)

16、0 ,g(x):RnRm h(x)=0 ,h(x):RnRl 当当 f(x),gi(x),hj(x)均为线性函数时，称其均为线性函数时，称其为线性规划；若其中有非线性函数时，称其为非为线性规划；若其中有非线性函数时，称其为非线性规划。线性规划。1.凸集凸集（1）凸集的概念）凸集的概念定义定义1 设集合设集合 S Rn，若若 x(1),x(2)S,0,1，必有必有 x(1)(1)x(2)S，则称，则称 S 为凸集。为凸集。规定：单点集规定：单点集 x 为凸集，空集为凸集，空集为凸集。为凸集。注注:x(1)(1)x(2)=x(2)(x(1)x(2)是是连接连接 x(1)与与x(2)的线段的线段。凸

17、集凸集非凸集非凸集非凸集非凸集 例例1 1 证明集合证明集合 S=x Ax=b 是凸集。是凸集。其中，其中，A为为 mn矩阵，矩阵，b为为m维向量。维向量。凸组合：凸组合：设设 x(1),x(2),x(m)R Rn,j 0，m m j=1,那么称那么称 j x(j)为为x(1),x(2),x(m)的的 j=1 j=1凸组合。凸组合。m 比较比较:z=j x(j)j=1j R 构成线性组合构成线性组合 线性子空间线性子空间j0,j 0 构成半正组合构成半正组合 凸锥凸锥j0,j=1 构成凸组合构成凸组合 凸集凸集定理定理1 S是凸集是凸集S中任意有限点的凸组合属于中任意有限点的凸组合属于S。多胞

18、形多胞形 H(x(1),x(2),x(m)：由：由 x(1),x(2),x(m)的所有凸组合构成。的所有凸组合构成。单纯形：若单纯形：若多胞形多胞形 H(x(1),x(2),x(m)满足，满足，x(2)x(1),x(3)x(1),x(m)x(1)线性无线性无关。关。多胞形多胞形单纯形单纯形单纯形单纯形（2）凸集的性质）凸集的性质1)凸集的交集是凸集；凸集的交集是凸集；（并？）（并？）2)凸集的内点集是凸集；凸集的内点集是凸集；（逆命题是否成立？）（逆命题是否成立？）3)凸集的闭包是凸集。凸集的闭包是凸集。（逆命题是否成立？）（逆命题是否成立？）4)分离与支撑：凸集边界上任意点存在支分离与支撑：

19、凸集边界上任意点存在支撑超平面；两个互相不交的凸集之间存撑超平面；两个互相不交的凸集之间存在分离超平面。在分离超平面。支撑支撑强分离强分离分离分离非正常非正常分离分离（3）凸锥）凸锥 定义定义2 C Rn,若若 x C,0，有，有 x C,则则称称 C 是以是以 0 为顶点的锥。如果为顶点的锥。如果 C 还是凸集，还是凸集，则称为凸锥。则称为凸锥。集合集合 0、Rn 是凸锥。是凸锥。命题：命题：C是凸锥是凸锥C中任意有限点的半正组合属于中任意有限点的半正组合属于S。02.凸函数凸函数 （1）凸函数及水平集）凸函数及水平集定义定义3 设集合设集合 S Rn 为凸集，函数为凸集，函数 f:SR。若

20、。若 x(1),x(2)S,(0,1)，均有，均有 f(x(1)(1)x(2)f(x(1)+(1 )f(x(2)，则称则称 f(x)为凸集为凸集 S 上的凸函数。上的凸函数。若进一步有上面不等式以严格不等式成立，则若进一步有上面不等式以严格不等式成立，则称称 f(x)为凸集为凸集 S 上的严格凸函数。上的严格凸函数。(几何意义见几何意义见P27)当当 f(x)为凸函数（严格凸函数）时，则称为凸函数（严格凸函数）时，则称 f(x)为凹函数（严格凹函数）。为凹函数（严格凹函数）。严格凸函数严格凸函数凸函数凸函数严格凹函数严格凹函数定理定理2 f(x)为凸集为凸集 S 上的凸函数上的凸函数 S 上上

21、任意有限点的凸组合的函数值不大于各点任意有限点的凸组合的函数值不大于各点函数值的凸组合。函数值的凸组合。思考：设思考：设f1,f2是凸函数。是凸函数。1)设设1,2 0,1f1+2f2,1f1 2f2是否凸是否凸函数？函数？(都是都是)2）f(x)=max f1(x),f2(x),g(x)=min f1(x),f2(x)是否凸函数？是否凸函数？（不一定）（不一定）定义定义4 设集合设集合 S Rn，函数，函数 f:SR，R，称称 S=x S f(x)为为 f(x)在在 S 上上 的的 水平集水平集。定理定理3 设集合设集合 S R n是凸集，函数是凸集，函数 f:SR是是凸函数，则对凸函数，则

22、对 R，S 是凸集是凸集。注：注：1)水平集的概念相当于在地形图中，海拔高度不高于某一水平集的概念相当于在地形图中，海拔高度不高于某一数值的区域。数值的区域。2)上述定理的逆不真。上述定理的逆不真。考虑分段函数考虑分段函数f(x)=1(x0)或或0(x 0 充分小时有充分小时有 x*+d S,如果如果 lim f(x*+d)f(x*)/存在（包括存在（包括 ）则称则称 f(x)为在点为在点x*沿方向沿方向d的方向导数存在，记的方向导数存在，记 f (x*;d)=lim f(x*+d)f(x*)/若若 f(x)在在 x*可导，则可导，则 f (x*;d)=f(x*)Td 。以下设以下设 S Rn

23、 为非空凸集，函数为非空凸集，函数 f:SR2）若）若f 凸，则凸，则 f 在在 S 的内点集上连续。的内点集上连续。注：注：f 在在 S 上不一定连续。上不一定连续。例如例如:f(x)2(当当 x=1)；f(x)x2(当 x 0,总有总有 x+d S(可行方向可行方向)。其中，当。其中，当d(1)=d(2)(0)时，称时，称 d(1)和和d(2)同方同方向。向。（4）极方向：方向）极方向：方向 d 不能表示为两个不不能表示为两个不同方向的组合同方向的组合(d=d(1)+d(2)。定理定理5（极点特征）设（极点特征）设 A 满秩，满秩，x 是是 S 极极点的充分必要条件是点的充分必要条件是:存

24、在分解存在分解 A=（B,N），其中），其中B为为m阶非奇异矩阵，使阶非奇异矩阵，使 xT=（xBT,xNT）,这里这里 xB=B1b0,xN=0。S中必存在有限多个极点中必存在有限多个极点(Cnm)。定理定理 6（极方向特征）设（极方向特征）设 A=（p1,p2,pn）秩秩为为m，d 是是 S 极方向的充分必要条件是极方向的充分必要条件是:存在分解存在分解 A=（B,N），其中），其中B为为m阶非阶非奇异矩阵，对于奇异矩阵，对于N中的列向量中的列向量 pj 使使 B1pj0,dT=（dBT,dNT）,这里这里 dB=B 1pj,dN=(0,.,1,0)T j S中必存在有限多个极方向中必存在

25、有限多个极方向 (nm)Cnm)。例例2 2 考虑多面体考虑多面体S=x Rn Ax=b,x0，其中其中 3 2 1 0 0 65 A=2 1 0 1 0 b=40 0 3 0 0 1 75 即即 3 x1+2 x2+x3 =65 2 x1+x2 +x4 =40 3 x2 +x5 =75 x1,x2,x3,x4,x5 0 例例 题题 3 2 1 0 0A=（p1,p2,p3,p4,p5）=2 1 0 1 0 0 3 0 0 1 A A矩阵包含以下10个33的子矩阵：B B1=（p p1 1，p p2 2，p p3 3）B B2=（p p1 1 ，p p2 2，p p4 4）B B3=（p p1

26、 1，p p2 2，p p5 5）B B4=（p p1 1，p p3 3，p p4 4）B B5=（p p1 1，p p3 3 ，p p5 5）B B6=（p p1 1，p p4 4，p p5 5）B B7=（p p2 2，p p3 3，p p4 4）B B8=（p p2 2，p p3 3，p p5 5）B B9=（p p2 2，p p4 4 ，p p5 5）B B10=（p p3 3，p p4 4，p p5 5）例例 题题 其中其中 B B4 4=0，因而，因而B B4 4不能构成极点和极方向。其余不能构成极点和极方向。其余均为非奇异方阵，因此该问题共有均为非奇异方阵，因此该问题共有9 9个

27、可构成极点、个可构成极点、极方向的子矩阵，我们称之为基。极方向的子矩阵，我们称之为基。对于基对于基B B3 3=(=(p p1 1 ，p p2 2 ，p p5 5)，令，令x3=0，x4 =0，在等，在等式约束中令式约束中令x3=0，x4=0，解线性方程组解线性方程组 3 x1+2 x2+0 x5 =65 2 x1+x2+0 x5 =40 0 x1+3 x2+x5 =75 得到得到x1=15，x2=10，x5=45，对应的极点对应的极点 x x=(x1，x2，x3，x4，x5)T =(15，10，0，0，45)T例例 题题 类似可得到极点类似可得到极点 x(2)=(5,25,0,5,0)T （

28、对应（对应B2）x(7)=(20,0,5,0,75)T （对应（对应B5）x(8)=(0,25,15,15,0)T（对应对应B7）x(9)=(0,0,65,40,75)T（对应对应B10）而而 x(3)=(0,32.5,0,7.5,22.5)T（对应（对应B9）x(4)=(65/3,0,0,10/3,75)T（对应（对应B6）x(5)=(7.5,25,7.5,0,0)T （对应（对应B1）x(6)=(0,40,15,0,45)T （对应（对应B8）不是极点。不是极点。例例 题题 多面体多面体 S=x Rn Ax=b,x0 的极点和极方向的极点和极方向定理定理7（表示定理）考虑上述多面体（表示定

29、理）考虑上述多面体S，设设A满秩，满秩，x(1),x(2),x(k)为所有极点，为所有极点，d(1),d(2),d(l)为所有极方向。那么，对为所有极方向。那么，对于于 x S，i0，i=1，2，k,且且1+2+k=1,j0,j=1,2,l,使使 x=1 x(1)+2 x(2)+k x(k)+1 d(1)+2 d(2)+l d(l)线线 性性 规规 划划 例例1 1 某工厂拥有某工厂拥有A A、B B、C C 三种类型的设备，三种类型的设备，生产甲、乙两种产品。每件产品在生产中需生产甲、乙两种产品。每件产品在生产中需要占用的设备机时数、每件产品可以获得的要占用的设备机时数、每件产品可以获得的利

30、润以及三种设备可利用的时数如下表所示。利润以及三种设备可利用的时数如下表所示。产品甲产品乙设备能力/h设备A3 32 26565设备B2 21 14040设备C0 03 37575利润/（元/件）1500150025002500 问题：工厂应如何安排生产可获得最大的总利润？解 设变量xi为第i种（甲、乙）产品的生产件数（i1，2）。根据题意，我们知道两种产品的生产受到设备能力（机时数）的限制。对设备A，两种产品生产所占用的机时数不能超过65，于是我们可以得到不等式：3 x1+2 x2 65。对设备B，两种产品生产所占用的机时数不能超过40，于是我们可以得到不等式：2 x1+x2 40。对于设备

31、对于设备C C，两种产品生产所占用的机，两种产品生产所占用的机时数不能超过时数不能超过7575，于是我们可以得到不等式：，于是我们可以得到不等式：3 3x x2 2 75 75；另外，产品数不可能为负，即；另外，产品数不可能为负，即 x x1 1,x,x2 2 0 0。同时，我们有一个追求目标，。同时，我们有一个追求目标，即获取最大利润。于是可写出目标函数即获取最大利润。于是可写出目标函数z z为为相 应 的 生 产 计 划 可 以 获 得 的 总 利 润：相 应 的 生 产 计 划 可 以 获 得 的 总 利 润：z z=1500=1500 x x1 1+2500+2500 x x2 2。综

32、合上述讨论，在加工。综合上述讨论，在加工时间以及利润与产品产量呈线性关系的假设时间以及利润与产品产量呈线性关系的假设下，把目标函数和约束条件放在一起，可以下，把目标函数和约束条件放在一起，可以建立如下线性规划模型：建立如下线性规划模型：目标函数 Max z=1500 x1+2500 x2 约束条件 s.t.3x1+2x2 65 2x1+x2 40 3x2 75 x1,x2 0 这是一个典型的利润最大化的生产计划问题。其中，“Max”是英文单词“Maximize”的缩写，含义为“最大化”；“s.t.”是“subject to”的缩写，表示“满足于”。因此，上述模型的含义是：在给定条件限制下，求使

33、目标函数z达到最大的x1,x2 的取值。一般形式 目标函数：Max(Min)z=c1x1+c2x2+cnxn 约束条件：a11x1+a12x2+a1nxn(=,)b1a21x1+a22x2+a2nxn(=,)b2 .am1x1+am2x2+amnxn(=,)bm x1，x2，xn 0标准形式目标函数：Max z=c1x1+c2x2+cnxn 约束条件：a11x1+a12x2+a1nxn=b1a21x1+a22x2+a2nxn=b2 .am1x1+am2x2+amnxn=bm x1，x2，xn 0 可以看出，线性规划的标准形式有如下四个特点：目标最大化、约束为等式、决策变量均非负、右端项非负。对

34、于各种非标准形式的线性规划问题，我们总可以通过以下变换，将其转化为标准形式。1.极小化目标函数的问题 设目标函数为 Min f=c1x1+c2x2+cnxn 则可以令z -f，该极小化问题与下面的极大化问题有相同的最优解，即 Max z=-c1x1-c2x2-cnxn 但必须注意，尽管以上两个问题的最优解相同，但它们最优解的目标函数值却相差一个符号，即 Min f -Max z 2.约束条件不是等式的问题 设约束条件为 ai1 x1+ai2 x2+ain xn bi 可以引进一个新的变量s，使它等于约束右边与左边之差，即 s=bi(ai1 x1+ai2 x2+ain xn)显然，s 也具有非负

35、约束，即s0，这时新的约束条件成为 ai1 x1+ai2 x2+ain xn+s=bi 当约束条件为 ai1 x1+ai2 x2+ain xn bi 时，类似地令 s=(ai1 x1+ai2 x2+ain xn)-bi 显然，s 也具有非负约束，即s0，这时新的约束条件成为 ai1 x1+ai2 x2+ain xn-s=bi 为了使约束由不等式成为等式而引进的变量s称为“松弛变量”。如果原问题中有若干个非等式约束，则将其转化为标准形式时，必须对各个约束引进不同的松弛变量。例2 将以下线性规划问题转化为标准形式 Min f =3.6 x1-5.2 x2+1.8 x3 s.t.2.3 x1 +5.

36、2 x2-6.1 x3 15.7 4.1 x1 +3.3 x3 8.9 x1+x2+x3 =38 x1,x2,x3 0 解 首先,将目标函数转换成极大化：令 z=-f=-3.6x1+5.2x2-1.8x3 其次考虑约束，有2个不等式约束，引进松弛变量x4，x5 0。于是，我们可以得到以下标准形式的线性规划问题：Max z=-3.6 x1+5.2 x2-1.8 x3s.t.2.3x1+5.2x2-6.1x3+x4=15.7 4.1x1+3.3x3-x5=8.9 x1+x2+x3=38 x1,x2,x3,x4,x5 0 3.变量无符号限制的问题在标准形式中，必须每一个变量均有非负约束。当某一个变量

37、xj没有非负约束时，可以令 xj=xj-xj其中 xj0，xj0即用两个非负变量之差来表示一个无符号限制的变量，当然xj的符号取决于xj和xj的大小。4.右端项有负值的问题 在标准形式中，要求右端项必须每一个分量非负。当某一个右端项系数为负时，如 bi 0,且且 B-1pj0,则则(LP)无有界解无有界解。2.表格单纯形法原理及算法过程表格单纯形法原理及算法过程 Max cTx (LP)s.t.Ax=b x0其中其中,c,x Rn b Rm A 为为 m n 矩阵，秩（矩阵，秩（A）=m 算法过程算法过程(考虑一般步考虑一般步,k=0,1,2,)设设 x(k)为极点为极点,对应分解对应分解 A

38、=（B,N），使），使 xT=（xBT,xNT）,这里这里 xB=B-1b0,xN=0，相应相应 cT=（cBT,cNT）。那么，。那么，（1）若）若 cNT-cBT B-1N0,则则 x(k)opt，停；，停；（2）否则，存在）否则，存在 cj-cBT B-1pj 0,1）若若 B-1pj0,则则(LP)无有界解，停；无有界解，停；2）若存在）若存在(B-1pj)i 0,取取 =min(B-1b)i/(B-1pj)i|(B-1pj)i 0 =(B-1b)r/(B-1pj)r 0.单纯形法原理及算法过程单纯形法原理及算法过程 得到得到 x(k+1)=x(k)+d 是极点是极点其中其中,dT=（

39、dBT,dNT）,这里这里 j dB=-B-1pj,dN=(0,.,1,0)T有有,cTx(k+1)=cTx(k)+cTd =cTx(k)+(cj-cBTB-1pj)cTx(k)所以，所以，x(k+1)比比 x(k)好。好。重复这个过程，直到停机。重复这个过程，直到停机。.单纯形表：单纯形表：设设 x 为初始极点为初始极点,相应分解相应分解 A=（B,N）fxBTxNTRHS目标行目标行1cBTcNT01行行约束行约束行0BNbm行行1列列m列列nm列列1列列作变换，使前作变换，使前m+1列对应的列对应的m+1阶矩阵变为单位矩阶矩阵变为单位矩阵。相当于该表左乘阵。相当于该表左乘1cBT 1 1

40、-cBT B-1 0B 0B-1 =得到得到检验数检验数fxBTxNTRHS目标行目标行10TcNT cBT B-1cBTB-1 b1行行 xB0IB-1NB-1bm行行1列列m列列nm列列1列列为了计算方便，我们对规范形式建立如为了计算方便，我们对规范形式建立如下单纯形表：下单纯形表：（注：引入了注：引入了m个松弛变量个松弛变量）考虑：考虑：bi 0 i=1,m Max z=c1 x1+c2 x2+cn xn s.t.a11 x1+a12 x2+a1n xn b1 a21 x1+a22 x2+a2n xn b2 am1 x1+am2 x2+amn xn bm x1，x2，xn 0 加入松弛变

41、量加入松弛变量 Max z=c1 x1+c2 x2+cn xn s.t.a11 x1+a12 x2+a1n xn+xn+1=b1 a21 x1+a22 x2+a2n xn+xn+2=b2 am1 x1+am2 x2+amn xn+xn+m=bm x1，x2，xn，xn+1，xn+m 0显然，显然，xj=0，j=1,n;xn+i=bi ，i=1,m 是基本可行解。对应的基是单位矩阵。以下是初始单纯形表：m m其中：f=cn+i bi j=cj cn+i aij 为检验数 cn+i=0 i=1,m i=1 i=1 an+i,i=1 ,an+i,j=0(ji)i,j=1,m 利用求解线性规划问题基本

42、可行解（极点）的方法来求解较大规模的问题是不可行的。单纯形法的基本思路是有选择地取基本可行解，即是从可行域的一个极点出发，沿着可行域的边界移到另一个相邻的极点，要求新极点的目标函数值不比原目标函数值差。单单 纯纯 形形 法法初始基本可行解初始基本可行解是否最优解或是否最优解或无限最优解无限最优解?结束结束沿边界找新沿边界找新的基本可行解的基本可行解NY单纯形法的基本过程 例4 用单纯形法的基本思路解前例的线性规划问题 Max z=1500 x1+2500 x2 s.t.3 x1+2 x2+x3=652x1+x2+x4=40 3 x2+x5=75 x1,x2,x3,x4,x5 0最优解最优解x1

43、=5x2=25x4=5（松弛标量，表示（松弛标量，表示B设设备有备有5个机时数的剩余）个机时数的剩余），最优值最优值z*=70000 注意：单纯形法中，注意：单纯形法中，（1）每一步运算只能用矩阵初）每一步运算只能用矩阵初等行变换；等行变换；（2）表中第）表中第3列的数总应保持非列的数总应保持非负（负（0）；）；（3）当所有检验数均非正（）当所有检验数均非正（0）时，得到最优单纯形表。时，得到最优单纯形表。一般情况的处理及注意事项的强调：主要是讨论初始基本可行解不明显时常用的方法。要弄清它的原理，并通过例题掌握这些方法，同时进一步熟悉用单纯形法解题。考虑一般问题：bi 0 i=1,mMax z

44、=c1x1+c2x2+cnxn s.t.a11x1+a12x2+a1nxn=b1 a21x1+a22x2+a2nxn=b2 .am1x1+am2x2+amnxn =bm x1，x2，xn 0大大M M 法法 引入人工变量 xn+i 0（i=1,m）及充分大正数M。得到 MaxMax z=c1x1+c2x2+cnxn-Mxn+1-Mxn+m s.t.s.t.a11x1+a12x2+a1nxn+xn+1 =b1 a21x1+a22x2+a2nxn+xn+2 =b2 .am1x1+am2x2+amnxn+xn+m =bm x1，x2，xn ，xn+1，xn+m 0 0显然显然 x xj j=0=0，

45、j j=1,=1,n n x xn+in+i=b bi i ，i i=1,=1,m m 是基本可行解。是基本可行解。对应的基是单位矩阵。对应的基是单位矩阵。结论：结论：若得到的最优解满足若得到的最优解满足 ：x xn+in+i=0=0，i i=1,=1,m m 则是原问题的最优解；否则，原问题无可行解。则是原问题的最优解；否则，原问题无可行解。3.2 3.2 线性规划的单纯形法线性规划的单纯形法 两阶段法 引入人工变量 xn+i 0，i=1,m；构造:Max z=-xn+1-xn+2-xn+m s.t.a11x1+a12x2+a1nxn+xn+1=b1 a21x1+a22x2+a2nxn+xn

46、+2=b2 .am1x1+am2x2+amnxn+xn+m=bm x1,x2，.xn,xn+1,xn+m 03.2 3.2 线性规划的单纯形法线性规划的单纯形法 第一阶段求解上述问题：第一阶段求解上述问题：显然显然x xj j=0 =0，j j=1,=1,n n;x xn+in+i=b bi i ，i i=1,=1,m m 是基本可行解是基本可行解,它对应的基是单位矩阵。它对应的基是单位矩阵。结论：结论：若得到的最优解满足若得到的最优解满足 x xn n+i i=0=0 i i=1,=1,m m ，则是原问题的基本可则是原问题的基本可行解行解;否则，原问题无可行解。否则，原问题无可行解。得到原

47、问题的基本可行解后，第二得到原问题的基本可行解后，第二阶段求解原问题。阶段求解原问题。3.2 3.2 线性规划的单纯形法线性规划的单纯形法例5（LP）Max z=5x1+2x2+3x3-x4 s.t.x1+2x2+3x3=15 2x1+x2+5x3=20 x1+2x2+4x3 +x4 =26 x1,x2,x3,x4 0 Max z=5x1+2x2+3x3-x4-Mx5-Mx6 s.t.x1+2x2+3x3+x5=15 2x1+x2+5x3+x6=20 x1+2x2+4x3+x4=26 x1,x2,x3,x4,x5,x6 0cB xB 5 2 3-1-M-M i x1 x2 x3 x4 x5 x

48、6-M x5 15 1 2 3 0 1 0 5-M x6 20 2 1(5)0 0 1 4-1 x4 26 1 2 4 1 0 0 6.5-z 35M+26 3M+6 3M+4 8M+7 0 0 0 -M x5 3-1/5(7/5)0 0 1-3/5 15/7 3 x3 4 2/5 1/5 1 0 0 1/5 20-1 x4 10-3/5 6/5 0 1 0-4/5 25/3-z 3M-2-M/5+16/5 7/5M+13/5 0 0 0-8/5M-7/5 2 x2 15/7-1/7 1 0 0 5/7-3/7 3 x3 25/7(3/7)0 1 0-1/7 2/7 25/3-1 x4 52/

49、7-3/7 0 0 1-6/7-2/7 -z -53/7 25/7 0 0 0-M-13/7-M-2/7 2 x2 10/3 0 1 1/3 0 2/3-1/3 5 x1 25/3 1 0 7/3 0-1/3 2/3 -1 x4 11 0 0 1 1-1 0 -z -112/3 0 0-25/3 0-M-2/3-M+8/3 大大M M 法法 （LP-M）得到最优解：(25/3，10/3，0，11)T 最优目标值：112/3 第一阶段问题（LP-1）Max z=-x5-x6 s.t.x1+2x2+3x3+x5 =15 2x1+x2+5x3+x6=20 x1+2x2+4x3 +x4 =26 x1,

50、x2,x3,x4,x5,x6 0cB xB 0 0 0 0-1-1 i x1 x2 x3 x4 x5 x6-1 x5 15 1 2 3 0 1 0 5-1 x6 20 2 1(5)0 0 1 4 0 x4 26 1 2 4 1 0 0 6.5-z 35 3 3 8 0 0 0 -1 x5 3-1/5(7/5)0 0 1-3/5 15/7 0 x3 4 2/5 1/5 1 0 0 1/5 20 0 x4 10-3/5 6/5 0 1 0-4/5 25/3-z 3-1/5 7/5 0 0 0-8/5 0 x2 15/7-1/7 1 0 0 5/7-3/7 0 x3 25/7 3/7 0 1 0-1