线性规划与单纯形法课件

运筹学,Operational research,主讲 朱兴亮,绪论,运筹帷幄，决胜千里 运筹=谋划（规划）,第一节 运筹学释义和发展简史,运筹学是一门应用科学，它广泛应用现有的科学技术知识和数学方法，解决生产和管理过程中提出的专门问题，为决策者选择最优方案提供定量依据。,运筹学管理科学 用科学（系统化的知识）代替凭经验 的方法,1914，F.W.Lanchester战斗方程 一方有x个战斗单位，另一方有y个战斗单位， dy/dt=-ax, dx/dt=-ay ax2=by2 1935，Bawdsey雷达站的研究 1942，大西洋反潜作战 P.W.Morse协助英国打破德国对英吉利海峡的封锁： 将反潜攻击由潜艇投掷水雷，改为飞机投掷深水炸弹。起爆深度由100米改为25米。 运送物资的船队及护航舰队编队，由小规模多批次，改为加大规模，减少批次，这样损失率将减少,第二节 运筹学研究的基本特征和基本方法,基本特征： 系统的整体观念 多学科的综合 模型方法的应用 研究的基本步骤 分析和表述问题 建立模型 求解模型和优化方案 测试模型及对模型进行必要的修正 建立对解的有效控制 方案的实施,第三节 运筹学的主要分支,线性规划 非线性规划 动态规划 图论与网络分析 存储论 排队论 对策论 决策论,运筹学的主要内容,第一章 线性规划与单纯形法 第二章 对偶理论与灵敏度分析 第三章 运输问题 第四章 目标规划 第五章 整数规划 第十章 图与网络分析 第十二章 排队论,运筹学学习方法,1、课前预习 2、认真听课，适当笔记 3、认真作业 运筹学有一定难度，该课程有一定的研究性特征；以线性代数和概率论为基础,运筹学 解决问题的主要程序,建立数学模型（线性规划数学模型）,求解数学模型（图解法与单纯形法）,分析求解结果（对偶问题与灵敏度分析）,生产问题管理问题,第一章 线性规划与单纯形法,1 线性规划问题及其数学模型 2 线性规划问题的几何意义 3 单纯形法 4 单纯形法的计算步骤与表格单纯形法 5 单纯形法的进一步讨论 6 应用举例,线性规划(运筹学)主要解决两类问题,企业利润=收入-成本 收入由提供产品或服务获得 成本由消耗的资源承担 1、资源有限（获成本），要求生产的产品获得的收入（或利润）最多。1 2、任务（或产品收入）一定，要求消耗的资源（或成本）最少。2,线性规划中的两类数学模型1,1、max 总收入或总利润 总成本b 返回,线性规划中的两类数学模型2,2、min 总成本 总收入b 返回 2）表格单纯形法,线性规划问题的数学模型 线性规划的数学模型的一般形式 两个自变量线性规划的图解法 线性规划问题的标准形式 线性规划问题的解的概念,1 线性规划问题 及其数学模型,1.1 问题的提出,线性规划是运筹学的一个重要分支。线性规划在理论上比较成熟，在实用中的应用日益广泛与深入。特别是在电子计算机能处理成千上万个约束条件和决策变量的线性规划问题之后，线性规划的适用领域更为广泛了。从解决技术问题的最优化设计到工业、农业、商业、交通运输业、军事、经济计划和管理决策等领域都可以发挥作用。它已是现代科学管理的重要手段之一。,1、线性规划问题的提出,将生产经营和管理过程中的决策问题 转化成数学模型,例1: 生产计划问题(步骤),是问题中要确定的未知量，表明规划中的用数量表示的方案、措施，可由决策者决定和控制。,第1步 -确定决策变量（设决策变量的原则）,设 I的产量 II的产量 利润,第2步 -定义目标函数,Max Z = x1 + x2,Max Z = 2 x1 + 3 x2,第2步 -定义目标函数,x1 + 2 x2 8 4 x1 16 4 x2 12 x1、 x2 0,第3步 -表示约束条件,该计划的数学模型,目标函数 Max Z = 2x1 + 3x2 约束条件 x1 + 2x2 8 4x1 16 4x2 12 x1、 x2 0,x1,x2,决策变量（Decision variables） 目标函数（Objective function） 约束条件（Constraint conditions） 符号约束 可行域（Feasible region) 最优解（Optimal solution),基本概念,问题中要确定的未知量，表明规划中的用数量表示的方案、措施，可由决策者决定和控制。,它是决策变量的函数,指决策变量取值时受到的各种资源条件的限制，通常表达为含决策变量的等式或不等式。,满足约束条件的决策变量的取值范围,可行域中使目标函数达到最优的决策变量的值,建立线性规划数学模型的步骤,1、选择适当的决策变量 设决策变量的原则 2、用决策变量表达目标函数 收入或利润极大化 成本或支出极小化 3、用决策变量表达所有的约束条件 4、注意变量的符号约束返回,例 2 环境保护问题,工厂1（工业污水2万m3 ）治污成本 1000元/万m3 500万m3 20%自然净化 200万m3 工厂2 （工业污水1.4万m3 ） 治污成本800元/万m3 要求污水含量不大于0.2%(步骤),长江,嘉陵江,朝天门,说明,从第一化工厂排出的工业污水流到第二化工厂以前,有20%可以净化. 江水中要求污水含量不大于0.2%. 工厂1和工厂2的污水净化成本分别为1000元/万m和800元/万m 问每个厂各应处理多少工业污手,使这两个工厂总的处理工业污水费用最小.,设： 化工厂1每天处理的污水量为x1万立方米； 化工厂2每天处理的污水量为x2万立方米,建模型之前的分析和计算,整理得到本问题的数学模型为：,例3 合理下料问题,书上P38例10,原材料，长7.4米,一套钢架,任务：100套钢架 目标：成本最少,2.9m,2.1m,1.5m,分析下料的方式,原材料7.4m,2.9m的元钢不少于100根： 2x1+ x2 + x3 + x4100,2.1m的元钢不少于100根： 2x2 + x3 + 3x5 +2 x6 + x7 + x8 100,1.5m的元钢不少于100根： x1+ x3 + 3x4 + x5 + 2x6 +3 x7 + 4x8 100,数学模型为,min z= x1+ x2 + x3 + x4 + x5 + x6 + x7 + x8 2x1+ x2 + x3 + x4100 2x2 + x3 + 3x5 +2 x6 + x7 + x8 100 x1 + x3 + 3x4 + x5 + 2x6 +3 x7 + 4x8 100 xj 0， xj 为整数，j=1,2,8,能够求出最优解为： x1=10 ，x2 =50 ，x4 =30 (最优值)minz=90,模型建立,1、设(未知数)决策变量 设按方案下料的原材料根数为x1,方案为x2，方案为x3，方案为x4,方案为x5 ， 2、用决策变量表达目标函数 min z= 0x1+0.1 x2 + 0.2x3 + 0.3x4 + 0.8x5 3、用决策变量表达全部的约束条件 4、注意符号约束,教材上的模型说明,上题计算求得如下方案: x1=30,x2=10,x4=50,其余为0.即按方案1下料30根,按方案2下料10根,按方案4下料50根,总共需要90根原材料可以制造100套钢架.,例4 人事管理问题,一个企业每周七天都要生产或营业 每个工作人员每周连续5天 据分析每天的上班人数分别60、40、50、30、65、70和75人 问该企业至少需要多少个职工？,模型建立,1、设(未知数)决策变量 设从星期一开始上班的人数为x1,星期二开始上班的人数为x2，星期三开始上班的人数为x3，星期四开始上班的人数为x4,星期五开始上班的人数为x5 ，星期六开始上班的人数为x6，星期日开始上班的人数为x7。 2、用决策变量表达目标函数 min z= x1+ x2 + x3 + x4 + x5 + x6 + x7 3、用决策变量表达全部的约束条件 4、注意符号约束,min z=x1+ x2 + x3 + x4 + x5 + x6 + x7 x4 + x5 + x6 + x7 + x1 60 x5 + x6 + x7 + x1+ x2 40 x6 + x7 + x1+ x2 + x3 50 x7 + x1+ x2 + x3 + x4 30 x1+ x2 + x3 + x4 + x5 65 x2 + x3 + x4 + x5 + x6 70 x3 + x4 + x5 + x6 + x7 75 xj 0， xj 为整数，j=1,2,7,数学模型为,能够求出最优解为： x1=9 ，x2 =0， x3 =23，x4 =19， x5 =14， x6 =19， x7 =0 (最优值)minz=84,设决策变量的原则,1、将决策者想知道但还不知道的设为未知数； （返回） 2、所取决策变量要便于表达目标函数和约束条件。 3、当将决策者想知道但还不知道的是由多个部分组成时，则应将最基本的部分取为决策变量。(作业),建立线性规划数学模型的步骤,1、选择适当的决策变量 设决策变量的原则 2、用决策变量表达目标函数 收入或利润极大化 成本或支出极小化 3、用决策变量表达所有的约束条件 4、注意变量的符号约束返回,线性规划数学模型 的特点,1、一组决策变量(x1,x2,xn) 决策者可选择 2、一个目标函数 极大化或极小化 是决策变量的线性函数 Max(或min) z=c1x1+c2x2+cnxn 3、一组约束条件 决策变量的线性等式或不等式组 4、通常变量有符号约束 xj,P38例11 配料问题,模型建立,1、设(未知数)决策变量 设A产品中含原材料C、P、H的数量分别为AC、AP、AH B产品中含原材料C、P、H的数量分别为BC、BP、BH D产品中含原材料C、P、H的数量分别为DC、DP、DH。 2、用决策变量表达目标函数(利润=销售收入-成本) max z= 50(AC+AP+AH)+35(BC+BP+BH)+25(DC+DP+DH)-65(AC+ BC+ DC)-25(AP+ BP+ DP)-35(AH +BH +DH) = -15AC+25AP+15AH-30BC+10BP-40DC-10DH 3、用决策变量表达全部的约束条件 4、注意符号约束,约束条件,整理得,AC+BC+DC100 AP+BP+DP100 AH+BH+DH60,含量约束,原材料数量约束,数学模型为,max z= -15AC+25AP+15AH-30BC+10BP-40DC-10DH,AC、AP、AH， BC、BP、BH ，DC、DP、DH0,能够求得最优解和最优值,最优解 需要用原料C为100kg，P为50kg，H为50kg，构成产品A。其它产品不生产。 即每天只生产产品A为200kg，分别需要用原料C为100kg，P为50kg，H为50kg。 最优值即总利润是z=500元/天。,生产与库存的优化安排,某工厂生产五种产品（i=1，.，5），上半年各月对每种产品的最大市场需求为dij。已知每件产品的单件售价为Si元，生产每件产品所需要的工时为ai，单件成本为Ci元；该工厂上半年各月正常生产工时为ri（j=1，.，6），各月允许的加班工时为ri ,Ci为加班单件成本。又每月生产的各种产品如当月销售不完，可以库存。库存费用为Hi（元/件.月)。假设1月初所有产品的库存为0，要求6月末个产品库存量为ki件。现要求为该厂制定一个生产计划，在尽可能利用生产能力的条件下，获取最大利润。,设xij，xij分别为该厂第i种产品第j个月在正常时间和加班时间内的生产量；yii为i种产品在第j个月的销售量，wij为第i种产品第j月末的库存量。,例4 运输问题,P80, 产销平衡表 单位：吨,作业,P46 习题1.9， 提示：设从第i个班次开始上班的人数为xi,i=1,2,6 习题1.10,线性规划数学模型 的特点,1、一组决策变量(x1,x2,xn) 决策者可选择 2、一个目标函数 极大化或极小化 是决策变量的线性函数 Max(或min) z=c1x1+c2x2+cnxn 3、一组约束条件 决策变量的线性等式或不等式组 4、通常变量有符号约束或整数约束或0-1变量约束 xj； xj为整数； xj=0或1,线性规划模型的一般形式,线性规划问题的标准形式,标准形式为:,1、目标函数最大 2、约束条件等式 3、决策变量非负 4、右端系数非负,将下述线性规划化为标准形式,可行解，最优解 图解法的步骤 (1)画出可行区域 1)作出每个约束取等号的直线 2)判断可行域在直线的那一边 (2)找出最优解 1)作目标函数等值线，确定使目标函数最优的移动方向； 2)平移目标函数的等值线，找出最优点，算出最优值。,1.2 线性规划问题的图解法 适用于两个自变量,例1的数学模型,目标函数 Max Z = 2x1 + 3x2 约束条件 x1 + 2x2 8 4x1 16 4x2 12 x1、 x2 0,x1,x2,图解法,9 8 7 6 5 4 3 2 1 0,| | | | | | | | | 1 2 3 4 5 6 7 8 9,x1,x2,x1 + 2x2 8,目标函数 Max Z = 2x1 + 3x2 约束条件 x1 + 2x2 8 4x1 16 4x2 12 x1、 x2 0,4x1 16,4 x2 12,图解法,9 8 7 6 5 4 3 2 1 0,x2,目标函数 Max Z = 2x1 + 3x2 约束条件 x1 + 2x2 8 4x1 16 4x2 12 x1、 x2 0,可行域,图解法,9 8 7 6 5 4 3 2 1 0,| | | | | | | | | 1 2 3 4 5 6 7 8 9,x1,x2,目标函数 Max Z = 2x1 + 3x2 约束条件 x1 + 2x2 8 4x1 16 4x2 12 x1、 x2 0,可行域,图解法,9 8 7 6 5 4 3 2 1 0,x2,目标函数 Max Z = 2x1 + 3x2 约束条件 x1 + 2x2 8 4x1 16 4x2 12 x1、 x2 0,2x1 + 3x2 = 6,图解法,9 8 7 6 5 4 3 2 1 0,x2,目标函数 Max Z = 2x1 + 3x2 约束条件 x1 + 2x2 8 4x1 16 4x2 12 x1、 x2 0,x1+ 2x2=8 4x1 =16,图解法,线性规划问题求解的 几种可能结果,(a) 唯一最优解,(b)无穷多最优解,线性规划问题求解的 几种可能结果,(c)无界解 Max Z = x1 + x2 -2x1 + x2 4 x1 - x2 2 x1、 x2 0,x1,线性规划问题求解的 几种可能结果,(d)无可行解 Max Z = 2x1 + 3x2 x1 +2 x2 8 4 x1 16 4x2 12 -2x1 + x2 4 x1、 x2 0 可行域为空集,线性规划问题求解的 几种可能结果,图解法的几点结论:,1、可行域是非空有界或无界的凸多边形,也可能为空集。 2、可行域为有界时，一定有最优解 1）有唯一最优解 2）有两个以上的最优解（也必有无穷多个最优解） 3、可行域为无界时，可能有最优解，也可能无最优解 1）有唯一最优解 2）有两个以上的最优解（也必有无穷多个最优解） 3）无界解 4、可行域为空集，一定没有最优解 若线性规划问题存在最优解，它一定可以在可行域的顶点得到。 若两个顶点同时得到最优解，则其连线上的所有点都是最优解。,练习： 用图解法求解LP问题,图解法 （练习）,18 16 14 12 10 8 6 4 2 0,| | | | | | | | | 2 4 6 8 10 12 14 16 18,x1,x2,4x1 + 6x2 48,2x1 + 2x2 18,2x1 + x2 16,图解法 （练习）,18 16 14 12 10 8 6 4 2 0,| | | | | | | | | 2 4 6 8 10 12 14 16 18,x1,x2,4x1 + 6x2 48,2x1 + 2x2 18,2x1 + x2 16,可行域,A,B,C,D,E,图解法 （练习）,18 16 14 12 10 8 6 4 2 0,| | | | | | | | | 2 4 6 8 10 12 14 16 18,x1,x2,4x1 + 6x2 48,2x1 + 2x2 18,2x1 + x2 16,A,B,C,D,E (8,0),(0,6.8),34x1 + 40x2 = 272,图解法 （练习）,18 16 14 12 10 8 6 4 2 0,| | | | | | | | | 2 4 6 8 10 12 14 16 18,x1,x2,4x1 + 6x2 48,2x1 + 2x2 18,2x1 + x2 16,A,B,C,D,E (8,0),(0,6.8),图解法 （练习）,x2,18 16 14 12 10 8 6 4 2 0,| | | | | | | | | 2 4 6 8 10 12 14 16 18,x1,4x1 + 6x2 48,2x1 + 2x2 18,2x1 + x2 16,A,B,C,D,E (8,0),(0,6.8),最优解 (3,6),4x1+ 6x2=48 2x1+ 2x2 =18,图解法,9 8 7 6 5 4 3 2 1 0,x2,可行域为凸集 目标函数不同时 等值线的斜率不同 最优解在顶点产生,目标函数等值线的斜率,最优解,图解法,9 8 7 6 5 4 3 2 1 0,x2,可行域为凸集 目标函数不同时 等值线的斜率不同 最优解在顶点产生,目标函数等值线的斜率,最优解,图解法,9 8 7 6 5 4 3 2 1 0,x2,可行域为凸集 目标函数不同时 等值线的斜率不同 最优解在顶点产生,目标函数等值线的斜率,最优解,求解LP的基本思路,1、构造初始可行基； 2、求出一个基可行解（顶点） 3、最优性检验：判断是否最优解； 4、基变化，转2。要保证目标函数值比 原来更优。,下面的内容主要是为了 研究一般(多个变量)线性规划数学模型的求解,1.3 线性规划问题的标准形式,标准形式为:,1、目标函数最大 2、约束条件等式 3、决策变量非负 4、右端系数非负,举例,解：已知本例的标准型为：,1.3 线性规划问题的标准型式,用向量形式表示的标准形式线性规划,线性规划问题的几种表示形式,1.3 线性规划问题的标准型式,用矩阵形式表示的标准形式线性规划,1.3 线性规划问题的标准型式,(1) 若要求目标函数实现最小化，即min z =CX，则只需将目标函数最小化变换求目标函数最大化，即令z= z，于是得到max z= CX。 (2) 约束条件为不等式。分两种情况讨论： 若约束条件为“”型不等式，则可在不等式左端加入非负松弛变量，把原“”型不等式变为等式约束； 若约束条件为“”型不等式，则可在不等式左端减去一个非负剩余变量(也称松弛变量)，把不等式约束条件变为等式约束。 (3) 若存在取值无约束的变量xk,可令,如何将一般线性规划转化为标准形式的线性规划,一般线性规划问题的标准形化,min Z=CX 等价于 max Z = -CX “” 约束：加入非负松驰变量,例：,目标函数 Max Z = 2x1 + 3x2 约束条件 x1 + 2x2 8 4x1 16 4x2 12 x1、 x2 0,min Z=CX 等价于 max Z = -CX “” 约束：加入非负松驰变量,一般线性规划问题的标准形化,例：,“” 约束： 减去非负剩余变量；,Max,例 ：,可正可负（即无约束）；,解 ：标准形为,第三节 单纯形法原理 一、线性规划问题解的概念,标准型 可行解:满足AX=b, X=0的解X称为线性规划问题的可行解。 最优解：使Z=CX达到最大值的可行解称为最优解。,基：若B是矩阵A中mm阶非奇异子矩阵（B0），则B是线性规划问题的一个基。不妨设：, j=1，2，,m 基向量。 ，j=1，2，,m 基变量。 , j=m+1,n 非基变量。,线性规划问题解的概念,例,基、基变量、非基变量、基向量、非基向量、基解、基可行解、 可行基,例,行列式,基变量,非基变量,基向量,非基向量,对应于基B1的基解X1,非基可行解,例,行列式,基变量,非基变量,基变量,非基变量,对应于基B2的基解X2,基可行解,求解,线性规划问题解的概念,基解：称上面求出的X解为基解。 基可行解：非负的基解X称为基可行解 可行基：对应基可行解的基称为可行基,线性规划问题解的概念,线性规划解的关系图,非可行解,可行解,基可行解,基解,线性规划问题解的概念,最优解？,例：求基解、基可行解、最优解。,线性规划问题解的概念,最优解,线性规划问题解的概念,解：,：求基解、基可行解、最优解。,练习：,线性规划问题解的概念,2 线性规划问题的几何意义,基本概念 凸集：,线性规划问题的几何意义,顶点:若K是凸集，XK；若X不能用不同的两点 的线性组合表示为： 则X为顶点.,凸集,线性规划问题的几何意义,凸组合：,n=2，k=3,线性规划问题的几何意义,定理1: 若线性规划问题存在可行域, 则其可行域: 是凸集.,基本定理,证明:,线性规划问题的几何意义,只要验证X在D中即可,引理：可行解X为基可行解 X的正分量对应的列向量线性无关,定理3：若可行域有界，线性规划 问题的目标函数一定可以在 其可行域的顶点上达到最优。,定理2：线性规划问题的基可行解X 对应于可行域D的顶点。 证明：反证法。分两步。,几点结论：,线性规划问题的可行域是凸集。 基可行解与可行域的顶点一一对应，可行域有有限多个顶点。 最优解必在顶点上得到。,简写形式为：,向量和矩阵表示,max z=CX,其中，C=(c1,c2,cn ) 向量Pj对应的决策变量是xj.,矩阵形式为：,max z=CX s.t,称A为约束条件的mn维系数矩阵，一般m0; b为资源向量； C为价值向量； X为决策变量向量。 实际遇到的各种线性规划问题的数学模型都应变换为标准形式后求解。 以下讨论如何化标准型的问题：,若要求目标函数实现最小化， 即min z=CX.这时只需将目标函数最小化变换为最大化，即令z=-z,于是得到max z=-CX,这就和标准型的目标函数的形式一致了。,（2） 约束方程为不等式。这里有两种情况：一种是约束方程为不等式，则可在不等式的左边加上非负松弛变量，把原不等式变为等式；另一种是约束方程不等式，则可在不等式的左端减去一个非负剩余变量（也可称松弛变量），把不等式约束条件变为等式约束条件。,(3)若存在取值无（符号）约束的变量xk,可令xk=xk-xk,其中xk，xk0。,下面举例说明,例3 将下面的数学模型化为标准型。 Max z=2x1+3x2 x1+2x28 4x116 4x212 x1，x20,解,将各不等式加上松弛变量即得 Max z=2x1+3x2 x1+2x2+x3=8 4x1+x4=16 4x2+x512 x1,x2,x3,x4,x50,例3 将下述线性规划问题化为标准型,min z=-x1+2x2-3x3 x1+x2+x37 x1-x2+x32 -3x1+x2+2x3=5 x1，x20,x3为无约束,解,步骤为 1、 令x3=x4-x5,其中x4,x50; 2、 在第一个不等式的左边加上松弛变量x6; 3、 在第二个不等式的左边减去剩余变量x7; 4、 令z=-z, 把求 min z 改为求 max z; 即可得该问题的标准型,max z=x1-2x2+3(x4-x5) x1+x2+(x4-x5)+x6 =7 x1-x2+(x4-x5) -x7=2 -3x1+x2+2(x4-x5)=5 x1,x2,x4,x5,x6,x70,整理得:,max z=x1-2x2+3x4-3x5 x1+x2+x4-x5+x6 =7 x1-x2+x4-x5 -x7=2 -3x1+x2+2x4-2x5=5 x1,x2,x4,x5,x6,x70,1.4 线性规划问题的解概念,可行解 满足约束条件和非负约束的解称为可行解. 使目标函数达到最大值的可行解叫最优解。,基，基向量 基变量，非基变量 基（本）解，基（本）可行解，可行基,不失一般性，可设,称PJ（J=1,2,m）为基向量，与基向量Pj相应的xj(j=1,2,m)为基变量。否则称为非基变量。,为了进一步讨论线性规划问题的解，下面研究约束方程（1.5）的求解问题。假设该方程组系数矩阵A的秩为m,因mn,故它有无穷多个解。假设前m个变量的系数列向量是线性独立的。,这时（1.5）可写成,方程组（1.7）的一个基是,设XB是对应于这个基的基变量 XB=(x1,x2,xm)T 现若令（1.7）的非基变量xm+1=xm+2=xn=0，并用高斯消去法，可以求出一个解 X=(x1,x2,xm,0,0)T 这个解的非零分量的数目不大于方程的个数m,称为基解。于是，由一个基可以求出一个基解。,基可行解,满足非负条件（1.6）的基解，称为基可行解。于是基可行解的非零分量的数目也不大于m,并且都是非负的。,可行基,对应于基可行解的基，称为可行基。 可见，约束方程祖（1.5）具有的基解的数目最多是 个。,基解中非零分量的个数小于m时（或基变量有零时），这基解（或基可行解）称为退化解（或退化基可行解）。,2 线性规划问题的几何意义,凸集,2.1 基本概念,凸集 设K是n维欧氏空间的一点集，若任意两点X(1)K,X(2)K的连线上的点X(1)+（1-）K，（01），则称K为凸集。 一般的实心圆，实心多边形、实心多面体等都是凸集，而圆周和有洞的圆盘等都不是凸集。,凸组合 设X(1)，X(2)，X(k)是n维欧氏空间En中的k个点，若存在1，2，k,且0i1,i=1,2,k; =1,使 X=1X(1)+2X(2)+kX(k) 则称X为X(1)，X(2)，X(k)的凸组合。,顶点 设K是凸集，XK,若X不能用不同的两点X(1)K和X(2)K的线性组合表示为 X=X(1)+（1-）X(2)，（01） 则称X为K的一个顶点（或极点）。,2.2 基本定理,定理1 若线性规划问题存在可行域，则其可行域 是凸集。,证明:,任意x1 ,x2D,则 , 对任意0,1,显然凸组合 0, 又有 因此,XD,故D为凸集.,引理1 线性规划问题的可行解X=(x1,x2,xn)T为基可行解的充分必要条件是X的正分量是线性独立的。 定 理 2 线性规划问题的基可行解X对应于可行域的顶点。 引 理 2 若K是有界凸集，则任意一点xK可表示为K的顶点的凸组合。 定 理 3 若可行域有界，线性规划问题的目标函数一定可以在其可行域的顶点上达到最优。,有时目标函数可能在多个顶点达到最大值。这时这些顶点的凸组合上也达到最大值。称这种线性规划问题有无限多个最优值。,3 单纯形法,3.1 单纯形法举例 例6 求解下面的线性规划 max z=2x1+3x2+0x3+0x4+0x5 x1+2x2+x3 =8 4x1 +x4 =16 1.12 4x2 +x5=12 x1,x2,x3,x4,x50,单纯形法的步骤：,1、找一个基可行解X0作为初始解; 最容易得到的可行基是标准型线性规划的系数矩阵的单位矩阵.,2、求检验数，检验X0是否为最优解,（）求检验数 将约束方程组的基变量的系数矩阵化为单位矩阵（或将基变量用非基变量表出）； 通过代入或加减乘除消元法将目标函数中的基变量消去，则非基变量的系数即为检验数 （）最优解的判别 当检验数全部小于或等于0时， 该基可行解为最优解,求解可结束. 当存在正的检验数时,该基可行解就不是最优解,就要换到一个新的(与X0相邻的)基可行解（X1）,Z=2x1+3x2+0 X3=8-x1-2x2 X4=16-4x2 X5=12-4x2 目标函数的表达式中还存在正系数的非基变量,这表示目标函数还有增加的可能,就需要基变量和非基变量对换. 一般取正系数最大的那个基变量x2为换入变量,那么取哪个基变量为换出变量呢?,当将x2确定为换入变量,x1=0时,必须确保x3,x4,x5均非负. X3=8-2x2=0 X4=16=0 X5=12-4x2=0,3 、换基,(1)确定进基变量:凡是检验数大于0的非基变量都可进基;但一般选择最大的检验数对应的变量进基 (2)按最小比原则确定出基变量，就可得一新的（更接近于最优解的）基可行解（X1），对（X1）重复的过程就可在有限步得到最优解，或判断出无最优解。,解 ： 1、求一个初始基可行解 约束方程的系数矩阵,从上面（1.12）中可以看到x3,x4,x5的系数列向量,组成一个单位矩阵，是一个可行基。,这些向量构成一个可行解基，对应的基可行解为x0=（0，0，8，16，12），基,2、求对应于 X0的检验数,对应于基B0的变量x3,x4,x5为基变量。 为求检验数，将约束方程组（1.12）的基变量的系数矩阵化为单位矩阵（或将基变量用非基变量表出）可以得到 x3 + x1+2x2 =8 x4 +4x1 =16 x5 +4x2 =12 或 x3 =8 - x1-2x2 x4 =16-4x1 （1.13） x5=12- 4x2 将（1.13）代入目标函数z=2x1+3x2+0x3+0x4+0x5得到 z=0+2x1+3x2。 于是非基变量x1，x2的系数就为检验数，分别为2，3。,最优性判别,从目标函数可以看出，该基可行解X0=(0,0,8,16,12,)对应的目标值为0， 但是非基变量x1,x2的系数为正，因此只要增加x1或x2的值，（最大化的）目标函数就可以增加。 只要有正的检验数，该基可行解就不会是最优解，只有当全部的检验数都小于或等于零时，对应的基可行解才为最优解。,3、换基,1、先确定进基变量 凡是检验数大于0的非基变量都可进基;但一般选择最大的检验数对应的变量进基,现分析（1.13），由于x2的系数为正，显然当x2增大，则目标函数z的值也增大。当x2 定为换入变量后，必须从x3,x4,x5中换出一个，并保证其余的变量都是非负，即x3,x4,x50。,2、确定出基变量,由于在下一个基可行解中， x1仍然为非基变量，x1=0，由（1.13）式得到 x3 =8 -2x20 x4 =160 （1.15） x5=12-4x20 从（1.15）中可以看出，x2的最大值只有选择x2=min(8/2,-，12/4)=3，才能使（1.15）成立。,当x2=3时，基变量x5=0，这就决定用x2去替换x5。因此x5为出基变量。 。以上数学描述说明了每生产一件产品，需要用掉各种资源的数量为2，0，4。由这些资源中的薄弱环节，就确定了产品的产量，这里就是由原材料B的数量确定了产品的产量x2=12/4=3件。,为了求得以x3,x4,x2为基变量的一个基可行解和相应的检验数，需将（1.13）中x2 与x5的位置对换。得到 X3 +2x2 =8 - x1 (1) x4 =16-4x1 (2) （1.16） 4x2=12 - x5 (3) 或x1+ 2x2 +x3 =8 4x1 +x4 =16 4x2 +x5 =12,用消元法，将（1.16）式中基变量的系数列向量变换为单位列向量。其运算步骤:（3）=（3）/4；（1）=（1）-2（3）；（2）=（2），并将结果仍按原顺序有： x3 =2- x1 +1/2x5 (1) x4 =16-4x1 (2) （1.17） x2=3 -1/4 x5 (3),再将（1.17）代入目标函数（1.11）得到 z=9+2x1-3/4x5 (1.18) 在（1.17）中令非基变量x1=x5=0，得到另一个基可行解X(1)=(0,3,2,16,0)T。 将基可行解X(1)的值代入目标函数得z=9. 从目标函数(1.18)中可看出,非基变量x1,x5检验数分别为2，-3/4。 X(1)不是最优解。 再换基.,从目标函数的表达式（1.18）中可以看到，非基变量x1的系数是正的，说明目标函数值还可以增大，X(1)不一定是最优解。 于是再用上述方法，确定x1为换入、变量，为确定换出变量:,x3 =2- x1 +1/2x5 (1) x4 =16-4x1 (2)（1.17） x2=3 -1/4 x5 (3) 在上式中，由于x5在下一基可行解中仍然为非基变量取0值，x1的最大取值为min(2,16/4,-)=2,此时x3=0,因此x3出基，得一新的基。,换基,将x1 与x3的位置交换得 x1 =2- x3 +1/2x5 4x1 +x4 =16 x2=3 -1/4 x5 用消去法将x1的系数化成出基变量的系数列 x1 =2- x3+1/2x5 x4 =8+4x3-2x5 x2=3 -1/4 x5 将x1代入前面的目标函数得: z=9+2x1-3/4x5=13-2 x3+1/4x5,容易看出此时的基可行解为 X(2)=(2,3,0,8,0) z=13. z=13-2 x3+1/4x5,有正的检验数,因此还不是最优解. 再次换基. 先确定进基变量, x5, 再确定出基变量:,看看前一次的约束条件 x1 =2- x3+1/2x5 x4 =8+4x3-2x5 x2=3 -1/4x5 最小比 = min(-,8/2,3/(1/4)=8/2=4, 因此x4出基, X1 -1/2x5 =2- x3 2x5 =8+4x3- x4 1/4x5 +x2=3,X1 =4 -1/4x4 x5 =4+2x3- 1/2x4 x2=2-1/2x3+1/8x4 代入目标函数z=13-2x3+1/4x5消去基变量x5得: z=14-3/2x3-1/8x4 由于所有的检验数都小于等于零,因此该基可行解X(4)=(4,2,0,0,4)为最优解.最优值z=14.,再分析（1.19），可见到所有非基变量x3,x4的系数都是负数。这说明若要用剩余资源x3,x4，就必须支付附加费用。所以当x3=x4=0时，即不再利用这些资源时，目标函数达到最大值。所以X(3)是最优解。即应当产品生产4件，产品生产2件，工厂才能得到最大利润。,3.2 初始基可行解的确定,为了确定初始基可行解，首先找出初始可行基，其方法如下： 1、 若线性规划问题 (1.20),从Pj(j=1,2,n)中一般能直接观察到存在一个初始可行基,2、对所有约束条件是“”形式的不等式，可以利用化标准型的方法，在每个约束条件的左端加上一个松驰变量。经整理，重新对xj及aij(i=1,2,m;j=1,2,n)进行编号，则可得下列方程组,x1 +a1,m+1xm+1+a1nxn=b1 x2 +a2,m+1xm+1+a2nxn=b2 xm+am,m+1xm+1+amnxn=bm xj0，j=1,2,n,显然得到一个mm单位矩阵,以B作为可行基。移项得 x1=b1-a1,m+1xm+1- a1nxn x2=b2-a2,m+1xm+1-a2nxn xm=bm -am,m+1xm+1-amnxn 令xm+1=xm+2=xn=0,由（1.23）可得xi=bi (I=1,2,m) 又因bj0，所以得到一个初始基可行解 X=(x1,x2,xm,0,0)T =(b1,b2,bm,0,0)T,3.对所有约束条件是“”形式的不等式及等式约束情况，若不存在单位矩阵时，就采取人造基的方法。即对不等式约束减去一个非负的剩余变量后，再加上一个非负的人工变量。对于等式约束加上一个非负的人工变量，总能得到一个单位矩阵。,33 最优性检验与解的判别,线性规划问题的求解结果可能出现唯一最优解、无穷多最优解、无界解和无可行解四种情况，为此需要建立对解的判别准则。一般情况下，经过迭代后（1.23）式变为,(i=1,2,m) (1.24 ),将（1.24）式代入目标函数（1.20），整理后得,令 ， （j=m+1,n） 于是 再 （j=m+1,n） 则 （1.27）,1、最优解的判别定理： 若X(0)=( 0,0)T为对应于基B的一个基可行解，且对于一切j=m+1,n有j0，则X(0)为最优解，称j为检验数。,2、无穷多最优解判别定理：若X(0)=( 0,0)T为一个基可行解，对于一切j=m+1,n有j0，又存在某个非基变量xm+j的检验数m+k=0,则线性规划问题有无穷多最优解。 因为将 xm+j将得到一个新的基可行解仍为最优解,由于最优解的凸组合还是最优解,因此有无穷多最优解.,3、 无界解判别定理: 若X(0)=( 0,0)T为一个基可行解，有一个非基变量xm+k的检验数m+k0,并且对i=1,2,m有ai,m+k0, 那么该线性规划问题具有无界解（或称无最优解）,例,x3 =8 -2x20 x4 =160 （1.15） x5=12-4x20 此时最小比=min(8/2,-,12/4)=3是进基变量的最大取值，但是若（1.15）式中x2的系数全部非负，则最小比为+，即x2可以取到+，目标函数值 z=0+2x1+3x2 就可取到+，因此目标函数无界。,3.4 基变换,1、换入变量的确定：由（1.27）式看到，当某些j0时，xj增加则目标函数还可以增大，这时要将某个非基变量xj换到基变量中去（称为换入变量）。若有两个以上的j0，那么选哪个非基变量作为换入变量呢？,为了使目标函数值增加最快，从直观上一般选j0种的大者（可以任意选或按最小下标选）即 max(j0)=k 则对应的xk为换入变量。 实际上换一次基将使目标函数值改进k。,1、 换出变量的确定,按最小比值确定换出变量。,3.5 迭代（旋转运算）,将约束条件的增广矩阵中新基变量的系数通过矩阵的行变换或Gauss变换变为单位矩阵。,例7 试用上述方法计算例6的两个基变换。,解 约束条件的增广矩阵为 x1 x2 x3 x4 x5 b,当以x3，x4，x5为基变量，x1，x2为非基变量，令x1 =x2=0，可得到一个基可行解 X(0)=(0,0,8,16,12) 现用x2去替换x5,于是将x3，x4，x2的系数矩阵变换为单位矩阵,经变换后为 x1 x2 x3 x4 x5 b 令非基变量x1,x5=0,得到新的基可行解 X(1)=(0，3，2，16，0)T,4 单纯形法的计算步骤 与表格单纯形法,线性规划问题,X1 +a1,m+1xm+1+a1nxn =b1 x2 +a2,m+1xm+1+a2nxn =b2 xm+am,m+1xm+1+amnxn=bm -z+c1x1+c2x2+cmxm+c m+1xm+1+cnxn =0,为了便于迭代运算，可将上述方程组写成增广矩阵 -z x1 x2 xm xm+1 xn b,若将z看成不参与基变换的基变量，它与x1，x2，xm的系数构成一个基，这时可采用行初等变换将c1,c2,cm变换为零，使其对应的系数矩阵为单位矩阵，,得到 -z x1 x2 xm xm+1 xn b,可根据上述增广矩阵设计计算表如下：,4.2 计算步骤,（1） 找出初始可行基，确定初始基可行解，建立初始单纯形表。 （2） 检验各非基变量xj的检验数是 则已得到最优解。可停止计算。否则，转入下一步。 （3 ）在 中，若有某个对应项xk的系数列向量Pk0，则此问题是无界，停止计算。否则，转入下一步。,（4） 根据max(j0)=k,确定xk为换入变量，按规则计算 可确定xl换入变量。转入下一步。 （5） 以alk为主元素进行迭代（即用高斯消去法或称为旋转运算），把xk所对应的列向量,将xB列中的xl换为xk,得到新的单纯形表。重复（2）（5），直到终止。 现用例1的标准型来说明上述计算步骤。 （1） 根据例1的标准型，以x3,x4,x5为基变量，它对应的单位矩阵为基。这就得到初始即可行解X(0)=(0,0,8,16,12)T 将有关数值填入表中，得到（对应于初始基可行解的）初始单纯形表。,表1-3,(初始)单纯形表的特点,1、一个单纯形表对应于一个基可行解; 2、一个单纯形表中，基变量的系数矩阵是单位矩阵; 3、一个单纯形表中，目标函数中基变量的系数为零，非基变量的系数为检验数； 4 、检验数的计算既可用公式法，也可用消去法； 5 、一个单纯形表