大学精品课件：Ch1线性规划.ppt

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 Programming Page 3 2023年年3月月1日

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

3、产获得最好的经济效益（如产品量最多产获得最好的经济效益（如产品量最多、利润最大）。、利润最大）。Chapter 1 线性规划线性规划Linear Programming Page 4 2023年年3月月1日星期三日星期三【例例1-1】生产计划问题。某企业在计划期内计划生产甲、乙两生产计划问题。某企业在计划期内计划生产甲、乙两种产品。按工艺资料规定，每件产品甲需要消耗材料种产品。按工艺资料规定，每件产品甲需要消耗材料A 2公斤，公斤，消耗材料消耗材料B 1公斤，每件产品乙需要消耗材料公斤，每件产品乙需要消耗材料A 1公斤，消耗材公斤，消耗材料料B 1.5公斤。已知在计划期内可供材料分别为公斤。已

4、知在计划期内可供材料分别为40、30公斤；每公斤；每生产一件甲、乙两产品，企业可获得利润分别为生产一件甲、乙两产品，企业可获得利润分别为40、30元，如元，如表表11所示。假定市场需求无限制。企业决策者应如何安排生所示。假定市场需求无限制。企业决策者应如何安排生产计划，使企业在计划期内总的利润收入最大。产计划，使企业在计划期内总的利润收入最大。1.1 线性规划的数学模型线性规划的数学模型 Mathematical Model of LP1.1.1 应用模型举例应用模型举例Chapter 1 线性规划线性规划Linear Programming Page 5 产品产品 资源资源 甲甲 乙乙现有资

5、现有资源源材料材料C材料材料D利润（元利润（元/件）件）2023年年3月月1日星期三日星期三12max300400Zxx【解解】设设x1、x2分别为甲、乙产品的产量，数学模型为：分别为甲、乙产品的产量，数学模型为：1.1 线性规划的数学模型线性规划的数学模型 Mathematical Model of LP1212122401.5300,0 xxxxxx表表1-1Chapter 1 线性规划线性规划Linear Programming Page 6 2023年年3月月1日星期三日星期三线性规划的数学模型由线性规划的数学模型由决策变量决策变量 Decision variables 目标函数目标函

6、数Objective function及约束条件及约束条件Constraints构成。称为三个要素构成。称为三个要素。n其特征是：其特征是：n1解决问题的目标函数是多个决策变量的解决问题的目标函数是多个决策变量的 线性函数，通常是求最大值或线性函数，通常是求最大值或 最小值；最小值；n2解决问题的解决问题的是一组多个决策变量是一组多个决策变量 的线性不等式或等式。的线性不等式或等式。怎样辨别一个模型是线性规划模型？怎样辨别一个模型是线性规划模型？1.1 线性规划的数学模型线性规划的数学模型 Mathematical Model of LPChapter 1 线性规划线性规划Linear Pro

7、gramming Page 7 2023年年3月月1日星期三日星期三【例例1-2】某商场决定：营业员每周连续工作某商场决定：营业员每周连续工作5天后连续休息天后连续休息2天，天，轮流休息。根据统计，商场每天需要的营业员如表轮流休息。根据统计，商场每天需要的营业员如表1-2所示。所示。表表1-2 营业员需要量统计表营业员需要量统计表商场人力资源部应如何安排每天的上班人数，使商场总的营业员商场人力资源部应如何安排每天的上班人数，使商场总的营业员最少。最少。星期星期需要人数需要人数星期星期需要人数需要人数一一300五五480二二300六六600三三350日日550四四4001.1 线性规划的数学模型

8、线性规划的数学模型 Mathematical Model of LPChapter 1 线性规划线性规划Linear Programming Page 8 2023年年3月月1日星期三日星期三【解解】设设xj(j=1，2，7)为休息为休息2天后星期一到星期日开始上班天后星期一到星期日开始上班的营业员，则这个问题的线性规划模型为的营业员，则这个问题的线性规划模型为 7,2,1,0550600480400350300300min765436543254321743217632176521765417654321jxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx

