1、1,第五章 线性规划,线性规划模型 线性规划的图解 单纯形法原理 单纯形法 单纯形表 单纯形的理论分析 人工变量法,2,5.1 线性规划的数学模型,一、问题的提出例1：生产计划问题：,问：甲乙各生产多少，使企业利润最大？,3,解:设产品甲、乙各生产x1 ， x2公斤,设总利润为Z，则：,资源约束,变量非负约束,4,二、线性规划模型的一般特点,Max(Min) z=c1x1+c2x2+cnxna11x1+a12x2+a1nxn(=或)b1a21x1+a22x2+a2nxn(=或)b2 am1x1+am2x2+amnxn(=或)bmxj(j=1,n) () 0，或者没有限制,s.t.,cj为价值系
2、数,反映了客观限制条件。,明确的目标要求，极大或极小,行动方案,线性规划模型的一般形式：,1、决策变量：向量(x1 xn)T 2、目标函数：Z=(x1 xn)线性式， 3、约束条件：线性等式或不等式,变量约束,约束方程,5,表2：,例2：资源合理利用问题：某厂生产A、B两种产品，都需用煤、金属材料、电力等资源，各产品对三种资源的消耗及可供利用的资源如表2示：,问：应如何安排生产，使企业获利最大？,三、常用的线性规划模型,6,解：设产品A、B产量分别为变量x1 ， x2（吨），则：,7,例3、合理下料问题：有一批长度为180厘米的钢管，需截成70、52和35厘米3种管料。它们的需求量分别不少于1
3、00、150和100根。问如何下料才能使钢管的消耗量为最少？,先找出各种可能的下料方式：（再在各种可能的下料方案中去选择）设在180厘米长的钢管上能下出u个70厘米管料，v个52厘米管料， w个35厘米，则满足约束条件： 70u+52v+35w180，其中，u，v，w只能是正整数。从最大尺寸管料下起：,8,各种可能的下料方案：,9,2x1 + x2 +x3+x4 1002x2 +x3+ 3x5+2x6+x7 150x1 +x3+3x4+ x6+3x7+5x8100xi 0 (i =1,8)，且为整数,min Z= 5x1 + 6x223x3+5x4+24x5+6x6+23x7+5x8,解：设按
4、第j种方案下料的原材料为xj根,10,例4：运输问题,问：如何安排运输，使运输费用最小？,11,解：设xij为第i个矿山运到第j个冶炼厂的矿石量,MinZ=1.5x11+2x12+0.3x13+3x14+7x21+0.8x22+1.4x23+2x24+1.2x31+0.3x32+2x33+2.5x34 (万元),x11+x12+x13+x14=100 x21+x22+x23+x24=80 x31+x32+x33+x34=50 x11+x21+x31=50 x12+x22+x32=70 x13+x23+x33=80 x14+x24+x34=30 xij0(i=1,2,3。 j=1,2,3,4),
5、第i个矿山的产量,第j个冶炼厂的需求量,12,例5：投资方案选择问题（01规划）,13,又要求：方案1和2只能选择其中一种，不能兼而实现，并且，选择方案2，则方案3必须与2同时选择，或者都不选择。 现该公司可供支配的资金总额为：第一年有650万元，第二年仅有460万元。要求技改后，至少增加出油能力500桶/天，但又不得超过1100桶/天，确定该公司总经济效益最大的投资方案。,解：1）确定决策变量：方案的选择只有两种状态，选或不选，设xj（j=1,5）为第j方案的取舍，有：,2）目标函数： max Z=100x1+200x2+50x3+30x4+20x5,14,200x1+300x2+150x3
6、+100x4+50x5650 （万元） 200x1+150x2+50x3+70x4+40x5460 500x1+1000x2+100x3+50x4+20x5500 500x1+1000x2+100x3+50x4+20x51100 x1+x21 -x2+x3=0 xj=1或0 (j=1,5),3) 约束条件：（投资总额约束（第一、二年），生产能力增加约束，方案制约约束，变量的取舍限制。,15,例6：人员分派问题数模（01规划）,每项工作只能由一个人承担，每人做每项工作的工作效率如上表所示，现在怎样安排工作使总的效率最大。,16,解：设xij为第i个人做第j项工作，（xij=1或0）,Max Z0
7、.6x11+0.2x12+0.3x13+0.1x14+0.7x21+0.4x22+0.3x23+0.2x24 +0.8x31+x32+0.7x33+0.3x34 +0.7x41+0.7x42+0.5x43+0.4x44,x11+x12+x13+x14=1 x21+x22+x23+x24=1 x31+x32+x33+x34=1 x41+x42+x43+x44=1 x11+x21+x31+x41=1x12+x22+x32+x42=1x13+x23+x33+x43=1 x14+x24+x34+x44=1xij=1或0 (i=1,.,4。 j=1,4）,每一项工作都有人做,每个人只做一项工作,17,线
8、性规划建立模型步骤：确定一组决策变量确定目标函数确定对决策变量的约束条件,线性规划建模小结,线性规划的共同点：要解决的问题的目标可以用数值指标反映对于要实现的目标有多种方案可选择有影响决策的若干约束条件,18,作业：现有一家公司准备制定一个广告宣传计划来宣传开发的新产品，以使尽可能多的未来顾客特别是女顾客得知。现可利用的广告渠道有电视、广播和报纸，根据市场调查整理得到下面的数据：,该企业计划用于此项广告宣传的经费预算是80万元，此外要求： 至少有200万人次妇女接触广告宣传； 电视广告费用不得超过50万元, 电视广告至少占用三个单元一般时间和两个单元黄金时间, 广播和报纸广告单元均不少于5个单
9、元而不超过10个单元。试为该企业制定广告计划，使得广告所接触的未来顾客总数尽可能多，建立线性规划数学模型。,19,5.2 线性规划的图解法,一、图解法求最优解的步骤,思路：在直角坐标系中，描绘出约束条件和变量限制的公共区域，然后通过观察确定符合目标要求的变量的取值。 求解例1中的生产计划问题：,对于简单的线性规划问题(只有两个决策变量的线性规划问题),我们通过图解法可以对它进行求解。,20,O,x1,x2,80,60,30,70,90,1、绘出约束方程的图形 2、确定可行解域 3、绘出目标函数图形 4、确定最优解及目标函数值,可行解域,目标函数变形得：,目标函数等值线,最优解,Q2(75,15
10、),Q1,Q3,Q4,Q5,Q6,Q7,Q8,21,几个概念： 可行解：满足线性规划所有约束条件（含约束方程与变量约束）的点。 可行解域：所在可行解的集合。 最优解：使目标函数得到极值的可行解。最优解包括：唯一最优解和无穷多最优解。,等值线：具有相同目标函数值的直线。 法向量(梯度):由目标函数系数组成的与等值线垂直的向量。,22,二、二维线性规划问题解的形式,1、唯一最优解,2、无穷多个最优解,6,6,8,4,3,x2,可行解域,目标函数的等值线,C(1,2),Q2(4,2),Q3(2,3),x1,Max Z=x1+2x2x1+x26x1+2x28x23 xi0(i=1,2),23,3、有可
11、行解但无最优解,max Z=x1+x2-2x1+x24x1-x22x1,x20,x2,x1,-2,4,-2,2,可行解域,(1,1),24,4、无可行解,Min Zx1+2x2s.t. x1+x212x1+x24x1,x20,x2,x1,1,1,4,2,(1,2),可行域为空集，无可行解!,25,线性规划的可行解域为凸多边形（凸集）。 可行解域凸多边形有若干个顶点，顶点的个数是有限的。,三、线性规划的几何意义,线性规划问题若存在最优解，则最优解必可在其可行域的某一顶点上得到。,26,四、单纯形法原理,O,x1,x2,Q2(75,15),60,最优解,Q1,Q3,Q4,Q5,Q6,Q7,Q8,找
12、可行解域顶点的计算方法，但不是计算所有的顶点，而是从凸集的一个顶点出发，沿着凸集的边缘逐个验算所遇到的顶点，直到找到目标函数为最优的顶点为止。如从O Q1 Q2或从O Q4 Q3 Q2 。,27,1.3 单纯形法原理,5.3 线性规划标准型和规范型,一、线性规划的标准型,约束方程均为等式方程。 右边常数bi为正数。 所有变量均为非负变量。 目标函数求max,1、一般形式：,28,或写成累加和形式：,标准型的一般形式,29,或写成矩阵形式：,其中：,30,2、化线性规划问题为标准型,约束方程为“号，在方程式的左端“”一个变量（变量0，称为松驰变量），原不等式化为等式约束。约束方程为“”号在方程式
13、的左端“”一个变量（变量0，称为剩余变量），原不等式化为等式约束。,(1) 约束条件为等式,31,（2）变量非负约束 若xk为无约束变量（即可0，也可0），引进两个变量xk,xk”（均0），令xk=xkxk”。在规划模型中去掉xk这个变量。,（3）约束方程右边常数非负约束 在方程两边同时乘以（-1）使得约束方程右边常数变为非负,32,标准型为：,例1：把下面的线性规划模型化为标准型：,33,得到该问题的标准型为：,(1) 用x4x5替换x3，其中x4，x50 (2)在第一个约束不等式号左端加上松驰变量x6 (3)在第二个约束不等式左边减去松驰变量x7 (4)令DZ,把求min Z化成max D
14、,例2：把下面的线性规划模型化为标准型：,34,二、线性规划的规范型,要用单纯形法求解线性规划数学模型，还需要把数学模型化成规范型。,1基、基变量与非基变量,基：设A是约束方程组的mn维系数矩阵，B是矩阵A中m阶方阵（行列式的值不为0），则称B是线性规划问题的一个基。 基变量与非基变量：与基B对应的变量为基变量。其余变量为非基变量。,设线性规划模型的标准型：,35,请列举出其中的三个基及对应的基变量与非基变量。,例1：,解：从约束系数矩阵可看出，该模型的基不超过,个。,对应的基变量为x3,x4,x5,非基变量为x1,x2。,36,对应的基变量为x1,x3,x4，非基变量为x2,x5。,对应的基
15、变量为x1,x2,x3，非基变量为x4,x5。,37,2基本解和基本可行解,基本解：对某一确定的基，令非基变量等于0，可求出m个约束方程的基变量的值，则这组解称为基本解。,基本可行解：若基本解还满足决策变量非负要求，则这组基本解称为基本可行解（也称基可行解）。,38,对基B1来说，令非基变量,，则可以得到一个基本解,因为,，故,是基可行解。,对基B2来说，令非基变量,，则可以得到一个基本解,因为,，故,也是基可行解。,39,对基B3来说，令非基变量,，则可以得到一个基本解,因为,，故,不是基可行解。,对基B4来说，令非基变量, 则可得基本解,因为,，故,也不是基可行解。,40,3基可行解与可行
16、解域顶点的关系,O,x1,x2,Q2(75,15),60,最优解,Q1,Q3,Q4,Q5,Q6,Q7,Q8,X(1)对应原点O, X(2)对应顶点Q1, X(3) 对应Q7.,X(4) 对应?,41,O,x1,x2,80,60,90,最优解,Q2(75,15),Q1,Q3,Q4,Q5,Q6,Q7,Q8,42,定理1：线性规划的基本可行解对应于可行解域的顶 点。,从定理1和单纯形的几何意义知，用单纯形法寻求最优解，就可从基本可行解（顶点）出发，在基本可行解（顶点）之间变换，如果L.P.有最优解，则最优解一定可在某一基本可行解（顶点）上得到。这个方法可用来求有任意多个变量的线性规划模型！,O,x1
17、,x2,Q2(75,15),60,最优解,Q1,Q3,Q4,Q5,Q6,Q7,Q8,43,已是标准型；,得初始基本可行解：X(1）=(0,0,540,450,720) T,Z=0。,4、线性规划的规范型,例1：,特点（1）基变量的值刚好是约束方程右边的常数；（2）目标函数Z的值就是目标函数表达式中的常数。,含单位基；,目标函数用非基变量表示。,规范型条件：,44,若取基变量x3,x4,x1,则基解及目标函数值？,可把模型化成以基变量系数矩阵为单位阵的规范型：,得到基本可行解：,，,45,引例1：求解下列线性规划模型的最优解,解：1、确定初始基可行解 取B1（P3 P4 P5）I，,令非基变量x
18、1,x2=0，得 X(1)（0,0,540,450,720）T， Z(1)0；（解的含义？）,从规范型出发,5.4 单纯形法步骤,46,2、判定解是否最优 目标函数 Max Z0+70x1+30x2 检验数：用非基变量表达的目标函数中变量前的系数Rj（判别数或检验数）。 当x1从0或x2从0， Z从0， X(1) 不是最优解,3、由一个基可行解另一个基可行解。(1) 确定入基变量 可选Rj0的任一变量入基。（意义？）一般地，选择maxRj的变量入基，选x1从0，保持x2 =0(2)确定出基变量,47,问题：确定入基变量x1增加的上界：从约束方程组怎样求解？,在中，继续令x2为非基变量，即x2
19、0，求出当前每个基变量出基能使x1增大的上界值。即：,x3=5403x10 x1180=540/3 x4=4505x10 x190=450/5 x5=720 9x1 0 x180=720/9,48,min180 ,90,80= min540/3 ,450/5,720/9= 80, x5出基(变为0)，即x1的取值受第三种资源的约束。 规则：入基变量满足约束条件下取最大值。（大中取小）,x3=5403x10 x1180 x4=4505x10 x190 x5=720 9x1 0 x180,新的基变量为x3,x4,x1，怎样求出新的基可行解？,把模型变成以基变量的系数矩阵为单位阵的规范型。,(3)
20、求出新的基可行解,49,以基变量x3,x4,x5的系数矩阵为单位阵的规范型:,（1）从出基变量x5所在的方程开始：方程两边同时除以入基变量x1的系数9，得：,（2）方程中消去x1（入基变量）：方程两边同时乘以某个数，加到方程上。,（3）目标函数中消去x1：从方程中解出x1的值代入目标函数中：,新的基变量为x3,x4,x1,本质：就是线性代数中的高斯消去法方程组同解变形.,50,通过以上方程的变换，原线性规划模型等价于以下模型（得到当前基表示的规范型）：,X(2)（80,0,300,50,0）T ， Z(2)5600； 对应图形上的Q1点。,1、确定出新的基可行解,51,2、判定解是否最优,3、
21、由一个基可行解另一个基可行解。 (1) 确定入基变量 选择x2入基，即x2从0，x5 仍为0,从约束方程组求解x2的最大取值，从而确定出基变量。,同理：在中令x5=0，求出当前解下x2取值的上界。,当x2从0，Z从5600， X(2) 不是最优解.,目标函数：,，R2=20/3, R5=-70/9,52,=min 37.5，15 ，24015，x4出基,(2) 确定新基可行解：,x3=3008x2 x237.5 x4=5010x2/3 x215 x1=80x2/3 x2240,把模型变成以基变量x3,x2,x1的系数矩阵为单位阵的规范型。,新的基变量x3,x2,x1,53,怎样把模型变成以基变
22、量x3,x2,x1的系数矩阵为单位阵的规范型？,(1)从出基变量x4所在的方程开始：使入基变量x2 的系数变成1。 (2)用消元法消去方程中的x2。,54,X(3)（75,15,180,0,0）T， Z(3)5700；,由方程组变形得：,55,2、判定解是否最优目标函数,X(3)（75，15，180，0，0）T ，Z(3)5700；,非基变量的检验系数均为负数，故不能入基，否则使目标值劣化。 当前解为最优解。,最优解判断标准： （1） 若全部检验数Rj 0，当前基本可行解为最优解。 （2） 若存在Rj 0，则当前解非最优，解可改进，寻求 更好的解。,56,1、 确定初始基可行解。本题确定初始基
23、为单位阵I，令单位阵对应的变量为基变量，可得到一个基本可行解。,小结：单纯形法求解线性规划的过程,2、最优化检验：用当前可行基的非基变量的检验数确定。,3、 从一个基本可行解到另一个基本可行解 入基变量：由检验数确定。 出基变量：由规则确定。,57,用单纯形法从另一条路径寻优？,58,5.5 单纯形表,目标函数行：常数Z0在右边。,59,1、由规范型列出初始单纯形表：,X(1)（0,0,540,450,720）T Z(1)0,主元,60,2、变换到下一单纯表（变成以新基为单位阵的规范型）,思考：单纯形表有什么特点？ （1）基变量对应的约束方程中系数矩阵为单位矩阵。 （2）目标函数基变量的检验数
24、为0。 （3）基可行解(？)不同，反映在原表中就是对应的基不同。,新的基变量：x3 ,x4,x1,主元,61,表一,表二,0,0,0,0,30,70,-Z,80,720,1,0,0,3,9,x5,0,90,450,0,1,0,5,5,x4,0,180,540,0,0,1,9,3,x3,0,x5,x4,x3,x2,x1,XB,CB,0,0,0,30,70,Cj,9,-5600,-70/9,0,0,20/3,0,-Z,240,80,1/9,0,0,1/3,1,x1,15,50,-5/9,1,0,10/3,0,x4,0,37.5,300,-1/3,0,1,8,0,x3,0,70,?,62,3、重复以
25、上过程直到得最优解：,思考：在单纯形表中，怎样判断LP问题已取得最优解？,最优解判断标准： （1） 若全部检验数Rj 0，当前基本可行解为最优解。 （2） 若存在Rj 0，则当前解非最优，解可改进，寻求更好的解。,63,X*=(75,15,180, 0,0)T, Z=5700,64,例1：求解下列线性规划模型：,解：化线性规划模型为规范型，并列出初始单纯形表：,按单纯法迭代，计算如下表，得最优解为:,X=(1500,0,0,3500,0)T, Z=6000,65,-6000,-2,0,-3,-1,0,-Z,1500,1/2,0,2,1/2,1,x1,3500,-3/2,1,-2,-1/2,0,
26、x4,-3750,-5/4,0,0,-1/4,3/2,-Z,1500,750,1/4,0,1,1/4,x3,5000,5000,-1,1,0,0,1,x4,0,0,0,5,1,4,-Z,750,3000,1,0,4,1,2,x5,2000,8000,0,1,4,1,3,x4,b,x5,x4,x3,x2,x1,XB,CB,0,0,5,1,4,Cj,4,1/2,66,例2： 用单纯形法求解下列线性规划数学模型,选x1、x3、x6为基变量 目标函数用非基变量表示： 由 约束方程(1)(2)(3)解出 x3 = 6 - x2 + x4 - 2x5 x1 = 5 - 2x2 + 2x4 代入目标函数得：
27、 Min Z = 11 - 4x2 + 3x4 - 5x5,把LP化成求极大的规范型：,67,68,X(3) = (0，5/2，3/2，0，1，0)T D(3) = 4，Z4,-4,-5/3,0,-4,0,0,-1/3,-D,1,1/3,1,1,0,0,-1/3,x5,3/2,-2/3,0,-2,1,0,1/6,x3,5/2,0,0,-1,0,1,1/2,x2,-7/3,-5/3,0,-14/3,0,2/3,0,-D,4,8/3,1/3,1,1/3,0,2/3,0,x5,2/3,-2/3,0,-5/3,1,-1/3,0,x3,5/2,5,0,0,-2,0,2,1,x1,11,0,5,-3,0,
28、4,0,-D,8/3,8,1,3,1,0,2,0,x6,3,6,0,2,-1,1,1,0,x3,5,0,0,-2,0,2,1,x1,b,x6,x5,x4,x3,x2,x1,XB,69,假设目标函数求极大MAX 1、从规范型出发，得出一个初始基可行解。按要求填入表中。 2、最优化检验：若还存在Rj0，则当前解不是最优解。,3、解的改进： 由检验数确定入基变量xp。(一般正系数大的变量先入基) 确定出基变量:,确定L为出基行，则xL为换出变量。得到一个新的可行基。,单纯形算法步骤,4、用初等行变换方法把主元（aLp）变为1，把入基列（含其检验数）中除主元的其它元素消为零。转2.,70,讨论：单纯形
29、表进行求解的特殊情况,（1）若最大检验数有两个或两个以上并且相等，应如何确定入基变量，理论上可任选一个非基变量入基，但在实际应用中，可采用以下法则：,依次选择X1和X2入基，分别计算出两组比值1和2，每组比值中分别选择最小值得80和60，两个最小值中选择最大值80，因此确定X1入基，此时目标函数值改变得最快(?)。,71,（2）原问题有解但无最优解(无界)的判断：某个Rj0,但aij0(i=1,2,m)。,例4：求解线性规划问题：,标准化,72,一、最优决策变量的解最优解是单纯形法的基本目标信息，在建模参数可靠的基础上，它提供最优决策方案 。,如例2中： 最优解：X(3)（75，15，180，
30、0，0）T ，Z(3)5700； X4 = 0， X5 = 0，表明资源B、C没有剩余，为企业的关键资源； X3 = 180，资源A还剩180个单位。 应设法提高关键资源的获得量。,二、松弛变量的解单纯形表的每一个基本可行解，还包含有松弛变量的解，在最优决策条件下，松弛变量的解提供资源的剩余量。,5.6 单纯形的经济意义,73,三、检验数Rj(产品的相关价值系数)经济意义,基本解X(2)（80，0，300，50，0）T Z(2)5600；,基本解：X(1)（0，0，540，450，720）T ，Z(1)0； Max Z70x1+30x2,当前方案下，非基变量Xj增加1个单位，使目标函数增大的量
31、。,R2=20/3，而当前表中，入基变量x2可增加值为15，故当前表中x2入基，利润可增加100。,74,从例1的第二个单纯形表来看，生产80个单位的x1，C资源全部用完，A、B资源分别剩余300和50。 生产1个单位的x2，分别需要A、B、C各9,5，3单位，由于资源总量的约束，只能少生产1/3单位的x1，所以少生产1/3单位的x1要损失的利润为： Z20803/10+701/3=70/3， 故R23070/320/3。,-5600,-70/9,0,0,20/3,0,-Z,240,80,1/9,0,0,1/3,1,x1,70,15,50,-5/9,1,0,10/3,0,x4,0,37.5,3
32、00,-1/3,0,1,8,0,x3,0,x5,x4,x3,x2,x1,XB,CB,0,0,0,30,70,Cj,75,C230，孤立地讲，生产1个单位的乙产品对市场的利润还是30，但在企业的资源约束下，在当前的生产方案下，要使x2=1，必然以少生产其它产品为代价，故在当前方案下增加1个单位的乙产品只能净得利润20/3。为了生产一单位的某产品将所需资源从原来的用途中抽出来而牺牲的利润为此种产品在此生产方案下的机会成本。（Zj为生产一单位xj产品所付出的成本。cjzj表示生产1单位j产品对方案收益的增量。检验数Rj综合考虑了市场信息和规划方案改变对利润的影响。一旦作出了生产安排，单位产品的利润增
33、值（Rj）就可能变化， Rj能起到判别计划能否进一步改进的作用。,76,四、资源的影子（潜在）价格,1、定义：最优规划条件下，单位资源能够带来的目标函数增量。是反映资源最优利用的一种虚拟价格，也叫资源边际利润。,2、影子价格的计算最优表中表示资源的松弛变量检验数的相反数。,-5700,0,-20/3,-2,0,0,-Z,75,1/6,-1/10,0,0,1,x1,15,-1/6,3/10,0,1,0,x2,180,1,-12/5,1,0,0,x3,x5,x4,x3,x2,x1,XB,CB,0,0,0,4,3,Cj,77,根据影子价格的定义： 资源A的影子价格为0，资源B的影子价格为2，资源C的
34、影子价格为20/3。,含义：在最优方案下，资源B增加1个单位，能使利润增加2个单位。资源C增加1个单位，能使利润增加20/3个单位。 资源A增加1个单位，不会使利润增加(A本身有剩余)。资源影子价格的高低表明资源的重要性的大小，影子价格为0的资源是非关键资源，影子价格大于0的资源是关键资源。,X(3)（75，15，180，0，0）T,78, 在企业内部：指出挖潜方向，影子价格高的资源潜力大，影子价格低的资源潜力小。问题：资源的影子价格是否是一定的？注意：随着资源可用量的不断增加，其影子价格会不断下降，当影子价格降为0时，再增加该资源的可用量,利润不会增加，此时该资源已成为非关键资源。,衡量资源
35、的使用是否合理。同一种资源在不同的地方和不同的时期，其影子价格不相同，影子价格高的说明使用合理，所以应建立动态影子价格体系，做到物尽其用。,对企业外部来讲，影子价格是决定资源在市场上出售的标准：当资源的市场价不低于其影子价格时，企业管理人员可以考虑出售，得到的利润与自己组织生产所得利润是一样的。,3、影子价格的应用,79,一、线性规划标准型的表达形式,约束方程均为等式方程。 所有变量均为非负变量。 右边常数bi为正数。,Max Z=c1x1+ c2x2+cnxna11x1+ a12x2+ a1nxn =b1a21x1+ a22x2+ a2nxn =b2 am1x1+ am2x2+ amnxn
36、=bmxj 0(j=1,2,n),1、一般形式：,5.7 单纯形法理论分析,80,2、求和表达式,81,3、矩阵表达式,C=(c1 c2 cn ),maxZ=CX AX=b X 0,82,一、单纯形表（规范型）的一般表示 1、单纯形表的数学推导,不失一般性，设某一基变量为XB=(x1,x2,xm)T，则对应此基下的约束方程组可表达为：,LP的数学模型为：,83,基变量的求和表达式：,把目标函数也表达成基变量和非基变量两部分的求和表达式：,把（1）式代入（2）式经整理得：,84,Zj基变量的价值系数当前单纯形表中该变量前的系数,检验数RjCj Zj,2、当前解的改进和最优解的确定,设检验数为：,
37、Rj0解能改进的条件。 Rj0最优解的确定条件。当存在若干个Rj0，一般选最大的数,实际上：可选使目标函数值Z变化最大的非基变量入基：ZZ0Rj,85,3、出基变量、主元素,xp入基为正数，其它非基变量保持为零，,入基变量的上界值为：,aip0，因为xp为非负的有限数，要求aip0,由规则为：,则xl行为换出行，主元为：,86,4、旋转运算要得到下一单纯形表，即使入基列向量xp成为单位向量，其旋转运算方法：,第l行（出基行）元素除以主元，使主元变为1。 入基列xp中除主元外的其它元素（包括检验数行）消为零。,87,例1：用公式验算引例第二个单纯形表（见表1）中目标函数的值与检验数。,解：计算检
38、验数：,其中ci为基变量的价值系数。,R230(08+ 010/3+ 701/3)=20/3,R50(0(-1/3)+ 0(-5/9)+ 701/9)70/9,计算目标函数值：,ZCixi=70805600,88,对于线性规划模型的标准型：,设某个基可行解对应的基为B，LP模型又可表示为：,对约束方程，两边同乘B1得：,怎样得出该基对应下的单纯形表呢？,二、单纯形表（规范型）的矩阵表示,IXB+B-1NXN=B-1b，解出：XB =B-1 bB-1 NXN,代入目标函数，消去基变量，得：,Z0XB（CNCBB1N）XNCBB1b,单纯形表的矩阵表达式：,89,问题：与原模型相比， 1、基变量的
39、系数向量如何变化？非基变量的呢？ 2、与原模型中的价值系数比较，基变量的检验数如何变化？非基变量的呢？ 3、与原模型相比，约束方程右边的常数如何变化？ 4、在当前基可行解下，目标函数值与B、CB及b的关系？,90,例1：用单纯形表的矩阵表达式计算引例中以x3,x4,x1为基变量的单纯形表。,(1)基变量的值：,(2)非基变量的系数：,91,(3)非基变量的检验数：,用单纯形表的计算公式算出来的结果与用表格迭代的结果一致！,92,例2：引例中，若知道最优基（以x3,x4,x1为基变量），最优基对应的单纯形表是否可一步求出？如何求？,93,(1)、定初始基，初始基本可行解,(2)、对应于非基变量检
40、验数Rj全0。 若是，停，得到最优解； 若否，转(3)。,(3)、若有Rp 0，全Pp 0，停，（Pp为入基列的系数向量） 没有有限最优解； 否则转(4),(4)、maxRj =RpXp 入基变量,XL为出基变量，aLp为主元。,(5)、以 为中心，换基迭代，得出新的基可行解。,单纯形法基本步骤 (max型),出基变量确定：,思考：求MIN型？,94,95,练习：下表为用单纯形法计算时某一步的表格。已知该线性规划的目标函数为：max Z=5x1+3x2,约束形式为，x3,x4为松弛变量，表中解代入目标函数后得Z10。 （1）求ag 的值； （2）表中给出的解是否为最优解。,答案：a=2,b=0
41、,c=0,d=1,e=4/5,f=0,g=-5,96,5.8 两阶段法与大M法,下面的线性规划模型，怎样得到一个初始基本可行解？,一般说来，对于不是规范型的标准型，我们看不出哪组变量为基变量，可得基可行解。对于不是规范型的标准型，用单纯形法求解的办法就是添加人工变量，使标准型人为地变成规范型的形式。,标准化,97,人工变量法思想： 目的：使A中含单位基，得到模型（2）的一个基可行解，但此基可行解不是（1）的可行解。,人工变量是人为添加到原约束方程的虚拟变量，若人工变量不等于0，则不是原模型（1）的解。,单纯形法是确定入基变量和出基变量的过程，(约束方程的等价变换过程)，只要人工变量全部出基，基
42、变量中不含有人工变量，这时模型（2）的基可行解也是（1）的可行解。,如模型(2)的解：,98,一、两阶段法,第一阶段：不考虑原问题是否存在基可行解；给原LP模型加入人工变量，并构造仅含有人工变量的目标函数，实现极小化。 如xn+1,xn+2,xn+m为加入的人工变量，则新的目标函数为：,然后用单纯形法求解上述模型，若得到W=0，这说明原问题存在基可行解，可以进入第二阶段计算。否则，原问题无可行解，应停止计算。 第二阶段也分2种情形1)无人工变量作为基变量，直接进入第二阶段；2)有人工变量为0作为基变量，该行约束冗余，可以丢掉，在进入第二阶段.,min W= xn+1xn+2xn+m,99,1,
43、0,0,0,0,0,-Z,2,1,-1/2,-1,1/2,1,1/2,0,x3,0,6,3,1/2,0,-1/2,0,1/2,1,x1,0,0,0,1,0,-1,-2,-Z,4,4,0,-1,0,1,1,1,x3,0,3,6,1,0,-1,0,1,2,x6,1,b,x6,x5,x4,x3,x2,x1,XB,1,0,0,0,0,0,cj,2,1/2,第一阶段，构造新的目标函数：min w=x6,100,36,-6,-2,-1,0,0,-Z,2,-2,1,2,1,0,x2,-8,2,1,-1,-1,0,1,x1,-10,-7,-3/2,0,1/2,0,-Z,2,1,-1,1/2,1,1/2,0,x
44、3,-7,6,3,0,-1/2,0,1/2,1,x1,-10,b,x5,x4,x3,x2,x1,XB,0,0,-7,-8,-10,cj,1/2,第二阶段：换回原来的目标函数 max z=10x18x27x3,cB,教材例,101,把标准型化为规范型，如右边示： x6, x7为人工变量。,解：第一阶段：希望人工变量等于零，故构造仅含人工变量的目标函数，并要求实现最小化。,用单纯形法求解模型(2)，若人工变量x6，x7 能全部出基，变成非基变量，则W0，同时原问题也存在一个可行基，进入第二阶段的运算，否则原问题无可行解。,102,0,1,1,0,0,0,0,0,-W,3/2,-1/2,-1/2,1
45、,1/2,1/2,0,0,x5,0,3/2,1/2,1/2,0,-1/2,-1/2,1,0,x2,0,1/2,-1/2,1/2,0,1/2,-1/2,0,1,x1,0,-1,2,0,0,-1,1,0,-2,-W,2,2,-1,0,1,1,0,0,1,x5,0,-,1,1,0,0,-1,0,1,-1,x2,0,1/2,1,-1,1,0,1,-1,0,2,x6,1,-3,0,0,0,1,1,-2,0,-W,3,3,0,0,1,0,0,1,0,x5,0,1,1,1,0,0,-1,0,1,-1,x7,1,2,2,0,1,0,0,-1,1,1,x6,1,b,x7,x6,x5,x4,x3,x2,x1,XB
46、,CB,1,1,0,0,0,0,0,cj,103,第二阶段：将第一阶段计算得到的最终表，去掉人工变量，将目标函数换回原问题的目标函数，并用非基变量表示目标函数。（此时原问题已变换成规范型）,104,105,例3.用两阶段单纯形法求解线性规划,解：标准形式为,106,在第一、三约束方程中加入人工变量x6、x7后，构造第一阶段问题,用单纯形法求解，得到第一阶段问题的计算表格,107,108,最优解为,最优值w=0。第一阶段最后一张最优表说明找到了原问题的一组基可行解，将它作为初始基可行解，求原问题的最优解,即第二阶段问题为,109,用单纯形法计算得到下表,检验数j0,j=1,2,5，最优解与最优值,110,注：在第二阶段计算时，初始表中的检验数不能引用第一阶段最优表的检验数，必须换成原问题的检验数，用代入法或消元法计算。 另外，即使第一阶段最优值w=0，只能说明原问题有可行解，第二阶段问题不一定有最优解，即原问题可能无界。,例4：用两阶段法求解下列线性规划。,111,加入松驰变量x3、x4化为标准型,第一阶段问题为,
