《运筹学》课程授课教案（讲稿）第3讲 单纯形法（1/4）

课程名称：《运筹学》第3讲次授课题目2.4单纯形法（1)本讲目的要求及重点难点：【目的要求】通过本讲课程的学习，了解线性规划问题模型的结构和相关概念、定理。[重点及难点]掌握标准化的方法。内容[本讲课程的引入]图解法虽然直观、简便，但当变量多于三个时，它就无能为力了。所以我们要介绍线性规划问题的单纯形解法，为此先需规定线性规划问题的数学模型的标准形式。[本讲课程的内容]（一）线性规划问题的标准型maxz=clxl + c2x2 + *+cnxnallxl+al2x2+ ... +alnxn= bla21xl+a22x2+...+a2nxn= b2amlxl+am2x2+...+amnxn=bmxl,x2,...xn ≥0简写为：maxz= c,jnnijxj=bii=l,2,,mi=lxj≥0j=l,2,",n在标准型中规定各约束条件的右端项bi≥0，否则等式两端乘以-1

课程名称：《运筹学》 第 3 讲次 授课题目 2.4 单纯形法（1） 本讲目的要求及重点难点： 目的要求] 通过本讲课程的学习，了解线性规划问题模型的结构和相关概念、定理。 [重点及难点] 掌握标准化的方法。 内 容 [本讲课程的引入] 图解法虽然直观、简便，但当变量多于三个时，它就无能为力了。所以我们要介绍 线性规划问题的单纯形解法，为此先需规定线性规划问题的数学模型的标准形式。 [本讲课程的内容] （一）线性规划问题的标准型 max z = c1x1 + c2x2 + . + cnxn a11x1 + a12x2 + . +a1nxn = b1 a21x1 + a22x2 + . +a2nxn = b2 . . . . am1x1 + am2x2 + . +amnxn = bm x1 , x2 , . xn ≥ 0 简写为： max z = ∑ cj xj ∑aijxj = bi i = 1 , 2 , . , m xj ≥0 j = 1 , 2 , . , n 在标准型中规定各约束条件的右端项 bi≥0，否则等式两端乘以-1。 n J=1 J=m+1 n m ( P1 , P2 , . ,Pn ) = a11 a12 . a1n n j=1

内容用向量和矩阵符号表述时为maxz=Cx「n Pjxj = bL J=Ixj ≥00j=1,2,,n其中：C=(cl，c2，cn)X1aljDPj=b=b2X2a2jX=:::bmXnanj用矩阵描述时为：maxz=cxAX = bx ≥0其中：a12..ainanA=(Pi,P2,...,Pn)amlam2amn0=0称A为约束条件的mXn维系数矩阵，一般m0：b为资源向量；C为价值向量：X为决策变量向量。实际中，各种线性规划问题的数学模型都应变换为标准型后求解

内 容 用向量和矩阵符号表述时为： max z = CX ∑ Pjxj = b xj ≥0 j = 1 , 2 , . , n 其中：C = （c1 , c2 , . cn） 用矩阵描述时为： max z = CX AX = b X ≥O 其中： 称 A 为约束条件的 m×n 维系数矩阵，一般 m0 ；b 为资源向量；C 为价值向量； X 为决策变量向量。 实际中，各种线性规划问题的数学模型都应变换为标准型后求解。 n J=1 x1 x2 ┇ xn a1j a2j ┇ anj b1 b2 ┇ bm X = Pj = b = a11 a12 . a1n ┇ ┇ ┇ am1 am2 . amn = ( P1 , P2 , . ,Pn ) O = A = 0 0 ┇ 0

内容变换标准型的步骤：1、若目标函数为实现最小化，即minz=CX，则令z'=-z，于是得到maxz=-CX。2、若约束方程为不等式，有两种情况：一种是约束方程为≤不等式，可在不等式的左端加上一个非负松弛变量，把原不等式变为等式：另一种是约束方程为≥不等式，则可在不等式的左端减去一个非负的剩余变量（也可称松弛变量），把原不等式变为等式。所加松弛变量表示没有被利用的资源，当然也没有利润，在目标函数中系数为零。3、若存在取值无约束的变量xk，可令xk=xk1-xk2，其中xkl ，xk2 ≥ 0。（二）线性规划问题的解的概念可行解满足约束条件的解X=（xl,x2，xn）T，称为线性规划问题的可行解，而使目标函数达到最大值的可行解叫最优解。基设A是约束方程组的mXn维系数矩阵，其秩为m。B是矩阵A中mXm阶非奇异子矩阵（IB≠0），则称B是线性规划问题的一个基。这就是说，矩阵B是由m个线性独立的列向量组成，为不失一般性，可设B=（P1,P2，Pm）。称Pj（j=1，2，，m）为基向量，与之对应的变量xj（j=1，2，，m）为基变量，否则称为非基变量。设约束方程组系数矩阵A的秩为m，因m<n，故它有无穷多解。假设前m个变量的系数列向量线性独立，则：_Pjxj=b-E Pj j基变量XB=（xl,x2，xm）T，令非基变量xm+1=xm+2=.…=xn=0，可以求出一个解X=（xl,x2，xm，0，…，0）T，这个解的非零分量的数目不大于方程个数m，称X为基解。有一个基，就有一个基解。基可行解满足非负条件的基解，称为基可行解。可行基对应于基可行解的基，称为可行基。约束方程组具有基解的数目最多是Cn

