《数据模型与决策线性规划PPT110页》由会员分享，可在线阅读，更多相关《数据模型与决策线性规划PPT110页（110页珍藏版）》请在金锄头文库上搜索。
1、数据、模型与决策数据、模型与决策线性规划线性规划LinearProgramming1.1 LP的数学模型的数学模型MathematicalModelofLP1.2 图解法图解法 GraphicalMethod1.3 标准型标准型 StandardformofLP1.4 基本概念基本概念BasicConcepts1.5 SimplexMethod8/13/20241.1数学模型数学模型MathematicalModel8/13/2024 制作与教学 线性规划线性规划LinearProgramming Page 3 来自来自中国最大的资料库下载中国最大的资料库下载1.1线性规划的数学模型线性规划的
2、数学模型MathematicalModelofLP线性规划通常研究资源的最优利用、设备最佳运行等问线性规划通常研究资源的最优利用、设备最佳运行等问题。例如，当任务或目标确定后，如何统筹兼顾，合理安题。例如，当任务或目标确定后，如何统筹兼顾，合理安排，用最少的资源排，用最少的资源（如资金、设备、原标材料、人工、时（如资金、设备、原标材料、人工、时间等）去完成确定的任务或目标；企业在一定的资源条件间等）去完成确定的任务或目标；企业在一定的资源条件限制下，如何组织安排生产获得最好的经济效益（如产品限制下，如何组织安排生产获得最好的经济效益（如产品量最多量最多、利润最大）。、利润最大）。线性规划线性规
3、划（Linear Programming,缩写为LP）是运筹学的重要是运筹学的重要分支之一，在实际中应用得较广泛，其方法也较成熟，借助分支之一，在实际中应用得较广泛，其方法也较成熟，借助计算机，使得计算更方便，应用领域更广泛和深入。计算机，使得计算更方便，应用领域更广泛和深入。8/13/2024 制作与教学 线性规划线性规划LinearProgramming Page 4 来自来自中国最大的资料库下载中国最大的资料库下载【例例1.1】最最优优生生产产计计划划问问题题。某某企企业业在在计计划划期期内内计计划划生生产产甲甲、乙乙、丙丙三三种种产产品品。这这些些产产品品分分别别需需要要要要在在设设备
4、备A、B上上加加工工，需需要要消消耗耗材材料料C、D，按按工工艺艺资资料料规规定定，单单件件产产品品在在不不同同设设备备上上加加工工及及所所需需要要的的资资源源如如表表1.1所所示示。已已知知在在计计划划期期内内设设备备的的加加工工能能力力各各为为200台台时时，可可供供材材料料分分别别为为360、300公公斤斤；每每生生产产一一件件甲甲、乙乙、丙丙三三种种产产品品，企企业业可可获获得得利利润润分分别别为为40、30、50元元，假假定定市市场场需需求求无无限限制制。企企业业决决策策者者应应如如何何安安排排生生产产计计划划，使使企企业业在在计划期内总的利润收入最大？计划期内总的利润收入最大？1.
5、1线性规划的数学模型线性规划的数学模型MathematicalModelofLP1.1.1应用模型举例应用模型举例8/13/2024 制作与教学 线性规划线性规划LinearProgramming Page 5 来自来自中国最大的资料库下载中国最大的资料库下载产品产品产品产品 资源资源资源资源 甲甲甲甲 乙乙乙乙 丙丙丙丙现有资源现有资源现有资源现有资源设备设备设备设备A A331122200200设备设备设备设备B B222244200200材料材料材料材料C C445511360360材料材料材料材料D D223355300300利润（元利润（元利润（元利润（元/ /件）件）件）件） 40
6、4030305050表表1.1产品资源消耗产品资源消耗1.1线性规划的数学模型线性规划的数学模型MathematicalModelofLP8/13/2024 制作与教学 线性规划线性规划LinearProgramming Page 6 来自来自中国最大的资料库下载中国最大的资料库下载【解】设【解】设x1、x2、x3分别为甲、乙、丙三种产品的产量数学模型分别为甲、乙、丙三种产品的产量数学模型为：为：1.1线性规划的数学模型线性规划的数学模型MathematicalModelofLP产品产品产品产品 资源资源资源资源 甲甲甲甲 乙乙乙乙 丙丙丙丙现有资现有资现有资现有资源源源源设备设备设备设备A
7、A331122200200设备设备设备设备B B222244200200材料材料材料材料C C445511360360材料材料材料材料D D223355300300利润（元利润（元利润（元利润（元/ /件）件）件）件） 404030305050最优解最优解X=(50,30,10);Z=34008/13/2024 制作与教学 线性规划线性规划LinearProgramming Page 7 来自来自中国最大的资料库下载中国最大的资料库下载线性规划的数学模型由线性规划的数学模型由决策变量决策变量Decisionvariables 目标函数目标函数Objectivefunction及约束条件及约束条
8、件Constraints构成。称为三个要素构成。称为三个要素。n其特征是：其特征是：n1解决问题的目标函数是多个决策变量的解决问题的目标函数是多个决策变量的线性函数，通常是求最大值或线性函数，通常是求最大值或最小值；最小值；n2解决问题的解决问题的约束条件约束条件约束条件约束条件是一组多个决策变量是一组多个决策变量的线性不等式或等式。的线性不等式或等式。怎样辨别一个模型是线性规划模型？怎样辨别一个模型是线性规划模型？1.1线性规划的数学模型线性规划的数学模型MathematicalModelofLP8/13/2024 制作与教学 线性规划线性规划LinearProgramming Page 8
9、 来自来自中国最大的资料库下载中国最大的资料库下载【例例1.2】某某商商场场决决定定：营营业业员员每每周周连连续续工工作作5天天后后连连续续休休息息2天天，轮流休息。根据统计，商场每天需要的营业员如表轮流休息。根据统计，商场每天需要的营业员如表1.2所示。所示。表表1.2营业员需要量统计表营业员需要量统计表商场人力资源部应如何安排每天的上班人数，使商场总的营业员商场人力资源部应如何安排每天的上班人数，使商场总的营业员最少。最少。星期星期星期星期需要人数需要人数需要人数需要人数星期星期星期星期需要人数需要人数需要人数需要人数一一一一300300五五五五480480二二二二300300六六六六60
10、0600三三三三350350日日日日550550四四四四4004001.1线性规划的数学模型线性规划的数学模型MathematicalModelofLP8/13/2024 制作与教学 线性规划线性规划LinearProgramming Page 9 来自来自中国最大的资料库下载中国最大的资料库下载【解】【解】设设xj(j=1，2，7)为休息为休息2天后星期一到星期日开始上天后星期一到星期日开始上班的营业员，则这个问题的线性规划模型为班的营业员，则这个问题的线性规划模型为1.1线性规划的数学模型线性规划的数学模型MathematicalModelofLP星星星星期期期期需要需要需要需要人数人数人
11、数人数星星星星期期期期需要需要需要需要人数人数人数人数一一一一300300五五五五480480二二二二300300六六六六600600三三三三350350日日日日550550四四四四4004008/13/2024 制作与教学 线性规划线性规划LinearProgramming Page 10 来自来自中国最大的资料库下载中国最大的资料库下载1 1 1 1 X1X1X1X10 0 0 0 C1C1C1C1404404404404 =3003003003001041041041042 2 2 2 X2X2X2X267676767 C2C2C2C2301301301301 =300300300300
12、1 1 1 13 3 3 3 X3X3X3X3146146146146 C3C3C3C3350350350350 =3503503503500 0 0 04 4 4 4 X4X4X4X4170170170170 C4C4C4C4400400400400 =4004004004000 0 0 05 5 5 5 X5X5X5X597979797 C5C5C5C5480480480480 =4804804804800 0 0 06 6 6 6 X6X6X6X6120120120120 C6C6C6C6600600600600 =6006006006000 0 0 07 7 7 7 X7X7X7X71
13、7171717 C7C7C7C7550550550550 =5505505505500 0 0 0最优解：最优解：Z617（人）（人）8/13/2024 制作与教学 线性规划线性规划LinearProgramming Page 11 来自来自中国最大的资料库下载中国最大的资料库下载【例【例1.3】合理用料问题。某汽车需要用甲、乙、丙三种规格的轴各一根，这些】合理用料问题。某汽车需要用甲、乙、丙三种规格的轴各一根，这些轴的规格分别是轴的规格分别是1.5，1，0.7（m），这些轴需要用同一种圆钢来做，圆钢长度），这些轴需要用同一种圆钢来做，圆钢长度为为4m。现在要制造。现在要制造1000辆汽车，最
14、少要用多少圆钢来生产这些轴？辆汽车，最少要用多少圆钢来生产这些轴？【解】这是一个条材下料问题【解】这是一个条材下料问题，设切口宽度为零。，设切口宽度为零。设一根圆钢切割成甲、设一根圆钢切割成甲、乙、丙三种轴的根数分别为乙、丙三种轴的根数分别为y1，y2，y3,则切割方式可用不等式则切割方式可用不等式1.5y1+y2+0.7y34表示，求这个不等式关于表示，求这个不等式关于y1，y2，y3的非负整数解。象这样的非负整数解。象这样的非负整数解共有的非负整数解共有10组，也就是有组，也就是有10种下料方式，如表种下料方式，如表1.3所示。所示。表表13下料方案下料方案方案方案方案方案规格规格规格规格
15、112 23 34 45 56 67 78 89 91010需求量需求量需求量需求量y y1 1( (根根根根) ) 2 22 21 1111 100000 00 00 010001000y y221 10 02 2110 044332 21 10 010001000y y3 3 0 01 10 0223 300112 24 45 510001000余料余料余料余料（mm）0 00.30.30.50.50.10.1o.4o.4000.30.30.60.60.20.20.50.51.1线性规划的数学模型线性规划的数学模型MathematicalModelofLP8/13/2024 制作与教学 线
16、性规划线性规划LinearProgramming Page 12 来自来自中国最大的资料库下载中国最大的资料库下载设设xj(j=1,2,10)为为第第j种种下下料料方方案案所所用用圆圆钢钢的的根根数数。则则用用料料最最少数学模型少数学模型为为为为: :求下料方案时应注意，余料不能超过最短毛坯的长度；最好将毛求下料方案时应注意，余料不能超过最短毛坯的长度；最好将毛坯长度按降的次序排列，即先切割长度最长的毛坯，再切割次长坯长度按降的次序排列，即先切割长度最长的毛坯，再切割次长的，最后切割最短的，不能遗漏了方案的，最后切割最短的，不能遗漏了方案。如果方案较多，用计算。如果方案较多，用计算机编程排方案
17、，去掉余料较长的方案，进行初选。机编程排方案，去掉余料较长的方案，进行初选。1.1线性规划的数学模型线性规划的数学模型MathematicalModelofLP方案方案方案方案规格规格规格规格112 23 34 45 56 67 78 89 91010需求量需求量需求量需求量y y1 1( (根根根根) )2 22 21 11 11 10 00 00 00 00 010001000y y221 10 02 21 10 0443 32 21 10 010001000y y3 3 0 01 10 02 23 30 01 12 24 45 510001000余料（余料（余料（余料（mm）0 00.3
18、0.30.50.50.10.1o.4o.40 00.30.30.60.60.20.20.50.58/13/2024 制作与教学 线性规划线性规划LinearProgramming Page 13 来自来自中国最大的资料库下载中国最大的资料库下载1 1 1 1 X1X1X1X15005005005002 2 2 2 X2X2X2X20 0 0 03 3 3 3 X3X3X3X30 0 0 04 4 4 4 X4X4X4X40 0 0 05 5 5 5 X5X5X5X50 0 0 06 6 6 6 X6X6X6X662.562.562.562.57 7 7 7 X7X7X7X70 0 0 08 8
19、 8 8 X8X8X8X80 0 0 09 9 9 9 X9X9X9X925025025025010101010 X10X10X10X100 0 0 0Z812.58/13/2024 制作与教学 线性规划线性规划LinearProgramming Page 14 来自来自中国最大的资料库下载中国最大的资料库下载【例例1.4】配配料料问问题题。某某钢钢铁铁公公司司生生产产一一种种合合金金，要要求求的的成成分分规规格格是是：锡锡不不少少于于28%，锌锌不不多多于于15%，铅铅恰恰好好10%，镍镍要要界界于于35%55%之之间间，不不允允许许有有其其他他成成分分。钢钢铁铁公公司司拟拟从从五五种种不不
20、同同级级别别的的矿矿石石中中进进行行冶冶炼炼，每每种种矿矿物物的的成成分分含含量量和和价价格格如如表表1.4所所示示。矿矿石石杂杂质质在在治治炼炼过过程程中中废废弃弃，现现要要求求每每吨吨合合金金成成本本最最低低的的矿矿物物数数量量。假设矿石在冶炼过程中，合金含量没有发生变化。假设矿石在冶炼过程中，合金含量没有发生变化。表表1.4矿石的金属含量矿石的金属含量合金合金合金合金矿石矿石矿石矿石锡锡锡锡%锌锌锌锌%铅铅铅铅%镍镍镍镍% 杂质杂质杂质杂质费用（元费用（元费用（元费用（元/t/t）1 1252510101010252530303403402 240400 00 0303030302602
21、603 30 015155 5202060601801804 4202020200 0404020202302305 58 85 51515171755551901901.1线性规划的数学模型线性规划的数学模型MathematicalModelofLP8/13/2024 制作与教学 线性规划线性规划LinearProgramming Page 15 来自来自中国最大的资料库下载中国最大的资料库下载解解:设设xj（j=1,2，5）是第）是第j种矿石数量，得到下列线性规划模种矿石数量，得到下列线性规划模型型注注意意，矿矿石石在在实实际际冶冶炼炼时时金金属属含含量量会会发发生生变变化化，建建模模时时
22、应应将将这这种种变变化化考考虑虑进进去去，有有可可能能是是非非线线性性关关系系。配配料料问问题题也也称称配配方方问问题题、营养问题或混合问题，在许多行业生产中都能遇到。营养问题或混合问题，在许多行业生产中都能遇到。1.1线性规划的数学模型线性规划的数学模型MathematicalModelofLP矿石矿石矿石矿石锡锡锡锡%锌锌锌锌%铅铅铅铅%镍镍镍镍%杂质杂质杂质杂质费用（元费用（元费用（元费用（元/t/t）1 1252510101010252530303403402 240400 00 0303030302602603 30 015155 5202060601801804 420202020
23、0 0404020202302305 58 85 51515171755551901908/13/2024 制作与教学 线性规划线性规划LinearProgramming Page 16 来自来自中国最大的资料库下载中国最大的资料库下载1 1 1 1 X1X1X1X10 0 0 02 2 2 2 X2X2X2X20.33330.33330.33330.33333 3 3 3 X3X3X3X30 0 0 04 4 4 4 X4X4X4X40.58330.58330.58330.58335 5 5 5 X5X5X5X50.66670.66670.66670.6667最优解：最优解：Z=347.51
24、.1线性规划的数学模型线性规划的数学模型MathematicalModelofLP8/13/2024 制作与教学 线性规划线性规划LinearProgramming Page 17 来自来自中国最大的资料库下载中国最大的资料库下载【例例1.5】投投资资问问题题。某某投投资资公公司司在在第第一一年年有有200万万元元资资金金，每每年年都都有有如如下下的的投投资资方方案案可可供供考考虑虑采采纳纳：“假假使使第第一一年年投投入入一一笔笔资资金金，第第二二年年又又继继续续投投入入此此资资金金的的50%，那那么么到到第第三三年年就就可可回回收收第第一一年年投投入入资资金金的的一一倍倍金金额额”。投投资资
25、公公司司决决定定最最优优的的投投资资策策略略使使第第六六年年所所掌掌握握的的资资金金最最多。多。第五年：第五年：(x7/2+x9)=x8+2x5第一年：第一年：x1+x2=200(万元万元)第二年：第二年：(x1/2+x3)+x4=x2第三年第三年(x3/2+x5)+x6=x4+2x1第四年：第四年：(x5/2+x7)+x8=x6+2x3到第六年实有资金总额为到第六年实有资金总额为x9+2x7，整理后得到下列线性规划模型，整理后得到下列线性规划模型1.1线性规划的数学模型线性规划的数学模型MathematicalModelofLP【解】设【解】设x1：第一年的投资；：第一年的投资；x2：第一年
26、的保留资金：第一年的保留资金x3：第二年新的投资；：第二年新的投资；x4：第二年的保留资金：第二年的保留资金x5：第三年新的投资；：第三年新的投资；x6：第三年的保留资金：第三年的保留资金x7：第四年新的投资：第四年新的投资x8：第四年的保留资金：第四年的保留资金x9：第五年的保留资金：第五年的保留资金8/13/2024 制作与教学 线性规划线性规划LinearProgramming Page 18 来自来自中国最大的资料库下载中国最大的资料库下载1.1线性规划的数学模型线性规划的数学模型MathematicalModelofLP1 1 1 1 X1X1X1X155.284655.284655
27、.284655.28462 2 2 2 X2X2X2X2144.7155144.7155144.7155144.71553 3 3 3 X3X3X3X3117.0732117.0732117.0732117.07324 4 4 4 X4X4X4X40 0 0 05 5 5 5 X5X5X5X552.032552.032552.032552.03256 6 6 6 X6X6X6X60 0 0 07 7 7 7 X7X7X7X7208.1301208.1301208.1301208.13018 8 8 8 X8X8X8X80 0 0 09 9 9 9 X9X9X9X90 0 0 0最优解：最优解：
28、Z416.26万元万元x1：第一年的投资；：第一年的投资；x2：第一年的保留资金：第一年的保留资金x3：第二年新的投资；：第二年新的投资；x4：第二年的保留资金：第二年的保留资金x5：第三年新的投资；：第三年新的投资；x6：第三年的保留资金：第三年的保留资金x7：第四年新的投资：第四年新的投资x8：第四年的保留资金：第四年的保留资金x9：第五年的保留资金：第五年的保留资金8/13/2024 制作与教学 线性规划线性规划LinearProgramming Page 19 来自来自中国最大的资料库下载中国最大的资料库下载【例例1.6】均均衡衡配配套套生生产产问问题题。某某产产品品由由2件件甲甲、3
29、件件乙乙零零件件组组装装而而成成。两两种种零零件件必必须须经经过过设设备备A、B上上加加工工，每每件件甲甲零零件件在在A、B上上的的加加工工时时间间分分别别为为5分分钟钟和和9分分钟钟，每每件件乙乙零零件件在在A、B上上的的加加工工时时间间分分别别为为4分分钟钟和和10分分钟钟。现现有有2台台设设备备A和和3台台设设备备B，每每天天可可供供加加工工时时间间为为8小小时时。为为了了保保持持两两种种设设备备均均衡衡负负荷荷生生产产，要要求求一一种种设设备备每每天天的的加加工工总总时时间间不不超超过过另另一一种种设设备备总总时时间间1小小时时。怎怎样样安安排排设设备备的的加加工工时时间间使使每每天天
30、产产品品的的产量最大。产量最大。【解】【解】设设x1、x2为每天加工甲、乙两种零件的件数，则产品的产量是为每天加工甲、乙两种零件的件数，则产品的产量是设备设备A、B每天加工工时的约束为每天加工工时的约束为要求一种设备每台每天的加工时间不超过另一种设备要求一种设备每台每天的加工时间不超过另一种设备1小时的约束小时的约束为为1.1线性规划的数学模型线性规划的数学模型MathematicalModelofLP8/13/2024 制作与教学 线性规划线性规划LinearProgramming Page 20 来自来自中国最大的资料库下载中国最大的资料库下载目标函数线性化。产品的产量目标函数线性化。产品
31、的产量y等价于等价于整理得到线性规划模型整理得到线性规划模型约束线性化。将绝对值约束写成两个不等式约束线性化。将绝对值约束写成两个不等式1.1线性规划的数学模型线性规划的数学模型MathematicalModelofLP8/13/2024 制作与教学 线性规划线性规划LinearProgramming Page 21 来自来自中国最大的资料库下载中国最大的资料库下载1.1.2线性规划的一般模型线性规划的一般模型一一般般地地，假假设设线线性性规规划划数数学学模模型型中中，有有m个个约约束束，有有n个个决决策策变变量量xj,j=1,2,n，目目标标函函数数的的变变量量系系数数用用cj表表示示,cj
32、称称为为价价值值系系数数。约约束束条条件件的的变变量量系系数数用用aij表表示示，aij称称为为工工艺艺系系数数。约约束束条条件件右右端端的的常常数数用用bi表表示示，bi称称为为资资源源限限量量。则则线线性性规规划划数数学学模模型型的的一一般般表表达达式可写成式可写成为了书写方便，上式也可写成：为了书写方便，上式也可写成：1.1线性规划的数学模型线性规划的数学模型MathematicalModelofLP8/13/2024 制作与教学 线性规划线性规划LinearProgramming Page 22 来自来自中国最大的资料库下载中国最大的资料库下载在实际中一般在实际中一般xj0,但有时但有
33、时xj0或或xj无符号限制。无符号限制。1.1线性规划的数学模型线性规划的数学模型MathematicalModelofLP8/13/2024 制作与教学 线性规划线性规划LinearProgramming Page 23 来自来自中国最大的资料库下载中国最大的资料库下载1.什么是线性规划，掌握线性规划在管理中的什么是线性规划，掌握线性规划在管理中的几个应用例子几个应用例子2.线性规划数学模型的组成及其特征线性规划数学模型的组成及其特征3.线性规划数学模型的一般表达式。线性规划数学模型的一般表达式。作业：教材作业：教材P31T2，3，4，5，61.1线性规划的数学模型线性规划的数学模型Math
34、ematicalModelofLP下一节：图解法下一节：图解法8/13/20241.2图解法图解法 GraphicalMethod8/13/2024 制作与教学 线性规划线性规划LinearProgramming Page 25 来自来自中国最大的资料库下载中国最大的资料库下载图解法的步骤：图解法的步骤：1.求可行解集合。求可行解集合。分别求出满足每个约束包括变量非分别求出满足每个约束包括变量非负要求的负要求的区域，其交集就是可行解集合，或称为区域，其交集就是可行解集合，或称为可行域可行域；2.绘制目标函数图形。绘制目标函数图形。先过原点作一条矢量指向点（先过原点作一条矢量指向点（c1,c2)
35、，矢量的方向就是目标函数增加的方向，称为梯度方向，再作一矢量的方向就是目标函数增加的方向，称为梯度方向，再作一条与矢量垂直的直线，这条直线就是目标函数图形；条与矢量垂直的直线，这条直线就是目标函数图形；3.求最优解。求最优解。依据目标函数求最大或最小移动目标函数直线，依据目标函数求最大或最小移动目标函数直线，直线与可行域相交的点对应的坐标就是直线与可行域相交的点对应的坐标就是最优解。最优解。一般地，将目标函数直线放在可行域中一般地，将目标函数直线放在可行域中求最大值时直线沿着矢量方向移动求最大值时直线沿着矢量方向移动求最小值时沿着矢量的反方向移动求最小值时沿着矢量的反方向移动1.2图解法图解法
36、TheGraphicalMethod8/13/2024 制作与教学 线性规划线性规划LinearProgramming Page 26 来自来自中国最大的资料库下载中国最大的资料库下载x1x2O1020304010203040(3,4)(15,10)最优解最优解X=(15,10)最优值最优值Z=85例例1.71.2图解法图解法TheGraphicalMethod8/13/2024 制作与教学 线性规划线性规划LinearProgramming Page 27 来自来自中国最大的资料库下载中国最大的资料库下载246x1x2246最优解最优解X=(3,1)最优值最优值Z=5(3,1)min Z=x
37、1+2x2例例1.8(1,2)1.2图解法图解法TheGraphicalMethod8/13/2024 制作与教学 线性规划线性规划LinearProgramming Page 28 来自来自中国最大的资料库下载中国最大的资料库下载246x1x2246X（2）（3,1）X（1）（1,3）(5,5)min Z=5x1+5x2例例1.9有无穷多个最优解有无穷多个最优解即具有多重解即具有多重解,通解为通解为01 当当=0.5时时=(x1,x2)=0.5(1,3)+0.5(3,1)=(2,2)1.2图解法图解法TheGraphicalMethod8/13/2024 制作与教学 线性规划线性规划Line
38、arProgramming Page 29 来自来自中国最大的资料库下载中国最大的资料库下载246x1x2246(1,2)无界解无界解(无最优解无最优解)max Z=x1+2x2例例1.108/13/2024 制作与教学 线性规划线性规划LinearProgramming Page 30 来自来自中国最大的资料库下载中国最大的资料库下载x1x2O10203040102030405050无可行解无可行解即无最优解即无最优解max Z=10x1+4x2例例1.111.2图解法图解法TheGraphicalMethod8/13/2024 制作与教学 线性规划线性规划LinearProgramming
39、 Page 31 来自来自中国最大的资料库下载中国最大的资料库下载由以上例题可知，线性规划的解有由以上例题可知，线性规划的解有4种形式种形式：1.有唯一最优解有唯一最优解(例例1.7例例1.8)2.有多重解有多重解(例例1.9)3.有无界解有无界解(例例1.10)4.无可行解无可行解(例例1.11)1、2情形为有最优解情形为有最优解3、4情形为无最优解情形为无最优解1.2图解法图解法TheGraphicalMethod8/13/2024 制作与教学 线性规划线性规划LinearProgramming Page 32 来自来自中国最大的资料库下载中国最大的资料库下载1.通过图解法了解线性规划有几
40、种解的形式通过图解法了解线性规划有几种解的形式2.作图的关键有三点作图的关键有三点(1)可行解区域要画正确可行解区域要画正确(2)目标函数增加的方向不能画错目标函数增加的方向不能画错(3)目标函数的直线怎样平行移动目标函数的直线怎样平行移动作业：教材作业：教材P34T71.2图解法图解法TheGraphicalMethod下一节：线性规划的标准型下一节：线性规划的标准型8/13/20241.3线性规划的标准型线性规划的标准型StandardformofLP8/13/2024 制作与教学 线性规划线性规划LinearProgramming Page 34 来自来自中国最大的资料库下载中国最大的资
41、料库下载在用单纯法求解线性规划问题时，为了讨论问题在用单纯法求解线性规划问题时，为了讨论问题方便，需将线性规划模型化为统一的标准形式。方便，需将线性规划模型化为统一的标准形式。1.3线性规划的标准型线性规划的标准型StandardformofLP线性规划问题的标准型为线性规划问题的标准型为:1目标函数求最大值（或求最小值）目标函数求最大值（或求最小值）2约束条件都为等式方程约束条件都为等式方程3变量变量xj非负非负4常数常数bi非负非负8/13/2024 制作与教学 线性规划线性规划LinearProgramming Page 35 来自来自中国最大的资料库下载中国最大的资料库下载max(或m
42、in)Z=c1x1+c2x2+cnxn1.3线性规划的标准型线性规划的标准型StandardformofLP注：本教材默认目标函数是注：本教材默认目标函数是max8/13/2024 制作与教学 线性规划线性规划LinearProgramming Page 36 来自来自中国最大的资料库下载中国最大的资料库下载或写成下列形式或写成下列形式： 或用矩阵形式或用矩阵形式1.3线性规划的标准型线性规划的标准型StandardformofLP8/13/2024 制作与教学 线性规划线性规划LinearProgramming Page 37 来自来自中国最大的资料库下载中国最大的资料库下载通常通常X记为：
43、记为：称为约束方称为约束方程的系数矩阵，程的系数矩阵，m是约束方程的个数，是约束方程的个数，n是决策变量的个数，是决策变量的个数，一般情况一般情况mn，且，且r()m。其中其中:1.3线性规划的标准型线性规划的标准型StandardformofLP8/13/2024 制作与教学 线性规划线性规划LinearProgramming Page 38 来自来自中国最大的资料库下载中国最大的资料库下载【例【例1.12】将下列线性规划化为标准型】将下列线性规划化为标准型【解】（）因为【解】（）因为x3无符号要求无符号要求，即，即x3取正值也取正值也可取负值，标准型中要求变量非负，所以令可取负值，标准型中
44、要求变量非负，所以令1.3线性规划的标准型线性规划的标准型StandardformofLP8/13/2024 制作与教学 线性规划线性规划LinearProgramming Page 39 来自来自中国最大的资料库下载中国最大的资料库下载(3)第二个约束条件是第二个约束条件是号，在号，在号号左左端减去剩余变量端减去剩余变量(Surplusvariable)x5，x50。也称松驰变。也称松驰变量量1.3线性规划的标准型线性规划的标准型StandardformofLP(2)第一个约束条件是第一个约束条件是号，在号，在左左端加入松驰变量端加入松驰变量(slackvariable)x4，x40,化为等
45、式；化为等式；(4)第三个约束条件是第三个约束条件是号且常数项为负数，因此在号且常数项为负数，因此在左边加入左边加入松驰变量松驰变量x6，x60，同时两边乘以，同时两边乘以1。（5）目标函数是最小值，为了化为求最大值，令）目标函数是最小值，为了化为求最大值，令Z=Z,得到得到maxZ=Z，即当，即当Z达到最小值时达到最小值时Z达到最大值，反之亦然。达到最大值，反之亦然。8/13/2024 制作与教学 线性规划线性规划LinearProgramming Page 40 来自来自中国最大的资料库下载中国最大的资料库下载综合起来得到下列标准型综合起来得到下列标准型1.3线性规划的标准型线性规划的标准
46、型StandardformofLP8/13/2024 制作与教学 线性规划线性规划LinearProgramming Page 41 来自来自中国最大的资料库下载中国最大的资料库下载当某个变量当某个变量xj0时时,令令x/j=xj。当某个约束是绝对值不等式当某个约束是绝对值不等式时，将绝对值不等式化为两个不等式，再化为等式，例如约束时，将绝对值不等式化为两个不等式，再化为等式，例如约束将其化为两个不等式将其化为两个不等式再加入松驰变量化为等式。再加入松驰变量化为等式。1.3线性规划的标准型线性规划的标准型StandardformofLP8/13/2024 制作与教学 线性规划线性规划Linea
47、rProgramming Page 42 来自来自中国最大的资料库下载中国最大的资料库下载【例例1.13】将下例线性规划化为标准型】将下例线性规划化为标准型【解】解】此题关键是将目标函数中的绝对值去掉。此题关键是将目标函数中的绝对值去掉。令令则有则有1.3线性规划的标准型线性规划的标准型StandardformofLP8/13/2024 制作与教学 线性规划线性规划LinearProgramming Page 43 来自来自中国最大的资料库下载中国最大的资料库下载得到线性规划的标准形式得到线性规划的标准形式1.3线性规划的标准型线性规划的标准型StandardformofLP对于对于axb(a
48、、b均大于零均大于零)的有界变量化为标准形式有两种方的有界变量化为标准形式有两种方法，一种方法是增加两个约束法，一种方法是增加两个约束xa及及xb，另一种方法是令，另一种方法是令=xa，则，则axb等价于等价于0ba，增加一个约束，增加一个约束ba并且将原问并且将原问题所有题所有x用用x=+a替换。替换。8/13/2024 制作与教学 线性规划线性规划LinearProgramming Page 44 来自来自中国最大的资料库下载中国最大的资料库下载1.如何化标准形式？如何化标准形式？可以对照四条标准逐一判断！可以对照四条标准逐一判断！标准形式是人为定义的，目标函数可以是求最小值。标准形式是人
49、为定义的，目标函数可以是求最小值。2.用用WinQSB软件求解时，不必化成标准型。软件求解时，不必化成标准型。图解法时不必化为标准型。图解法时不必化为标准型。3.单纯形法求解时一定要化为标准型。单纯形法求解时一定要化为标准型。作业：教材作业：教材P34T81.3线性规划的标准型线性规划的标准型StandardformofLP下一节：基本概念下一节：基本概念8/13/20241.4线性规划的有关概念线性规划的有关概念BasicConceptsofLP8/13/2024 制作与教学 线性规划线性规划LinearProgramming Page 46 来自来自中国最大的资料库下载中国最大的资料库下载
50、设线性规划的标准型设线性规划的标准型maxZ=CX（1.1）AX=b（1.2）X0（1.3）式式中中A是是mn矩矩阵阵，mn并并且且r（A）=m，显显然然A中中至至少少有有一一个个mm子矩阵子矩阵B，使得，使得r（B）=m。1.4基本概念基本概念BasicConcepts基基(basis)A中中mm子矩阵子矩阵B并且有并且有r（B）=m，则称，则称B是线性规是线性规划的一个基（或基矩阵划的一个基（或基矩阵basismatrix）。当）。当m=n时，基矩阵唯一，时，基矩阵唯一，当当mn时，基矩阵就可能有多个，但数目不超过时，基矩阵就可能有多个，但数目不超过8/13/2024 制作与教学 线性规划
51、线性规划LinearProgramming Page 47 来自来自中国最大的资料库下载中国最大的资料库下载【例【例1.14】线性规划】线性规划求所有基矩阵求所有基矩阵。【解】约束方程的系数矩阵为【解】约束方程的系数矩阵为25矩阵矩阵容易看出容易看出r(A)=2，2阶子矩子矩阵有有C52=10个，其中第个，其中第1列与第列与第3列构成列构成的的2阶矩阵不是一个基，基矩阵只有阶矩阵不是一个基，基矩阵只有9个，即个，即1.4基本概念基本概念BasicConcepts8/13/2024 制作与教学 线性规划线性规划LinearProgramming Page 48 来自来自中国最大的资料库下载中国最
52、大的资料库下载由线性代数知，基矩阵由线性代数知，基矩阵B必为非奇异矩阵并且必为非奇异矩阵并且|B|0。当矩阵。当矩阵B的行列式等式零即的行列式等式零即|B|=0时就不是基时就不是基当确定某一矩阵为基矩阵时，则基矩阵对应的列向量称为当确定某一矩阵为基矩阵时，则基矩阵对应的列向量称为基基向量向量(basisvector)，其余列向量称为，其余列向量称为非基向量非基向量基向量对应的变量称为基向量对应的变量称为基变量基变量(basisvariable)，非基向，非基向量对应的变量称为量对应的变量称为非基变量非基变量在在上上例例中中B2的的基基向向量量是是A中中的的第第一一列列和和第第四四列列，其其余余
53、列列向向量量是是非非基基向向量量，x1、x4是是基基变变量量，x2、x3、x5是是非非基基变变量量。基基变变量量、非非基基变变量量是是针针对对某某一一确确定定基基而而言言的的，不不同同的的基基对对应应的的基基变量和非基变量也不同。变量和非基变量也不同。1.4基本概念基本概念BasicConcepts8/13/2024 制作与教学 线性规划线性规划LinearProgramming Page 49 来自来自中国最大的资料库下载中国最大的资料库下载可行解可行解(feasiblesolution)满足式（满足式（1.2）及（）及（1.3）的解）的解X=（x1,x2，xn)T称为可行解称为可行解。基基
54、本本可可行行解解(basisfeasiblesolution)若若基基本本解解是是可可行行解解则则称称为是基本可行解（也称基可行解）。为是基本可行解（也称基可行解）。例如，例如，与与X=（0，0，0，3，2，）都是例，）都是例1的可行解。的可行解。基本解基本解(basissolution)对某一确定的基对某一确定的基B，令非基变量等于零，令非基变量等于零，利用式（利用式（1.）解出基变量，则这组解称为基解出基变量，则这组解称为基的基的基本解。本解。最最优优解解(optimalsolution)满满足足式式（1.1）的的可可行行解解称称为为最最优优解解，即即是是使使得得目目标标函函数数达达到到最
55、最大大值值的的可可行行解解就就是是最最优优解解，例如可行解例如可行解是例是例2的最优解。的最优解。非可行解非可行解(Infeasiblesolution)无界解无界解(unboundsolution)1.4基本概念基本概念BasicConcepts8/13/2024 制作与教学 线性规划线性规划LinearProgramming Page 50 来自来自中国最大的资料库下载中国最大的资料库下载显然，只要基本解中的基变量的解满足式（显然，只要基本解中的基变量的解满足式（1.）的非负要求，）的非负要求，那么这个基本解就是基本可行解。那么这个基本解就是基本可行解。在在例例1.13中中，对对来来说说，
56、x1,x2是是基基变变量量，x3,x4，x5是是非非基基变变量，令量，令x3=x4=x5=0，则式（，则式（1.）为）为对对B2来说，来说，x1,x4,为基变量，令非变量为基变量，令非变量x2,x3,x5为零，由式为零，由式（1.2）得到）得到，x4=4，因因|B1|，由克莱姆法，由克莱姆法则知，知，x1、x2有唯一解有唯一解x12/5,x2=1则则基基本解为本解为1.4基本概念基本概念BasicConcepts8/13/2024 制作与教学 线性规划线性规划LinearProgramming Page 51 来自来自中国最大的资料库下载中国最大的资料库下载由于由于是基本解，从而它是基本可行解
57、，在是基本解，从而它是基本可行解，在中中x10,因此不是可行解，也就不是基本可行解。因此不是可行解，也就不是基本可行解。反之，可行解不一定是基本可行解反之，可行解不一定是基本可行解例如例如满足式（满足式（1.2）（）（1.3），但不是），但不是任何基矩阵的基本解。任何基矩阵的基本解。基本解为基本解为1.4基本概念基本概念BasicConcepts8/13/2024 制作与教学 线性规划线性规划LinearProgramming Page 52 来自来自中国最大的资料库下载中国最大的资料库下载可行基可行基基可行解对应的基称为可行基；基可行解对应的基称为可行基；最优基最优基基本最优解对应的基称为最
58、优基；基本最优解对应的基称为最优基；如上述如上述B3就是最优基，最优基也是可行基。就是最优基，最优基也是可行基。当最优解唯一时，最优解亦当最优解唯一时，最优解亦是基本最优解，当最优解不唯一时，是基本最优解，当最优解不唯一时，则最优解不一定是基本最优解。例则最优解不一定是基本最优解。例如右图中线段如右图中线段的点为最优的点为最优解解时，时，Q1点及点及Q2点是基本最优解点是基本最优解,线线段段的内点是最优解而不是基的内点是最优解而不是基本最优解。本最优解。基本最优解基本最优解最优解是基本解称为基本最优解。例如，满足式最优解是基本解称为基本最优解。例如，满足式（1.1）(1.3)是最优解是最优解,
59、又是又是B3的基本解的基本解,因此它是基本最优解。因此它是基本最优解。1.4基本概念基本概念BasicConcepts8/13/2024 制作与教学 线性规划线性规划LinearProgramming Page 53 来自来自中国最大的资料库下载中国最大的资料库下载基基本本最最优优解解、最最优优解解、基基本本可可行行解解、基基本本解解、可可行行解解的关系如下所示：的关系如下所示：基本最优解基本最优解基本可行解基本可行解可行解可行解最最优优解解基本解基本解例如例如,B点和点和D点是可点是可行解行解,不是基本解不是基本解;C点是基本可行解点是基本可行解;A点点是基本最优解是基本最优解,同时同时也是
60、最优解、基本可也是最优解、基本可行解、基本解和可行行解、基本解和可行解。解。1.4基本概念基本概念BasicConcepts8/13/2024 制作与教学 线性规划线性规划LinearProgramming Page 54 来自来自中国最大的资料库下载中国最大的资料库下载凸集凸集(Convexset)设设K是是n维空间的一个点集，对任意两点维空间的一个点集，对任意两点时，则称时，则称K为凸集。为凸集。就就是是以以X（1）、X（2）为为端端点点的的线线段段方方程程，点点X的的位位置置由由的的值值确确定定，当当=0时时，X=X（2），当当=1时时X=X（1）凸凸组组合合(Convexcombina
61、tion) 设设是是Rn中的点若存在中的点若存在使使得得成成立立，则则称称X为为的的凸组合。凸组合。1.4基本概念基本概念BasicConcepts8/13/2024 制作与教学 线性规划线性规划LinearProgramming Page 55 来自来自中国最大的资料库下载中国最大的资料库下载极极点点(Extremepoint) 设设K是是凸凸集集，若若X不不能能用用K中两个不同的中两个不同的点点的凸组合表示为的凸组合表示为 )10()1 ()2()1( 0i表表1-4(1)XBx1x2x3x4bx3211040x4130130j3400(2)x3x2j(3)x1x2j基变量基变量11000
62、1/301/3105/31- -1/3405/30- -4/330103/5- -1/51801- -1/52/5400- -1- -1将将3化为化为1乘乘以以1/3后后得得到到1.5单纯形法单纯形法SimplexMethod30188/13/2024 制作与教学 线性规划线性规划LinearProgramming Page 64 来自来自中国最大的资料库下载中国最大的资料库下载最优解最优解X=(18，4，0，0)T，最优值，最优值Z=70O20301040(3,4)X(3)=(18,4)最优解最优解X=(18,4)最优值最优值Z=70X(1)=(0,0)2010x2x1301.5单纯形法单纯
63、形法SimplexMethodX(2)=(0,10)8/13/2024 制作与教学 线性规划线性规划LinearProgramming Page 65 来自来自中国最大的资料库下载中国最大的资料库下载单单纯纯形形法法全全过过程程的的计计算算，可可以以用用列列表表的的方方法法计计算算更更为为简简洁洁，这种表格称为单纯形表（表这种表格称为单纯形表（表1.4）。）。计算步骤：计算步骤：1.求初始基可行解，列出初始单纯形表，求出检验数。其中求初始基可行解，列出初始单纯形表，求出检验数。其中基变量的检验数必为零；基变量的检验数必为零；2.判断：判断：（a）若）若j（j，n）得到最解；）得到最解；（b）某
64、某个个k0且且aik（i=1，2,m）则则线线性性规规划划具具有有无无界解界解(见例见例1.18)。（c）若存在）若存在k0且且aik(i=1,m)不全非正，则进行换基；不全非正，则进行换基；1.5单纯形法单纯形法SimplexMethod8/13/2024 制作与教学 线性规划线性规划LinearProgramming Page 66 来自来自中国最大的资料库下载中国最大的资料库下载第第个个比比值值最最小小，选选最最小小比比值值对对应应行行的的基基变变量量为为出出基基变变量量，若若有相同最小比值，则任选一个。有相同最小比值，则任选一个。aLk为主元素；为主元素；(c）求求新新的的基基可可行行
65、解解：用用初初等等行行变变换换方方法法将将aLk化化为为,k列列其其它它元元素素化化为为零零（包包括括检检验验数数行行）得得到到新新的的可可行行基基及及基基本本可可行解，再判断是否得到最优解。行解，再判断是否得到最优解。（b）选出基变量）选出基变量，求最小比值：，求最小比值：1.5单纯形法单纯形法SimplexMethod3.换基：换基：（a）选进基变量）选进基变量设设k=maxj|j0,xk为进基变量为进基变量8/13/2024 制作与教学 线性规划线性规划LinearProgramming Page 67 来自来自中国最大的资料库下载中国最大的资料库下载【例【例1.16】用单纯形法求解用单
66、纯形法求解【解】将数学模型化为标准形式：【解】将数学模型化为标准形式：不难看出不难看出x4、x5可作为初始基变量，单纯法计算结果如表可作为初始基变量，单纯法计算结果如表1.所示所示。1.5单纯形法单纯形法SimplexMethod8/13/2024 制作与教学 线性规划线性规划LinearProgramming Page 68 来自来自中国最大的资料库下载中国最大的资料库下载Cj12100bCBXBx1x2x3x4x50x423210150x51/3150120j121000x42x2j1x12x2j表表151/3150120301713751/30902M2025601017/31/3125
67、0128/91/92/335/30098/91/97/3最优解最优解X=(25，35/3，0，0，0)T，最优值，最优值Z=145/31.5单纯形法单纯形法SimplexMethod8/13/2024 制作与教学 线性规划线性规划LinearProgramming Page 69 来自来自中国最大的资料库下载中国最大的资料库下载【例【例1.17】用单纯形法求解】用单纯形法求解 【解】【解】这是一个极小化的线性规划问题这是一个极小化的线性规划问题,可以将其化为极大化问题可以将其化为极大化问题求解求解,也可以直接求解也可以直接求解,这时判断标准是：这时判断标准是：j0(j=1，n)时得到时得到最优
68、解最优解。容易观察到容易观察到,系数矩阵中有一个系数矩阵中有一个3阶单位矩阵阶单位矩阵,x3、x4、x5为基变量。为基变量。目标函数中含有基变量目标函数中含有基变量x4,由第二个约束得到由第二个约束得到x4=6+x1x2，并代入，并代入目标函数消去目标函数消去x4得得1.5单纯形法单纯形法SimplexMethod8/13/2024 制作与教学 线性规划线性规划LinearProgramming Page 70 来自来自中国最大的资料库下载中国最大的资料库下载XBx1x2x3x4x5bx3x4x51- -1611210001000156215621/2j1- -1000x2x4x51- -24
69、1001- -1- -20100015111j20100表中表中j0,j=1,2,5所以最优解为所以最优解为X=(0,5,0,1,11,)最优值最优值Z=2x12x2x4=251=11极小值问题极小值问题,注意判断标准注意判断标准,选进基变量时选进基变量时,应选应选j0,x2进进基基，而而a120，a220且且aik（i=1，2,m）则线）则线性规划具有无界解性规划具有无界解退化基本可行解的判断退化基本可行解的判断:存在某个基变量为零的基本可存在某个基变量为零的基本可行解。行解。1.5单纯形法单纯形法SimplexMethod8/13/2024 制作与教学 线性规划线性规划LinearProg
70、ramming Page 77 来自来自中国最大的资料库下载中国最大的资料库下载在在实实际际问问题题中中有有些些模模型型并并不不含含有有单单位位矩矩阵阵，为为了了得得到到一一组组基基向向量量和和初初基基可可行行解解，在在约约束束条条件件的的等等式式左左端端加加一一组组虚虚拟拟变变量量，得得到到一一组组基基变变量量。这这种种人人为为加加的的变变量量称称为为人人工工变变量量，构构成成的的可可行行基基称称为为人人工工基基，用用大大M法法或或两两阶阶段段法法求求解解，这这种种用用人人工工变变量量作作桥梁的求解方法称为人工变量法。桥梁的求解方法称为人工变量法。【例【例1.20】用大】用大M法解法解下列线
71、性规划下列线性规划1.大大M单纯形法单纯形法1.5.2大大M和两阶段单纯形法和两阶段单纯形法1.5单纯形法单纯形法SimplexMethod8/13/2024 制作与教学 线性规划线性规划LinearProgramming Page 78 来自来自中国最大的资料库下载中国最大的资料库下载【解】首先将数学模型化为标准形式【解】首先将数学模型化为标准形式式式中中x4，x5为为松松弛弛变变量量，x5可可作作为为一一个个基基变变量量，第第一一、三三约约束束中中分分别别加加入入人人工工变变量量x6、x7，目目标标函函数数中中加加入入Mx6Mx7一一项项，得得到到人人工工变量单纯形法数学模型变量单纯形法数
72、学模型用前面介绍的单纯形法求用前面介绍的单纯形法求解，见下表。解，见下表。1.5单纯形法单纯形法SimplexMethod8/13/2024C Cj j3 32 21 10 00 0MMMMb bC CB BX XB Bx x1 1x x2 2x x3 3x x4 4x x5 5x x6 6x x7 7MM0 0MMx x6 6x x5 5x x7 74 41 12 23 31 12 21 12 2111 10 00 00 01 10 01 10 00 00 00 01 14 4101011 j j3-2M3-2M2+M2+M-1+2M-1+2MMM0 00 00 0MM0 01 1x x6
73、6x x5 5x x3 36 63 32 2553 32 20 00 01 11 10 00 00 01 10 01 10 00 0338 81 1 j j5-6M5-6M5M5M0 0MM0 00 02 20 01 1x x2 2x x5 5x x3 36/56/53/53/52/52/51 10 00 00 00 01 11/51/53/53/52/52/50 01 10 03/53/531/531/511/511/5 j j550 00 00 00 02 23 31 1x x2 2x x1 1x x3 30 01 10 01 10 00 00 00 01 11 11 10 02 25/3
74、5/32/32/3131331/331/319/319/3 j j0 00 00 05 5-25/3-25/38/13/2024 制作与教学 线性规划线性规划LinearProgramming Page 80 来自来自中国最大的资料库下载中国最大的资料库下载（1）初初始始表表中中的的检检验验数数有有两两种种算算法法，第第一一种种算算法法是是利利用用第第一一、三三约约束束将将x6、x7的的表表达达式式代代入入目目标标涵涵数数消消去去x6和和x7，得得到到用用非非基基变变量量表表达达的的目目标标函函数数，其其系系数数就就是是检检验验数数；第第二二种种算算法法是是利利用用公式计算，如公式计算，如（2
75、）M是是一一个个很很大大的的抽抽象象的的数数，不不需需要要给给出出具具体体的的数数值值，可可以以理解为它能大于给定的任何一个确定数值；理解为它能大于给定的任何一个确定数值；最优解最优解X（31/3，13，19/3，0，0)T；最优值；最优值Z152/3注意：注意：1.5单纯形法单纯形法SimplexMethod8/13/2024 制作与教学 线性规划线性规划LinearProgramming Page 81 来自来自中国最大的资料库下载中国最大的资料库下载【例【例1.21】求解线性规划】求解线性规划【解】加入松驰变量【解】加入松驰变量x3、x4化为标准型化为标准型在第二个方程中加入人工变量在第
76、二个方程中加入人工变量x5，目标函数中加上，目标函数中加上Mx5一项，一项，得到得到1.5单纯形法单纯形法SimplexMethod8/13/2024 制作与教学 线性规划线性规划LinearProgramming Page 82 来自来自中国最大的资料库下载中国最大的资料库下载用单纯形法计算如下表所示。用单纯形法计算如下表所示。Cj5800MbCBXBx1x2x3x4x50Mx3x5311210010164j5M8+2M0M05Mx1x5101/37/31/31/3010122j029/3+7/3M5/3+1/3MM01.5单纯形法单纯形法SimplexMethod8/13/2024 制作与
77、教学 线性规划线性规划LinearProgramming Page 83 来自来自中国最大的资料库下载中国最大的资料库下载表表中中j0，j=1，2，5，从从而而得得到到最最优优解解X=（2，0，0，0，2），Z=10+2M。但但最最优优解解中中含含有有人人工工变变量量x50说说明明这这个个解解是伪最优解，是不可行的，因此原问题无可行解。是伪最优解，是不可行的，因此原问题无可行解。两阶段单纯形法与大两阶段单纯形法与大M单纯形法的目的类似，将人工变量从基单纯形法的目的类似，将人工变量从基变量中换出，以求出原问题的初始基本可行解。将问题分成两变量中换出，以求出原问题的初始基本可行解。将问题分成两个阶
78、段求解，第一阶段的目标函数个阶段求解，第一阶段的目标函数是是约束条件是加入人工变量后的约束方程，当第一阶段的最优解约束条件是加入人工变量后的约束方程，当第一阶段的最优解中没有人工变量作基变量时，得到原线性规划的一个基本可行中没有人工变量作基变量时，得到原线性规划的一个基本可行解，第二阶段就以此为基础对原目标函数求最优解。解，第二阶段就以此为基础对原目标函数求最优解。当第一阶当第一阶段的最优解段的最优解w0时，说明还有不为零的人工变量是基变量，则原时，说明还有不为零的人工变量是基变量，则原问题无可行解。问题无可行解。1.5单纯形法单纯形法SimplexMethod2.两阶段单纯形法两阶段单纯形法
79、8/13/2024 制作与教学 线性规划线性规划LinearProgramming Page 84 来自来自中国最大的资料库下载中国最大的资料库下载【例【例1.22】用两阶段单纯形法求解例】用两阶段单纯形法求解例19的线性规划。的线性规划。【解】标准型为【解】标准型为在第一、三约束方程中加入人工变量在第一、三约束方程中加入人工变量x6、x7后，第一阶段问题为后，第一阶段问题为用单纯形法求解，得到第一阶段问题的计算表如下：用单纯形法求解，得到第一阶段问题的计算表如下：1.5单纯形法单纯形法SimplexMethod8/13/2024 制作与教学 线性规划线性规划LinearProgramming
80、 Page 85 来自来自中国最大的资料库下载中国最大的资料库下载Cj0000011bCBXBx1x2x3x4x5x6x7101x6x5x74123121211000101000014101j2121000100x6x5x3632532001100010100381j650100000x2x5x36/53/52/51000011/53/52/50103/531/511/5j000001.5单纯形法单纯形法SimplexMethod8/13/2024 制作与教学 线性规划线性规划LinearProgramming Page 86 来自来自中国最大的资料库下载中国最大的资料库下载最最优优解解为为最
81、最优优值值w=0。第第一一阶阶段段最最后后一一张张最最优优表表说说明明找找到到了了原原问问题题的的一一组组基基可可行行解解，将将它它作作为为初初始始基基可可行行解解，求求原问题的最优解，即第二阶段问题为原问题的最优解，即第二阶段问题为1.5单纯形法单纯形法SimplexMethod8/13/2024 制作与教学 线性规划线性规划LinearProgramming Page 87 来自来自中国最大的资料库下载中国最大的资料库下载Cj32-100bCBXBx1x2x3x4x5201x2x5x3100001010j50000231x2x1x3010100001110213j0005Cj32100bC
82、BXBx1x2x3x4x5201x2x5x36/53/52/51000011/53/52/50103/531/511/5j50000231x2x1x301010000111025/32/31331/319/3j000525/3用单纯形法计算得到下表用单纯形法计算得到下表最优解最优解X（31/3，13，19/3，0，0)T；最优值；最优值Z152/31.5单纯形法单纯形法SimplexMethod8/13/2024 制作与教学 线性规划线性规划LinearProgramming Page 88 来自来自中国最大的资料库下载中国最大的资料库下载【例【例1.23】用两阶段法求解例】用两阶段法求解例1
83、.21的线性规划。的线性规划。【解】例【解】例1.21的第一阶段问题为的第一阶段问题为用单纯形法计算如下表：用单纯形法计算如下表：1.5单纯形法单纯形法SimplexMethod8/13/2024 制作与教学 线性规划线性规划LinearProgramming Page 89 来自来自中国最大的资料库下载中国最大的资料库下载Cj00001bCBXBx1x2x3x4x501x3x5311210010164j1201001x1x5101/37/31/31/3010122j07/31/310j0,得到第一阶段的最优解得到第一阶段的最优解X=(2,0,0,0,2)T,最优目标值最优目标值w=20,x5
84、仍在基变量中仍在基变量中,从而原问题无可行解。从而原问题无可行解。1.5单纯形法单纯形法SimplexMethod8/13/2024 制作与教学 线性规划线性规划LinearProgramming Page 90 来自来自中国最大的资料库下载中国最大的资料库下载解的判断解的判断唯一最优解的判断唯一最优解的判断：最优表中所有非基变量的检验数非零：最优表中所有非基变量的检验数非零,则线则线规划具有唯一最优解规划具有唯一最优解多重最优解的判断多重最优解的判断:最优表中存在非基变量的检验数为零最优表中存在非基变量的检验数为零,则则线则性规划具有多重最优解。线则性规划具有多重最优解。无无界界解解的的判判
85、断断:某某个个k0且且aik（i=1，2,m）则则线线性性规规划具有无界解划具有无界解退化基本可行解的判断退化基本可行解的判断:存在某个基变量为零的基本可行解。存在某个基变量为零的基本可行解。无无可可行行解解的的判判断断：(1)当当用用大大M单单纯纯形形法法计计算算得得到到最最优优解解并并且存在且存在Ri0时，则表明原线性规划无可行解。时，则表明原线性规划无可行解。(2)当第一阶段的最优值当第一阶段的最优值w0时，则原问题无可行解时，则原问题无可行解。1.5单纯形法单纯形法SimplexMethod8/13/2024 制作与教学 线性规划线性规划LinearProgramming Page 9
86、1 来自来自中国最大的资料库下载中国最大的资料库下载设有线性规划设有线性规划其中其中Amn且且r(A)=m,X0应理解为应理解为X大于等于零向量，即大于等于零向量，即xj0,j=1,2,n。1.5.3计算公式计算公式1.5单纯形法单纯形法SimplexMethod8/13/2024 制作与教学 线性规划线性规划LinearProgramming Page 92 来自来自中国最大的资料库下载中国最大的资料库下载不不妨妨假假设设A（P1，P2，Pn）中中前前m个个列列向向量量构构成成一一个个可可行行基基，记记为为B=(P1，P2，Pm)。矩矩阵阵A中中后后nm列列构构成成的的矩矩阵阵记记为为N（P
87、m+1,Pn）,则则A可可以以写写成成分分块块矩矩阵阵A=（B，N）。对对于于 基基 B， 基基 变变 量量 为为 XB=（ x1,x2， ， xm）T, 非非 基基 变变 量量 为为XN=(xm+1,xm+2,xn)T。则则X可表示成可表示成同理将同理将C写成分块矩阵写成分块矩阵C=（CB，CN），），CB=(C1,C2,Cm), CN=(Cm+1Cm+2，cn)则则AX=b可写成可写成1.5单纯形法单纯形法SimplexMethod8/13/2024 制作与教学 线性规划线性规划LinearProgramming Page 93 来自来自中国最大的资料库下载中国最大的资料库下载因为因为r（
88、B）=m（或（或|B|0）所以）所以B1存在，因此可有存在，因此可有令令非非基基变变量量XN=0，XB=B1b，由由B是是可可行行基基的的假假设设，则则得得到到基本可行解基本可行解X=(B1b，0)T将目标函数写成将目标函数写成1.5单纯形法单纯形法SimplexMethod8/13/2024 制作与教学 线性规划线性规划LinearProgramming Page 94 来自来自中国最大的资料库下载中国最大的资料库下载得到下列五个计算公式：得到下列五个计算公式：(令令XN=0) 1.5单纯形法单纯形法SimplexMethod8/13/2024 制作与教学 线性规划线性规划LinearPro
89、gramming Page 95 来自来自中国最大的资料库下载中国最大的资料库下载上上述述公公式式可可用用下下面面较较简简单单的的矩矩阵阵表表格格运运算算得得到到，设设初初始始矩矩阵阵单纯形表单纯形表1-15 将将B化化为为I（I为为m阶阶单单位位矩矩阵阵）,CB化化为为零零,即即求求基基本本可可行行解解和和检验数。用检验数。用B1左乘表中第二行左乘表中第二行,得到表得到表1-16X XB BX XN Nb bX XB BI IB B- -1 1N NB B- -1 1b bC Cj j-Z-Zj jC CB BC CN N0 0X XB BX XN Nb bX XB BB BN Nb bC
90、Cj j-Z-Zj jC CB BC CN N0 0表表115表表1161.5单纯形法单纯形法SimplexMethod8/13/2024 制作与教学 线性规划线性规划LinearProgramming Page 96 来自来自中国最大的资料库下载中国最大的资料库下载再将第二行左乘再将第二行左乘CB后加到第三行后加到第三行,得到得到XBZ0X XB BX XN Nb bX XB BI IB B- - - -1 1N NB B- - - -1 1 1 1b b C Cj j- -Z Zj j0 0C CN N- - - -C CB BB B1 1N NC CB BB B1 1b b表表1171.
91、5单纯形法单纯形法SimplexMethod8/13/2024 制作与教学 线性规划线性规划LinearProgramming Page 97 来自来自中国最大的资料库下载中国最大的资料库下载五个公式的应用五个公式的应用【例【例1.24】线性规划】线性规划已知可行基已知可行基求求(1)单纯形乘子单纯形乘子;(2)基可行解及目标值基可行解及目标值;(3)求求3;(4)B1是否是最优基是否是最优基,为什么为什么;(5)当可行基为当可行基为时求时求1及及3。1.5单纯形法单纯形法SimplexMethod8/13/2024 制作与教学 线性规划线性规划LinearProgramming Page 9
92、8 来自来自中国最大的资料库下载中国最大的资料库下载【解解】(1)因因为为B1由由A中中第第一一列列、第第二二列列组组成成,故故x1、x2为为基基变变量量，x3、x4、x5为非基变量为非基变量,有关矩阵为有关矩阵为CB=(c1,c2)=(1,2)CN=(c3,c4,c5)=(1,0,0)故单纯形乘子故单纯形乘子1.5单纯形法单纯形法SimplexMethod8/13/2024 制作与教学 线性规划线性规划LinearProgramming Page 99 来自来自中国最大的资料库下载中国最大的资料库下载(2)基变量的解为基变量的解为故基本可行解为故基本可行解为目标函数值为目标函数值为1.5单纯
93、形法单纯形法SimplexMethod8/13/2024 制作与教学 线性规划线性规划LinearProgramming Page 100 来自来自中国最大的资料库下载中国最大的资料库下载(3)求求31.5单纯形法单纯形法SimplexMethod8/13/2024 制作与教学 线性规划线性规划LinearProgramming Page 101 来自来自中国最大的资料库下载中国最大的资料库下载(4)要判断要判断B1是不是最优基是不是最优基,亦是要求出所有检验数则否满亦是要求出所有检验数则否满足足j0,j=1,5。x1,x2是基变量是基变量,故故1=0,2=0,而而剩下来求剩下来求4,5，由，
94、由N计算公式得计算公式得因因j0,j=1,5,故故B1是最优基。是最优基。1.5单纯形法单纯形法SimplexMethod8/13/2024 制作与教学 线性规划线性规划LinearProgramming Page 102 来自来自中国最大的资料库下载中国最大的资料库下载(5)因因B2是是A中中第第四四列列与与第第二二列列组组成成的的,x4、x2是是基基变变量量x1、x3、x5是非基变量是非基变量,这时有这时有即即1.5单纯形法单纯形法SimplexMethod8/13/2024 制作与教学 线性规划线性规划LinearProgramming Page 103 来自来自中国最大的资料库下载中国
95、最大的资料库下载【例【例1.26】求解线性规划】求解线性规划解解用大用大M单纯形法，加入人工变量单纯形法，加入人工变量x4、x5，构造数学模型，构造数学模型1.5.4退化与循环退化与循环1.5单纯形法单纯形法SimplexMethod8/13/2024 制作与教学 线性规划线性规划LinearProgramming Page 104 来自来自中国最大的资料库下载中国最大的资料库下载C Cj j1 12 21 1MMMMb b C CB BX XB Bx x1 1x x2 2x x3 3x x4 4x x5 5(1)(1)MMMMx x4 4x x5 51 14 42 29 94414141 1
96、0 00 01 14416161 18/78/7 j j1 15M5M2+11M2+11M1 118M18M0 00 0(2)(2)1 1MMx x3 3x x5 51/41/41/21/21/21/22 21 10 01/41/47/27/20 01 1112 24 44 4 j j3/43/41/2M1/2M5/2+2M5/2+2M0 01/4+9/2M1/4+9/2M0 0(3)(3)1 1MMx x1 1x x5 51 10 02 2 114 42 21 14 40 01 14 400 j j0 04+M4+M3+2M3+2M1+5M1+5M0 0(4)(4)1 12 2x x1 1x
97、 x2 21 10 00 01 18 8229 94 42 21 14 400 j j0 00 01111MM1717MM4 4(5)(5)1 11 1x x1 1x x3 31 10 04 41/21/20 01 11 12 22 21/21/24 40 0 j j0 015/215/20 0MM1717MM3/23/2表表1181.5单纯形法单纯形法SimplexMethod8/13/2024 制作与教学 线性规划线性规划LinearProgramming Page 105 来自来自中国最大的资料库下载中国最大的资料库下载单纯形法迭代对于大多数退化解时是有效的，很少出现不收敛单纯形法迭代对
98、于大多数退化解时是有效的，很少出现不收敛的情形的情形1955年年Beale提出了一个用单纯形法计算失效的模型提出了一个用单纯形法计算失效的模型加入松弛变量后用单纯形法计算并且按字典序方法（按变量下加入松弛变量后用单纯形法计算并且按字典序方法（按变量下标顺序）选进基变量，迭代标顺序）选进基变量，迭代6次后又回到初始表，继续迭代出现次后又回到初始表，继续迭代出现了无穷的循环，永远得不到最优解但该模型的最优解为了无穷的循环，永远得不到最优解但该模型的最优解为X(1，0，1，0)T，Z5/41.5单纯形法单纯形法SimplexMethod8/13/2024 制作与教学 线性规划线性规划LinearPr
99、ogramming Page 106 来自来自中国最大的资料库下载中国最大的资料库下载1.5单纯形法单纯形法SimplexMethod1.将问题化为标准型，寻找一个初始可行基，化为典式，列出初将问题化为标准型，寻找一个初始可行基，化为典式，列出初始单纯性表；始单纯性表；2.判断基本可行解。有判断基本可行解。有3种情形：种情形：已是最优解，已是最优解，是无界解，是无界解，不能确定。不能确定。前前2种情形计算结束，第种情形计算结束，第3种情形需要继续迭代，先进基后出种情形需要继续迭代，先进基后出基，初等变换求下一个基本可行解，直到出现最优解或无界解为基，初等变换求下一个基本可行解，直到出现最优解或
100、无界解为止。止。3.人工变量是过度变量，当原问题有可行解时，人工变量最终会人工变量是过度变量，当原问题有可行解时，人工变量最终会退出基变量。如果原问题没有可行解，人工变量就不会退出基退出基变量。如果原问题没有可行解，人工变量就不会退出基变量。变量。4.处理人工变量的方法有两种，无论哪一种结果都是一样。处理人工变量的方法有两种，无论哪一种结果都是一样。8/13/2024 制作与教学 线性规划线性规划LinearProgramming Page 107 来自来自中国最大的资料库下载中国最大的资料库下载TheEndofChapter1作业：作业：P35T10175.本节的本节的5个公式是单纯形法的基
101、本公式个公式是单纯形法的基本公式6.只要已知基矩阵，利用公式就能计算我们所需要的结果只要已知基矩阵，利用公式就能计算我们所需要的结果7.应用公式时注意数据的来源，即给定基矩阵应用公式时注意数据的来源，即给定基矩阵B和和C CB B、C CN N、N N、b b都都是标准型的数据，而是标准型的数据，而、Z Z0 0、 是通过公式计算的结果。是通过公式计算的结果。1.5单纯形法单纯形法SimplexMethod8/13/2024部分习题答案部分习题答案8/13/2024 制作与教学 线性规划线性规划LinearProgramming Page 109 来自来自中国最大的资料库下载中国最大的资料库下载习题习题1.7(5)(1)(2)(3)8/13/2024 制作与教学 线性规划线性规划LinearProgramming Page 110 来自来自中国最大的资料库下载中国最大的资料库下载习题习题1.7(6)(1)(2)(3)8/13/2024
