最优化分类简介

1、线性规划的主要内容线性规划线性规划数数学学规规划划非线性规划非线性规划整数规划整数规划动态规划动态规划学学科科内内容容多目标规划多目标规划双层规划双层规划组组合合优优化化最优计数问题最优计数问题网络优化网络优化排序问题排序问题统筹图统筹图随随机机优优化化对策论对策论排队论排队论库存论库存论决策分析决策分析可靠性分析可靠性分析 许多生产计划与管理问题都可以归纳为最优许多生产计划与管理问题都可以归纳为最优化问题化问题, , 最优化模型是数学建模中应用最广泛的最优化模型是数学建模中应用最广泛的模型之一模型之一, ,其内容包括线性规划、整数线性规划、其内容包括线性规划、整数线性规划、非线性规划、动态规

2、划、变分法、最优控制等非线性规划、动态规划、变分法、最优控制等. .此类问题的一般形式为：此类问题的一般形式为：min f (x),s.t. x .目标函数 约束条件 可行解域 线性规划线性规划（Linear Programming,缩写为缩写为LP）是运筹学的重要分支之一，在实际中应用得较广是运筹学的重要分支之一，在实际中应用得较广泛，其方法也较成熟，借助计算机，使得计算更方便，泛，其方法也较成熟，借助计算机，使得计算更方便，应用领域更广泛和深入。应用领域更广泛和深入。线性规划通常研究资源的最优利用、设备最佳运线性规划通常研究资源的最优利用、设备最佳运行等问题。例如，当任务或目标确定后，如何

3、统筹兼行等问题。例如，当任务或目标确定后，如何统筹兼顾，合理安排，用最少的资源（如资金、设备、原标顾，合理安排，用最少的资源（如资金、设备、原标材料、人工、时间等）去完成确定的任务或目标；企材料、人工、时间等）去完成确定的任务或目标；企业在一定的资源条件限制下，如何组织安排生产获得业在一定的资源条件限制下，如何组织安排生产获得最好的经济效益（如产品量最多最好的经济效益（如产品量最多 、利润最大）。、利润最大）。第一章线性规划第一章线性规划第一节线性规划的基本概念第一节线性规划的基本概念第二节线性规划的标准形式和解的性质第二节线性规划的标准形式和解的性质第三节单纯形法第三节单纯形法第四节人工变量

4、法第四节人工变量法第五节线性规划应用举例第五节线性规划应用举例第一节线性规划的基本概念第一节线性规划的基本概念1.1 线性规划线性规划数学模型数学模型 (Mathematical Model of Linear Programming)【例例1.11.1】最优生产计划问题。最优生产计划问题。某企业在计划期内计划生产甲、乙、丙三种产品。某企业在计划期内计划生产甲、乙、丙三种产品。这些产品分别需要要在设备这些产品分别需要要在设备A A、B B上加工，需要消耗材上加工，需要消耗材料料C C、D D，按工艺资料规定，单件产品在不同设备上加，按工艺资料规定，单件产品在不同设备上加工及所需要的资源如表工及

5、所需要的资源如表1.11.1所示。已知在计划期内设备所示。已知在计划期内设备的加工能力各为的加工能力各为200200台时，可供材料分别为台时，可供材料分别为360360、300300公公斤；每生产一件甲、乙、丙三种产品，企业可获得利斤；每生产一件甲、乙、丙三种产品，企业可获得利润分别为润分别为4040、3030、5050元，假定市场需求无限制。企业元，假定市场需求无限制。企业决策者应如何安排生产计划，使企业在计划期内总的决策者应如何安排生产计划，使企业在计划期内总的利润收入最大？利润收入最大？1.1.1 应用模型举例应用模型举例 产品产品 资源资源 甲甲 乙乙 丙丙现有资源现有资源设备设备A

6、3 1 2 200设备设备B 2 2 4 200材料材料C 4 5 1 360材料材料D 2 3 5 300利润（元利润（元/件）件） 40 30 50表表1.1 产品资源消耗产品资源消耗321503040maxxxxZ0003005323605420042220023321321321321321xxxxxxxxxxxxxxx，【解解】设设x1、x2、x3 分别为甲、乙、丙三种产品的产量数学模型分别为甲、乙、丙三种产品的产量数学模型为：为： 产品产品 资源资源 甲甲 乙乙 丙丙现有资现有资源源设备设备A 3 1 2 200设备设备B 2 2 4 200材料材料C 4 5 1 360材料材料D

