线性规划单纯形法PPT实用版课件.ppt

1、线性规划单纯形法（优选）线性规划单纯形法历史，性质，应用历史，性质，应用q20世纪整个世界参与规模最大的事件是什么？世纪整个世界参与规模最大的事件是什么？q第二次世界大战！第二次世界大战！q整个世界的资源都投入到了第二次世界大战中。整个世界的资源都投入到了第二次世界大战中。q如何才能更好地利用资源，分配有限的资源，这是一个值得如何才能更好地利用资源，分配有限的资源，这是一个值得研究的问题。研究的问题。q当时在英国军队中率先成立了研究小组当时在英国军队中率先成立了研究小组运筹小组运筹小组 来研究这些问题，这就是著名的来研究这些问题，这就是著名的OR小组小组.很快美军中很快美军中 也相继成立了也相

2、继成立了OR小组。小组。q战争战争 运筹学诞生的温床。运筹学诞生的温床。 历史，性质，应用历史，性质，应用二战中成功的运筹学案例二战中成功的运筹学案例英国防空部门如何布置防空雷达，建立最有效的防空英国防空部门如何布置防空雷达，建立最有效的防空警报系统。警报系统。英，美空军如何提高对地面目标轰炸的命中率。英，美空军如何提高对地面目标轰炸的命中率。如何安排反潜飞机的巡逻飞行线路。如何安排反潜飞机的巡逻飞行线路。深水炸弹的合理爆炸深度，摧毁德军潜艇数增加深水炸弹的合理爆炸深度，摧毁德军潜艇数增加400%。商船如何编队，遭潜艇攻击时如何减少损失。商船如何编队，遭潜艇攻击时如何减少损失。 使船只受敌机攻

3、击时，中弹数由使船只受敌机攻击时，中弹数由47%降到降到29%。这些研究大大提高了盟军的作战能力，为反法西斯这些研究大大提高了盟军的作战能力，为反法西斯 战争的最后胜利作出了巨大的贡献！战争的最后胜利作出了巨大的贡献！历史，性质，应用历史，性质，应用战争结束了！战争结束了！ 整个世界投入到了战后的重建国家的经济之整个世界投入到了战后的重建国家的经济之中。中。q运筹学的方法相继在工业，农业，经济，社会问题等各个运筹学的方法相继在工业，农业，经济，社会问题等各个领域中展开了应用。与此同时，运筹数学有了飞快的发展，领域中展开了应用。与此同时，运筹数学有了飞快的发展，并形成了许多运筹学的分支。并形成了

4、许多运筹学的分支。q线性规划，非线性规划，整数规划，目标规划，动态规划，线性规划，非线性规划，整数规划，目标规划，动态规划，图与网络分析，统筹方法，排队论，存储论，对策论，决图与网络分析，统筹方法，排队论，存储论，对策论，决策论，多目标决策。策论，多目标决策。历史，性质，应用历史，性质，应用运筹学的性质和特点运筹学的性质和特点n一种哲学方法论一种哲学方法论; n研究研究“事事”而非而非“物物”; n科学性，实践性，系统性，综合性科学性，实践性，系统性，综合性;n模型的特点模型的特点系统优化模型。系统优化模型。q运筹学运筹学 为决策机构在对其控制下业务活动进行决策时，为决策机构在对其控制下业务活

5、动进行决策时，提供以数量化为基础的科学方法。提供以数量化为基础的科学方法。q运筹学运筹学 一门应用科学，它广泛应用现有的科学技术知一门应用科学，它广泛应用现有的科学技术知识和数学方法，解决实际中提出的专门问题。识和数学方法，解决实际中提出的专门问题。a.运筹学运筹学 是一种给出问题坏的答案的艺术，否则问题的是一种给出问题坏的答案的艺术，否则问题的结果会更坏。结果会更坏。历史，性质，应用历史，性质，应用运筹学的工作步骤运筹学的工作步骤 运筹学在解决大量实际问题的过程中形成了自己的工运筹学在解决大量实际问题的过程中形成了自己的工作步骤作步骤提出和形成问题。提出和形成问题。 即弄清问题的目标，可能的

6、约束，即弄清问题的目标，可能的约束，问题的可控变量以及有关参数，搜集有关资料问题的可控变量以及有关参数，搜集有关资料;建立模型。建立模型。 即把问题中可控变量，参数和目标与约束即把问题中可控变量，参数和目标与约束之间的关系用一定的模型表示出来之间的关系用一定的模型表示出来;求解。用各种手段（主要是数学方法，也可用其他方求解。用各种手段（主要是数学方法，也可用其他方法）将模型求解。解可以是最优解、次优解、满意法）将模型求解。解可以是最优解、次优解、满意解。复杂模型的求解需用计算机，解的精度要可由解。复杂模型的求解需用计算机，解的精度要可由求决策者提出。求决策者提出。历史，性质，应用历史，性质，应

