数据、模型与决策--线性规划.pptx

《数据、模型与决策--线性规划.pptx》由会员分享，可在线阅读，更多相关《数据、模型与决策--线性规划.pptx（110页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、数据、模型与决策数据、模型与决策线性规划线性规划LinearProgramming1.1 LP的数学模型的数学模型MathematicalModelofLP1.2 图解法图解法 GraphicalMethod1.3 标准型标准型 StandardformofLP1.4 基本概念基本概念BasicConcepts1.5 单纯形法单纯形法SimplexMethod4/1/20231.1数学模型数学模型MathematicalModel4/1/2023 制作与教学 线性规划线性规划LinearProgramming Page 3 1.1线性规划的数学模型线性规划的数学模型MathematicalMo

2、delofLP线性规划通常研究资源的最优利用、设备最佳运行等问线性规划通常研究资源的最优利用、设备最佳运行等问题。例如，当任务或目标确定后，如何统筹兼顾，合理安题。例如，当任务或目标确定后，如何统筹兼顾，合理安排，用最少的资源排，用最少的资源（如资金、设备、原标材料、人工、时（如资金、设备、原标材料、人工、时间等）去完成确定的任务或目标；企业在一定的资源条件间等）去完成确定的任务或目标；企业在一定的资源条件限制下，如何组织安排生产获得最好的经济效益（如产品限制下，如何组织安排生产获得最好的经济效益（如产品量最多量最多、利润最大）。、利润最大）。线性规划线性规划（Linear Programmi

3、ng,缩写为LP）是运筹学的重要是运筹学的重要分支之一，在实际中应用得较广泛，其方法也较成熟，借助分支之一，在实际中应用得较广泛，其方法也较成熟，借助计算机，使得计算更方便，应用领域更广泛和深入。计算机，使得计算更方便，应用领域更广泛和深入。4/1/2023 制作与教学 线性规划线性规划LinearProgramming Page 4【例例1.1】最最优优生生产产计计划划问问题题。某某企企业业在在计计划划期期内内计计划划生生产产甲甲、乙乙、丙丙三三种种产产品品。这这些些产产品品分分别别需需要要要要在在设设备备A、B上上加加工工，需需要要消消耗耗材材料料C、D，按按工工艺艺资资料料规规定定，单单

4、件件产产品品在在不不同同设设备备上上加加工工及及所所需需要要的的资资源源如如表表1.1所所示示。已已知知在在计计划划期期内内设设备备的的加加工工能能力力各各为为200台台时时，可可供供材材料料分分别别为为360、300公公斤斤；每每生生产产一一件件甲甲、乙乙、丙丙三三种种产产品品，企企业业可可获获得得利利润润分分别别为为40、30、50元元，假假定定市市场场需需求求无无限限制制。企企业业决决策策者者应应如如何何安安排排生生产产计计划划，使使企企业业在在计划期内总的利润收入最大？计划期内总的利润收入最大？1.1线性规划的数学模型线性规划的数学模型MathematicalModelofLP1.1.

5、1应用模型举例应用模型举例4/1/2023 制作与教学 线性规划线性规划LinearProgramming Page 5 产品产品产品产品 资源资源资源资源 甲甲甲甲 乙乙乙乙 丙丙丙丙现有资源现有资源现有资源现有资源设备设备设备设备A A331122200200设备设备设备设备B B222244200200材料材料材料材料C C445511360360材料材料材料材料D D223355300300利润（元利润（元利润（元利润（元/件）件）件）件）404030305050表表1.1产品资源消耗产品资源消耗1.1线性规划的数学模型线性规划的数学模型MathematicalModelofLP4/1

6、/2023 制作与教学 线性规划线性规划LinearProgramming Page 6【解】设【解】设x1、x2、x3分别为甲、乙、丙三种产品的产量数学模型分别为甲、乙、丙三种产品的产量数学模型为：为：1.1线性规划的数学模型线性规划的数学模型MathematicalModelofLP产品产品产品产品 资源资源资源资源 甲甲甲甲 乙乙乙乙 丙丙丙丙现有资现有资现有资现有资源源源源设备设备设备设备A A331122200200设备设备设备设备B B222244200200材料材料材料材料C C445511360360材料材料材料材料D D223355300300利润（元利润（元利润（元利润（元

