线性代数第7章

1、1 1 1 1线性代数第一章线性代数第一章 1.1 第七章第七章 线性规线性规划划2 2 22线性代数线性代数 第七章第七章线性规划研究的主要问题线性规划研究的主要问题 一类是已有一定数量的资源（人力、物质、时间等），研一类是已有一定数量的资源（人力、物质、时间等），研究如何充分合理地使用它们，才能使完成的任务量为最大。究如何充分合理地使用它们，才能使完成的任务量为最大。 实际上，上述两类问题是一个问题的两个不同的方面，实际上，上述两类问题是一个问题的两个不同的方面，都是求问题的最优解（都是求问题的最优解（ maxf 或或 minf ）。）。 另一类是当一项任务确定以后，研究如何统筹安排，另一

2、类是当一项任务确定以后，研究如何统筹安排，才能使完成任务所耗费的资源量为最少。才能使完成任务所耗费的资源量为最少。3 3 33线性代数线性代数 第七章第七章 1939年，前苏联数学家康托洛维奇用线性模型研究提高年，前苏联数学家康托洛维奇用线性模型研究提高组织和生产效率问题组织和生产效率问题 1947年，美国数学家丹茨格（年，美国数学家丹茨格（Dantzig）提出求解线性规）提出求解线性规划的单纯形法划的单纯形法 1950-1956年，主要研究线性规划的对偶理论年，主要研究线性规划的对偶理论 1958年，发表整数规划的割平面法年，发表整数规划的割平面法 1960年，年，Dantzig和和Wolf

3、e研究成功分解算法，奠定了大规研究成功分解算法，奠定了大规模线性规划问题理论和算法的基础。模线性规划问题理论和算法的基础。 1979年，年，Khachiyan，1984年，年，Karmarkaa研究成功线性研究成功线性规划的多项式算法。规划的多项式算法。线性规划的发展线性规划的发展4 4 44线性代数线性代数 第七章第七章例例1.1 某厂生产两种产品，下表给某厂生产两种产品，下表给出了单位产品所需资源及单位产品出了单位产品所需资源及单位产品利润利润 问：应如何安排生产计划，才能使问：应如何安排生产计划，才能使 总利润最大？总利润最大？ 7.1 7.1 线性规划的数学模型线性规划的数学模型一、问

4、题的提出一、问题的提出解：解：1.决策变量：设产品决策变量：设产品I、II的产量分的产量分 别为别为 x1、x22.目标函数：设总利润为目标函数：设总利润为z，则有：，则有： max z = 2 x1 + 3 x23.约束条件：约束条件： x1 + 2x2 8 4x1 16 4x2 12 x1， x205 5 55线性代数线性代数 第七章第七章例例1.2 某厂生产三种药物，这些药某厂生产三种药物，这些药物可以从四种不同的原料中提取。物可以从四种不同的原料中提取。下表给出了单位原料可提取的药物下表给出了单位原料可提取的药物量量要求：生产要求：生产A种药物至少种药物至少160单位；单位；B种药物恰

5、好种药物恰好200单位，单位，C种药物不种药物不超过超过180单位，且使原料总成本最单位，且使原料总成本最小。小。解：解：1.决策变量：设四种原料的使用决策变量：设四种原料的使用 量分别为：量分别为： x1、x2 、x3 、x42.目标函数：设总成本为目标函数：设总成本为z，则有：，则有： min z = 5 x1 + 6 x2 + 7 x3 + 8 x43.约束条件：约束条件： x1 + 2x2 + x3 + x4 160 2x1 +4 x3 +2 x4 160 3x1 x2 +x3 +2 x4 180 x1、x2 、x3 、x40 药物药物原料原料ABC单位成本单位成本（元吨）（元吨）甲甲

