[管理学]第一章-线性规划课件

,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,运筹学,管理科学与工程系,经济与管理学院,浙江科技学院经济管理学院管工系,运筹学 管,课堂要求,1.要求学生上课不迟到，不早退，不得旷课；,2.上课认真听讲，要求每位同学都做笔记；,3.上课不得讲话，看书，玩手机等与课堂无关的内容；,4.课后要求独自完成作业，不得抄袭或不做课后作业。,8/30/2024,2,课堂要求1.要求学生上课不迟到，不早退，不得旷课；9/5/2,参考资料,1.胡运权主编，运筹学教程（第三版），清华大学出版社；,2.周华任主编，运筹学解题指导，清华大学出版社；,3.运筹学习题集（修订版），清华大学出版社；,4.熊伟编著，运筹学，机械工业出版社；,5.运筹学数据、模型、决策，科学出版社。,8/30/2024,3,参考资料1.胡运权主编，运筹学教程（第三版），清华大学出版社,前言运筹学简介,运筹学是管理科学的重要理论基础和应用手段，是管理专业的重要专业基础课程之一。,运筹学根据管理问题的环境条件和决策要求，建立相应的数学模型，利用数学模型对实际问题进行分析和求解，经过分析和比较，得到适合实际问题的方案。,求解,结果,.,求解,结果,.,建立模型,求解模型,修改,模型,求解,结果,.,修改,模型,实际问题,数学模型,8/30/2024,4,前言运筹学简介运筹学是管理科学的重要理论基础和应用手段，是,运筹学是在第二次世界大战中诞生和发展起来的。由于战争的需要，英国和美国招募了一批年轻的科学家和工程师，在军队将军的领导下研究战争中的问题，例如大规模轰炸的效果，搜索和攻击敌军潜水艇的策略，兵力和军需物质的调运等等。这些研究在战争中取得了很好的效果。当时英国把这些研究成为“作战研究”，英文是Operational Research，在美国称为Operations Research。,8/30/2024,5,运筹学是在第二次世界大战中诞生和发展起来的。由于战争的需要，,战后这些研究成果逐渐公开发表，这些理论和方法被应用到经济计划，生产管理领域，也产生了很好的效果。这样，Operations Research就转义成为“作业研究”。我国把Operations Research译成“运筹学”，非常贴切地涵盖了这个词作战研究和作业研究两方面的涵义。,运筹学的内容十分广泛，包括线性规划、整数规划、动态规划、非线性规划、图论与网络优化、排队论、决策理论、库存理论等。在本课程中，结合管理学科的特点，主要介绍线性规划、对偶问题，整数规划、运输问题、动态规划、图与网络分析。,8/30/2024,6,战后这些研究成果逐渐公开发表，这些理论和方法被应用到经济计划,授课主要内容,目录：,绪论（1）,第一章线性规划（12）,第二章对偶问题（10）,第三章运输问题（6）,第五章整数规划（6）,第七章动态规划（8）,第八章 图与网络分析（8）,上课总课时：51课时 课程设计1周（下学期开学前）,8/30/2024,7,授课主要内容目录：上课总课时：51课时 课程设计1周（下学,第一章 线性规划及单纯形法,1.1 线性规划问题及其数学模型,1.2 图解法,1.3 单纯形法原理,1.4 单纯形法计算步骤,1.5 单纯形法进一步讨论,8/30/2024,8,第一章 线性规划及单纯形法1.1 线性规划问题及其数学模型,本章学习要求,能建立实际问题的数学规划模型,理解线性规划模型的特点，标准型,掌握线性规划的图解法及其几何意义,掌握单纯形法原理,掌握运用单纯形表计算线性规划问题的步骤及解法,能用二阶段法和大M法求解线性规划问题。,掌握任何基可行解原表及单纯形表的对应关系,8/30/2024,9,本章学习要求能建立实际问题的数学规划模型9/5/20239,1.1线性规划问题及其数学模型,举例说明,线性规划数学模型的标准形式,8/30/2024,10,1.1线性规划问题及其数学模型举例说明9/5/202310,一、线性规划问题举例说明,生产计划问题,配料问题,背包问题,运输问题,指派问题,下料问题,8/30/2024,11,一、线性规划问题举例说明生产计划问题9/5/202311,例1：美佳公司生产计划问题,1、确定决策变量,通常由目标问题分解,设,x1代表生产种家电数量；,x2代表生产种家电数量；,2、分析并表达限制条件，包括约束条件,通常由等式或不等式表示。,0x1+5x215,6x1+2x224,x1+ x2 5,x1 0,x20,3、分析目标,是利润最大化,MaxZ=2x1+x2,8/30/2024,12,例1：美佳公司生产计划问题1、确定决策变量通常由目标问,例2：捷运公司,表12,所需仓库面积,1、确定决策变量,通常由目标问题分解,每个月有不同的租用方案，共有4个月需要租用仓库。则：,表13,租金与期限的关系,8/30/2024,13,例2：捷运公司表12 1、确定决策变量通常由目标问题分,1. 生产计划问题（Production Planning）,某工厂拥有A、B、C三种类型的设备，生产甲、乙、丙、丁四种产品。每件产品在生产中需要占有的设备机时数，每件产品可以获得的利润以及三种设备可利用的时数如下表所示：求使得总利润最大的生产计划。,设四种产品的产量分别为x,1,，x,2,，x,3,，x,4,，总利润为z，线性规划模型为：,max z=5.24x,1,+7.30x,2,+8.34x,3,+4.18x,4,s.t. 1.5x,1,+1.0x,2,+2.4x,3,+1.0x,4,2000,1.0x,1,+5.0x,2,+1.0x,3,+3.5x,4,8000,1.5x,1,+3.0x,2,+3.5x,3,+1.0x,4,5000,x,1, x,2, x,3, x,4,0,8/30/2024,14,1. 生产计划问题（Production Planning）,2. 配料问题（Material Blending）,某工厂要用四种合金T,1,、T,2,、T,3,、T,4,为原料，经熔炼成为新的不锈钢G。这四种原料含铬（Cr）、锰（Mn）和镍（Ni）的含量（），这四种原料的单价以及新的不锈钢G所要求的Cr、Mn、Ni的最低含量（）如下表：要求配100公斤不锈钢G，并假定在配制过程中没有损耗。求使得总成本最低的配料方案。,设四种原料分别选取x,1,，x,2,，x,3,，x,4,公斤，总成本为z。,min z=115x,1,+97x,2,+82x,3,+76x,4,s.t. 3.21x,1,+4.53x,2,+2.19x,3,+1.76x,4,3.20 Cr的含量下限约束,2.04x,1,+1.12x,2,+3.57x,3,+4.33x,4,2.10 Mn的含量下限约束,5.82x,1,+3.06x,2,+4.27x,3,+2.73x,4,4.30 Ni的含量下限约束,x,1,+x,2,+x,3,+x,4,=100 物料平衡约束,x,1, x,2, x,3, x,4,0,8/30/2024,15,2. 配料问题（Material Blending）某工厂要,3. 背包问题（Knapsack Problem）,一只背包最大装载重量为50公斤。现有三种物品，每种物品数量无限。每种物品每件的重量、价格如下表：求背包中装入每种物品各多少件，使背包中物品总价值最高。,设三种物品的件数各为x,1,，x,2,，x,3,件，总价值为z。,max z=17x,1,+72x,2,+35x,3,s.t. 10x,1,+41x,2,+20x,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元,8/30/2024,16,3. 背包问题（Knapsack Problem）一只背包最,4. 运输问题（Transportation）,某种物资从两个供应地A,1,，A,2,运往三个需求地B,1,，B,2,，B,3,。各供应地的供应量、各需求地的需求量、每个供应地到每个需求地每吨物资的运输价格如下表：求总运费最低的运输方案。,A1,A2,B3,B2,B1,35吨,25吨,10吨,30吨,20吨,2,3,5,4,7,8,8/30/2024,17,4. 运输问题（Transportation）某种物资从两个,设从两个供应地到三个需求地的运量（吨）如下表：,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,8/30/2024,18,设从两个供应地到三个需求地的运量（吨）如下表：min z=2,这个问题的最优解表示如下：,最小总运费为：z=330+55+410+815=275元,A1,A2,B3,B2,B1,35吨,25吨,10吨,30吨,20吨,2,3,5,4,7,8,30吨,5吨,10吨,15吨,8/30/2024,19,这个问题的最优解表示如下：最小总运费为：z=330+55,5. 指派问题（Assignment Problem）,有n项任务由n个人完成，每项任务交给一个人，每人都有一项任务。由i个人完成j项任务的成本（或效益）为c,ij,。求使总成本最小（或总效益最大）的分配方案。,设：,8/30/2024,20,5. 指派问题（Assignment Problem）有n项,张、王、李、赵四位老师被分配教语文、数学、物理化学四门课程，每位老师教一门课，每门课由一位老师教。根据这四位老师以往教课的情况，他们分别教四这门课程的平均成绩如下表。要求确定哪一位老师上哪一门课，使四门课的平均总成绩最高。,设：,8/30/2024,21,张、王、李、赵四位老师被分配教语文、数学、物理化学四门课程，,设：,max z=92x,11,+68x,12,+85x,13,+76x,14,+82x,21,+91x,22,+77x,23,+63x,24,+,83x,31,+90x,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,8/30/2024,22,设：max z=92x11+68x12+85x13+76x1,6. 下料问题,现将1m长的钢切成A0.4m,B=0.3m，C=0.2m长的三种钢，其中A，B，C三种钢分别需要20根，45根和50根，问如何进行切割使得需要的1m钢为最少？,解：将1m的钢分别切成A，B，C三种钢的可能方案如下：,设第i种方案进行切割的1m钢的为x,i,根；,minZ=0.1x,3,+0.1x,5,+0.1x,7,s.t. 2x,1,+x,2,+x,3,+x,4,20,2x,2,+x,3,+3x,5,+2x,6,+x,7,45,x,1,+x,3,+3x,4,+2x,6,+3x,7,+5x,8,50,x,i,0 (i=1,28),8/30/2024,23,6. 下料问题 解：将1m的钢分别切成A，B，C三种钢,小结,线性规划问题要求目标函数和约束方程必须是线性函数，隐含如下假定：,比例性假定：,每个决策变量对目标函数的贡献与决策变量的值成比例。每个变量对约束条件左端的贡献与变量的值成比例；,可加性假定：,任何变量对目标函数的贡献都与其他决策变量的值无关。一个变量对每个约束条件左端的贡献与该变量的值无关。,连续性假定,（可除性假定）,：,允许每个决策变量值使用分数值。,确定性假定：,已经确切知道每个参数（价值系数，工艺系数，右侧常数）,线性规划,数学模型三个要素：,决策变量,目标函数,约束条件,8/30/2024,24,小结线性规划问题要求目标函数和约束方程必须是线性函数，隐含如,课堂习题,P45 1.13 1.14(1),课后作业,P46 1.14(2) 1.15,8/30/2024,25,课堂习题9/5/202325,二、线性规划模型标准形式,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),线性规划模型的目标函数必须是变量的线性函数，约束条件必须是变量的线性等式或不等式。如右的问题就不是线性规划问题：,1.一般形式,8/30/2024,26,二、线性规划模型标准形式min(max) z=c1x1+c2,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,8/30/2024,27,2.线性规划的标准形式目标函数为极大化，约束条件全部为等号约,3.线性规划模型用矩阵和向量表示,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,价值系数,工艺系数矩阵,资源约束,8/30/2024,28,3.线性规划模型用矩阵和向量表示max z=c1x1+c2x,线性规划模型用矩阵和向量表示（续）,因此，线性规划模型可以写成如下矩阵和向量的形式,MaxZ =CX,s.t. AX=b,X,0,8/30/2024,29,线性规划模型用矩阵和向量表示（续）因此，线性规划模型可以写成,4.线性规划模型总结,线性规划模型的结构,目标函数 ：max，min,约束条件：,=,变量符号：0, 0, Free,线性规划的标准形式,目标函数：max,约束条件：=,变量符号：0,MaxZ =CX,s.t. AX=b,X,0,8/30/2024,30,4.线性规划模型总结线性规划模型的结构MaxZ =CX9/,5.线性规划问题的标准化,极小化目标函数转化为极大化,小于等于约束条件转化为等号约束,大于等于约束条件转化为等号约束,变量没有符号限制（Free）的标准化,变量小于等于0的标准化,8/30/2024,31,5.线性规划问题的标准化极小化目标函数转化为极大化9/5/2,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,取得极小化的最优解时，这个最优解同时使原目标函数值取得最大化的最优解。但两个问题最优解的目标函数值相差一个负号。,极小化目标函数问题转化为极大化目标函数,例如，对于以下两个线性规划问题,Max z=2x,1,+3x,2,s.t. x,1,+x,2,3,x,2,1 (A),x,1, x,2,0,Min 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)的最大化的目标函数值为max z=7，(B)的最小化的目标函数值为min z=-7,8/30/2024,32,min z=2x1-3x2+x3极小化目标函数问题转化,2x,1,+3x,2,-4x,3,5,引进,松弛变量,(Slack variable) x,4,0,2x,1,+3x,2,-4x,3,+x,4,=5,如果有一个以上小于等于约束，要引进不同的松弛变量。例如：,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,小于等于约束条件转化为等号约束,大于等于约束条件转化为等号约束,将不等式约束变为等式约束。例如：,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,8/30/2024,33,2x1+3x2-4x35小于等于约束条件转化为等号,没有符号限制的变量，用,两个非负变量之差,表示。例如：,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)的标准化,8/30/2024,34,没有符号限制的变量，用两个非负变量之差表示。例如：变量没有符,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,8/30/2024,35,Max z=-x1-2x2+3x39/5/202335,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,变量小于等于0的的标准化,8/30/2024,36,min z=x1+2x2-3x3变量小于等于0的的标准化9,课堂习题,P43 1.2,8/30/2024,37,课堂习题9/5/202337,1.2 图解法,相关概念和图解法步骤,线性规划问题图解法求解的几种结果,结论,8/30/2024,38,1.2 图解法相关概念和图解法步骤9/5/202338,模型中只有两个变量的线性规划问题，可以通过在平面上作图的方法求解。,可行解,：一个线性规划问题有解，是指能找出一组x,j,(j=1,2,n)满足约束条件，称这组x,j,为问题的可行解。,可行域：,通常线性规划问题总是含有多个可行解，全部可行解的集合为可行域。,最优解：,可行域中使目标函数为最优的可行解为最优解。,图解法的步骤：,建立坐标系，确定比例尺；,画出各约束条件的边界，定出可行域；,画出目标函数的一根等值线，平移得出最优解；,算出目标函数最优值。,1.相关概念和图解法步骤,8/30/2024,39,模型中只有两个变量的线性规划问题，可以通过在平面上作图的方法,线性规划的图解,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、线性规划的最优解是否可能位于可行域的边界上？,8/30/2024,40,线性规划的图解max z=x1+3x2可行域目标函数等值线,唯一最优解,无穷多最优解,无界解（,可行域无界）,无解（无可行解）,2.线性规划问题图解法求解的几种结果,1、唯一最优解（封闭）,2、多个最优解（封闭）,3、唯一最优解（开放）,4、多个最优解（开放）,5、目标函数无界（开放）,6、无可行解,8/30/2024,41,唯一最优解2.线性规划问题图解法求解的几种结果1、唯一最优解,线性规划问题解的形式:唯一最优解，无穷多最优解，无界解，无可行解；,若LP的可行域存在，即有可行解，则可行域是一个凸集；,若LP的最优解存在，则一定可以在可行域的某个顶点达到，如果在某两个顶点上达到最优，则该LP有无穷多最优解；,用图解法求解LP时，如果可行域封闭，可比较可行域的顶点的目标函数值，得到最优解；,注意,用图解法如果可以得到封闭的可行域，则定有最优解存在；,如果可行域不封闭，则解的三种形式都可能出现，必须用目标函数等值线的平移来判断。,3.结论,8/30/2024,42,线性规划问题解的形式:唯一最优解，无穷多最优解，无界解，无可,举例：,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,无解,8/30/2024,43,举例： 3.maxZ=3x1+9x24.maxZ=x1+ x,课后作业,P43 1.1,8/30/2024,44,课后作业9/5/202344,1.3 单纯形法原理,LP解的相关概念,凸集及其顶点,几个基本定理,单纯形法迭代原理,8/30/2024,45,1.3 单纯形法原理LP解的相关概念9/5/202345,x,3,=0,x,4,=0,max,z=x1+2x2,s.t. x1+x2,3,x2,1,x1, x2,0,max,z=x1+2x2,s.t. x1+x2,+ x3 =,3,x2,+x4=,1,x1, x2 ,x3, x4,0,x1=0, x2=0,x3=3, x4=1,x1=0, x4=0,x2=1, x3=2,x2=0, x3=0,x1=3, x4=1,x3=0, x4=0,x1=2, x2=1,x,1,=0, x,3,=0,x,2,=3,x,4,=-2,x,2,=0,x,1,=0,O,A,B,C,D,一.LP解的相关概念,1.可行域，可行解，最优解,8/30/2024,46,x3=0x4=0max z=x1+2x2max z=x1+2,LP问题数学模型,因此：,可行解,：满足（1.7）（1.8）的解称为LP的可行解；,可行域,：全部可行解的集合；,最优解,：使目标函数(1.6)达到最大值的可行解,8/30/2024,47,LP问题数学模型因此：9/5/202347,定义1,：从n个变量中任取m个变量x,i1,x,i2,x,im,，若这m个变量对应的系数列向量P,i1,P,i2,P,im,线性无关，即对应系数列向量行列式,0，,则称B=(P,i1,P,i2,P,im,),为基矩阵，简称,基,， x,i1,x,i2,x,im,为,基变量,，其余n-m变量为,非基变量,。,定义2,：在约束方程(1.7)中，令所有非基变量为0，根据克莱姆法则，则(1.7)有唯一解。令x,i1,1,x,i2,2,x,im,m,，称,为一组,基解,。,基可行解,：满足（1.8）中的基解为基可行解，即基解中每一分量均非负。,可行基,：基可行解对应的基。,退化解,：基变量中有分量为0的解。,线性规划的基可行解就是可行域的,顶点,。,2.基，基变量，非基变量；基解，基可行解，可行基,8/30/2024,48,定义1：从n个变量中任取m个变量xi1,xi2,xim，,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,可行域,8/30/2024,49,max z=x1+2x2max z=x1+2x2x1=0,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,最优解为x1 2，x24， x3 3，Z19,8/30/2024,50,1.maxZ=2x1+3x2最优解为x1 2，x24，,二 . 凸集和顶点,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.顶点,如果集合C中不存在任何两个不同的点x,1,，x,2,，使x为这两点连线上的一个点，称x为顶点。,对任何x,1,C，,x,2,C，不存在x=,x,1,（1,）x,2,(0,1),，则称x为凸集的顶点。,8/30/2024,51,二 . 凸集和顶点1.凸集9/5/202351,三.几个基本定理,定理1：,若线性规划问题存在可行解，则问题的可行域是凸集,引理：,线性规划问题的可行解X(x,1,x,2,x,n,)为基可行解的充要条件是X的正分量所对应的系数列向量是线性独立的（所组成的矩阵是非奇异的）。,8/30/2024,52,三.几个基本定理定理1：若线性规划问题存在可行解，则问题的可,定理2：,线性规划问题的基可行解X对应线性规划问题可行域的顶点。,分两步：1）顶点基可行解,2）基可行解顶点,反证法：,1）假设X,0,是可行域的顶点，X,0,不是基可行解，X,0,的前k个分量大于0，其余为0，因不是基可行解，则存在,所以X,0,不是可行域的顶点，与假设矛盾，则X,0,必为基可行解。,8/30/2024,53,定理2：线性规划问题的基可行解X对应线性规划问题可行域的顶点,2）假设X,0,是基可行解，X,0,不是顶点。,假设X,0,是一个基可行解，设X,0,的前m个分量为正，令X,0,=(x,1,x,2,x,m,0,0),T,因为不是顶点，则X,0,可以表示成另外两个点X,(1,)，X,(2),的凸组合，且P,1,P,m,线性无关。,所以X不能表示成可行域中另外两点的凸组合，与假设相矛盾，则X必为可行域的顶点。,8/30/2024,54,2）假设X0是基可行解，X0不是顶点。所以X不能表示成可行域,定理3：,若线性规划问题有最优解，一定存在一个基可行解是最优解,。,X,0,为LP的最优解，Z,*,=CX,0,，如果X,0,不是基可行解，则定有,X,(1),X,0,-ta , X,(2),=X,0,+ta为可行解，则有,CX,(1),=CX,0,+tCa,CX,0,CX,(2),=CX,0,-tCa,CX,0,则必有tCa=0,所以X,0,，X,(1),，X,(2),均为最优解，如果X,(1),，X,(2),不是基可行解，继续下去，则必可以找到基可行解为最优解。,8/30/2024,55,定理3：若线性规划问题有最优解，一定存在一个基可行解是最优解,四.单纯形法迭代原理,迭代基础,：如果LP存在最优解，则一定有一个基可行最优解，且对应LP可行域的顶点。（可行，基解，最优）,1.确定初始基可行解,基解，可行解,8/30/2024,56,四.单纯形法迭代原理迭代基础：如果LP存在最优解，则一定有一,2.最优性检验和解的判别,非基变量检验数,8/30/2024,57,2.最优性检验和解的判别非基变量检验数9/5/202357,由检验数可以判断解的最优性情况,（1）因为所有X,j,0，当所有,j,0,且所有a,ik,0(P,j,0), i=1,2,m，则该问题无界。,（4）,因为所有X,j,0，当存在,j,0时，则该基可行解不是最优解，需要寻找另一个基可行解；,8/30/2024,58,由检验数可以判断解的最优性情况（4）因为所有Xj0，当存在,3.基变换,变换目的,：使目标函数Z值得到改善，接近最优解，一次基变换，是从该顶点到相邻顶点，即一次基变换仅变换一个基变量。,换入变量的确定,k,0,a,ik,至少一个大于0，若,k,=Max,j,|,j,0,则x,k,为换入变量。,换出变量的确定,令x,k,=,0,x,j,=0,j=m+1,n,j,k,则x,i,=b,i,-a,ik,0，i=1,m,当a,ik,0时，,可任取；,当a,ik,0时，,则x,l,为换出变量。,系数变换,8/30/2024,59,3.基变换变换目的：使目标函数Z值得到改善，接近最优解，一次,以a,lk,为主元进行初等行变换,8/30/2024,60,以alk为主元进行初等行变换9/5/202360,习题,1.8；1.6,8/30/2024,61,习题9/5/202361,1.4 单纯形法计算步骤,求初始基可行解,最优性检验,基变换,8/30/2024,62,1.4 单纯形法计算步骤求初始基可行解9/5/202362,单纯形法原理单纯形法总结,STEP 0 找到一个初始的基础可行解，确定基变量和非基变量。,转STEP 1,。,STEP 1 将目标函数和基变量分别用非基变量表示。,转STEP 2,。,STEP 2,如果,目标函数中所有非基变量的检验数全部为非正数，,则,已经获得最优解，,如果,全为负数，则为,唯一最优解，,运算终止,。,；,如果,有为0的非基变量检验数，则有,无穷多最优解,。,运算终止,。,如果,有某非基变量检验数为正，且工艺系数全非正，则无界，,运算终止,。,否则,，选取检验数为正数最大的非基变量进基。,转STEP 3,。,STEP 3 选择最小比值对应的基变量离基，进行系数初等行变换，得新的基可行解，,转STEP 1,。,8/30/2024,63,单纯形法原理单纯形法总结STEP 0 找到一个初始,一.求初始基可行解,1.当约束条件为“”时，直接在约束不等式左边加上非负的松弛变量，使约束方程的系数矩阵很容易找到一个单位矩阵，求出一个初始基可行解。,2.当约束条件为“时，直接在约束不等式左边减去非负的剩余变量，此情况下很难找到一个单位矩阵，为求出初始基可行解，为此需要引入人工变量，以方便构成初始基可行解的一个基。,为了不改变问题的性质，对引入人工变量X,i,”的线性规划问题，需要在目标函数中减去MX,i,”,M为足够大的正数，称罚因子，促使X,i,”最终必为0。,3.当约束条件为”=“时，同样需要引入人工变量，以方便构成初始基可行解的一个基。目标函数需要减去罚因子。,8/30/2024,64,一.求初始基可行解1.当约束条件为“”时，直接在约束不等式,二.最优性检验,（1）若所有,j,0,且所有a,ik,0(P,j,0), i=1,2,m，则该问题无界，计算终止。,（4）当存在,j,0时，且有a,ik,0,继续第三步；,8/30/2024,65,二.最优性检验（1）若所有j0，且所有的aik0时；,得最优解时，有检验数为0的非基变量；,得最优解时，所有非基变量检验数为负；,8/30/2024,77,目标函数极小化时解的最优性判别；三、单纯形法计算中的几个问题,j,40,45,0,25,100/3,40, 3 ,x2入，x3出,j,0,0,0,-5,因为,j全0,且,1=0,则有无穷多最优解。 所以：X*=(0,80/3,20,0,0),Z*=1700,例:,0,-10,8/30/2024,78,j4045025100/340 3 x2入，x3出,j,1,1,0,0,-,50, ,x1入，x4出,j,0,2,0,-1,因为,2=2,且ai2全0所以：无界,例:,8/30/2024,79,j1100 -50 x1入，x4出j020-,例:,下表为一极大化问题对应的单纯形表,讨论在a1,a2,a3,a4,a5,a6取何值的情况下，该表中的解为：,唯一最优解；,无穷多最优解；,退化解；,无界；,无可行解；,X3换入，x2换出,A40,a50,a20, a30,a40,a50, x4或x2为人工变量，a60 ；x1为人工变量a60,A40,a4a5;a6/a12a10,a60 a1 0,8/30/2024,80,例:下表为一极大化问题对应的单纯形表讨论在a1,a2,a3,课后作业,P43 1.7,8/30/2024,81,课后作业9/5/202381,