7、/件）件）件）件）404030305050最优解最优解X=(50,30,10);Z=34004/1/2023 制作与教学 线性规划线性规划LinearProgramming Page 7 线性规划的数学模型由线性规划的数学模型由决策变量决策变量Decisionvariables 目标函数目标函数Objectivefunction及约束条件及约束条件Constraints构成。称为三个要素构成。称为三个要素。n其特征是：其特征是：n1解决问题的目标函数是多个决策变量的解决问题的目标函数是多个决策变量的线性函数，通常是求最大值或线性函数，通常是求最大值或最小值；最小值；n2解决问题的解决问题的约束

8、条件约束条件约束条件约束条件是一组多个决策变量是一组多个决策变量的线性不等式或等式。的线性不等式或等式。怎样辨别一个模型是线性规划模型？怎样辨别一个模型是线性规划模型？1.1线性规划的数学模型线性规划的数学模型MathematicalModelofLP4/1/2023 制作与教学 线性规划线性规划LinearProgramming Page 8【例例1.2】某某商商场场决决定定：营营业业员员每每周周连连续续工工作作5天天后后连连续续休休息息2天天，轮流休息。根据统计，商场每天需要的营业员如表轮流休息。根据统计，商场每天需要的营业员如表1.2所示。所示。表表1.2营业员需要量统计表营业员需要量统

9、计表商场人力资源部应如何安排每天的上班人数，使商场总的营业员商场人力资源部应如何安排每天的上班人数，使商场总的营业员最少。最少。星期星期星期星期需要人数需要人数需要人数需要人数星期星期星期星期需要人数需要人数需要人数需要人数一一一一300300五五五五480480二二二二300300六六六六600600三三三三350350日日日日550550四四四四4004001.1线性规划的数学模型线性规划的数学模型MathematicalModelofLP4/1/2023 制作与教学 线性规划线性规划LinearProgramming Page 9【解】【解】设设xj(j=1，2，7)为休息为休息2天后星

10、期一到星期日开始上天后星期一到星期日开始上班的营业员，则这个问题的线性规划模型为班的营业员，则这个问题的线性规划模型为1.1线性规划的数学模型线性规划的数学模型MathematicalModelofLP星星星星期期期期需要需要需要需要人数人数人数人数星星星星期期期期需要需要需要需要人数人数人数人数一一一一300300五五五五480480二二二二300300六六六六600600三三三三350350日日日日550550四四四四4004004/1/2023 制作与教学 线性规划线性规划LinearProgramming Page 10 1 1 1 1 X1X1X1X10 0 0 0 C1C1C1C1

11、404404404404=3003003003001041041041042 2 2 2 X2X2X2X267676767 C2C2C2C2301301301301=3003003003001 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

12、0 0 06 6 6 6 X6X6X6X6120120120120 C6C6C6C6600600600600=6006006006000 0 0 07 7 7 7 X7X7X7X717171717 C7C7C7C7550550550550=5505505505500 0 0 0最优解：最优解：Z617（人）（人）4/1/2023 制作与教学 线性规划线性规划LinearProgramming Page 11【例【例1.3】合理用料问题。某汽车需要用甲、乙、丙三种规格的轴各一根，这些】合理用料问题。某汽车需要用甲、乙、丙三种规格的轴各一根，这些轴的规格分别是轴的规格分别是1.5，1，0.7（m）

13、，这些轴需要用同一种圆钢来做，圆钢长度），这些轴需要用同一种圆钢来做，圆钢长度为为4m。现在要制造。现在要制造1000辆汽车，最少要用多少圆钢来生产这些轴？辆汽车，最少要用多少圆钢来生产这些轴？【解】这是一个条材下料问题【解】这是一个条材下料问题，设切口宽度为零。，设切口宽度为零。设一根圆钢切割成甲、设一根圆钢切割成甲、乙、丙三种轴的根数分别为乙、丙三种轴的根数分别为y1，y2，y3,则切割方式可用不等式则切割方式可用不等式1.5y1+y2+0.7y34表示，求这个不等式关于表示，求这个不等式关于y1，y2，y3的非负整数解。象这样的非负整数解。象这样的非负整数解共有的非负整数解共有10组，也

14、就是有组，也就是有10种下料方式，如表种下料方式，如表1.3所示。所示。表表13下料方案下料方案方案方案方案方案规格规格规格规格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.5