7、用运筹学的工作步骤运筹学的工作步骤n解的检验。首先检查求解步骤和程序有无错误，然后检查解的检验。首先检查求解步骤和程序有无错误，然后检查解是否反映现实问题；解是否反映现实问题；n解的控制。通过控制解的变化过程决定是否要作一定的改解的控制。通过控制解的变化过程决定是否要作一定的改变；变；4)解的实施。是指将解用到实际中必须考虑到实施的问题，解的实施。是指将解用到实际中必须考虑到实施的问题，如向实际部门讲清解的用法，在实施中可能产生的问题和如向实际部门讲清解的用法，在实施中可能产生的问题和修改。修改。设线性规划问题变量取值限制一般情况下，决策变量取正值（非负值）。正式提出了运筹学的一个新领域数据包

8、络分析。线性规划 Linear Programming（LP）AX b s.表中当前所指基本可行解即为最优解。X4= 50 - 2X1 - X2 （1.线性规划 Linear Programming（LP）按研究者对问题内在机理的认识直接构造出模型。2X1+ X2 + X4 = 50a11x1 + a12x2 + a1nxn = b1am1x1 + am2x2 + + amnxn bm线性规划 Linear Programming（LP）表中当前所指基本可行解即为最优解。唯一最优解 X=（9/2，3/2）相对有效性评价问题例子（优选）线性规划单纯形法线性规划 Linear Programmin

9、g（LP）历史，性质，应用历史，性质，应用运筹学的模型运筹学的模型模型的三种基本形式模型的三种基本形式 （1）形象模型，（）形象模型，（2）模拟模型，（）模拟模型，（3）符号或数学模型。符号或数学模型。构造模型是一种创造性劳动，成功的模型构造模型是一种创造性劳动，成功的模型往往是科学和艺术的结晶，构造模型的往往是科学和艺术的结晶，构造模型的方法和思路通常有以下几种方法和思路通常有以下几种历史，性质，应用历史，性质，应用q直接分析法直接分析法 按研究者对问题内在机理的认识直接构造出模型。按研究者对问题内在机理的认识直接构造出模型。q类比法类比法 有些问题可以用不同方法构造出模型；而这些模型的结构

10、有些问题可以用不同方法构造出模型；而这些模型的结构性质是类同的，这就可以互相类比。性质是类同的，这就可以互相类比。q数据分析法数据分析法 对有些问题的机理尚未了解清楚，若能搜集对有些问题的机理尚未了解清楚，若能搜集到与此问题密切有关的大量数据，或通过某些试验获得大到与此问题密切有关的大量数据，或通过某些试验获得大量数据，这就可以用统计分析法建摸。量数据，这就可以用统计分析法建摸。历史，性质，应用历史，性质，应用q试验分析法试验分析法 有些问题的机理不清，又不能作大量试验来有些问题的机理不清，又不能作大量试验来获得数据，这时只能通过做局部试验的数据加上分析来构获得数据，这时只能通过做局部试验的数

11、据加上分析来构造模型。造模型。q想定（构想）法想定（构想）法 当有些问题的机理不清，又缺少数据，当有些问题的机理不清，又缺少数据，又不能作试验来获得数据时，人们只能在已有的知识、经又不能作试验来获得数据时，人们只能在已有的知识、经验的基础上，对于未来可能发生的情况给出逻辑上合理的验的基础上，对于未来可能发生的情况给出逻辑上合理的设想和描述。然后用已有的设想和描述。然后用已有的方法构造模型，并不断修正完善，方法构造模型，并不断修正完善，直至比较满意为止。直至比较满意为止。历史，性质，应用历史，性质，应用运筹学的主要应用运筹学的主要应用 二战后运筹学的应用迅速转向了民用，下面对某二战后运筹学的应用

12、迅速转向了民用，下面对某些重要领域给于简述些重要领域给于简述市场销售广告预算和媒介选择、竞争性定价、新品开市场销售广告预算和媒介选择、竞争性定价、新品开发、销售计划的制订。（美）杜邦公司在五十年发、销售计划的制订。（美）杜邦公司在五十年代起就非常重视将运筹学用于如何做好广告工作、代起就非常重视将运筹学用于如何做好广告工作、产品定价、新品引入。产品定价、新品引入。生产计划从总体确定生产、存储和劳动力的配合等计生产计划从总体确定生产、存储和劳动力的配合等计划适应波动的需求计划。巴基斯坦一重型制造厂划适应波动的需求计划。巴基斯坦一重型制造厂用线性规划安排生产计划，节省用线性规划安排生产计划，节省10

