管理会计MAchp6线性规划

1、运筹学运筹学 Operations ResearchChapter 1 线性规划线性规划 Linear Programming1.1 LP的数学模型的数学模型 Mathematical Model of LP 1.2 图解法图解法 Graphical Method 1.3 标准型标准型 Standard form of LP 1.4 基本概念基本概念 Basic Concepts 1.5 单纯形法单纯形法 Simplex Method Chapter 1 线性规划线性规划 Linear Programming【例例1.1】最优生产计划问题最优生产计划问题。某企业在计划期内计划。某企业在计划期内

2、计划生产甲、乙、丙三种产品。这些产品分别需要在设备生产甲、乙、丙三种产品。这些产品分别需要在设备A、B上加工，需要消耗材料上加工，需要消耗材料C、D，按工艺资料规定，按工艺资料规定，单件产品在不同设备上加工及所需要的资源如表单件产品在不同设备上加工及所需要的资源如表1.1所所示。已知在计划期内设备的加工能力各为示。已知在计划期内设备的加工能力各为200台时，可台时，可供材料分别为供材料分别为360、300公斤；每生产一件甲、乙、丙公斤；每生产一件甲、乙、丙三种产品，企业可获得利润分别为三种产品，企业可获得利润分别为40、30、50元，假元，假定市场需求无限制。企业决策者应如何安排生产计划，定市

3、场需求无限制。企业决策者应如何安排生产计划，使企业在计划期内总的利润收入最大？使企业在计划期内总的利润收入最大？1.1.1 应用模型举例应用模型举例1.1 线性规划的数学模型线性规划的数学模型 Mathematical Model of LPChapter 1 线性规划线性规划 Linear Programming 产品产品 资源资源 甲甲 乙乙丙丙现有资源现有资源设备设备A 3 1 2 200设备设备B 2 2 4 200材料材料C 4 5 1 360材料材料D 2 3 5 300利润利润(元元/件件) 40 30 50表表1.1 产品资源消耗产品资源消耗1.1 线性规划的数学模型线性规划的

4、数学模型 Mathematical Model of LPChapter 1 线性规划线性规划 Linear Programming321503040maxxxxZ0003005323605420042220023321321321321321xxxxxxxxxxxxxxx，【解解】 设设x1、x2、x3 分别为甲、乙、丙三种产品的产分别为甲、乙、丙三种产品的产量量, 则则 数学模型为：数学模型为： 产品产品 资源资源甲甲 乙乙丙丙现有现有 资源资源设备设备A 3 1 2 200设备设备B 2 2 4 200材料材料C 4 5 1 360材料材料D 2 3 5 300利润利润(元元/件件) 4

5、0 30 50最优解最优解X=(50,30,10); Z=34001.1 线性规划的数学模型线性规划的数学模型 Mathematical Model of LPChapter 1 线性规划线性规划 Linear Programming【例例1.2】某商场决定：营业员每周连续工作某商场决定：营业员每周连续工作5天后连续天后连续休息休息2天，天， 轮流休息。根据统计，商场每天需要的营业轮流休息。根据统计，商场每天需要的营业员如表员如表1.2所示。所示。表表1.2 营业员需要量统计表营业员需要量统计表问：问：商场人力资源部应如何安排每天的上班人数，使商商场人力资源部应如何安排每天的上班人数，使商场总

6、的营业员最少？场总的营业员最少？ 星期星期 需要人数需要人数 星期星期 需要人数需要人数 一一 300 五五 480 二二 300 六六 600 三三 350 日日 550 四四 400 【解解】 设设 ( j=1，2，7)为休息为休息2天后星期一到星天后星期一到星期日开始上班的营业员，则这个问题的线性规划模型为期日开始上班的营业员，则这个问题的线性规划模型为 jx1.1 线性规划的数学模型线性规划的数学模型 Mathematical Model of LPChapter 1 线性规划线性规划 Linear Programming7,2, 1,0550600480400350300300min

