《运筹学》线性规划(精品).ppt

《《运筹学》线性规划(精品).ppt》由会员分享，可在线阅读，更多相关《《运筹学》线性规划(精品).ppt（146页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

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 Method4/6/20231.1 数学模型数学模型 Mathematical Model 4/6/2023Chapter 1 线性规划线性规划Linear Programming Pa

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

3、得最好的经济效益（如产品量最多产获得最好的经济效益（如产品量最多、利润最大）。、利润最大）。4/6/2023Chapter 1 线性规划线性规划Linear Programming Page 4【例例1-1】生生产产计计划划问问题题。某某企企业业在在计计划划期期内内计计划划生生产产甲甲、乙乙两两种种产产品品。按按工工艺艺资资料料规规定定，需需要要A、B两两种种原原材材料料的的数数量量、获获利利情情况况，以以及及两两种种材材料料数数量量限限制制见见表表1-1.企企业业决决策策者者应应如如何何安安排排生生产计划，使企业在计划期内总的利润收入最大。产计划，使企业在计划期内总的利润收入最大。1.1 线

4、性规划的数学模型线性规划的数学模型 Mathematical Model of LP1.1.1 应用模型举例应用模型举例 产品产品 资源资源 甲甲 乙乙现有资现有资源源材料材料A2 21 14040材料材料B1 11.51.53030利润（元利润（元/件）件）300300400400表表1-14/6/2023Chapter 1 线性规划线性规划Linear Programming Page 5【解】设【解】设x1、x2分别为甲、乙产品的产量，数学模型为：分别为甲、乙产品的产量，数学模型为：1.1 线性规划的数学模型线性规划的数学模型 Mathematical Model of LP 产品产品

5、资源资源 甲甲 乙乙现有资现有资源源材料材料A2 21 14040材料材料B1 11.51.53030利润（元利润（元/件）件）3003004004004/6/2023Chapter 1 线性规划线性规划Linear Programming Page 6 线性规划的数学模型由线性规划的数学模型由决策变量决策变量 Decision variables 目标函数目标函数Objective function及约束条件及约束条件Constraints构成。称为三个要素构成。称为三个要素。n其特征是：其特征是：n1解决问题的目标函数是多个决策变量的解决问题的目标函数是多个决策变量的 线性函数，通常是求最

6、大值或线性函数，通常是求最大值或 最小值；最小值；n2解决问题的解决问题的约束条件约束条件约束条件约束条件是一组多个决策变量是一组多个决策变量 的线性不等式或等式。的线性不等式或等式。怎样辨别一个模型是线性规划模型？怎样辨别一个模型是线性规划模型？1.1 线性规划的数学模型线性规划的数学模型 Mathematical Model of LP4/6/2023Chapter 1 线性规划线性规划Linear Programming Page 7 1.1 线性规划的数学模型线性规划的数学模型 Mathematical Model of LP【例【例1-2】4/6/2023Chapter 1 线性规划

7、线性规划Linear Programming Page 8 4/6/2023Chapter 1 线性规划线性规划Linear Programming Page 9【例例1-3】某某商商场场决决定定：营营业业员员每每周周连连续续工工作作5天天后后连连续续休休息息2天天，轮流休息。根据统计，商场每天需要的营业员如表轮流休息。根据统计，商场每天需要的营业员如表1-2所示。所示。表表1-2 营业员需要量统计表营业员需要量统计表商场人力资源部应如何安排每天的上班人数，使商场总的营业员商场人力资源部应如何安排每天的上班人数，使商场总的营业员最少。最少。星期星期需要人数需要人数星期星期需要人数需要人数一一3

8、00五五480二二300六六600三三350日日550四四4001.1 线性规划的数学模型线性规划的数学模型 Mathematical Model of LP4/6/2023Chapter 1 线性规划线性规划Linear Programming Page 10【解】【解】设设xj(j=1，2，7)为休息为休息2天后星期一到星期日开始上天后星期一到星期日开始上班的营业员，则这个问题的线性规划模型为班的营业员，则这个问题的线性规划模型为 1.1 线性规划的数学模型线性规划的数学模型 Mathematical Model of LP星星期期需要需要人数人数星星期期需要需要人数人数一一300五五48

