第二章 线性规划

1、第一章第一章 线性规划线性规划LINEAR PROGRAMMINGLINEAR PROGRAMMING本章的主要内容本章的主要内容一般线性规划问题的数学模型一般线性规划问题的数学模型图解法图解法单纯形法原理单纯形法原理单纯形法的计算步骤单纯形法的计算步骤单纯形法的进一步讨论单纯形法的进一步讨论数据包络分析数据包络分析 School of Management Harbin Institute of Technology 2线性规划问题的数学模型线性规划问题的数学模型规划问题规划问题生产和经营管理中经常提出如何合理安排，使人力、物力等资源得到充分利用，获得最大的效益，这就是规划问题线性规划通常解

2、决以下两类问题线性规划通常解决以下两类问题当任务和目标确定后，如何统筹兼顾，合理安排，用最少的资源去完成确定的任务和目标在一定的资源限制下，如何组织安排生产获得最好的经济效益School of Management Harbin Institute of Technology 3线性规划问题的数学模型线性规划问题的数学模型School of Management Harbin Institute of Technology 4线性规划问题的数学模型线性规划问题的数学模型 例子例子1.2 1.2 某企业计划生产甲，乙两种产品。这两某企业计划生产甲，乙两种产品。这两种产品需要在种产品需要在A A，

3、B B，C C三种不同的设备上进行三种不同的设备上进行加工。按工艺需求，加工各种产品所需每种设加工。按工艺需求，加工各种产品所需每种设备的单位工时如下表所示，问如何安排生产计备的单位工时如下表所示，问如何安排生产计划，使企业的总利润最大？划，使企业的总利润最大？School of Management Harbin Institute of Technology 5ABC甲甲2402乙乙2053121615线性规划问题的数学模型线性规划问题的数学模型School of Management Harbin Institute of Technology 6线性规划问题的数学模型线性规划问题的数学

4、模型线性规划的数学模型由以下三个要素线性规划的数学模型由以下三个要素决策变量决策变量 decision variabledecision variable目标函数目标函数 objective functionobjective function约束条件约束条件 constrainsconstrains线性规划问题的辨别线性规划问题的辨别目标函数是多个决策变量的线性函数，取最大值或最小值约束条件是一组多个决策变量的线性不等式或等式School of Management Harbin Institute of Technology 7线性规划问题的数学模型线性规划问题的数学模型School of

5、 Management Harbin Institute of Technology 8线性规划问题的数学模型线性规划问题的数学模型School of Management Harbin Institute of Technology 9线性规划问题的数学模型线性规划问题的数学模型标准形式的转换标准形式的转换目标函数的转换目标函数的转换无约束决策变量的转换无约束决策变量的转换约束方程的转换约束方程的转换 松弛变量松弛变量 剩余变量剩余变量非正决策变量的转换非正决策变量的转换School of Management Harbin Institute of Technology 10线性规划问题的

6、数学模型线性规划问题的数学模型School of Management Harbin Institute of Technology 11线性规划问题的数学模型线性规划问题的数学模型School of Management Harbin Institute of Technology 12School of Management Harbin Institute of Technology 13线性规划数学模型假设线性规划数学模型假设（1 1）比例性）比例性（2 2）可叠加性）可叠加性（3 3）可分性）可分性（4 4）确定性）确定性School of Management Harbin Ins

7、titute of Technology 14构建构建线性规划数学模型线性规划数学模型（1 1）分析问题：确定决策内容、要实）分析问题：确定决策内容、要实现的目标以及所受到的限制条件。现的目标以及所受到的限制条件。（2）具体构造模型：选择合适的决策具体构造模型：选择合适的决策变量、确定目标函数的表达式、约变量、确定目标函数的表达式、约束条件的表达式，分析各变量取值束条件的表达式，分析各变量取值的符号限制。的符号限制。School of Management Harbin Institute of Technology 15构建构建线性规划数学模型线性规划数学模型例例1：某工厂在生产过程中需要使

8、用浓度为：某工厂在生产过程中需要使用浓度为80%的硫酸的硫酸100 吨，而市面上只有浓度为吨，而市面上只有浓度为30%，45%，73%，85%，92%的硫酸出售，的硫酸出售， 每吨的价格每吨的价格分别为分别为400、700、1400、1900和和2500元。元。 问：问：采用怎样的购买方案，才能使所需总费用最小？采用怎样的购买方案，才能使所需总费用最小？School of Management Harbin Institute of Technology 16构建构建线性规划数学模型线性规划数学模型例例2：设有下面四个投资机会：设有下面四个投资机会： 甲：在三年内，投资人应在每年年初投资，每年