6、1235乙乙2016丙丙1417丁丁12286 6 66线性代数线性代数 第七章第七章模型特点模型特点1 都用一组决策变量都用一组决策变量X = (x1,x2,xn)T表示某一方案，且决策变量表示某一方案，且决策变量取值非负；取值非负； 满足以上三个条件的数学模型称为线性规划满足以上三个条件的数学模型称为线性规划2 都有一个要达到的目标，并且目标要求可以表示成决策变量都有一个要达到的目标，并且目标要求可以表示成决策变量的线性函数；的线性函数；3 都有一组约束条件，这些约束条件可以用决策变量的线性等都有一组约束条件，这些约束条件可以用决策变量的线性等式或线性不等式或线性不等 式来表示。式来表示。

7、7 7 77线性代数线性代数 第七章第七章二二. . 线性规划的数学模型线性规划的数学模型一般表示方式一般表示方式nnnxcxcxcxxf 22111),(min(max) 0,),(),(),(.2122112222212111212111nmnmnmmnnnnxxxbxaxaxabxaxaxabxaxaxats均为实常数均为实常数式中的式中的ijijbca,8 8 88线性代数线性代数 第七章第七章线性规划的标准形有如下四个特点：线性规划的标准形有如下四个特点： 目标最小化、目标最小化、 约束为等式、约束为等式、 变量均非负、变量均非负、 右端约束常数非负。右端约束常数非负。 0,),(m

8、in212211222221211121211122111nmnmnmmnnnnnnnxxxbxaxaxabxaxaxabxaxaxaxcxcxcxxf标准标准2134, 0 ib9 9 99线性代数线性代数 第七章第七章线性规划模型的变换线性规划模型的变换1 1 极小化目标函数的问题极小化目标函数的问题设目标函数为设目标函数为nnxcxcxcfMax 2211nnxcxcxcfMin 2211令令 则可转化为标准形则可转化为标准形ff 2 右端项有负值的问题右端项有负值的问题inniiibxaxaxa 2211 在标准形式中，要求右端项必须每一个分量非在标准形式中，要求右端项必须每一个分量非

9、负负，当某一个右端项系数为负时，则把该等式约束两当某一个右端项系数为负时，则把该等式约束两端同时乘以端同时乘以1 1，得到：，得到：10101010线性代数线性代数 第七章第七章3 3约束条件不是等式的问题约束条件不是等式的问题inniiibxaxaxa 2211isnniiibyxaxaxa 2211（1）设约束条件为：）设约束条件为：可以引进一个新的变量可以引进一个新的变量 使得：使得：iy显然，显然， 也具有非负约束，即也具有非负约束，即 0iyiy （2 2）当约束条件为：）当约束条件为：inniiibxaxaxa 2211 如果原问题中有若干个非等式约束，则将其转化为标准如果原问题中

10、有若干个非等式约束，则将其转化为标准形式时，必须对各个约束引进不同的松弛变量。形式时，必须对各个约束引进不同的松弛变量。可以引进一个新的变量可以引进一个新的变量 使得：使得：syiinniiibyxaxaxa 2211显然，显然， 也具有非负约束，即也具有非负约束，即 0sysy为了使约束由不等式成为等式而引进的变量为了使约束由不等式成为等式而引进的变量 ， 称为称为“松弛变量松弛变量”。siyy ,11111111线性代数线性代数 第七章第七章 在标准形式中，必须每一个变量有非负约束，当在标准形式中，必须每一个变量有非负约束，当某一个变量某一个变量 xj 没有非负约束时，令没有非负约束时，令

11、 jjjxxx0,0 jjxx变量无符号限制的问题变量无符号限制的问题12121212线性代数线性代数 第七章第七章例例1 将将 线性规划模型化为标准型。线性规划模型化为标准型。 0,12416482.212121xxxxxxts 2132minxxf5432100032minxxxxxf 0,12416482.43215241321xxxxxxxxxxxxts13131313线性代数线性代数 第七章第七章 例例2.2.线性规划模型化为标准型。线性规划模型化为标准型。 0,2004006653004432.0004423)(min:65433216332153321433216543321xx

12、xxxxxxxxxxxxxxxxxxxxtsxxxxxxxxf标准型标准型 0, ,20040065300432.423)(max:213321321321321xxxxxxxxxxxxtsxxxxf不限不限原非标准型原非标准型14141414线性代数线性代数 第七章第七章标准标准矩阵式矩阵式 0bA.C)(min xxtsxxfTTmTnTnmnmmnnbbbxxxxcccaaaaaaaaa),(b),(;),(CA212121212222111211 其中，其中，15151515线性代数线性代数 第七章第七章三三 线性规划模型解的基本概念线性规划模型解的基本概念定义定义7.1.0,.),(

13、21称为可行域称为可行域有可行解的集合有可行解的集合为该问题的可行解。所为该问题的可行解。所则称则称标准形式中的约束条件标准形式中的约束条件若满足线性规划模型的若满足线性规划模型的向量向量DxxbAxtsxxxxTn 定义定义7.2.),()(,优优解解为为该该线线性性规规划划问问题题的的最最则则称称有有即即上上达达到到最最小小值值，在在解解，且且使使目目标标函函数数为为线线性性规规划划模模型型的的可可行行设设xxfxfDxDfx 性质性质7.1。其其可可行行解解，其其中中仍仍是是解解，则则为为线线性性规规划划模模型型的的可可行行若若10)1(,2121 xxxxxbbbAxAxxxAAxbA

14、xbAx )1()1()1(,212121 所有所有证明：因为证明：因为16161616线性代数线性代数 第七章第七章.10)1(,2121为凸集为凸集，则称集合，则称集合其中其中有有意意为非空集合，如果对任为非空集合，如果对任一般地，设一般地，设DDxxDxxD 性质性质7.2 若线性规划模型的可行域非空，则可行域为凸集若线性规划模型的可行域非空，则可行域为凸集17171717线性代数线性代数 第七章第七章0123451243例例1.求解线性规划问题求解线性规划问题 )2 , 1(03482.43max212121jxxxxxtsxxfj., 0,. 33:4:82:. 2.,. 1.212

15、31221121域域取交集即为所求的可行取交集即为所求的可行半平面，结合半平面，结合确定每个不等式表示的确定每个不等式表示的约束画出约束画出用等式约束代替不等式用等式约束代替不等式看作平面上的点的坐标看作平面上的点的坐标把决策变量把决策变量定的可行域定的可行域一。画出由约束条件确一。画出由约束条件确 xxxlxlxxlxx., 1 , 04343443.1221坐坐标标就就是是要要求求的的最最优优解解因因此此，极极限限位位置置的的点点的的，增增多多的的方方向向如如箭箭头头所所指指平平行行线线簇簇在在平平面面上上截截距距的的平平行行线线簇簇，令令为为变变化化时时便便产产生生一一簇簇斜斜率率当当变

16、变形形为为为为此此，将将目目标标函函数数最最大大值值的的可可行行域域中中的的点点最最优优解解是是使使目目标标函函数数去去从从可可行行域域中中找找出出最最优优解解二二 ffxfxxxf7.2线性规划问题的图解法线性规划问题的图解法18181818线性代数线性代数 第七章第七章 482121xxx极值点满足方程极值点满足方程.20min,)2 , 4(.2024 fxfT最优目标函数值最优目标函数值因此得唯一最优解因此得唯一最优解），此时），此时，求得极值点坐标（求得极值点坐标（19191919线性代数线性代数 第七章第七章 0022.2min21212121xxxxxxtsxxf为无界域。为无界

17、域。可以看到，其可行域可以看到，其可行域域域取交集即为所求的可行取交集即为所求的可行半平面，结合半平面，结合确定每个不等式表示的确定每个不等式表示的约束画出约束画出用等式约束代替不等式用等式约束代替不等式定的可行域定的可行域一。画出由约束条件确一。画出由约束条件确., 0,. 22:2:. 1.21212211 xxxxlxxl01234512431x2x., 1 , 0212212.1221坐标就是要求的最优解坐标就是要求的最优解因此，极限位置的点的因此，极限位置的点的，减少的方向如箭头所指减少的方向如箭头所指平行线簇在平面上截距平行线簇在平面上截距的平行线簇，令的平行线簇，令为为变化时便产

18、生一簇斜率变化时便产生一簇斜率当当变形为变形为为此，将目标函数为此，将目标函数从可行域中找出最优解从可行域中找出最优解二二 fffxxxxf 22121xxx 极值点满足方程极值点满足方程. 2min,)02(. 202 fxfT最优目标函数值最优目标函数值，因此得唯一最优解因此得唯一最优解），此时），此时，求得极值点坐标（求得极值点坐标（例例2.求解线性规划问题求解线性规划问题20202020线性代数线性代数 第七章第七章 04182.36max2212121xxxxxtsxxf01234512431x2x., 0,. 24:1:82:. 1.212312211域域取交集即为所求的可行取交集

19、即为所求的可行半平面，结合半平面，结合确定每个不等式表示的确定每个不等式表示的约束画出约束画出用等式约束代替不等式用等式约束代替不等式定的可行域定的可行域一。画出由约束条件确一。画出由约束条件确 xxxlxlxxl122112.632320,1,28.max24.ffxxxxffxxABf 二 从可行域中找出最优解为此，将目标函数变形为当 变化时便产生一簇斜率为 的平行线簇，令平行线簇在平面上截距增大的方向如箭头所指，此时，极限位置恰与可行域的边界线 重合因此，边界线段上的所有点均为最优解例例3.求解线性规划问题求解线性规划问题21212121线性代数线性代数 第七章第七章0123451243

20、1x2x 0025.3min2112121xxxxxtsxxf为空集。为空集。可以看到，其可行域可以看到，其可行域域域取交集即为所求的可行取交集即为所求的可行半平面，结合半平面，结合确定每个不等式表示的确定每个不等式表示的约束画出约束画出用等式约束代替不等式用等式约束代替不等式定的可行域定的可行域一。画出由约束条件确一。画出由约束条件确., 0,. 22:5:. 1.2112211 xxxlxxl. 3也也就就没没有有最最优优解解因因此此没没有有可可行行解解，当当然然可可行行域域是是空空集集，由由于于该该线线性性规规划划问问题题的的例例4.求解线性规划问题求解线性规划问题22222222线性代

21、数线性代数 第七章第七章图解法解题步骤： 1.确定可行域 2.做目标函数等值线，确定目标函数增大或减少的方向； 3.确定最优解和最优值23232323线性代数线性代数 第七章第七章线性规划最优解的3种情况： 1.不存在最优解；此时可行域为空集或者为非空无界集； 2.存在唯一的最优解，此最优解为可行域的顶点，此时可行域为非空有界集或者为非空无界集； 3.存在唯一的最优解，此最优解与可行域的一条边界重回。 由于边界上必包含可行域的顶点，因此，必有最优解为可行域的顶点。24242424线性代数线性代数 第七章第七章7.3线性规划问题的单纯形法线性规划模型的标准型线性规划模型的标准型 ), 2 , 1