9、0二二300六六600三三350日日550四四4004/6/2023Chapter 1 线性规划线性规划Linear Programming Page 11 1 1 X1X10 0 C1C1404404=3003001041042 2 X2X26767 C2C2301301=3003001 13 3 X3X3146146 C3C3350350=3503500 04 4 X4X4170170 C4C4400400=4004000 05 5 X5X59797 C5C5480480=4804800 06 6 X6X6120120 C6C6600600=6006000 07 7 X7X71717 C7

10、C7550550=5505500 0最优解：最优解：Z617（人）（人）1.1 线性规划的数学模型线性规划的数学模型 Mathematical Model of LP4/6/2023Chapter 1 线性规划线性规划Linear Programming Page 12【例【例1-4】合理用料问题。某汽车需要用甲、乙、丙三种规格的轴各一根，这】合理用料问题。某汽车需要用甲、乙、丙三种规格的轴各一根，这些轴的规格分别是些轴的规格分别是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 5678

12、910需求量需求量y1(根根)：1.5221 11 0 00001000y2：1.0102 10 4 32101000y3：0.7010 23 0 12451000余料（余料（m）00.30.5 0.1o.4 00.30.60.20.51.1 线性规划的数学模型线性规划的数学模型 Mathematical Model of LP4/6/2023Chapter 1 线性规划线性规划Linear Programming Page 13 设设xj(j=1,2,10)为为第第j种种下下料料方方案案所所用用圆圆钢钢的的根根数数。则则用用料料最最少数学模型少数学模型为为为为:求下料方案时应注意，余料不能超

13、过最短毛坯的长度；最好将毛求下料方案时应注意，余料不能超过最短毛坯的长度；最好将毛坯长度按降的次序排列，即先切割长度最长的毛坯，再切割次长坯长度按降的次序排列，即先切割长度最长的毛坯，再切割次长的，最后切割最短的，不能遗漏了方案的，最后切割最短的，不能遗漏了方案。如果方案较多，用计算。如果方案较多，用计算机编程排方案，去掉余料较长的方案，进行初选。机编程排方案，去掉余料较长的方案，进行初选。1.1 线性规划的数学模型线性规划的数学模型 Mathematical Model of LP 方案方案规格规格 1234 5678910需求量需求量y1(根根)221 11 0 00001000y2 10

14、2 10 4 32101000y3 010 23 0 12451000余料（余料（m）00.30.5 0.1o.4 00.30.60.20.54/6/2023Chapter 1 线性规划线性规划Linear Programming Page 14 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 L

15、P4/6/2023Chapter 1 线性规划线性规划Linear Programming Page 15【例例1-5】配配料料问问题题。某某钢钢铁铁公公司司生生产产一一种种合合金金，要要求求的的成成分分规规格格是是：锡锡不不少少于于28%，锌锌不不多多于于15%，铅铅恰恰好好10%，镍镍要要界界于于35%55%之之间间，不不允允许许有有其其他他成成分分。钢钢铁铁公公司司拟拟从从五五种种不不同同级级别别的的矿矿石石中中进进行行冶冶炼炼，每每种种矿矿物物的的成成分分含含量量和和价价格格如如表表1-4所所示示。矿矿石石杂杂质质在在治治炼炼过过程程中中废废弃弃，现现要要求求每每吨吨合合金金成成本本最

16、最低低的的矿矿物物数数量量。假设矿石在冶炼过程中，合金含量没有发生变化。假设矿石在冶炼过程中，合金含量没有发生变化。表表1-4 矿石的金属含量矿石的金属含量 合金合金矿石矿石锡锡%锌锌%铅铅%镍镍%杂质杂质费用（元费用（元/t）1251010253034024000303026030155206018042020040202305851517551901.1 线性规划的数学模型线性规划的数学模型 Mathematical Model of LP4/6/2023Chapter 1 线性规划线性规划Linear Programming Page 16 解解:设设xj（j=1,2，5）是第）是第j种

17、矿石数量，得到下列线性规划模种矿石数量，得到下列线性规划模型型 注注意意，矿矿石石在在实实际际冶冶炼炼时时金金属属含含量量会会发发生生变变化化，建建模模时时应应将将这这种种变变化化考考虑虑进进去去，有有可可能能是是非非线线性性关关系系。配配料料问问题题也也称称配配方方问问题题、营养问题或混合问题，在许多行业生产中都能遇到。营养问题或混合问题，在许多行业生产中都能遇到。1.1 线性规划的数学模型线性规划的数学模型 Mathematical Model of LP矿石矿石锡锡%锌锌%铅铅%镍镍%杂质杂质费用（元费用（元/t）1251010253034024000303026030155206018