9、每元投甲：在三年内，投资人应在每年年初投资，每年每元投资可获利资可获利0.2元，每年取息后可重新将本息用于投资。元，每年取息后可重新将本息用于投资。 乙：在三年内，投资人应在第一年年初投资，每两年每乙：在三年内，投资人应在第一年年初投资，每两年每元投资可获利元投资可获利0.5元，两年后取息，取息后可重新将本息用元，两年后取息，取息后可重新将本息用于投资。这种投资最多不得超过于投资。这种投资最多不得超过20,000元。元。 丙：在三年内，投资人应在第二年年初投资，两年后每丙：在三年内，投资人应在第二年年初投资，两年后每元投资可获利元投资可获利0.6元。这种投资最多不得超过元。这种投资最多不得超过

10、15,000元。元。 丁：在三年内，投资人应在第三年年初投资，一年后每丁：在三年内，投资人应在第三年年初投资，一年后每元投资可获利元投资可获利0.4元。这种投资最多不得超过元。这种投资最多不得超过10,000元。元。 假定在这三年为一期的投资中，每期的开始有假定在这三年为一期的投资中，每期的开始有30,000元元资金可供使用，问：采取怎样的投资计划，才能在第三年资金可供使用，问：采取怎样的投资计划，才能在第三年年底获得最大收益？年底获得最大收益？School of Management Harbin Institute of Technology 17构建构建线性规划数学模型线性规划数学模型例

11、例3：合理下料：合理下料问题问题： ： 要制作要制作100套套钢钢筋架子，每套含筋架子，每套含2.9米、米、2.1米、米、1.5米的米的钢钢筋各一根。已知原料筋各一根。已知原料长长7.4米，米，问问：如何下料，使用料最：如何下料，使用料最省？省？方案方案下料数下料数长长度度2.9米米2.1米米1.5米米121221 3123合合计计(米米)7.47.37.27.16.6料料头头(米米)00.10.20.30.8School of Management Harbin Institute of Technology 18思考思考题题： ：目目标标函数是否可以函数是否可以选选取取为为 min z=x

12、1+x2+x3+x4+x5 ， ，为为什么？什么？构建构建线性规划数学模型线性规划数学模型School of Management Harbin Institute of Technology 19构建构建线性规划数学模型线性规划数学模型例例4 4：有：有A A、 、B B两种两种产产品，都需要品，都需要经过经过前、后两到化学反前、后两到化学反应过应过程。每种程。每种产产品需品需要的反要的反应时间应时间及其可供使用的及其可供使用的总时间总时间如表示。如表示。 每生每生产产一个一个单单位位产产品品B B的同的同时时，会，会产产生生2 2个个单单位的副位的副产产品品C C，且不需，且不需外加任何外

13、加任何费费用。副用。副产产品品C C的一部分可以出售盈利，其余的只能加以的一部分可以出售盈利，其余的只能加以销毁销毁。 。 副副产产品品C C每每卖卖出一个出一个单单位可位可获获利利3 3元，但是如果元，但是如果卖卖不出去，不出去，则则每每单单位需位需销毁费销毁费用用2 2元。元。预测预测表明，最多可售出表明，最多可售出5 5个个单单位的副位的副产产品品C C。 。 要求确定使利要求确定使利润润最大的最大的生生产计产计划。划。线性规划问题的数学模型线性规划问题的数学模型线性规划问题的解线性规划问题的解求解线性规划问题，就是从满足约束条件（2）（3）的解中找出一个解，使目标函数（1）达到最大值S

14、chool of Management Harbin Institute of Technology 20线性规划问题的数学模型线性规划问题的数学模型School of Management Harbin Institute of Technology 21线性规划问题的数学模型线性规划问题的数学模型 基解：某一确定的基基解：某一确定的基B B，零非基变量等于零，由约束条，零非基变量等于零，由约束条件方程（件方程（2 2）解出基变量，称这组解为基解。在基解中）解出基变量，称这组解为基解。在基解中，变量取非零的个数不大于方程数，变量取非零的个数不大于方程数m m。 基可行解：满足变量非负约束的基

