运筹学ppt课件Ch1线性规划

1、运筹学运筹学operations researchchapter 1 线性规划线性规划linear programming1.1 lp的数学模型的数学模型 mathematical model of lp1.2 图解法图解法 graphical method1.3 标准型标准型 standard form of lp1.4 基本概念基本概念 basic concepts1.5 单纯形法单纯形法 simplex method1.1 数学模型数学模型 mathematical model 制作与教学 武汉理工大学管理学院 熊伟 chapter 1 线性规划线性规划linear programmin

2、g page 3 2021年11月14日星期日1.1 线性规划的数学模型线性规划的数学模型 mathematical model of lp线性规划线性规划（linear programming,缩写为lp）通常研究资源通常研究资源的最优利用、设备最佳运行等问题。例如，当任务或目标的最优利用、设备最佳运行等问题。例如，当任务或目标确定后，如何统筹兼顾，合理安排，用最少的资源确定后，如何统筹兼顾，合理安排，用最少的资源 （如资（如资金、设备、原标材料、人工、时间等）去完成确定的任务金、设备、原标材料、人工、时间等）去完成确定的任务或目标；企业在一定的资源条件限制下，如何组织安排生或目标；企业在一

3、定的资源条件限制下，如何组织安排生产获得最好的经济效益（如产品量最多产获得最好的经济效益（如产品量最多 、利润最大）。、利润最大）。 制作与教学 武汉理工大学管理学院 熊伟 chapter 1 线性规划线性规划linear programming page 4 2021年11月14日星期日【例【例1-1】生产计划问题。某企业在计划期内计划生产甲、乙两】生产计划问题。某企业在计划期内计划生产甲、乙两种产品。按工艺资料规定，每件产品甲需要消耗材料种产品。按工艺资料规定，每件产品甲需要消耗材料a 2公斤，公斤，消耗材料消耗材料b 1公斤，每件产品乙需要消耗材料公斤，每件产品乙需要消耗材料a 1公斤，

4、消耗材公斤，消耗材料料b 1.5公斤。已知在计划期内可供材料分别为公斤。已知在计划期内可供材料分别为40、30公斤；每公斤；每生产一件甲、乙两产品，企业可获得利润分别为生产一件甲、乙两产品，企业可获得利润分别为300、400元，元，如表如表11所示。假定市场需求无限制。企业决策者应如何安排所示。假定市场需求无限制。企业决策者应如何安排生产计划，使企业在计划期内总的利润收入最大。生产计划，使企业在计划期内总的利润收入最大。1.1 线性规划的数学模型线性规划的数学模型 mathematical model of lp1.1.1 应用模型举例应用模型举例 制作与教学 武汉理工大学管理学院 熊伟 ch

5、apter 1 线性规划线性规划linear programming page 5 2021年11月14日星期日12max300400zxx【解】设【解】设x1、x2分别为甲、乙产品的产量，数学模型为：分别为甲、乙产品的产量，数学模型为：1.1 线性规划的数学模型线性规划的数学模型 mathematical model of lp 产品产品 资源资源 甲甲 乙乙现有资现有资源源材料材料a2140材料材料b11.530利润（元利润（元/件）件） 3004001212122401.5300,0 xxxxxx表表1-1 制作与教学 武汉理工大学管理学院 熊伟 chapter 1 线性规划线性规划li

6、near programming page 6 2021年11月14日星期日线性规划的数学模型由线性规划的数学模型由决策变量决策变量 decision variables 目标函数目标函数objective function及约束条件及约束条件constraints构成。称为三个要素构成。称为三个要素。n其特征是：其特征是：n1解决问题的目标函数是多个决策变量的解决问题的目标函数是多个决策变量的 线性函数，通常是求最大值或线性函数，通常是求最大值或 最小值；最小值；n2解决问题的解决问题的是一组多个决策变量是一组多个决策变量 的线性不等式或等式。的线性不等式或等式。怎样辨别一个模型是线性规划模

7、型？怎样辨别一个模型是线性规划模型？1.1 线性规划的数学模型线性规划的数学模型 mathematical model of lp 制作与教学 武汉理工大学管理学院 熊伟 chapter 1 线性规划线性规划linear programming page 7 2021年11月14日星期日【例【例1-2】某商场决定：营业员每周连续工作】某商场决定：营业员每周连续工作5天后连续休息天后连续休息2天，天，轮流休息。根据统计，商场每天需要的营业员如表轮流休息。根据统计，商场每天需要的营业员如表1-2所示。所示。表表1-2 营业员需要量统计表营业员需要量统计表商场人力资源部应如何安排每天的上班人数，使商