9、Zj1.1 线性规划的数学模型线性规划的数学模型 Mathematical Model of LP星星期期需要需要人数人数星星期期需要需要人数人数一一300五五480二二300六六600三三350日日550四四400Chapter 1 线性规划线性规划Linear Programming Page 9 2023年年3月月1日星期三日星期三1 1 X1X10 0 C1C1404404=3003001041042 2 X2X26767 C2C2301301=3003001 13 3 X3X3146146 C3C3350350=3503500 04 4 X4X4170170 C4C4400400=4

10、004000 05 5 X5X59797 C5C5480480=4804800 06 6 X6X6120120 C6C6600600=6006000 07 7 X7X71717 C7C7550550=5505500 0最优解：最优解：Z617（人）（人）1.1 线性规划的数学模型线性规划的数学模型 Mathematical Model of LPChapter 1 线性规划线性规划Linear Programming Page 10 2023年年3月月1日星期三日星期三【例例1-3】合理用料问题。某汽车需要用甲、乙、丙三种规格的轴各一根，这合理用料问题。某汽车需要用甲、乙、丙三种规格的轴各一根

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

12、负整数解。象这样的非负整数解共有的非负整数解共有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.1 线性规划的数学模型线性规划的数学模型 Mathematical Model of LPChapter 1 线性规划线性规划Linear Programming Page 11 20

13、23年年3月月1日星期三日星期三设设xj(j=1,2,10)为第为第j种下料方案所用圆钢的根数。则用料最少种下料方案所用圆钢的根数。则用料最少数学模型数学模型求下料方案时应注意，余料不能超过最短毛坯的长度；最好将毛求下料方案时应注意，余料不能超过最短毛坯的长度；最好将毛坯长度按降的次序排列，即先切割长度最长的毛坯，再切割次长坯长度按降的次序排列，即先切割长度最长的毛坯，再切割次长的，最后切割最短的，不能遗漏了方案的，最后切割最短的，不能遗漏了方案。如果方案较多，用计。如果方案较多，用计算机编程排方案，去掉余料较长的方案，进行初选。算机编程排方案，去掉余料较长的方案，进行初选。102,1,010

14、005423210002342100022min10987542987643154321101，jxxxxxxxxxxxxxxxxxxxxxZjjj1.1 线性规划的数学模型线性规划的数学模型 Mathematical Model of LP 方案方案规格规格 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.5Chapter 1 线性规划线性规划Linear Programming Page 12 2023年年3

15、月月1日星期三日星期三1 1 X1X15005002 2 X2X20 03 3 X3X30 04 4 X4X40 05 5 X5X50 06 6 X6X662.562.57 7 X7X70 08 8 X8X80 09 9 X9X92502501010 X10X100 0Z812.51.1 线性规划的数学模型线性规划的数学模型 Mathematical Model of LPChapter 1 线性规划线性规划Linear Programming Page 13 2023年年3月月1日星期三日星期三【例例1-4】配料问题。某钢铁公司生产一种合金，要求的成分规格配料问题。某钢铁公司生产一种合金，要

16、求的成分规格是：锡不少于是：锡不少于28%，锌不多于，锌不多于15%，铅恰好，铅恰好10%，镍要界于，镍要界于35%55%之间，不允许有其他成分。钢铁公司拟从五种不同级之间，不允许有其他成分。钢铁公司拟从五种不同级别的矿石中进行冶炼，每种矿物的成分含量和价格如表别的矿石中进行冶炼，每种矿物的成分含量和价格如表1-4所示。所示。矿石杂质在治炼过程中废弃，现要求每吨合金成本最低的矿物数矿石杂质在治炼过程中废弃，现要求每吨合金成本最低的矿物数量。假设矿石在冶炼过程中，合金含量没有发生变化。量。假设矿石在冶炼过程中，合金含量没有发生变化。表表1-4 矿石的金属含量矿石的金属含量 合金合金矿石矿石锡锡%