15、解称为基可行解。基可行解：满足变量非负约束的基解称为基可行解。 可行基：对应于基可行解的基称为可行基。可行基：对应于基可行解的基称为可行基。School of Management Harbin Institute of Technology 22线性规划问题的数学模型线性规划问题的数学模型有解，或无解有解，或无解解就在那里解就在那里可行才是关键可行才是关键最优，或不优最优，或不优答案就在那里答案就在那里顶点才能发现顶点才能发现School of Management Harbin Institute of Technology 23线性规划问题的数学模型线性规划问题的数学模型School o

16、f Management Harbin Institute of Technology 24线性规划问题的数学模型线性规划问题的数学模型基基基解基解是基可行解？是基可行解？ 目目标标函数函数x1x2x3x4x5P1P2P343-200否17P1P2P433040是15*P1P2P542005是14P1P3P5404015是8P1P4P5600-815否12P2P3P4036160是9P2P4P506016-15否18P3P4P500121615是0School of Management Harbin Institute of Technology 25图解法图解法线性规划求解方法线性规划求解

17、方法图解法单纯形法对于只有两个决策变量的线性规划问对于只有两个决策变量的线性规划问题，可以通过图解的方法求解。图解题，可以通过图解的方法求解。图解法简单直观，有助于我们理解线性规法简单直观，有助于我们理解线性规划求解的基本原理和几何意义。划求解的基本原理和几何意义。School of Management Harbin Institute of Technology 26图解法图解法School of Management Harbin Institute of Technology 27图解法图解法School of Management Harbin Institute of Techno

18、logy 28图解法图解法 线性规划问题的解：唯一最优解、无穷多最线性规划问题的解：唯一最优解、无穷多最优解、无界解、无可行解优解、无界解、无可行解 若线性规划问题的可行域存在，则该可行域若线性规划问题的可行域存在，则该可行域是一个凸集是一个凸集 若若LPLP的最优解存在，则最优解或最优解之一的最优解存在，则最优解或最优解之一一定能够在可行域（凸集）的某个顶点找到一定能够在可行域（凸集）的某个顶点找到 解题思路是先找到凸集中的任意一点，计算解题思路是先找到凸集中的任意一点，计算目标函数值，与周边相邻顶点目标函数进行目标函数值，与周边相邻顶点目标函数进行比较比较School of Managem

19、ent Harbin Institute of Technology 29单纯形法原理单纯形法原理School of Management Harbin Institute of Technology 30单纯形法原理单纯形法原理School of Management Harbin Institute of Technology 31单纯形法原理单纯形法原理School of Management Harbin Institute of Technology 32单纯形法原理单纯形法原理School of Management Harbin Institute of Technology 3

20、3单纯形法原理单纯形法原理可行解聚成凸集可行解聚成凸集向量独立方为基向量独立方为基顶点对应基可行顶点对应基可行最优需到基中寻最优需到基中寻School of Management Harbin Institute of Technology 34单纯形法原理单纯形法原理School of Management Harbin Institute of Technology 35单纯形法原理单纯形法原理 从初始基可行解转换为另一基可行解从初始基可行解转换为另一基可行解 最优解检验和解的判断最优解检验和解的判断 所有检验数不大于零，对应的基可行解为最优解 所有检验数不大于零，并且某个非基变量的检验数

21、等于零，则该问题有无穷多最优解； 如果某个检验数大于零，并且其对应的约束条件系数向量的所有分量均不大于零，则该问题存在无界解。School of Management Harbin Institute of Technology 36单纯形法原理单纯形法原理检验主要看贡献检验主要看贡献系数比较成关键系数比较成关键目系减去基系权目系减去基系权收益不增方清闲收益不增方清闲另一非基无增减另一非基无增减只要可行无穷钱只要可行无穷钱就怕有个冒头鸟就怕有个冒头鸟处处作对解无边处处作对解无边School of Management Harbin Institute of Technology 37单纯形法计

22、算步骤单纯形法计算步骤 求出线性规划的初始基可行解，列出初求出线性规划的初始基可行解，列出初始单纯形表始单纯形表 进行最优性检验进行最优性检验 从一个基可行解转换到另一个目标函数从一个基可行解转换到另一个目标函数值更大的基可行解，列出新的单纯形表值更大的基可行解，列出新的单纯形表 重复第二、三步一直到计算终止重复第二、三步一直到计算终止School of Management Harbin Institute of Technology 38单纯形法计算步骤单纯形法计算步骤 确定换入基的变量确定换入基的变量 确定换出基的变量确定换出基的变量 用换入变量替换基变量中的换出变量用换入变量替换基变量