8、场总的营业员商场人力资源部应如何安排每天的上班人数，使商场总的营业员最少。最少。 星期星期需要人数需要人数星期星期需要人数需要人数一一300五五480二二300六六600三三350日日550四四4001.1 线性规划的数学模型线性规划的数学模型 mathematical model of lp 制作与教学 武汉理工大学管理学院 熊伟 chapter 1 线性规划线性规划linear programming page 8 2021年11月14日星期日【解】【解】 设设xj (j=1，2，7)为休息为休息2天后星期一到星期日开始上天后星期一到星期日开始上班的营业员，则这个问题的线性规划模型为班的营

9、业员，则这个问题的线性规划模型为 145671256712367123471234523456345673003003504004806005500,1,2,7jxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxj1.1 线性规划的数学模型线性规划的数学模型 mathematical model of lp星星期期需要需要人数人数星星期期需要需要人数人数一一300五五480二二300六六600三三350日日550四四4001234567minzxxxxxxx 制作与教学 武汉理工大学管理学院 熊伟 chapter 1 线性规划线性规划linear programming

10、page 9 2021年11月14日星期日【例【例1-3】合理用料问题。某汽车需要用甲、乙、丙三种规格的轴各一根，这】合理用料问题。某汽车需要用甲、乙、丙三种规格的轴各一根，这些轴的规格分别是些轴的规格分别是1.5，1，0.7（m），这些轴需要用同一种圆钢来做，圆钢长），这些轴需要用同一种圆钢来做，圆钢长度为度为4 m。现在要制造。现在要制造1000辆汽车，最少要用多少圆钢来生产这些轴？辆汽车，最少要用多少圆钢来生产这些轴？ 【解】这是一个条材下料问题【解】这是一个条材下料问题 ，设切口宽度为零。，设切口宽度为零。 设一根圆钢切割成甲、设一根圆钢切割成甲、乙、丙三种轴的根数分别为乙、丙三种轴的

11、根数分别为y1，y2，y3,则切割方式可用不等式则切割方式可用不等式1.5y1+y2+0.7y34表示，求这个不等式关于表示，求这个不等式关于y1，y2，y3的非负整数解。象这样的非负整数解。象这样的非负整数解共有的非负整数解共有10组，也就是有组，也就是有10种下料方式，如表种下料方式，如表1-3所示。所示。表表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.

12、1 线性规划的数学模型线性规划的数学模型 mathematical model of lp 制作与教学 武汉理工大学管理学院 熊伟 chapter 1 线性规划线性规划linear programming page 10 2021年11月14日星期日设设xj(j=1,2,10)为第为第j种下料方案所用圆钢的根数。则用料最少种下料方案所用圆钢的根数。则用料最少数学模型数学模型求下料方案时应注意，余料不能超过最短毛坯的长度；最好将毛求下料方案时应注意，余料不能超过最短毛坯的长度；最好将毛坯长度按降的次序排列，即先切割长度最长的毛坯，再切割次长坯长度按降的次序排列，即先切割长度最长的毛坯，再切割次长

13、的，最后切割最短的，不能遗漏了方案的，最后切割最短的，不能遗漏了方案 。如果方案较多，用计。如果方案较多，用计算机编程排方案，去掉余料较长的方案，进行初选。算机编程排方案，去掉余料较长的方案，进行初选。102 , 1, 010005423210002342100022min10987542987643154321101，jxxxxxxxxxxxxxxxxxxxxxzjjj1.1 线性规划的数学模型线性规划的数学模型 mathematical model of lp 方案方案规格规格 1234 5678910需求量需求量y1(根根) 221 11 0 00001000y2 102 10 4 32

14、101000y3 010 23 0 12451000余料（余料（m）00.30.5 0.1o.4 00.30.60.20.5 制作与教学 武汉理工大学管理学院 熊伟 chapter 1 线性规划线性规划linear programming page 11 2021年11月14日星期日1.1.2 线性规划的一般模型线性规划的一般模型一般地，假设线性规划数学模型中，有一般地，假设线性规划数学模型中，有m个约束，有个约束，有n个决策变量个决策变量xj, j=1,2,n，目标函数的变量系数用，目标函数的变量系数用cj表示表示, cj称为称为价值系数价值系数。约。约束条件的变量系数用束条件的变量系数用a

15、ij表示，表示，aij称为称为工艺系数工艺系数。约束条件右端的。约束条件右端的常数用常数用bi表示，表示，bi称为称为资源限量资源限量。则线性规划数学模型的一般表达。则线性规划数学模型的一般表达式可写成式可写成1 1221111221121 1222221 122max(min)(, )(, )(, )0,1,2,nnnnnnmmmnnmjzc xc xc xa xa xa xba xa xa xba xaxaxbxjn 或或或为了书写方便，上式也可写成：为了书写方便，上式也可写成： 1.1 线性规划的数学模型线性规划的数学模型 mathematical model of lp 制作与教学 武