18、042020040202305851517551904/6/2023Chapter 1 线性规划线性规划Linear Programming Page 17 1 1 X1X10 02 2 X2X20.33330.33333 3 X3X30 04 4 X4X40.58330.58335 5 X5X50.66670.6667最优解：最优解：Z=347.51.1 线性规划的数学模型线性规划的数学模型 Mathematical Model of LP4/6/2023Chapter 1 线性规划线性规划Linear Programming Page 18 1.1 线性规划的数学模型线性规划的数学模型 M

19、athematical Model of LP【例【例1-6】投资问题。某投资公司拟将】投资问题。某投资公司拟将5000万元的资金用于国万元的资金用于国债、地方国债及基金三种类型证券投资，每类各有两种。每种债、地方国债及基金三种类型证券投资，每类各有两种。每种证券的评级、到期年限及每年税后收益率见表证券的评级、到期年限及每年税后收益率见表1-5所示。所示。表表15 证券投资方案证券投资方案序号序号证券类型证券类型 评级评级 到期年限到期年限 每年税后收益率每年税后收益率(%)1国债国债1 1 83.22国债国债2 1 103.83地方债券地方债券1 2 44.34地方债券地方债券2 3 64.

20、75基金基金1 4 34.26基金基金2 5 44.6 决策者希望：国债投资额不少于决策者希望：国债投资额不少于1000万，平均到期年限不超过万，平均到期年限不超过5年，年，平均评级不超过平均评级不超过2。问每种证券各。问每种证券各投资多少使总收益最大。投资多少使总收益最大。4/6/2023Chapter 1 线性规划线性规划Linear Programming Page 19 1.1 线性规划的数学模型线性规划的数学模型 Mathematical Model of LP解解 设设xj(j=1,2,，6)为第为第j种证券的投资额，目标函数是税后总种证券的投资额，目标函数是税后总收益为收益为资金

21、约束：资金约束：国债投资额约束：国债投资额约束：平均评级约束：平均评级约束：平均到期年限约束：平均到期年限约束：4/6/2023Chapter 1 线性规划线性规划Linear Programming Page 20 整理后得到线性规划模型整理后得到线性规划模型1.1 线性规划的数学模型线性规划的数学模型 Mathematical Model of LP4/6/2023Chapter 1 线性规划线性规划Linear Programming Page 21【例例1-7】均均衡衡配配套套生生产产问问题题。某某产产品品由由2件件甲甲、3件件乙乙零零件件组组装装而而成成。两两种种零零件件必必须须经经

22、过过设设备备A、B上上加加工工，每每件件甲甲零零件件在在A、B上上的的加加工工时时间间分分别别为为5分分钟钟和和9分分钟钟，每每件件乙乙零零件件在在A、B上上的的加加工工时时间间分分别别为为4分分钟钟和和10分分钟钟。现现有有2台台设设备备A和和3台台设设备备B，每每天天可可供供加加工工时时间间为为8小小时时。为为了了保保持持两两种种设设备备均均衡衡负负荷荷生生产产，要要求求一一种种设设备备每每天天的的加加工工总总时时间间不不超超过过另另一一种种设设备备总总时时间间1小小时时。怎怎样样安安排排设设备备的的加加工工时时间间使使每每天天产产品品的的产量最大。产量最大。【解】【解】设设x1、x2为每

23、天加工甲、乙两种零件的件数，则产品的产量是为每天加工甲、乙两种零件的件数，则产品的产量是设备设备A、B每天加工工时的约束为每天加工工时的约束为要求一种设备每台每天的加工时间不超过另一种设备要求一种设备每台每天的加工时间不超过另一种设备1小时的约束小时的约束为为 1.1 线性规划的数学模型线性规划的数学模型 Mathematical Model of LP4/6/2023Chapter 1 线性规划线性规划Linear Programming Page 22 目标函数线性化。产品的产量目标函数线性化。产品的产量y等价于等价于整理得到线性规划模型整理得到线性规划模型 约束线性化。将绝对值约束写成两