13、%的生产费用。的生产费用。历史，性质，应用历史，性质，应用n运输问题涉及空运、水运、公路、铁路运输、管道运输等。运输问题涉及空运、水运、公路、铁路运输、管道运输等。公路网的设计和分析，市内公共汽车路线的选择和行车时公路网的设计和分析，市内公共汽车路线的选择和行车时刻表的安排，出租车的调度等。刻表的安排，出租车的调度等。n人事管理需求估计，教育和培训，人员分配（各种指派问人事管理需求估计，教育和培训，人员分配（各种指派问题），合理利用，人才评价等。题），合理利用，人才评价等。n设备维修，更新和可靠性等。设备维修，更新和可靠性等。历史，性质，应用历史，性质，应用n计算机和信息系统内存分配研究，网络

14、设计分析等。计算机和信息系统内存分配研究，网络设计分析等。n城市管理紧急服务系统的设计和运用，区域布局规划，管城市管理紧急服务系统的设计和运用，区域布局规划，管道网络设计等。（美）曾用排队论确定纽约市紧急电话站道网络设计等。（美）曾用排队论确定纽约市紧急电话站的值班人数，（加）设计城市警车配置和负责范围、指挥的值班人数，（加）设计城市警车配置和负责范围、指挥接警后的行走路线等。接警后的行走路线等。n对策研究价格竞争，中央与地方政府投资分配博弈，工会对策研究价格竞争，中央与地方政府投资分配博弈，工会与雇主间的博弈。与雇主间的博弈。第一讲第一讲线性规划线性规划 Linear Programming

15、( LP )目标规划目标规划 Goal Programming( GP )整数规划整数规划 Integer Programming( IP ) 表中当前所指基本可行解即为最优解。例 一连锁餐饮企业拥有遍布全国的20家连锁餐厅，每家餐厅的每周运营时间、员工人数以及每周利润和所占市场份额如下表在本例中，空军基地有 7 个，分别记为 A 、B 、C 、D 、E 、F 、G 。X4= 50 2X1 X2 0B N I求各个分理处的运行是否DEA有效。2X1+ X2 + X4 = 50使用DEA进行评价，结果基本合理。绪论 历史，性质，应用研究“事”而非“物”;综上所述决策者所需考虑的区域内各个化工厂应

16、处理的工业污水量 Xi应满足上述所有不等式方程。64X9 2.给定线性规划问题（标准形式）11 = 2X1 + X2X4 +0.复杂模型的求解需用计算机，解的精度要可由求决策者提出。am1 am2 amn绪论 历史，性质，应用设线性规划问题焦炭是产钢必不可少的原料，每年 NBS 需要采购约11.第一章第一章线性规划及单纯形法线性规划及单纯形法线性规划线性规划 Linear Programming（LP）引引 言言q线性规划是运筹学的一个重要分支，也是运筹学中应用最线性规划是运筹学的一个重要分支，也是运筹学中应用最广泛的方法之一。调查表明，在世界广泛的方法之一。调查表明，在世界500家最大的企业

17、中，家最大的企业中，有有85%的企业都曾使用线性规划解决经营管理中遇到的复的企业都曾使用线性规划解决经营管理中遇到的复杂问题。线性规划的使用为应用者节约了数以亿万计的资杂问题。线性规划的使用为应用者节约了数以亿万计的资金。金。q解决有限资源在有竞争的使用方向中如何进行最佳分配。解决有限资源在有竞争的使用方向中如何进行最佳分配。线性规划线性规划 Linear Programming（LP）q本讲中我们将讨论什么是线性规划问题，线性规划问题的本讲中我们将讨论什么是线性规划问题，线性规划问题的数学表示，基本理论、概念和求解方法。数学表示，基本理论、概念和求解方法。q线性规划问题是什么样的一类问题呢？

18、线性规划问题是什么样的一类问题呢？q 请看案例请看案例线性规划线性规划 Linear Programming（LP）线性规划线性规划 Linear Programming（LP）曾几何时长江水，曾几何时长江水，哺育华夏代代人哺育华夏代代人; ;谁知后代疏珍惜，谁知后代疏珍惜，清清江水黑如泥。清清江水黑如泥。案案 例例 河流污染治理规划问题河流污染治理规划问题线性规划线性规划 Linear Programming（LP）曾几何时长江水，曾几何时长江水，哺育华夏代代人哺育华夏代代人; ;谁知后代疏珍惜，谁知后代疏珍惜，清清江水黑如泥。清清江水黑如泥。工厂工厂2 2工厂工厂3 3工厂工厂1 1工厂工