7、 2 3 5 300利润（元利润（元/件）件） 40 30 50最优解最优解X=(50,30,10);Z=3400目标函数目标函数约束条件约束条件线性规划的数学模型由线性规划的数学模型由 决策变量决策变量 Decision variables 目标函数目标函数 Objective function约束条件约束条件 Constraints构成。称为三个要素构成。称为三个要素。n其特征是：其特征是：n1解决问题的解决问题的是多个决策变量的是多个决策变量的线性线性函数，函数，通常是求最大值或通常是求最大值或 最小值；最小值；n2解决问题的解决问题的是一组多个决策变量的是一组多个决策变量的线性线性不不

8、等式或等式。等式或等式。怎样辨别一个模型是线性规划模型？怎样辨别一个模型是线性规划模型？【例例1.2】某商场决定：营业员每周连续工作某商场决定：营业员每周连续工作5天后连续休息天后连续休息2天，天，轮流休息。根据统计，商场每天至少需要的营业员如表轮流休息。根据统计，商场每天至少需要的营业员如表1.2所示。所示。表表1.2 营业员需要量统计表营业员需要量统计表商场人力资源部应如何安排每天的上班人数，使商场总的营业员商场人力资源部应如何安排每天的上班人数，使商场总的营业员最少。最少。 星期星期需要人数需要人数星期星期需要人数需要人数一一300五五480二二300六六600三三350日日550四四4

9、00【解解】 设设 xj (j=1，2，7)为休息为休息2天后星期一到星期日开始天后星期一到星期日开始上班的营业员，则这个问题的线性规划模型为上班的营业员，则这个问题的线性规划模型为 7, 2, 1, 0550600480400350300300min765436543254321743217632176521765417654321jxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxZj星星期期需要需要人数人数星星期期需要需要人数人数一一300五五480二二300六六600三三350日日550四四400目标函数：总人数最少目标函数：总人数最少约束条件：上班

10、人数大于每天需要人数约束条件：上班人数大于每天需要人数1 1 X1X10 0人人 C1=C1=404404 =300300404-300=104404-300=1042 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人人 C7C7550550 =5505

11、500 0最优解：最优解： Z617（人）（人）14567x x x x x 【例例1.3】合理用料问题。某汽车需要用甲、乙、丙三种规格的轴各一根，合理用料问题。某汽车需要用甲、乙、丙三种规格的轴各一根，这些轴的规格分别是这些轴的规格分别是1.5，1，0.7（m），这些轴需要用同一种圆钢来做，圆），这些轴需要用同一种圆钢来做，圆钢长度为钢长度为4 m。现在要制造。现在要制造1000辆汽车，最少要用多少圆钢来生产这些轴？辆汽车，最少要用多少圆钢来生产这些轴？ 【解解】这是个条材下料问题这是个条材下料问题 ，设切口宽度为零。，设切口宽度为零。 设一根圆钢切割成甲、乙、设一根圆钢切割成甲、乙、丙三种

12、轴的根数分别为丙三种轴的根数分别为y1，y2，y3,则切割方式可用不等式则切割方式可用不等式1.5y1+y2+0.7y34表表示，求这个不等式关于示，求这个不等式关于y1，y2，y3的非负整数解。象这样的非负整数解共有的非负整数解。象这样的非负整数解共有10组，也就是有组，也就是有10种下料方式，如表种下料方式，如表1.3所示。所示。表表13 下料方案下料方案 方案方案规格规格 1234 5678910需求量需求量y1(根根) 221 11 0 00001000y2 102 10 4 32101000y3 010 23 0 12451000余料（余料（m）00.30.5 0.1o.4 00.3

13、0.60.20.5设设xj ( j = 1,2,10)为第为第j种下料方案所用圆钢的根数。则用料最种下料方案所用圆钢的根数。则用料最少数学模型少数学模型 方案方案规格规格 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.5102 , 1, 010005423210002342100022min10987542987643154321101，jxxxxxxxxxxxxxxxxxxxxxZjjj求下料方案时应注意，

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

