运筹学A-第1章线性规划.ppt

第1章 线性规划 与单纯形法,2019/8/13,2,第1 章 线性规划,内容提要,第一节 线性规划问题的数学模型 第二节 两个变量LP问题的图解法 第三节 LP问题数学模型的标准型 第四节 线性规划问题解的性质 第五节 单纯形法原理及求解步骤,2019/8/13,3,第一节 线性规划问题的数学模型,线性规划(Linear Programming，LP)是运筹学的重要分支之一，在实际中应用得较广泛，其方法也较成熟，借助计算机，使得计算更方便，应用领域更广泛和深入。,线性规划通常研究资源的最优利用、设备最佳运行以及费用最低等问题。例如，当任务或目标确定后，如何统筹兼顾，合理安排，用最少的资源 （如资金、设备、原标材料、人工、时间等）去完成确定的任务或目标；企业在一定的资源条件限制下，如何组织安排生产获得最好的经济效益（如产品量最多 、利润最大）。,2019/8/13,4,一、问题的提出（线性规划问题举例）3.26,例1-1(生产计划问题) 某厂在计划期内安排、生产两种产品，已知生产单位产品所需要的设备台数、A和B两种原材料的消耗量以及利润如表1-1所示，问如何安排生产使利润最大？（假设产品全部售出）,x1,x1,x1,x2,x2,x2,2019/8/13,5,(1)决策变量：设x1为甲产品的产量，x2为乙产品的产量。 (2)约束条件：生产受资源制约，不能突破有限供给量。 设备约束条件的数学表达为： x1 + 2x2 8 原材料A约束条件数学表达为：4x1 16 原材料B约束条件数学表达为： 4x2 12 (3)目标函数：目标函数反映企业利润最大化 max Z = 2x1 + 3x2 (4)非负约束：两产品的产量为非负 x1 0， x2 0,LP模型：,s.t. (subject to) 使满足，使服从,例1-2 见教材第5页,2019/8/13,6,例1-3. 某工地租赁甲、乙两种机械安装A、B、C三种构件，这两种机械每天的安装能力、租赁费用以及工程任务如下表所示，问如何租赁甲、乙两机械才能使总的租赁费用最低？,2019/8/13,7,【解】设租赁机械甲x1天、机械乙x2天，则该线性规划问题的数学模型为：,例1-4 见教材第6页，例【1.2】人员分配问题,2019/8/13,8,某一机床需要用甲、乙、丙三种规格的轴各一根，这些轴的规格分别是2.9、2.1和1.5m，这些轴需要用同一种圆钢切割而成，圆钢长度为7.4m。现在要制造100台机床，问：最少要用多少圆钢来生产这些轴？(切割损失不计),解：1、设一根圆钢切割成甲、乙、丙三种轴的根数分别为y1, y2, y3, 则切割方式可用不等式2.9y1+2.1y2+1.5y37.4表示，求这个不等式关于y1，y2，y3的非负整数解。例如：y1=2， y2=0 ，则 y3 只能为1，余料为0.1。像这样的非负整数解共有8组，也就是有8种下料方式，如表1.4所示。,2、建立线性规划数学模型。设xj (j=1,2,8)为第 j 种下料方案所用圆钢的根数。,思考题：（下料问题）,2019/8/13,9,min Z = x1+x2+x3 +x4+x5 +x6+x7 +x8,(x1=10, x2=50, x4=30, 16m),2019/8/13,10,思考题：某糖果厂用原料A，B，C加工成三种不同牌号糖果甲、乙、丙。已知各种糖果的中A，B，C的含量，原料成本，各种原料每月的限制用量，三种牌号糖果的单位加工费及售价如下表所示。,问该厂每月生产这三种牌号糖果各多少kg，利润最大？,2019/8/13,11,解：设xij为生产第j种糖果使用的第i种原料的公斤数，i=1,2,3；j=1,2,3，则该问题的数学模型可归结为：,最优解：,即该厂每月应生产甲种牌号糖果906.67kg，乙种牌号糖果4793.33kg。,2019/8/13,12,思考题：（投资问题）,某投资公司在第一年初有100万元资金，每年都有如下的投资方案：假使第一年初投入一笔资金，第二年初又继续投入此资金的50%，那么到第三年初就可回收第一年初投入资金的两倍。问：该投资公司如何确定投资策略使第六年初所拥有的资金最多？,解：设x1为第一年的投资，x2为第一年的保留资金，则：,x1 + x2 = 100,第二年： 设x3为第二年新的投资，x4为第二年的保留资金，则：,2019/8/13,13,第三年：设 x5 为新的投资，x6 为第三年的保留资金；,第四年：设新的投资 x7 ，第四年的保留资金 x8 ；,第五年：设 x9 为第五年的保留资金。根据题意，第五年初不再进行新的投资，因为这笔投资要到第七年初才能收回。,约束条件 每年应满足如下的关系： 追加投资金额 + 新投资金额 + 保留资金=可利用的资金总额,2019/8/13,14,X*(22.64, 72.36, 58.54, 0, 26.02, 0, 104.06, 0, 0)T，Z*208.12。,到第六年初，实有资金总额为x9 + 2x7，整理后得到下列线性规划模型：,max Z = 2x7 + x9,第一年投资22.64元; 第二年新投资58.54元; 第三年新投资26.02元;第四年新投资104.06元; 第六年初拥有资金208.12万元。,2019/8/13,15,思考题：某人有30万元资金，在今后的三年内有以下投资 项目可供参考： (1) 三年内的每年年初均可投资，每年获利为投资额的20%，其本利可一起用于下一年的投资； (2) 只允许第一年年初投入，第二年末可收回，本利合计为投资额的150%，但此类投资额不超过15万元； (3) 第二年初允许投资，可于第三年末收回，本利合计为投资额的160%，这类投资限额20万元； (4) 第三年初允许投资，一年回收，可获利40%，投资限额为10万元。 试为该人确定一个使第三年末本利和为最大的投资计划？ （假设有钱就用于投资）,设xij为第 i 年初投入到 j 项目的资金额,2019/8/13,16,对于约束条件：,第1年，可用于项目1和2投资： x11 + x12 = 300000,第2年，可用于项目1和3投资，投资额为x11的本利和：x21 + x23 = 1.2 x11,第3年，可用于项目1和4投资，投资额x21和x12有关： x31 + x34 = 1.2 x21 + 1.5 x12,投资限额： x12 150000; x23 200000; x34 100000,非负约束： xij 0 ( i = 1,2,3; j = 1,2,3,4 ),对于目标函数，只需考虑第3年末的收益：,项目1：x31 1.2 x31 (本利和)；,项目2：x22 0；,项目3：x23 1.6 x23 (本利和)；,项目4：x34 1.4x34 (本利和)；,maxZ = 1.2 x31 + 1.6 x23 + 1.4 x34,2019/8/13,17,解：设xij为第 i 年初投入到 j 项目的资金额，其数学模型为：,maxZ = 1.2 x31 + 1.6 x23 + 1.4 x34,注意本题条件：有钱就会用于投资，即： 可利用的资金 = 投资金额，据此建立约束等式。,x11 + x12 = 300000 x21 + x23 = 1.2 x11 x31 + x34 = 1.2 x21 + 1.5 x12 x12 150000 x23 200000 x34 100000 xij 0 (i = 1,2,3; j = 1,2,3,4),2019/8/13,18,二、线性规划问题的数学模型3.30,线性规划问题的数学模型包括三大要素： （1）一组决策变量（x1 , x2 , , xn），是模型中需要首确定的未知量。 （2）一组约束条件，是模型中决策变量受到的约束限制，包括两个部分：不等式或等式；非负取值（实际问题）。 （3）一个目标函数，是关于决策变量的最优函数，max或min。,2019/8/13,19,思考：为什么称以上问题为线性规划问题呢？,其主要特征是： 1. 解决的问题是规划问题； 2解决问题的目标函数是多个决策变量的 线性函数，通常是求最大值或最小值； 3解决问题的约束条件是多个决策变量 的线性不等式或等式。,2019/8/13,20,线性规划问题模型的一般形式可总结为：,线性规划问题模型的一般形式,用一组非负决策变量表示的一个决策问题； 存在一组等式或不等式的线性约束条件； 有一个希望达到的目标，可表示成决策变量的极值线性函数。,为了书写方便，上式也可简写：,2019/8/13,21,一般地，xj0，但有时xj0或xj无符号限制。,2019/8/13,22,其中：cj为价值系数，C=(c1, c2, cn)为价值向量；aij为技术系数，A=(P1, P2, Pn)为技术矩阵，如： P1=(a11, a21, am1)T， P2=(a12, a22, am2)T， Pn=(a1n, a2n, amn)T； bi为限制系数，b=(b1, b2, bm)T。,2019/8/13,23,线性规划模型矩阵形式，,其中： X=(x1, x2, xn)T； C=(c1, c2, cn) ； b=(b1, b2, bm)T。,技术系数矩阵：,2019/8/13,24,第二节 用于两个变量线性规划问题的图解法,1、概念： 利用几何图形求解两个变量线性规划问题的方法。,3、求解步骤：,第一步：建立平面直角坐标系；,第三步：在可行域内平移目标函数等值线， 确定最优解及最优目标函数值。,2、特点： 简单、直观，但只适用于两个变量的LP问题。,第二步：根据约束条件画出可行域；,2019/8/13,25,可行解：满足约束条件的解； 可行域：所有可行解的集合； 最优解：使目标函数达到最优的可行解。 可行域：满足所有约束条件的解的集合，即所有约束条件 共同围城的区域。,maxZ= 3x1 + 5x2 2x1 16 2x2 10 3x1+4x2 32 x10, x20,s.t.,2019/8/13,26,目标函数等值线,目标函数 Z = 3x1 + 5x2 代表以 Z 为参数的一族平行线。,(4, 5),2019/8/13,27,例：用图解法求解线性规划问题？,坐标系：横坐标x1 ，纵坐标x2,(2, 6),先将约束不等式变为等式，画出各等式对应的直线，然后再根据不等式符号确定可行域,*线性规划问题解的可能,结论： 该问题具有唯一最优解，X*=(2,6)T，Z*=360,向上平移目标函数等值线 x2 = -3x1/5 + Z/50，确定最优解。,2019/8/13,28,x1,x2,O,10,20,30,40,10,20,30,40,(15,10),最优解 X* = (15,10)T,最优值 Z* = 85,2019/8/13,29,2,4,6,x1,x2,2,4,6,最优解 X* = (3,1)T 最优值 Z* = 5,(3,1),min Z = x1 + 2x2,2019/8/13,30,例：用图解法进行求解线性规划问题？,如果线性规划问题有两个最优解， 则它一定有无穷多最优解（多重最优解）。,2019/8/13,31,例 用图解法求线性规划问题？,2019/8/13,32,该线性规划问题具有无界解。 可行域无上界，目标值可以无限增大 (缺乏必要约束),2019/8/13,33,例,2019/8/13,34,该线性规划问题无可行解，原因： 线性规划问题的可行域是空集 (约束条件相互矛盾),2019/8/13,35,x2,x1,O,10,20,30,40,10,20,30,40,50,50,无可行解 即无最优解,max Z=10x1+4x2,2019/8/13,36,图解法的解题思路和几何上的直观表示，对求解线性规划问题的求解具有重要启示： （1）LP问题的解一般有唯一解、无穷多最优解、无界解和无可行解四种情况。 （2）LP问题的可行域一般为无界或有界凸多边形。 （3）若LP问题的最优解存在，即有唯一最优解或无穷多最优解，则必在可行域的某个项点上找到最优解。 （4）若LP问题有两个最优解，则在它们的连线上的任意一点都是最优解。,作业：教材第37页，1.3：(1)、(2)、(3)；1.4,2019/8/13,37,一、线性规划数学模型的标准型,第三节 线性规划问题数学模型的标准形式,1、标准型表达方式,(1)代数式：,(2)向量式：,(3)矩阵式：,A：技术系数矩阵，简称系数矩阵； B：可用的资源量，称资源向量； C：决策变量对目标的贡献，称价值向量； X：决策向量。,2019/8/13,38,通常X记为： ，其中，为约束方程的系数矩阵，m是约束方程的个数，n是决策变量的个数，一般情况mn，且r()m。,其中:,2019/8/13,39,2、一般型标准型的转换方法,(1) “决策变量非负”。若某决策变量 xk 为“取值无约束”(无符号限制)，令：xk = xk x”k ，(xk0, x”k 0) 。 (2) “目标函数求最大值”。如果极小化原问题minZ = CX，则令 Z = Z，转为求 maxZ = CX 。 注意：求解后还原。 (3) “约束条件为等式”。对于 “”型约束，则在“”左端加上一个非负松弛变量(slack variable) ，使其为等式。 对于“”型约束，则在“”左端减去一个非负剩余变量(Surplus variable) ，使其为等式。 (4) “资源限量非负”。若某个 bi 0，则将该约束两端同乘 “1” ，以满足非负性的要求。,2019/8/13,40,【例】将下列线性规划化为标准型？,【解】(1)因为 x3 无符号要求(取值无约束) ，x3可以取正值也可取负值，但标准型中要求变量非负，所以可令：,对于x10 ，可令：,2019/8/13,41,(3) 第二个约束条件是“”号，在“”左端减去剩余变量x5，x50， x5也称松驰变量,(2) 第一个约束条件是“”号，在“”左端加入松驰变量 x4，x40，化为等式；,(4) 第三个约束条件右端常数项为负数，因此在不等式两端乘以“1”。,(5) 目标函数是最小值，令Z=Z,得到max Z= max(Z)，即当Z达到最小值时Z达到最大值，反之亦然。,(1) x3 取值无约束 ，令 x3 = x3 x3，x3, x3 0。 同时,2019/8/13,42,标准型为：,2019/8/13,43,【练习】将下列线性规划化为标准型？,【解】(1)因为 x3 无符号要求(取值无约束) ，即x3取正值也可取负值，但标准型中要求变量非负，所以可令：,2019/8/13,44,(3) 第二个约束条件是“号”，在“号”左端减去剩余变量x5，x50， x5也称松驰变量,(2) 第一个约束条件是“号”，在“”左端加入松驰变量 x4，x40，化为等式；,(4) 第三个约束条件是“号”且常数项为负数，因此在“”左边加入松驰变量x6，x60，同时不等式两端乘以“1”。,(5) 目标函数是最小值，令Z=Z,得到max Z= max(Z)，即当Z达到最小值时Z达到最大值，反之亦然。,(1) x3 取值无约束 ，令 x3 = x3 x3，x3, x3 0。,作业：教材第38页，1.5：(1)、(2)、(3),2019/8/13,45,【练习】将下列线性规划化为标准型？(教材第38页，1.5),【解】先将模型变换成一般形式：,标准型：,2019/8/13,46,第四节 线性规划问题解的一般性质,1、线性规划解的概念,基矩阵：一个非奇异的子矩阵（线性无关）。 矩阵A 中任意一个 m 列的线性无关子矩阵 B ，称为一个基(矩阵)。 组成基的列向量称为基向量，用 Pj 表示 ( i = 1 , 2 , , m ) 。 基变量： 与基向量 Pj 相对应的变量 xj 称为基变量。 其余的 n m 个变量称为非基变量(基矩阵以外的列向量对应变量)。,基(本)解：令所有非基变量等于零，得出的唯一解。,2019/8/13,47,重要概念,可行解：满足约束条件AX=b和X0的解。 基(本)解：令所有非基变量等于零，得出的唯一解。 基(本)可行解：满足X0的基解。 可行基：基可行解对应的基矩阵。 最优解：使目标函数最优的基可行解，称为最优解。 最优基：最优解对应的基矩阵，称为最优基。,2019/8/13,48,基的概念,假设线性规划问题模型系数矩阵为m行、n列，则系数矩阵中秩为m的m行m列子矩阵，称为基矩阵，简称为基。,基中的列向量对应的变量称为基变量，决策变量中基变量以外的变量称为非基变量。,2019/8/13,49,基本解,对于某一确定的基，令所有非基变量为0，由约束方程组AX=b可解出m个基变量的唯一解，称为一个基本解。,2019/8/13,50,基本可行解,满足非负条件的基本解，称为基本可行解，基本可行解对应于凸多边形的项点。,2019/8/13,51,练习：已知线性规划问题4.2,问：,中哪一个是基本可行解？,2019/8/13,52,二、线性规划问题解的性质,1、凸集和极点(顶点)的概念,由约束条件形成的可行域是凸多边形(凸集) 凸集：对于某一集合内部任意两点连线上的点都属于这个集合，我们就称这个集合为凸集(直观理解)。,可行域具有有限个顶点。 目标函数最优值一定在可行域的边界(顶点)达到，而不可能在其区域的内部。,2019/8/13,53,凸集的数学定义,设K为n维欧氏空间的一个点集，若K中任意两个点X1和X2连线上的所有点都属于K，则称K为凸集。,X2,X1,X,设X(x1,x2,xn); X1(u1,u2,un); X2(v1,v2,vn),2019/8/13,54,极点： 设S为凸集，若S中的点x不能成为S中任何线段的内点，即“不能用S中两个不同的点线性表示”，则称x为S的极点。,2019/8/13,55,定理1.1 若线性规划问题的可行域非空，则S为凸集(有界或无界)。即连接任意两个可行解的线段上的点仍为可行解。 定理1.2 线性规划问题的可行域S中的点X是极点的充要条件是X是基本可行解。即凸多边形的顶点就是基本可行解。 定理1.3 若可行域有界，线性规划的目标函数一定可以在可行域的顶点上达到最优。 如果线性规划问题有最优解，则最优解一定在可行域S的某个极点上得到。,2019/8/13,56,第五节 单纯形法原理,一、线性规划问题的解题思路,首先，找到一个初始基可行解，也就是找到一个初始可行基，想办法判断这个基可行解是不是最优解。 如果是最优解，就得到这个线性规划问题的最优解； 如果判断出不是最优解，就想法由这个可行基按一定规则变化到下一个可行基，然后再判断新得到的基可行解是不是最优解； 如果还不是，再接着进行下一个可行基变化，直至找到最优解。,2019/8/13,57,求解线性规划问题的思路单纯形法,2019/8/13,58,一、用消化法求解线性规划问题（教材第20页例题）,解：(一)标准化：,(二)求初始基可行解,2019/8/13,59,令非基变量：x1=x2=0， 得到初始基可行解： X(0)=(0,0,4,3,8)T,此时，目标函数值： Z(0) = 2x1 + 5x2 + 0 = 0 目标函数用非基变量表示。,(三)判优,对于Z(0) = 2x1 + 5x2 ，若x1或x2从0变为正数，则目标函数值会增加，因此可判断X(0)一定不是最优解。 (X(0) X*),2019/8/13,60,Z(0) = 2x1 + 5x2,(四)方案调整(换基),寻找一个新的基可行解，使目标函数值得到改善。,选择入基变量 寻找使目标函数增加量最大的非基变量入基，即目标函数中系数最大的变量。(x2),选择出基变量 为什么要选择原基变量出基？,要求决策变量非负，因此有：,说明x2最大可以是3，且当x2=3时，x4=0，即x4出基 。 ( x4),2019/8/13,61,(五)求新的基可行解,此时，基变量为x3、x2和x5，非基变量为x1和x4。,用非基变量表示基变量： 用x4表示x2，x2 = 3 x4 ， 用x4表示x5，x5 = 2 x1 2x4 。,令非基变量 x1 = x4 = 0，则 X(1) = (0, 3, 4, 0, 2)T 。,2019/8/13,62,(六)判优(检验),将式(4)代入目标函数，目的：用非基变量表示目标函数，得到新的目标函数值： Z(1) = 2x1 + 5x2 = 2x1 + 5(3 x4) = 2x1 5x4 + 15,非基变量x1的系数为2，大于零，可见，如果x1 能从非基变量变为基变量，即变为正数，则目标函数值会增加，因此X(1) = (0, 3, 4, 0, 2)T 不是最优解。,2019/8/13,63,Z(1) = 2x1 5x4 + 15,(七)换基,当x1 = 2时，x5 = 0,即：当x1 入基，x5 出基。,2019/8/13,64,(八)求新的基可行解,此时，基变量为x3、x2和x1，非基变量为x4和x5。,用非基变量表示基变量： x1 = 2 + 2x4 x5 ， x3 = 2 2x4 + x5 。,令非基变量 x4 = x5 = 0，则 X(2) = (2, 3, 2, 0, 0)T 。,2019/8/13,65,松弛变量x3 = 2,说明第一项资源有剩余，资源相对宽松，这就是松驰变量的经济含义。,(九)判优(检验),非基变量x4和x5的系数均为负值，如果x4 和x5从非基变量变为基变量，即从零变为正数，则目标函数值会减少，因此X(2) = (2, 3, 2, 0, 0)T 是最优解，目标函数最优值Z* = 19。,2019/8/13,66,求解过程(换基迭代过程),初始基,初始基可行解：X(0)=(0,0,4,3,8)T Z(0) =0,新的基可行解：X(1)=(0,3,4,0,2)T Z(1) =15,新的可行基,最优基,最优解：X* = (2,3,2,0,0)T Z* =19,2019/8/13,67,单纯形法原理-矩阵推导(1),2019/8/13,68,单纯形法原理-矩阵推导(2),非基变量检验数,令非基变量等于0，则,2019/8/13,69,单纯形法原理(单纯形表),2019/8/13,70,单纯形法求解线性规划问题的步骤：,(1)求出初始基本可行解(标准化、单位基)；,(2)最优性检验(非基变量检验数非正时停止，否则进入下一步)；,(3)换基(迭代)； 确定入基变量 确定出基变量 初等变换，求出新的基本可行解,(4)重复步骤(2)、(3)，直到求出最优解。,2019/8/13,71,单纯形法求解步骤举例,maxZ = 2x1 + 5x2 +0x3 +0x4+0x5 x1 + x3 = 4 x2 + x4 = 3 x1 + 2x2 + x5 = 8 xj0, j = 1, 2, , 5,2019/8/13,72,最优解: X*=(2,3,2,0,0)T，Z*=19,思考: 在最终单纯形表中，B-1 = ？4.8,2019/8/13,73,单纯形法的管理启示,x1= 4,x1 + 2x2 = 8,X(0) =(0, 0, 4, 3, 8)T,X(1) =(0, 3, 4, 0, 2)T,X(2) =(2, 3, 2, 0, 0)T,在管理过程中，把现有方案作为初始方案，找到最急需要改进的某个问题和改进方向，一次做好某个主要问题的解决与改进；一次只解决和改进一个问题的难度最小；解决之后，再寻求可以改进的其它地方，再次改进，不断地追求更优。,2019/8/13,74,解：引入松驰变量x3, x4 , x5 ，化为标准形式：,2019/8/13,75,由于x1，x2的检验数均为非负，且x2的检验数2最大，选x2为入基变量；再按最小比值l = min(-, 3/1, 8/2) = 3，选x4为出基变量。,x2,5,2,1,0,0,-2,1,2,0,0,-5,0,15,2019/8/13,76,由于x1检验数为非负，选x1为入基变量；再按最小比值 l = min（4/1, -, 2/1）=2，选x5为出基变量。,x1,2,2,0,0,1,2,-1,0,0,0,-1,-2,19,2019/8/13,77,初始基本可行解：X(0) = (0, 0, 4, 3, 8)T，Z(0) = 0,新的基本可行解：X(1) = (0, 3, 4, 0, 2)T，Z(1) = 15,新的基本可行解：X(2) = (2, 3, 2, 0, 0)T，Z(2) = 19,判别定理 1： 在单纯形表中，若所有非基变量的检验数小于零，且B-1b均为非负，则线性规划问题具有唯一最优解。,2019/8/13,78,图解法与单纯形法求解结果对照：,A (0, 0),A：X(0) = (0, 0, 4, 3, 8)T，Z(0) = 0,B (0, 3),B：X(1) = (0, 3, 4, 0, 2)T，Z(1) = 15,C,C：X * = (2, 3, 2, 0, 0)T，Z* = 19,D (4, 2),E (4, 0),2019/8/13,79,课堂练习 求解下列线性规划问题,解：引进松驰变量x3, x4, x5，化为标准形式：,2019/8/13,80,x2,4,2,-1/2,1,1/2,0,0,6,2,0,-1,1,0,4,1/2,0,1/2,0,1,4,0,-2,0,0,8,2019/8/13,81,x1,2,3,1,0,-1/2,1/2,0,0,1,1/4,1/4,0,7/2,0,0,3/4,-1/4,1,5/2,0,0,-2,0,20,0,2019/8/13,82,x3,0,10/3,0,0,1,-1/3,4/3,8/3,0,1,0,1/3,-1/3,14/3,1,0,0,1/3,2/3,0,0,-2,0,0,20,2019/8/13,83,初始基本可行解：X(0) = (0, 0, 4, 10, 2)T，Z(0) = 0,新的基本可行解：X(1) = (0, 2, 0, 6, 4)T，Z(1) = 8,新的基本可行解：X(2) = (3, 7/2, 0, 0, 5/2)T，Z(2) = 20,新的基本可行解：X(3) = (14/3, 8/3, 10/3, 0, 0)T，Z(3) = 20,判别定理 2：在单纯形表中，若所有非基变量的检验数小于等于零，且B-1b均为非负，其中某个检验数等于零，则线性规划问题具有无穷多最优解(多重最优解)。,2019/8/13,84,图解法求解结果：,A (0, 0),A：X(0) = (0, 0, 4, 10, 2)T，Z(0) = 0,B (0, 2),B：X(1) = (0, 2, 0, 6, 4)T，Z(1) = 8,C (3,7/2),C：XC* = (3, 7/2, 0, 0, 5/2)T，Z* = 20,D (14/3, 8/3),E (2, 0),D：XD* = (14/3, 8/3, 10/3, 0, 0)T，Z* = 20,2019/8/13,85,例 求解下列线性规划问题,解：引进松驰变量x3, x4，标准化：,2019/8/13,86,不满足出基变量确定法则：,虽然，不能确定x3和x4中哪个变量出基，但无论哪个变量出基，都必须满足： x30，x40。x2入基，则： x2 0 (x20) 。,说明x2可以无限增大，所以目标函数值可以无限增大。,2019/8/13,87,图解法求解结果：,判定定理3：,在单纯形表中，若某个检验数k 大于零，且xk对应列向量的元素均为非正，导致出基变量无法确定，则线性规划问题具有无界解。,2019/8/13,88,练习 求解下列线性规划问题,解：引进松驰变量x3, x4，化为标准形式：,从标准形中可看出存在可行基B=(P3，P4)=I，基变量为X3，X4；非基变量为X1，X2。建立初始单纯形表得：,2019/8/13,89,由于x1，x2的检验数均为非负，且x1的检验数绝对值最大，选取x1为进基变量；再按最小比值=min（24/2，26/3）=26/3，选取x4为出基变量，进行换基迭代。,2019/8/13,90,表中最后一行的所有检验数均为非正，表明目标函数已达到最大值，上表为最优单纯形表。从表中可得到最优解为：X*=(x1, x2, x3, x4)T = (6, 4, 0, 0)T，最优值为：Z*=36。,作业：教材39页，1.8第(1),(4)题,在最终单纯形表中，所有非基变量检验数均为负数，说明该线性规划问题具有唯一最优解：X= (6, 4, 0, 0)T，Z*=36。,2019/8/13,91,练习：已知某线性规划用单纯形法求得的某两步迭代表如下，请将表中空白处填上适当的数字。,2019/8/13,92,讨论：用单纯形法求解某极大化问题的单纯形表如下，问表中参数 a1, a2, a3, d, 1, 2 为何取值范围时，下列结论成立。,(1)表中解为唯一最优解： (2)表中解为无穷多最优解： (3)该问题具有无界解： (4)表中解为退化的基解： (5)表中解为不可行解： (6) x1入基，x6出基：,10, 20, 12 = 0, d 0,1 0, 2 0, d 0,2 0, a1 0, d 0,d = 0,d 0,1 0, a3 0 , d 0, d /4 3/a3,2019/8/13,93,思考题： 已知线性规划问题：,其中b1, b2是常数，且已知此问题的最终单纯形表如下。试确定表中所有的参数及b1和b2的值？,e = 0, d = 5, b = 5, c = 10, a = 23, b1= 30, b2= 40,2019/8/13,94,思考题：已知线性规划问题的最优单纯形表如下，求初始单纯形表中参数C, A, b 以及最优基B ？,2019/8/13,95,解法(一)：矩阵初等行变换,增广矩阵：,求A和b：,2019/8/13,96,求cj：,最优基？,2019/8/13,97,解法(二)： 用B-1求解,2019/8/13,98,求C和b：,2019/8/13,99,求解结果：,2019/8/13,100,大M法（大M单纯形法）,通过添加人工变量构成单位基，进而求解线性规划问题的方法。,2019/8/13,101,例 求解下列线性规划问题,解：引进松驰变量x4, x5，化为标准形式：,2019/8/13,102,加入变量x6, x7，加入参数M，M为任意大的正数,2019/8/13,103,x3,-1,10,3,-2,0,1,0,0,-1,1,0,1,0,0,-1,1,-2,1,-1+M,0,0,-M,0,1-3M,2019/8/13,104,x2,-1,12,3,0,0,1,-2,2,-5,1,-2,0,1,0,0,0,1,1,0,0,0,-1,1-M,-1-M,2019/8/13,105,x1,3,4,1,0,0,1/3,-2/3,2/3,-5/3,9,0,0,1,2/3,-4/3,4/3,-7/3,0,0,0,-1/3,-1/3,1/3-M,2/3-M,2,X*= (4, 1, 9, 0, 0, 0, 0)T,Z*= 2,2019/8/13,106,大M法求解的可能结果：,(1)基变量中不含人工变量；,(2)基变量中含人工变量，但人工变量取值为零；,(3)基变量中含人工变量，但人工变量取值不为零；,只在前两种情况下，线性规划问题有最优解，对于第三种情况，线性规划问题无可行解。,2019/8/13,107,例,2019/8/13,108,x1,30,2,0,0,-1,-1,0,0,1,6,0,2,-3,0,0,1,0,2019/8/