19、厂4 4工厂工厂5 5工厂工厂6 6工厂工厂9 9工厂工厂8 8工厂工厂7 7案案 例例 河流污染治理规划问题河流污染治理规划问题线性规划线性规划 Linear Programming（LP）曾几何时长江水，曾几何时长江水，哺育华夏代代人哺育华夏代代人; ;谁知后代疏珍惜，谁知后代疏珍惜，清清江水黑如泥。清清江水黑如泥。今日认识未为晚，今日认识未为晚，吾辈齐心治环境吾辈齐心治环境; ;线性规划大有用，线性规划大有用，定让江水绿如蓝。定让江水绿如蓝。工厂工厂2 2工厂工厂3 3工厂工厂1 1工厂工厂4 4工厂工厂5 5工厂工厂6 6工厂工厂9 9工厂工厂8 8工厂工厂7 7案案 例例 河流污染治

20、理规划问题河流污染治理规划问题线性规划线性规划 Linear Programming（LP）今日认识未为晚，今日认识未为晚，吾辈齐心治环境吾辈齐心治环境; ;线性规划大有用，线性规划大有用，定让江水绿如蓝。定让江水绿如蓝。曾几何时长江水，曾几何时长江水，哺育华夏代代人哺育华夏代代人; ;谁知后代疏珍惜，谁知后代疏珍惜，清清江水黑如泥。清清江水黑如泥。工厂工厂2 2工厂工厂3 3工厂工厂1 1工厂工厂4 4工厂工厂5 5工厂工厂6 6工厂工厂9 9工厂工厂8 8工厂工厂7 7案案 例例 河流污染治理规划问题河流污染治理规划问题线性规划线性规划 Linear Programming（LP）案案 例

21、例 河流污染治理规划问题河流污染治理规划问题背景资料背景资料:长江流域某区域内有长江流域某区域内有9化工厂，各厂每月产生的工业化工厂，各厂每月产生的工业污水量如表污水量如表1，流经各化工厂的河流流量如表，流经各化工厂的河流流量如表2，各，各化工厂治理工业污水的成本如表化工厂治理工业污水的成本如表3。上游厂排放的。上游厂排放的污水流到相邻下游厂以前，有污水流到相邻下游厂以前，有20%可自然净化。可自然净化。 根根据环保标准河流中此种工业污水的含量不应超过据环保标准河流中此种工业污水的含量不应超过0.2%。从该区域整体考虑，各化工厂应该分别处理。从该区域整体考虑，各化工厂应该分别处理多少工业污水才

22、能既满足环保要求，又使多少工业污水才能既满足环保要求，又使9化工厂化工厂治理工业污水的总费用最少。治理工业污水的总费用最少。q背景资料背景资料: :线性规划线性规划 Linear Programming（LP）化工厂化工厂1 11.2化工厂化工厂4 42化工厂化工厂7 72化工厂化工厂2 21化工厂化工厂5 51化工厂化工厂8 80.8化工厂化工厂3 33化工厂化工厂6 61化工厂化工厂9 91.5表表-1 -1 污水产生量污水产生量 单位：万单位：万m m3 3表表-2 -2 流经各化工厂的河流流量流经各化工厂的河流流量 单位：万单位：万m m3 3表表-3 -3 治理工业污水的成本治理工业

23、污水的成本 单位：百万元单位：百万元/ /万万m m3 3化工厂化工厂1 1500化工厂化工厂4 41200化工厂化工厂7 71200化工厂化工厂2 2300化工厂化工厂5 5600化工厂化工厂8 8200化工厂化工厂3 31800化工厂化工厂6 6400化工厂化工厂9 9700化工厂化工厂1 13化工厂化工厂4 44化工厂化工厂7 71化工厂化工厂2 25化工厂化工厂5 55化工厂化工厂8 82化工厂化工厂3 32化工厂化工厂6 66化工厂化工厂9 93线性规划线性规划 Linear Programming（LP）194582637q问题分析问题分析q区域污染治理的决策区域污染治理的决策各个