24、个不等式约束线性化。将绝对值约束写成两个不等式1.1 线性规划的数学模型线性规划的数学模型 Mathematical Model of LP4/6/2023Chapter 1 线性规划线性规划Linear Programming Page 23 1.1.2 线性规划的一般模型线性规划的一般模型一一般般地地，假假设设线线性性规规划划数数学学模模型型中中，有有m个个约约束束，有有n个个决决策策变变量量xj,j=1,2,n，目目标标函函数数的的变变量量系系数数用用cj表表示示,cj称称为为价价值值系系数数。约约束束条条件件的的变变量量系系数数用用aij表表示示，aij称称为为工工艺艺系系数数。约约束

25、束条条件件右右端端的的常常数数用用bi表表示示，bi称称为为资资源源限限量量。则则线线性性规规划划数数学学模模型型的的一一般般表表达达式可写成式可写成为了书写方便，上式也可写成：为了书写方便，上式也可写成：1.1 线性规划的数学模型线性规划的数学模型 Mathematical Model of LP4/6/2023Chapter 1 线性规划线性规划Linear Programming Page 24 在实际中一般在实际中一般xj0,但有时但有时xj0或或xj无符号限制。无符号限制。1.1 线性规划的数学模型线性规划的数学模型 Mathematical Model of LP4/6/2023C

26、hapter 1 线性规划线性规划Linear Programming Page 25 1.什么是线性规划，掌握线性规划在管理中的什么是线性规划，掌握线性规划在管理中的几个应用例子几个应用例子2.线性规划数学模型的组成及其特征线性规划数学模型的组成及其特征3.线性规划数学模型的一般表达式。线性规划数学模型的一般表达式。1.1 线性规划的数学模型线性规划的数学模型 Mathematical Model of LP下一节：图解法下一节：图解法4/6/20231.2 图解法图解法 Graphical Method4/6/2023Chapter 1 线性规划线性规划Linear Programming

27、 Page 27 图解法的步骤：图解法的步骤：1.求可行解集合。求可行解集合。分别求出满足每个约束包括变量非负要求的分别求出满足每个约束包括变量非负要求的区域，其交集就是可行解集合，或称为区域，其交集就是可行解集合，或称为可行域可行域；2.绘制目标函数图形。绘制目标函数图形。先过原点作一条矢量指向点（先过原点作一条矢量指向点（c1,c2)，矢量的方向就是目标函数增加的方向，称为梯度方向，再作一矢量的方向就是目标函数增加的方向，称为梯度方向，再作一条与矢量垂直的直线，这条直线就是目标函数图形；条与矢量垂直的直线，这条直线就是目标函数图形；3.求最优解。求最优解。依据目标函数求最大或最小移动目标函

28、数直线，依据目标函数求最大或最小移动目标函数直线，直线与可行域相交的点对应的坐标就是直线与可行域相交的点对应的坐标就是最优解。最优解。一般地，将目标函数直线放在可行域中一般地，将目标函数直线放在可行域中 求最大值时直线沿着矢量方向移动求最大值时直线沿着矢量方向移动 求最小值时沿着矢量的反方向移动求最小值时沿着矢量的反方向移动1.2 图解法图解法The Graphical Method4/6/2023Chapter 1 线性规划线性规划Linear Programming Page 28 x1x2O1020304010203040(300,400)(15,10)最优解最优解X=(15,10)最优

29、值最优值Z=8500例例1-71.2 图解法图解法The Graphical Method4/6/2023Chapter 1 线性规划线性规划Linear Programming Page 29 246x1x2246最优解最优解X=(3,1)最优值最优值Z=5(3,1)min Z=x1+2x2例例1-8(1,2)1.2 图解法图解法The Graphical Method4/6/2023Chapter 1 线性规划线性规划Linear Programming Page 30 246x1x2246X（2）（3,1）X（1）（1,3）(5,5)min Z=5x1+5x2例例1-9有无穷多个最优解有

30、无穷多个最优解即具有多重解即具有多重解,通解为通解为 01 当当=0.5时时=(x1,x2)=0.5(1,3)+0.5(3,1)=(2,2)1.2 图解法图解法The Graphical Method4/6/2023Chapter 1 线性规划线性规划Linear Programming Page 31 246x1x2246(1,2)无界解无界解(无最优解无最优解)max Z=x1+2x2例例1-101.2 图解法图解法The Graphical Method4/6/2023Chapter 1 线性规划线性规划Linear Programming Page 32 x1x2O1020304010