7、765436543254321743217632176521765417654321jxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxZj1.1 线性规划的数学模型线性规划的数学模型 Mathematical Model of LP星期星期 需要人数需要人数 星期星期 需要人数需要人数 一一 300 五五 480 二二 300 六六 600 三三 350 日日 550 四四 400 Chapter 1 线性规划线性规划 Linear Programming1 1解决问题的目标函数是多个决策变量的线性函数，通常是解决问题的目标函数是多个决策变量的线性函数，通

8、常是 求最大值或最小值求最大值或最小值； 2 2解决问题的解决问题的是一组多个决策变量的线性不等式或是一组多个决策变量的线性不等式或等式等式。线性规划数学模型的线性规划数学模型的特征：特征：线性规划数学模型的线性规划数学模型的三要素：三要素：决策变量决策变量( Decision variables); 目标函数目标函数(Objective function); 约束条件约束条件(Constraints); 建立一个问题的线性规划模型的建立一个问题的线性规划模型的一般步骤：一般步骤：确定决策变量；确定决策变量； (2)(2)确定目标函数；确定目标函数； (3)(3)确定约束条件；确定约束条件；

9、(4)(4)确定变量是否有非负约束。确定变量是否有非负约束。1.1 线性规划的数学模型线性规划的数学模型 Mathematical Model of LPChapter 1 线性规划线性规划 Linear Programming【例例1.3】合理用料问题合理用料问题。某汽车需要用甲、乙、丙三。某汽车需要用甲、乙、丙三种规格的轴各一根，这些轴的规格分别是种规格的轴各一根，这些轴的规格分别是1.5，1，0.7(m)，这些轴需要用同一种圆钢来做，圆钢长度为，这些轴需要用同一种圆钢来做，圆钢长度为4 m。现在要制造。现在要制造1000辆汽车，最少要用多少圆钢来生辆汽车，最少要用多少圆钢来生产这些轴？产

10、这些轴？ 【解解】这是一个条材下料问题这是一个条材下料问题 ，设切口宽度为零。，设切口宽度为零。 设设一根圆钢切割成一根圆钢切割成甲、乙、丙三种轴的根数分别为甲、乙、丙三种轴的根数分别为y1，y2，y3,则切割方式可用不等式则切割方式可用不等式1.5y1+y2+0.7y34表示，求这表示，求这个不等式关于个不等式关于y1，y2，y3的非负整数解。象这样的非负的非负整数解。象这样的非负整数解共有整数解共有10组，也就是有组，也就是有10种下料方式，如表种下料方式，如表1.3所所示。示。1.1 线性规划的数学模型线性规划的数学模型 Mathematical Model of LPChapter 1

11、 线性规划线性规划 Linear Programming表表1. 3 下料方案下料方案 方案方案 规格规格 1234 5678910需求量需求量y1(根根) 221 11 0 00001000y2 102 10 4 32101000y3 010 23 0 12451000余料余料(m)00.30.5 0.1o.4 00.30.60.20.51.5y1+y2+0.7y3 4设设xj ( j = 1,2,10)为第为第 j 种下料方案所用圆钢的根数，种下料方案所用圆钢的根数，则用料最少数学模型则用料最少数学模型1.1 线性规划的数学模型线性规划的数学模型 Mathematical Model of

12、 LPChapter 1 线性规划线性规划 Linear Programming10, 2 , 1, 010005423210002342100022min10987542987643154321101jxxxxxxxxxxxxxxxxxxxxxZjjj 方案方案 规格规格 1234 5678910需求量需求量y1(根根) 221 11 0 00001000y2 102 10 4 32101000y3 010 23 0 12451000余料（余料（m）00.30.5 0.1o.4 00.30.60.20.51.1 线性规划的数学模型线性规划的数学模型 Mathematical Model of