24、化工厂应处理的工业污水量各个化工厂应处理的工业污水量（或应排放的工业污水量）。（或应排放的工业污水量）。q区域污染治理的约束区域污染治理的约束即满足环保要求排放工业污水即满足环保要求排放工业污水（区域内河流中任何点检测都应符合环保标准）。（区域内河流中任何点检测都应符合环保标准）。q区域污染治理的目标区域污染治理的目标总治理成本最少。总治理成本最少。q 这类问题的共同特点三大要素这类问题的共同特点三大要素q决策，目标，约束决策，目标，约束线性规划线性规划 Linear Programming（LP）194582637q建模分析建模分析q设第设第i个化工厂应处理的工业污水量为个化工厂应处理的工业

25、污水量为Xi万万m3，则根据问题，则根据问题描述的情况以化工厂描述的情况以化工厂1、2、 、9 加以分析则可得如下近加以分析则可得如下近似关系式似关系式q对化工厂对化工厂2应有应有q （1X2）/ 300 0.2%q对化工厂对化工厂8应有应有q （0.8X8）/200 0.2%q对化工厂对化工厂1应有应有q （1.2X1）+ 0.8（1X2）+（0.8X8） /500 0.2%线性规划线性规划 Linear Programming（LP）194582637q对化工厂对化工厂9应有应有q （1.5X9）/ 700 0.2%q对化工厂对化工厂7应有应有q （2X7）+ 0.8（1.5X9） / 1

26、200 0.2%q q此外显然还应有此外显然还应有q Xi 0 （i=1，2，3 8，9）q综上所述决策者所需考虑的区域内各个化工厂应处理的工综上所述决策者所需考虑的区域内各个化工厂应处理的工业污水量业污水量 Xi应满足上述所有不等式方程。我们将这些不等应满足上述所有不等式方程。我们将这些不等式方程构成的方程组称为污水治理的约束条件。式方程构成的方程组称为污水治理的约束条件。线性规划线性规划 Linear Programming（LP）194582637另一方面污水治理的总成本可表示为另一方面污水治理的总成本可表示为Z Z = 3X1+ 5X2+ 2X3+ 4X4+ 5X5+ 6X6+ 1X7

27、+ 2X8+ 3X9 而决策者的目标是确定满足约束条件的而决策者的目标是确定满足约束条件的Xi使得使得Z取得最小值。取得最小值。将上述分析归纳后即可得如下数学符合模型将上述分析归纳后即可得如下数学符合模型线性规划 Linear Programming（LP）a11x1 + a12x2 + a1nxn = b1j aij E aij0 （i = 1，2，m，E1）数据包络分析DEA问题线性规划数学模型线性规划 Linear Programming（LP）min Z = 5X1+4X2a11x1 + a12x2 + a1nxn + xn+1 = b1max z = 2x1 + x2区域污染治理的约

28、束即满足环保要求排放工业污水（区域内河流中任何点检测都应符合环保标准）。线性规划 Linear Programming（LP）运输问题涉及空运、水运、公路、铁路运输、管道运输等。XB ，XN，XS 0确定目标函数 目标函数决定线性规划问题的优化方向，是模型的重要组成部分。上游厂排放的污水流到相邻下游厂以前，有20%可自然净化。（美）曾用排队论确定纽约市紧急电话站的值班人数，（加）设计城市警车配置和负责范围、指挥接警后的行走路线等。X1 = 25 0.线性规划 Linear Programming（LP）而这些模型的结构性质是类同的，这就可以互相类比。s.长江流域某区域内有9化工厂，各厂每月产生

29、的工业污水量如表1，流经各化工厂的河流流量如表2，各化工厂治理工业污水的成本如表3。3x2 + x3 = 9线性规划线性规划 Linear Programming（LP）河流污染治理规划问题河流污染治理规划问题数学模型（整理之后）数学模型（整理之后）194582637Min Z= 3X1 +5X2 +2X3 +4X4 +5X5 +6X6 +1X7 +2X8 +3X9 X2 0.4 X8 0.4 X1 +0.8X2 +0.8X8 1.64 X9 0.1 X7 +0.8 X9 0.8 X4 +0.8X7 +0.64X9 2.16 X6 0.2 X5 +0.8X6 0.6 X3 +0.8X4 +0.

30、8X5 +0.64X6 +0.64X7 +5.12X9 9.4 Xi 0 （i=1，2，3，4，5，6，7，8，9）s.t.线性规划线性规划 Linear Programming（LP）基本概念基本概念 线性规划模型线性规划模型 Linear Programming ModelLinear Programming Model 或或 Linear Optimization ModelLinear Optimization Model 用线性规划方法解决实际经济与管理问题的第一用线性规划方法解决实际经济与管理问题的第一步是分析建立能够完整描述和反映实际问题的线性规步是分析建立能够完整描述和反映实际