17、锌锌%铅铅%镍镍%杂质杂质费用（元费用（元/t）1251010253034024000303026030155206018042020040202305851517551901.1 线性规划的数学模型线性规划的数学模型 Mathematical Model of LPChapter 1 线性规划线性规划Linear Programming Page 14 2023年年3月月1日星期三日星期三解解:设设xj（j=1,2，5）是第）是第j 种矿石数量，得到下列线性规划模种矿石数量，得到下列线性规划模型型 注意，矿石在实际冶炼时金属含量会发生变化，建模时应将这种注意，矿石在实际冶炼时金属含量会发生变

18、化，建模时应将这种变化考虑进去，有可能是非线性关系。配料问题也称配方问题、变化考虑进去，有可能是非线性关系。配料问题也称配方问题、营养问题或混合问题，在许多行业生产中都能遇到。营养问题或混合问题，在许多行业生产中都能遇到。1.1 线性规划的数学模型线性规划的数学模型 Mathematical Model of LP矿石矿石锡锡%锌锌%铅铅%镍镍%杂质杂质费用（元费用（元/t）1251010253034024000303026030155206018042020040202305851517551901234512451345135123451234512min3402601802301900.

19、250.40.20.080.280.10.150.20.050.150.10.050.150.10.250.30.20.40.170.550.250.30.20.40.170.350.70.7Zxxxxxxxxxxxxxxxxxxxxxxxxxxxx3450.40.80.4510,1,2,5jxxxxjChapter 1 线性规划线性规划Linear Programming Page 15 2023年年3月月1日星期三日星期三1 1 X1X10 02 2 X2X20.33330.33333 3 X3X30 04 4 X4X40.58330.58335 5 X5X50.66670.6667最优解

20、：最优解：Z=347.51.1 线性规划的数学模型线性规划的数学模型 Mathematical Model of LPChapter 1 线性规划线性规划Linear Programming Page 16 2023年年3月月1日星期三日星期三1.1 线性规划的数学模型线性规划的数学模型 Mathematical Model of LP【例例1-5】投资问题。某投资公司拟将投资问题。某投资公司拟将5000万元的资金用于国万元的资金用于国债、地方国债及基金三种类型证券投资，每类各有两种。每债、地方国债及基金三种类型证券投资，每类各有两种。每种证券的评级、到期年限及每年税后收益率见表种证券的评级、

21、到期年限及每年税后收益率见表1-5所示。所示。表表15 证券投资方案证券投资方案序序号号证券类型证券类型 评级评级 到期年限到期年限 每年税后每年税后收益率收益率(%)1国债国债1 1 83.22国债国债2 1 103.83地方债券地方债券1 2 44.34地方债券地方债券2 3 64.75基金基金1 4 34.26基金基金2 5 44.6 决策者希望：国债决策者希望：国债投资额不少于投资额不少于1000万，万，平均到期年限不超过平均到期年限不超过5年，平均评级不超年，平均评级不超过过2。问每种证券各。问每种证券各投资多少使总收益最投资多少使总收益最大。大。Chapter 1 线性规划线性规划

22、Linear Programming Page 17 2023年年3月月1日星期三日星期三1.1 线性规划的数学模型线性规划的数学模型 Mathematical Model of LP解解 设设xj(j=1,2,，6)为第为第j种证券的投资额，目标函数是税后总收种证券的投资额，目标函数是税后总收益为益为123456(8 3.210 3.84 4.36 4.73 4.24 4.6)/100Zxxxxxx 资金约束：资金约束：1234565000 xxxxxx国债投资额约束：国债投资额约束：121000 xx平均评级约束：平均评级约束：12345612345623452xxxxxxxxxxxx平均

23、到期年限约束：平均到期年限约束：12345612345681046345xxxxxxxxxxxxChapter 1 线性规划线性规划Linear Programming Page 18 2023年年3月月1日星期三日星期三整理后得到线性规划模型整理后得到线性规划模型1234561234561212456123456max0.2560.380.1720.2820.1260.1845000100023035200,1,2,6jZxxxxxxxxxxxxxxxxxxxxxxxxxxj1.1 线性规划的数学模型线性规划的数学模型 Mathematical Model of LPChapter 1 线性