15、1.1线性规划的数学模型线性规划的数学模型MathematicalModelofLP4/1/2023 制作与教学 线性规划线性规划LinearProgramming Page 12 设设xj(j=1,2,10)为为第第j种种下下料料方方案案所所用用圆圆钢钢的的根根数数。则则用用料料最最少数学模型少数学模型为为为为:求下料方案时应注意，余料不能超过最短毛坯的长度；最好将毛求下料方案时应注意，余料不能超过最短毛坯的长度；最好将毛坯长度按降的次序排列，即先切割长度最长的毛坯，再切割次长坯长度按降的次序排列，即先切割长度最长的毛坯，再切割次长的，最后切割最短的，不能遗漏了方案的，最后切割最短的，不能遗

16、漏了方案。如果方案较多，用计算。如果方案较多，用计算机编程排方案，去掉余料较长的方案，进行初选。机编程排方案，去掉余料较长的方案，进行初选。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 51

17、0001000余料（余料（余料（余料（mm）0 00.30.30.50.50.10.1o.4o.40 00.30.30.60.60.20.20.50.54/1/2023 制作与教学 线性规划线性规划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 0

18、8 8 8 8 X8X8X8X80 0 0 09 9 9 9 X9X9X9X925025025025010101010 X10X10X10X100 0 0 0Z812.54/1/2023 制作与教学 线性规划线性规划LinearProgramming Page 14【例例1.4】配配料料问问题题。某某钢钢铁铁公公司司生生产产一一种种合合金金，要要求求的的成成分分规规格格是是：锡锡不不少少于于28%，锌锌不不多多于于15%，铅铅恰恰好好10%，镍镍要要界界于于35%55%之之间间，不不允允许许有有其其他他成成分分。钢钢铁铁公公司司拟拟从从五五种种不不同同级级别别的的矿矿石石中中进进行行冶冶炼炼，

19、每每种种矿矿物物的的成成分分含含量量和和价价格格如如表表1.4所所示示。矿矿石石杂杂质质在在治治炼炼过过程程中中废废弃弃，现现要要求求每每吨吨合合金金成成本本最最低低的的矿矿物物数数量量。假设矿石在冶炼过程中，合金含量没有发生变化。假设矿石在冶炼过程中，合金含量没有发生变化。表表1.4矿石的金属含量矿石的金属含量合金合金合金合金矿石矿石矿石矿石锡锡锡锡%锌锌锌锌%铅铅铅铅%镍镍镍镍%杂质杂质杂质杂质费用（元费用（元费用（元费用（元/t/t）1 1252510101010252530303403402 240400 00 0303030302602603 30 015155 5202060601

20、801804 4202020200 0404020202302305 58 85 51515171755551901901.1线性规划的数学模型线性规划的数学模型MathematicalModelofLP4/1/2023 制作与教学 线性规划线性规划LinearProgramming Page 15 解解:设设xj（j=1,2，5）是第）是第j种矿石数量，得到下列线性规划模种矿石数量，得到下列线性规划模型型注注意意，矿矿石石在在实实际际冶冶炼炼时时金金属属含含量量会会发发生生变变化化，建建模模时时应应将将这这种种变变化化考考虑虑进进去去，有有可可能能是是非非线线性性关关系系。配配料料问问题题也

21、也称称配配方方问问题题、营养问题或混合问题，在许多行业生产中都能遇到。营养问题或混合问题，在许多行业生产中都能遇到。1.1线性规划的数学模型线性规划的数学模型MathematicalModelofLP矿石矿石矿石矿石锡锡锡锡%锌锌锌锌%铅铅铅铅%镍镍镍镍%杂质杂质杂质杂质费用（元费用（元费用（元费用（元/t/t）1 1252510101010252530303403402 240400 00 0303030302602603 30 015155 5202060601801804 4202020200 0404020202302305 58 85 51515171755551901904/1/2

22、023 制作与教学 线性规划线性规划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.1线性规划的数学模型线性规划的数学模型MathematicalModelofLP4/1/2023 制作与教学 线性规划线性规划LinearProg

