《运筹学课件第1章线性规划及单纯形法》由会员分享，可在线阅读，更多相关《运筹学课件第1章线性规划及单纯形法（85页珍藏版）》请在金锄头文库上搜索。
1、线性规划带来巨额财富,与其他传统数学学科相比较, 线性规划算是非常年轻却非常实用的一门应用数学。根据二十世纪八十年代的一项调查, 在美国财富杂志(Fortune) 名列前五百名的大公司中, 百分八十五均曾应用线性规划的方法来协助公司的营运。由此可见线性规划应用面的宽广与普及。,第1章 线性规划及单纯形法,1 一般线性规划问题的数学模型 2 图解法 3 单纯形法原理 4 单纯形法的计算步骤 5单纯形法的进一步讨论 6 数据包络分析,主 要 内 容,1 一般线性规划问题的数学模型,问题的提出 线性规划问题的数学模型 线性规划问题的标准形式 线性规划问题的解,常山机器厂生产I、II两种产品，这两种产
2、品都要分别在A、B、C三种不同设备上加工。生产两种产品，已知的条件如下表所示，问该企业应安排生产两种产品各多少件，使总的利润收入为最大。,例1.1 生产计划问题,1-1 问题的提出,问 题 分 析,可控因素(决策变量):,设在计划期内生产I、II两种产品的数量分别为,目标：,达到最大.,使得总利润最大，即利润函数：,受制条件：,计划期内设备的使用量不超过可用量：,设备B：,设备C：,设备A：,模 型,s.t.,1-2 线性规划问题的数学模型,(1) 规划问题的数学模型的3个组成要素：,决策变量、目标函数、约束条件,(2) 线性规划问题的数学模型：,决策变量为可控的连续变量、 目标函数和约束条件
3、关于决策变量都是线性,目标函数,约束条件,(3) 一般线性规划问题的数学模型的表示形式：,以上模型的简写形式,为待定的决策变量,价值系数,矩阵为系数矩阵(或约束矩阵)。,向量表示形式,其中,矩阵表示形式,价值向量,右端向量,(2)化为标准形式的方法,1-3 线性规划问题的标准形式,取极大,bi0,等式约束,非负约束,(1)标准形式,松弛变量,剩余变量,说明：松弛变量和剩余变量在实际问题中分别表示未被利用的资源和超用的资源数，均未转化为价值和利润，所以引进模型后它们在目标函数中的系数均为零。,例1.2 把问题转化为标准形式,1-4 线性规划问题的解,线性规划问题,满足约束条件(2)、(3)的解,
4、可行解(或可行点),可行域,全部可行解的集合,最优解,使目标函数(1)达到最大值的可行解,最优解集合,最优值,最优解的全体,最优解的目标函数值,基,设Amn为约束方程组(2)的系数矩阵(设nm), R(A)=m,B是矩阵A的mm阶的满秩子矩阵，,基向量,基变量,非基变量,基解,不失一般性，设,基B的每一个列向量Pj ( j=1, m),与基向量Pj 对应的变量xj,线性规划中除基变量以外的其他变量,在约束方程组(2)中, 令非基变量xm+1=xn=0,可解出m个基变量的惟一解XB=(x1,xm), X=(x1,xm,0,0)T,基解总数,基可行解,满足变量非负约束条件(3)的基解,可行基,对应
5、于基可行解的基,例1.3 列出下述线性规划问题的全部基、基解、基可行解、最优解,解：,系数矩阵,R(A)=2,-4 5.5 0 0,2/5 0 11/5 0,-1/3 0 0 11/6,0 1/2 2 0,0 -1/2 0 2,0 0 1 1,P1 P2,P1 P3,P1 P4,P2 P3,P2 P4,P3 P4,43/5,5,5,2 图解法,优点： 直观性强、计算方便 缺点：只适用问题中有两个变量的情况 步骤：建立坐标系，将约束条件在图上表示；确立满足约束条件的范围；绘制出目标函数的图形；确定最优解,s.t.,例2.1 用图解法解线性规划,x1,x2,o,B(0,6),A(6,0),2x1+
6、2x2=12,5x2=15,4x1=16,z =9,z =15,z =12,Q1,Q2,Q3,Q4,唯一最优解,线性规划问题解的情况： 无可行解(可行域是空集) 无界解或无最优解(可行域无界) 最优解存在且唯一，则一定在顶点上达到 最优解存在且不唯一(无穷多最优解)，一定存在顶点是最优解,(1)无可行解,s.t.,x1,x2,o,2x1+2x2=12,x1+2x2=14,(2)无界解,s.t.,(3)无穷多最优解,x1,x2,o,4x1=16,s.t.,x2,o,Q1,Q2,Q3,Q4,x1,图解法的启示,(1) 求解线性规划问题时，解的情况有：惟一最优解、无穷多最优解、无界解、无可行解；,(
7、2) 若线性规划问题的可行域存在，则可行域是一个凸集；,(3) 若线性规划问题的最优解存在，则最优解或最优解之一(如果有无穷多的话)一定能够在可行域的某个顶点找到；,(4) 解题思路：先找出凸集的任一顶点，计算在顶点处的目标函数值，比较周围相邻顶点的目标函数值是否比这个值更优，若为否，则该顶点就是最优解的点或最优解的点之一，否则转到比这个点的目标函数值更优的另一顶点重复上述过程，一直到找出使目标函数值达到最优的顶点为止。,内容小结,基本概念,线性规划、可行解、可行域、最优解、最优值、基向量、(非)基变量、基解、可行基,基本计算,把问题转化为标准形式,用图解法解线性规划,3 单纯形法原理,预备知
8、识：凸集和顶点 几个基本定理的证明 确定初始基可行解 从初始基可行解转化为另一基可行解 最优性检验和判别,3-1 预备知识：凸集和顶点,凸集,如果集合C中任意两个点X1、X2，其连线上的所有点也都是集合C中的点，,即对任何,有,顶点X,如果凸集合C中不存在任何两个不同的点X1、X2，使X成为这两个点连线上的一个点，,或,对任何,不存在,3-2 几个基本定理的证明,定理1 若线性规划问题存在可行解，则问题的可行域是凸集。,证明：,设C表示线性规划问题的可行域,则有,令,即,则有,显然,证毕,引理 线性规划问题的可行解X=(x1, xn)T为基可行解的充要条件是X的正分量所对应的系数列向量是线性独
9、立的。,证明：,必要性，由基可行解的定义显然成立。,充分性。,不失一般性不妨,恰好构成一个基，,从而,为相应的基可行解。,则必有,则一定可以从其余列向量中找出m-k个,若X为基解，如何判定是基可行解？ 若X为可行解，如何判定是基可行解？,定理2 线性规划问题的基可行解对应线性规划问题可行域的顶点。,分析：,X是可行域的顶点,X是基可行解,X不是可行域的顶点,X不是基可行解,定理2 线性规划问题的基可行解对应线性规划问题可行域的顶点。,X不是可行域的顶点,(1)X不是基可行解,证明：,使得,得,得,得,X是可行解,所有分量均非负,不失一般性, 不妨设X的前k个分量为正，由X是可行解，得,即存在一
10、组不全为零的数,令,选取适当的 值，使,则,又,即X不是可行域的顶点。,注: 一个线性规划问题,若存在可行解,则至少存在一个基可行解.,从而,由已知得,其不是可行域的顶点.,有,即,因,固有当xi=0时，必有yi= zi=0,得,(2)X不是可行域的顶点,X不是基可行解,不失一般性, 不妨设,因有,因,线性相关,故,不全为零,证毕,X是可行解,所有分量均非负,若线性规划问题有最优解,一定存在一个基可行解是最优解。,定理3,证明：,设,是最优解,是目标函数的最大值。,若X0 只是可行解,非基可行解，,则由定理2得,X0不是可行域的顶点， 从而根据定理2的证明过程可做出两个可行解(即能在可行域内找
11、到通过的X0的直线上的另外两个点）：,而,有,则,由此,从而,若,仍不是基可行解，,按上面的方法继续做下去, 最后一定可以找到一个基可行解, 其目标函数值等于CX0.,注: 一个线性规划问题,若存在可行解,则至少存在一个基可行解.,3-3 确定初始基可行解,由前面的定理可知：如果一个LP问题有最优解，则一定在某个基可行解处达到。单纯形法的基本思想就是先找到一个初始基可行解，判断它是否最优，如若不是，就找一个更好的基可行解，再进行判断。如此迭代下去，直至找到最优基可行解，或者判定该问题无界 ！,一种易求初始基可行解的情形,系数矩阵,化为标准形式,取单位矩阵,作为基，则,就是一个基可行解.,3-4
12、 从初始基可行解转化为另一基可行解,设初始基可行解为, 其中非零坐标有m个. (非退化问题),方程组(*)的增广矩阵可写为,固有,不失一般性, 假定前m个坐标为非零，因,得,由上式知，,满足,或,要使X 1是一个基可行解(最多有m个正分量)，而0,故,同时成立且至少有一个等号成立。,当aij0时，无论 如何取值，都无法使上式等式成立。,故可令,则由上式，知,则X 1中的正分量个数最多有m个，可证,故只需按 来确定的值， X 1就是一个新的基可行解。,线性无关，,线性无关，,线性无关，,当aij0时，无论 如何取值，都无法使上式等式成立。,3-5 最优性检验和解的判别,将基可行解X 0和X 1分
13、别代入目标函数得,通常简写为,检验数,说明：,1)当所有的 j0时, 现有基可行解即为惟一最优解。,2)当所有的 j0, 即对某个非基变量xj有cjzj=0，,且按,可以找到0，,这表明可以找到另一个基可行解使目标函数也达到最大，此时该规划有无穷多最优解。,3)如果存在某个 j0, 又Pj的所有分量aij0, 则对任意,0, 恒有,而取值可无限大，,故目标函数也可无限增大, 此时规划问题有无界解。,4)如果存在某个 j0, 又Pj的某个分量aij0, 则可按前述构造新的基可行解,使目标函数值增大.,在单纯形法的一次迭代过程中,迭代前后的两个基有m-1个相同的列向量，这样的基称为相邻基。在几何上
14、，可以严格证明相邻基所对应的要么是可行域多面凸集的相邻顶点 ，要么是同一顶点（退化时），因此直观地说，单纯形法是从可行域多面凸集的一个顶点迭代到与其相邻的另一个顶点，直至找到最优解或判定问题无界。,内容小结,基本概念,凸集、顶点,基本结论,1)若线性规划问题存在可行解，则可行域是凸集。,2) 可行解X为基可行解 X的正分量所对应的系数列向量是线性独立的。,3) 基可行解对应可行域的顶点。,4) 一定存在一个基可行解是最优解。,4 单纯形法的计算步骤,单纯形法的计算步骤：,step1、求出线性规划的初始基可行解，列出初始单纯形表。,先化成标准形式, 设法使系数矩阵中包含一个单位矩阵, 不妨设此单
15、位矩阵是( P1,P2,Pm ), 以此作为基可得一个初始基可行解X=( b1,b2,bm ).,构造初始单纯形表,cj -zj,基 变 量 对 应 的 价 值 系 数,基 变 量,基 变 量 取 值,所有变量对应的价值系数,所有决策变量,基 向 量 数 字,非 基 向 量 数 字,检验数,Step2 进行最优性检验,若表中所有的 j0, 则表中的基可行解就是问题的最优解，计算结束。否则转下一步。,Step3 基可行解转换，得到新单纯形表。,(1) 确定换入基变量.,对应的变量xk作为换入基的变量.,(2) 确定换出基变量.,xl作为换出基的变量.,alk称为主元素,(3) 生成新的单纯形表,Step4 重复第二、三步一直到计算终止。,s.t.,例1 用单纯形法求解线性规划问题,解：,将上述问题化为标准形式,组成初始基，,得到初始基可行解,初始单纯形表,为入基变量,为出基变量, , ,为入基变量,