24、规划线性规划Linear Programming Page 19 2023年年3月月1日星期三日星期三【例例1-6】均衡配套生产问题。某产品由均衡配套生产问题。某产品由2件甲、件甲、3件乙零件组装而成。件乙零件组装而成。两种零件必须经过设备两种零件必须经过设备A、B上加工，每件甲零件在上加工，每件甲零件在A、B上的加工时上的加工时间分别为间分别为5分钟和分钟和9分钟，每件乙零件在分钟，每件乙零件在A、B上的加工时间分别为上的加工时间分别为4分分钟和钟和10分钟。现有分钟。现有2台设备台设备A和和3台设备台设备B，每天可供加工时间为，每天可供加工时间为8小时。小时。为了保持两种设备均衡负荷生产，

25、要求一种设备每天的加工总时间不为了保持两种设备均衡负荷生产，要求一种设备每天的加工总时间不超过另一种设备总时间超过另一种设备总时间1小时。怎样安排设备的加工时间使每天产品的小时。怎样安排设备的加工时间使每天产品的产量最大。产量最大。【解解】设设x1、x2为每天加工甲、乙两种零件的件数，则产品的产量是为每天加工甲、乙两种零件的件数，则产品的产量是)31,21min(21xxy 设备设备A、B每天加工工时的约束为每天加工工时的约束为60831096082452121xxxx要求一种设备每台每天的加工时间不超过另一种设备要求一种设备每台每天的加工时间不超过另一种设备1小时的约小时的约束为束为 60)

26、109()452121xxxx（1.1 线性规划的数学模型线性规划的数学模型 Mathematical Model of LPChapter 1 线性规划线性规划Linear Programming Page 20 2023年年3月月1日星期三日星期三目标函数线性化。产品的产量目标函数线性化。产品的产量y等价于等价于2131,21xyxy整理得到线性规划模型整理得到线性规划模型 约束线性化。将绝对值约束写成两个不等式约束线性化。将绝对值约束写成两个不等式60)109()45(60)109()45(21212121xxxxxxxx1.1 线性规划的数学模型线性规划的数学模型 Mathematic

27、al Model of LP121212121212m a x1213549 6 091 01 4 4 0466 0466 00Zyyxyxxxxxxxxxyxx、Chapter 1 线性规划线性规划Linear Programming Page 21 2023年年3月月1日星期三日星期三1.1.2 线性规划的一般模型线性规划的一般模型一般地，假设线性规划数学模型中，有一般地，假设线性规划数学模型中，有m个约束，有个约束，有n个决策变量个决策变量xj,j=1,2,n，目标函数的变量系数用，目标函数的变量系数用cj表示表示,cj称为称为价值系数价值系数。约。约束条件的变量系数用束条件的变量系数用

28、aij表示，表示，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 LPChapter 1 线

29、性规划线性规划Linear Programming Page 22 2023年年3月月1日星期三日星期三11max(min)(,)1,2,0,1,2,njjjnijjijjZc xa xbimxjn 或在实际中一般在实际中一般xj0,但有时但有时xj0或或xj无符号限制。无符号限制。1.1 线性规划的数学模型线性规划的数学模型 Mathematical Model of LPChapter 1 线性规划线性规划Linear Programming Page 23 2023年年3月月1日星期三日星期三1.什么是线性规划，掌握线性规划在管理中的什么是线性规划，掌握线性规划在管理中的几个应用例子几个

30、应用例子2.线性规划数学模型的组成及其特征线性规划数学模型的组成及其特征3.线性规划数学模型的一般表达式。线性规划数学模型的一般表达式。作业：教材习题作业：教材习题 1.11.61.1 线性规划的数学模型线性规划的数学模型 Mathematical Model of LP下一节：图解法下一节：图解法1.2 图解法图解法 Graphical MethodChapter 1 线性规划线性规划Linear Programming Page 25 2023年年3月月1日星期三日星期三图解法的步骤：图解法的步骤：1.求可行解集合。求可行解集合。分别求出满足每个约束包括变量非分别求出满足每个约束包括变量非

31、 负要求负要求的区域，其交集就是可行解集合，或称为的区域，其交集就是可行解集合，或称为可行域可行域；2.绘制目标函数图形。绘制目标函数图形。先过原点作一条矢量指向点（先过原点作一条矢量指向点（c1,c2)，矢，矢量的方向就是目标函数增加的方向，称为梯度方向，再作一量的方向就是目标函数增加的方向，称为梯度方向，再作一条与矢量垂直的直线，这条直线就是目标函数图形；条与矢量垂直的直线，这条直线就是目标函数图形；3.求最优解。求最优解。依据目标函数求最大或最小移动目标函数直线，依据目标函数求最大或最小移动目标函数直线，直线与可行域相交的点对应的坐标就是直线与可行域相交的点对应的坐标就是最优解。最优解。