13、 LPChapter 1 线性规划线性规划 Linear Programming注注 意意 求下料方案时，余料不能超过最短毛坯的长度；求下料方案时，余料不能超过最短毛坯的长度；最好将毛坯长度按降的次序排列，即先切割长度最最好将毛坯长度按降的次序排列，即先切割长度最长的毛坯，再切割次长的，最后切割最短的，不能长的毛坯，再切割次长的，最后切割最短的，不能遗漏了方案遗漏了方案 。如果方案较多，用计算机编程排方案，。如果方案较多，用计算机编程排方案，去掉余料较长的方案，进行初选。去掉余料较长的方案，进行初选。 1.1 线性规划的数学模型线性规划的数学模型 Mathematical Model of L

14、PChapter 1 线性规划线性规划 Linear Programming1.1.2 线性规划的一般模型线性规划的一般模型 一般地一般地，假设线性规划数学模型中，假设线性规划数学模型中, ,有有m个约束个约束, ,有有n个决策变量个决策变量xj(j=1,2,n)，目标函数的变量系数用目标函数的变量系数用cj表示表示, , cj称为称为价值系数价值系数。约束条件的变量系数用约束条件的变量系数用aij表示表示，aij称为称为工艺系数工艺系数。约束条件右约束条件右端的常数用端的常数用bi 表示表示，bi 称为称为资源限量资源限量。则线性规划数学模型的则线性规划数学模型的一般表达式可写成一般表达式可

15、写成1 1221111221121 1222221 122max(min)(, )(, )(, )0,1,2,nnnnnnmmmnnmjZc xc xc xa xa xa xba xa xa xba xaxa xbxjn 或或或LLLLLLLLLLLLLLLLLLLL1.1 线性规划的数学模型线性规划的数学模型 Mathematical Model of LPChapter 1 线性规划线性规划 Linear Programming11max(min)(, )1,2,0,1,2,njjjnijjijjZc xa xbimxjn 或LL在实际中一般在实际中一般xj0, 但有时但有时 xj0或或

16、xj 无符号限制。无符号限制。为了书写方便，上式也可写成：为了书写方便，上式也可写成： 1.1 线性规划的数学模型线性规划的数学模型 Mathematical Model of LP1.2 图解法图解法 Graphical MethodChapter 1 线性规划线性规划 Linear Programming图解法的步骤：图解法的步骤：1. 在直角坐标系中画出可行解集：在直角坐标系中画出可行解集：分别画出满足每个约束包括分别画出满足每个约束包括变量非负要求的区域，其交集就是可行解集，或称变量非负要求的区域，其交集就是可行解集，或称可行域；可行域；2. 绘制目标函数图形：绘制目标函数图形：先过原

17、点作一条矢量指向点先过原点作一条矢量指向点(c c1, ,c c2 )，矢，矢量的方向就是目标函数值增加的方向，称为梯度方向，再作一量的方向就是目标函数值增加的方向，称为梯度方向，再作一条与矢量垂直的直线，这条直线就是目标函数图形；条与矢量垂直的直线，这条直线就是目标函数图形；3. 求最优解：求最优解：依据目标函数求最大或最小移动目标函数直线，依据目标函数求最大或最小移动目标函数直线， 直线与可行域相交的点对应的坐标就是直线与可行域相交的点对应的坐标就是最优解。最优解。 一般地，先将目标函数直线放在可行域中：一般地，先将目标函数直线放在可行域中： 若要求最大值，则将目标函数直线沿着矢量方向移动

18、；若要求最大值，则将目标函数直线沿着矢量方向移动； 若要求最小值，则将目标函数直线沿着矢量的反方向移动。若要求最小值，则将目标函数直线沿着矢量的反方向移动。1.2 图解法图解法 The Graphical MethodChapter 1 线性规划线性规划 Linear Programmingx1 x2 O1020304010203040(3,4)(15,10)最优解最优解X=(15,10)最优值最优值Z=8540221xx305 . 121xx0, 0305 . 1402212121xxxxxx例例1.42143maxxxZ1.2 图解法图解法 The Graphical MethodChap