23、ramming Page 17【例例1.5】投投资资问问题题。某某投投资资公公司司在在第第一一年年有有200万万元元资资金金，每每年年都都有有如如下下的的投投资资方方案案可可供供考考虑虑采采纳纳：“假假使使第第一一年年投投入入一一笔笔资资金金，第第二二年年又又继继续续投投入入此此资资金金的的50%，那那么么到到第第三三年年就就可可回回收收第第一一年年投投入入资资金金的的一一倍倍金金额额”。投投资资公公司司决决定定最最优优的的投投资资策策略略使使第第六六年年所所掌掌握握的的资资金金最最多。多。第五年：第五年：(x7/2+x9)=x8+2x5第一年：第一年：x1+x2=200(万元万元)第二年：第

24、二年：(x1/2+x3)+x4=x2第三年第三年(x3/2+x5)+x6=x4+2x1第四年：第四年：(x5/2+x7)+x8=x6+2x3到第六年实有资金总额为到第六年实有资金总额为x9+2x7，整理后得到下列线性规划模型，整理后得到下列线性规划模型1.1线性规划的数学模型线性规划的数学模型MathematicalModelofLP【解】设【解】设x1：第一年的投资；：第一年的投资；x2：第一年的保留资金：第一年的保留资金x3：第二年新的投资；：第二年新的投资；x4：第二年的保留资金：第二年的保留资金x5：第三年新的投资；：第三年新的投资；x6：第三年的保留资金：第三年的保留资金x7：第四年

25、新的投资：第四年新的投资x8：第四年的保留资金：第四年的保留资金x9：第五年的保留资金：第五年的保留资金4/1/2023 制作与教学 线性规划线性规划LinearProgramming Page 18 1.1线性规划的数学模型线性规划的数学模型MathematicalModelofLP1 1 1 1 X1X1X1X155.284655.284655.284655.28462 2 2 2 X2X2X2X2144.7155144.7155144.7155144.71553 3 3 3 X3X3X3X3117.0732117.0732117.0732117.07324 4 4 4 X4X4X4X40

26、 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最优解：最优解：Z416.26万元万元x1：第一年的投资；：第一年的投资；x2：第一年的保留资金：第一年的保留资金x3：第二年新的投资；：第二年新的投资；x4：第二年的保留资金：第二年的保留资金x5：第三年新的投资；：第三年新的投资；x6：第三年的保留资金：第三年的

27、保留资金x7：第四年新的投资：第四年新的投资x8：第四年的保留资金：第四年的保留资金x9：第五年的保留资金：第五年的保留资金4/1/2023 制作与教学 线性规划线性规划LinearProgramming Page 19【例例1.6】均均衡衡配配套套生生产产问问题题。某某产产品品由由2件件甲甲、3件件乙乙零零件件组组装装而而成成。两两种种零零件件必必须须经经过过设设备备A、B上上加加工工，每每件件甲甲零零件件在在A、B上上的的加加工工时时间间分分别别为为5分分钟钟和和9分分钟钟，每每件件乙乙零零件件在在A、B上上的的加加工工时时间间分分别别为为4分分钟钟和和10分分钟钟。现现有有2台台设设备备

28、A和和3台台设设备备B，每每天天可可供供加加工工时时间间为为8小小时时。为为了了保保持持两两种种设设备备均均衡衡负负荷荷生生产产，要要求求一一种种设设备备每每天天的的加加工工总总时时间间不不超超过过另另一一种种设设备备总总时时间间1小小时时。怎怎样样安安排排设设备备的的加加工工时时间间使使每每天天产产品品的的产量最大。产量最大。【解】【解】设设x1、x2为每天加工甲、乙两种零件的件数，则产品的产量是为每天加工甲、乙两种零件的件数，则产品的产量是设备设备A、B每天加工工时的约束为每天加工工时的约束为要求一种设备每台每天的加工时间不超过另一种设备要求一种设备每台每天的加工时间不超过另一种设备1小时

29、的约束小时的约束为为1.1线性规划的数学模型线性规划的数学模型MathematicalModelofLP4/1/2023 制作与教学 线性规划线性规划LinearProgramming Page 20 目标函数线性化。产品的产量目标函数线性化。产品的产量y等价于等价于整理得到线性规划模型整理得到线性规划模型约束线性化。将绝对值约束写成两个不等式约束线性化。将绝对值约束写成两个不等式1.1线性规划的数学模型线性规划的数学模型MathematicalModelofLP4/1/2023 制作与教学 线性规划线性规划LinearProgramming Page 21 1.1.2线性规划的一般模型线性规