31、问题的线性规划模型。划模型。线性规划线性规划 Linear Programming（LP）基本概念基本概念通常建立通常建立LP模型有以下几个基本步骤模型有以下几个基本步骤确定决策变量确定决策变量 决策变量是模型要确定的未知变量，决策变量是模型要确定的未知变量，也是模型最重要的参数，是决策者解决实际问题也是模型最重要的参数，是决策者解决实际问题的控制变量。的控制变量。确定目标函数确定目标函数 目标函数决定线性规划问题的优化方目标函数决定线性规划问题的优化方向，是模型的重要组成部分。实际问题的目标可向，是模型的重要组成部分。实际问题的目标可表示为决策变量的一个线性函数，并根据实际问表示为决策变量的

32、一个线性函数，并根据实际问题的优化方向求其最大化（题的优化方向求其最大化（max）或最小化）或最小化（min）。）。线性规划线性规划 Linear Programming（LP）基本概念基本概念 通常建立通常建立LP模型有以下几个步骤模型有以下几个步骤确定约束方程一个正确的线性规划模型应能通过约束确定约束方程一个正确的线性规划模型应能通过约束方程来描述和反映一系列客观条件或环境的限制，方程来描述和反映一系列客观条件或环境的限制，这些限制通过一系列线性等式或不等式方程组来这些限制通过一系列线性等式或不等式方程组来描述。描述。变量取值限制一般情况下，决策变量取正值（非负变量取值限制一般情况下，决策

33、变量取正值（非负值）。因此，模型中应有变量的非负约束即值）。因此，模型中应有变量的非负约束即Xj0，但要注意也存在例外的情形。但要注意也存在例外的情形。线性规划线性规划 Linear Programming（LP）基本概念基本概念线性规划的一般形式线性规划的一般形式: max（或（或min）z = c1x1 + c2x2 + + cnxn a11x1 + a12x2 + a1nxn （ = ）b1 a21x1 + a22x2 + a2nxn （ = ）b2 s.t. am1x1 + am2x2 + amnxn （ = ）bm xj 0 （j=1，2 n）线性规划线性规划 Linear Prog

34、ramming（LP）基本概念基本概念线性规划问题的标准形式线性规划问题的标准形式1、目标函数极大化、目标函数极大化 “ max ”2、等式约束条件、等式约束条件 “ = ” 且右端常数且右端常数bi非负非负3、变量非负、变量非负 “ xj 0 ” max z = c1x1 + c2x2 + + cnxn a11x1 + a12x2 + a1nxn = b1 a21x1 + a22x2 + a2nxn = b2 s.t. am1x1 + am2x2 + amnxn = bm xj 0 （j=1，2 n）线性规划线性规划 Linear Programming（LP）基本概念基本概念化标准形式的一

35、般步骤化标准形式的一般步骤n目标函数极小化目标函数极小化“极大化极大化”n约束条件的右端项约束条件的右端项 bi0 “bi0” n约束条件为不等式约束条件为不等式 或或 “=”n取值无约束（自由）变量取值无约束（自由）变量“非负变量非负变量”1)取值非正变量取值非正变量“非负变量非负变量”线性规划线性规划 Linear Programming（LP）基本概念基本概念线性规划问题的求解解（图解）线性规划问题的求解解（图解） 如何求解一般的线性规划呢？如何求解一般的线性规划呢？ 下面我们分析一下简单的情况下面我们分析一下简单的情况 只有两个决只有两个决策变量的线性规划问题，这时可以通过图解的方法来

36、策变量的线性规划问题，这时可以通过图解的方法来求解。图解法具有简单、直观、便于初学者窥探线性求解。图解法具有简单、直观、便于初学者窥探线性规划基本原理和几何意义等优点。规划基本原理和几何意义等优点。线性规划线性规划 Linear Programming（LP）基本概念基本概念例例1（page 11）max z = 2x1 + x2 5x2 15s.t. 6x1 + 2x2 24 x1 + x2 5 x1 ，x2 0线性规划线性规划 Linear Programming（LP）基本概念基本概念max z = 2x1 + x2 5x2 15s.t. 6x1 + 2x2 24 x1 + x2 5 x

37、1 ，x2 0唯一最优解唯一最优解 X=（9/2，3/2）线性规划线性规划 Linear Programming（LP）基本概念基本概念例例 max Z = 2X1 + X2 X1 + 1.9X2 3.8 X1 1.9X2 3.8 s.t. X1 + 1.9X2 10.2 X1 1.9X2 3.8 X1 ，X2 0 x1 + x2 + x3 4a11x1 + a12x2 + a1nxn + xn+1 = b1很快美军中 也相继成立了OR小组。2X1 = 50 X2 X4然后用已有的方法构造模型，并不断修正完善，直至比较满意为止。线性规划 Linear Programming（LP）Xi 0 （