19、ter 1 线性规划线性规划 Linear Programming246x1 x2 246最优解最优解X=(3,1) 最优值最优值Z=5(3,1)006346321212121xxxxxxxx、min Z=x1+2x2例例1. 5 (1,2)1.2 图解法图解法 The Graphical MethodChapter 1 线性规划线性规划 Linear Programming246x1 x2 246X（2）（3,1） X（1）（1,3） (5,5)006346321212121xxxxxxxx、min Z=5x1+5x2例例1.6有无穷多个最优解有无穷多个最优解 即具有多重解即具有多重解,通解

20、为通解为 01 ,)1 ()2() 1 (XXX 当当=0.5时时 =(x1,x2)=0.5(1,3)+0.5(3,1)=(2,2) 1.2 图解法图解法 The Graphical MethodChapter 1 线性规划线性规划 Linear Programming246x1 x2 246(1,2)006346321212121xxxxxxxx、无界解无界解(无最优解无最优解)max Z=x1+2x2例例1.71.2 图解法图解法 The Graphical MethodChapter 1 线性规划线性规划 Linear Programmingx1 x2 O1020304010203040

21、50500,050305 .140221212121xxxxxxxx无可行解，从无可行解，从 而无最优解。而无最优解。max Z=10 x1+x2例例1.81.2 图解法图解法 The Graphical MethodChapter 1 线性规划线性规划 Linear Programming由以上例题可知，线性规划的解有由以上例题可知，线性规划的解有4种形式种形式： 1.有惟一最优解有惟一最优解(例例1.4、例、例1.5)2.有多重解有多重解(例例1.6)3.有无界解有无界解(例例1.7)4.无可行解无可行解(例例1.8)1、2情形为有最优解情形为有最优解 3、4情形为无最优解情形为无最优解1

22、.2 图解法图解法 The Graphical MethodChapter 1 线性规划线性规划 Linear Programming1.3 线性规划的标准型线性规划的标准型 Standard form of LPChapter 1 线性规划线性规划 Linear Programming 在用单纯法求解线性规划问题时，为了讨论问在用单纯法求解线性规划问题时，为了讨论问题方便，需将线性规划模型化为统一的标准形式。题方便，需将线性规划模型化为统一的标准形式。 1.3 线性规划的标准型线性规划的标准型 Standard form of LP线性规划问题的标准型为线性规划问题的标准型为: 1目标函数求

23、最大值（或求最小值）目标函数求最大值（或求最小值） 2约束条件都为等式方程约束条件都为等式方程 3变量变量xj非负非负 4常数常数bi非负非负 Chapter 1 线性规划线性规划 Linear Programmingmibnjxbxaxaxabxaxaxabxaxaxaijmnmnmmnnnn,2, 1,0,2, 1,022112222212111212111max(或min)Z=c1x1+c2x2+cnxn 1.3 线性规划的标准型线性规划的标准型 Standard form of LP注：本教材默认标准型中目标函数是注：本教材默认标准型中目标函数是 maxChapter 1 线性规划线性

24、规划 Linear ProgrammingnjjjxcZ1maxnjxmibxajnjijij, 2 , 1, 0, 2 , 1,10maxXbAXCXZ或写成下列形式或写成下列形式： 或用矩阵形式或用矩阵形式1.3 线性规划的标准型线性规划的标准型 Standard form of LPChapter 1 线性规划线性规划 Linear Programming111211121222221212, , )nnnmmmnnmaaaxbaaaxbAXbCc ccaaaxb ； (通常通常X记为：记为： , 称称为约束方程为约束方程的系数矩阵，的系数矩阵，m是约束方程的个数，是约束方程的个数，n是

25、决策变量的个数，一般是决策变量的个数，一般情况情况mn，且，且r()m。TnxxxX),(21max0ZCXAXbX其中其中:1.3 线性规划的标准型线性规划的标准型 Standard form of LPChapter 1 线性规划线性规划 Linear Programming一般形式线性规划模型的标准化准则一般形式线性规划模型的标准化准则: （前提（前提 b bi 0 ）cxZ min.1injjijbxa1. 2injjijbxa1. 3cxZmax01iniinnjjijxbxxa01iniinnjjijxbxxa无符号要求ix.40, 0, iiiiixxxxx5. xj0令令xj

26、= xj , xj 0 Chapter 1 线性规划线性规划 Linear Programming【例例1】将下列线性规划化为标准型将下列线性规划化为标准型 3213minxxxZ无符号要求、32132132132100) 3(523)2(3) 1 (82xxxxxxxxxxxx【分析分析】()因为因为x3无符号要求无符号要求 ，即，即x3 可取正值也可取正值也可取负值，标准型中要求变量非负，所以令可取负值，标准型中要求变量非负，所以令 0,33333 xxxxx其中1.3 线性规划的标准型线性规划的标准型 Standard form of LPChapter 1 线性规划线性规划 Linea

27、r Programming (3)第二个约束条件是第二个约束条件是“”号，在号，在“”号左端减去剩余号左端减去剩余 变量变量(surplus variable) x5 ，x50，也称松驰变量；，也称松驰变量；1.3 线性规划的标准型线性规划的标准型 Standard form of LP(2) 第一个约束条件是第一个约束条件是“”号，号， 在在“”号左端加入松驰变量号左端加入松驰变量 (slack variable) x4，x40, 化为等式；化为等式；(4)第三个约束条件是第三个约束条件是“”号且常数项为负数，因此在号且常数项为负数，因此在“”左边加入松驰变量左边加入松驰变量x6，x60，同

28、时两边乘以，同时两边乘以1。 (5)目标函数是最小值，为了化为求最大值，令目标函数是最小值，为了化为求最大值，令Z=Z, 得到得到 max Z=Z，即当，即当Z达到最小值时达到最小值时Z达到最大值。达到最大值。 3213minxxxZ无符号要求、32132132132100)3(523)2(3)1 (82xxxxxxxxxxxxChapter 1 线性规划线性规划 Linear Programming综合起来得到下列标准型综合起来得到下列标准型 332133maxxxxxZ 05)(233826543321633215332143321xxxxxxxxxxxxxxxxxxxxxx、1.3 线性

29、规划的标准型线性规划的标准型 Standard form of LPChapter 1 线性规划线性规划 Linear Programming当某个约束是绝对值不等式时，将绝对值不等式化为两个不等当某个约束是绝对值不等式时，将绝对值不等式化为两个不等式，再化为等式，例如约束式，再化为等式，例如约束 974321xxx将其化为两个不等式将其化为两个不等式 974974321321xxxxxx再加入松驰变量化为等式。再加入松驰变量化为等式。 1.3 线性规划的标准型线性规划的标准型 Standard form of LP1.4 线性规划的有关概念线性规划的有关概念 Basic Concepts o

30、f LPChapter 1 线性规划线性规划 Linear Programming 设线性规划的标准型设线性规划的标准型 max Z=CX (1.1) AX=b (1.2) X 0 (1.3) 式中式中A 是是mn矩阵，矩阵，mn并且并且r(A)=m，显然，显然A中至少中至少有一个有一个mm子矩阵子矩阵B，使得，使得r(B)=m。1.4 基本概念基本概念 Basic Concepts 基基 (basis)：A中中 mm子矩阵子矩阵 B 并且有并且有r(B)=m，则称，则称B是线性规划的一个是线性规划的一个基基(或或基矩阵基矩阵basis matrix )。mnC注：注：基矩阵基矩阵B必为非奇异

31、矩阵必为非奇异矩阵(可逆可逆矩阵矩阵)即即|B|0。当当m=n时，基矩阵惟一，当时，基矩阵惟一，当mn时，基矩阵就可能有多个，但数时，基矩阵就可能有多个，但数目不超过目不超过Chapter 1 线性规划线性规划 Linear Programming【例例2】线性规划线性规划 32124maxxxxZ5 , 1, 0226103553214321jxxxxxxxxxj 求所有基矩阵求所有基矩阵。 【解解】约束方程的系数矩阵为约束方程的系数矩阵为25矩阵矩阵 10261001115A1.4 基本概念基本概念 Basic Concepts Chapter 1 线性规划线性规划 Linear Prog

32、ramming10261001115A,610151B,010152B,110053B26114B10019B,12017B,02118B,16016B,06115B容易看出容易看出r(A)=2，2阶子矩阵有阶子矩阵有C52=10个，其中第个，其中第1列与列与第第3列构成的列构成的2阶矩阵不是一个基，基矩阵只有阶矩阵不是一个基，基矩阵只有9个，即个，即 Chapter 1 线性规划线性规划 Linear Programming当确定某一矩阵为基矩阵时，则基矩阵对应的列向量当确定某一矩阵为基矩阵时，则基矩阵对应的列向量称为称为基向量基向量(basic vector)，其余列向量称为，其余列向量称

33、为非基向量非基向量; 基向量对应的变量称为基向量对应的变量称为基变量基变量(basic variable)， 非基向量对应的变量称为非基向量对应的变量称为非基变量非基变量 ；在上例中在上例中B2的基向量是的基向量是A中的第一列和第四列，其余列中的第一列和第四列，其余列向量是非基向量，向量是非基向量，x1、x4是基变量，是基变量，x2、x3、x5是非基是非基变量。变量。基变量、非基变量是针对某一确定基而言的基变量、非基变量是针对某一确定基而言的，不同的基对应的基变量和非基变量也不同。不同的基对应的基变量和非基变量也不同。 010152B10261001115A1.4 基本概念基本概念 Basic

34、 Concepts Chapter 1 线性规划线性规划 Linear Programming 可行解可行解(feasible solution): 满足式满足式(1.2)及及(1.3)的解的解X=（x1, x2 , xn)T 称为可行解；称为可行解； 基本可行解基本可行解(basic feasible solution): 若基本解是可行解若基本解是可行解 则称为是基本可行解（也称基可行解）。则称为是基本可行解（也称基可行解）。 基本解基本解(basic solution) : 对某一确定的基对某一确定的基B，令，令非基变量非基变量 等于零等于零，利用式，利用式(1.2)解出基变量，则这组解

