《运筹学》线性规划(课堂PPT).ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,第,2,章 线性规划,1,例,1,穗羊公司的例子,I,II,每周可使用量,A,（千克）,1,2,5,B,（吨）,2,1,4,C,（百工时）,4,3,9,单位产品利润（万元）,3,2,问该公司每周应生产产品,I,与产品,II,各多少单位，才能使每周的获利达到最大？,2,假设产品,I,、,II,每周的产量分别是,x,1,和,x,2,，得到如下的数学模型,其中,s.t.,是英文词组,subject to,的缩写，表示“受限制于”的意思，有时也约去不写出来。,该问题常称为,生产计划问题,或,产品组合,（,product mix,）问题。,3,例,2,设有一批规格为,10,米长的圆钢筋，将它截成分别为,3,米，,4,米长的预制构件的短钢筋各,100,根，问怎样截取最省料？,因为，,10,米长的钢筋截为,3,米或,4,米长，共有三种截法：,截法,：,3 3 3 1,米,截法,：,3 3 4 0,米,截法,：,4 4 0 2,米,假设按截法,，,，,各截取,10,米长的钢筋分别为,x,1,x,2,x,3,根,则可以获得,3,米长的短钢筋的根数是,3,x,1,+2,x,2,4,米长短钢筋的根数是,x,2,+2,x,3,按问题要求它们应该不小于,100,根。,总共用料是,x,1,+,x,2,+,x,3,要达到最省料的目的，就必须使总用料最小。,4,例,2,的模型就是,例,2,中的问题常称为,下料问题,。,5,线性规划的三个要素：,决策变量,目标函数,约束条件,其次线性规划模型必须满足如下两个要求：,目标函数必须是决策变量的线性函数；,约束条件必须是含决策变量的线性等式或不等式,。,运筹学建模步骤,:,识别问题定义决策变量建立约束条件,建立目标函数,6,2.2,线性规划模型的一般形式和标准形式,为了讨论一般的线性规划问题的求解。我们先给出线性规划模型的一般形式如下：,2.2.1,线性规划的一般模型,7,这里一共包含有,n,个决策变量，,m,个约束条件；,对目标函数既可以求最大的也可以求最小；,约束条件有,=,型；,决策变量通常非负，但也可以有其它情况；,c,j,:,称为价值系数；,b,i,:,资源常数（右端常数）,a,ij,称为技术系数、工艺系数,8,在今后的讨论中，为方便起见，还将用到线性规划模型一般形式的各种简写的形式。,利用和号“”，线性规划模型的一般形式可写为：,9,利用向量，可以将一般形式表示为：,其中,10,在今后的讨论，常将矩阵 称为线性规划问题的（约束条件）,系数矩阵,。明显地系数矩阵 与矩阵 之间存在关系：,用矩阵的记号可以将线性规划模型一般形式写成：,其中 同上，而矩阵 是由各约束条件的系数（技术系数）构成的 矩阵：,11,2.2.2,线性规划的标准形式,它具有如下四个特征：,目标函数求,max,；,约束条件两端用“,=”,连结；,b,i,非负；,所有决策变量,x,j,非负。,12,2.2.3,将线性规划的模型化为标准形式,1,、目标函数求最小值的情形,取原目标函数的相反数为新的目标函数，对原目标函数求最小值的问题就等价于对这一新的目标函数求最大值的问题。,例如：,等价于,13,2,、约束条件为不等式,(a),转化为,x,s,表示决策中尚未使用的那部分资源，因此称这一变量为,松弛变量,。,（,b,）,转化为：,它表示决策结果超过了实际需要的部分，因此常称它为,剩余变量,。,无论是松弛变量还是剩余变量在决策中都不产生实际价值，因此,它们在目标函数中的系数都应该为零,。在后面的讨论中，有时也将松弛变量和剩余变量统称为松弛变量。,14,3,、约束条件右端常数为负数,只需将这一约束条件两端同乘“,-1”,就可化为一个等价的约束条件，其右端常数满足标准形式的要求。,4,、决策变量不满足非负约束,（,a,）,（,b,）如,x,3,无约束，则令,15,例如，将例,1,中的线性规划模型化为标准形式就是：,其中 就是分别对第一、第二、第三个约束条件中添加的松弛变量。,16,例,3,化如下的线性规划问题模型,为标准形式。,(1),变量,是非正的，所以要将模型中的所有,都用,代替，其中,(2),变量,无约束，因此取两个变量,使得,。在模型中，所有的,都用,代替。,。在模型中，所有的,17,(5),约束条件,2,是“,”,型的，因此需要在左边加上一个松弛变量,化为等式，即,”,型的，并且右端的常数小于零。,(3),目标函数是求最小值的，因此令,，即,(4),约束条件,1,是“,然后在两端乘以,-1,得,也就是,因此先将其左边减取一个剩余变量,使它化为等式：,也就是,18,。,从而得到模型的标准形式为,19,课堂练习,某蓄场每日要为每头牲畜购买饲料，以使其获取所需的,A,、,B,、,C,、,D,四种养分。有关数据如下表，现饲料可从市场上出售的,M,、,N,两种饲料中选择，试决定总花费最小的购买方案。（列出模型）,A,B,C,D,价格,M,0.5,0.2,0.3,0,300,N,0.1,0.3,0.4,0.2,200,每头日需,10,5,8,7,养分,饲料,20,课堂练习,某蓄场每日要为每头牲畜购买饲料，以使其获取所需的,A,、,B,、,C,、,D,四种养分。有关数据如下表，现饲料可从市场上出售的,M,、,N,两种饲料中选择，试决定总花费最小的购买方案。（列出模型）,A,B,C,D,价格,M,0.5,0.2,0.3,0,300,N,0.1,0.3,0.4,0.2,200,每头日需,10,5,8,7,养分,饲料,答案：,设购买,M,饲料,x,1,，,N,饲料,x,2,0.5 x,1,+0.1x,2,10,0.2x,1,+0.3x,2,5,0.3x,1,+0.4x,2,8,0.2x,2,7,x,1,x,2,0,s.t.,Min Z=300 x,1,+200 x,2,21,2.3,线性规划的图解法,对,只包含两个决策变量,的线性规划问题，可以用,图解法,来求解。图解法顾名思义就是通过作图来求解的方法，它简单直观、并有助于说明一般线性规划问题求解的基本原理。,22,有关概念,可行解：,我们将满足线性规划问题的所有约束条件的变量,x,1,和,x,2,的一组取值称为线性规划问题的一个,可行解,。通常用,X,表示。,可行域：,我们将可行解的集合称为,可行域,。,最优解：,因此我们求解线性规划问题，就是要求使得目标函数取最优值（对例,1,，就是取最大值）的可行解，这样的可行解就称为线性规划问题的,最优解,。通常用,X*,表示。,最优值：,即最优的目标函数值,通常用,z*,表示,23,图解法步骤,:,建立平面直角坐标系,图示约束条件,求可行域,图示目标函数,求最优解,24,建立直角坐标系,图示约束条件，求可行域,x,1,x,2,25,图示目标函数,求最优解,x,1,x,2,最优解,等值线向右上方移动，函数值变大。在其即将离开可行域时达到,B,（,3/2,1,）点。所以最优解为：,此时最优值为：,26,2.2.2,线性规划求解的可能结局,1,、有唯一的最优解,2,、有无穷多个最优解,（,将目标函数改为,z,=4,x,1,+3,x,2,）,27,max,z,=,3,x,1,+5.7,x,2,s.t.,x,1,+1.9,x,2,3.8,x,1,-1.9,x,2,3.8,x,1,+1.9,x,2,11.4,x,1,-1.9,x,2,-3.8,x,1,，,x,2,0,x,1,x,2,o,x,1,-1.9,x,2,=3.8,x,1,+1.9,x,2,=3.8,x,1,+1.9,x,2,=11.4,（,7.6,2,）,D,0=3,x,1,+5.7,x,2,max Z,min Z,（,3.8,4,）,34.2,=3,x,1,+5.7,x,2,可行域,x,1,-1.9,x,2,=-3.8,(0,2),(3.8,0),绿色线段上的所有点,都是最优解,即有无穷多最优解。,Z,man,=34.2,28,3,、无界解,指线性规划问题有可行解，但是在可行域，目标函数值是无界的，因而达不到有限最优值。因此线性规划问题不存在最优解。,29,4,、无可行解,指找不到一组变量能满足线性规划的所有约束条件的情况，也就是线性规划问题不存在可行解，或者说可行域是空集。例如线性规划问题：,30,LP,解的几种情况,（,1,）唯一解,（,2,）多重最优解,（,3,）无可行解,注：出现（,3,）、（,4,）情况时，建模有问题,（,4,）无有限最优解,31,另外两个重要的结论,：,线性规划问题可行域若不是空集，则它是一个凸集；,线性规划问题的最优解若存在，则一定可以在其可行域的一个顶点上达到。,32,最优解：,x,1,=0,，,x,2,=1,最优目标值,z =3,课堂练习,图解法求解线性规划,0,1,2,3,4,1,2,3,4,x,1,x,2,O,-1,-2,(1),(2),(3),33,例 某工厂经市场调研，决定生产甲、乙两种产品，其单台利润分别为,60,元和,30,元，两种产品共用一种钢材、一台设备，其资源及获利情况如下：,甲,乙,现有资源,钢材消耗定额（公斤,/,台）,2,4,600,公斤,台时消耗定额（小时,/,台）,3,1,400,小时,配件（件,/,台）,2,0,250,件,利润（元）,60,30,求利润最大的产品结构决策。,作业练习,34,确定目标函数及约束条件,建立数学模型,目标函数：,将不等式变为等式并在,x,1,x,2,坐标图中作出直线,最优点在凸边形的顶点，代入（,1,）式可得,maxP,解,：,设变量：设甲生产,x,1,台，乙生产,x,2,台，可得最大利润,约束条件：,35,0,50,50,100,100,150,150,200,250,300,350,200,250,300,350,400,x,1,x,2,A(0,150),B(100,100),C(125,25),D(125,0),(4),36,2.4,线性规划解的基本概念与性质,在本节，我们主要考虑模型具有标准形式的线性规划问题,（,2.6,）,37,线性规划问题解的概念及性质,对于线性规划问题（,2.6,）来说，可行解实际上是由约束条件构成的线性方程组（常称为,约束方程组,）,的解，并且还满足非负约束条件，即各个决策变量都取非负值：。,38,对于线性规划问题（,2.6,），可以证明如下的结论：,定理,2.1,线性规划问题的可行域如果不是空集，就一定是凸集。,凸集,:,指一个非空集，并且以其中任意两个点为端点的直线段上的所有点都属于该集合。,顶点：,在凸集中，如果一个点不位于其他两点为端点的线段的内部，则称其为该凸集的,顶点,。例如上图中第一个凸集的,A,点，或第二个凸集的,B,点，分别是相应的凸集的顶点。,哪个是凸集呢？,39,今后我们将,A,的任一个具有这样的特征的子矩阵,B,称为线性规划问题（,2.6,）的一个,基,。也就是说线性规划问题的基就是矩阵,A,的一个 且行列式不为零的子矩阵。,我们将约束方程组的系数矩阵,称为线性规划问题的,系数矩阵,，并且,总假定其秩等于其行数,：,。这意味着系数矩阵,的各行是线性无关的，,这也表明约束方程中的各个方程是相互独立的。,由于矩阵,A,的秩为,m,故至少存在一个 的子矩阵,B,，其,行列式不为零。,40,例如，对于线性规划问题,其系数矩阵为,则下面两个矩阵都是该线性规划问题的基。,和,还能找出其它基吗？,41,例如，对上面的线性规划问题，若我们考虑基,则线性规划问题的,基变量,就是,x,2,和,x,4,，而,x,1,和,x,3,就是,非基变量,。但如果我们考虑的基是,则基变量是,x,1,和,x,2,，非基变量是,x,3,和,x,4,。,可见在线性规划问题中所谓基变量就是由,m,个变量构成的一组变量，其系数构成的行列式不等于零；反之满足系数行列式不等于零的一组,m,个变量，就是基变量。,42,基解,：,在约束方程组中,，,令非基变量等于,0,的解。,基可行解：,基解,+,可行解,例如，对于上面的线性规划问题，如果取,x,1,，,x,2,为基变量，则令非基变量,x,3,，,x,4,为零，约束方程组为,解之得 。故我们得到基解,注意到这个基解还是一个可行解。,是否所有的基解都是基可行解？（选,x,1,x,3,作为基变量）,43,定理,2.2,：,线性规划问题的基可行解是其可行域的顶点。,定理,2.3,：,线性规划问题的最优解如果存在，则一定有一个基可行解是最优解。,44,2.6,单纯形法计算,基本思路：,首先将线性规划问题化成标准形式,求出初始基本可行解,判断其是否为最优解,如果不是最优，则迭代到其相邻的基本可行解，并再次检验,45,旦茨基教授在一次演说中，形象而风趣地说明了单纯形解法的奇效：设给,70,个人分配,70,项任务，每人一项。如果每人完成各项任务所需要付出的代价（时间、工资）都知道，要寻求代价最小的方案。所有的可行方案共有,70,！种。,70,！比 还要大。,不仅如此，还能预测当方案中某因素发生变化，对决策目标的影响。,神奇的单纯形法,46,线性规划问题的可行解有无穷多个，与某一凸集上的无穷多个点一一对应。要从无穷多个可行解中寻找最优解，几乎不可能。可以证明，最优解必定能取在凸集的顶点（极点、基本可行解）上，而极点的个数是有限的。当然，这个,“,有限,”,，数字往往相当可观，如前面的,70,！，要逐个比较的话，也不现实。而单纯形解法，用跨跃的方式，高速地优化基本可行解，迅速达到最优。,单纯形法,跨跃式地寻求最优解,优,max S,S=o,o,A,B,C,D,E,47,初始可行解,为了便于求解，并使得整个求解过程程序化，我们通常是从求一个特殊的基可行解出发进行求解。这个特殊的基可行解称为,初始基可行解,。,要求初始基可行解需先确定初始基变量。我们称基矩阵为单位矩阵（或单位矩阵交换了列以后得到的矩阵）的基变量为,初始基变量,。,因此初始基变量具有特征：,它们是一组变量，个数等于约束方程的个数，每个变量仅出现在一个约束方程中且系数为,1,。,初始基变量对应的基解一定是可行解称为初始基可行解。,48,解：,数学模型,max S=6x,1,+4x,2,s.t.2x,1,+3x,2,100,4x,1,+2x,2,120,x,1,x,2,0,引进松弛变量,x,3,x,4,0,数学模型标准形式：,max S=6x,1,+4x,2,s.t.2x,1,+3x,2,+x,3,=100,4x,1,+2x,2,+x,4,=120,x,1,x,2,x,3,x,4,0,49,A=,（,P,1,，,P,2,，,P,3,，,P,4,）,=2 3,1 0,4 2,0 1,X=,（,x,1,x,2,x,3,x,4,),B=(P,3,，,P,4,）,=1 0,0 1,P,3,，,P,4,线性无关，,x3,x4,是基变量，,x,1,x,2,是非基变量。,令,A=,（,P,1,，,P,2,，,P,3,，,P,4,）,=2 3 1 0,4 2 0 1,X=,（,x,1,x,2,x,3,x,4,),50,用非基变量表示的方程：,x,3,=100-2x,1,-3x,2,x,4,=120-4x,1,-2x,2,(I),S =6x,1,+4x,2,令非基变量（,x,1,x,2,）,t,=,（,0,，,0,）,t,得基础可行解：,x,(1),=(0,0,100,120),t,S,1,=0,经济含义：不生产产品甲乙，利润为零。,分析：,S =,6,x,1,+,4,x,2,（分别增加单位产品甲、乙，目标函数分别增加,6,、,4,，即利润分别增加,6,百元、,4,百元。）,增加单位产品对目标函数的贡献，这就是,检验数,的概念。,51,增加单位产品甲（,x,1,）比乙对目标函数的贡献大,（检验数最大），,把非基变量,x,1,换成基变量，称,x,1,为,进基变量,，,而把基变量,x,4,换成非基变量，称,x,4,为,出基变量,。,确定了,进基变量,x,1,，,出基变量,x,4,以后，得到新的系统：,x,3,=40-2x,2,+,（,1/2,）,x,4,x,1,=30-,（,1/2,）,x,2,-,（,1/4,）,x,4,(II),S=180+x,2,-,（,3/2,）,x,4,令新的非基变量（,x,2,，,x,4,）,=,（,0,，,0,）,t,得到新的基础可行解：,x,(2),=(30,0,40,0),t,S,2,=180,经济含义：生产甲产品,30,个，获得利润,18000,元。,52,这个方案比前方案，但是否是最优？,分析：,S=180+x,2,-,（,3/2,）,x,4,非基变量,x,2,系数仍为,正,数，确定,x,2,为,进基变量,。,在保证常数项非负的情况下，确定,x,3,为,出基变量。,得到新的系统：,x,1,=20+,（,1/4,）,x,3,-,（,3/8,）,x,4,x,2,=20-,（,1/2,）,x,3,+,（,1/4,）,x,4,(III),S =200-,（,1/2,）,x,3,-,（,5/4,）,x,4,53,令新的非基变量（,x,3,x,4,）,t,=,（,0,0,）,t,得到新的基础可行解：,x,(3),=(20,20,0,0),t,S,3,=200,经济含义：分别生产甲乙产品,20,个，可获得利润,20000,元。,分析：,S =200-,（,1/2,）,x,3,-,（,5/4,）,x,4,目标函数中的非基变量的系数无正数，,S,3,=200,是最优值，,x,(3),=(20,20,0,0),t,是最优解。,该企业分别生产甲乙产品,20,个，可获得最大利润,20000,元。,54,利用单纯形表进行计算,从前面的单纯形法的计算过程可见，所有计算其实都归结为对标准形式的模型的系数的计算。因此可以通过将线性规划的系数矩阵及目标函数系数列成表格的方式进行计算。,max,z,=3,x,1,+2,x,2,x,1,+2,x,2,+,x,3,=5,2,x,1,+,x,2,+,x,4,=4,4,x,1,+3,x,2,+,x,5,=9,x,1,x,2,x,5,0,3 2,1 2 1 0 0 5,2 1 0 1 0 4,4 3 0 0 1 9,3 2 0 0 0,单纯形表,检验数,55,以,x,3,x,4,x,5,作为初始基变量得到,初始单纯形表,如下所示：,3,2,0,0,0,C,B,X,B,x,1,x,2,x,3,x,4,x,5,b,0,0,0,x,3,x,4,x,5,1,2,4,2,1,3,1,0,0,0,1,0,0,0,1,5,4,9,3,2,0,0,0,0,该初始单纯形表对应的初始解为,X,=(0,，,0,，,5,，,4,，,9),T,。对应目标函数值为,0.,因为,x,1,的检验数,我们选择,x,1,作为,换入变量,。这样可以使目标函数增加得更快。,然后用,b,列的数除以换入变量列的正的系数，所得最小商对应的变量,x,4,为换出变量。,56,以,x,3,x,1,x,5,作为基变量得到,第二张单纯形表按,如下方式计算：,3,2,0,0,0,C,B,X,B,x,1,x,2,x,3,x,4,x,5,b,0,0,0,x,3,x,4,x,5,1,2,4,2,1,3,1,0,0,0,1,0,0,0,1,5,4,9,3,2,0,0,0,0,该元素称为主元。下面开始迭代，,迭代的目标,就是把主元化为,1,，然后把主元所在列其他系数化为,0,。,x,1,3,3,2,1/2,0,1/2,1,0,0,0,3/2,1,-1/2,0,0,0,1,0,-2,1,1,0,1/2,0,-3/2,6,0,该单纯形表对应的基可行解为,X,=,（,2,，,0,，,3,，,0,，,1,）,T,，对应目标函数值为,6,。,现在,x,2,的检验数为,1/20,，且最大，所以我们选择,x,2,为换入变量。,因为,min3/,(3/2),2/,(1/2),1/1=1,所以选择,x,5,作为换出变量。,57,以,x,3,x,1,x,2,作为基变量得到,第三张单纯形表,如下所示：,3,2,0,0,0,C,B,X,B,x,1,x,2,x,3,x,4,x,5,b,0,3,0,x,3,x,1,x,5,0,1,0,3/2,1/2,1,1,0,0,-1/2,1/2,-2,0,0,1,3,2,1,0,1/2,0,-3/2,0,6,2,x,2,0,1,0,-2,1,1,0,0,0,1,5/2,-3/2,3/2,3,1,0,0,3/2,-1/2,3/2,0,0,0,-1/2,-1/2,13/2,现在所有的检验数都小于或者等于,0,，所以得到最优解为：,最优目标函数值为,13/2,。,该表称为最终单纯形表，其具有什么特征？,58,合并的单纯形表,3,2,0,0,0,C,B,X,B,x,1,x,2,x,3,x,4,x,5,b,0,0,0,x,3,x,4,x,5,1,2,4,2,1,3,1,0,0,0,1,0,0,0,1,5,4,9,5/1,4/2,9/4,3,2,0,0,0,0,0,3,0,x,3,x,1,x,5,0,1,0,3/2,1/2,1,1,0,0,-1/2,1/2,-2,0,0,1,3,2,1,2,4,1,0,1/2,0,-3/2,0,6,0,3,2,x,3,x,1,x,2,0,1,0,0,0,1,1,0,0,5/2,3/2,-2,-3/2,-1/2,1,3/2,3/2,1,0,0,0,-1/2,-1/2,13/2,59,单纯形法计算过程,构造初始单纯形表,对标准化后的线性规划问题，首先找出初始基变量，构造初始单纯形表。相应地可以得到初始基可行解，基可行解的目标函数值。,最优性检验,若得到单纯形表中所有的检验数都小于或等于零，则该单纯形表给出的基可行解就是最优解，终止计算。否则进行下一步。,确定换入变量,选择最大的正检验数对应的非基变量为换入变量。,确定换出变量,若换入变量（更一般地，若某个正检验数对应的变量）所作列的系数均小于或等于零，则线性规划问题为无界解，终止计算。否则用换入变量所作列的系数去除,b,列的对应数，在除得的商中选择最小者对应的基变量为换出变量。,旋转运算,确定换入和换出变量后得到新的基变量，然后以换入变量所在列、换出变量所在行交叉处的元素为主元，通过矩阵的初等行变换（一般不使用交换两行的运算）将约束方程组增广矩阵中主元变换为,1,，主元列的其它元素变换为零。从而得到一个新的单纯形表。然后回到第,2,步。,60,唯一最优解与无穷多个最优解,若最终单纯形表的非基变量的检验数都小于零,则线性规划问题有唯一的最优解,若最终单纯形表中存在某个非基变量,其检验数等于零,则该线性规划问题有无穷多个最优解,.,61,例,2.4,利用单纯形法求解下列线性规划问题,首先将线性规划标准化,62,很明显可以以,x4,、,x5,作为初始基变量，得到初始单纯形如下：,-2,1,2,0,0,C,B,X,B,x,1,x,2,x,3,x,4,x,5,b,0,0,x,4,x,5,3,2,-2,-1,-2,1,1,0,0,1,1,4,-2,1,2,0,0,此时，,x,2,的检验数大于,0,，还没有得到最优解。但是我们以,x,2,作为换入变量，但是,x,2,所在列所有系数都小于,0,，此时该线性规划存在,无界解,。,63,课堂作业,:,用单纯形法求解,解：将数学模型化为标准形式：,不难看出,x,4,、,x,5,可作为初始基变量，列单纯形表计算。,64,单纯形法的计算步骤,c,j,1,2,1,0,0,i,c,B,基变量,b,x,1,x,2,x,3,x,4,x,5,0,x,4,15,2,-3,2,1,0,0,x,5,20,1/3,1,5,0,1,1,2,1,0,0,0,x,4,2,x,2,20,x,2,2,1/3,1,5,0,1,20,75,3,0,17,1,3,1/3,0,9,0,2,25,60,x,1,1,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,65,单纯形法小结,66,c,j,i,C,B,X,B,b,x,1,x,2,x,3,x,4,x,5,x,m,6,b,c,d,1,0,x,n,1,-1,3,e,0,1,j,a,1,-2,0,0,x,s,f,g,2,-1,1/2,0,x,t,4,h,i,1,1/2,1,j,0,-7,j,k,l,2,、某求极大值,LP,问题的初始及经过一次迭代后的单纯形表，表如下，,x,4,、,x,5,为松驰变量，试求表中,a-l,及,m-t,的值。,解（,1,）因为初始表中,x,4,、,x,5,为基变量，所以，,m,4,；,n,5,；,67,（,2,）迭代后的表中，基变量为：,x,1,、,x,5,，因此：,g,1,；,h,0,；,s,1,；,t,5,；,c,j,a,1,2,0,0,i,C,B,X,B,b,x,1,x,2,x,3,x,4,x,5,0,x,4,6,b,c,d,1,0,0,x,5,1,-1,3,e,0,1,j,a,1,-2,0,0,x,s,f,g,2,-1,1/2,0,x,t,4,h,i,1,1/2,1,j,0,-7,j,k,l,68,（,3,）,x,5,为基变量，,l,0,；,（,4,）,p,4,由第一个表的,1,0,T,变为第二个表中的,1/2,1/2,T,，,即,/2,，因此，,f,3,；,b,2,；,c,4,；,d,2,；,c,j,a,1,2,0,0,i,C,B,X,B,b,x,1,x,2,x,3,x,4,x,5,0,x,4,6,b,c,d,1,0,0,x,5,1,-1,3,e,0,1,j,a,1,-2,0,0,a,x,1,f,1,2,-1,1/2,0,0,x,5,4,0,i,1,1/2,1,j,0,-7,j,k,l,69,（,5,）同理，行,行,行,i,5,；,e,2,；,（,6,）,2,1,2a,-7,，所以，,a,4,；,（,7,）,j,2,；,k,-2,；,c,j,a,1,2,0,0,i,C,B,X,B,b,x,1,x,2,x,3,x,4,x,5,0,x,4,6,2,4,2,1,0,0,x,5,1,-1,3,e,0,1,j,a,1,-2,0,0,a,x,1,3,1,2,-1,1/2,0,0,x,5,4,0,i,1,1/2,1,j,0,-7,j,k,0,70,