内 容 变换标准型的步骤： 1、 若目标函数为实现最小化，即 min z = CX ，则令 z´= -z ， 于是得到 max z´= - CX 。 2、 若约束方程为不等式，有两种情况：一种是约束方程为≤ 不等式，可在不等式的左端加上一个非负松弛变量，把原不等式变为等式；另一种是约束 方程为≥不等式，则可在不等式的左端减去一个非负的剩余变量（也可称松弛变量），把 原不等式变为等式。所加松弛变量表示没有被利用的资源，当然也没有利润，在目标函数 中系数为零。 3、 若存在取值无约束的变量 xk ，可令 xk = xk1 – xk2 ，其中 xk1 ，xk2 ≥ 0。 （二） 线性规划问题的解的概念 可行解 满足约束条件的解 X =（x1 , x2 , . xn）T , 称为线性规划问题的可行解， 而使目标函数达到最大值的可行解叫最优解。 基 设 A 是约束方程组的 m×n 维系数矩阵，其秩为 m。B 是矩阵 A 中 m×m 阶非奇异 子矩阵（|B|≠0），则称 B 是线性规划问题的一个基。这就是说，矩阵 B 是由 m 个线性独 立的列向量组成，为不失一般性，可设 B =（P1 , P2 , . Pm）。 称 Pj（j = 1 ，2 ，. ，m）为基向量，与之对应的变量 xj（j = 1 ，2 ，. ，m） 为基变量，否则称为非基变量。 设约束方程组系数矩阵 A 的秩为 m ，因 m<n ，故它有无穷多解。假设前 m 个变量的 系数列向量线性独立，则： ∑ Pjxj = b - ∑ Pjxj 基变量 XB = （x1 , x2 , . xm）T ，令非基变量 xm+1= xm+2= . = xn=0 ，可以求 出一个解 X=（x1 , x2 , . xm ，0 ，. ，0）T ，这个解的非零分量的数目不大于方程 个数 m ，称 X 为基解。有一个基，就有一个基解。 基可行解 满足非负条件的基解，称为基可行解。 可行基 对应于基可行解的基，称为可行基。约束方程组具有基解的数目最多是 Cn

内容个。一般基可行解的数目要小于基解的数目。如果基解中的非零分量的个数小于m个，这个基解是退化解（三）线性规划问题的几何意义基本概念凸集设K是n维欧氏空间的一点集，若任意两点X1，X2EK，它们连线上的一切点aX1+（1-a）X2EK，（0≤a≤1)：则称K为凸集。顶点设K为凸集，XEK若X不能用不同的两点X1，X2EK的线形组合表示为X=aX1+（1-a）x2，（0<a<1)：则称X为K的一个顶点。基本定理定理1若线性规划问题存在可行域，则其可行域是凸集。引理1线性规划问题的可行解X为基可行解的充要条件是X的正分量所对应的系数列向量是线形独立的。定理2线性规划问题的基可行解对应于可行域的顶点。定理3若可行域有界，线性规划问题的目标函数一定可以在其可行域的顶点上达到最优。另外，若可行域无界，则可能无最优解，也可能有最优解，若有也必定在某顶点上得到。根据以上讨论，可得以下结论：线性规划问题的所有可行解构成的集合是凸集，也可能为无界域，它们有有限个顶点，线性规划问题的每个基可行解对应可行域的一个顶点：若线性规划问题有最优解，必在某顶点上得到。【本讲小结】今天我们学习了线性规划问题模型的结构和相关概念、定理，希望大家重点掌握线性规划的标准化问题。[本讲课程的作业】43页第二题

内 容 个。一般基可行解的数目要小于基解的数目。如果基解中的非零分量的个数小于 m 个，这 个基解是退化解 （三） 线性规划问题的几何意义 基本概念 凸集 设 K 是 n 维欧氏空间的一点集，若任意两点 X1，X2∈K，它们连线上的一切 点αX1+（1-α）X2∈K ，（0≤α≤1）；则称 K 为凸集。 顶点 设 K 为凸集，X∈K；若 X 不能用不同的两点 X1，X2∈K 的线形组合表示为 X=αX1+（1-α）X2 ，（0<α<1）；则称 X 为 K 的一个顶点。 基本定理 定理 1 若线性规划问题存在可行域，则其可行域是凸集。 引理 1 线性规划问题的可行解 X 为基可行解的充要条件是 X 的正分量所对应的系 数列向量是线形独立的。 定理 2 线性规划问题的基可行解对应于可行域的顶点。 定理 3 若可行域有界，线性规划问题的目标函数一定可以在其可行域的顶点上达到 最优。 另外，若可行域无界，则可能无最优解，也可能有最优解，若有也必定在某顶点上得 到。根据以上讨论，可得以下结论： 线性规划问题的所有可行解构成的集合是凸集，也可能为无界域，它们有有限个顶点， 线性规划问题的每个基可行解对应可行域的一个顶点；若线性规划问题有最优解，必在某 顶点上得到。 [本讲小结] 今天我们学习了线性规划问题模型的结构和相关概念、定理，希望大家重点掌握线性 规划的标准化问题。 [本讲课程的作业] 43 页第二题