16、汉理工大学管理学院 熊伟 chapter 1 线性规划线性规划linear programming page 12 2021年11月14日星期日11max(min)(, )1,2,0,1,2,njjjnijjijjzc xa xbimxjn 或在实际中一般在实际中一般xj0,但有时但有时xj0或或xj无符号限制。无符号限制。1.1 线性规划的数学模型线性规划的数学模型 mathematical model of lp 制作与教学 武汉理工大学管理学院 熊伟 chapter 1 线性规划线性规划linear programming page 13 2021年11月14日星期日1.什么是线性规划，

17、掌握线性规划在管理中的什么是线性规划，掌握线性规划在管理中的几个应用例子几个应用例子2.线性规划数学模型的组成及其特征线性规划数学模型的组成及其特征3.线性规划数学模型的一般表达式。线性规划数学模型的一般表达式。作业：教材习题作业：教材习题 1.11.61.1 线性规划的数学模型线性规划的数学模型 mathematical model of lp下一节：图解法下一节：图解法1.2 图解法图解法 graphical method 制作与教学 武汉理工大学管理学院 熊伟 chapter 1 线性规划线性规划linear programming page 15 2021年11月14日星期日x1x2o

18、1020304010203040(300,400)(15,10)最优解最优解x=(15,10)最优值最优值z=850040221xx305 . 121xx0, 0305 . 1402212121xxxxxx例例1-712max300400zxx1.2 图解法图解法the graphical method 制作与教学 武汉理工大学管理学院 熊伟 chapter 1 线性规划线性规划linear programming page 16 2021年11月14日星期日246x1x2246最优解最优解x=(3,1)最优值最优值z=5(3,1)006346321212121xxxxxxxx、min z=x