38、i=1，2，3 8，9）a21 a22 a2n每个广告的成本（万元）采用大 M 法求解线性规划问题时可能出现的几种情况线性规划 Linear Programming（LP）至少要影响 500 万人口；线性规划 Linear Programming（LP）2、两阶段法第I 阶段4X1+ 3X2 + X3 = 120Max Z = 50X1+30X2想定（构想）法 当有些问题的机理不清，又缺少数据，又不能作试验来获得数据时，人们只能在已有的知识、经验的基础上，对于未来可能发生的情况给出逻辑上合理的设想和描述。如果该假想单元的各项产出均不低于 j0 决策单元的各项产出，它的各项投入均低于 j0 决策

39、单元的各项的各项投入。线性规划线性规划 Linear Programming（LP）基本概念基本概念max Z = 2X1 + X2x1x2oX1 - 1.9X2 = 3.8()X1 + 1.9X2 = 3.8()X1 - 1.9X2 = -3.8 ()X1 + 1.9X2 = 10.2()4 = 2X1 + X2 20 = 2X1 + X2 17.2 = 2X1 + X2 11 = 2X1 + X2 Lo： 0 = 2X1 + X2 （7.6，2）Dmax Zmin Z此点是唯一最优解，此点是唯一最优解，且最优目标函数值且最优目标函数值 max Z=17.2可行域可行域线性规划线性规划 Li

40、near Programming（LP）基本概念基本概念max Z = 3X1+5.7X2x1x2oX1 - 1.9X2 = 3.8 ()X1 + 1.9X2 = 3.8()X1 - 1.9X2 = -3.8()X1 + 1.9X2 = 10.2 ()（7.6，2）DL0： 0=3X1+5.7X2 max Z min Z（3.8，4）34.2 = 3X1+5.7X2 绿色线段上的所有点都是最绿色线段上的所有点都是最优解这种情形为有无穷多最优解这种情形为有无穷多最优解，但是最优目标函数值优解，但是最优目标函数值max Z=34.2是唯一的。是唯一的。可行域可行域线性规划线性规划 Linear P

41、rogramming（LP）基本概念基本概念min Z = 5X1+4X2x1x2oX1 - 1.9X2 = 3.8 ()X1 + 1.9X2 = 3.8()X1 - 1.9X2 = -3.8()X1 + 1.9X2 = 10.2 ()DL0： 0=5X1+4X2 max Z min Z 8=5X1+4X2 43=5X1+4X2 （0，2）可行域可行域此点是唯一最优解此点是唯一最优解线性规划线性规划 Linear Programming（LP）基本概念基本概念min Z = 5X1+4X2x1x2oD可行域可行域线性规划线性规划 Linear Programming（LP）基本概念基本概念ma

42、x Z = 5X1+4X2x1x2oD可行域可行域 max Z min Z最优解目标值最优解目标值Z趋于无穷趋于无穷线性规划线性规划 Linear Programming（LP）基本概念基本概念max Z = 5X1+4X2x1x2o可行解域为空可行解域为空线性规划线性规划 Linear Programming（LP）基本概念基本概念图解法的启示图解法的启示n线性规划问题解的可能情况线性规划问题解的可能情况 a.唯一最优解唯一最优解 b.无穷多最优解无穷多最优解 c.无解（没有有界最优解，无可行解）无解（没有有界最优解，无可行解）n若线性规划问题的可行域非空，则可行域是一个凸集；若线性规划问题

43、的可行域非空，则可行域是一个凸集；1)若线性规划问题的最优解存在，则一定可以在可行域的凸若线性规划问题的最优解存在，则一定可以在可行域的凸集的某个顶点上达到。集的某个顶点上达到。线性规划线性规划 Linear Programming（LP）单纯形法单纯形法 单纯形方法是单纯形方法是G.B.Danzig于于1947年首先发明的。近年首先发明的。近50年年来，一直是求解线性规划的最有效的方法之一，被广泛应用于来，一直是求解线性规划的最有效的方法之一，被广泛应用于各种线性规划问题的求解。本节讨论单纯形法的基本概念、原各种线性规划问题的求解。本节讨论单纯形法的基本概念、原理及算法。理及算法。线性规划线