32、一般地，将目标函数直线放在可行域中一般地，将目标函数直线放在可行域中 求最大值时直线沿着矢量方向移动求最大值时直线沿着矢量方向移动 求最小值时沿着矢量的反方向移动求最小值时沿着矢量的反方向移动1.2 图解法图解法The Graphical MethodChapter 1 线性规划线性规划Linear Programming Page 26 2023年年3月月1日星期三日星期三x1x2O1020304010203040(300,400)(15,10)最优解最优解X=(15,10)最优值最优值Z=850040221 xx305.121xx0,0305.1402212121xxxxxx例例1-712

33、max300400Zxx1.2 图解法图解法The Graphical MethodChapter 1 线性规划线性规划Linear Programming Page 27 2023年年3月月1日星期三日星期三246x1x2246最优解最优解X=(3,1)最优值最优值Z=5(3,1)006346321212121xxxxxxxx、min Z=x1+2x2例例1-8(1,2)1.2 图解法图解法The Graphical MethodChapter 1 线性规划线性规划Linear Programming Page 28 2023年年3月月1日星期三日星期三246x1x2246X（2）（3,1）

34、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 图解法图解法The Graphical MethodChapter 1 线性规划线性规划Linear Programming Page 29 2023年年3月月1日星期三日星期三246x1x2246(1,2)006346321212121xxxxxxxx、无界解无界解(无最优解无最优解)max

35、Z=x1+2x2例例1-101.2 图解法图解法The Graphical MethodChapter 1 线性规划线性规划Linear Programming Page 30 2023年年3月月1日星期三日星期三x1x2O102030401020304050500,050305.140221212121xxxxxxxx无可行解无可行解即无最优解即无最优解max Z=10 x1+4x2例例1-111.2 图解法图解法The Graphical MethodChapter 1 线性规划线性规划Linear Programming Page 31 2023年年3月月1日星期三日星期三由以上例题可知

36、，线性规划的解有由以上例题可知，线性规划的解有4种形式种形式：1.有唯一最优解有唯一最优解(例例1-7例例1-8)2.有多重解有多重解(例例1-9)3.有无界解有无界解(例例1-10)4.无可行解无可行解(例例1-11)1、2情形为有最优解情形为有最优解3、4情形为无最优解情形为无最优解1.2 图解法图解法The Graphical MethodChapter 1 线性规划线性规划Linear Programming Page 32 2023年年3月月1日星期三日星期三1.通过图解法了解线性规划有几种解的形式通过图解法了解线性规划有几种解的形式2.作图的关键有三点作图的关键有三点 (1)可行解

37、区域要画正确可行解区域要画正确 (2)目标函数增加的方向不能画错目标函数增加的方向不能画错 (3)目标函数的直线怎样平行移动目标函数的直线怎样平行移动作业：教材习题作业：教材习题 1.7 1.2 图解法图解法The Graphical Method下一节：线性规划的标准型下一节：线性规划的标准型1.3 线性规划的标准型线性规划的标准型Standard form of LPChapter 1 线性规划线性规划Linear Programming Page 34 2023年年3月月1日星期三日星期三 在用单纯法求解线性规划问题时，为了讨论问题在用单纯法求解线性规划问题时，为了讨论问题方便，需将线性