31、2030405050无可行解无可行解即无最优解即无最优解max Z=10 x1+4x2例例1-111.2 图解法图解法The Graphical Method4/6/2023Chapter 1 线性规划线性规划Linear Programming Page 33 由以上例题可知，线性规划的解有由以上例题可知，线性规划的解有4种形式种形式：1.有唯一最优解有唯一最优解(例例1-7例例1-8)2.有多重解有多重解(例例1-9)3.有无界解有无界解(例例1-10)4.无可行解无可行解(例例1-11)1、2情形为有最优解情形为有最优解3、4情形为无最优解情形为无最优解1.2 图解法图解法The Gra

32、phical Method4/6/2023Chapter 1 线性规划线性规划Linear Programming Page 34 1.通过图解法了解线性规划有几种解的形式通过图解法了解线性规划有几种解的形式2.作图的关键有三点作图的关键有三点 (1)可行解区域要画正确可行解区域要画正确 (2)目标函数增加的方向不能画错目标函数增加的方向不能画错 (3)目标函数的直线怎样平行移动目标函数的直线怎样平行移动作业：教材习题作业：教材习题 1.7 1.2 图解法图解法The Graphical Method下一节：线性规划的标准型下一节：线性规划的标准型4/6/20231.3 线性规划的标准型线性规

33、划的标准型Standard form of LP4/6/2023Chapter 1 线性规划线性规划Linear Programming Page 36 在用单纯法求解线性规划问题时，为了讨论问题在用单纯法求解线性规划问题时，为了讨论问题方便，需将线性规划模型化为统一的标准形式。方便，需将线性规划模型化为统一的标准形式。1.3 线性规划的标准型线性规划的标准型Standard form of LP线性规划问题的标准型为线性规划问题的标准型为:1目标函数求最大值（或求最小值）目标函数求最大值（或求最小值）2约束条件都为等式方程约束条件都为等式方程3变量变量xj非负非负4常数常数bi非负非负4/6

34、/2023Chapter 1 线性规划线性规划Linear Programming Page 37 max(或min)Z=c1x1+c2x2+cnxn1.3 线性规划的标准型线性规划的标准型Standard form of LP注：本教材默认目标函数是注：本教材默认目标函数是 max4/6/2023Chapter 1 线性规划线性规划Linear Programming Page 38 或写成下列形式或写成下列形式：或用矩阵形式或用矩阵形式1.3 线性规划的标准型线性规划的标准型Standard form of LP4/6/2023Chapter 1 线性规划线性规划Linear Progra

35、mming Page 39 通常通常X记为：记为：称为约束方称为约束方程的系数矩阵，程的系数矩阵，m是约束方程的个数，是约束方程的个数，n是决策变量的个数，是决策变量的个数，一般情况一般情况mn，且，且r()m。其中其中:1.3 线性规划的标准型线性规划的标准型Standard form of LP4/6/2023Chapter 1 线性规划线性规划Linear Programming Page 40【例【例1-12】将下列线性规划化为标准型】将下列线性规划化为标准型【解】（）因为【解】（）因为x3无符号要求无符号要求，即，即x3取正值也取正值也可取负值，标准型中要求变量非负，所以令可取负值，

36、标准型中要求变量非负，所以令 1.3 线性规划的标准型线性规划的标准型Standard form of LP4/6/2023Chapter 1 线性规划线性规划Linear Programming Page 41 (3)第二个约束条件是第二个约束条件是号，在号，在号号 左左端减去剩余变量端减去剩余变量(Surplus variable)x5，x50。也称松驰变。也称松驰变量量1.3 线性规划的标准型线性规划的标准型Standard form of LP(2)第一个约束条件是第一个约束条件是号，在号，在左左端加入松驰变量端加入松驰变量(slack variable)x4，x40,化为等式；化为等

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