44、性规划 Linear Programming（LP）单纯形法单纯形法给定线性规划问题（标准形式）给定线性规划问题（标准形式） max z = c1x1 + c2x2 + + cnxn a11x1 + a12x2 + a1nxn = b1 a21x1 + a22x2 + a2nxn = b2 s .t. am1x1 + am2x2 + amnxn = bm xj 0 （j=1，2 n）线性规划线性规划 Linear Programming（LP）单纯形法单纯形法一、线性规划问题的解的概念一、线性规划问题的解的概念 可行解可行解 最优解最优解 基基 基解（基本解）基解（基本解） 基可行解基可行解

45、可行基可行基线性规划线性规划 Linear Programming（LP）单纯形法单纯形法二、凸集及其顶点二、凸集及其顶点 凸集凸集 顶点（极点）顶点（极点）凸集凸集凹集凹集线性规划线性规划 Linear Programming（LP）12345678基解（可行）基解（可行）基解（不可行）基解（不可行）线性规划线性规划 Linear Programming（LP）单纯形法单纯形法三、线性规划基本定理三、线性规划基本定理基本定理基本定理 1 线性规划所有可行解组成的集合线性规划所有可行解组成的集合S= X | AX = b，X 0 是凸集。是凸集。基本定理基本定理 2 X是线性规划问题的基本可行

46、解的充要条件为是是线性规划问题的基本可行解的充要条件为是 X 是凸集是凸集S= X | AX = b，X 0 的极点。的极点。基本定理基本定理 3 给定线性规划问题，给定线性规划问题， A是秩为是秩为 m 的的 mn 矩阵，矩阵， （i） 若线性规划问题存在可行解，则必存在基本可行若线性规划问题存在可行解，则必存在基本可行解解 （ii）若线性规划问题存在有界最优解，则必存在有界若线性规划问题存在有界最优解，则必存在有界最优基本可行解。最优基本可行解。线性规划线性规划 Linear Programming（LP）单纯形法单纯形法单纯形法迭代原理及其思路单纯形法迭代原理及其思路单纯形法的初步讨论单

47、纯形法的初步讨论例例1.8 求解求解LP问题问题 化为化为标准型标准型Max Z = 50X1+30X2s.t. 4X1+3X2 120 2X1+ X2 50 X1，X2 0Max Z = 50X1+30X2s.t. 4X1+3X2 +X3 = 120 2X1+ X2 + X4 = 50 X1，X2，X3，X4 0（1.18）线性规划线性规划 Linear Programming（LP）单纯形法单纯形法 此线性规划问题转化为了一个含有四个变量的标准此线性规划问题转化为了一个含有四个变量的标准形线性规划问题，形线性规划问题，X3，X4为松弛变量。为求解上面为松弛变量。为求解上面的的LP问题，我们

48、要考虑满足约束条件问题，我们要考虑满足约束条件s.t.并使并使 Z 取得取得Max的的X1，X2，X3，X4的值，由此分析如下的值，由此分析如下线性规划线性规划 Linear Programming（LP）单纯形法单纯形法确定初始基可行解确定初始基可行解 通过观察可以发现，松弛变量通过观察可以发现，松弛变量X3和和X4对应的对应的等式约束条件中的系数矩阵为单位矩阵可以作为初始等式约束条件中的系数矩阵为单位矩阵可以作为初始可行基矩阵。因此可行基矩阵。因此取取 X3，X4为基变量；为基变量；X1，X2为非基变量。则为非基变量。则（1.18）可变为）可变为 Max Z = 50X1+30X2 s.t

49、. X3 = 120 - - 4X1 - - 3X2 X4= 50 - - 2X1 - - X2 （1.191.19） X1，X2，X3，X40线性规划线性规划 Linear Programming（LP）单纯形法单纯形法典式典式（1.191.19）或）或（1.181.18）称为关于基的典式称为关于基的典式 1、等式等式约束条件中显含约束条件中显含基可行解基可行解 2、目标函数中不、目标函数中不含含基基变量变量Max Z = 50X1+30X2s.t. 4X1+3X2 +X3 = 120 2X1+ X2 + X4 = 50 ( 1.18 ) X1，X2，X3，X4 0Max Z =50X1+3

50、0X2s.t. X3 = 120 - 4X1 - 3X2 X4= 50 - 2X1 - X2 （1.19 ） X1，X2，X3，X40线性规划线性规划 Linear Programming（LP）单纯形法单纯形法 在典式（在典式（1.19）中令）中令 X1=X2 =0，我们得到一个基本可行解我们得到一个基本可行解 X1 =（ X1，X2，X3，X4 ）T=（0，0，120，50）T ，其对应的目标函数值其对应的目标函数值 Z1 = 50X1 + 30X2 = 0线性规划线性规划 Linear Programming（LP）单纯形法单纯形法最优性检验最优性检验 基本可行解基本可行解 X1 是最优