30、划的一般模型一一般般地地，假假设设线线性性规规划划数数学学模模型型中中，有有m个个约约束束，有有n个个决决策策变变量量xj,j=1,2,n，目目标标函函数数的的变变量量系系数数用用cj表表示示,cj称称为为价价值值系系数数。约约束束条条件件的的变变量量系系数数用用aij表表示示，aij称称为为工工艺艺系系数数。约约束束条条件件右右端端的的常常数数用用bi表表示示，bi称称为为资资源源限限量量。则则线线性性规规划划数数学学模模型型的的一一般般表表达达式可写成式可写成为了书写方便，上式也可写成：为了书写方便，上式也可写成：1.1线性规划的数学模型线性规划的数学模型MathematicalModel

31、ofLP4/1/2023 制作与教学 线性规划线性规划LinearProgramming Page 22 在实际中一般在实际中一般xj0,但有时但有时xj0或或xj无符号限制。无符号限制。1.1线性规划的数学模型线性规划的数学模型MathematicalModelofLP4/1/2023 制作与教学 线性规划线性规划LinearProgramming Page 23 1.什么是线性规划，掌握线性规划在管理中的什么是线性规划，掌握线性规划在管理中的几个应用例子几个应用例子2.线性规划数学模型的组成及其特征线性规划数学模型的组成及其特征3.线性规划数学模型的一般表达式。线性规划数学模型的一般表达式

32、。作业：教材作业：教材P31T2，3，4，5，61.1线性规划的数学模型线性规划的数学模型MathematicalModelofLP下一节：图解法下一节：图解法4/1/20231.2图解法图解法 GraphicalMethod4/1/2023 制作与教学 线性规划线性规划LinearProgramming Page 25 图解法的步骤：图解法的步骤：1.求可行解集合。求可行解集合。分别求出满足每个约束包括变量非分别求出满足每个约束包括变量非负要求的负要求的区域，其交集就是可行解集合，或称为区域，其交集就是可行解集合，或称为可行域可行域；2.绘制目标函数图形。绘制目标函数图形。先过原点作一条矢量

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

34、最小值时沿着矢量的反方向移动1.2图解法图解法TheGraphicalMethod4/1/2023 制作与教学 线性规划线性规划LinearProgramming Page 26 x1x2O1020304010203040(3,4)(15,10)最优解最优解X=(15,10)最优值最优值Z=85例例1.71.2图解法图解法TheGraphicalMethod4/1/2023 制作与教学 线性规划线性规划LinearProgramming Page 27 246x1x2246最优解最优解X=(3,1)最优值最优值Z=5(3,1)min Z=x1+2x2例例1.8(1,2)1.2图解法图解法The

35、GraphicalMethod4/1/2023 制作与教学 线性规划线性规划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图解法图解法TheGraphicalMethod4/1/2023 制作与教学 线性规划线性规划LinearProgramming Page 29 246x1x2246(1,2)无界解无界解(无最优解无最优解)

36、max Z=x1+2x2例例1.104/1/2023 制作与教学 线性规划线性规划LinearProgramming Page 30 x1x2O10203040102030405050无可行解无可行解即无最优解即无最优解max Z=10 x1+4x2例例1.111.2图解法图解法TheGraphicalMethod4/1/2023 制作与教学 线性规划线性规划LinearProgramming Page 31 由以上例题可知，线性规划的解有由以上例题可知，线性规划的解有4种形式种形式：1.有唯一最优解有唯一最优解(例例1.7例例1.8)2.有多重解有多重解(例例1.9)3.有无界解有无界解(例

37、例1.10)4.无可行解无可行解(例例1.11)1、2情形为有最优解情形为有最优解3、4情形为无最优解情形为无最优解1.2图解法图解法TheGraphicalMethod4/1/2023 制作与教学 线性规划线性规划LinearProgramming Page 32 1.通过图解法了解线性规划有几种解的形式通过图解法了解线性规划有几种解的形式2.作图的关键有三点作图的关键有三点(1)可行解区域要画正确可行解区域要画正确(2)目标函数增加的方向不能画错目标函数增加的方向不能画错(3)目标函数的直线怎样平行移动目标函数的直线怎样平行移动作业：教材作业：教材P34T71.2图解法图解法TheGrap