22、( , 0.22112222212111212111njxbxaxaxabxaxaxabxaxaxatsjmnmnmmnnnnnnxcxcxcf 2211min其约束方程为其约束方程为 mnmmmmnmnmaaaaaaaaaaaa21222221111211 nnbbbxxx2121nmAr )(不不妨妨假假设设非非基基变变量量。为为基基变变量量，否否则则称称为为包包含含在在基基中中，则则称称所所对对应应的的列列向向量量若若变变量量基基矩矩阵阵，简简称称一一个个基基。为为线线性性规规划划模模型型的的一一个个则则称称若若阶阶子子阵阵，的的一一个个）为为约约束束矩矩阵阵（设设定定义义jjjjjjx

23、pxBmArmmApppBp,)(,3 . 721 1x2x25252525线性代数线性代数 第七章第七章 mnmmmmnmnmaaaaaaaaaaaa21222221111211 nnbbbxxx2121约束方程约束方程mAr )(每给非基变量一组值，就能得到非基变量的一组相应的值，每给非基变量一组值，就能得到非基变量的一组相应的值，从而得到线性规划问题的一个解从而得到线性规划问题的一个解。特别地特别地：127.4( , ,)TnBAx bxx xxBB 定义设 为线性规划模型的一个基，令所有非基变量为零而得到的满足的解称为对应于基 的基本解。如果基本解非负，则称为基本可行解。此时，称其对应

24、的基 为可行基。注：若约束等式中有注：若约束等式中有n个变量，个变量，m个约束，则个约束，则基本解基本解的个数的个数mnC26262626线性代数线性代数 第七章第七章令非基变量令非基变量 x10，x2 0则得：则得：x (0, 0, 3, 1 )T基本解基本解2：基变量为：基变量为x2、x3，非基变量为，非基变量为x1、x4令非基变量令非基变量 x10，x4 0则得：则得：x (0, 1, 5, 0 )T基本解基本解非基本可行解非基本可行解基本可行解基本可行解例例 讨论下述约束方程的解讨论下述约束方程的解 x1 2x2 x3 3 2x1 x2 x4 1解解约束矩阵为：约束矩阵为：101201

25、21A1：基变量为：基变量为x3、x4，非基变量为，非基变量为x1、x23:x (1/2, 1/2, 3/2, 1/2)T不是基本解不是基本解可行解可行解不是基本可行解不是基本可行解27272727线性代数线性代数 第七章第七章线性规划解的性质线性规划解的性质 线性规划问题的一个解线性规划问题的一个解x x为基可行解的充分必要条件是：为基可行解的充分必要条件是：x x的的非零分量所对应的系数矩阵非零分量所对应的系数矩阵A A的列向量线性无关的列向量线性无关。 mnmmmmnmnmaaaaaaaaaaaa21222221111211 nnbbbxxx2121若线性规划问题存在可行解，则一定存在基

26、本可行解若线性规划问题存在可行解，则一定存在基本可行解若线性规划问题存在最优解，则一定存在基本可行解且此解为最若线性规划问题存在最优解，则一定存在基本可行解且此解为最 优解优解. .28282828线性代数线性代数 第七章第七章二二.单纯形法基本思想单纯形法基本思想.求解线性规划问题：求解线性规划问题： 0,12 4 16 48 232min54321524132121xxxxxxxxxxxxxxf1、构造初始可行基；、构造初始可行基； 1 0 00 1 00 0 1),(5430PPPB 1 0 0 4 00 1 0 0 40 0 1 2 1),.,(51PPA根据根据可构成初始可行基可构成

27、初始可行基为为基基变变量量443,xxx2、求出一个基本可行解、求出一个基本可行解032 )12,16, 8 , 0 , 0(, 0021)0()0(21 ）（，得得代代入入目目标标函函数数把把，得得一一基基本本可可行行解解代代入入约约束束方方程程令令：fxxfxxxx3、最优性检验：判断是否最优解；、最优性检验：判断是否最优解； 是否是最优解是否是最优解？不是最优基不是最优基不是最优解，不是最优解，小，所以小，所以增大，便使目标函数减增大，便使目标函数减分析目标函数，只要分析目标函数，只要（0)02Bxx怎么办？换基怎么办？换基从一个基本可行解出发，经从一个基本可行解出发，经换基迭代，找出另