15、 9 X9X92502501010 X10X100 0Z812.5最优解：最优解：【例例1.4】配料问题。某钢铁公司生产一种合金，要求的成分规格配料问题。某钢铁公司生产一种合金，要求的成分规格是：锡不少于是：锡不少于28%，锌不多于，锌不多于15%，铅恰好，铅恰好10%，镍要界于，镍要界于35%55%之间，不允许有其他成分。钢铁公司拟从五种不同级之间，不允许有其他成分。钢铁公司拟从五种不同级别的矿石中进行冶炼，每种矿物的成分含量和价格如表别的矿石中进行冶炼，每种矿物的成分含量和价格如表1.4所示。所示。矿石杂质在治炼过程中废弃，现要求每吨合金成本最低的矿物数矿石杂质在治炼过程中废弃，现要求每吨

16、合金成本最低的矿物数量。假设矿石在冶炼过程中，合金含量没有发生变化。量。假设矿石在冶炼过程中，合金含量没有发生变化。表表1.4 矿石的金属含量矿石的金属含量 合金合金矿石矿石锡锡%锌锌%铅铅%镍镍%杂质杂质费用（元费用（元/t ）125101025303402400030302603015520601804202004020230585151755190解解: 设设xj（j=1,2，5）是第）是第j 种矿石数量，得到下列线性规划模种矿石数量，得到下列线性规划模型型 矿石矿石锡锡%锌锌%铅铅%镍镍%杂质杂质费用（元费用（元/t ）125101025303402400030302603015520

17、6018042020040202305851517551901234512451345135123451234512min3402601802301900.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,5jxxxxj注意，矿石在实际冶炼时金属含量会发生变化，建模注意，矿石在实际冶炼时金属含量会发生变化，建模时应将这种变化考虑进去，有可能是非线性关系。配时

18、应将这种变化考虑进去，有可能是非线性关系。配料问题也称配方问题、营养问题或混合问题，在许多料问题也称配方问题、营养问题或混合问题，在许多行业生产中都能遇到。行业生产中都能遇到。1 1 X1X10 02 2 X2X20.33330.33333 3 X3X30 04 4 X4X40.58330.58335 5 X5X50.66670.6667最优解：最优解： Z=347.5第五年：第五年：(x7/2+x9)=x8+2x5第一年：第一年：x1+x2=200(万元万元)第二年：第二年：(x1/2 +x3)+x4=x2第三年第三年(x3/2+x5)+x6=x4+2x1第四年：第四年：(x5/2+x7)+

19、x8=x6+2x3到第六年实有资金总额为到第六年实有资金总额为x9+2x7，整理后得到下列线性规划模型，整理后得到下列线性规划模型 【解解】设设 x1：第一年的投资；：第一年的投资； x2：第一年的保留资金：第一年的保留资金 x3：第二年新的投资；：第二年新的投资； x4：第二年的保留资金：第二年的保留资金 x5：第三年新的投资；：第三年新的投资； x6：第三年的保留资金：第三年的保留资金 x7：第四年新的投资：第四年新的投资 x8：第四年的保留资金：第四年的保留资金 x9：第五年的保留资金：第五年的保留资金【例例1.5】投资问题。某投资公司在第一年有投资问题。某投资公司在第一年有200万元资

20、金，每年万元资金，每年都有如下的投资方案可供考虑采纳：都有如下的投资方案可供考虑采纳：“假使第一年投入一笔资金，假使第一年投入一笔资金，第二年又继续投入此资金的第二年又继续投入此资金的50%，那么到第三年就可回收第一年，那么到第三年就可回收第一年投入资金的一倍金额投入资金的一倍金额”。投资公司决定最优的投资策略使第六年。投资公司决定最优的投资策略使第六年所掌握的资金最多。所掌握的资金最多。7912123413456356785789max22002220422204222042200,1,2,9jZxxxxxxxxxxxxxxxxxxxxxxxj1 1 X1X155.284655.28462

21、2 X2X2144.7155144.71553 3 X3X3117.0732117.07324 4 X4X40 05 5 X5X552.032552.03256 6 X6X60 07 7 X7X7208.1301208.13018 8 X8X80 09 9 X9X90 0最优解：最优解：Z 416.26万元万元x1：第一年的投资；：第一年的投资； x2：第一年的保留资金：第一年的保留资金 x3：第二年新的投资；：第二年新的投资；x4：第二年的保留资金：第二年的保留资金 x5：第三年新的投资；：第三年新的投资； x6：第三年的保留资金：第三年的保留资金 x7：第四年新的投资：第四年新的投资 x8

