第1章 线性规划 (2)—03,04,05讲.ppt
第1章 线性规划 (2)—03,04,05讲.ppt
- 配套讲稿：
如PPT文件的首页显示word图标，表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制：
部分文档作品中含有的国旗、国徽等图片，仅作为作品整体效果示例展示，禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词：
- 第1章 线性规划 2—03 04 05讲 03 04 05
- 资源描述：
-
单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,手机：,13551284516,院系：交通与汽车学院，交通运输系,主讲,:,罗 建,运筹学,邮箱：,luo06_jian2000,第,1,章 线性规划,复习,1,、线性规划问题的数学模型包含三个组成要素：,决策变量 目标函数 约束条件,2,、线性规划数学模型的标准型，以及与非标准型的转化。,3,、图解法的一般步骤。,本堂课的主要内容,1,、图解法的几何意义；,2,、单纯形法的概念；,3,、单纯形法的几何语言；,4,、单纯形法的代数形式,5,、单纯型表格。,重点及难点：单纯形表,1,、图解法的几何意义；,凸集,（,Convex set,）,概念：,设,K,是,n,维欧氏空间,的一个点集，若,K,中的任意两点,x,(1),x,(2),的连,线上的一切点,x,仍在,K,中，则称,K,为凸集。,即：,若,K,中的任意两点,x,(1),x,(2),K,，存在,0=,=1,使得,x=,x,(1),+(1-,)x,(2),K,则称,K,为凸集,例（凸集）,例（非凸集）,两个基本概念：,凸组合,(Convex combination),：,设,x,(1),x,(2),.,x,(k,),是,n,维欧氏空间,中的,k,个点，若,存在数,u,1,u,2,.,u,k,且,0u,i,1 (i=1,2,k),u,i,=1,使得,x=u,1,x,(1),+u,2,x,(2),+.+,u,k,x,(k,),成立，则称,x,为,x,(1),x,(2),.,x,(k,),的凸组合,。,两个基本概念：,顶点,：,设,K,是凸集,若,K,中的点,x,不能成为,K,中任何线段上的内点，则称,x,为凸集,K,的顶点。,即：,若,K,中的任意两点,x,(1),x,(2),，不存在数,（,0,0,，转,3,。,3.,换基迭代（基变换）,（,1,）进基：取,对应的,P,k,进基。,（,2,）出基：取,对应的,P,l,进基。,得新基，转,2,。,注：,（,2,）若对一切非基变量有,j,0,，且存在,k,=0,，,则有无穷多解。,的计算,:,X,B,C,B,B,-1,b,x,1,x,2,x,3,x,4,x,5,四、单纯形法的实现,单纯形表,例,：,Max Z=7 x,1,+12x,2,9 x,1,+4x,2,360,4x,1,+5x,2,200,3 x,1,+10 x,2,300,x,1,x,2,0,s.t,.,Max Z=7 x,1,+12x,2,9 x,1,+4x,2,+x,3,=360,4x,1,+5x,2,+x,4,=200,3 x,1,+10 x,2,+x,5,=300,x,1,x,5,0,s.t,.,化为标准型,x,3,x,4,x,5,0,0,0,360,200,300,9,4,3,4,5,10,1,0,0,0,1,0,0,0,1,12,0,0,0,单纯形表,:,7,x,5,x,4,x,3,x,2,x,1,B,-1,b,C,B,X,B,四、单纯形法的实现,单纯形表,例,：煤电油例,Max Z=7 x,1,+12x,2,9 x,1,+4x,2,360,4x,1,+5x,2,200,3 x,1,+10 x,2,300,x,1,x,2,0,s.t,.,Max Z=7 x,1,+12x,2,9 x,1,+4x,2,+x,3,=360,4x,1,+5x,2,+x,4,=200,3 x,1,+10 x,2,+x,5,=300,x,1,x,5,0,s.t,.,化为标准型,x,3,x,4,x,5,0,0,0,360,200,300,9,4,3,4,5,10,1,0,0,0,1,0,0,0,1,12,0,0,0,单纯形表,:,7,90,的计算,:,40,30,x,5,x,4,x,3,x,2,x,1,B,-1,b,C,B,X,B,四、单纯形法的实现,单纯形表,例,：煤电油例,Max Z=7 x,1,+12x,2,9 x,1,+4x,2,360,4x,1,+5x,2,200,3 x,1,+10 x,2,300,x,1,x,2,0,s.t,.,Max Z=7 x,1,+12x,2,9 x,1,+4x,2,+x,3,=360,4x,1,+5x,2,+x,4,=200,3 x,1,+10 x,2,+x,5,=300,x,1,x,5,0,s.t,.,化为标准型,x,3,x,4,x,5,0,0,0,360,200,300,9,4,3,4,5,10,1,0,0,0,1,0,0,0,1,12,0,0,0,单纯形表,:,7,90,40,30,枢纽元素,x,5,x,4,x,3,x,2,x,1,B,-1,b,C,B,X,B,x,3,x,4,x,5,0,0,0,360,200,300,9,4,3,4,5,10,1,0,0,0,1,0,0,0,1,12,0,0,0,单纯形表,:,7,90,40,30,x,3,x,4,x,2,0,0,12,30,0.3,1,0,0,0.1,以,10,为主元进行初等行变换,50,2.5,0,0,1,-0.5,240,7.8,0,1,0,-0.4,3.4,0,0,0,-1.2,或,:,x,5,x,4,x,3,x,2,x,1,B,-1,b,C,B,X,B,x,3,x,4,x,5,0,0,0,360,200,300,9,4,3,4,5,10,1,0,0,0,1,0,0,0,1,12,0,0,0,单纯形表,:,7,90,40,30,x,3,x,4,x,2,0,0,12,30,0.3,1,0,0,0.1,以,10,为主元进行初等行变换,50,2.5,0,0,1,-0.5,240,7.8,0,1,0,-0.4,3.4,0,0,0,-1.2,或,:,30.8,20,100,x,5,x,4,x,3,x,2,x,1,B,-1,b,C,B,X,B,x,3,x,4,x,5,0,0,0,360,200,300,9,4,3,4,5,10,1,0,0,0,1,0,0,0,1,12,0,0,0,单纯形表,:,7,90,40,30,x,3,x,4,x,2,0,0,12,30,0.3,1,0,0,0.1,以,10,为主元进行初等行变换,50,2.5,0,0,1,-0.5,240,7.8,0,1,0,-0.4,3.4,0,0,0,-1.2,30.8,20,100,x,3,x,1,x,2,0,7,12,24,0,1,0,-0.12,0.16,20,1,0,0,0.4,-0.2,84,0,0,1,-3.12,1.16,0,0,0,-1.36,-0.52,x,5,x,4,x,3,x,2,x,1,B,-1,b,C,B,X,B,x,3,x,4,x,5,0,0,0,360,200,300,9,4,3,4,5,10,1,0,0,0,1,0,0,0,1,12,0,0,0,单纯形表,:,7,90,40,30,x,3,x,4,x,2,0,0,12,30,0.3,1,0,0,0.1,50,2.5,0,0,1,-0.5,240,7.8,0,1,0,-0.4,3.4,0,0,0,-1.2,30.8,20,100,以 为主元进行初等行变换,2.5,x,3,x,1,x,2,0,7,12,24,0,1,0,-0.12,0.16,20,1,0,0,0.4,-0.2,84,0,0,1,-3.12,1.16,0,0,0,-1.36,-0.52,x,5,x,4,x,3,x,2,x,1,B,-1,b,C,B,X,B,x,3,x,4,x,5,0,0,0,360,200,300,9,4,3,4,5,10,1,0,0,0,1,0,0,0,1,12,0,0,0,单纯形表,:,7,90,40,30,x,3,x,4,x,2,0,0,12,30,0.3,1,0,0,0.1,50,2.5,0,0,1,-0.5,240,7.8,0,1,0,-0.4,3.4,0,0,0,-1.2,30.8,20,100,X*=(20,24,84,0,0),T,Z*=428,x,3,x,1,x,2,0,7,12,24,0,1,0,-0.12,0.16,20,1,0,0,0.4,-0.2,84,0,0,1,-3.12,1.16,0,0,0,-1.36,-0.52,x,5,x,4,x,3,x,2,x,1,B,-1,b,C,B,X,B,x,3,x,4,x,5,0,0,0,360,200,300,9,4,3,4,5,10,1,0,0,0,1,0,0,0,1,12,0,0,0,单纯形表,:,7,90,40,30,x,3,x,4,x,2,0,0,12,30,0.3,1,0,0,0.1,50,2.5,0,0,1,-0.5,240,7.8,0,1,0,-0.4,3.4,0,0,0,-1.2,30.8,20,100,注：单纯形表中的信息,每一列的含义：,B,-1,(bA)=(B,-1,b,B,-1,P,1,，,B,-1,P,n,),每个表中的,B,和,B,-1,的查找：,B,从初表中找；,B,-1,从当前表中找，对应于初表中的,I,的位置。,以第,2,个表为例：,终表分析,最优基,B*,和,(B*),-1,的查找,x,3,x,1,x,2,0,7,12,24,0,1,0,-0.12,0.16,20,1,0,0,0.4,-0.2,84,0,0,1,-3.12,1.16,0,0,0,-1.36,-0.52,x,5,x,4,x,3,x,2,x,1,B,-1,b,C,B,X,B,x,3,x,4,x,5,0,0,0,360,200,300,9,4,3,4,5,10,1,0,0,0,1,0,0,0,1,12,0,0,0,单纯形表,:,7,90,40,30,x,3,x,4,x,2,0,0,12,30,0.3,1,0,0,0.1,50,2.5,0,0,1,-0.5,240,7.8,0,1,0,-0.4,3.4,0,0,0,-1.2,30.8,20,100,注：单纯形表中的信息,换入基变量中，得到基可行解,定理：,若检验数全小于等于零，且某一个非基变量的检验数为,0,，则线性规划问题有无穷多最优解。（无穷多最优解情况）,证明：,某个非基变量,为最优解。故线性规划问题有无穷多最优解。,为一基可行解，有一个变量,X,m+k,对应,因,为可行解。,定理：,若存在检验数大于零，但所对应的换入变量,X,m+k,的系数向量,P,m+k,0,则原问题无最优解。（,无界解的情况）,证明：,构造一个新的解 ，分量为,定理,：若非基变量检验数严格小于零，则线性规划问题有唯一最优解。,定理,：若检验数全小于等于零，且某一个非基变量的检验数为,0,，则线性规划问题有无穷多最优解。,定理,：,若某一个非基变量的检验数大于,0,，其系数列向量,P,m+k,0,则原问题无最优解。（,无界解的情况）,线性规划为求最大化的标准型：,线性规划为求最小化的标准型时，相应的结果？,定理（求最小化的最优解判别准则）,（,1,）,若,=C-C,B,B,-1,A 0,，,则对应于基,B,的基础可行解,x,就是,基础最优解，此时的可行基就是最优基。,（,2,）,若检验数全大于等于零，且某一个非基变量的检验数为,0,，则线性规划问题有无穷多最优解。,（无穷多最优解情况）,（,3,）若存在检验数小于零，但所对应的换入变量,X,m+k,的系数向量,P,m+k,0,则原问题无最优解。（,无界解的情况）,确定换入变量时，找小于,0,中的最小者。,课堂练习,用单纯形法求解,Min S=-x,1,+2x,2,x,1,-x,2,-2,x,1,+2x,2,6,x,1,x,2,0,s.t,.,化为标准型,Max S,=x,1,-2x,2,-x,1,+x,2,+x,3,=,2,x,1,+2x,2,+x,4,=,6,x,1,x,4,0,s.t,.,X,B,C,B,B,-1,b,x,1,x,2,x,3,x,4,x,3,0,2,-1,1,1,0,不考虑,x,4,0,6,1,2,0,1,6,1,-2,x,3,0,8,0,3,1,1,x,1,1,6,1,2,0,1,0,-4,0,-1,X*=(6,0,8,0),T,Z*=-6,单纯形法的进一步讨论：人工变量法（大,M,法）,当原问题求最大化时，假定人工变量在目标函数中的系数为（,-M,）（,M,为任意大正数），目标函数求最大化，必须把,人工变量从基变量换出,，否则，不可能实现最大化。,当原问题求最小化时，假定人工变量在目标函数中的系数为,M,（,M,为任意大正数），目标函数求最小化，必须把,人工变量从基变量换出,，否则，不可能实现最小化。,Max Z=CX,AX=b,X 0,s.t,.,设问题,(),：,，,A,中不含,I,增加人工变量,X,人,=,（,x,n+1,，,，,x,n+m,）,T,，,X,人,在目标函数中的系数为,-M,（,M,为充分大正数）。,于是原问题化为,(),：,Max Z=CX-M X,人,AX+IX,人,=b,X,X,人,0,s.t,.,1,问题,:,2,方法,:,单纯形法求解,(),若,最优基变量中不含,X,人,，则所得解的前,n,个分量即为,X*,否则，,(),无解。,3,结论,:,例：,用单纯形法求解,Max Z=5x,1,+3x,2,+2x,3,+4x,4,5x,1,+x,2,+x,3,+8x,4,=10,2x,1,+4x,2,+3x,3,+2x,4,=10,x,1,x,2,x,3,x,4,0,s.t,.,解：,增加人工变量,x,5,、,x,6,，则模型化为：,Max Z=5x,1,+3x,2,+2x,3,+4x,4,-Mx,5,-Mx,6,5x,1,+x,2,+x,3,+8x,4,+x,5,=10,2x,1,+4x,2,+3x,3,+2x,4,+x,6,=10,x,1,x,6,0,s.t,.,Max Z=5x,1,+3x,2,+2x,3,+4x,4,-Mx,5,-Mx,6,5x,1,+x,2,+x,3,+8x,4,+x,5,=10,2x,1,+4x,2,+3x,3,+2x,4,+x,6,=10,x,1,x,6,0,s.t,.,X,B,C,B,B,-1,b,x,1,x,2,x,3,x,4,x,5,x,6,5,1,1,8,1,0,2,4,3,2,0,1,x,5,x,6,-M,-M,10,10,5+7M,3+5M,2+4M,4+10M,0,0,5/4,5,0,1,x,5,1,2,3,4,2,0,8,1,1,5,x,6,x,4,x,3,x,2,x,1,B,-1,b,C,B,X,B,x,5,x,6,-M,-M,10,10,5+7M,3+5M,2+4M,4+10M,0,0,5/4,5,x,4,x,6,4,-M,5/4,5/8,1/8,1/8,1,0,15/2,3/4,15/4,11/4,0,1,5/2+3/4M,0,0,5/2+15/4M,3/2+11/4M,10,2,0,1,x,5,1,2,3,4,2,0,8,1,1,5,x,6,x,4,x,3,x,2,x,1,B,-1,b,C,B,X,B,x,5,x,6,-M,-M,10,10,5+7M,3+5M,2+4M,4+10M,0,0,5/4,5,x,4,x,6,4,-M,5/4,5/8,1/8,1/8,1,0,15/2,3/4,15/4,11/4,0,1,5/2+3/4M,0,0,5/2+15/4M,3/2+11/4M,10,2,x,4,x,2,4,3,1,3/5,0,1/30,1,2,1/5,1,11/15,0,2,0,0,-1/3,5/3,10,0,1,x,5,1,2,3,4,2,0,8,1,1,5,x,6,x,4,x,3,x,2,x,1,B,-1,b,C,B,X,B,x,5,x,6,-M,-M,10,10,5+7M,3+5M,2+4M,4+10M,0,0,5/4,5,x,4,x,6,4,-M,5/4,5/8,1/8,1/8,1,0,15/2,3/4,15/4,11/4,0,1,5/2+3/4M,0,0,5/2+15/4M,3/2+11/4M,10,2,x,4,x,2,4,3,1,3/5,0,1/30,1,2,1/5,1,11/15,0,2,0,0,-1/3,5/3,10,x,1,x,2,5,3,5/3,1,0,1/18,5/3,5/3,0,1,13/18,-1/3,0,-10/3,0,-4/9,X*=(5/3,5/3,0,0),T,Z*=40/3,单纯形法总结,1,、,Min,型单纯形表与,Max,型的区别仅在于：,令,k,=,min,j,0,的,x,k,进基，当,0,时最优。,2,、解的几种情况及其在单纯形表上的体现（,讨论,Max,型,）,唯一,最优解,j,0,非基,0,无穷多,最优解,j,0,有非基,k,=0,无界解,有,k,0,但,B,-1,P,k,0,无可行解,用大,M,法求解，最优基中含有,X,人,退化解,有两个或两个以上的,min,线性规划的对偶问题,（,Dual Programming,，简称,DP,）,一、对偶问题的提出和模型,1,、问题的提出,产品组合问题,今有另公司要购买三种资源，至少出价多少，才能使原公司出让资源？,Max Z=3 x,1,+5x,2,x,1,4,2x,2,12,3 x,1,+2x,2,18,x,1,x,2,0,s.t,.,设三种资源价格分别为,y,1,y,2,y,3,Min W=4y,1,+12y,2,+18y,3,s.t,.,y,1,+3y,3,3,2y,2,+2y,3,5,y,1,y,2,y,3,0,y,1,y,2,y,3,收购总价,收购总价,出让生产某产品的资源,消耗的价值不低于该产品,的利润价值,Max Z=3 x,1,+5x,2,x,1,4,2x,2,12,3 x,1,+2x,2,18,x,1,x,2,0,s.t,.,Min W=4y,1,+12y,2,+18y,3,s.t,.,y,1,+3y,3,3,2y,2,+2y,3,5,y,1,y,2,y,3,0,2,、模型,Max Z=CX,AXb,X 0,s.t,.,原问题（,P,）：,对偶问题（,D,）：,Min W=,b,T,Y,A,T,Y C,T,Y 0,s.t,.,Max Z=CX,AXb,X 0,s.t,.,原问题（,P,）：,对偶问题（,D,）：,Min W=,b,T,Y,A,T,Y C,T,Y 0,s.t,.,原问题,对偶问题,目标函数,max,min,目标函数,约束条件,=,变量,无约束,变量符号,无约束,约束条件,=,3,、如何求,LP,模型的对偶问题,（,1,）若,LP,为,Max,型，则尽量化成,(P),形式。,(,等式、自由变量不用转换,),（,2,）若,LP,为,Min,型，则尽量化成,(D),形式。,(,等式、自由变量不用转换,),例：写出下面,LP,的对偶,解：,令,1,、对称性,（,P,）与（,D,）互为对偶,二、对偶性质与定理,2,、弱对偶性,设,X,、,Y,分别为（,P,）、（,D,）的任一可行解，则,证：,X,、,Y,为（,P,）、（,D,）的可行解,5,、对偶定理,若（,P,）有最优解，则（,D,）也有最优解，且二者最优值相等,.,3,、解的最优性,设,、,分别为（,P,）与（,D,）的可行解，且,则,4,、无界性,若（,P,）为无界解，则（,D,）无可行解,若（,D,）为无界解，则（,P,）无可行解,6,、松紧定理（互补松弛性）,设,分别为（,P,）与（,D,）的可行解,例,1.4,讲解，掌握对偶问题的基本性质。,其对偶问题的最优解为,试找出原问题的最优解？,线性规划问题最优解为,用对偶问题求原问题的最优解。,解：标准型为：,对偶问题为：,标准型为：,代入原问题标准型有：,三、对偶问题最优解的经济解释,影子价格,设,DP,其最优值为,Z,*,(,注：与,LP,最优值同），则根据,Z,*,=,b,T,y,*,=b,1,y,1,*,+b,2,y,2,*,+,+,b,m,y,m,*,Z/,b,i,=,y,i,*,简单推导：,Y,*,=(y,1,*,y,2,*,，,y,m,*,）为,DP,的最优解，则,y,i,*,表示,LP,某资源,b,i,变化,1,个单位对目标 产生的影响，称,y,i,*,为,b,i,的,影子价格,。,例、煤电油例的对偶问题的最优解为,Y,*,=(0 1.36 0.52),则煤电油三种资源的影子价格分别为,0,、,1.36,、,0.52,影子价格在管理决策中的作用：,（,1,）影子价格市场价格,若,影子价格市场价格，则应,影子价格市场价格，则应,买进该资源,卖出该资源,（,2,）影子价格反映了资源的稀缺性，影子价格越高，则越稀缺,例如：煤的影子价格为,0,，则表明有剩余,展开阅读全文
咨信网温馨提示：1、咨信平台为文档C2C交易模式，即用户上传的文档直接被用户下载，收益归上传人（含作者）所有；本站仅是提供信息存储空间和展示预览，仅对用户上传内容的表现方式做保护处理，对上载内容不做任何修改或编辑。所展示的作品文档包括内容和图片全部来源于网络用户和作者上传投稿，我们不确定上传用户享有完全著作权，根据《信息网络传播权保护条例》，如果侵犯了您的版权、权益或隐私，请联系我们，核实后会尽快下架及时删除，并可随时和客服了解处理情况，尊重保护知识产权我们共同努力。
2、文档的总页数、文档格式和文档大小以系统显示为准(内容中显示的页数不一定正确)，网站客服只以系统显示的页数、文件格式、文档大小作为仲裁依据，个别因单元格分列造成显示页码不一将协商解决，平台无法对文档的真实性、完整性、权威性、准确性、专业性及其观点立场做任何保证或承诺，下载前须认真查看，确认无误后再购买，务必慎重购买；若有违法违纪将进行移交司法处理，若涉侵权平台将进行基本处罚并下架。
3、本站所有内容均由用户上传，付费前请自行鉴别，如您付费，意味着您已接受本站规则且自行承担风险，本站不进行额外附加服务，虚拟产品一经售出概不退款（未进行购买下载可退充值款），文档一经付费（服务费）、不意味着购买了该文档的版权，仅供个人/单位学习、研究之用，不得用于商业用途，未经授权，严禁复制、发行、汇编、翻译或者网络传播等，侵权必究。
4、如你看到网页展示的文档有www.zixin.com.cn水印，是因预览和防盗链等技术需要对页面进行转换压缩成图而已，我们并不对上传的文档进行任何编辑或修改，文档下载后都不会有水印标识（原文档上传前个别存留的除外），下载后原文更清晰；试题试卷类文档，如果标题没有明确说明有答案则都视为没有答案，请知晓；PPT和DOC文档可被视为“模板”，允许上传人保留章节、目录结构的情况下删减部份的内容；PDF文档不管是原文档转换或图片扫描而得，本站不作要求视为允许，下载前可先查看【教您几个在下载文档中可以更好的避免被坑】。
5、本文档所展示的图片、画像、字体、音乐的版权可能需版权方额外授权，请谨慎使用；网站提供的党政主题相关内容(国旗、国徽、党徽－－等)目的在于配合国家政策宣传，仅限个人学习分享使用，禁止用于任何广告和商用目的。
6、文档遇到问题，请及时联系平台进行协调解决，联系【微信客服】、【QQ客服】，若有其他问题请点击或扫码反馈【服务填表】；文档侵犯商业秘密、侵犯著作权、侵犯人身权等，请点击“【版权申诉】”，意见反馈和侵权处理邮箱：1219186828@qq.com；也可以拔打客服电话：0574-28810668；投诉电话：18658249818。
实名认证
平台协调中心【客服】
自信AI助手
微信客服
客服QQ
发送邮件
意见反馈
链接地址：https://www.zixin.com.cn/doc/13222368.html