线性规划及单纯形法(新).ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,运筹学,经济学院,1,课堂要求,1.要求同学们上课不迟到，不早退，不得旷课；,2.上课认真听讲，要求每位同学都做笔记；,3.上课不得讲话，看书，玩手机等与课堂无关的内容；,4.课后要求独自完成作业，不得抄袭或不做课后作业。,2,参考资料,1.胡运权主编，运筹学教程（第三版），清华大学出版社；,2.周华任主编，运筹学解题指导，清华大学出版社；,3.运筹学习题集（修订版），清华大学出版社；,4.熊伟编著，运筹学，机械工业出版社；,5.运筹学数据、模型、决策，科学出版社。,3,教学计划,以线性规划和运输问题为讲授重点，其它部分作为选讲内容。,教学方法,以授课为主，案例分析与上机演示为辅。而讲课中主要培养用最优化方法解决实际问题的能力。,教学计划与方法,4,前言运筹学简介,运筹学是管理科学的重要理论基础和应用手段，是管理专业的重要专业基础课程之一。,运筹学根据管理问题的环境条件和决策要求，建立相应的数学模型，利用数学模型对实际问题进行分析和求解，经过分析和比较，得到适合实际问题的方案。,求解结果,.,求解结果,.,建立模型,求解模型,修改,模型,求解结果,.,修改,模型,实际问题,数学模型,5,运筹学是在第二次世界大战中诞生和发展起来的。由于战争的需要，英国和美国招募了一批年轻的科学家和工程师，在军队将军的领导下研究战争中的问题，例如大规模轰炸的效果，搜索和攻击敌军潜水艇的策略，兵力和军需物质的调运等等。这些研究在战争中取得了很好的效果。当时英国把这些研究成为“作战研究”，英文是Operational Research，在美国称为Operations Research。,6,目录：,第一章线性规划及单纯形法,第二章 对偶问题,第三章灵敏度分析,第四章线性规划的建模与应用,第五章 运输问题,9,第一章 线性规划,线性规划问题,线性规划模型,线性规划的图解,可行域的性质,线性规划的基本概念,基础解、基础可行解,单纯形表,10,第1节线性规划问题及其数学模型,生产计划问题,配料问题,背包问题,运输问题,指派问题,1.1问题的提出,11,1.生产计划问题（Production Planning）,产品甲,产品乙,产品丙,产品丁,设备能力（小时）,设备A,1.5,1.0,2.4,1.0,2000,设备B,1.0,5.0,1.0,3.5,8000,设备C,1.5,3.0,3.5,1.0,5000,利润（元/件）,5.24,7.30,8.34,4.18,某工厂拥有A、B、C三种类型的设备，生产甲、乙、丙、丁四种产品。每件产品在生产中需要占有的设备机时数，每件产品可以获得的利润以及三种设备可利用的时数如下表所示：,求使得总利润最大的生产计划。,12,产品甲,产品乙,产品丙,产品丁,设备能力（小时）,设备A,1.5,1.0,2.4,1.0,2000,设备B,1.0,5.0,1.0,3.5,8000,设备C,1.5,3.0,3.5,1.0,5000,利润（元/件）,5.24,7.30,8.34,4.18,设四种产品的产量分别为x,1,，x,2,，x,3,，x,4,，总利润为z，线性规划模型为：,max z=5.24x,1,+7.30 x,2,+8.34x,3,+4.18x,4,s.t.1.5x,1,+1.0 x,2,+2.4x,3,+1.0 x,4,2000,1.0 x,1,+5.0 x,2,+1.0 x,3,+3.5x,4,8000,1.5x,1,+3.0 x,2,+3.5x,3,+1.0 x,4,5000,x,1,x,2,x,3,x,4,0,目标函数,约束条件,变量非负约束,这个问题的最优解为：x,1,=294.12件，x,2,=1500件，x,3,=0，x,4,=58.82件,最大利润为：z=12737.06元。,13,2.配料问题（Material Blending）,某工厂要用四种合金T,1,、T,2,、T,3,、T,4,为原料，经熔炼成为新的不锈钢G。这四种原料含铬（Cr）、锰（Mn）和镍（Ni）的含量（），这四种原料的单价以及新的不锈钢G所要求的Cr、Mn、Ni的最低含量（）如下表：,T,1,T,2,T,3,T,4,G,Cr,3.21,4.53,2.19,1.76,3.20,Mn,2.04,1.12,3.57,4.33,2.10,Ni,5.82,3.06,4.27,2.73,4.30,单价（元/公斤）,115,97,82,76,要求配100公斤不锈钢G，并假定在配制过程中没有损耗。求使得总成本最低的配料方案。,14,T,1,T,2,T,3,T,4,G,Cr,3.21,4.53,2.19,1.76,3.20,Mn,2.04,1.12,3.57,4.33,2.10,Ni,5.82,3.06,4.27,2.73,4.30,单价（元/公斤）,115,97,82,76,min z=115x,1,+97x,2,+82x,3,+76x,4,s.t.3.21x,1,+4.53x,2,+2.19x,3,+1.76x,4,320 Cr的含量下限约束,2.04x,1,+1.12x,2,+3.57x,3,+4.33x,4,210 Mn的含量下限约束,5.82x,1,+3.06x,2,+4.27x,3,+2.73x,4,430 Ni的含量下限约束,x,1,+x,2,+x,3,+x,4,=100 物料平衡约束,x,1,x,2,x,3,x,4,0,设四种原料分别选取x,1,，x,2,，x,3,，x,4,公斤，总成本为z。,这个问题的最优解为：x,1,=26.58,x,2,=31.57,x,3,=41.84，x,4,=0（公斤）,最低成本为z=9549.87元。,问题：如果某一种成分的含量既有下限，又有上限怎么办？,15,3.背包问题（Knapsack Problem）,一只背包最大装载重量为50公斤。现有三种物品，每种物品数量无限。每种物品每件的重量、价格如下表：,物品1,物品2,物品3,重量（公斤/件）,10,41,20,价值（元/件）,17,72,35,求背包中装入每种物品各多少件，使背包中物品总价值最高。,16,设三种物品的件数各为x,1,，x,2,，x,3,件，总价值为z。,max z=17x,1,+72x,2,+35x,3,s.t.10 x,1,+41x,2,+20 x,3,50,x,1,，x,2,，x,3,0 x,1,，x,2,，x,3,为整数,这是一个整数规划问题（Integer Programming）。这个问题的最优解为：,x,1,=1件，x,2,=0件，x,3,=2件，最高价值z=87元,物品1,物品2,物品3,重量（公斤/件）,10,41,20,价值（元/件）,17,72,35,17,4.运输问题（Transportation）,某种物资从两个供应地A,1,，A,2,运往三个需求地B,1,，B,2,，B,3,。各供应地的供应量、各需求地的需求量、每个供应地到每个需求地每吨物资的运输价格如下表：,运价（元/吨）,B,1,B,2,B,3,供应量（吨）,A,1,2,3,5,35,A,2,4,7,8,25,需求量（吨）,10,30,20,60,求总运费最低的运输方案。,18,运价,（元/吨）,B,1,B,2,B,3,供应量（吨）,A,1,2,3,5,35,A,2,4,7,8,25,需求量（吨）,10,30,20,60,A,1,A,2,B,3,B,2,B,1,35吨,25吨,10吨,30吨,20吨,2,3,5,4,7,8,19,运价,（元/吨）,B,1,B,2,B,3,供应量（吨）,A,1,2,3,5,35,A,2,4,7,8,25,需求量（吨）,10,30,20,60,设从两个供应地到三个需求地的运量（吨）如下表：,B,1,B,2,B,3,A,1,x,11,x,12,x,13,A,2,x,21,x,22,x,23,20,运价,（元/吨）,B,1,B,2,B,3,供应量（吨）,A,1,2,3,5,35,A,2,4,7,8,25,需求量（吨）,10,30,20,60,min z=2x,11,+3x,12,+5x,13,+4x,21,+7x,22,+8x,23,s.t.x,11,+x,12,+x,13,=35 供应地A,1,x,21,+x,22,+x,23,=25 供应地A,2,x,11,+x,21,=10 需求地B,1,x,12,+x,22,=30 需求地B,2,x,13,+x,23,=20 需求地B,3,x,11,x,12,x,13,x,21,x,22,x,23,0,21,运量（吨）,B,1,B,2,B,3,供应量（吨）,A,1,30,5,35,A,2,10,15,25,需求量（吨）,10,30,20,60,这个问题的最优解表示如下：,最小总运费为：z=330+55+410+815=275元,A,1,A,2,B,3,B,2,B,1,35吨,25吨,10吨,30吨,20吨,2,3,5,4,7,8,30吨,5吨,10吨,15吨,22,5.指派问题（Assignment Problem）,有n项任务由n个人完成，每项任务交给一个人，每人都有一项任务。由i个人完成j项任务的成本（或效益）为c,ij,。求使总成本最小（或总效益最大）的分配方案。,设：,23,张、王、李、赵四位老师被分配教语文、数学、物理化学四门课程，每位老师教一门课，每门课由一位老师教。根据这四位老师以往教课的情况，他们分别教四这门课程的平均成绩如下表。要求确定哪一位老师上哪一门课，使四门课的平均总成绩最高。,语文,数学,物理,化学,张,92,68,85,76,王,82,91,77,63,李,83,90,74,65,赵,93,61,83,75,24,设：,语文,数学,物理,化学,张,x,11,x,12,x,13,x,14,王,x,21,x,22,x,23,x,24,李,x,31,x,32,x,33,x,34,赵,x,41,x,42,x,43,x,44,max z=92x,11,+68x,12,+85x,13,+76x,14,+82x,21,+91x,22,+77x,23,+63x,24,+,83x,31,+90 x,32,+74x,33,+65x,34,+93x,41,+61x,42,+83x,43,+75x,44,s.t.x,11,+x,12,+x,13,+x,14,=1 (1),x,21,+x,22,+x,23,+x,24,=1 (2),x,31,+x,32,+x,33,+x,34,=1 (3),x,41,+x,42,+x,43,+x,44,=1 (4),x,11,+x,21,+x,31,+x,41,=1 (5),x,12,+x,22,+x,32,+x,42,=1 (6),x,13,+x,23,+x,33,+x,43,=1 (7),x,14,+x,24,+x,34,+x,44,=1 (8),x,ij,=0,1,25,最优解为：x,14,=1，x,23,=1，x,32,=1，x,41,=1，max z=336,即张老师教化学，王老师教语文，李老师教数学，赵老师教语文。,语文,数学,物理,化学,张,0,0,0,1,王,0,0,1,0,李,0,1,0,0,赵,1,0,0,0,语文,数学,物理,化学,张,92,68,85,76,王,82,91,77,63,李,83,90,74,65,赵,93,61,83,75,四门课的总分可以达到336分。,26,线性规划模型,min(max)z=c,1,x,1,+c,2,x,2,+c,n,x,n,s.t.a,11,x,1,+a,12,x,2,+a,1n,x,n,(,)b,1,a,21,x,1,+a,22,x,2,+a,2n,x,n,(,)b,2,a,m1,x,1,+a,m2,x,2,+a,mn,x,n,(,)b,m,x,1,x,2,x,n,0(,Free),线性规划模型的目标函数必须是变量的线性函数，约束条件必须是变量的线性等式或不等式。如右的问题就不是线性规划问题：,27,1.2线性规划的标准形式,目标函数为极大化，约束条件全部为等号约束，右端常数项均为非负，所有变量全部是非负的，这样的线性规划模型称为标准形式,maxz=c,1,x,1,+c,2,x,2,+c,n,x,n,s.t.a,11,x,1,+a,12,x,2,+a,1n,x,n,b,1,a,21,x,1,+a,22,x,2,+a,2n,x,n,b,2,a,m1,x,1,+a,m2,x,2,+a,mn,x,n,b,m,x,1,x,2,x,n,0,28,线性规划模型用矩阵和向量表示,max z=c,1,x,1,+c,2,x,2,+c,n,x,n,s.t.a,11,x,1,+a,12,x,2,+a,1n,x,n,b,1,a,21,x,1,+a,22,x,2,+a,2n,x,n,b,2,a,m1,x,1,+a,m2,x,2,+a,mn,x,n,b,m,x,1,x,2,x,n,0,29,线性规划模型用矩阵和向量表示（续）,因此，线性规划模型可以写成如下矩阵和向量的形式,MaxZ =C,T,X,s.t.AX=b,X,0,30,线性规划模型总结,线性规划模型的结构,目标函数：,max,，,min,约束条件：,=,变量符号：,0,0,Free,线性规划的标准形式,目标函数：,max,约束条件：,=,右端常数项：,0,变量符号：,0,MaxZ =C,T,X,s.t.AX=b,X,0,31,线性规划问题的标准化,极小化目标函数转化为极大化,小于等于约束条件转化为等号约束,大于等于约束条件转化为等号约束,右端常数项小于等于,0,的标准化,变量小于等于,0,的标准化,变量没有符号限制（,Free,）,的标准化,32,非标准形式如何化为标准,1),Min型化为Max型,加负号,因为，求一个函数,的极小点，等价于求该,函数的负函数的极大点。,注意：Min型化为Max型求解后，最优解不变，但最优值差负号。,33,min z=2x,1,-3x,2,+x,3,令 z=-z，z=-2x,1,+3x,2,-x,3,新的目标函数,max z=-2x,1,+3x,2,-x,3,取得极大化的最优解时，这个最优解同时使原目标函数值取得最小化的最优解。但两个问题最优解的目标函数值相差一个负号。,极小化目标函数问题转化为极大化目标函数,34,例如，对于以下两个线性规划问题,min z=2x,1,+3x,2,s.t.x,1,+x,2,3,x,2,1 (A),x,1,x,2,0,max z=-2x,1,-3x,2,s.t.x,1,+x,2,3,x,2,1 (B),x,1,x,2,0,它们的最优解都是x,1,=2,x,2,=1，但(A)的最小化的目标函数值为min z=7，(B)的最大化的目标函数值为max z=-7,35,2),不等式约束化为等式约束,分析：,以下面约束为例,之所以“不等”是因为左右两边有一个差额，称为“松,弛量”，若在左边加上这个松弛量，则化为等式。而这,个松弛量也是变量，记为,，则有,称为松弛变量。问题：,它的实际意义是什么？,资源的“剩余”。,36,2x,1,+3x,2,-4x,3,5,引进松弛变量(Slack variable)x,4,=5-(2x,1,+3x,2,-4x,3,)，把松弛变量x,4,加在约束条件左边，就可以将小于等于约束变为等式。,2x,1,+3x,2,-4x,3,+x,4,=5,由此可以知道，松弛变量x,4,0。如果有一个以上小于等于约束，要对于每一个约束引进不同的松弛变量。例如：,2x,1,+3x,2,-4x,3,5,3x,1,-2x,2,+5x,3,8,在两个约束中分别引进松弛变量x,4,，x,5,0,2x,1,+3x,2,-4x,3,+x,4,=5,3x,1,-2x,2,+5x,3,+x,5,=8,小于等于约束条件转化为等号约束,37,将不等式约束变为等式约束。例如：,2x,1,+3x,2,-4x,3,5,3x,1,-2x,2,+5x,3,8,在两个约束的左边分别减去剩余变量x,4,，x,5,0,2x,1,+3x,2,-4x,3,-x,4,=5,3x,1,-2x,2,+5x,3,-x,5,=8,大于等于约束条件转化为等号约束,38,练习：请将下列约束化为标准型,解：增加松弛变量,则约束化为,易见，增加的松弛变量的系数恰构成一个单位阵I。,39,一般地，记松弛变量的向量为,X,s,，则,问题：松弛变量在目标中的系数为何？,0。,3),当模型中有某变量,x,k,没有非负要求，,称,为自由变量,则可令,化为标准型。,40,没有符号限制的变量，用两个非负变量之差表示。例如：,min z=x,1,+2x,2,-3x,3,s.t.2x,1,+3x,2,-4x,3,5,3x,1,-2x,2,+5x,3,8,x,1,0,x,2,:free,x,3,0,先将目标函数转化为极大化，并在约束中引进松弛变量，把不等式约束变为等式。,Max z=-x,1,-2x,2,+3x,3,s.t.2x,1,+3x,2,-4x,3,+x,4,=5,3x,1,-2x,2,+5x,3,-x,5,=8,x,1,0,x,2,:free,x,3,x,4,x,5,0,变量没有符号限制(Free)的标准化,41,Max z=-x,1,-2x,2,+3x,3,s.t.2x,1,+3x,2,-4x,3,+x,4,=5,3x,1,-2x,2,+5x,3,-x,5,=8,x,1,0,x,2,:free,x,3,x,4,x,5,0,然后，令x,2,=x,2,-x,2,”，其中x,2,x,2,”0。代入模型，消去x,2,Max z=-x,1,-2(x,2,-x”,2,)+3x,3,s.t.2x,1,+3(x,2,-x”,2,)-4x,3,+x,4,=5,3x,1,-2(x,2,-x”,2,)+5x,3,-x,5,=8,x,1,x,2,x”,2,x,3,x,4,x,5,0,整理，得到标准形式：,Max z=-x,1,-2x,2,+x”,2,+3x,3,s.t.2x,1,+3x,2,-3x”,2,-4x,3,+x,4,=5,3x,1,-2x,2,+2x”,2,+5x,3,-x,5,=8,x,1,x,2,x”,2,x,3,x,4,x,5,0,42,4）右端常数项小于等于0的标准化,当右端常数项为小于等于0时，如：,2x,1,-3x,2,+4x,3,-4,只需不等式两边同乘以-1，不等式改好就可以了,-2x,1,+3x,2,-4x,3,4,43,min z=x,1,+2x,2,-3x,3,s.t.2x,1,+3x,2,-4x,3,5,3x,1,-2x,2,+5x,3,8,x,1,0,x,2,0,x,3,0,max z=-x,1,-2x,2,+3x,3,s.t.2x,1,+3x,2,-4x,3,+x,4,=5,3x,1,-2x,2,+5x,3,-x,5,=8,x,1,0,x,2,0,x,3,x,4,x,5,0,令 x,2,=-x,2,，x,2,0,代入模型,max z=-x,1,+2x,2,+3x,3,s.t.2x,1,-3x,2,-4x,3,+x,4,=5,3x,1,+2x,2,+5x,3,-x,5,=8,x,1,0,x,2,0,x,3,x,4,x,5,0,5）变量小于等于0的的标准化,44,练习：,min z=2x,1,-x,2,+4x,3,s.t.x,1,+x,2,-x,3,3,3x,1,-x,2,+2x,3,6,x,1,-3x,2,-4x,3,-4,x,1,0,x,3,0,45,1.3线性规划问题解的概念,设线性规划,46,举例：,1.maxZ=8x,1,+10 x,2,2x,1,+x,2,11,x,1,+2x,2,10,x,1,x,2,0,确定下列向量中哪些是解？可行解？,求出可行域。,47,基本概念,（1）可行解与最优解,直观上，,可行解是可行域中的点，是一个可行的方案；,最优解是可行域的角点，是一个最优的方案。,48,1.4 图解法：,对于模型中只有两个变量的线性规划问题，可以通过在平面上作图的方法求解。,一个线性规划问题有解，是指能找出一组x,j,(j=1,2,n)，满足约束条件，称这组x,j,为问题的可行解。,通常线性规划问题总是含有多个可行解，称全部可行解的集合为可行域，可行域中使目标函数为最优的可行解为最优解。,图解法的目的是判别线性规划问题的求解结局和存在最优解的条件下求出最优解。,49,图解法的步骤,1.建立具有合适刻度单位的坐标系统；,2.对每一约束条件建立直线，从而确定可行域；,3.确定目标函数等值线的移动方向；,4.求出最优解：最优解为等值线在移动过程中与可行域的最后交点。,50,线性规划的图解,max z=x,1,+3x,2,s.t.x,1,+x,2,6,-x,1,+2x,2,8,x,1,0,x,2,0,可行域,目标函数等值线,最优解,6,5,4,3,2,1,1 2 3 4 5 6,-8 -7 -6 -5 -4 -3-2 -1 0,x,1,x,2,z=6,z=3,z=9,z=12,问题：1、线性规划的最优解是否可能位于可行域的内部？,2、线性规划的最优解是否可能位于可行域的边界上？,51,举例：,1.maxZ=2x,1,+x,2,5x,2,15,6x,1,+2x,2,24,x,1,+x,2,5,x,1,x,2,0,唯一最优解,2.maxZ=x,1,+x,2,-2x,1,+x,2,4,x,1,-x,2,2,x,1,x,2,0,无界解,3.maxZ=3x,1,+9x,2,x,1,+3x,2,22,-x,1,+x,2,4,x,1,x,2,0,无穷多最优解,4.maxZ=x,1,+x,2,x,1,+x,2,1,2x,1,+2x,2,4,x,1,x,2,0,无解,52,线性规划可行域和最优解的几种情况,1、可行域封闭,唯一最优解,2、可行域封闭,多个最优解,3、可行域开放,唯一最优解,4、可行域开放,多个最优解,5、可行域开放,目标函数无界,6、无可行解,53,标准化的线性规划问题，有n个变量，m个约束。,maxz=c,1,x,1,+c,2,x,2,+c,n,x,n,s.t.a,11,x,1,+a,12,x,2,+a,1n,x,n,b,1,a,21,x,1,+a,22,x,2,+a,2n,x,n,b,2,a,m1,x1+a,m2,x,2,+a,mn,x,n,b,m,x,1,x,2,x,n,0,如果,m,个变量的系数矩阵的行列式不等于,0,，这个,mm,的矩阵称为线性规划的一个,基,。其余的,n-m,个变量称为,非基变量,，,m,个变量称为,基变量,。,1.5线性规划的基本概念基、基解、基可行解、极点,54,求解mm的线性方程组，得到基变量的一组解，连同等于0的非基变量这n个变量的值称为线性规划的一个,基解,。,如果一个基解中的所有变量都是非负的，这个基解称为,基可行解,。,线性规划的基可行解就是可行域的,极点,。,55,基矩阵与基变量,基矩阵(简称基)：,系数阵,A,中的,m,阶可逆子阵，记,为,B,；其余部分称为非基矩阵，记为,N。,基向量：,基,B,中的列；其余称非基向量。,基变量：,与基向量,P,j,对应的决策变量,x,j,，,记其组成的,向量为,X,B,；与非基向量对应的变量称非基变,量，记其组成的向量为,X,N,。,56,6个。,一般地，,m,n,阶矩阵,A,中基的个数最多有多少个？,问题：本例的A中一共有几个基？,57,基本解与基本可行解,可见：一个基本解是由一个基决定的。,注意：基本解仅是资源约束的解，并未要求其非负，因此其未必可行。,称非负的基本解为,基本可行解,（简称基可行解）。,58,例4：在上例中,求相应于基,B,1,和,B,2,的基本解，它们是否基本可行解？,59,上二组概念间的联系：,系数阵,A,中可找出若干个基,B,每个基,B,都对应于一个基本解,非负的基本解就是基本可行解,几种解之间的关系：,可行解,基本解,非可行解,基本可行解,问题：基本可行解是可行域中的哪些点？,60,1.找出下述线性规划问题的全部基解，指出其中的基可行解，并确定最优解。,maxZ=2x,1,+3x,2,x,1,+x,3,5,x,1,+2x,2,+x,4,10,x,2,+,x,5,4,x,i,0,61,解：,x,1,x,2,x,3,x,4,x,5,Z,是否为基可行解,1,0,0,5,10,4,5,2,0,4,5,2,0,17,3,5,0,0,5,4,10,4,0,5,5,0,1,20,5,10,0,5,0,4,15,6,5,2.5,0,0,1.5,17.5,7,5,4,0,3,0,22,8,2,4,3,0,0,19,最优解为x1 2，x24，x3 3，Z19,62,1.6 解的可行性和松弛变量符号的关系,A(1,2.5),B(2,1),C(1.5,3),max z=2x,1,+3x,2,s.t.x,1,+x,2,4 (1),-x,1,+x,2,1 (2),x,1,x,2,0,max z=2x,1,+3x,2,s.t.x,1,+x,2,+x,3,=4,-x,1,+x,2,-x,4,=1,x,1,x,2,x,3,x,4,0,引进松,弛变量,约束条件(1),约束条件(2),D(3,2),A(1,2.5)满足所有约束条件，x,3,=0.5,x,4,=0.5,B(2,1)满足(1)，不满足(2)，x,3,=1,x,4,=-2,C(1.5,3)不满足(1),满足(2)，x,3,=-0.5,x,4,=0.5,D(3,2)不满足(1)和(2)，x,3,=-1,x,4,=-2,结论：如果一个解满足一个约束条件，相应的松弛变量大于等于0。如果一个解不满足一个约束条件，相应的松弛变量小于0。,0 1 2 3 4,-1,4,3,2,1,x,2,x,1,63,max z=x,1,+2x,2,s.t.x,1,+x,2,3,x,2,1,x,1,x,2,0,max z=x,1,+2x,2,s.t.x,1,+x,2,+x,3,=,3,x,2,+x,4,=,1,x,1,x,2,x,3,x,4,0,x,1,=0,x,2,=0 x,3,=3,x,4,=1,基可行解,x,1,=0,x,4,=0 x,2,=1,x,3,=2,基可行解,x,2,=0,x,3,=0 x,1,=3,x,4,=1,基可行解,x,3,=0,x,4,=0 x,1,=2,x,2,=1,基可行解,x,1,=0,x,3,=0 x,2,=3,x,4,=-2,是基解，但不是可行解,O,A,B,x,3,=0,x,4,=0,x,2,=0,x,1,=0,C,D,可行域,64,第2节 线性规划问题的几何意义,1.凸集,如果集合C中任意两点x,1,，x,2,，其连线上的所有点也都是集合C中的点，则称C为凸集，其中x,1,，x,2,的连线可以表示为：,x,1,（1,）x,2,(0,1),数学解析式为：,x,1,C，,x,2,C，,有,x,1,（1,）x,2,C,(0,1)，则C为凸集。,2.1基本概念,65,2.极点,如果集合C中任意两点x,1,，x,2,，使x为这两点连线上的一个点，对任何x,1,C，,x,2,C，不存在,x=,x,1,（1,）x,2,(0,1),，则称x为凸集的顶点。,3.凸组合P16,66,2.2 几个基本定理,定理1：若线性规划问题存在可行解，则问题的可行域是凸集,引理：线性规划问题的可行解X(x,1,x,2,x,n,)为基可行解的充要条件是X的正分量所对应的系数列向量是线性独立的（所组成的矩阵是非奇异的）。,定理2：线性规划问题的基可行解X对应线性规划问题可行域的顶点。,定理3：若线性规划问题有最优解，一定存在一个基可行解是最优解。,67,第3节 单纯形法,maxZ=6x,1,+5x,2,x,1,+3x,2,90,2x,1,+x,2,75,2x,1,+2x,2,80,x,1,x,2,0,maxZ=6x,1,+5x,2,x,1,+3x,2,+x,3,90,2x,1,+x,2,+x,4,75,2x,1,+2x,2,+x580,x,i,0,找一个基可行解，X（0，0，90，75，80），Z=0,1）Z6x,1,+5x,2,，x,1,的系数C,1,6大于C,2,=5；选择x,1,为新的基变量。,X,3,=90-(x,1,+3x,2,)当x,3,=0，X,2,=0时，x,1,=90 选择x,4,为,X,4,=75-(2x,1,+x,2,)当x,4,=0，X,2,=0时，x,1,=37.5 换出变量，,X,5,=80-(2x,1,+2x,2,)当x,5,=0，X,2,=0时，x,1,=40 即x,4,0,最小,3.1举例,68,3）Z225+2x,2,-3x,4,，x2的系数C,2,2大于0；选择x,2,为新的基变量。,X,3,=52.5-(2.5x,2,-0.5x,4,)当x,3,=0，x,4,=0时，x,2,=21,X,1,=75/2-(0.5x,2,+0.5x,4,)当x,1,=0，x,4,=0时，x,2,=75,X,5,=5-(x,2,-x,4,)当x,5,=0，x,4,=0时，x,2,=5,所以选择x,5,为换出变量,x,2,为换入变量,最小,则X（37.5，0，52.5，0，5）,T,，Z2252X,2,-3X,4,2）仍然用非基变量表示基变量,X,3,=52.5-(2.5x,2,-0.5x,4,),X,1,=75/2-(0.5x,2,+0.5x,4,),X,5,=5-(x,2,-x,4,),Z225+2x,2,-3x,4,69,4)用非基变量表示基变量,X,3,=40-(1.5x,4,-2.5x,5,),X,1,=35-(x,4,-0.5x,5,),X,2,=5-(x,5,-x,4,),Z235-x,4,-2x,5,则X（35，5，40，0，0）,T,，Z235-x,4,-2x,5,为最优解,70,（1）线性规划模型为标准形式,（2）约束条件系数矩阵中至少有一个单位子矩阵,（3）目标函数中不含基变量,这样的线性规划模型称为规范型,71,线性规划基本概念练习（1）,0,3,6,x,1,x,2,O,A,B,C,E,F,G,H,I,4,6,-2,min z=-x,1,+2x,2,s.t.3x,1,+2x,2,12(1),x,1,+2x,2,6(2),-2x,1,+x,2,4(3),x,1,x,2,0,1、约束条件（1）对应的直线是（），对应的半平面是,约束条件（2）对应的直线是（），对应的半平面是,约束条件（3）对应的直线是（），对应的半平面是,2、这个线性规划的可行域是（）。,3、对于z=2和4,分别画出目标函数等值线。,4、这个线性规划的最优解位于（）。,ACEF,BCDH,EGHI,CDGE,z=2,z=4,C,D,4,72,1.确定初始基可行解,由于基可行解是由一个可行基决定的，因此，确定初始基可行解,X,0,相当于确定一个初始可行基,B,0,。,方法：,若,A,中含,I,，则,B,0,=,I,；,若,A,中不含,I,，则可用人工变量法构,造一个,I,。,问题：若,B,0,=I，则,X,0,=？,3.2单纯形法的步骤,73,2.最优性检验,问题：用什么检验？,目标。,问题：非最优的特征为何？,74,3.寻找更好的基可行解,由于基可行解与基对应，即寻找一个新的基可行解，相当于从上一个基,B,0,变换为下一个新的基,B,1,，因,此，本步骤也称为基变换。,（基变换）,进基,出基,75,4.迭代,76,以下面模型为例，可按上述单纯形法的步骤求出其最优解，其大致的过程如下。,（1）先将模型化为标准型,(2)确定初始基可行解、检验,77,（3）换基、计算下一个基可行解、再检验，直至最优,问题：当模型规模较大时，计算量很大。,事实上，单纯形法的实现是在单纯形表上完成的。,78,第4节单纯形法的计算步骤单纯形表,单纯形表是基于单纯形法的步骤设计的计算格式，是单纯形法的具体实现。,回顾单纯形法步骤,79,单纯形表的主要结构：,问题：第一张表的,B,-1,=？,单位阵,I,。,检验数的公式是什么？,80,单纯形表求解线性规划问题,maxZ=6x,1,+5x,2,x,1,+3x,2,90,2x,1,+x,2,75,2x,1,+2x,2,80,x,1,x,2,0,maxZ=6x,1,+5x,2,x,1,+3x,2,+x,3,90,2x,1,+x,2,+x,4,75,2x,1,+2x,2,+x580,x,i,0,81,c,j,6,5,0,0,0,C,B,X,B,b,x,1,x,2,x,3,x,4,x,5,0,x,3,90,1,3,1,0,0,0,x,4,75,2,1,0,1,0,0,x,5,80,2,2,0,0,1,c,j,-z,j,6,5,0,0,0,82,c,j,6,5,0,0,0,C,B,X,B,b,x,1,x,2,x,3,x,4,x,5,0,x,3,90,1,3,1,0,0,0,x,4,75,2,1,0,1,0,0,x,5,80,2,2,0,0,1,c,j,-z,j,6,5,0,0,0,83,c,j,6,5,0,0,0,C,B,X,B,b,x,1,x,2,x,3,x,4,x,5,0,x,3,90,1,3,1,0,0,90/1,0,x,4,75,2,1,0,1,0,75/2,0,x,5,80,2,2,0,0,1,80/2,c,j,-z,j,6,5,0,0,0,所以把x,4,换出为非基变量，x,1,为换入变量即新的基变量。,84,c,j,6,5,0,0,0,C,B,X,B,b,x,1,x,2,x,3,x,4,x,5,0,x,3,90,1,3,1,0,0,90/1,0,x,4,75,2,1,0,1,0,75/2,0,x,5,80,2,2,0,0,1,80/2,c,j,-z,j,6,5,0,0,0,6,x,1,75/2,1,1/2,0,1/2,0,85,c,j,6,5,0,0,0,C,B,X,B,b,x,1,x,2,x,3,x,4,x,5,0,x,3,90,1,3,1,0,0,90/1,0,x,4,75,2,1,0,1,0,75/2,0,x,5,80,2,2,0,0,1,80/2,c,j,-z,j,6,5,0,0,0,0,x,3,105/2,0,5/2,1,-1/2,0,6,x,1,75/2,1,1/2,0,1/2,0,86,c,j,6,5,0,0,0,C,B,X,B,b,x,1,x,2,x,3,x,4,x,5,0,x,3,90,1,3,1,0,0,90/1,0,x,4,75,2,1,0,1,0,75/2,0,x,5,80,2,2,0,0,1,80/2,c,j,-z,j,6,5,0,0,0,0,x,3,105/2,0,5/2,1,-1/2,0,6,x,1,75/2,1,1/2,0,1/2,0,0,x,5,5,0,1,0,-1,1,87,c,j,6,5,0,0,0,C,B,X,B,b,x,1,x,2,x,3,x,4,x,5,0,x,3,90,1,3,1,0,0,90/1,0,x,4,75,2,1,0,1,0,75/2,0,x,5,80,2,2,0,0,1,80/2,c,j,-z,j,6,5,0,0,0,0,x,3,105/2,0,5/2,1,-1/2,0,6,x,1,75/2,1,1/2,0,1/2,0,0,x,5,5,0,1,0,-1,1,c,j,-z,j,0,2,0,-3,0,88,c,j,6,5,0,0,0,C,B,X,B,b,x,1,x,2,x,3,x,4,x,5,0,x,3,90,1,3,1,0,0,90/1,0,x,4,75,2,1,0,1,0,75/2,0,x,5,80,2,2,0,0,1,80/2,c,j,-z,j,6,5,0,0,0,0,x,3,105/2,0,5/2,1,-1/2,0,21,6,x,1,75/2,1,1/2,0,1/2,0,75,0,x,5,5,0,1,0,-1,1,5,c,j,-z,j,0,2,0,-3,0,所以把x,5,换出为非基变量，x,2,为换入变量即新的基变量。,89,c,j,6,5,0,0,0,C,B,X,B,b,x,1,x,2,x,3,x,4,x,5,0,x,3,90,1,3,1,0,0,90/1,0,x,4