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 1.1 线性规划的数学模型线性规划的数学模型 Mathematical Model of
2、 LP 线性规划通常研究资源的最优利用、设备最佳运行等问线性规划通常研究资源的最优利用、设备最佳运行等问题。例如，当任务或目标确定后，如何统筹兼顾，合理安题。例如，当任务或目标确定后，如何统筹兼顾，合理安排，用最少的资源排，用最少的资源（如资金、设备、原标材料、人工、时（如资金、设备、原标材料、人工、时间等）去完成确定的任务或目标；企业在一定的资源条件间等）去完成确定的任务或目标；企业在一定的资源条件限制下，如何组织安排生产获得最好的经济效益（如产品限制下，如何组织安排生产获得最好的经济效益（如产品量最多量最多、利润最大）。、利润最大）。线性规划线性规划（Linear Programming,
3、缩写为LP）是运筹学的重要是运筹学的重要分支之一，在实际中应用得较广泛，其方法也较成熟，借助分支之一，在实际中应用得较广泛，其方法也较成熟，借助计算机，使得计算更方便，应用领域更广泛和深入。计算机，使得计算更方便，应用领域更广泛和深入。【例例1.1】最优生产计划问题。某企业在计划期内计划生产甲、最优生产计划问题。某企业在计划期内计划生产甲、乙、丙三种产品。这些产品分别需要要在设备乙、丙三种产品。这些产品分别需要要在设备A、B上加工，需上加工，需要消耗材料要消耗材料C、D，按工艺资料规定，单件产品在不同设备上加按工艺资料规定，单件产品在不同设备上加工及所需要的资源如表工及所需要的资源如表1.1所
4、示。已知在计划期内设备的加工能所示。已知在计划期内设备的加工能力各为力各为200台时，可供材料分别为台时，可供材料分别为360、300公斤；每生产一件甲、公斤；每生产一件甲、乙、丙三种产品，企业可获得利润分别为乙、丙三种产品，企业可获得利润分别为40、30、50元，假定元，假定市场需求无限制。企业决策者应如何安排生产计划，使企业在市场需求无限制。企业决策者应如何安排生产计划，使企业在计划期内总的利润收入最大？计划期内总的利润收入最大？1.1 线性规划的数学模型线性规划的数学模型 Mathematical Model of LP1.1.1 应用模型举例应用模型举例 产品产品 资源资源 甲甲 乙乙
5、 丙丙现有资源现有资源设备设备A 3 1 2 200设备设备B 2 2 4 200材料材料C 4 5 1 360材料材料D 2 3 5 300利润（元利润（元/件）件）40 30 50表表1.1 产品资源消耗产品资源消耗1.1 线性规划的数学模型线性规划的数学模型 Mathematical Model of LP321503040maxxxxZ0003005323605420042220023321321321321321xxxxxxxxxxxxxxx，【解解】设设x1、x2、x3 分别为甲、乙、丙三种产品的产量数学模型分别为甲、乙、丙三种产品的产量数学模型为：为：1.1 线性规划的数学模型线
6、性规划的数学模型 Mathematical Model of LP 产品产品 资源资源 甲甲 乙乙 丙丙现有资现有资源源设备设备A 3 1 2 200设备设备B 2 2 4 200材料材料C 4 5 1 360材料材料D 2 3 5 300利润（元利润（元/件）件）40 30 50最优解最优解X=(50,30,10);Z=3400线性规划的数学模型由线性规划的数学模型由决策变量决策变量 Decision variables 目标函数目标函数Objective function及约束条件及约束条件Constraints构成。称为三个要素构成。称为三个要素。n其特征是：其特征是：n1解决问题的目标
7、函数是多个决策变量的解决问题的目标函数是多个决策变量的 线性函数，通常是求最大值或线性函数，通常是求最大值或 最小值；最小值；n2解决问题的解决问题的是一组多个决策变量是一组多个决策变量 的线性不等式或等式。的线性不等式或等式。怎样辨别一个模型是线性规划模型？怎样辨别一个模型是线性规划模型？1.1 线性规划的数学模型线性规划的数学模型 Mathematical Model of LP【例例1.2】某商场决定：营业员每周连续工作某商场决定：营业员每周连续工作5天后连续休息天后连续休息2天，天，轮流休息。根据统计，商场每天需要的营业员如表轮流休息。根据统计，商场每天需要的营业员如表1.2所示。所示
8、。表表1.2 营业员需要量统计表营业员需要量统计表商场人力资源部应如何安排每天的上班人数，使商场总的营业员商场人力资源部应如何安排每天的上班人数，使商场总的营业员最少。最少。星期星期需要人数需要人数星期星期需要人数需要人数一一300五五480二二300六六600三三350日日550四四4001.1 线性规划的数学模型线性规划的数学模型 Mathematical Model of LP【解解】设设xj(j=1，2，7)为休息为休息2天后星期一到星期日开始上班天后星期一到星期日开始上班的营业员，则这个问题的线性规划模型为的营业员，则这个问题的线性规划模型为 7,2,1,05506004804003
9、50300300min765436543254321743217632176521765417654321jxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxZj1.1 线性规划的数学模型线性规划的数学模型 Mathematical Model of LP星星期期需要需要人数人数星星期期需要需要人数人数一一300五五480二二300六六600三三350日日550四四4001 1X1X10 0C1C1404404=3003001041042 2X2X26767C2C2301301=3003001 13 3X3X3146146C3C3350350=3503500
10、 04 4X4X4170170C4C4400400=4004000 05 5X5X59797C5C5480480=4804800 06 6X6X6120120C6C6600600=6006000 07 7X7X71717C7C7550550=5505500 0最优解：最优解：Z617（人）（人）【例例1.3】合理用料问题。某汽车需要用甲、乙、丙三种规格的轴各一根，这合理用料问题。某汽车需要用甲、乙、丙三种规格的轴各一根，这些轴的规格分别是些轴的规格分别是1.5，1，0.7（m），），这些轴需要用同一种圆钢来做，圆钢长这些轴需要用同一种圆钢来做，圆钢长度为度为4 m。现在要制造。现在要制造100
11、0辆汽车，最少要用多少圆钢来生产这些轴？辆汽车，最少要用多少圆钢来生产这些轴？【解解】这是一个条材下料问题这是一个条材下料问题，设切口宽度为零。，设切口宽度为零。设一根圆钢切割成甲、设一根圆钢切割成甲、乙、丙三种轴的根数分别为乙、丙三种轴的根数分别为y1，y2，y3,则切割方式可用不等式则切割方式可用不等式1.5y1+y2+0.7y34表示，求这个不等式关于表示，求这个不等式关于y1，y2，y3的非负整数解。象这样的非负整数解。象这样的非负整数解共有的非负整数解共有10组，也就是有组，也就是有10种下料方式，如表种下料方式，如表1.3所示。所示。表表13 下料方案下料方案 方案方案规格规格 1
12、234 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 LP设设xj(j=1,2,10)为第为第j种下料方案所用圆钢的根数。则用料最少种下料方案所用圆钢的根数。则用料最少数学模型数学模型求下料方案时应注意，余料不能超过最短毛坯的长度；最好将毛求下料方案时应注意，余料不能超过最短毛坯的长度；最好将毛坯长度按降的次序排列，即先切割长度最
13、长的毛坯，再切割次长坯长度按降的次序排列，即先切割长度最长的毛坯，再切割次长的，最后切割最短的，不能遗漏了方案的，最后切割最短的，不能遗漏了方案。如果方案较多，用计。如果方案较多，用计算机编程排方案，去掉余料较长的方案，进行初选。算机编程排方案，去掉余料较长的方案，进行初选。102,1,010005423210002342100022min10987542987643154321101，jxxxxxxxxxxxxxxxxxxxxxZjjj1.1 线性规划的数学模型线性规划的数学模型 Mathematical Model of LP 方案方案规格规格 1234 5678910需求量需求量y1(根
14、根)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 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.5【例例1.4】配料问题。某钢铁公司生产一种合金，要求的成分规格配料问题。某钢铁公司生产一种合金，要求的成分规格是：锡不少于是：锡不少于28%，锌不多于
15、，锌不多于15%，铅恰好，铅恰好10%，镍要界于，镍要界于35%55%之间，不允许有其他成分。钢铁公司拟从五种不同级之间，不允许有其他成分。钢铁公司拟从五种不同级别的矿石中进行冶炼，每种矿物的成分含量和价格如表别的矿石中进行冶炼，每种矿物的成分含量和价格如表1.4所示。所示。矿石杂质在治炼过程中废弃，现要求每吨合金成本最低的矿物数矿石杂质在治炼过程中废弃，现要求每吨合金成本最低的矿物数量。假设矿石在冶炼过程中，合金含量没有发生变化。量。假设矿石在冶炼过程中，合金含量没有发生变化。表表1.4 矿石的金属含量矿石的金属含量 合金合金矿石矿石锡锡%锌锌%铅铅%镍镍%杂质杂质费用（元费用（元/t）12
16、51010253034024000303026030155206018042020040202305851517551901.1 线性规划的数学模型线性规划的数学模型 Mathematical Model of LP解解:设设xj（j=1,2，5）是第是第j 种矿石数量，得到下列线性规划模种矿石数量，得到下列线性规划模型型 注意，矿石在实际冶炼时金属含量会发生变化，建模时应将这种注意，矿石在实际冶炼时金属含量会发生变化，建模时应将这种变化考虑进去，有可能是非线性关系。配料问题也称配方问题、变化考虑进去，有可能是非线性关系。配料问题也称配方问题、营养问题或混合问题，在许多行业生产中都能遇到。营养
17、问题或混合问题，在许多行业生产中都能遇到。1.1 线性规划的数学模型线性规划的数学模型 Mathematical Model of LP矿石矿石锡锡%锌锌%铅铅%镍镍%杂质杂质费用（元费用（元/t）1251010253034024000303026030155206018042020040202305851517551901234512451345135123451234512min3402601802301900.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.35
18、0.70.7Zxxxxxxxxxxxxxxxxxxxxxxxxxxxx3450.40.80.4510,1,2,5jxxxxj1 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 LP【例例1.5】投资问题。某投资公司在第一年有投资问题。某投资公司在第一年有200万元资金，每年都有如下的万元资金，每年都有如下的投资方案可供考虑采纳：投资方案可供考虑采纳：“假使第一年投入
19、一笔资金，第二年又继假使第一年投入一笔资金，第二年又继续投入此资金的续投入此资金的50%，那么到第三年就可回收第一年投入资金的一，那么到第三年就可回收第一年投入资金的一倍金额倍金额”。投资公司决定最优的投资策略使第六年所掌握的资金最。投资公司决定最优的投资策略使第六年所掌握的资金最多。多。第五年：第五年：(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，整理后得
20、到下列线性规划模型整理后得到下列线性规划模型 1.1 线性规划的数学模型线性规划的数学模型 Mathematical Model of LP【解解】设设 x1：第一年的投资；第一年的投资；x2：第一年的保留资金第一年的保留资金 x3：第二年新的投资；第二年新的投资；x4：第二年的保留资金第二年的保留资金 x5：第三年新的投资；：第三年新的投资；x6：第三年的保留资金第三年的保留资金 x7：第四年新的投资第四年新的投资 x8：第四年的保留资金第四年的保留资金 x9：第五年的保留资金第五年的保留资金 7912123413456356785789max22002220422204222042200,
21、1,2,9jZxxxxxxxxxxxxxxxxxxxxxxxj1.1 线性规划的数学模型线性规划的数学模型 Mathematical Model of LP1 1X1X155.284655.28462 2X2X2144.7155144.71553 3X3X3117.0732117.07324 4X4X40 05 5X5X552.032552.03256 6X6X60 07 7X7X7208.1301208.13018 8X8X80 09 9X9X90 0最优解：最优解：Z 416.26万元万元x1：第一年的投资；第一年的投资；x2：第一年的保留资金第一年的保留资金 x3：第二年新的投资；第二年
22、新的投资；x4：第二年的保留资金第二年的保留资金 x5：第三年新的投资；：第三年新的投资；x6：第三年的保留资金第三年的保留资金 x7：第四年新的投资第四年新的投资 x8：第四年的保留资金第四年的保留资金 x9：第五年的保留资金第五年的保留资金 【例例1.6】均衡配套生产问题。某产品由均衡配套生产问题。某产品由2件甲、件甲、3件乙零件组装而成。件乙零件组装而成。两种零件必须经过设备两种零件必须经过设备A、B上加工，每件甲零件在上加工，每件甲零件在A、B上的加工时上的加工时间分别为间分别为5分钟和分钟和9分钟，每件乙零件在分钟，每件乙零件在A、B上的加工时间分别为上的加工时间分别为4分分钟和钟和
23、10分钟。现有分钟。现有2台设备台设备A和和3台设备台设备B，每天可供加工时间为每天可供加工时间为8小时。小时。为了保持两种设备均衡负荷生产，要求一种设备每天的加工总时间不为了保持两种设备均衡负荷生产，要求一种设备每天的加工总时间不超过另一种设备总时间超过另一种设备总时间1小时。怎样安排设备的加工时间使每天产品的小时。怎样安排设备的加工时间使每天产品的产量最大。产量最大。【解解】设设x1、x2为每天加工甲、乙两种零件的件数，则产品的产量是为每天加工甲、乙两种零件的件数，则产品的产量是)31,21min(21xxy 设备设备A、B每天加工工时的约束为每天加工工时的约束为6083109608245
24、2121xxxx要求一种设备每台每天的加工时间不超过另一种设备要求一种设备每台每天的加工时间不超过另一种设备1小时的约小时的约束为束为 60)109()452121xxxx（1.1 线性规划的数学模型线性规划的数学模型 Mathematical Model of LP目标函数线性化。产品的产量目标函数线性化。产品的产量y等价于等价于2131,21xyxy整理得到线性规划模型整理得到线性规划模型 约束线性化。将绝对值约束写成两个不等式约束线性化。将绝对值约束写成两个不等式60)109()45(60)109()45(21212121xxxxxxxx1.1 线性规划的数学模型线性规划的数学模型 Ma
25、thematical Model of LP121212121212m a x1213549 6 091 01 4 4 0466 0466 00Zyyxyxxxxxxxxxyxx、1.1.2 线性规划的一般模型线性规划的一般模型一般地，假设线性规划数学模型中，有一般地，假设线性规划数学模型中，有m个约束，有个约束，有n个决策变量个决策变量xj,j=1,2,n，目标函数的变量系数用目标函数的变量系数用cj表示表示,cj称为称为价值系数价值系数。约。约束条件的变量系数用束条件的变量系数用aij表示，表示，aij称为称为工艺系数工艺系数。约束条件右端的。约束条件右端的常数用常数用bi表示，表示，bi
26、称为称为资源限量资源限量。则线性规划数学模型的一般表达。则线性规划数学模型的一般表达式可写成式可写成1 1221111221121 1222221 122max(min)(,)(,)(,)0,1,2,nnnnnnmmmnnmjZc xc xc xa xa xa xba xa xa xba xaxaxbxjn 或或或为了书写方便，上式也可写成：为了书写方便，上式也可写成：1.1 线性规划的数学模型线性规划的数学模型 Mathematical Model of LP11max(min)(,)1,2,0,1,2,njjjnijjijjZc xa xbinxjn 或在实际中一般在实际中一般xj0,但有
27、时但有时xj0或或xj无符号限制。无符号限制。1.1 线性规划的数学模型线性规划的数学模型 Mathematical Model of LP1.什么是线性规划，掌握线性规划在管理中的什么是线性规划，掌握线性规划在管理中的几个应用例子几个应用例子2.线性规划数学模型的组成及其特征线性规划数学模型的组成及其特征3.线性规划数学模型的一般表达式。线性规划数学模型的一般表达式。作业：教材作业：教材P31 T 2，3，4，5，61.1 线性规划的数学模型线性规划的数学模型 Mathematical Model of LP下一节：图解法下一节：图解法1.2 图解法图解法 Graphical Method图
28、解法的步骤：图解法的步骤：1.求可行解集合。求可行解集合。分别求出满足每个约束包括变量非分别求出满足每个约束包括变量非 负要求负要求的区域，其交集就是可行解集合，或称为的区域，其交集就是可行解集合，或称为可行域可行域；2.绘制目标函数图形。绘制目标函数图形。先过原点作一条矢量指向点（先过原点作一条矢量指向点（c1,c2)，矢矢量的方向就是目标函数增加的方向，称为梯度方向，再作一量的方向就是目标函数增加的方向，称为梯度方向，再作一条与矢量垂直的直线，这条直线就是目标函数图形；条与矢量垂直的直线，这条直线就是目标函数图形；3.求最优解。求最优解。依据目标函数求最大或最小移动目标函数直线，依据目标函
29、数求最大或最小移动目标函数直线，直线与可行域相交的点对应的坐标就是直线与可行域相交的点对应的坐标就是最优解。最优解。一般地，将目标函数直线放在可行域中一般地，将目标函数直线放在可行域中 求最大值时直线沿着矢量方向移动求最大值时直线沿着矢量方向移动 求最小值时沿着矢量的反方向移动求最小值时沿着矢量的反方向移动1.2 图解法图解法The Graphical Methodx1x2O1020304010203040(3,4)(15,10)最优解最优解X=(15,10)最优值最优值Z=8540221xx305.121xx0,0305.1402212121xxxxxx例例1.72143maxxxZ1.2
30、图解法图解法The Graphical Method246x1x2246最优解最优解X=(3,1)最优值最优值Z=5(3,1)006346321212121xxxxxxxx、min Z=x1+2x2例例1.8(1,2)1.2 图解法图解法The Graphical Method246x1x2246X（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)
31、=(2,2)1.2 图解法图解法The Graphical Method246x1x2246(1,2)006346321212121xxxxxxxx、无界解无界解(无最优解无最优解)max Z=x1+2x2例例1.10 x1x2O102030401020304050500,050305.140221212121xxxxxxxx无无可行解可行解即无最优解即无最优解max Z=10 x1+4x2例例1.111.2 图解法图解法The Graphical Method由由以上例题可知，线性规划的解有以上例题可知，线性规划的解有4种形式种形式：1.有唯一最优解有唯一最优解(例例1.7例例1.8)2.有
32、多重解有多重解(例例1.9)3.有无界解有无界解(例例1.10)4.无可行解无可行解(例例1.11)1、2情形为有最优解情形为有最优解3、4情形为无最优解情形为无最优解1.2 图解法图解法The Graphical Method1.通过图解法了解线性规划有几种解的形式通过图解法了解线性规划有几种解的形式2.作图的关键有三点作图的关键有三点 (1)可行解区域要画正确可行解区域要画正确 (2)目标函数增加的方向不能画错目标函数增加的方向不能画错 (3)目标函数的直线怎样平行移动目标函数的直线怎样平行移动作业：教材作业：教材P34 T7 1.2 图解法图解法The Graphical Method下
33、一节：线性规划的标准型下一节：线性规划的标准型1.3 线性规划的标准型线性规划的标准型Standard form of LP 在用单纯法求解线性规划问题时，为了讨论问题在用单纯法求解线性规划问题时，为了讨论问题方便，需将线性规划模型化为统一的标准形式。方便，需将线性规划模型化为统一的标准形式。1.3 线性规划的标准型线性规划的标准型Standard form of LP线性规划问题的标准型为线性规划问题的标准型为:1目标函数求最大值（或求最小值）目标函数求最大值（或求最小值）2约束条件都为等式方程约束条件都为等式方程3变量变量xj非负非负4常数常数bi非负非负mibnjxbxaxaxabxax
34、axabxaxaxaijmnmnmmnnnn,2,1,0,2,1,02211222222111212111max(或min)Z=c1x1+c2x2+cnxn1.3 线性规划的标准型线性规划的标准型Standard form of LP注：本教材默认目标函数是注：本教材默认目标函数是 maxnjjjxcZ1maxminjxbxajnjijij,2,1,2,1,010maxXbAXCXZ或写成下列形式或写成下列形式：或用矩阵形式或用矩阵形式1.3 线性规划的标准型线性规划的标准型Standard form of LP111211121222221212,)nnnmmm nnmaaaxbaaaxbA
35、XbCc ccaaaxb ；(通常通常X记为：记为：称为约束方称为约束方程的系数矩阵，程的系数矩阵，m是约束方程的个数，是约束方程的个数，n是决策变量的个数，是决策变量的个数，一般情况一般情况mn，且，且r()m。TnxxxX),21（m ax0ZC XA XbX其中其中:1.3 线性规划的标准型线性规划的标准型Standard form of LP【例例1.12】将下列线性规划化为标准型将下列线性规划化为标准型 3213minxxxZ无符号要求、32132132132100)3(523)2(3)1(82xxxxxxxxxxxx【解解】（）因为（）因为x3无符号要求无符号要求，即，即x3取正值
36、也取正值也可取负值，标准型中要求变量非负，所以令可取负值，标准型中要求变量非负，所以令 0,33333 xxxxx其中1.3 线性规划的标准型线性规划的标准型Standard form of LP(3)第二个约束条件是第二个约束条件是号，在号，在号号 左左端减去剩余变量端减去剩余变量(Surplus variable)x5，x50。也称松驰变。也称松驰变量量3213minxxxZ无符号要求、32132132132100)3(523)2(3)1(82xxxxxxxxxxxx1.3 线性规划的标准型线性规划的标准型Standard form of LP(2)第一个约束条件是第一个约束条件是号，在号
37、，在左端左端加入松驰变量加入松驰变量(slack variable)x4，x40,化为等式；化为等式；(4)第三个约束条件是第三个约束条件是号且常数项为负数，因此在号且常数项为负数，因此在左边加入松左边加入松驰变量驰变量x6，x60，同时两边乘以同时两边乘以1。（5）目标函数是最小值，为了化为求最大值，令）目标函数是最小值，为了化为求最大值，令Z=Z,得到得到max Z=Z，即当即当Z达到最小值时达到最小值时Z达到最大值，反之亦然。达到最大值，反之亦然。综合起来得到下列标准型综合起来得到下列标准型 332133maxxxxxZ 05)(233826543321633215332143321xx
38、xxxxxxxxxxxxxxxxxxxx、1.3 线性规划的标准型线性规划的标准型Standard form of LP 当某个变量当某个变量xj0时时,令令x/j=xj。当某个约束是绝对值不等式当某个约束是绝对值不等式时，将绝对值不等式化为两个不等式，再化为等式，例如约束时，将绝对值不等式化为两个不等式，再化为等式，例如约束 974321xxx将其化为两个不等式将其化为两个不等式 974974321321xxxxxx再加入松驰变量化为等式。再加入松驰变量化为等式。1.3 线性规划的标准型线性规划的标准型Standard form of LP【例例1.13】将下例线性规划化为标准型将下例线性规
39、划化为标准型无约束、211212145|maxxxxxxxxZ【解解】此题关键是将目标函数中的绝对值去掉。此题关键是将目标函数中的绝对值去掉。令令 0000000000002222222211111111xxxxxxxxxxxxxxxx，222222111111,|,|xxxxxxxxxxxx 则有则有1.3 线性规划的标准型线性规划的标准型Standard form of LP得到线性规划的标准形式得到线性规划的标准形式 112211223114112234max()()540Zxxxxxxxxxxxxxxxxxx、1.3 线性规划的标准型线性规划的标准型Standard form of L
40、P对于对于axb(a、b均大于零均大于零)的有界变量化为标准形式有两种方的有界变量化为标准形式有两种方法，一种方法是增加两个约束法，一种方法是增加两个约束xa及及xb，另一种方法是令，另一种方法是令=xa，则，则axb等价于等价于0ba，增加一个约束，增加一个约束ba并且将原问并且将原问题所有题所有x用用x=+a替换。替换。1.如何化标准形式？如何化标准形式？可以对照四条标准逐一判断！可以对照四条标准逐一判断！标准形式是人为定义的，目标函数可以是求最小值。标准形式是人为定义的，目标函数可以是求最小值。2.用用WinQSB软件求解时，不必化成标准型。软件求解时，不必化成标准型。图解法时不必化为标
41、准型。图解法时不必化为标准型。3.单纯形法求解时一定要化为标准型。单纯形法求解时一定要化为标准型。作业：教材作业：教材P34 T 81.3 线性规划的标准型线性规划的标准型Standard form of LP下一节：基本概念下一节：基本概念1.4 线性规划的有关概念线性规划的有关概念Basic Concepts of LP 设线性规划的标准型设线性规划的标准型 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
42、 Concepts 基基 (basis)A中中mm子矩阵子矩阵B并且有并且有r（B）=m，则称则称B是线性规是线性规划的一个基（或基矩阵划的一个基（或基矩阵basis matrix）。当）。当m=n时，基矩阵唯一，时，基矩阵唯一，当当mn时，基矩阵就可能有多个，但数目不超过时，基矩阵就可能有多个，但数目不超过mnC【例例1.14】线性规划线性规划 32124maxxxxZ5,1,0226103553214321jxxxxxxxxxj 求所有基矩阵求所有基矩阵。【解解】约束方程的系数矩阵为约束方程的系数矩阵为25矩阵矩阵 10261001115A,610151B,010152B,110053B2
43、6114B10019B,12017B,02118B,16016B,06115B容易看出容易看出r(A)=2，2阶子矩阵有阶子矩阵有C52=10个，其中第个，其中第1列与第列与第3列构成列构成的的2阶矩阵不是一个基，基矩阵只有阶矩阵不是一个基，基矩阵只有9个，即个，即1.4 基本概念基本概念Basic Concepts 由线性代数知，基矩阵由线性代数知，基矩阵B必为非奇异矩阵并且必为非奇异矩阵并且|B|0。当矩当矩阵阵B的行列式等式零即的行列式等式零即|B|=0时就不是基时就不是基 当确定某一矩阵为基矩阵时，则基矩阵对应的列向量称为当确定某一矩阵为基矩阵时，则基矩阵对应的列向量称为基基向量向量(
44、basis vector)，其余列向量称为其余列向量称为非基向量非基向量 基向量对应的变量称为基向量对应的变量称为基变量基变量(basis variable)，非基向量非基向量对应的变量称为对应的变量称为非基变量非基变量 在上例中在上例中B2的基向量是的基向量是A中的第一列和第四列，其余列向量中的第一列和第四列，其余列向量是非基向量，是非基向量，x1、x4是基变量，是基变量，x2、x3、x5是非基变量。基变是非基变量。基变量、非基变量是针对某一确定基而言的，不同的基对应的基量、非基变量是针对某一确定基而言的，不同的基对应的基变量和非基变量也不同。变量和非基变量也不同。010152B102610
45、01115A1.4 基本概念基本概念Basic Concepts 可行解可行解(feasible solution)满足式（满足式（1.2）及（）及（1.3）的解）的解X=（x1,x2，xn)T 称为可行解称为可行解。基本可行解基本可行解(basis feasible solution)若基本解是可行解则称若基本解是可行解则称为是基本可行解（也称基可行解）。为是基本可行解（也称基可行解）。例如，例如，与与X=（0，0，0，3，2，），）都是例都是例1 的可行解。的可行解。TX)1,27,21,0,0(基本解基本解(basis solution)对某一确定的基对某一确定的基B，令非基变量等于零，
46、令非基变量等于零，利用式（利用式（1.）解出基变量，则这组解称为基解出基变量，则这组解称为基的基的基本解。本解。最优解最优解(optimal solution)满足式满足式 （1.1）的可行解称为最优解，）的可行解称为最优解，即是使得目标函数达到最大值的可行解就是最优解，例即是使得目标函数达到最大值的可行解就是最优解，例如可行解如可行解 是例是例2的最优解。的最优解。TX)8,0,0,0,53(非可行解非可行解(Infeasible solution)无界解无界解(unbound solution)1.4 基本概念基本概念Basic Concepts 显然，只要基本解中的基变量的解满足式（显然
47、，只要基本解中的基变量的解满足式（1.）的非负要求，）的非负要求，那么这个基本解就是基本可行解。那么这个基本解就是基本可行解。在例在例1.13中，对中，对来说，来说，x1,x2是基变量，是基变量，x3,x4，x5是非基变量，是非基变量，令令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,
48、0,0,1,52()1(1.4 基本概念基本概念Basic Concepts 由于由于 是基本解，从而它是基本可行解，在是基本解，从而它是基本可行解，在 中中x10i表表1-4(1)XBx1x2x3x4bx3211040 x4130130j3400 (2)x3x2j (3)x1 x2 j 基变量基变量110001/301/3105/31-1/3405/30-4/330103/5-1/51801-1/5 2/5400-1-1将将3化为化为1乘乘以以1/3后后得得到到1.5 单纯形法单纯形法 Simplex Method3018最优解最优解X=(18，4，0，0)T，最优值最优值Z=70O2030
49、1040(3,4)X(3)=(18,4)最优解最优解X=(18,4)最优值最优值Z=7040221xx305.121xx0,30340243max432142132121xxxxxxxxxxxxZX(1)=(0,0)2010 x2x1301.5 单纯形法单纯形法 Simplex Method0,0305.1402212121xxxxxxX(2)=(0,10)单纯形法全过程的计算，可以用列表的方法计算更为简洁，单纯形法全过程的计算，可以用列表的方法计算更为简洁，这种表格称为单纯形表（表这种表格称为单纯形表（表1.4）。）。计算步骤计算步骤：1.求初始基可行解，列出初始单纯形表，求出检验数。其中求
50、初始基可行解，列出初始单纯形表，求出检验数。其中基变量的检验数必为零；基变量的检验数必为零；2.判断：判断：（a）若）若j（j，n）得到最解；得到最解；（b）某个某个k0且且aik（i=1，2,m）则线性规划具有无则线性规划具有无界解界解(见例见例1.18)。（c）若存在若存在k0且且aik(i=1,m)不全非正，则进行换基；不全非正，则进行换基；1.5 单纯形法单纯形法 Simplex Methodmin0,0,iiLikikikikbbaaM Maa当 时为任意大的正数第第个比值最小个比值最小，选最小比值对应行的基变量为出基变量，选最小比值对应行的基变量为出基变量，若有相同最小比值，则任选