38、hicalMethod下一节：线性规划的标准型下一节：线性规划的标准型4/1/20231.3线性规划的标准型线性规划的标准型StandardformofLP4/1/2023 制作与教学 线性规划线性规划LinearProgramming Page 34 在用单纯法求解线性规划问题时，为了讨论问题在用单纯法求解线性规划问题时，为了讨论问题方便，需将线性规划模型化为统一的标准形式。方便，需将线性规划模型化为统一的标准形式。1.3线性规划的标准型线性规划的标准型StandardformofLP线性规划问题的标准型为线性规划问题的标准型为:1目标函数求最大值（或求最小值）目标函数求最大值（或求最小值）

39、2约束条件都为等式方程约束条件都为等式方程3变量变量xj非负非负4常数常数bi非负非负4/1/2023 制作与教学 线性规划线性规划LinearProgramming Page 35 max(或min)Z=c1x1+c2x2+cnxn1.3线性规划的标准型线性规划的标准型StandardformofLP注：本教材默认目标函数是注：本教材默认目标函数是max4/1/2023 制作与教学 线性规划线性规划LinearProgramming Page 36 或写成下列形式或写成下列形式：或用矩阵形式或用矩阵形式1.3线性规划的标准型线性规划的标准型StandardformofLP4/1/2023 制

40、作与教学 线性规划线性规划LinearProgramming Page 37 通常通常X记为：记为：称为约束方称为约束方程的系数矩阵，程的系数矩阵，m是约束方程的个数，是约束方程的个数，n是决策变量的个数，是决策变量的个数，一般情况一般情况mn，且，且r()m。其中其中:1.3线性规划的标准型线性规划的标准型StandardformofLP4/1/2023 制作与教学 线性规划线性规划LinearProgramming Page 38【例【例1.12】将下列线性规划化为标准型】将下列线性规划化为标准型【解】（）因为【解】（）因为x3无符号要求无符号要求，即，即x3取正值也取正值也可取负值，标准

41、型中要求变量非负，所以令可取负值，标准型中要求变量非负，所以令1.3线性规划的标准型线性规划的标准型StandardformofLP4/1/2023 制作与教学 线性规划线性规划LinearProgramming Page 39(3)第二个约束条件是第二个约束条件是号，在号，在号号左左端减去剩余变量端减去剩余变量(Surplusvariable)x5，x50。也称松驰变。也称松驰变量量1.3线性规划的标准型线性规划的标准型StandardformofLP(2)第一个约束条件是第一个约束条件是号，在号，在左左端加入松驰变量端加入松驰变量(slackvariable)x4，x40,化为等式；化为等

42、式；(4)第三个约束条件是第三个约束条件是号且常数项为负数，因此在号且常数项为负数，因此在左边加入左边加入松驰变量松驰变量x6，x60，同时两边乘以，同时两边乘以1。（5）目标函数是最小值，为了化为求最大值，令）目标函数是最小值，为了化为求最大值，令Z=Z,得到得到maxZ=Z，即当，即当Z达到最小值时达到最小值时Z达到最大值，反之亦然。达到最大值，反之亦然。4/1/2023 制作与教学 线性规划线性规划LinearProgramming Page 40 综合起来得到下列标准型综合起来得到下列标准型1.3线性规划的标准型线性规划的标准型StandardformofLP4/1/2023 制作与教

43、学 线性规划线性规划LinearProgramming Page 41 当某个变量当某个变量xj0时时,令令x/j=xj。当某个约束是绝对值不等式当某个约束是绝对值不等式时，将绝对值不等式化为两个不等式，再化为等式，例如约束时，将绝对值不等式化为两个不等式，再化为等式，例如约束将其化为两个不等式将其化为两个不等式再加入松驰变量化为等式。再加入松驰变量化为等式。1.3线性规划的标准型线性规划的标准型StandardformofLP4/1/2023 制作与教学 线性规划线性规划LinearProgramming Page 42【例例1.13】将下例线性规划化为标准型】将下例线性规划化为标准型【解】

44、解】此题关键是将目标函数中的绝对值去掉。此题关键是将目标函数中的绝对值去掉。令令则有则有1.3线性规划的标准型线性规划的标准型StandardformofLP4/1/2023 制作与教学 线性规划线性规划LinearProgramming Page 43 得到线性规划的标准形式得到线性规划的标准形式1.3线性规划的标准型线性规划的标准型StandardformofLP对于对于axb(a、b均大于零均大于零)的有界变量化为标准形式有两种方的有界变量化为标准形式有两种方法，一种方法是增加两个约束法，一种方法是增加两个约束xa及及xb，另一种方法是令，另一种方法是令=xa，则，则axb等价于等价于0