38、规划模型化为统一的标准形式。方便，需将线性规划模型化为统一的标准形式。1.3 线性规划的标准型线性规划的标准型Standard form of LP线性规划问题的标准型为线性规划问题的标准型为:1目标函数求最大值（或求最小值）目标函数求最大值（或求最小值）2约束条件都为等式方程约束条件都为等式方程3变量变量xj非负非负4常数常数bi非负非负Chapter 1 线性规划线性规划Linear Programming Page 35 2023年年3月月1日星期三日星期三mibnjxbxaxaxabxaxaxabxaxaxaijmnmnmmnnnn,2,1,0,2,1,0221122222211121

39、2111max(或min)Z=c1x1+c2x2+cnxn1.3 线性规划的标准型线性规划的标准型Standard form of LP注：本教材默认目标函数是注：本教材默认目标函数是 maxChapter 1 线性规划线性规划Linear Programming Page 36 njjjxcZ1max2023年年3月月1日星期三日星期三minjxbxajnjijij,2,1,2,1,010maxXbAXCXZ或写成下列形式或写成下列形式：或用矩阵形式或用矩阵形式1.3 线性规划的标准型线性规划的标准型Standard form of LPChapter 1 线性规划线性规划Linear Pr

40、ogramming Page 37 2023年年3月月1日星期三日星期三111211121222221212,)nnnmmmnnmaaaxbaaaxbAXbCc ccaaaxb；(通常通常X记为：记为：称为约束方称为约束方程的系数矩阵，程的系数矩阵，m是约束方程的个数，是约束方程的个数，n是决策变量的个数，是决策变量的个数，一般情况一般情况mn，且，且r()m。TnxxxX),21（max0ZCXAXbX其中其中:1.3 线性规划的标准型线性规划的标准型Standard form of LPChapter 1 线性规划线性规划Linear Programming Page 38 2023年年3