28、一个基本换基迭代，找出另一个基本可行解同时不断改进目标函可行解同时不断改进目标函数直到判断出是否有最优解数直到判断出是否有最优解.29292929线性代数线性代数 第七章第七章4、基变换，寻找新的基本可行解、基变换，寻找新的基本可行解.进基：进基：.22量量由由非非基基变变量量变变换换成成基基变变因因此此，把把小小增增大大，便便使使目目标标函函数数减减由由于于xx出基：出基：.2量量必必须须有有一一个个变变成成非非基基变变进进基基，因因而而原原基基变变量量中中由由于于x谁呢？谁呢？0,0543112 xxxxxx保保持持，并并要要新新基基本本可可行行解解中中仍仍取取仍仍为为非非基基变变量量，所

29、所以以在在进进基基后后，当当.03.0. 0,3)4/12, 2/8min( 04 12 0 16 02 8 5525432543225423出出基基，因因此此确确定定时时，注注意意到到）解解中中取取（非非基基变变量量在在基基本本可可行行中中有有一一个个取取值值为为的的取取值值还还必必须须使使中中有有一一个个出出基基，为为使使xxxxxxxxxxxxxxxx 因此，基由因此，基由 变为变为)(5430PPPB )(2431PPPB 转第转第2步：求出一个基本可行解步：求出一个基本可行解.932 )0 ,16,2 ,3 ,0(,0121)0()1(51目目标标函函数数值值得得以以改改善善，得得代

30、代入入目目标标函函数数把把，得得一一基基本本可可行行解解代代入入约约束束方方程程令令：）（ fxxfXXxxf (1) 是否是最优解是否是最优解？30303030线性代数线性代数 第七章第七章3、最优性检验：判断是否最优解；、最优性检验：判断是否最优解；在新基下，把约束方程中的基变量用非基变量表示在新基下，把约束方程中的基变量用非基变量表示 04 16 0 21 2 41 3 1451352xxxxxxx9432325121 xxfxxf以以后后的的目目标标函函数数基基变变量量表表示示，得得到到改改进进这这样样，将将目目标标函函数数用用非非，再再代代入入目目标标函函数数.0,51将将增增大大变

31、变大大时时，由由易易见见，非非基基变变量量fxx. 9min)0 ,16, 2 , 3 , 0()1( fX是是最最优优解解，所所以以 0,12 4 16 48 232min54321524132121xxxxxxxxxxxxxxf31313131线性代数线性代数 第七章第七章 0,12 4 16 48 232min54321524132121xxxxxxxxxxxxxxf上例可通过以下形式求解上例可通过以下形式求解),(5430PPPB 定定一一个个可可行行基基首首先先，从从约约束束方方程程中中选选03221 xxf成方程形式：成方程形式：将目标函数表达式改写将目标函数表达式改写 03212

32、 4 16 48 2215241321xxfxxxxxxx下下线线性性方方程程组组：于于是是，标标准准型型可可视视为为如如行行变变换换对对其其增增广广矩矩阵阵施施以以初初等等1x3x2x4x5xb 01216801 00 00 34 200 1 0 0 40 0 1 2 1 54321 bxxx xx.12x确确定定进进基基变变量量为为是是否否为为正正）按按目目标标函函数数中中的的系系数数（值值原原则则确确定定离离基基变变量量。列列的的正正系系数数，按按最最小小比比以以进进基基变变量量所所在在）用用约约束束常常数数项项分分别别除除（2.3量量进进基基变变量量成成为为单单位位列列向向上上通通过过

33、行行变变换换使使）换换基基迭迭代代过过程程，实实际际（非基变量非基变量基变量基变量001032323232线性代数线性代数 第七章第七章 01216801 00 00 34 200 1 0 0 40 0 1 2 1 54321 bxxx xx1x3x2x4x5xb 3162 00 00 0100 1 0 0 4 0 1 01 54321 bxxx xx1x3x2x4x5xb943251xxf. 9min)0 ,16, 2 , 3 , 0()1( fx是最优解，是最优解，所以所以21414329001033333333线性代数线性代数 第七章第七章 2 3 0 0 0 1 2 1 0 0 4 0

34、 0 1 0 0 4 0 0 1 8 16 122 3 0 0 0 03x5x1x2x3x4x5xjx基变量基变量4xjcj 检验数检验数常常数数单纯形方法单纯形方法单纯形方法是表格化的换基迭代法单纯形方法是表格化的换基迭代法.用单纯形方法解线性规划问题需将用单纯形方法解线性规划问题需将增广矩阵换基迭代的过程用表格形式表示出来增广矩阵换基迭代的过程用表格形式表示出来.,0, 03. 1222作作为为进进基基变变量量因因此此目目标标函函数数值值减减小小增增大大时时由由其其对对应应的的变变量量量量的的系系数数称称为为检检验验数数。成成方方程程形形式式，其其决决策策变变将将目目标标函函数数非非基基化

35、化后后写写xxcjj 就就是是离离基基变变量量。原原来来基基变变量量的的最最小小值值所所在在行行对对应应的的按按最最小小比比值值原原则则其其比比值值5. 2x代。代。，就完成了一次换基迭，就完成了一次换基迭列其余元素化为列其余元素化为，该，该为为，称为主元素。将其化，称为主元素。将其化的的基变量所在行的交叉处基变量所在行的交叉处以进基变量所在列与离以进基变量所在列与离014. 3 0,12 4 16 48 232min54321524132121xxxxxxxxxxxxxxf34343434线性代数线性代数 第七章第七章 2 0 0 0 1 0 1 0 4 0 0 1 0 0 1 0 0 8

36、16 3 0 0 0 3x2x1x2x3x4x5xjx基变量基变量4xjcj 检验数检验数常常数数21414343. 0 此时，因为全部检验数此时，因为全部检验数. 9min)0 ,16, 2 , 3 , 0()1( fx是最优解，是最优解，所以所以2935353535线性代数线性代数 第七章第七章 . 3 , 2 , 1, 062253222.33max. 1321321321221jxxxxxxxxxxtsxxxfj求线性规划问题求线性规划问题例例 -3 -1 -3 0 0 0 2 1 1 1 0 0 1 2 3 0 1 0 2 2 1 0 0 1 2 5 6 3 1 3 0 0 0 0j

37、x基变量基变量jcj 检验数检验数常常数数1x4x3x2x5x6x6x4x5x.2,2226,15,22min, 04111321xax，离离基基变变量量为为故故主主元元素素为为由由于于此此进进基基变变量量为为先先考考虑虑下下标标最最小小的的。因因，此此时时检检验验数数 6 , 5 , 4 , 3 , 2 , 1, 062253222.33min632153214321321jxxxxxxxxxxxxxtsxxxfj解：化为标准形式：解：化为标准形式：36363636线性代数线性代数 第七章第七章 jx基变量基变量jcj 检验数检验数常常数数1x4x3x2x5x6x6x1x5x21212125

38、2323210212300000212311113440110002300为进基变量。为进基变量。此时，此时，33. 023x 254254,211min 由于由于为离基变量。为离基变量。，所以主元素为所以主元素为52325xa 代。代。，就完成了一次换基迭，就完成了一次换基迭，列其余元素化为，列其余元素化为将主元素化为将主元素化为01. 3037373737线性代数线性代数 第七章第七章 jx基变量基变量jcj 检验数检验数常常数数1x4x3x2x5x6x6x1x3x15351151000005153515258000011140000575653527575653. 0 此时，因为全部检验

39、数此时，因为全部检验数.527min)400 ,58, 0 ,51( fx是最优解，是最优解，所以所以.527max) ,58, 0 ,51( fx是最优解，是最优解，故，原问题中故，原问题中迭代。迭代。，再次完成了一次换基，再次完成了一次换基，列其余元素化为，列其余元素化为将主元素化为将主元素化为0138383838线性代数线性代数 第七章第七章321254540min. 3xxxf 求线性规划问题求线性规划问题例例 . 543 , 2 , 1, 012023310032.53214321，jxxxxxxxxxtsj53 jx基变量基变量jcj 检验数检验数常常数数1x4x3x2x5x4x5

40、x jx基变量基变量jcj 检验数检验数常常数数1x4x3x2x5x4x1x40454025000000000120321005116001111332452553323400311132031204005530340(二二)(一一)39393939线性代数线性代数 第七章第七章 jx基变量基变量jcj 检验数检验数常常数数1x4x3x2x5x2x1x jx基变量基变量jcj 检验数检验数常常数数1x4x3x2x5x2x3x000000020110000000051017001111132313238031312015170051011120100510(四四)(三三)为为主主元元素素，得得表表四四。为为离离基基变变量量，为为进进基基变变量