运筹学-单纯形原理.pptVIP

主讲教师 季敏,联系电话E-mail: ,清华大学出版社,运筹学教程（第二版）,运筹学基础,胡运权 主编,教材,上堂课回顾,【运筹学】,运用数学方法研究经济、民政和国防等部门在内外环境的约束条件下合理分配人力、物力、财力等资源，使实际系统有效运行的技术科学，它可以用来预测发展趋势，制定行动规划或优选方案。,【解决问题的过程】,1）提出问题，认清问题分析和表述问题 2）问题的抽象建模 3）确定问题的各种方案及确定方案的标准或方法、途径求解和优化 4）评估各个方案，选择最优方案测量模型及对模型进行必要的修正 5）对解进行检验、灵敏性分析等建立对解的有效控制 6）回到实践中方案实施,上堂课回顾,【运筹学的分支】,非线性规划,动态规划,图论与网络分析,存贮论,排队论,对策论,决策论,规划论,多目标规划随机规划 模糊规划等,线性规划,上堂课回顾,1）数学模型的要素,规划问题的数学模型的要素包括： （1）变量，或决策变量，是问题中待确定的未知量； （2）目标函数 它是决策变量的函数。按优化目标有最大化与最小化， 即max或min （3）约束条件，指约束变量取值时受到的各种资源条件的限制。,2）线性规划的特征（含义）,线性规划问题的特征（含义） ： （1）目标函数是决策变量的线性函数 （2）约束条件是含决策变量的线性等式或不等式 实际问题中线性的含义：（1）严格的比例性（正、反比）； （2）可叠加性,上堂课回顾,max（min） z = c1x1 + c2x2 + + cnxn,x1，x2 ， ，xn 0,目标函数,约束条件,一、线性规划的数学模型的表示,上堂课回顾,xj 0 (j=1,2, ,n),st .,aijxj (或=,) bi (i=1,2, ,m),max（min） z =,X 0,st .,CX C=（c1 , c2 , , cn ）,Pjxj (或=,) b,用向量表达,Pj=（a1j , a2j , , amj）-1,b=（b1 , b2 , , bm）-1,简化表示,X=（x1 , x2 , , xn）-1,其中,X 0,st .,AX (或=,) b,用矩阵表达,A=,a11 a12 a1n,a21 a22 a2n,am1 am2 amn,矩阵A称为约束方程组（约束条件）的系数矩阵。,max（min） z =,CX C=（c1 , c2 , , cn ）,上堂课回顾,1）线性规划问题的标准格式,max z =,xj 0 (j=1,2, ,n),st .,cjxj,aijxj = bi (i=1,2, ,m),其中： 1）目标为最大化； 2） bi 为非负数； 3） xj 为非负数； 4）约束为等式。,目标为 最大化,约束为等式,bi 为非负数,xi 为非负数,一个最有代表性的例子,min z = x1 + 2x2 + 3x3,约束条件,-2x1 + x2 + x3 9,-3x1 + x2 + 2x3 4,4x1 - 2x2 - 3x3 = -6,x1 0； x2 0； x3取值无约束,st .,步骤,1）加入松弛变量和剩余变量把 不等式约束变为等式约束；,约束条件,-2x1 + x2 + x3 9,-3x1 + x2 + 2x3 4,4x1 - 2x2 - 3x3 = -6,x1 0；,st .,x2 0；,x3取值无约束,-3x1 + x2 + 2x3 x5 = 4,-2x1 + x2 + x3 + x4 = 9,x4，x5 0；,上堂课回顾,一个最有代表性的例子,min z = x1 + 2x2 + 3x3,约束条件,-2x1 + x2 + x3 9,-3x1 + x2 + 2x3 4,4x1 - 2x2 - 3x3 = -6,x1 0； x2 0； x3取值无约束,st .,1）加入松弛变量和剩余变量把 不等式约束变为等式约束；,约束条件,4x1 - 2x2 - 3x3 = -6,x1 0；,st .,x2 0；,x3取值无约束,-3x1 + x2 + 2x3 x5 = 4,-2x1 + x2 + x3 + x4 = 9,2）把b0加等式约束两边同 乘以-1把b变成0约束；,-4x1 + 2x2 + 3x3 = 6,x4，x5 0；,步骤,上堂课回顾,一个最有代表性的例子,min z = x1 + 2x2 + 3x3,约束条件,-2x1 + x2 + x3 9,-3x1 + x2 + 2x3 4,4x1 - 2x2 - 3x3 = -6,x1 0； x2 0； x3取值无约束,st .,1）加入松弛变量和剩余变量把 不等式约束变为等式约束；,约束条件,x1 0；,st .,x2 0；,x3取值无约束,-3x1 + x2 + 2x3 x5 = 4,-2x1 + x2 + x3 + x4 = 9,2）把b0加等式约束两边同 乘以-1把b变成0约束；,-4x1 + 2x2 + 3x3 = 6,3）变量xi0，令xi/=- xi 此时xi/ 0；,x1/ 0；,4x1/ + 2x2 + 3x3 = 6,3x1/ + x2 + 2x3 x5 = 4,2x1/ + x2 + x3 + x4 = 9,x4，x5 0；,步骤,上堂课回顾,一个最有代表性的例子,min z = x1 + 2x2 + 3x3,约束条件,-2x1 + x2 + x3 9,-3x1 + x2 + 2x3 4,4x1 - 2x2 - 3x3 = -6,x1 0； x2 0； x3取值无约束,st .,1）加入松弛变量和剩余变量把 不等式约束变为等式约束；,约束条件,st .,x2 0；,x3取值无约束,2）把b0加等式约束两边同 乘以-1把b变成0约束；,3）变量xi0，令xi/=- xi 此时xi/ 0；,x4，x5 0；,4）令无约束变量xi=xi/- xi代入 约束条件，xi用xi/， xi代替；,x3/ 0 ， x3 0,4x1/ + 2x2 + 3x3/ - 3x3 = 6,3x1/ + x2 + 2x3/ -2x3 x5 = 4,2x1/ + x2 + x3/ - x3 + x4 = 9,步骤,上堂课回顾,一个最有代表性的例子,min z = x1 + 2x2 + 3x3,约束条件,-2x1 + x2 + x3 9,-3x1 + x2 + 2x3 4,4x1 - 2x2 - 3x3 = -6,x1 0； x2 0； x3取值无约束,st .,1）加入松弛变量和剩余变量把 不等式约束变为等式约束；,约束条件,st .,x2 0；,2）把b0加等式约束两边同 乘以-1把b变成0约束；,3）变量xi0，令xi/=- xi 此时xi/ 0；,x1/ 0；,x4，x5 0；,4）令无约束变量xi=xi/- xi代入 约束条件，xi用xi/， xi代替；,x3/ 0 ， x3 0,4x1/ + 2x2 + 3x3/ - 3x3 = 6,3x1/ + x2 + 2x3/ -2x3 x5 = 4,2x1/ + x2 + x3/ - x3 + x4 = 9,5）如目标为min的，令z/ = -z ， 求z/ 的max。,max z/ = -z = x1/ - 2x2 - 3x3/ + 3x3 + 0x4 - 0x5,步骤,上堂课回顾,上堂课回顾,max z= 2 x1 + x2,可行域,线性规划解的性质,X 0,st.,AX = b,max z =,CX,其中： C=（c1，c2, ,cn) X=（x1，x2, ,xn)T b=（b1，b2, ,bm)T,A=,a11 a12 a1n a11 a12 a1n am1 am2 amn,设Amn中，m，R(A)=m。则我们一定能找出m个线性无关的向量 组B=(P1, P2, ,Pm)，我们称B为该问题的一个基。不妨假设为前m个， 则约束方程组的增广矩阵可以表示成为：,a11 a12 a1m a1,m+1 a1n a21 a22 a2m a2,m+1 a2n am1 am2 amm am,m+1 amn,b1 b2 bm,B-1,我们称一个非负的基解为基可行解，其基为可行基。,线性规划解的性质,X 0,st.,AX = b,max z =,CX,可行解,任意一个维向量X，只要满足线性规划问题的约束条件， 则称该向量为线性规划问题的可行解。,其中： C=（c1，c2, ,cn) X=（x1，x2, ,xn)T b=（b1，b2, ,bm)T,A=,a11 a12 a1n a11 a12 a1n am1 am2 amn,可行域,一个线性规划问题的所有可行解的集合称为该线性规划问题 的可行域， 不妨记为。,最优解,如果一个可行解X*，对任意一个可行解x ，有： CX*Cx ，则称X*为最优解，Z*为最优解的值。换句话 说，最优解就是使目标函数达到最大的可行解。,线性规划解的性质,如果X1、X2为线性规划的两个可行解，则我们可以验证由它们,构造的,= aX1 + (1-a)X2也为该问题的可行解。由此我们可以得到,一个非常有用的结论：任意X1，X2，则当0a1，有 aX1+ (1-a)X2 。,凸集,一个集合A ：任意a1，a2A，则当01，有 a1+ (1- )a2 A ，则称A 为凸集。,线性规划解的性质,正因为线性规划问题的可行域是一个凸集，人们在分析中发现，其最优解总在该集合的某个顶点中出现。该结论正确吗？顶点有何特殊性？,设X为一个凸集，有一个点X3 X ，！X1 X ， X2 X， 使得X3= X1+(1- )X2 (01) 成立，则称X3为凸集X的顶点 。,顶点,线性规划解的性质,几个重要定（引）理献,定理1,若线性规划问题存在可行解，则问题的可行域是凸集。,引理1,线性规划问题的可行解X=(x1,x2,xn)为基可行解的充分必要 条件是X的正分量所对应的系数列向量是线性独立的。,定理2,线性规划问题的基可行解x对应线性规划问题可行域的顶点。,证明方法：反证法,定理3,若线性规划问题有最优解，一定存在一个基可行解是最优解 （线性规划问题的目标函数一定可以在其可行域的顶点上达 到最优）,对于一个线性规划问题：总共基解的个数,引理2,凸集中的任何一点都可由该凸集的顶点凸组合表示出来。,线性规划解的可能情况,1）唯一最优解,3）无可行解,2）无穷多最优解,4）无界解,= aX1 + (1-a)X2，则：,线性规划解的性质,线性规划问题为什么不可能只有有限多个最优解 ？,max z =,X 0,st.,CX,AX = b,AX,= A(aX1 + (1-a)X2),设X1、X2为线性规划的两个最优解，最优值为Z*，0a1的实数，,并有：,= A aX1 + A(1-a)X2,= aAX1 + (1-a)AX2,= b,= ab + (1-a)b,为该问题的可行解,且有C,= C(aX1+(1-a)X2),=CaX1+C(1-a)X2,= aCX1+(1-a)CX2,= aZ*+(1-a)Z*,= Z*,为该问题的最优解,该问题有无限多个最优解,由于a为(0,1) 间任意值,例子,0 5 1 0 0 15,6 2 0 1 0 24,1 1 0 0 1 5,X = (0 0 15 24 5) z = 0,例,max z =,st .,2x1 + 3x2 + x3,x1 + x3 = 5,x1 + 2x2 + x4 = 10,x2 + x5 = 4,x1 -5 0,单纯形法,线性规划问题求解思路,若线性规划问题有最优解，一定存在一个基可行解是最优解,基础知识,例七,x1 + 2x2 + x3 = 8 x1 + x4 = 4 x2 + x5 = 3 -2x1 + x2 + + x6 = 4,X=（0，0，8，4，3，4）,X=（8，0，0，-4，3，20）,X=（4，0，4，0，3，12）,I,变量要求为 非负呢,X=（-2，0，10，6，3，0）,单纯形法,线性规划问题求解过程,相邻基可行解,两个基可行解称为相邻的，如果它们之间变换仅变换一个基 变量。换句话，它们对应的基之间仅有一个列向量不同。,1 0 0 a1m+1 a1k a1n 0 1 0 a2m+1 a2k a2n 0 0 1 amm+1 amk amn,b1 b2 bm,单纯形法,X=（ b1，b2， ，bm ，0， ，0） Z=c1b1+c2b2+cmbm,1 0 0,令：j =bj/ajk,bj- ajkb1 /a1k 0,X=（ 0 ，b2-a2k ， ，bm-amk ，0， , ，0） Z(1)= Z + (ck-(i从1到m)ciaik ), ,单纯形法,重要结论,当所有j0时，此时的基可行解就是最优解。,当所有j0时，且有一个非基变量对应的j=0， 且对应的Pj存在正数分量，则问题有无数个最优解； 否则，当所有j 0时,问题有唯一最优解。,当存在j0，且对应的Pj 0时，问题的解无界。,增广矩阵,单纯形法,单纯形表,1 0 0 a1,m+1 a1k a1n,0 1 0 a2,m+1 a2k a2n,0 0 1 amm+1 amk amn,b1 b2 bm, ,= (1