38、/2023Chapter 1 线性规划线性规划Linear Programming Page 43 当某个变量当某个变量xj0时时,令令x/j=xj。当某个约束是绝对值不等式当某个约束是绝对值不等式时，将绝对值不等式化为两个不等式，再化为等式，例如约束时，将绝对值不等式化为两个不等式，再化为等式，例如约束 将其化为两个不等式将其化为两个不等式 再加入松驰变量化为等式。再加入松驰变量化为等式。1.3 线性规划的标准型线性规划的标准型Standard form of LP4/6/2023Chapter 1 线性规划线性规划Linear Programming Page 44【例例1-13】将下例线

39、性规划化为标准型】将下例线性规划化为标准型【解】解】此题关键是将目标函数中的绝对值去掉。此题关键是将目标函数中的绝对值去掉。令令 则有则有1.3 线性规划的标准型线性规划的标准型Standard form of LP4/6/2023Chapter 1 线性规划线性规划Linear Programming Page 45 得到线性规划的标准形式得到线性规划的标准形式 1.3 线性规划的标准型线性规划的标准型Standard form of LP对于对于axb(a、b均大于零均大于零)的有界变量化为标准形式有两种方的有界变量化为标准形式有两种方法。法。一种方法是增加两个约束一种方法是增加两个约束x

40、a及及xb 另一种方法是令另一种方法是令x=xa，则，则axb等价于等价于0 xba，增加，增加一个约束一个约束xba并且将原问题所有并且将原问题所有x用用x=x+a替换。替换。4/6/2023Chapter 1 线性规划线性规划Linear Programming Page 46 1.如何化标准形式？如何化标准形式？可以对照四条标准逐一判断！可以对照四条标准逐一判断！标准形式是人为定义的，目标函数可以是求最小值。标准形式是人为定义的，目标函数可以是求最小值。2.用用WinQSB软件求解时，不必化成标准型。软件求解时，不必化成标准型。图解法时不必化为标准型。图解法时不必化为标准型。3.单纯形法

41、求解时一定要化为标准型。单纯形法求解时一定要化为标准型。作业：教材习题作业：教材习题 1.81.3 线性规划的标准型线性规划的标准型Standard form of LP下一节：基本概念下一节：基本概念4/6/20231.4 线性规划的有关概念线性规划的有关概念Basic Concepts of LP4/6/2023Chapter 1 线性规划线性规划Linear Programming Page 48 设线性规划的标准型设线性规划的标准型 maxZ=CX （1.1）AX=b （1.2）X0 （1.3）式式中中A是是mn矩矩阵阵，mn并并且且r（A）=m，显显然然A中中至至少少有有一一个个mm

42、子矩阵子矩阵B，使得，使得r（B）=m。1.4 基本概念基本概念Basic Concepts 基基 (basis)A中中mm子矩阵子矩阵B并且有并且有r（B）=m，则称，则称B是线性规是线性规划的一个基（或基矩阵划的一个基（或基矩阵basis matrix）。当）。当m=n时，基矩阵唯一，时，基矩阵唯一，当当mn时，基矩阵就可能有多个，但数目不超过时，基矩阵就可能有多个，但数目不超过4/6/2023Chapter 1 线性规划线性规划Linear Programming Page 49【例【例1-14】线性规划】线性规划 求所有基矩阵求所有基矩阵。【解】约束方程的系数矩阵为【解】约束方程的系数

43、矩阵为25矩阵矩阵 容易看出容易看出r(A)=2，2阶阶子矩子矩阵阵有有C52=10个，其中第个，其中第1列与第列与第3列构成列构成的的2阶矩阵不是一个基，基矩阵只有阶矩阵不是一个基，基矩阵只有9个，即个，即1.4 基本概念基本概念Basic Concepts 4/6/2023Chapter 1 线性规划线性规划Linear Programming Page 50 由线性代数知，基矩阵由线性代数知，基矩阵B必为非奇异矩阵并且必为非奇异矩阵并且|B|0。当矩阵。当矩阵B的行列式等式零即的行列式等式零即|B|=0时就不是基时就不是基 当确定某一矩阵为基矩阵时，则基矩阵对应的列向量称为当确定某一矩阵

