《第1章线性规划及单纯形法课件》由会员分享，可在线阅读，更多相关《第1章线性规划及单纯形法课件（87页珍藏版）》请在金锄头文库上搜索。
1、第1章 线性规划及单纯形法 (Linear Programming and Simplex Method),2011-2012 (1),1一般线性规划问题及其数学模型,2图解法,3单纯形法原理,5单纯形法的进一步讨论,7线性规划应用,4单纯形法的计算步骤,6数据包络分析,为了完成一项任务或达到一定的目的，怎样用最少的人力、物力去完成或者用最少的资源去完成较多的任务或达到一定的目的，这个过程就是规划。,例一、有一正方形铁皮，如何截取 x 使容积为最大？,x,a,此为无约束极值问题,（一）、问题的提出,1一般线性规划问题及其数学模型,例二、已知资料如表所示，问如何安排生产才能使利润最大？或如何考虑
2、利润大，产品好销。,模 型,max Z = 2x1 + 3x2,x1 0 , x2 0,s.t.,2x1 + 2x2 12 x1 + 2x2 8 4x1 16 4x2 12,此为带约束的极值问题,问题中总有未知的变量，需要我们去解决。,要求：有目标函数及约束条件，一般有非负条件存在，由此组成规划数学模型。,如果在规划问题的数学模型中，变量是连续的（数值取实数）其目标函数是线性函数（一次方），约束条件是有关变量的线性等式或不等式，这样，规划问题的数学模型是线性的。反之，就是非线性的规划问题。,（二）、数学模型 1、,目标函数：,约束条件：,2、线性规划数学模型的一般形式,也可以记为如下形式：,目
3、标函数：,约束条件：,如将上例用表格表示如下：,设变量,向 量 形 式：,矩阵形式：,3、线性规划的标准形式,一 般 有 两种方法,图 解 法 单纯形法,两个变量、直角坐标 三个变量、立体坐标,适用于任意多个变量、但需将 一般形式变成标准形式,4、线性规划问题的解,（一）求解方法,1、解的概念, 可行解：满足约束条件、的解为可行解。所有解的集合为可行解的集或可行域。, 最优解：使目标函数达到最大值的可行解。, 基：B是矩阵A中mm阶非奇异子矩阵（B0），则B是一个基。,则称 Pj ( j = 1 2 m) 为基向量。 Xj 为基变量，否则为非基变量。,（二）线性规划问题的解, 基本解：满足条件
4、，但不满足条件由基B决定的解.最多为 个。, 基本可行解：满足非负约束条件的基本解，简称基可行解。, 可行基：对应于基可行解的基称为可行基。,非可行解,可 行 解,基解,基可行解,例题 基可行解说明,maxZ=70X1+120X2 P1 P2 P3 P4 P5 9X1+4X2+X3=360 9 4 1 0 0 4X1+5X2 +x4=200 A= 4 5 0 1 0 3X1+10X2+x5 =300 3 10 0 0 1 Xj0 j=1,2,5 这里m=3,n=5。 Cmn=10,基（p3,p4,p5） ，令非基变量x1,x2=0，则基变量x3=360, x4=200, x5=300, 可行解
5、 基（p2,p4,p5）,令非基变量x1=0,x3=0基变量x2=90,x4=250,x5=600. 非可行解 基（ p2,p3,p4 ），令非基变量x1,x5=0，则基变量x2=30, x3=240, x4=50,可行解.,例一、,2 图 解 法,0,1 2 3 4 5 6 7 8,1 2 3 4 5 6,作 图, 最 优 解：x1 = 4 ， x2 = 2,有唯一最优解，Z = 14,x2,x1,(4 2),例二、,例三、,无穷多最优解,无界解,x1,x1,x2,x2,x1,x2,无可行解,例四、,图解法的解题思路和几何上直观得到的一些结论对于求解一般的线性规划有什么启示?,3 单纯形法原
6、理,(1),(2) 几个,1,引理 标准形线性规划问题的可行解X=(x1,x2, ,xn)T为基可行解的充要条件是X的正分量所对应的系数列向量是线性独立的.,定理2 标准形线性规划的基本可行解X对应可行域(凸 集)的顶点(极点).,证明: (1)若X不是基本可行解X不是可行域的顶点.,不失一般性,假设X的前m个分量正,故有,由引理知P1,P2, ,Pm线性相关, 即存在一组不全为零的数,i (i=1,2, m), 使得1P1+ 2P2+ + mPm=0 (2),(1),于是有: (x11) P1+ (x22) P2+ + (xmm) Pm=b (3),其中的选取使得对所有xii0 (i=1,2
7、,m). 由(3)式可知:,X(1) = (x1+1, x2+2, , xm+m, 0, , 0)T,X(2) = (x1-1, x2-2, , xm-m, 0, , 0)T,是线性规划的可行解,即为可行域中的点,但是点,是X(1)和X(2)的凸组合,所以不是极点(顶点).,(2)若X不是可行域的顶点X不是基本可行解.,如果X不是可行域内的点,即X不是可行解,当然X不是基本可行解. 不妨设X是一个可行解,X=(x1, x2, ,xr,0,0)T且,但不是可行域的顶点.由于可行域是凸集, 所以存在两个不同的点Y和Z, 使得X=aY+(1-a)Z, 其中0a1.,当xj=0时, 必有yj=zj=0
8、, 因此,而yj-zj不全为零, 故P1, P2, , Pr线性相关, X不是基本可行解.,定理3 若线性规划有最优解,则一定有最优基本可行解.,证明: 见P20-21,略.,(3) 初始基本可行解的确定,方法一: 对于非标准形线性规划通过引入人工变量法(松驰变量或剩余变量)产生初始的基本可行解;,方法二: 对于标准形线性规划,通过增广矩阵的初等行变换产生一个m阶单位阵, 从而得到一个初始的基本可行解;,方法三: 两阶段法(将在5中讲述).,(4) 初始基本可行解的转换,假设标准形线性规划的系数矩阵的秩为m, 且前m列线性无关, 则线性方程组的增广矩阵通过有限次初等行变换, 前m列可以变换成m
9、阶单位阵:,P1 P2 Pm Pm+1 Pj Pn b,这说明原来的第1,第2,第m列P1 , P2 , Pm 是一个基,非基列,上式两边同乘以一个待确定的正数:,再与式,相加, 得到:,记,如果基本解X0是基本可行解,并希望X(1)也是一个基本可行解,则对所有i=1, 2, , m,且这m个不等式中至,少要有一个等式成立. 如果所有的aij0, 则可以取任意正数, 解无界, 无法构造一个新的基本可行解;只要存在某个aij0, 令,则X(1)中正分量最多m个, P1, , Pl-1, Pl+1, , Pm, Pj线性无关,构成一组新基, 得到新的基本可行解X(1).,(5) 最优基本可行解的判
10、别,记,(检验数),你可以得出什么结论?,结论,1 当所有检验数小于或等于0时,现有基本可行解为最优解;,2 基变量的检验数都等于0;,3 当所有非基变量的检验数小于或等于0, 且某个非基变量xj的检验数等于0、 以xj为进基变量, 求出的0时, 目标函数值不变, 可以得到另一个最优基本可行解，从而该线性规划有无数多个最优解；,4 如果存在某个非基变量对应的检验数j0,且Pj列的分量aij都小于或等于0，则线性规划存在无界解。,5 如果存在某个非基变量对应的检验数j0,且Pj列的分量aij部分为正，则可以确定和旋转主元alj,选择Pj为进基,列, Pl为离基列, 利用矩阵的初等行变换,将alj
11、变成1, Pj列的其它元素变成0, 构造一组新基,求出相应的新的基本可行解.,（一）、基本思想,将模型的一般形式变成标准形式，再根据标准型模型，从可行域中找一个基本可行解，并判断是否是最优。如果是，获得最优解；如果不是，转换到另一个基本可行解，当目标函数达到最大时，得到最优解。,（二）、线性规划模型的标准形式,4 单纯形法的计算步骤,例 一、将下列线性规划问题化为标准形式,为无约束（无非负限制）,解: 用 替换 ，且 ，,将第3个约束方程两边乘以（1）,将极小值问题反号，变为求极大值,标准形式如下：,引入变量,找出一个初始可行解,是否最优,转移到另一个基本可行解,最优解,是,否,循 环,核心是
12、：变量迭代,结束,（三）求解步骤,（四）单纯形表,例 题：,5、单纯形法的进一步讨论,(1) 构造初始基本可行解的大M法,模型1,模型2,(其中M为充分大的正数),定理:,如果,是模型2的最优解,则当Y*=0时, X*一定是模,型1的最优解; 当Y*0时, 模型1没有可行解.,反之,如果X*是模型1的最优解, 则,是模型2的最,优解.,证明:,设,是模型2的最优解, 则,显然,如果X是模型1的可行解, 则(X, 0)T是模型2的可行解.,即X*是模型1的可行解;由于Z*=CX*=CX*-METY*CX-MET0,故X*是模型1的最优解.,如果Y*0,假设模型1有可行解X,则因(X, 0)T是模
13、型2的可行解,则有W*=CX*-METY*CX,对于充分大的M不可能成立! 因此模型1没有可行解.,后一结论比较显然.请同学们自己证明.,(2) 构造初始基本可行解的二阶段法,模型1,模型3,定理:,如果,是模型3的最优基本可行解,则当Y*=0时, X*,一定是模型1的基本可行解; 当Y*0时, 模型1没有可行解.,课堂思考:,1) 该定理与前一定理有何不同?,2) 如何证明?,3) 如何运用该定理求解标准形线性规划?,(3) 求解标准形线性规划的流程,A, b, C,例题,作业,一、问题的提出 实际问题中常常会碰到测定一组同类可比机构综合运作效率的问题，例如，对学校、医院、银行、法院、连锁店
14、等系统内各分支机构部门运作效率的评价。由于测定指标的多样化，所以需要有一种科学的方法能够将各项指标进行综合归纳，避免诸如评分类方法在操作过程中过多的人为因素作用。 DEA（Data Envelopment Analysis）方法采用的是一种相对评价技术，它能够对被测定部门的工作效果度量，从而对系统中参评机构的运作效率评定优劣。,数据包络分析（DEA）,一个评价问题示例,例：某城市有四家综合性医院：中心医院、市立医院、省医院和医大附属医院，现有他们的管理部门要对该四家医院的工作效率进行考评，测定哪家医院效率更高？,评价一个任何一个组织机构的工作效果，通常都是经过对其“输入量”和“输出量”的比较而
15、衡量其运作效率的，并且对“好”、“坏”的认定必须能够确定出一个参照标准，或者是借助于与同类机构的比较分析才能实现，否则，评价无意义。 DEA方法的建模思想就是通过对各机构的输入、输出量的比较分析后，建立一个“较理想”的“复合机构”（高效率）作为评价的标准，将被评机构与该“复合机构”进行对比分析：设定“复合机构”的输出量不小于某一参评机构的输出量，那么它的输入量与该参评机构输入量的比较则可反映被评机构的效率情况。如果“复合机构”用较小的输入量即可获得同样或者较多的输出，则可认定该被评机构是低效的，而按此比值量的大小就可以对各个参评机构的运作效率进行排序。,二、建模思想,Min Z=Ei（i=1,n） 对第i机构评价 ST. wi=1 权重限制 wi OitOit (t=1,T) 输出约束 wiIisEiIis(s=1,S) 输入约束 wi 0，Ei 0 变量符号限制,三、模型结构,i=1,n,n,i=1,n,i=1