22、：第四年的保留资金：第四年的保留资金 x9：第五年的保留资金：第五年的保留资金【例例1.6】均衡配套生产问题。某产品由均衡配套生产问题。某产品由2件甲、件甲、3件乙零件组装而成。件乙零件组装而成。两种零件必须经过设备两种零件必须经过设备A、B上加工，每件甲零件在上加工，每件甲零件在A、B上的加工时上的加工时间分别为间分别为5分钟和分钟和9分钟，每件乙零件在分钟，每件乙零件在A、B上的加工时间分别为上的加工时间分别为4分分钟和钟和10分钟。现有分钟。现有2台设备台设备A和和3台设备台设备B，每天可供加工时间为，每天可供加工时间为8小时。小时。为了保持两种设备均衡负荷生产，要求一种设备每天的加工总

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

24、xxxx（目标函数线性化。产品的产量目标函数线性化。产品的产量y等价于等价于2131,21xyxy整理得到线性规划模型整理得到线性规划模型 约束线性化。将绝对值约束写成两个不等式约束线性化。将绝对值约束写成两个不等式60)109()45(60)109()45(21212121xxxxxxxx121212121212m a x1213549 6 091 01 4 4 0466 0466 00Zyyxyxxxxxxxxxyxx、【例例1.7】（饼干生产问题）某厂生产两类饼干，需搅拌机（饼干生产问题）某厂生产两类饼干，需搅拌机A1，成形，成形机机A2 ，烘箱，烘箱A3三种设备，每天的所需机时及机时限

25、制，利润指标如下三种设备，每天的所需机时及机时限制，利润指标如下表，问如何制订生产计划，可使获得最高利润？表，问如何制订生产计划，可使获得最高利润？【解解】 设设x1、x2为每天生产为每天生产 、 两种饼干的产量（单位：吨），则两种饼干的产量（单位：吨），则目标函数是目标函数是产品资源产品资源每天现每天现有工时有工时搅拌机搅拌机A13515成形机成形机A2215烘箱烘箱A32211利润利润/（百元（百元/吨）吨）54 12max 54zxx约束条件有：约束条件有：搅拌机约束搅拌机约束成形机约束成形机约束烘箱约束烘箱约束非负约束非负约束123515xx1225xx122211xx120 xx ，

26、本问题的数学模型本问题的数学模型1212121212max 54. 5415 25 2211 0,0zxxstxxxxxxxx【例例1.8】（运输问题）总公司收到上海（运输问题）总公司收到上海B1，青岛，青岛B2 ，西安，西安B3三家商三家商场的电机订单，需求分别为场的电机订单，需求分别为100台，台，80台，台，90-120台，现有北京台，现有北京A1，武，武汉汉A2二个仓库，库存分别为二个仓库，库存分别为200台，台，150台，所需运费如下表，问如何台，所需运费如下表，问如何调运电机，可使总运费最少？调运电机，可使总运费最少？ B1B2B3库存库存A1152118200A220251615

27、0需求需求1008090-120 【解解】 设设 xij 为从仓库为从仓库 Ai 调到商场调到商场 Bj 的电机数量（的电机数量（i=1,2, j=1,2,3），），则目标函数是则目标函数是111231212223min 152118202516zxxxxxx库存约束库存约束需求约束需求约束非负约束非负约束111213200 xxx1121100 xx0, (1,2 ; 1,2,3)ijxij问题的数问题的数学模型学模型212223150 xxx12220 xx8132390 xx1323120 xx1112132122231112132122231121122213231323min 152

28、118202516. 200 150 100, 80 90, 120 0ijzxxxxxxstxxxxxxxxxxxxxxx小结：建立线性规划数学模型小结：建立线性规划数学模型建立数学模型是学习线性规划的第一步也是建立数学模型是学习线性规划的第一步也是关键的一步。关键的一步。建立正确的数学模型要掌握建立正确的数学模型要掌握3个要素：个要素：研究的问题是求什么，即设置决策变量；研究的问题是求什么，即设置决策变量；问题要达到的目标是什么，即建立目标函数，问题要达到的目标是什么，即建立目标函数，目标函数一定是决策变量的线性函数并且求最大目标函数一定是决策变量的线性函数并且求最大值或求最小值；值或求最

29、小值；限制达到目标的条件是什么，即建立约束条件。限制达到目标的条件是什么，即建立约束条件。线性规划的一般形式为：线性规划的一般形式为：1 12211 11221121 1222221 12212max(min)( , )( , ) ( , ),0nnnnnnmmmnnmnzc xc xc xa xa xa xba xa xa xba xaxa xbx xx 变量变量x1，x2，xn称为决策变量，目标函数中变量系数称为决策变量，目标函数中变量系数cj，称为价值系数，称为价值系数，bi称为右端常数，约束条件（称为右端常数，约束条件（1-3）称为非负约束，）称为非负约束，（1-2）称为技术约束，系数

30、）称为技术约束，系数aij称为技术系数。满足全部约束条件称为技术系数。满足全部约束条件的变量值（的变量值（x1，xn）称为）称为可行解可行解，可行解的集合称为可行域，可行解的集合称为可行域，记为记为R；使目标函数取得最大（最小）值的可行解（；使目标函数取得最大（最小）值的可行解（x1，xn）称为称为最优解最优解。 （1-31-3）（1-21-2）（1-11-1）采用求和符号采用求和符号，线性规划的一般形式，线性规划的一般形式可以可以简写为：简写为：11max(min)( , ) 1,2, 0 1,2,njjjnijjijjzc xa xbimxjn 用向量形式可表示为：用向量形式可表示为：11

31、max(min)( , )b ,0njjjnzCXP xxx 用矩阵和向量形式用矩阵和向量形式表示为：表示为：max(min)( , )b 0zCXAXX 式中：式中：X=（x1，x2，xn）TC=（c1，c2，cn）b=（b1，b2，bm）TA=（aij）mn Pj=（a1j，a2j，amj）T 二、图解法二、图解法 当决策变量个数当决策变量个数n=2时，时，LP问题可以通过在问题可以通过在平面上作图的方法求解，称为图解法。平面上作图的方法求解，称为图解法。图解法求解的目的：图解法求解的目的：1.1.判别线性规划问题的求解结局。判别线性规划问题的求解结局。2.2.在存在最优解的条件下，把问题

32、的最优解找出来。在存在最优解的条件下，把问题的最优解找出来。 【例例1-41-4】 求下列问题的最优解。求下列问题的最优解。121212212max25 285220 412,0zxxxxxxxxx（1 1）确定问题的可行域）确定问题的可行域R R。x2x1Q4Q3Q2Q1l1l2l3123456图图1-11-11 123405可行域可行域R是凸多角形是凸多角形OQ1Q2Q3Q4121212212max25 285220 412,0zxxxxxxxxx（2 2）分析目标函数）分析目标函数Z的等值线平行移动与的等值线平行移动与Z值的关系，确定最优解的位置。值的关系，确定最优解的位置。当当z取定值

33、时，方程取定值时，方程z=2x1+5x2或或x2=2/5x1+z/5表示一条斜率为表示一条斜率为2/5的直线的直线 l ， 称为称为z的等值线，它在的等值线，它在x2轴上的截距为轴上的截距为z/5。当。当l向右向右上方平行移动且保持与上方平行移动且保持与R有共同部分时，有共同部分时，z值不值不断上升，由于断上升，由于l的斜率为的斜率为2/5，因此当，因此当l向右上向右上方平移的过程中，与方平移的过程中，与R最后的公共点是最后的公共点是Q3，z在在Q3达到最大值。达到最大值。 121212212max25 285220 412,0zxxxxxxxxx（3 3）计算最优解。）计算最优解。点点Q3是

34、直线是直线l1与与l3的交点，它的坐标由方程组的交点，它的坐标由方程组124 82221xxx 决定，从中解得决定，从中解得x1=2，x2=3。这就是问题的最优。这就是问题的最优解，相应的目标函数值解，相应的目标函数值z=2253=19。最优产。最优产量计划是量计划是P，Q分别生产分别生产2个与个与3个单位，最大产值个单位，最大产值为为19万元。这时原料万元。这时原料A与与C用完，用完，B剩余剩余4吨。吨。 121212212max25 285220 412,0zxxxxxxxxx线性规划问题求解的几种可能结局：线性规划问题求解的几种可能结局：1.唯一最优解：如上例。唯一最优解：如上例。2.无

35、穷多最优解：如无穷多最优解：如Z换成换成maxZ=2X1+4X2,，此时最，此时最优解在线段优解在线段Q2Q3 上达到，有无穷多最优解。上达到，有无穷多最优解。已求得已求得Q3的坐标为（的坐标为（2，3）；）；Q2坐标由方程组坐标由方程组2025822121xxxx决定，从中解得决定，从中解得x1=3，x2=5/2。设，设， ，线段，线段Q2Q3上的点可用上的点可用X1+（1）X2（01）表示。因此，）表示。因此，X1+（1）X2（01）是问题的全部最优解。）是问题的全部最优解。 321X2/53 2X3.3.无界解无界解如约束条件只保留第如约束条件只保留第3个，即个，即4X212，这，这时可

36、行域无界，时可行域无界，Z值可无限上升，无最优解，值可无限上升，无最优解，简称无界解，即有可行解，但目标函数值无解。简称无界解，即有可行解，但目标函数值无解。产生原因：是由于在建立实际问题的数学产生原因：是由于在建立实际问题的数学模型中遗漏了某些必要的资源约束条件。模型中遗漏了某些必要的资源约束条件。121212212max25 285220 412,0zxxxxxxxxx4.4.无解或无可行解无解或无可行解可行域是空集，问题无可行解，当然更无最优解。可行域是空集，问题无可行解，当然更无最优解。图解法得到的启示图解法得到的启示1.1.求解线性规划问题时，解的情况有：唯一最优求解线性规划问题时，

37、解的情况有：唯一最优解、无穷多最优解、无界解和无可行解。解、无穷多最优解、无界解和无可行解。2.2.若线性规划问题的可行域存在，则可行域是一若线性规划问题的可行域存在，则可行域是一凸集。凸集。3.3.若线性规划问题的最优解存在，则最优解一定若线性规划问题的最优解存在，则最优解一定在某个顶点可达到。在某个顶点可达到。4.4.解题思路是：先找出凸集的任一顶点，计算解题思路是：先找出凸集的任一顶点，计算Z Z值，比较相邻顶点值，比较相邻顶点Z Z值，如大，转到相邻顶点，值，如大，转到相邻顶点，一直到找出使一直到找出使Z Z值最大的顶点为止。值最大的顶点为止。第二节第二节 线性规划的标准形式和线性规划

38、的标准形式和解的性质解的性质 一、一、 LP的标准形式的标准形式11max 1,2, 0 1,2,njjjnijjijjzc xa xbimxjn称为线性规划问题的标准形式（其中右端常数称为线性规划问题的标准形式（其中右端常数b1，b2，bm0）。）。 线性规划标准形式的特点：线性规划标准形式的特点：1. 1. 技术约束条件全部是等式约束技术约束条件全部是等式约束2. 2. 目标函数限定求最大值目标函数限定求最大值变换一般变换一般LPLP为标准形式的方法：为标准形式的方法：（1 1）如果原问题目标函数求极小值：）如果原问题目标函数求极小值： 1minnjjjzc x令令z1=z，转化为求。，转

39、化为求。（2）若某个右端常数）若某个右端常数bi0时，时，xj为入基变量为入基变量。 miijijjacc12.2.单纯形表单纯形表 表1-5 jcnmmcccc11BcBXbmcc 1mxx 1mbb 1nmmxxxx 11im 1mnmmnmaaaa1,11, 110010 01mjjiijjcc aj总结 从表中可以直接读出基可行解从表中可以直接读出基可行解X：xi=bi（i=1，m），），其它其它xj=0； 相应目标函数值相应目标函数值，是是CB列与列与b列元素列元素乘积之和；乘积之和； 每个变量每个变量xj（包括基变量在内）的检验数包括基变量在内）的检验数j，等于等于cj减去减去CB

40、列元素与表中列元素与表中xj的系数列向量元素乘积之和的系数列向量元素乘积之和。 单纯形法的全部分析和计算过程，可以比较方便地单纯形法的全部分析和计算过程，可以比较方便地在单纯形表中完成。在单纯形表中完成。1miiizc b3. 3. 单纯形法的基本法则单纯形法的基本法则 法则法则1 1 最优性判定法则最优性判定法则若对基可行解若对基可行解X1，所有检验数，所有检验数j0（求最大值时），则（求最大值时），则X1为最优解。为最优解。 法则法则2 2 入基变量确定法则入基变量确定法则（最大价值系数法则）（最大价值系数法则）设，则设，则xk为换入变量。为换入变量。 0maxjjjk法则法则3 3 出基

41、变量确定法则出基变量确定法则 （最小比值法则）（最小比值法则）设设xk为换入变量，并设为换入变量，并设则最小比值所在行的原基变量则最小比值所在行的原基变量xl为为换换出变量。出变量。 lklikikiiabaab0min法则法则4 4 换基迭代运算法则换基迭代运算法则 对方程组的增广矩阵实施行的初等对方程组的增广矩阵实施行的初等变换，使主元变换，使主元alk化为化为1，主元列其它元素，主元列其它元素化为化为0。具体地说，第。具体地说，第l行乘以行乘以1/alk，并将，并将第第l行的行的aik/alk倍加到第倍加到第i行上去，行上去，i=1，2，m，il。 可将这些重要结论的计算设计成如下一个简

42、单的表格，可将这些重要结论的计算设计成如下一个简单的表格，即单纯形表来完成：即单纯形表来完成：C CBCN CB XB b X1 X2 Xm X m+1 Xm+2 Xn C1C2.Cm X1X2 .Xm b1b2.bm I I N 12.m Z CBb 0 CN- - CBN 例例1 1、试利用单纯形表线性规划的最优解解：、试利用单纯形表线性规划的最优解解：得初始的单纯形表：得初始的单纯形表：C = (5 ,2 ,3 ,1,1)122108(Ab)=341017123451234123512345maxZ=5x2x3xxxx2x2xx83x4xxx7 x ,x ,x ,x ,x0NNB=C-C

43、 NBZ=C b初始基本可行解，初始基本可行解，Z= Z= -1-1，X = (0,0,0,8, 7 )T 1 2 2 1 08x4-1 3 0 4 0 0-1Z 3 4 1 0 17x51 x1 x2 x3 x4 x5bXBCB 5 2 3 -1 1C换入变量，换出变量，为主元进行旋转变换换入变量，换出变量，为主元进行旋转变换3x4x基本可行解，基本可行解，Z= 15Z= 15，X = (0,0,4, 0, 3)T1/2 1 1 1/2 04x33 1 -4 0 -2 015Z5/2 3 0 -1/2 13x51 x1 x2 x3 x4 x5bXBCB 5 2 3 -1 1C 1 2 2 1

44、 08x4-1 3 0 4 0 0-1Z 3 4 1 0 17x51 x1 x2 x3 x4 x5bXBCB 5 2 3 -1 1C8/27/1最优解最优解 最优值最优值 617X,0,0,055T换入变量，换出变量，换入变量，换出变量，/ /为主元进行旋转变换为主元进行旋转变换1x5xNNB=C-C N081Z54/1/21/2 1 1 1/2 04x33 1 -4 0 -2 015Z3/5/25/2 3 0 -1/2 13x51x1 x2 x3 x4 x5bXBCB 5 2 3 -1 1C 0 2/5 1 3/5 -1/517/5x33 0 -26/5 0 -9/5 -2/581/5Z 1

45、 6/5 0 -1/5 2/56/5x15 x1 x2 x3 x4 x5bXBCB 5 2 3 -1 1C三、三、 关于单纯形法的补充说明关于单纯形法的补充说明 1. 1. 无穷多最优解与唯一最优解的判别法则无穷多最优解与唯一最优解的判别法则若对某可行解若对某可行解X1，（1）所有检验数）所有检验数j0，且有一个非基变量，且有一个非基变量xk的检验数等于的检验数等于0，则问题有无穷多最优解；，则问题有无穷多最优解；（2）所有非基变量的检验数）所有非基变量的检验数j0，但，但aik0，i=1，2，m即即xk的系数列向量无正分量，则问题无的系数列向量无正分量，则问题无最优解。最优解。 如上例中，如

46、上例中， 111a 3. 3. 求求min min z z 的情况的情况 这时可以有两种处理方式：这时可以有两种处理方式： 一种方式是令一种方式是令z1=z，转化为求，转化为求max z1， 另一种是直接计算。另一种是直接计算。v最优性检验条件改为：所有最优性检验条件改为：所有j0；v换入变量确定法则改为：如果换入变量确定法则改为：如果则则xk为换入变量。为换入变量。v单纯形法的其它要点完全无须改变。单纯形法的其它要点完全无须改变。 min0jjkj 例一例一求下列求下列LP问题的最优解问题的最优解 121231242512345max 25 2 852 20 4 12,0zxxxxxxxxx

47、xx x x x x例二例二求下列求下列LP问题的最优解问题的最优解 23512352342356123456max 323 2 7 24 12 43 810,0zxxxxxxxxxxxxxxx x x x x x 例三例三求下列求下列LP问题的最优解问题的最优解 12341341241234max 2 1 20,0zxxxxxxxxxxx x x x第四节第四节 初始可行基的求法初始可行基的求法人工变量法人工变量法 大大M法法首先将线性规划问题化为标准型。如果约束方程首先将线性规划问题化为标准型。如果约束方程组中包含有一个单位矩阵组中包含有一个单位矩阵I，那么已经得到了一个初始可，那么已经得

48、到了一个初始可行基。否则在约束方程组的左边加上若干个非负的人工行基。否则在约束方程组的左边加上若干个非负的人工变量，使人工变量对应的系数列向量与其它变量的系数变量，使人工变量对应的系数列向量与其它变量的系数列向量共同构成一个单位矩阵。以单位矩阵为初始基，列向量共同构成一个单位矩阵。以单位矩阵为初始基，即可求得一个初始的基本可行解。即可求得一个初始的基本可行解。 为了求得原问题的初始基本可行解，必须尽快通过迭为了求得原问题的初始基本可行解，必须尽快通过迭代过程把人工变量从基变量中替换出来成为非基变量。代过程把人工变量从基变量中替换出来成为非基变量。为此可以在目标函数中赋予人工变量一个绝对值很大的

49、为此可以在目标函数中赋予人工变量一个绝对值很大的负系数负系数-。这样只要基变量中还存在人工变量，目标函。这样只要基变量中还存在人工变量，目标函数就不可能实现极大化。数就不可能实现极大化。 以后的计算与单纯形表解法相同，只需认定是一个以后的计算与单纯形表解法相同，只需认定是一个很大的正数即可。假如在单纯形最优表的基变量中还包很大的正数即可。假如在单纯形最优表的基变量中还包含人工变量，则说明原问题无可行解。否则最优解中剔含人工变量，则说明原问题无可行解。否则最优解中剔除人工变量的剩余部分即为原问题的初始基本可行解。除人工变量的剩余部分即为原问题的初始基本可行解。例例2 2、用大、用大M M法求解下

50、面的线性规划问题法求解下面的线性规划问题: :解：解： 首先将原问题化为标准型首先将原问题化为标准型添加人工变量，并在目标函数中分别赋予添加人工变量，并在目标函数中分别赋予- - 121212212maxZ=-x +2xxx2 -xx1 x3 x ,x012312425j xx -x 2-xx -x 1 x x3 x0,j1,2,3,4,512671236124725jmaxZ= -x +2x -Mx -Mx xx -x x 2 -xx -x x1 x x 3 x0,j1,2,3,4,5,6,767x ,x- 0 1 -1/2 -1/2 0 1/2 1/23/2X22 1 0 -1/2 1/2

51、 0 1/2 -1/21/2X1-1- -1 1 0 -1 0 0 11X221/2 2 0 -1 1 0 1 -11X6-M1/1 -1 1 0 -1 0 0 11X7-M2/1 1 1 -1 0 0 1 02X6-M 0 0 1/2 3/2 0 -1/2-M -3/2-M5/2Z 0 0 1/2 1/2 1 -1/2 -1/23/2X50 1+2M 0 -M 2+M 0 0 -2-2M2-MZ2/1 1 0 0 1 1 0 -12X50 -1 2+2M -M -M 0 0 0-3MZ3/1 0 1 0 0 1 0 03X50 X1 x2 x3 x4 x5 x6 x7bXBCB -1 2 0

52、 0 0 -M -MC 0 1 0 0 1 0 03X22 1 0 0 1 1 0 -12X40 1 1 -1 0 0 1 02X22 2 0 -1 1 0 1 -11X40- 0 1 -1/2 -1/2 0 1/2 1/23/2X221/2/1/2 1 0 -1/2 1/2 0 1/2 -1/21/2X1-1 -1 0 0 0 -2 -M -M6Z -1 0 1 0 1 -1 01X30 -3 0 2 0 0 -2-M -M4Z -1 0 1 0 1 -1 01X50 0 0 1/2 3/2 0 -1/2-M -3/2-M5/2Z3/2 /1/2 0 0 1/2 1/2 1 -1/2 -1/23/2X50 X1 x2 x3 x4 x5 x6 x7bXBCB -1 2 0 0 0 -M -MC最优解最优解 最优值最优值X0,3,1,2,0TZ6M是个很大的正数，因为是对目标函数实现最大化，因此人工变量必须从基变量中迅速换出去，否则目标函数不可能实现最大化n两阶段法两阶段法 两阶段法引入人工变量的目的和原则与大两阶段法引入人工变量的目的和原则与大M M法相同，所不同的是法相同，所不同的是处理人工变量的方法。处理人工变量的方法。两阶段法的步骤：两阶段法的步骤：l 求解一个辅助线性规划。目标