44、为基矩阵时，则基矩阵对应的列向量称为基基向量向量(basis vector)，其余列向量称为，其余列向量称为非基向量非基向量 基向量对应的变量称为基向量对应的变量称为基变量基变量(basis variable)，非基向，非基向量对应的变量称为量对应的变量称为非基变量非基变量 在在上上例例中中B2的的基基向向量量是是A中中的的第第一一列列和和第第四四列列，其其余余列列向向量量是是非非基基向向量量，x1、x4是是基基变变量量，x2、x3、x5是是非非基基变变量量。基基变变量量、非非基基变变量量是是针针对对某某一一确确定定基基而而言言的的，不不同同的的基基对对应应的的基基变量和非基变量也不同。变量和

45、非基变量也不同。1.4 基本概念基本概念Basic Concepts 4/6/2023Chapter 1 线性规划线性规划Linear Programming Page 51 可行解可行解(feasible solution)满足式（满足式（1.2）及（）及（1.3）的解）的解X=（x1,x2，xn)T称为可行解称为可行解。基基本本可可行行解解(basis feasible solution)若若基基本本解解是是可可行行解解则则称称为是基本可行解（也称基可行解）。为是基本可行解（也称基可行解）。例如，例如，与与X=（0，0，0，3，2，）都是例，）都是例1-14 的可行解。的可行解。基本解基本

46、解(basis solution)对某一确定的基对某一确定的基B，令非基变量等于零，令非基变量等于零，利用式（利用式（1.）解出基变量，则这组解称为基解出基变量，则这组解称为基的基的基本解。本解。最最优优解解(optimal solution)满满足足式式（1.1）的的可可行行解解称称为为最最优优解解，即即是是使使得得目目标标函函数数达达到到最最大大值值的的可可行行解解就就是是最最优优解解，例例如可行解如可行解 是例是例1-14的最优解。的最优解。非可行解非可行解(Infeasible solution)无界解无界解(unbound solution)1.4 基本概念基本概念Basic Con

47、cepts 4/6/2023Chapter 1 线性规划线性规划Linear Programming Page 52 显然，只要基本解中的基变量的解满足式（显然，只要基本解中的基变量的解满足式（1.）的非负要求，）的非负要求，那么这个基本解就是基本可行解。那么这个基本解就是基本可行解。在在例例1-14中中，对对来来说说，x1,x2是是基基变变量量，x3,x4，x5是是非非基基变变量，令量，令x3=x4=x5=0，则式（，则式（1.）为）为对对B2来说，来说，x1,x4,为基变量，令非基变量为基变量，令非基变量x2,x3,x5为零，由式为零，由式（1.2）得到）得到，x4=4，因因|B1|，由克

48、莱姆法，由克莱姆法则则知，知，x1、x2有唯一解有唯一解x12/5,x2=1则则 基基本解为本解为1.4 基本概念基本概念Basic Concepts 4/6/2023Chapter 1 线性规划线性规划Linear Programming Page 53 由于由于 是基本解，从而它是基本可行解，在是基本解，从而它是基本可行解，在 中中x1=0的解X称为线性规划问题的可行解。最优解：使Z=CX达到最大值的可行解称为最优解。4/6/2023Chapter 1 线性规划线性规划Linear Programming Page 56 基：若B是矩阵A中mm阶非奇异子矩阵（B0），则B是线性规划问题的一

49、个基。不妨设：,j=1，2，,m 基向量。，j=1，2，,m 基变量。,j=m+1,n 非基变量。4/6/2023Chapter 1 线性规划线性规划Linear Programming Page 57 求解求解 4/6/2023Chapter 1 线性规划线性规划Linear Programming Page 58 T基变量令 可求出：基解：称上面求出的X解为基解。基可行解：非负的基解X称为基可行解可行基：对应基可行解的基称为可行基基本最优解 最优解是基本解称为基本最优解。最优基基本最优解对应的基称为最优基；4/6/2023Chapter 1 线性规划线性规划Linear Programmi

50、ng Page 59 基基本本最最优优解解、最最优优解解、基基本本可可行行解解、基基本本解解、可可行行解解的关系如下所示：的关系如下所示：基本最优解基本最优解基本可行解基本可行解可行解可行解最最 优优 解解基本解基本解1.4 基本概念基本概念Basic Concepts 4/6/2023Chapter 1 线性规划线性规划Linear Programming Page 60 线性规划解的关系图 非可行解非可行解非可行解非可行解 基解基解基解基解 基可行解基可行解最优解？最优解？4/6/2023Chapter 1 线性规划线性规划Linear Programming Page 61 例：求基解、