35、称为基解出基变量，则这组解称为基 的的 基本解。基本解。 最优解最优解(optimal solution): 满足式满足式(1.1)的可行解称为最优的可行解称为最优 解，即使得目标函数达到解，即使得目标函数达到最大值最大值的的可行解可行解就是最优解；就是最优解；非可行解非可行解(infeasible solution) 无界解无界解 (unbounded solution)1.4 基本概念基本概念 Basic Concepts Chapter 1 线性规划线性规划 Linear Programming显然，只要基本解中的基变量的解满足式显然，只要基本解中的基变量的解满足式(1.3)的非负的非负

36、要求，那么这个基本解就是基本可行解。要求，那么这个基本解就是基本可行解。 在上例中，对在上例中，对来说，来说，x1, x2是基变量，是基变量，x3 , x4 ，x5是是非基变量，令非基变量，令x3=x4=x5=0，则式，则式(1.2)为为2610352121xxxx,610151B 因因|B1|，由克莱姆法则知，由克莱姆法则知，x1、x2有惟一解有惟一解x12/5, x2=1, 从而从而基本解为基本解为TX)0 , 0 , 0 , 1 ,52()1(1.4 基本概念基本概念 Basic Concepts Chapter 1 线性规划线性规划 Linear Programming对对B2来说，来

37、说，x1, x4,为基变量，令非变量为基变量，令非变量x2, x3, x5为零，由为零，由式式(1.2)得得 ，x4=4，则基本解为，则基本解为511xTX)0 , 4 , 0 , 0 ,51()2(,010152B反之，反之，可行解不一定是基本可行解可行解不一定是基本可行解，如，如 满足式满足式(1.2)(1.3)，但不是任何基矩阵的基本解。，但不是任何基矩阵的基本解。TX) 1 ,27,21, 0 , 0(在在 中中x10 i 表表1. 5 (1) XB x1 x2 x3 x4 b x3 2 1 1 0 40 x4 1 3 0 1 30 j 3 4 0 0 (2) x3 x2 j (3)

38、x1 x2 j 基变量基变量 110001/301/3105/31- -1/3405/30- -4/330103/5- -1/51801- -1/5 2/5400- -1- -1将将3化为化为1乘乘以以1/3后后得得到到1.5 单纯形法单纯形法 Simplex Method3018Chapter 1 线性规划线性规划 Linear Programming单纯形法的单纯形法的计算步骤计算步骤：1. 找一个找一个初始可行基初始可行基，写出对应的典式，列出初始单，写出对应的典式，列出初始单纯形表纯形表,其中基变量的检验数必为零；其中基变量的检验数必为零； 2. 判断：判断： (a)若若j( j，n)

39、，则得到最优解则得到最优解； (b)若存在某个若存在某个k0且且aik(i=1，2,m)，则线性则线性 规划具有无界解规划具有无界解； (c)若存在若存在k0且且aik (i=1,m)不全非正，则进行换基不全非正，则进行换基；1.5 单纯形法单纯形法 Simplex Method3. 换基：换基： (a)选选进基变量进基变量：设：设k=max j | j 0, 选第选第k列所对应列所对应的变量的变量xk为进基变量为进基变量。Chapter 1 线性规划线性规划 Linear Programming第第个比值最小，选最小比值对应行的基变量为出基个比值最小，选最小比值对应行的基变量为出基变量，若有

40、相同最小比值，则任选一个变量，若有相同最小比值，则任选一个aLk为主元素为主元素。 (c)求新的基可行解求新的基可行解：用初等行变换方法将：用初等行变换方法将aLk化为化为, 第第 k 列其它元素化为零（包括检验数行）得到新的可列其它元素化为零（包括检验数行）得到新的可行基及基本可行解，再判断是否得到最优解。行基及基本可行解，再判断是否得到最优解。(b)选选出基变量出基变量 ：求最小比值：求最小比值1.5 单纯形法单纯形法 Simplex Method0|minikikiLaabChapter 1 线性规划线性规划 Linear Programming【例例4】 用单纯形法求解用单纯形法求解3

41、212maxxxxZ02053115232321321321xxxxxxxxx、 【解解】将数学模型化为标准型：将数学模型化为标准型：3212maxxxxZ5 , 2 , 1, 0205311523253214321jxxxxxxxxxj1.5 单纯形法单纯形法 Simplex MethodChapter 1 线性规划线性规划 Linear ProgrammingCj 1 2 1 0 0 b CB XB x1 x2 x3 x4 x5 0 x4 2 3 2 1 0 15 0 x5 1/3 1 5 0 1 20 j 1 2 1 0 0 0 x4 2 x2 j 1 x1 2 x2 j 表表1. 61

42、/3150120301713751/30902 2025601017/31/31250128/91/92/335/30098/91/97/3最优解最优解X=(25，35/3，0，0，0)T，最优值，最优值 Z =145/31.5 单纯形法单纯形法 Simplex MethodChapter 1 线性规划线性规划 Linear Programming1.3 线性规划的标准型线性规划的标准型 Standard form of LP下一节：基本概念下一节：基本概念1.线性规划问题化标准形式；线性规划问题化标准形式；4.单纯形法思想。单纯形法思想。2. 线性规划常用的概念：可行解、基本解、基本线性规划

43、常用的概念：可行解、基本解、基本 可行可行解、最优解、基本最优解、基、可行基、最优基、凸集、解、最优解、基本最优解、基、可行基、最优基、凸集、极点极点(凸点凸点)、凸组合；、凸组合；3. 线性规划的三个基本定理。线性规划的三个基本定理。Chapter 1 线性规划线性规划 Linear Programming【例例3】求解线性规划求解线性规划2142maxxxZ0,21024221212121xxxxxxxx用单纯形法计算如下表所示：用单纯形法计算如下表所示：1.5 单纯形法单纯形法 Simplex Method【解解】化为标准型为：化为标准型为：2142maxxxZ021024254321521421321xxxxxxxxxxxxxx,Chapter 1 线性规划线性规划 Linea