23、中的换出变量将主元素所在行数字除以主元素其它行变换检验数变换School of Management Harbin Institute of Technology 39单纯形法计算步骤单纯形法计算步骤School of Management Harbin Institute of Technology 40老虎里面打苍蝇老虎里面打苍蝇被抓全因台不硬被抓全因台不硬串通一窝全被免串通一窝全被免重新洗牌新联姻重新洗牌新联姻竖除横乘负后加竖除横乘负后加新主登基换新人新主登基换新人政权是否稳如山政权是否稳如山照镜检验万里行照镜检验万里行单纯形法计算步骤单纯形法计算步骤School of Manageme

24、nt Harbin Institute of Technology 41单纯形法计算步骤单纯形法计算步骤School of Management Harbin Institute of Technology 42 人工变量法人工变量法前面讨论了在标准型中系数矩阵有单位矩阵，很容易确定一组初始基可行解。但实际问题中有一些模型并不含有单位矩阵，为得到一组基向量和初始基可行解，在约束条件的等式左端（标准化后的模型）加一组虚拟变量，从而得到一组基变量。这种人为加的变量称为人工变量，对应的可行基称为人工基，用大M法或两阶段法求解。School of Management Harbin Institute

25、 of Technology 43单纯形法的进一步讨论单纯形法的进一步讨论单纯形法的进一步讨论单纯形法的进一步讨论School of Management Harbin Institute of Technology 44单纯形法的进一步讨论单纯形法的进一步讨论School of Management Harbin Institute of Technology 45Cj-30100-M-MCB基bx1x2x3x4x5x6x70 x441111000-Mx61-21-10-110-Mx790310001cj-zj-2M-34M10-M000 x4330211-100 x21-21-10-110

26、-Mx7660403-31cj-zj6M-304M+103M-4M00 x400011-1/21/2-1/20 x23011/30001/3-3x11102/301/2-1/21/6cj-zj00303/2-M-3/2-M+1/20 x400001-1/21/2-1/20 x25/2-1/2100-1/41/41/41x33/23/20103/4-3/41/4cj-zj-9/2000-3/4-M+3/4-M-1/4 两阶段法两阶段法第一阶段：求解一个目标函数中只包含人工变量的线性规划问题。令目标函数中其他变量的系数取零，人工变量的系数取某个正的常数（一般取1），在保持原问题约束条件不变的情况下

27、求这个目标函数极小化时的解（目标函数为零）第二阶段：当第一阶段有可行解时，从第一阶段的最终单纯形表出发，去掉人工变量，并按原问题的目标函数继续寻求最优解。School of Management Harbin Institute of Technology 46单纯形法的进一步讨论单纯形法的进一步讨论单纯形法的进一步讨论单纯形法的进一步讨论- -两阶段法两阶段法School of Management Harbin Institute of Technology 47单纯形法的进一步讨论单纯形法的进一步讨论- -两阶段法两阶段法School of Management Harbin Insti

28、tute of Technology 48Cj00000-1-1CB基bx1x2x3x4x5x6x70 x441111000-1x61-21-10-110-1x790310001cj-zj-2400-1000 x4330211-100 x21-21-10-110-1x7660403-31cj-zj60403-400 x400011-1/21/2-1/20 x23011/30001/3-3x11102/301/2-1/21/6cj-zj00000-1-1单纯形法的进一步讨论单纯形法的进一步讨论- -两阶段法两阶段法School of Management Harbin Institute of

29、Technology 49Cj-30100CB基bx1x2x3x4x50 x400011-1/20 x23011/300-3x11102/301/2cj-zj00303/20 x400001-1/20 x25/2-1/2100-1/41x33/23/20103/4cj-zj-9/2000-3/4单纯形法的进一步讨论单纯形法的进一步讨论School of Management Harbin Institute of Technology 50CB基基bx1x2x3x4x53x13101/20-1/50 x4400-214/53x2301001/500-3/200CB基基bx1x2x3x4x53x141001/400 x5500-5/25/413x22011/2-1/4000-3/