19、1+2x2例例1-8(1,2)1.2 图解法图解法the graphical method 制作与教学 武汉理工大学管理学院 熊伟 chapter 1 线性规划线性规划linear programming page 17 2021年11月14日星期日246x1x2246x（2）（3,1）x（1）（1,3）(5,5)006346321212121xxxxxxxx、min z=5x1+5x2例例1-9有无穷多个最优解有无穷多个最优解即具有多重解即具有多重解,通解为通解为 01 ,)1 ()2() 1 (xxx 当当=0.5时时=(x1,x2)=0.5(1,3)+0.5(3,1)=(2,2) 1.2

20、 图解法图解法the graphical method 制作与教学 武汉理工大学管理学院 熊伟 chapter 1 线性规划线性规划linear programming page 18 2021年11月14日星期日246x1x2246(1,2)006346321212121xxxxxxxx、无界解无界解(无最优解无最优解)max z=x1+2x2例例1-101.2 图解法图解法the graphical method 制作与教学 武汉理工大学管理学院 熊伟 chapter 1 线性规划线性规划linear programming page 19 2021年11月14日星期日x1x2o10203

21、0401020304050500,050305 .140221212121xxxxxxxx无可行解无可行解即无最优解即无最优解max z=10 x1+4x2例例1-111.2 图解法图解法the graphical method 制作与教学 武汉理工大学管理学院 熊伟 chapter 1 线性规划线性规划linear programming page 20 2021年11月14日星期日由以上例题可知，线性规划的解有由以上例题可知，线性规划的解有4种形式种形式：1.有唯一最优解有唯一最优解(例例1-7例例1-8)2.有多重解有多重解(例例1-9)3.有无界解有无界解(例例1-10)4.无可行解无

22、可行解(例例1-11)1、2情形为有最优解情形为有最优解3、4情形为无最优解情形为无最优解1.2 图解法图解法the graphical method 制作与教学 武汉理工大学管理学院 熊伟 chapter 1 线性规划线性规划linear programming page 21 2021年11月14日星期日图解法的步骤：图解法的步骤：1.求可行解集合。求可行解集合。分别求出满足每个约束包括变量非分别求出满足每个约束包括变量非 负要求负要求的区域，其交集就是可行解集合，或称为的区域，其交集就是可行解集合，或称为可行域可行域；2.绘制目标函数图形。绘制目标函数图形。先过原点作一条矢量指向点（先过

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

24、时沿着矢量的反方向移动1.2 图解法图解法the graphical method 制作与教学 武汉理工大学管理学院 熊伟 chapter 1 线性规划线性规划linear programming page 22 2021年11月14日星期日1.通过图解法了解线性规划有几种解的形式通过图解法了解线性规划有几种解的形式2.作图的关键有三点作图的关键有三点 (1)可行解区域要画正确可行解区域要画正确 (2)目标函数增加的方向不能画错目标函数增加的方向不能画错 (3)目标函数的直线怎样平行移动目标函数的直线怎样平行移动作业：教材习题作业：教材习题 1.7 1.2 图解法图解法the graphica

25、l method下一节：线性规划的标准型下一节：线性规划的标准型1.3 线性规划的标准型线性规划的标准型standard form of lp 制作与教学 武汉理工大学管理学院 熊伟 chapter 1 线性规划线性规划linear programming page 24 2021年11月14日星期日 在用单纯法求解线性规划问题时，为了讨论问题在用单纯法求解线性规划问题时，为了讨论问题方便，需将线性规划模型化为统一的标准形式。方便，需将线性规划模型化为统一的标准形式。1.3 线性规划的标准型线性规划的标准型standard form of lp线性规划问题的标准型为线性规划问题的标准型为:1目

26、标函数求最大值（或求最小值）目标函数求最大值（或求最小值）2约束条件都为等式方程约束条件都为等式方程3变量变量xj非负非负4常数常数bi非负非负 制作与教学 武汉理工大学管理学院 熊伟 chapter 1 线性规划线性规划linear programming page 25 2021年11月14日星期日mibnjxbxaxaxabxaxaxabxaxaxaijmnmnmmnnnn,2, 1,0,2, 1,02211222222111212111max(或min)z=c1x1+c2x2+cnxn1.3 线性规划的标准型线性规划的标准型standard form of lp注：本教材默认目标函数是

27、注：本教材默认目标函数是 max 制作与教学 武汉理工大学管理学院 熊伟 chapter 1 线性规划线性规划linear programming page 26 2021年11月14日星期日njjjxcz1maxminjxbxajnjijij, 2 , 1, 2 , 1, 010maxxbaxcxz或写成下列形式或写成下列形式： 或用矩阵形式或用矩阵形式1.3 线性规划的标准型线性规划的标准型standard form of lp 制作与教学 武汉理工大学管理学院 熊伟 chapter 1 线性规划线性规划linear programming page 27 2021年11月14日星期日11

28、1211121222221212, , , )nnnmmm nnmaaaxbaaaxbaxbcc ccaaaxb ； (通常通常x记为：记为： 称为约束方称为约束方程的系数矩阵，程的系数矩阵，m是约束方程的个数，是约束方程的个数，n是决策变量的个数，是决策变量的个数，一般情况一般情况mn，且，且r()m。tnxxxx),21（m ax0zc xa xbx其中其中:1.3 线性规划的标准型线性规划的标准型standard form of lp 制作与教学 武汉理工大学管理学院 熊伟 chapter 1 线性规划线性规划linear programming page 28 2021年11月14日星