45、ba，增加一个约束，增加一个约束ba并且将原问并且将原问题所有题所有x用用x=+a替换。替换。4/1/2023 制作与教学 线性规划线性规划LinearProgramming Page 44 1.如何化标准形式？如何化标准形式？可以对照四条标准逐一判断！可以对照四条标准逐一判断！标准形式是人为定义的，目标函数可以是求最小值。标准形式是人为定义的，目标函数可以是求最小值。2.用用WinQSB软件求解时，不必化成标准型。软件求解时，不必化成标准型。图解法时不必化为标准型。图解法时不必化为标准型。3.单纯形法求解时一定要化为标准型。单纯形法求解时一定要化为标准型。作业：教材作业：教材P34T81.3

46、线性规划的标准型线性规划的标准型StandardformofLP下一节：基本概念下一节：基本概念4/1/20231.4线性规划的有关概念线性规划的有关概念BasicConceptsofLP4/1/2023 制作与教学 线性规划线性规划LinearProgramming Page 46 设线性规划的标准型设线性规划的标准型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

47、并且有并且有r（B）=m，则称，则称B是线性规是线性规划的一个基（或基矩阵划的一个基（或基矩阵basismatrix）。当）。当m=n时，基矩阵唯一，时，基矩阵唯一，当当mn时，基矩阵就可能有多个，但数目不超过时，基矩阵就可能有多个，但数目不超过4/1/2023 制作与教学 线性规划线性规划LinearProgramming Page 47【例【例1.14】线性规划】线性规划求所有基矩阵求所有基矩阵。【解】约束方程的系数矩阵为【解】约束方程的系数矩阵为25矩阵矩阵容易看出容易看出r(A)=2，2阶阶子矩子矩阵阵有有C52=10个，其中第个，其中第1列与第列与第3列构成列构成的的2阶矩阵不是一个

48、基，基矩阵只有阶矩阵不是一个基，基矩阵只有9个，即个，即1.4基本概念基本概念BasicConcepts4/1/2023 制作与教学 线性规划线性规划LinearProgramming Page 48 由线性代数知，基矩阵由线性代数知，基矩阵B必为非奇异矩阵并且必为非奇异矩阵并且|B|0。当矩阵。当矩阵B的行列式等式零即的行列式等式零即|B|=0时就不是基时就不是基当确定某一矩阵为基矩阵时，则基矩阵对应的列向量称为当确定某一矩阵为基矩阵时，则基矩阵对应的列向量称为基基向量向量(basisvector)，其余列向量称为，其余列向量称为非基向量非基向量基向量对应的变量称为基向量对应的变量称为基变量

49、基变量(basisvariable)，非基向，非基向量对应的变量称为量对应的变量称为非基变量非基变量在在上上例例中中B2的的基基向向量量是是A中中的的第第一一列列和和第第四四列列，其其余余列列向向量量是是非非基基向向量量，x1、x4是是基基变变量量，x2、x3、x5是是非非基基变变量量。基基变变量量、非非基基变变量量是是针针对对某某一一确确定定基基而而言言的的，不不同同的的基基对对应应的的基基变量和非基变量也不同。变量和非基变量也不同。1.4基本概念基本概念BasicConcepts4/1/2023 制作与教学 线性规划线性规划LinearProgramming Page 49 可行解可行解(

50、feasiblesolution)满足式（满足式（1.2）及（）及（1.3）的解）的解X=（x1,x2，xn)T称为可行解称为可行解。基基本本可可行行解解(basisfeasiblesolution)若若基基本本解解是是可可行行解解则则称称为是基本可行解（也称基可行解）。为是基本可行解（也称基可行解）。例如，例如，与与X=（0，0，0，3，2，）都是例，）都是例1的可行解。的可行解。基本解基本解(basissolution)对某一确定的基对某一确定的基B，令非基变量等于零，令非基变量等于零，利用式（利用式（1.）解出基变量，则这组解称为基解出基变量，则这组解称为基的基的基本解。本解。最最优优解