41、月月1日星期三日星期三【例例1-12】将下列线性规划化为标准型将下列线性规划化为标准型 3213minxxxZ无符号要求、32132132132100)3(523)2(3)1(82xxxxxxxxxxxx【解解】（）因为（）因为x3无符号要求无符号要求，即，即x3取正值也取正值也可取负值，标准型中要求变量非负，所以令可取负值，标准型中要求变量非负，所以令 0,33333 xxxxx其中1.3 线性规划的标准型线性规划的标准型Standard form of LPChapter 1 线性规划线性规划Linear Programming Page 39 2023年年3月月1日星期三日星期三(3)第

42、二个约束条件是第二个约束条件是号，在号，在号号 左左端减去剩余变量端减去剩余变量(Surplus variable)x5，x50。也称松驰变。也称松驰变量量3213minxxxZ无符号要求、32132132132100)3(523)2(3)1(82xxxxxxxxxxxx1.3 线性规划的标准型线性规划的标准型Standard form of LP(2)第一个约束条件是第一个约束条件是号，在号，在左端左端加入松驰变量加入松驰变量(slack variable)x4，x40,化为等式；化为等式；(4)第三个约束条件是第三个约束条件是号且常数项为负数，因此在号且常数项为负数，因此在左边加入松左边加

43、入松驰变量驰变量x6，x60，同时两边乘以，同时两边乘以1。（5）目标函数是最小值，为了化为求最大值，令）目标函数是最小值，为了化为求最大值，令Z=Z,得到得到max Z=Z，即当，即当Z达到最小值时达到最小值时Z达到最大值，反之亦然。达到最大值，反之亦然。Chapter 1 线性规划线性规划Linear Programming Page 40 2023年年3月月1日星期三日星期三综合起来得到下列标准型综合起来得到下列标准型 332133maxxxxxZ 05)(233826543321633215332143321xxxxxxxxxxxxxxxxxxxxxx、1.3 线性规划的标准型线性规划

44、的标准型Standard form of LPChapter 1 线性规划线性规划Linear Programming Page 41 2023年年3月月1日星期三日星期三 当某个变量当某个变量xj0时时,令令x/j=xj。当某个约束是绝对值不等式当某个约束是绝对值不等式时，将绝对值不等式化为两个不等式，再化为等式，例如约束时，将绝对值不等式化为两个不等式，再化为等式，例如约束 974321xxx将其化为两个不等式将其化为两个不等式 974974321321xxxxxx再加入松驰变量化为等式。再加入松驰变量化为等式。1.3 线性规划的标准型线性规划的标准型Standard form of LP

45、Chapter 1 线性规划线性规划Linear Programming Page 42 2023年年3月月1日星期三日星期三【例例1-13】将下例线性规划化为标准型将下例线性规划化为标准型无约束、211212145|maxxxxxxxxZ【解解】此题关键是将目标函数中的绝对值去掉。此题关键是将目标函数中的绝对值去掉。令令 0000000000002222222211111111xxxxxxxxxxxxxxxx，222222111111,|,|xxxxxxxxxxxx 则有则有1.3 线性规划的标准型线性规划的标准型Standard form of LPChapter 1 线性规划线性规划Li

46、near Programming Page 43 2023年年3月月1日星期三日星期三得到线性规划的标准形式得到线性规划的标准形式 112211223114112234max()()540Zxxxxxxxxxxxxxxxxxx、1.3 线性规划的标准型线性规划的标准型Standard form of LP对于对于axb(a、b均大于零均大于零)的有界变量化为标准形式有两种方的有界变量化为标准形式有两种方法。法。一种方法是增加两个约束一种方法是增加两个约束xa及及xb 另一种方法是令另一种方法是令x=xa，则，则axb等价于等价于0 xba，增加，增加一个约束一个约束xba并且将原问题所有并且将

47、原问题所有x用用x=x+a替换。替换。Chapter 1 线性规划线性规划Linear Programming Page 44 2023年年3月月1日星期三日星期三1.如何化标准形式？如何化标准形式？可以对照四条标准逐一判断！可以对照四条标准逐一判断！标准形式是人为定义的，目标函数可以是求最小值。标准形式是人为定义的，目标函数可以是求最小值。2.用用WinQSB软件求解时，不必化成标准型。软件求解时，不必化成标准型。图解法时不必化为标准型。图解法时不必化为标准型。3.单纯形法求解时一定要化为标准型。单纯形法求解时一定要化为标准型。作业：教材习题作业：教材习题 1.81.3 线性规划的标准型线性

48、规划的标准型Standard form of LP下一节：基本概念下一节：基本概念1.4 线性规划的有关概念线性规划的有关概念Basic Concepts of LPChapter 1 线性规划线性规划Linear Programming Page 46 2023年年3月月1日星期三日星期三 设线性规划的标准型设线性规划的标准型 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 基基 (b

49、asis)A中中mm子矩阵子矩阵B并且有并且有r（B）=m，则称，则称B是线性规是线性规划的一个基（或基矩阵划的一个基（或基矩阵basis matrix）。当）。当m=n时，基矩阵唯一，时，基矩阵唯一，当当mn时，基矩阵就可能有多个，但数目不超过时，基矩阵就可能有多个，但数目不超过mnCChapter 1 线性规划线性规划Linear Programming Page 47 2023年年3月月1日星期三日星期三【例例1-14】线性规划线性规划 32124maxxxxZ5,1,0226103553214321jxxxxxxxxxj 求所有基矩阵求所有基矩阵。【解解】约束方程的系数矩阵为约束方程的

50、系数矩阵为25矩阵矩阵 10261001115A,610151B,010152B,110053B26114B10019B,12017B,02118B,16016B,06115B容易看出容易看出r(A)=2，2阶子矩阵有阶子矩阵有C52=10个，其中第个，其中第1列与第列与第3列构成列构成的的2阶矩阵不是一个基，基矩阵只有阶矩阵不是一个基，基矩阵只有9个，即个，即1.4 基本概念基本概念Basic Concepts Chapter 1 线性规划线性规划Linear Programming Page 48 2023年年3月月1日星期三日星期三由线性代数知，基矩阵由线性代数知，基矩阵B必为非奇异矩阵