29、期日【例【例1-12】将下列线性规划化为标准型】将下列线性规划化为标准型 3213minxxxz无符号要求、32132132132100)3(523)2(3) 1 (82xxxxxxxxxxxx【解】（）因为【解】（）因为x3无符号要求无符号要求 ，即，即x3取正值也取正值也可取负值，标准型中要求变量非负，所以令可取负值，标准型中要求变量非负，所以令 0,33333 xxxxx其中1.3 线性规划的标准型线性规划的标准型standard form of lp 制作与教学 武汉理工大学管理学院 熊伟 chapter 1 线性规划线性规划linear programming page 29 202

30、1年11月14日星期日 (3)第二个约束条件是第二个约束条件是号，在号，在号号 左左端减去剩余变量端减去剩余变量(surplus variable)x5，x50。也称松驰变。也称松驰变量量3213minxxxz无符号要求、32132132132100) 3(523)2(3) 1 (82xxxxxxxxxxxx1.3 线性规划的标准型线性规划的标准型standard form of lp(2) 第一个约束条件是第一个约束条件是号，在号，在左端左端加入松驰变量加入松驰变量 (slack variable) x4，x40,化为等式；化为等式；(4)第三个约束条件是第三个约束条件是号且常数项为负数，因

31、此在号且常数项为负数，因此在左边加入松左边加入松驰变量驰变量x6，x60，同时两边乘以，同时两边乘以1。 （5）目标函数是最小值，为了化为求最大值，令）目标函数是最小值，为了化为求最大值，令z=z,得到得到max z=z，即当，即当z达到最小值时达到最小值时z达到最大值，反之亦然。达到最大值，反之亦然。 制作与教学 武汉理工大学管理学院 熊伟 chapter 1 线性规划线性规划linear programming page 30 2021年11月14日星期日综合起来得到下列标准型综合起来得到下列标准型 332133maxxxxxz 05)(23382654332163321533214332

32、1xxxxxxxxxxxxxxxxxxxxxx、1.3 线性规划的标准型线性规划的标准型standard form of lp 制作与教学 武汉理工大学管理学院 熊伟 chapter 1 线性规划线性规划linear programming page 31 2021年11月14日星期日 当某个变量当某个变量xj0时时,令令x/j=xj 。 当某个约束是绝对值不等式当某个约束是绝对值不等式时，将绝对值不等式化为两个不等式，再化为等式，例如约束时，将绝对值不等式化为两个不等式，再化为等式，例如约束 974321xxx将其化为两个不等式将其化为两个不等式 974974321321xxxxxx再加入松

33、驰变量化为等式。再加入松驰变量化为等式。 1.3 线性规划的标准型线性规划的标准型standard form of lp 制作与教学 武汉理工大学管理学院 熊伟 chapter 1 线性规划线性规划linear programming page 32 2021年11月14日星期日【例例1-13】将下例线性规划化为标准型】将下例线性规划化为标准型无约束、211212145|maxxxxxxxxz【解】解】 此题关键是将目标函数中的绝对值去掉。此题关键是将目标函数中的绝对值去掉。令令 0000000000002222222211111111xxxxxxxxxxxxxxxx，222222111111

34、,|,|xxxxxxxxxxxx 则有则有1.3 线性规划的标准型线性规划的标准型standard form of lp 制作与教学 武汉理工大学管理学院 熊伟 chapter 1 线性规划线性规划linear programming page 33 2021年11月14日星期日得到线性规划的标准形式得到线性规划的标准形式 112211223114112234max()()540zxxxxxxxxxxxxxxxxxx 、 、 、 、 、1.3 线性规划的标准型线性规划的标准型standard form of lp对于对于axb(a、b均大于零均大于零)的有界变量化为标准形式有两种方的有界变量化

35、为标准形式有两种方法。法。 一种方法是增加两个约束一种方法是增加两个约束xa及及xb 另一种方法是令另一种方法是令x=xa，则，则axb等价于等价于0 xba，增加，增加一个约束一个约束xba并且将原问题所有并且将原问题所有x用用x= x+a替换。替换。 制作与教学 武汉理工大学管理学院 熊伟 chapter 1 线性规划线性规划linear programming page 34 2021年11月14日星期日1.如何化标准形式？如何化标准形式？ 可以对照四条标准逐一判断！可以对照四条标准逐一判断！ 标准形式是人为定义的，目标函数可以是求最小值。标准形式是人为定义的，目标函数可以是求最小值。2

36、.用用winqsb软件求解时，不必化成标准型。软件求解时，不必化成标准型。图解法时不必化为标准型。图解法时不必化为标准型。3.单纯形法求解时一定要化为标准型。单纯形法求解时一定要化为标准型。作业：教材习题作业：教材习题 1.81.3 线性规划的标准型线性规划的标准型standard form of lp下一节：基本概念下一节：基本概念1.4 线性规划的有关概念线性规划的有关概念basic concepts of lp 制作与教学 武汉理工大学管理学院 熊伟 chapter 1 线性规划线性规划linear programming page 36 2021年11月14日星期日 设线性规划的标准型

37、设线性规划的标准型 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 ）。当）。当m=n时，基矩阵唯一，时，基矩阵唯一，当当mn时，基矩阵就可能有多个，但数目不超过时，基矩阵就可能有多个，但数目不超过mnc 制作与教学 武汉

38、理工大学管理学院 熊伟 chapter 1 线性规划线性规划linear programming page 37 2021年11月14日星期日【例【例1-14】线性规划】线性规划 32124maxxxxz5 , 1, 0226103553214321jxxxxxxxxxj 求所有基矩阵求所有基矩阵。 【解】约束方程的系数矩阵为【解】约束方程的系数矩阵为25矩阵矩阵 10261001115a,610151b,010152b,110053b26114b10019b,12017b,02118b,16016b,06115b容易看出容易看出r(a)=2，2阶子矩阵有阶子矩阵有c52=10个，其中第个，其

39、中第1列与第列与第3列构成列构成的的2阶矩阵不是一个基，基矩阵只有阶矩阵不是一个基，基矩阵只有9个，即个，即1.4 基本概念基本概念basic concepts 制作与教学 武汉理工大学管理学院 熊伟 chapter 1 线性规划线性规划linear programming page 38 2021年11月14日星期日由线性代数知，基矩阵由线性代数知，基矩阵b必为非奇异矩阵并且必为非奇异矩阵并且|b|0。当矩。当矩阵阵b的行列式等式零即的行列式等式零即|b|=0时就不是基时就不是基 当确定某一矩阵为基矩阵时，则基矩阵对应的列向量称为当确定某一矩阵为基矩阵时，则基矩阵对应的列向量称为基基向量向量

40、(basis vector)，其余列向量称为，其余列向量称为非基向量非基向量 基向量对应的变量称为基向量对应的变量称为基变量基变量(basis variable)，非基向量，非基向量对应的变量称为对应的变量称为非基变量非基变量 在上例中在上例中b2的基向量是的基向量是a中的第一列和第四列，其余列向量中的第一列和第四列，其余列向量是非基向量，是非基向量，x1、x4是基变量，是基变量，x2、x3、x5是非基变量。基变是非基变量。基变量、非基变量是针对某一确定基而言的，不同的基对应的基量、非基变量是针对某一确定基而言的，不同的基对应的基变量和非基变量也不同。变量和非基变量也不同。010152b102

41、61001115a1.4 基本概念基本概念basic concepts 制作与教学 武汉理工大学管理学院 熊伟 chapter 1 线性规划线性规划linear programming page 39 2021年11月14日星期日可行解可行解(feasible solution) 满足式（满足式（1.2）及（）及（1.3）的解）的解x=（x1,x2，xn)t 称为可行解称为可行解 。基本可行解基本可行解(basis feasible solution) 若基本解是可行解则称若基本解是可行解则称为是基本可行解（也称基可行解）。为是基本可行解（也称基可行解）。 例如，例如， 与与x=（0，0，0，

