运筹学ppt课件Ch1线性规划

制作与教学,武汉理工大学,管理学院 熊伟,Chapter 1 线性规划,Linear Programming,Page,97,*,运筹学,Operations Research,Chapter 1 线性规划,Linear Programming,1.1,LP的数学模型,Mathematical Model of LP,1.2,图解法,Graphical Method,1.3,标准型,Standard form of LP,1.4,基本概念,Basic Concepts,1.5,单纯形法,Simplex Method,10/7/2024,1.1,数学模型,Mathematical Model,10/7/2024,1.1 线性规划的数学模型,Mathematical Model of LP,线性规划,（Linear Programming,缩写为LP）,通常研究资源的最优利用、设备最佳运行等问题。例如，当任务或目标确定后，如何统筹兼顾，合理安排，用最少的资源 （如资金、设备、原标材料、人工、时间等）去完成确定的任务或目标；企业在一定的资源条件限制下，如何组织安排生产获得最好的经济效益（如产品量最多 、利润最大）。,10/7/2024,【例1-1】生产计划问题。某企业在计划期内计划生产甲、乙两种产品。按工艺资料规定，每件产品甲需要消耗材料A 2公斤，消耗材料B 1公斤，每件产品乙需要消耗材料A 1公斤，消耗材料B 1.5公斤。已知在计划期内可供材料分别为40、30公斤；每生产一件甲、乙两产品，企业可获得利润分别为300、400元，如表11所示。假定市场需求无限制。企业决策者应如何安排生产计划，使企业在计划期内总的利润收入最大。,1.1 线性规划的数学模型,Mathematical Model of LP,1.1.1 应用模型举例,10/7/2024,【解】设,x,1,、,x,2,分别为甲、乙产品的产量，数学模型为：,1.1 线性规划的数学模型,Mathematical Model of LP,产品,资源,甲,乙,现有资源,材料A,2,1,40,材料B,1,1.5,30,利润（元/件）,300,400,表1-1,10/7/2024,线性规划的数学模型由,决策变量,Decision variables,目标函数,Objective function,及约束条件,Constraints,构成。称为三个要素,。,其特征是：,1,解决问题的目标函数是多个决策变量的,线性函数，通常是求最大值或 最小值；,2,解决问题的,约束条件,是一组多个决策变量,的线性不等式或等式。,怎样辨别一个模型是线性规划模型？,1.1 线性规划的数学模型,Mathematical Model of LP,10/7/2024,【例1-2】某商场决定：营业员每周连续工作5天后连续休息2天，轮流休息。根据统计，商场每天需要的营业员如表1-2所示。,表1,-2,营业员需要量统计表,商场人力资源部应如何安排每天的上班人数，使商场总的营业员最少。,星期,需要人数,星期,需要人数,一,300,五,480,二,300,六,600,三,350,日,550,四,400,1.1 线性规划的数学模型,Mathematical Model of LP,10/7/2024,【解】 设,x,j,(,j,=1，2，7)为休息2天后星期一到星期日开始上班的营业员，则这个问题的线性规划模型为,1.1 线性规划的数学模型,Mathematical Model of LP,星期,需要人数,星期,需要人数,一,300,五,480,二,300,六,600,三,350,日,550,四,400,10/7/2024,【例1-3】合理用料问题。某汽车需要用甲、乙、丙三种规格的轴各一根，这些轴的规格分别是1.5，1，0.7（m），这些轴需要用同一种圆钢来做，圆钢长度为4 m。现在要制造1000辆汽车，最少要用多少圆钢来生产这些轴？,【解】这是一个条材下料问题 ，设切口宽度为零。 设一根圆钢切割成甲、乙、丙三种轴的根数分别为y,1,，y,2,，y,3,则切割方式可用不等式1.5,y,1,+,y,2,+0.7,y,3,4表示，求这个不等式关于y,1,，y,2,，y,3,的非负整数解。象这样的非负整数解共有,10,组，也就是有,10,种下料方式，如表,1-3,所示。,表,1-3,下料方案,方案,规格,1,2,3,4,5,6,7,8,9,10,需求量,y,1,(根),2,2,1,1,1,0,0,0,0,0,1000,y,2,1,0,2,1,0,4,3,2,1,0,1000,y,3,0,1,0,2,3,0,1,2,4,5,1000,余料（m）,0,0.3,0.5,0.1,o.4,0,0.3,0.6,0.2,0.5,1.1 线性规划的数学模型,Mathematical Model of LP,10/7/2024,设,x,j,(,j,=1,2,10)为第,j,种下料方案所用圆钢的根数。则用料最少数学模型,为:,求下料方案时应注意，余料不能超过最短毛坯的长度；最好将毛坯长度按降的次序排列，即先切割长度最长的毛坯，再切割次长的，最后切割最短的，不能遗漏了方案 。如果方案较多，用计算机编程排方案，去掉余料较长的方案，进行初选。,1.1 线性规划的数学模型,Mathematical Model of LP,方案,规格,1,2,3,4,5,6,7,8,9,10,需求量,y,1,(根),2,2,1,1,1,0,0,0,0,0,1000,y,2,1,0,2,1,0,4,3,2,1,0,1000,y,3,0,1,0,2,3,0,1,2,4,5,1000,余料（m）,0,0.3,0.5,0.1,o.4,0,0.3,0.6,0.2,0.5,10/7/2024,1.1.2,线性规划的一般模型,一般地，假设线性规划数学模型中，有,m,个约束，有,n,个决策变量,x,j,j,=1,2,n,，目标函数的变量系数用,c,j,表示,c,j,称为,价值系数,。约束条件的变量系数用,a,ij,表示，,a,ij,称为,工艺系数,。约束条件右端的常数用,b,i,表示，,b,i,称为,资源限量,。则线性规划数学模型的一般表达式可写成,为了书写方便，上式也可写成：,1.1 线性规划的数学模型,Mathematical Model of LP,10/7/2024,在实际中一般,x,j,0,但有时,x,j,0或,x,j,无符号限制。,1.1 线性规划的数学模型,Mathematical Model of LP,10/7/2024,1.什么是线性规划，掌握线性规划在管理中的几个应用例子,2.线性规划数学模型的组成及其特征,3.线性规划数学模型的一般表达式。,作业：教材习题 1.11.6,1.1 线性规划的数学模型,Mathematical Model of LP,下一节：图解法,10/7/2024,1.2 图解法,Graphical Method,10/7/2024,x,1,x,2,O,10,20,30,40,10,20,30,40,(300,400),(15,10),最优解,X,=(15,10),最优值,Z,=8500,例1-7,1.2 图解法,The Graphical Method,10/7/2024,2,4,6,x,1,x,2,2,4,6,最优解,X,=(3,1),最优值,Z,=5,(3,1),min,Z,=,x,1,+2,x,2,例1-8,(1,2),1.2 图解法,The Graphical Method,10/7/2024,2,4,6,x,1,x,2,2,4,6,X,（2）,（3,1）,X,（1）,（1,3）,(5,5),min,Z,=,5,x,1,+,5,x,2,例1-9,有无穷多个最优解,即具有多重解,通解为,01,当=0.5时,=(,x,1,x,2,)=0.5(1,3)+0.5(3,1)=(2,2),1.2 图解法,The Graphical Method,10/7/2024,2,4,6,x,1,x,2,2,4,6,(1,2),无界解(无最优解),max,Z,=,x,1,+2,x,2,例1-10,1.2 图解法,The Graphical Method,10/7/2024,x,1,x,2,O,10,20,30,40,10,20,30,40,50,50,无可行解,即无最优解,max Z=10,x,1,+4,x,2,例1-11,1.2 图解法,The Graphical Method,10/7/2024,由以上例题可知，线性规划的解有4种形式,：,1.有唯一最优解(例1-7例1-8),2.有多重解(例1-9),3.有无界解(例1-10),4.无可行解(例1-11),1、2情形为有最优解,3、4情形为无最优解,1.2 图解法,The Graphical Method,10/7/2024,图解法的步骤：,1.求可行解集合。,分别求出满足每个约束包括变量非 负要求的区域，其交集就是可行解集合，或称为,可行域,；,2.绘制目标函数图形。,先过原点作一条矢量指向点（,c,1,c,2,)，矢量的方向就是目标函数增加的方向，称为梯度方向，再作一条与矢量垂直的直线，这条直线就是目标函数图形；,3.求最优解。,依据目标函数求最大或最小移动目标函数直线，直线与可行域相交的点对应的坐标就是,最优解。,一般地，将目标函数直线放在可行域中,求最大值时直线沿着矢量方向移动,求最小值时沿着矢量的反方向移动,1.2 图解法,The Graphical Method,10/7/2024,1.通过图解法了解线性规划有几种解的形式,2.作图的关键有三点,(1)可行解区域要画正确,(2)目标函数增加的方向不能画错,(3)目标函数的直线怎样平行移动,作业：教材习题 1.7,1.2 图解法,The Graphical Method,下一节：线性规划的标准型,10/7/2024,1.3,线性规划的标准型,Standard form of LP,10/7/2024,在用单纯法求解线性规划问题时，为了讨论问题方便，需将线性规划模型化为统一的标准形式。,1.3 线性规划的标准型,Standard form of LP,线性规划问题的标准型为:,1目标函数求最大值（或求最小值）,2约束条件都为等式方程,3变量,x,j,非负,4常数,b,i,非负,10/7/2024,max(或min,)Z=c,1,x,1,+c,2,x,2,+,+,c,n,x,n,1.3 线性规划的标准型,Standard form of LP,注：本教材默认目标函数是 max,10/7/2024,或写成下列形式,：,或用矩阵形式,1.3 线性规划的标准型,Standard form of LP,10/7/2024,通常X记为：,称为约束方程的系数矩阵，,m,是约束方程的个数，,n,是决策变量的个数，一般情况,m,n,，且,r,(),m,。,其中:,1.3 线性规划的标准型,Standard form of LP,10/7/2024,【例1-12】将下列线性规划化为标准型,【解】（）因为,x,3,无符号要求 ，即,x,3,取正值也可取负值，标准型中要求变量非负，所以令,1.3 线性规划的标准型,Standard form of LP,10/7/2024,(3)第二个约束条件是号，在号 左端减去剩余变量(Surplus variable),x,5,，,x,5,0。也称松驰变量,1.3 线性规划的标准型,Standard form of LP,(2) 第一个约束条件是号，在左端加入松驰变量 (slack variable),x,4,，,x,4,0,化为等式；,(4)第三个约束条件是号且常数项为负数，因此在左边加入松驰变量,x,6,，,x,6,0，同时两边乘以1。,（5）目标函数是最小值，为了化为求最大值，令Z,=Z,得到max Z,=Z，即当Z达到最小值时Z,达到最大值，反之亦然。,10/7/2024,综合起来得到下列标准型,1.3 线性规划的标准型,Standard form of LP,10/7/2024,当某个变量,x,j,0时,令,x,/,j,=,x,j,。 当某个约束是绝对值不等式时，将绝对值不等式化为两个不等式，再化为等式，例如约束,将其化为两个不等式,再加入松驰变量化为等式。,1.3 线性规划的标准型,Standard form of LP,10/7/2024,【,例,1-13,】将下例线性规划化为标准型,【,解】,此题关键是将目标函数中的绝对值去掉。,令,则有,1.3 线性规划的标准型,Standard form of LP,10/7/2024,得到线性规划的标准形式,1.3 线性规划的标准型,Standard form of LP,对于,a,x,b,(,a,、,b,均大于零)的有界变量化为标准形式有两种方法。,一种方法是增加两个约束,x,a,及,x,b,另一种方法是令,x,=x,a,，则,a,x,b,等价于0,x,b,a,，增加一个约束,x,b,a,并且将原问题所有,x,用,x,=,x,+,a,替换。,10/7/2024,1.如何化标准形式？,可以对照四条标准逐一判断！,标准形式是人为定义的，目标函数可以是求最小值。,2.用WinQSB软件求解时，不必化成标准型。,图解法时不必化为标准型。,3.单纯形法求解时一定要化为标准型。,作业：教材习题 1.8,1.3 线性规划的标准型,Standard form of LP,下一节：基本概念,10/7/2024,1.4,线性规划的有关概念,Basic Concepts of LP,10/7/2024,设线性规划的标准型,max,Z=CX,（1.1）,AX=b,（1.2）,X,0 （1.3）,式中,A,是,m,n,矩阵，,m,n,并且,r,（,A,）=,m,，显然,A,中至少有一个,m,m,子矩阵,B,，使得,r,（,B,）=,m,。,1.4 基本概念,Basic Concepts,基,(,basis),A,中,m,m,子矩阵,B,并且有,r,（,B,）=,m,，则称,B,是线性规划的一个基（或基矩阵basis matrix ）。当,m,=,n,时，基矩阵唯一，当,m,n,时，基矩阵就可能有多个，但数目不超过,10/7/2024,【例1-14】线性规划,求所有基矩阵,。,【解】约束方程的系数矩阵为25矩阵,容易看出,r,(A)=2，2阶子矩阵有C,5,2,=10个，其中第1列与第3列构成的2阶矩阵不是一个基，基矩阵只有9个，即,1.4 基本概念,Basic Concepts,10/7/2024,由线性代数知，基矩阵,B,必为非奇异矩阵并且|,B,|0。当矩阵,B,的行列式等式零即|,B,|=0时就不是基,当确定某一矩阵为基矩阵时，则基矩阵对应的列向量称为,基向量,(basis vector)，其余列向量称为,非基向量,基向量对应的变量称为,基变量,(basis variable)，非基向量对应的变量称为,非基变量,在上例中,B,2,的基向量是A中的第一列和第四列，其余列向量是非基向量，,x,1,、,x,4,是基变量，,x,2,、,x,3,、,x,5,是非基变量。基变量、非基变量是针对某一确定基而言的，不同的基对应的基变量和非基变量也不同。,1.4 基本概念,Basic Concepts,10/7/2024,可行解,(feasible solution),满足式（1.2）及（1.3）的解,X,=（,x,1,x,2,，,x,n,),T,称为可行解 。,基本可行解,(basis,feasible solution),若基本解是可行解则称为是基本可行解（也称基可行解）。,例如， 与,X,=（0，0，0，3，2，）都是例1 的可行解。,基本解,(basis solution) 对某一确定的基,B,，令非基变量等于零，利用式（1.） 解出基变量，则这组解称为基,的基本解。,最优解,(optimal solution) 满足式 （1 .1）的可行解称为最优解，即是使得目标函数达到最大值的可行解就是最优解，例如可行解 是例2的最优解。,非可行解,(Infeasible solution),无界解,(unbound solution),1.4 基本概念,Basic Concepts,10/7/2024,显然，只要基本解中的基变量的解满足式（1.）的非负要求，那么这个基本解就是基本可行解。,在例1-13中，对,来说，,x,1,x,2,是基变量，,x,3,x,4,，,x,5,是非基变量，令,x,3,=,x,4,=,x,5,=0，则式（1.）为,对,B,2,来说，,x,1,x,4,为基变量，令非基变量,x,2,x,3,x,5,为零，由式,（1.2）得到,，,x,4,=4，,因|B,1,|，由克莱姆法则知，,x,1,、,x,2,有唯一解,x,1,2/5,x,2,=1,则 基本解为,1.4 基本概念,Basic Concepts,10/7/2024,由于 是基本解，从而它是基本可行解，在 中,x,1,0,因此不是可行解，也就不是基本可行解。,反之，可行解不一定是基本可行解,例如 满足式（1.2）（1.3），但不是,任何基矩阵的基本解。,基本解为,1.4 基本概念,Basic Concepts,10/7/2024,可行基,基可行解对应的基称为可行基；,最优基,基本最优解对应的基称为最优基；,如上述,B,3,就是最优基，最优基也是可行基。,当最优解唯一时，最优解亦是基本最优解，当最优解不唯一时，则最优解不一定是基本最优解。例如右图中线段 的点为最优 解时，Q,1,点及Q,2,点是基本最优解,线段 的内点是最优解而不是基本最优解。,基本最优解,最优解是基本解称为基本最优解。例如，满足式（1.1）(1.3)是最优解,又是,B,3,的基本解,因此它是基本最优解。,1.4 基本概念,Basic Concepts,10/7/2024,基本最优解、最优解、基本可行解、基本解、可行解的关系如下所示：,基本最优解,基本可行解,可行解,最 优 解,基本解,例如,B点和D点是可行解,不是基本解;C点是基本可行解;A点是基本最优解,同时也是最优解、基本可行解、基本解和可行解。,1.4 基本概念,Basic Concepts,10/7/2024,凸集,(Convex set)设,K,是,n,维空间的一个点集，对任意两点,时，则称,K,为凸集。,就是以,X,（1）,、,X,（2）,为端点的线段方程，点,X,的位置由的值确定，当=0时，,X,=,X,（2）,，当=1时,X=X,（1）,凸组合,(Convex combination),设 是,R,n,中的点若存在,使得 成立， 则称,X,为 的凸组合。,1.4 基本概念,Basic Concepts,10/7/2024,极点,(Extreme point),设,K,是凸集， ，若,X,不能用,K,中两个不同的 点 的凸组合表示为,),1,0,(,),1,(,),2,(,),1,(,0,i,表1-6,(,a,),X,B,x,1,x,2,x,3,x,4,b,x,3,2,1,1,0,40,x,4,1,3/2,0,1,30,j,300,400,0,0,(,b,),x,3,x,2,j,(,c,),x,1,x,2,10,j,基变量,1,20,0,0,2/3,0,2/3,20,4/3,1,-,2/3,40,100/3,0,-,800/3,30,1,0,3/4,-,1/2,15,0,1,-,1/2,1,10,0,0,-,25,-,250,将3/2化为1,1.5 单纯形法,Simplex Method,20,15,10/7/2024,最优解X=(15，10，0，0),T,，最优值Z=8500,X,(1),=(0,0),x,1,1.5 单纯形法,Simplex Method,x,1,x,2,O,10,20,30,40,10,20,30,40,X,(2),=(0,20),X,(3),=(15,10),10/7/2024,单纯形法全过程的计算，可以用列表的方法计算更为简洁，这种表格称为单纯形表（表1-6）。,计算步骤：,1.求初始基可行解，列出初始单纯形表，求出检验数。其中基变量的检验数必为零；,2.判断：,（a）若,j,（,j,，,n,）得到最优解；,（b）某个,k,0且,a,ik,（,i,=1，2,m,）则线性规划具有无界解(见例1-18)。,（c）若存在,k,0且,a,ik,(,i,=1,m,)不全非正，则进行换基；,1.5 单纯形法,Simplex Method,10/7/2024,第,个比值最小 ，选最小比值对应行的基变量为出基变量，若有相同最小比值，则任选一个。,a,Lk,为主元素；,(c）求新的基可行解：用初等行变换方法将,a,Lk,化为,k,列其它元素化为零（包括检验数行）得到新的可行基及基本可行解，再判断是否得到最优解。,（,b,）选出基变量 ，求最小比值：,1.5 单纯形法,Simplex Method,3.换基：,（,a,）选进基变量,设,k,=max ,j,| ,j,0,x,k,为进基变量,10/7/2024,【例1-16】 用单纯形法求解,【解】将数学模型化为标准形式：,不难看出,x,4,、x,5,可作为初始基变量，单纯法计算结果如表 1-7所示 。,1.5 单纯形法,Simplex Method,10/7/2024,C,j,1,2,1,0,0,b,C,B,X,B,x,1,x,2,x,3,x,4,x,5,0,x,4,2,3,2,1,0,15,0,x,5,1/3,1,5,0,1,20,j,1,2,1,0,0,0,x,4,2,x,2,j,1,x,1,2,x,2,j,表17,1/3,1,5,0,1,20,3,0,17,1,3,75,1/3,0,9,0,2,M,20,25,60,1,0,17/3,1/3,1,25,0,1,28/9,1/9,2/3,35/3,0,0,98/9,1/9,7/3,最优解X=(25，35/3，0，0，0),T,，最优值Z=145/3,1.5 单纯形法,Simplex Method,10/7/2024,【例,1-17,】用单纯形法求解,【解】,这是一个极小化的线性规划问题,可以将其化为极大化问题求解,也可以直接求解,这时判断标准是：,j,0(,j,=1,，,，,n,),时得到最优解,。,容易观察到,系数矩阵中有一个,3,阶单位矩阵,x,3,、,x,4,、,x,5,为基变量。目标函数中含有基变量,x,4,由第二个约束得到,x,4,=6+,x,1,x,2,，并代入目标函数消去,x,4,得,1.5 单纯形法,Simplex Method,10/7/2024,X,B,x,1,x,2,x,3,x,4,x,5,b,x,3,x,4,x,5,1,-,1,6,1,1,2,1,0,0,0,1,0,0,0,1,5,6,21,5,6,21/2,j,1,-,1,0,0,0,x,2,x,4,x,5,1,-,2,4,1,0,0,1,-,1,-,2,0,1,0,0,0,1,5,1,11,j,2,0,1,0,0,表中,j,0,j,=1,2,5所以最优解为X=(0,5,0,1,11,)最优值,Z=2,x,1,2,x,2,x,4,=251=11,极小值问题,注意判断标准,选进基变量时,应选,j,0,x,2,进基，而,a,12,0，,a,22,0且,a,ik,（,i,=1，2,m）则线性规划具有无界解,退化基本可行解的判断:,存在某个基变量为零的基本可行解。,1.5 单纯形法,Simplex Method,10/7/2024,在实际问题中有些模型并不含有单位矩阵，为了得到一组基向量和初基可行解，在约束条件的等式左端加一组虚拟变量，得到一组基变量。这种人为加的变量称为人工变量，构成的可行基称为人工基，用大M法或两阶段法求解，这种用人工变量作桥梁的求解方法称为人工变量法。,【例1-20】用大M法解 下列线性规划,1. 大M 单纯形法,大M和两阶段单纯形法,1.5 单纯形法,Simplex Method,10/7/2024,【解】首先将数学模型化为标准形式,式中,x,4,，,x,5,为松弛变量，,x,5,可作为一个基变量，第一、三约束中分别加入人工变量,x,6,、,x,7,，目标函数中加入M,x,6,M,x,7,一项，得到人工变量单纯形法数学模型,用前面介绍的单纯形法求解，见下表。,1.5 单纯形法,Simplex Method,10/7/2024,C,j,3,2,1,0,0,M,M,b,C,B,X,B,x,1,x,2,x,3,x,4,x,5,x,6,x,7,M0,M,x,6,x,5,x,7,4,1,2,3,1,2,1,2,1,1,0,0,0,1,0,1,0,0,0,0,1,4,10,1,j,3-2M,2+M,-1+2M,M,0,0,0,M,0,1,x,6,x,5,x,3,6,3,2,5,3,2,0,0,1,1,0,0,0,1,0,1,0,0,3,8,1,j,5-6M,5M,0,M,0,0,2,0,1,x,2,x,5,x,3,6/5,3/5,2/5,1,0,0,0,0,1,1/5,3/5,2/5,0,1,0,3/5,31/511/5,j,5,0,0,0,0,2,3,1,x,2,x,1,x,3,0,1,0,1,0,0,0,0,1,1,1,0,2,5/3,2/3,13,31/3,19/3,j,0,0,0,5,-25/3,10/7/2024,（2）初始表中的检验数有两种算法，第一种算法是利用第一、三约束将,x,6,、,x,7,的表达式代入目标涵数消去,x,6,和,x,7,，得到用非基变量表达的目标函数，其系数就是检验数；第二种算法是利用公式计算，如,最优解X（31/3，13，19/3，0，0),T,；最优值Z152/3,注意：,1.5 单纯形法,Simplex Method,(1) M是一个很大的抽象的数，不需要给出具体的数值，可以理解为它能大于给定的任何一个确定数值,10/7/2024,【例1-21】求解线性规划,【解】加入松驰变量,x,3,、,x,4,化为标准型,在第二个方程中加入人工变量,x,5,，目标函数中加上M,x,5,一项，得到,1.5 单纯形法,Simplex Method,10/7/2024,用单纯形法计算如下表所示。,C,j,5,8,0,0,M,b,C,B,X,B,x,1,x,2,x,3,x,4,x,5,0,M,x,3,x,5,3,1,1,2,1,0,0,1,0,1,6,4,j,5,M,8+2,M,0,M,0,5,M,x,1,x,5,1,0,1/3,7/3,1/3,1/3,0,1,0,1,2,2,j,0,29/3+7/3,M,5/3+1/3,M,M,0,1.5 单纯形法,Simplex Method,10/7/2024,表中,j,0，,j,=1，2，5，从而得到最优解X=（2，0，0，0，2）， Z=10+2,M,。但最优解中含有人工变量,x,5,0说明这个解是伪最优解，是不可行的，因此原问题无可行解。,两阶段单纯形法与大M单纯形法的目的类似，将人工变量从基变量中换出，以求出原问题的初始基本可行解。将问题分成两个阶段求解，第一阶段的目标函数,是,约束条件是加入人工变量后的约束方程，当第一阶段的最优解中没有人工变量作基变量时，得到原线性规划的一个基本可行解，第二阶段就以此为基础对原目标函数求最优解。,当第一阶段的最优解,w,0时，说明还有不为零的人工变量是基变量，则原问题无可行解。,1.5 单纯形法,Simplex Method,2. 两阶段单纯形法,10/7/2024,【例1-22】用两阶段单纯形法求解例19的线性规划。,【解】标准型为,在第一、三约束方程中加入人工变量,x,6,、,x,7,后，第一阶段问题为,用单纯形法求解，得到第一阶段问题的计算表如下：,1.5 单纯形法,Simplex Method,10/7/2024,C,j,0,0,0,0,0,1,1,b,C,B,X,B,x,1,x,2,x,3,x,4,x,5,x,6,x,7,1,0,1,x,6,x,5,x,7,4,1,2,3,1,2,1,2,1,1,0,0,0,1,0,1,0,0,0,0,1,4,10,1,j,2,1,2,1,0,0,0,1,0,0,x,6,x,5,x,3,6,3,2,5,3,2,0,0,1,1,0,0,0,1,0,1,0,0,3,8,1,j,6,5,0,1,0,0,0,0,0,x,2,x,5,x,3,6/5,3/5,2/5,1,0,0,0,0,1,1/5,3/5,2/5,0,1,0,3/5,31/5,11/5,j,0,0,0,0,0,1.5 单纯形法,Simplex Method,10/7/2024,最优解为 最优值,w,=0。第一阶段最后一张最优表说明找到了原问题的一组基可行解，将它作为初始基可行解，求原问题的最优解，即第二阶段问题为,1.5 单纯形法,Simplex Method,10/7/2024,C,j,3,2,-1,0,0,b,C,B,X,B,x,1,x,2,x,3,x,4,x,5,2,0,1,x,2,x,5,x,3,1,0,0,0,0,1,0,1,0,j,5,0,0,0,0,2,3,1,x,2,x,1,x,3,0,1,0,1,0,0,0,0,1,1,1,0,2,13,j,0,0,0,5,C,j,3,2,1,0,0,b,C,B,X,B,x,1,x,2,x,3,x,4,x,5,2,0,1,x,2,x,5,x,3,6/5,3/5,2/5,1,0,0,0,0,1,1/5,3/5,2/5,0,1,0,3/5,31/5,11/5,j,5 ,0,0,0,0,2,3,1,x,2,x,1,x,3,0,1,0,1,0,0,0,0,1,1,1,0,2,5/3,2/3,13,31/3,19/3,j,0,0,0,5,25/3,用单纯形法计算得到下表,最优解X（31/3，13，19/3，0，0),T,；最优值Z152/3,1.5 单纯形法,Simplex Method,10/7/2024,【例1-23】用两阶段法求解例1-21的线性规划。,【解】例1-21的第一阶段问题为,用单纯形法计算如下表：,1.5 单纯形法,Simplex Method,10/7/2024,C,j,0,0,0,0,1,b,C,B,X,B,x,1,x,2,x,3,x,4,x,5,0,1,x,3,x,5,3,1,1,2,1,0,0,1,0,1,6,4,j,1,2,0,1,0,0,1,x,1,x,5,1,0,1/3,7/3,1/3,1/3,0,1,0,1,2,2,j,0,7/3,1/3,1,0,j,0,得到第一阶段的最优解X=(2,0,0,0,2),T,最优目标值w=20,x,5,仍在基变量中,从而原问题无可行解。,1.5 单纯形法,Simplex Method,10/7/2024,解的判断,唯一最优解的判断,：最优表中所有非基变量的检验数非零,则线 规划具有唯一最优解,多重最优解的判断,:最优表中存在非基变量的检验数为零,则线则性规划具有多重最优解。,无界解的判断:,某个,k,0且,a,ik,（,i,=1，2,m）则线性规划具有无界解,退化基本可行解的判断:,存在某个基变量为零的基本可行解。,无可行解的判断：,(1)当用大M单纯形法计算得到最优解并且存在,R,i,0时，则表明原线性规划无可行解。,(2) 当第一阶段的最优值,w,0时，则原问题无可行解,。,1.5 单纯形法,Simplex Method,10/7/2024,设有线性规划,其中,A,m,n,且,r,(,A,)=,m,X,0应理解为,X,大于等于零向量，即,x,j,0,j,=1,2,n,。,1.5.3 计算公式,1.5 单纯形法,Simplex Method,10/7/2024,不妨假设,A,（,P,1,，,P,2,，,P,n,）中前,m,个列向量构成一个可行基，记为,B,=,(P,1,，,P,2,，,P,m,)。矩阵,A,中后,nm,列构成的矩阵记为,N,（,P,m,+1,P,n,）,则A可以写成分块矩阵,A,=（,B,，,N,）。对于基,B,，基变量为,X,B,=（,x,1,x,2,，,x,m,）,T, 非基变量为,X,N,=(,x,m,+1,x,m,+2,x,n,),T,。,则,X,可表示成 同理将,C,写成分块矩阵,C,=（,C,B,，,C,N,），,C,B,=(,C,1,C,2,C,m,),C,N,=(,C,m,+1,C,m,+2,，,c,n,) 则,AX=b,可写成,1.5 单纯形法,Simplex Method,10/7/2024,因为,r,（,B,）=,m,（或|,B,|0）所以,B,1,存在，因此可有,令非基变量,X,N,=0,，X,B,=,B,1,b,，由,B,是 可行基的假设，则得到基本可行解,X,=(,B,1,b,，0),T,将目标函数写成,1.5 单纯形法,Simplex Method,10/7/2024,得到下列五个计算公式：,(令,X,N,=0),1.5 单纯形法,Simplex Method,10/7/2024,上述公式可用下面较简单的矩阵表格运算得到，设初始矩阵单纯形表1-16,将,B,化为I（I为,m,阶单位矩阵）,C,B,化为零,即求基本可行解和检验数。用,B,1,左乘表中第二行,得到表1-17,X,B,X,N,b,X,B,I,B,-,1,N,B,-,1,b,C,j,-Z,j,C,B,C,N,0,X,B,X,N,b,X,B,B,N,b,C,j,-Z,j,C,B,C,N,0,表116,表117,1.5 单纯形法,Simplex Method,10/7/2024,再将第二行左乘,C,B,后加到第三行,得到,X,B,Z,0,X,B,X,N,b,X,B,I,B,-,1,N,B,-,1,b,C,j,-,Z,j,0,C,N,-,C,B,B,1,N,C,B,B,1,b,表118,1.5 单纯形法,Simplex Method,10/7/2024,五个公式的应用,【例1-24】线性规划,已知可行基,求(1)单纯形乘子; (2)基可行解及目标值; (3)求,3,;,(4),B,1,是否是最优基,为什么;,(5)当可行基为 时求,1,及,3,。,1.5 单纯形法,Simplex Method,10/7/2024,【解】(1)因为,B,1,由,A,中第一列、第二列组成,故,x,1,、,x,2,为基变量，,x,3,、,x,4,、,x,5,为非基变量,有关矩阵为,C,B,=(,c,1,c,2,)=(1,2),C,N,=(,c,3,c,4,c,5,)=(1,0,0),故单纯形乘子,1.5 单纯形法,Simplex Method,10/7/2024,(2)基变量的解为,故基本可行解为,目标函数值为,1.5 单纯形法,Simplex Method,10/7/2024,(3) 求,3,1.5 单纯形法,Simplex Method,10/7/2024,(4) 要判断,B,1,是不是最优基,亦是要求出所有检验数则否满足,j,0,j=1,5。,x,1,x,2,是基变量,故,1,=0,2,=0,而 剩下来求,4,5,，由,N,计算公式得,因,j,0,j,=1,5,故,B,1,是最优基。,1.5 单纯形法,Simplex Method,10/7/2024,(5) 因,B,2,是,A,中第四列与第二列组成的,x,4,、,x,2,是基变量,x,1,、,x,3,、,x,5,是非基变量,这时有,即,1.5 单纯形法,Simplex Method,10/7/2024,【例1-26】求解线性规划,解 用大M单纯形法，加入人工变量,x,4、,x,5，构造数学模型,1.5.4 退化与循环,1.5 单纯形法,Simplex Method,10/7/2024,C,j,1,2,1,M,M,b,C,B,X,B,x,1,x,2,x,3,x,4,x,5,(1),M,M,x,4,x,5,1,4,2,9,4,14,1,0,0,1,4,16,1,8/7,j,15M,2+11M,118M,0,0,(2),1,M,x,3,x,5,1/4,1/2,1/2,2,1,0,1/4,7/2,0,1,1,2,4,4,j,3