42、3，2，）都是例，）都是例1 的可行解。的可行解。 tx) 1 ,27,21, 0 , 0( 基本解基本解(basis solution) 对某一确定的基对某一确定的基b，令非基变量等于零，令非基变量等于零，利用式（利用式（1.） 解出基变量，则这组解称为基解出基变量，则这组解称为基的基的基本解。本解。 最优解最优解(optimal solution) 满足式满足式 （1 .1）的可行解称为最优解，）的可行解称为最优解，即是使得目标函数达到最大值的可行解就是最优解，例即是使得目标函数达到最大值的可行解就是最优解，例如可行解如可行解 是例是例2的最优解。的最优解。tx)8 ,0,0,0,53(非

43、可行解非可行解(infeasible solution) 无界解无界解 (unbound solution)1.4 基本概念基本概念basic concepts 制作与教学 武汉理工大学管理学院 熊伟 chapter 1 线性规划线性规划linear programming page 40 2021年11月14日星期日显然，只要基本解中的基变量的解满足式（显然，只要基本解中的基变量的解满足式（1.）的非负要求，）的非负要求，那么这个基本解就是基本可行解。那么这个基本解就是基本可行解。 在例在例1-13中，对中，对来说，来说，x1,x2是基变量，是基变量，x3,x4，x5是非基变量，是非基变量，

44、令令x3=x4=x5=0，则式（，则式（1.）为）为2610352121xxxx,610151b对对b2来说，来说，x1,x4,为基变量，令非基变量为基变量，令非基变量x2,x3,x5为零，由式为零，由式（1.2）得到）得到 ，x4=4，511x因因|b1|，由克莱姆法则知，由克莱姆法则知，x1、x2有唯一解有唯一解x12/5,x2=1则则 基基本解为本解为tx)0 , 0 , 0 , 1 ,52()1(1.4 基本概念基本概念basic concepts 制作与教学 武汉理工大学管理学院 熊伟 chapter 1 线性规划线性规划linear programming page 41 2021

45、年11月14日星期日由于由于 是基本解，从而它是基本可行解，在是基本解，从而它是基本可行解，在 中中x10i表表1-6(a)xbx1x2x3x4bx3211040 x413/20130j30040000 (b)x3x2j (c)x1 x210 j 基变量基变量120002/302/3204/31- -2/340100/30- -800/330103/4- -1/21501- -1/2 11000- -25- -250将将3/2化为化为11.5 单纯形法单纯形法 simplex method2015 制作与教学 武汉理工大学管理学院 熊伟 chapter 1 线性规划线性规划linear pro

46、gramming page 54 2021年11月14日星期日最优解最优解x=(15，10，0，0)t，最优值，最优值z=8500x(1)=(0,0)x11.5 单纯形法单纯形法 simplex methodx1x2o102030401020304040221xx305 . 121xx0, 0305 . 1402212121xxxxxx12max300400zxxx(2)=(0,20)x(3)=(15,10) 制作与教学 武汉理工大学管理学院 熊伟 chapter 1 线性规划线性规划linear programming page 55 2021年11月14日星期日单纯形法全过程的计算，可以用

47、列表的方法计算更为简洁，单纯形法全过程的计算，可以用列表的方法计算更为简洁，这种表格称为单纯形表（表这种表格称为单纯形表（表1-6）。）。计算步骤：计算步骤：1.求初始基可行解，列出初始单纯形表，求出检验数。其中求初始基可行解，列出初始单纯形表，求出检验数。其中基变量的检验数必为零；基变量的检验数必为零； 2.判断：判断： （a）若）若j（j，n）得到最优解；）得到最优解； （b）某个）某个k0且且aik（i=1，2,m）则线性规划具有无）则线性规划具有无界解界解(见例见例1-18)。 （c）若存在）若存在k0且且aik (i=1,m)不全非正，则进行换基；不全非正，则进行换基；1.5 单纯形

48、法单纯形法 simplex method 制作与教学 武汉理工大学管理学院 熊伟 chapter 1 线性规划线性规划linear programming page 56 2021年11月14日星期日min0,0,iilikikikikbbaam maa当 时为任意大的正数第第个比值最小个比值最小 ，选最小比值对应行的基变量为出基变量，选最小比值对应行的基变量为出基变量，若有相同最小比值，则任选一个。若有相同最小比值，则任选一个。alk为主元素；为主元素； (c）求新的基可行解：用初等行变换方法将）求新的基可行解：用初等行变换方法将alk 化为化为,k列列其它元素化为零（包括检验数行）得到新的

49、可行基及基本可其它元素化为零（包括检验数行）得到新的可行基及基本可行解，再判断是否得到最优解。行解，再判断是否得到最优解。（b）选出基变量）选出基变量 ，求最小比值：，求最小比值：1.5 单纯形法单纯形法 simplex method3.换基：换基：（a）选进基变量）选进基变量设设k=max j | j 0,xk为进基变量为进基变量 制作与教学 武汉理工大学管理学院 熊伟 chapter 1 线性规划线性规划linear programming page 57 2021年11月14日星期日【例【例1-16】 用单纯形法求解用单纯形法求解3212maxxxxz020531152323213213

50、21xxxxxxxxx、【解】将数学模型化为标准形式：【解】将数学模型化为标准形式：3212maxxxxz5 , 2 , 1, 0205311523253214321jxxxxxxxxxj不难看出不难看出x4、x5可作为初始基变量，单纯法计算结果如可作为初始基变量，单纯法计算结果如表表 1-7所示所示 。 1.5 单纯形法单纯形法 simplex method 制作与教学 武汉理工大学管理学院 熊伟 chapter 1 线性规划线性规划linear programming page 58 2021年11月14日星期日cj12100bcbxbx1x2x3x4x50 x423210150 x51/

51、3150120j12100 0 x42x2j 1x1 2x2 j 表表171/3150120301713751/30902m2025601017/31/31250128/91/92/335/30098/91/97/3最优解最优解x=(25，35/3，0，0，0)t，最优值，最优值z=145/31.5 单纯形法单纯形法 simplex method 制作与教学 武汉理工大学管理学院 熊伟 chapter 1 线性规划线性规划linear programming page 59 2021年11月14日星期日【例【例1-17】用单纯形法求解】用单纯形法求解 42122minxxxz5 , 1, 02

52、12665521421321jxxxxxxxxxxj【解】【解】 这是一个极小化的线性规划问题这是一个极小化的线性规划问题,可以将其化为极大化问可以将其化为极大化问题求解题求解,也可以直接求解也可以直接求解,这时判断标准是：这时判断标准是：j0(j=1，n)时得时得到最优解到最优解。容易观察到容易观察到,系数矩阵中有一个系数矩阵中有一个3阶单位矩阵阶单位矩阵,x3、x4、x5为基变量为基变量。目标函数中含有基变量。目标函数中含有基变量x4,由第二个约束得到由第二个约束得到x4=6+x1x2，并代，并代入目标函数消去入目标函数消去x4得得12121222(6)6zxxxxxx 1.5 单纯形法单

53、纯形法 simplex method 制作与教学 武汉理工大学管理学院 熊伟 chapter 1 线性规划线性规划linear programming page 60 2021年11月14日星期日xbx1x2x3x4x5bx3x4x51- -1611210001000156215621/2j1- -1000 x2x4x51- -241001- -1- -20100015111 j20100 表中表中j0,j=1,2,5所以最优解为所以最优解为x=(0,5,0,1,11,)最优值最优值 z=2x12x2x4=251=11极小值问题极小值问题,注意判断标准注意判断标准,选进基变量时选进基变量时,应

54、选应选j0, x2进基，而进基，而a120，a220且且aik（i=1，2,m）则线）则线性规划具有无界解性规划具有无界解退化基本可行解的判断退化基本可行解的判断:存在某个基变量为零的基本可存在某个基变量为零的基本可行解。行解。1.5 单纯形法单纯形法 simplex method 制作与教学 武汉理工大学管理学院 熊伟 chapter 1 线性规划线性规划linear programming page 67 2021年11月14日星期日在实际问题中有些模型并不含有单位矩阵，为了得到一组基向在实际问题中有些模型并不含有单位矩阵，为了得到一组基向量和初基可行解，在约束条件的等式左端加一组虚拟变量

55、，得量和初基可行解，在约束条件的等式左端加一组虚拟变量，得到一组基变量。这种人为加的变量称为人工变量，构成的可行到一组基变量。这种人为加的变量称为人工变量，构成的可行基称为人工基，用大基称为人工基，用大m法或两阶段法求解，这种用人工变量作法或两阶段法求解，这种用人工变量作桥梁的求解方法称为人工变量法。桥梁的求解方法称为人工变量法。【例【例1-20】用大】用大m法解法解 下列线性规划下列线性规划012210243423max321321321321321xxxxxxxxxxxxxxxz、1. 大大m 单纯形法单纯形法1.5.2大大m和两阶段单纯形法和两阶段单纯形法1.5 单纯形法单纯形法 sim

56、plex method 制作与教学 武汉理工大学管理学院 熊伟 chapter 1 线性规划线性规划linear programming page 68 2021年11月14日星期日【解】首先将数学模型化为标准形式【解】首先将数学模型化为标准形式5 , 2 , 1, 012210243423max32153214321321jxxxxxxxxxxxxxxxzj式中式中x4，x5为松弛变量，为松弛变量，x5可作为可作为一个基变量，第一、三约束中分一个基变量，第一、三约束中分别加入人工变量别加入人工变量x6、x7，目标函，目标函数中加入数中加入mx6mx7一项，得到一项，得到人工变量单纯形法数学模

57、型人工变量单纯形法数学模型用前面介绍的单纯形法求用前面介绍的单纯形法求解，见下表。解，见下表。 7 , 2 , 1, 012210243423max732153216432176321jxxxxxxxxxxxxxxmxmxxxxzj1.5 单纯形法单纯形法 simplex methodcj32100mmbcbxbx1x2x3x4x5x6x7m0mx6x5x74123121211000101000014101j3-2m2+m-1+2mm000m01x6x5x3632532001100010100381j5-6m5m0m00201x2x5x36/53/52/51000011/53/52/50103

58、/531/511/5j50000231x2x1x301010000111025/32/31331/319/3 制作与教学 武汉理工大学管理学院 熊伟 chapter 1 线性规划线性规划linear programming page 70 2021年11月14日星期日（2）初始表中的检验数有两种算法，第一种算）初始表中的检验数有两种算法，第一种算法是利用第一、三约束将法是利用第一、三约束将x6、x7的表达式代入目的表达式代入目标涵数消去标涵数消去x6和和x7，得到用非基变量表达的目标，得到用非基变量表达的目标函数，其系数就是检验数；第二种算法是利用公函数，其系数就是检验数；第二种算法是利用公式

59、计算，如式计算，如最优解最优解x（31/3，13，19/3，0，0)t；最优值；最优值z152/3注意：注意：1.5 单纯形法单纯形法 simplex method11143( m,0, m)123( m) ( 4)0 1 ( m) 232mbcc p (1) m是一个很大的抽象的数，不需要给出具体的数值，可是一个很大的抽象的数，不需要给出具体的数值，可以理解为它能大于给定的任何一个确定数值以理解为它能大于给定的任何一个确定数值 制作与教学 武汉理工大学管理学院 熊伟 chapter 1 线性规划线性规划linear programming page 71 2021年11月14日星期日【例【例

60、1-21】求解线性规划】求解线性规划 0,426385min21212121xxxxxxxxz【解】加入松驰变量【解】加入松驰变量x3、x4化为标准型化为标准型4 , 2 , 1, 0426385min42132121jxxxxxxxxxzj在第二个方程中加入人工变量在第二个方程中加入人工变量x5，目标函数中加上，目标函数中加上m x5一项，一项，得到得到 1.5 单纯形法单纯形法 simplex method 制作与教学 武汉理工大学管理学院 熊伟 chapter 1 线性规划线性规划linear programming page 72 2021年11月14日星期日5 , 2 , 1, 04