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

1、线性规划单纯形法（优选）线性规划单纯形法2绪论 历史，性质，应用20世纪整个世界参与规模最大的事件是什么？第二次世界大战！整个世界的资源都投入到了第二次世界大战中。如何才能更好地利用资源，分配有限的资源，这是一个值得研究的问题。当时在英国军队中率先成立了研究小组运筹小组 来研究这些问题，这就是著名的OR小组.很快美军中 也相继成立了OR小组。战争 运筹学诞生的温床。 3绪论 历史，性质，应用二战中成功的运筹学案例英国防空部门如何布置防空雷达，建立最有效的防空警报系统。英，美空军如何提高对地面目标轰炸的命中率。如何安排反潜飞机的巡逻飞行线路。深水炸弹的合理爆炸深度，摧毁德军潜艇数增加400%。商

2、船如何编队，遭潜艇攻击时如何减少损失。 使船只受敌机攻击时，中弹数由47%降到29%。这些研究大大提高了盟军的作战能力，为反法西斯 战争的最后胜利作出了巨大的贡献！4绪论 历史，性质，应用战争结束了！ 整个世界投入到了战后的重建国家的经济之中。运筹学的方法相继在工业，农业，经济，社会问题等各个领域中展开了应用。与此同时，运筹数学有了飞快的发展，并形成了许多运筹学的分支。线性规划，非线性规划，整数规划，目标规划，动态规划，图与网络分析，统筹方法，排队论，存储论，对策论，决策论，多目标决策。5绪论 历史，性质，应用运筹学的性质和特点一种哲学方法论; 研究“事”而非“物”; 科学性，实践性，系统性，

3、综合性;模型的特点系统优化模型。运筹学 为决策机构在对其控制下业务活动进行决策时，提供以数量化为基础的科学方法。运筹学 一门应用科学，它广泛应用现有的科学技术知识和数学方法，解决实际中提出的专门问题。运筹学 是一种给出问题坏的答案的艺术，否则问题的结果会更坏。6绪论 历史，性质，应用运筹学的工作步骤 运筹学在解决大量实际问题的过程中形成了自己的工作步骤提出和形成问题。 即弄清问题的目标，可能的约束，问题的可控变量以及有关参数，搜集有关资料;建立模型。 即把问题中可控变量，参数和目标与约束之间的关系用一定的模型表示出来;求解。用各种手段（主要是数学方法，也可用其他方法）将模型求解。解可以是最优解

4、、次优解、满意解。复杂模型的求解需用计算机，解的精度要可由求决策者提出。7绪论 历史，性质，应用运筹学的工作步骤解的检验。首先检查求解步骤和程序有无错误，然后检查解是否反映现实问题；解的控制。通过控制解的变化过程决定是否要作一定的改变；解的实施。是指将解用到实际中必须考虑到实施的问题，如向实际部门讲清解的用法，在实施中可能产生的问题和修改。8设线性规划问题变量取值限制一般情况下，决策变量取正值（非负值）。正式提出了运筹学的一个新领域数据包络分析。线性规划 Linear Programming（LP）AX b s.表中当前所指基本可行解即为最优解。X4= 50 - 2X1 - X2 （1.线性规

5、划 Linear Programming（LP）按研究者对问题内在机理的认识直接构造出模型。2X1+ X2 + X4 = 50a11x1 + a12x2 + a1nxn = b1am1x1 + am2x2 + + amnxn bm线性规划 Linear Programming（LP）表中当前所指基本可行解即为最优解。唯一最优解 X=（9/2，3/2）相对有效性评价问题例子（优选）线性规划单纯形法线性规划 Linear Programming（LP）绪论 历史，性质，应用运筹学的模型模型的三种基本形式 （1）形象模型，（2）模拟模型，（3）符号或数学模型。构造模型是一种创造性劳动，成功的模型往往

6、是科学和艺术的结晶，构造模型的方法和思路通常有以下几种9绪论 历史，性质，应用直接分析法 按研究者对问题内在机理的认识直接构造出模型。类比法 有些问题可以用不同方法构造出模型；而这些模型的结构性质是类同的，这就可以互相类比。数据分析法 对有些问题的机理尚未了解清楚，若能搜集到与此问题密切有关的大量数据，或通过某些试验获得大量数据，这就可以用统计分析法建摸。10绪论 历史，性质，应用试验分析法 有些问题的机理不清，又不能作大量试验来获得数据，这时只能通过做局部试验的数据加上分析来构造模型。想定（构想）法 当有些问题的机理不清，又缺少数据，又不能作试验来获得数据时，人们只能在已有的知识、经验的基础

7、上，对于未来可能发生的情况给出逻辑上合理的设想和描述。然后用已有的方法构造模型，并不断修正完善，直至比较满意为止。11绪论 历史，性质，应用运筹学的主要应用 二战后运筹学的应用迅速转向了民用，下面对某些重要领域给于简述市场销售广告预算和媒介选择、竞争性定价、新品开发、销售计划的制订。（美）杜邦公司在五十年代起就非常重视将运筹学用于如何做好广告工作、产品定价、新品引入。生产计划从总体确定生产、存储和劳动力的配合等计划适应波动的需求计划。巴基斯坦一重型制造厂用线性规划安排生产计划，节省10%的生产费用。12绪论 历史，性质，应用运输问题涉及空运、水运、公路、铁路运输、管道运输等。公路网的设计和分析

8、，市内公共汽车路线的选择和行车时刻表的安排，出租车的调度等。人事管理需求估计，教育和培训，人员分配（各种指派问题），合理利用，人才评价等。设备维修，更新和可靠性等。13绪论 历史，性质，应用计算机和信息系统内存分配研究，网络设计分析等。城市管理紧急服务系统的设计和运用，区域布局规划，管道网络设计等。（美）曾用排队论确定纽约市紧急电话站的值班人数，（加）设计城市警车配置和负责范围、指挥接警后的行走路线等。对策研究价格竞争，中央与地方政府投资分配博弈，工会与雇主间的博弈。14第一讲线性规划 Linear Programming( LP )目标规划 Goal Programming( GP )整数规

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

10、形式）11 = 2X1 + X2X4 +0.复杂模型的求解需用计算机，解的精度要可由求决策者提出。am1 am2 amn绪论 历史，性质，应用设线性规划问题焦炭是产钢必不可少的原料，每年 NBS 需要采购约11.第一章线性规划及单纯形法线性规划 Linear Programming（LP）16引 言线性规划是运筹学的一个重要分支，也是运筹学中应用最广泛的方法之一。调查表明，在世界500家最大的企业中，有85%的企业都曾使用线性规划解决经营管理中遇到的复杂问题。线性规划的使用为应用者节约了数以亿万计的资金。解决有限资源在有竞争的使用方向中如何进行最佳分配。线性规划 Linear Programm

11、ing（LP）17本讲中我们将讨论什么是线性规划问题，线性规划问题的数学表示，基本理论、概念和求解方法。线性规划问题是什么样的一类问题呢？ 请看案例线性规划 Linear Programming（LP）18线性规划 Linear Programming（LP）曾几何时长江水，哺育华夏代代人;谁知后代疏珍惜，清清江水黑如泥。案 例 河流污染治理规划问题19线性规划 Linear Programming（LP）曾几何时长江水，哺育华夏代代人;谁知后代疏珍惜，清清江水黑如泥。工厂2工厂3工厂1工厂4工厂5工厂6工厂9工厂8工厂7案 例 河流污染治理规划问题20线性规划 Linear Programm

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

13、域内有9化工厂，各厂每月产生的工业污水量如表1，流经各化工厂的河流流量如表2，各化工厂治理工业污水的成本如表3。上游厂排放的污水流到相邻下游厂以前，有20%可自然净化。 根据环保标准河流中此种工业污水的含量不应超过0.2%。从该区域整体考虑，各化工厂应该分别处理多少工业污水才能既满足环保要求，又使9化工厂治理工业污水的总费用最少。23背景资料:线性规划 Linear Programming（LP）化工厂11.2化工厂42化工厂72化工厂21化工厂51化工厂80.8化工厂33化工厂61化工厂91.5表-1 污水产生量 单位：万m3表-2 流经各化工厂的河流流量 单位：万m3表-3 治理工业污水的

14、成本 单位：百万元/万m3化工厂1500化工厂41200化工厂71200化工厂2300化工厂5600化工厂8200化工厂31800化工厂6400化工厂9700化工厂13化工厂44化工厂71化工厂25化工厂55化工厂82化工厂32化工厂66化工厂9324线性规划 Linear Programming（LP）194582637问题分析区域污染治理的决策各个化工厂应处理的工业污水量（或应排放的工业污水量）。区域污染治理的约束即满足环保要求排放工业污水（区域内河流中任何点检测都应符合环保标准）。区域污染治理的目标总治理成本最少。 这类问题的共同特点三大要素决策，目标，约束25线性规划 Linear P

15、rogramming（LP）194582637建模分析设第i个化工厂应处理的工业污水量为Xi万m3，则根据问题描述的情况以化工厂1、2、 、9 加以分析则可得如下近似关系式对化工厂2应有 （1X2）/ 300 0.2%对化工厂8应有 （0.8X8）/200 0.2%对化工厂1应有 （1.2X1）+ 0.8（1X2）+（0.8X8） /500 0.2%26线性规划 Linear Programming（LP）194582637对化工厂9应有 （1.5X9）/ 700 0.2%对化工厂7应有 （2X7）+ 0.8（1.5X9） / 1200 0.2% 此外显然还应有 Xi 0 （i=1，2，3 8

16、，9）综上所述决策者所需考虑的区域内各个化工厂应处理的工业污水量 Xi应满足上述所有不等式方程。我们将这些不等式方程构成的方程组称为污水治理的约束条件。27线性规划 Linear Programming（LP）194582637另一方面污水治理的总成本可表示为Z Z = 3X1+ 5X2+ 2X3+ 4X4+ 5X5+ 6X6+ 1X7+ 2X8+ 3X9 而决策者的目标是确定满足约束条件的Xi使得Z取得最小值。将上述分析归纳后即可得如下数学符合模型28线性规划 Linear Programming（LP）a11x1 + a12x2 + a1nxn = b1j aij E aij0 （i =

17、1，2，m，E1）数据包络分析DEA问题线性规划数学模型线性规划 Linear Programming（LP）min Z = 5X1+4X2a11x1 + a12x2 + a1nxn + xn+1 = b1max z = 2x1 + x2区域污染治理的约束即满足环保要求排放工业污水（区域内河流中任何点检测都应符合环保标准）。线性规划 Linear Programming（LP）运输问题涉及空运、水运、公路、铁路运输、管道运输等。XB ，XN，XS 0确定目标函数 目标函数决定线性规划问题的优化方向，是模型的重要组成部分。上游厂排放的污水流到相邻下游厂以前，有20%可自然净化。（美）曾用排队论确

18、定纽约市紧急电话站的值班人数，（加）设计城市警车配置和负责范围、指挥接警后的行走路线等。X1 = 25 0.线性规划 Linear Programming（LP）而这些模型的结构性质是类同的，这就可以互相类比。s.长江流域某区域内有9化工厂，各厂每月产生的工业污水量如表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.

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

20、线性规划模型。30线性规划 Linear Programming（LP）基本概念通常建立LP模型有以下几个基本步骤确定决策变量 决策变量是模型要确定的未知变量，也是模型最重要的参数，是决策者解决实际问题的控制变量。确定目标函数 目标函数决定线性规划问题的优化方向，是模型的重要组成部分。实际问题的目标可表示为决策变量的一个线性函数，并根据实际问题的优化方向求其最大化（max）或最小化（min）。31线性规划 Linear Programming（LP）基本概念 通常建立LP模型有以下几个步骤确定约束方程一个正确的线性规划模型应能通过约束方程来描述和反映一系列客观条件或环境的限制，这些限制通过一系

21、列线性等式或不等式方程组来描述。变量取值限制一般情况下，决策变量取正值（非负值）。因此，模型中应有变量的非负约束即Xj0，但要注意也存在例外的情形。32线性规划 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）33线性规划 Linear Programming（LP）基本概念线性规划问题

22、的标准形式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）34线性规划 Linear Programming（LP）基本概念化标准形式的一般步骤目标函数极小化“极大化”约束条件的右端项 bi0 “bi0” 约束条件为不等式 或 “=”取值无约束（自由）变量“非负变量”取值非正

23、变量“非负变量”35线性规划 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 037线性规划 Linear Programming（LP）基本概念max z = 2x1 +

24、x2 5x2 15s.t. 6x1 + 2x2 24 x1 + x2 5 x1 ，x2 0唯一最优解 X=（9/2，3/2）38线性规划 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 039x1 + x2 + x3 4a11x1 + a12x2 + a1nxn + xn+1 = b1很快美军中 也相继成立了OR小组。2X1 = 50 X2 X4然后用已有的方法构造模型，并不断修正完善，直至比较满意为止。线性规划 L

25、inear Programming（LP）Xi 0 （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想定（构想）法 当有些问题的机理不清，又缺少数据，又不能作试验来获得数据时，人们只能在已有的知识、经验的基础上，对于未来可能发生的情况给出逻辑上合理的设想和描述。如果该假想单元的各项产出均不低于 j

26、0 决策单元的各项产出，它的各项投入均低于 j0 决策单元的各项的各项投入。线性规划 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可行域40线性规划 Linea

27、r 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是唯一的。可行域41线性规划 Linear Programming（LP）基本概念min Z = 5X1+4X2x1x2oX1 - 1.9X2 = 3.

28、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）可行域此点是唯一最优解42线性规划 Linear Programming（LP）基本概念min Z = 5X1+4X2x1x2oD可行域43线性规划 Linear Programming（LP）基本概念max Z = 5X1+4X2x1x2oD可行域 max Z min Z最优解目标值Z趋于无穷44线性规划 Linear Programming（LP）基本概念max Z

29、 = 5X1+4X2x1x2o可行解域为空45线性规划 Linear Programming（LP）基本概念图解法的启示线性规划问题解的可能情况 a.唯一最优解 b.无穷多最优解 c.无解（没有有界最优解，无可行解）若线性规划问题的可行域非空，则可行域是一个凸集；若线性规划问题的最优解存在，则一定可以在可行域的凸集的某个顶点上达到。46线性规划 Linear Programming（LP）单纯形法 单纯形方法是G.B.Danzig于1947年首先发明的。近50年来，一直是求解线性规划的最有效的方法之一，被广泛应用于各种线性规划问题的求解。本节讨论单纯形法的基本概念、原理及算法。47线性规划 L

30、inear 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）48线性规划 Linear Programming（LP）单纯形法一、线性规划问题的解的概念 可行解 最优解 基 基解（基本解） 基可行解 可行基49线性规划 Linear Programming（LP）单纯形法二、凸集及其顶点 凸集 顶点（极点）凸集凹集50

31、线性规划 Linear Programming（LP）12345678基解（可行）基解（不可行）51线性规划 Linear Programming（LP）单纯形法三、线性规划基本定理基本定理 1 线性规划所有可行解组成的集合S= X | AX = b，X 0 是凸集。基本定理 2 X是线性规划问题的基本可行解的充要条件为是 X 是凸集S= X | AX = b，X 0 的极点。基本定理 3 给定线性规划问题， A是秩为 m 的 mn 矩阵， （i） 若线性规划问题存在可行解，则必存在基本可行解 （ii）若线性规划问题存在有界最优解，则必存在有界最优基本可行解。52线性规划 Linear Pro

32、gramming（LP）单纯形法单纯形法迭代原理及其思路单纯形法的初步讨论例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）53线性规划 Linear Programming（LP）单纯形法 此线性规划问题转化为了一个含有四个变量的标准形线性规划问题，X3，X4为松弛变量。为求解上面的LP问题，我们要考虑满足约束条件s.t.并使 Z 取得Max的X1，X2

33、，X3，X4的值，由此分析如下54线性规划 Linear Programming（LP）单纯形法确定初始基可行解 通过观察可以发现，松弛变量X3和X4对应的等式约束条件中的系数矩阵为单位矩阵可以作为初始可行基矩阵。因此取 X3，X4为基变量；X1，X2为非基变量。则（1.18）可变为 Max Z = 50X1+30X2 s.t. X3 = 120 - 4X1 - 3X2 X4= 50 - 2X1 - X2 （1.19） X1，X2，X3，X4055线性规划 Linear Programming（LP）单纯形法典式（1.19）或（1.18）称为关于基的典式 1、等式约束条件中显含基可行解 2、目

34、标函数中不含基变量Max Z = 50X1+30X2s.t. 4X1+3X2 +X3 = 120 2X1+ X2 + X4 = 50 ( 1.18 ) X1，X2，X3，X4 0Max Z =50X1+30X2s.t. X3 = 120 - 4X1 - 3X2 X4= 50 - 2X1 - X2 （1.19 ） X1，X2，X3，X4056线性规划 Linear Programming（LP）单纯形法 在典式（1.19）中令 X1=X2 =0，我们得到一个基本可行解 X1 =（ X1，X2，X3，X4 ）T=（0，0，120，50）T ，其对应的目标函数值 Z1 = 50X1 + 30X2 =

35、 057线性规划 Linear Programming（LP）单纯形法最优性检验 基本可行解 X1 是最优解吗？显然不是。应寻找更好的解。从问题的数学角度分析，在典式（1.19）的目标函数中，非基变量X1，X2前的系数都为正，而此时的X1，X2均取零值，表明只要增加其值，则目标函数值有增加的可能。因此，将目标函数中系数为正的某一非基变量与某一基变量地位对换。58线性规划 Linear Programming（LP）单纯形法换基迭代 进行换基就是要从非基变量中选一个变量入基，再从基变量中选一个变量出基。并且换基后仍需满足 新的解仍是基本可行解； 目标函数值将得到改善。59线性规划 Linear

36、Programming（LP）单纯形法选择入基变量 由于在目标函数 Z1 =50X1+30X2 中X1，X2的系数都为正，哪一个入基都可使目标函数值得到改善。对于求目标函数极大化的问题，我们希望目标值增加得越快越好，因此系数最大的X1入基。选择出基变量 X1入基后，其值从零增加并由于约束条件的原因会引起其他变量的变化。由典式（1.19）以及变量必须取正值（可行）的条件，我们可以得到下列不等式关系 X3 = 120 4X1 3X2 0 X4= 50 2X1 X2 060线性规划 Linear Programming（LP）单纯形法 因为迭代后X2仍为非基变量（仍会令其取值为零），则上式可简化为

37、120 4X1 0 ，且 50 2X1 0 ， 由此可以看出，虽然我们希望X1入基后取正值，取值越大目标值增加越大，但是 X1又得受到以上约束（保证其可行）。 显然，当取 X1 =min（120/4，50/2）=25时，才能使上述不等式成立，且此时恰使基变量X4变为零，这正好满足非基变量必须取值零的条件，所以可令X4 出基，这样，新的基变量变为X3 ，X1 ，而 X2 ，X4 成了非基变量，则61线性规划 Linear Programming（LP）单纯形法约束方程变为 4X1+ X3 =120 3X2 2X1 = 50 X2 X4化简后得新的典式方程 X3 = 20 X2 + 2X4 X1

38、= 25 0.5X2 0.5X462线性规划 Linear Programming（LP）单纯形法代入目标函数可得 Z2 =1250+5X225X4 令非基变量X2 =X4 = 0，即可得一个新的基本可行解 X2 =（ 25，0，20，0）T ，其对应的目标函数值Z2 =1250，并完成了第一次迭代。由于目标函数 Z2 =1250+5X225X4中X2的系数仍为正，该解X2仍不是最优解。重复上述迭代过程得到X2入基，X3出基，则新的典式方程变为 X1 = 15 +0.5X3 1.5X4 X2 =20 X3 + 2X4 Z3 =1350 5X3 15X463线性规划 Linear Program

39、ming（LP）单纯形法第三个基本可行解 X3 =（ 15，20，0，0）T，其对应的目标函数值 Z3 = 1350 。此时松弛变量 都是非基变量（取值为零），这表明资源已用尽；并且目标函数值 Z3 =1350 5X3 15X4中非基变量X3，X4的系数全为负值，说明目标函数已无法进一步改善，因此该解已是最优解。64线性规划 Linear Programming（LP）单纯形法小结 单纯形法是这样一种迭代算法如下图当 Zk 中非基变量的系数的系数全为负值时，这时的基本可行解 Xk 即是 线性规划问题的最优解，迭代结束。X1Z1保持单调增保持可行性保持可行性保持可行性保持可行性保持单调增保持单调

40、增保持单调增X2X3.XkZ2Z3.Zk 当 Zk 中非基变量的系数的系数全为负值时，这时的基本可行解 Xk 即是线性规划问题的最优解，迭代结束。65线性规划 Linear Programming（LP）单纯形表对于给定的线性规划问题max Z = c1x1 + c2x2 + + cnxn a11x1 + a12x2 + + a1nxn b1 a21x1 + a22x2 + + a2nxn b2s.t. am1x1 + am2x2 + + amnxn bm xj 0 （j=1，2 n） 对此问题添加m个松弛变量后，可得下面线性规划问题并且是典式的形式。66线性规划 Linear Program

41、ming（LP）单纯形表线性规划的典式max Z = c1x1 + c2x2 + + cnxn a11x1 + a12x2 + a1nxn + xn+1 = b1 a21x1 + a22x2 + a2nxn + xn+2 = b2s.t. am1x1 + am2x2 + amnxn + xn+m = bm xj 0 （j=1，2 n，n+1，n+2，n+m）67线性规划 Linear Programming（LP）单纯形表 将上面典式中各变量及系数填写在一张表格中就形成下面的单纯形表cj c1 c2cn000CB基变量基解x1x2xnxn+1xn+2xn+m0 xn+1 b1a11a12a1n

42、110 xn+2 b2a21a22a2n120 xn+m bmam1am2amn1j = cj zj c1 c2cn00012nn+1n+2n+m基矩阵B=I非基矩阵N=ACNCBB-1b注意：在今后的迭代中基矩阵 B 会不断地发生变化！XB68线性规划 Linear Programming（LP）单纯形表 上面的单纯形表还可以表示成矩阵的形式基解 X XSXSb A Ij C 0基解 XB XN XSXSb B N Ij CB CN 0或69线性规划 Linear Programming（LP）单纯形法由单纯形表进行迭代步骤选择 Xj 入基当 j 行中 j= max i i 0 选择 Xi

43、出基当 i = min bi/aijaij 0 换基迭代当确定了入基变量 Xj 、出基变量 Xi 后，以 aij 作为主元对单纯形表进行取主运算，取主运算即采用初等行变换将主元 aij 所在列，除将 aii 变换为1而外，该列中的其余元素都变换为 0。注意这种变换只能采用初等行变换!70线性规划 Linear Programming（LP）单纯形法最优解检验当迭代进行至某一步时，j 行中所有检验数均小于等于零，则迭代结束。表中当前所指基本可行解即为最优解。当迭代进行至某一步时，j 行中所有检验数均小于等于零，且此时至少有一个非基变量所对应的检验数k 等于零，则原线性规划问题有无穷多个最优解。当

44、迭代进行至某一步时，j 行中至少有一个检验数 k 大于零，且该检验数对应的列中a1k ，a2k ， amk ，均小于等于零，则原线性规划问题最优解无界（ max Z +）。71线性规划 Linear Programming（LP）单纯形方法的矩阵描述设线性规划问题 max Z = CX max Z = CX + 0XS s.t. AX b s.t. AX + I XS = b （I 式） X 0 X ，XS 0其中 b 0 ，I 是 mm 单位矩阵。对上面（I 式）经过迭代，并设最终的最优基矩阵为B（不妨设B 为A 的首m 列，则将（I 式）改写后有72线性规划 Linear Programm

45、ing（LP）单纯形方法的矩阵描述max Z = CBXB + CNXN + 0XS s.t. BXB + NXN + I XS = b XB ，XN，XS 0 max Z = CB B -1+（CN- CB B -1）XN - CB B -1XS s.t. XB + B -1NXN + B -1XS = B -1b XB ，XN，XS 0 B 式中最优目标函数值Z*= CB B -1 ，检验数 CN - CB B -1 0 ， - CB B -1 0单纯形方法迭代（I 式）（B 式）73线性规划 Linear Programming（LP）单纯形方法的矩阵描述基解 XB XN XSXSb B

46、 N Ij CB CN 0基解 XB XN XSXBB -1b I B -1N B -1j 0 CN - CB B 1N - CB B -1对应I 式的单纯形表 I 表对应B 式的单纯形表 B 表迭代74线性规划 Linear Programming（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 075线性规划 Linear Program

47、ming（LP）单纯形表计算步骤举例max z = 50X1 + 30X2s.t. 4X1+ 3X2 + X3 = 120 2X1+ X2 + X4 = 50 X1， X2 ，X3 ，X4 0Cj 503000基XB解B-1bX1X2X3X4X31204310X4502101检验数 j 503000初始单纯形表：基矩阵B非基矩阵NCBCNB-1b基变量非基变量76线性规划 Linear Programming（LP）单纯形表计算步骤举例max z = 50X1 + 30X2s.t. 4X1+ 3X2 + X3 = 120 2X1+ X2 + X4 = 50 X1， X2 ，X3 ，X4 0基X

48、B解B-1bX1X2X3X4X31204310X4502101检验数 j 5030002120/450/2X111/201/2250201- 2050- 2520/125211X2150- 1/23/210- 5- 1577线性规划 Linear Programming（LP）单纯形法的进一步讨论人工变量法 当一般线性规划问题标准化之后，我们或可得到一个显然的基本可行解（如松弛变量作为基变量的一个初始基本可行解），这样我们就可以马上进入单纯形表的运算步骤。然而，并非所有问题标准化之后我们都可得到一个显然的初始基本可行解，这时就需要我们首先确定出一个基本可行解作为初始基本可行解。通常采用的是人工

49、变量法来确定这样的初始基本可行解。这种情况下一般有两种方法 大M法（罚因子法） 两阶段法78线性规划 Linear Programming（LP）单纯形法的进一步讨论1、大 M 法（罚因子法）max z = - 3X1 + X3 x1 + x2 + x3 4 - 2x1 + x2 x3 1 3x2 + x3 = 9 x1 ，x2 ，x3 0LPM max z = - 3x1 + x3 + 0 x4 + 0 x5 Mx6 Mx7 x1 + x2 + x3 + x4 = 4 - 2x1 + x2 x3 - x5 + x6 = 1 3x2 + x3 +x7 = 9 x1 ，x2 ，x3 ， x4 ，

50、 x5 ， x6 ， x7 079线性规划 Linear Programming（LP）1、大 M 法LPM max z = - 3x1 + x3 + 0 x4 + 0 x5 Mx6 Mx7 x1 + x2 + x3 + x4 = 4 - 2x1 + x2 x3 - x5 + x6 = 1 3x2 + x3 +x7 = 9 x1 ，x2 ，x3 ， x4 ， x5 ， x6 ， x7 0基XB解B-1bX1X2X3X4X5X6X7X441111000X61-21-10-110X790310001检验数 j-30100-M-M80线性规划 Linear Programming（LP）1、大 M

51、法基XB解B-1bX1X2X3X4X5X6X7X441111000X61-21-10-110X790310001检验数 j-3-2MM1-M0-M0-M基XB解B-1bX1X2X3X4X5X6X7X441111000X61-21-10-110X790310001检验数 j-3-2M4M10-M0081线性规划 Linear Programming（LP）1、大 M 法基XB解B-1bX1X2X3X4X5X6X7X4411110004X61-21-10-1101X7903100013检验数 j-3-2M4M10-M00基XB解B-1bX1X2X3X4X5X6X7X4330211-10X21-21

52、-10-110X7660403-31检验数 j-3+6M01+4M03M-4M082线性规划 Linear Programming（LP）1、大 M 法基XB解B-1bX1X2X3X4X5X6X7X4330211-101X21-21-10-110X7660403-311检验数 j-3+6M01+4M03M-4M0基XB解B-1bX1X2X3X4X5X6X7X400001-1/21/2-1/2X23011/30001/3X11102/301/2-1/21/6检验数 j00301.5-1.5-M0.5-M83线性规划 Linear Programming（LP）1、大 M 法基XB解B-1bX1X

53、2X3X4X5X6X7X400001-1/21/2-1/2X23011/30001/39X11102/301/2-1/21/63/2检验数 j00301.5-1.5-M0.5-M基XB解B-1bX1X2X3X4X5X6X7X400001-1/21/2-1/2X25/2-1/2100-1/41/41/4X33/23/20103/4-3/41/4检验数 j-9/2000-3/43/4-M-1/4-M84线性规划 Linear Programming（LP）采用大 M 法求解线性规划问题时可能出现的几种情况当采用单纯形法求解 LPM 得到最优解时，基变量不含任何人工变量，则所得到的最优解就是原问题的

54、最优解；当采用单纯形法求解 LPM 得到最优解时，基变量至少含有一个人工变量且非零，则原问题无可行解；当采用单纯形法求解 LPM 得到最优解时，基变量至少含有一个人工变量且人工变量都为零，则通过变换得到原问题最优解；85线性规划 Linear Programming（LP）2、两阶段法max z = - 3X1 + X3 x1 + x2 + x3 4 - 2x1 + x2 x3 1 3x2 + x3 = 9 x1 ，x2 ，x3 0I阶段问题 max z = x6 x7 x1 + x2 + x3 + x4 = 4 - 2x1 + x2 x3 - x5 + x6 = 1 3x2 + x3 +x7

55、 = 9 x1 ，x2 ，x3 ， x4 ， x5 ， x6 ， x7 086线性规划 Linear Programming（LP）2、两阶段法I 阶段问题 max z = x6 x7 x1 + x2 + x3 + x4 = 4 - 2x1 + x2 x3 - x5 + x6 = 1 3x2 + x3 +x7 = 9 x1 ，x2 ，x3 ， x4 ， x5 ， x6 ， x7 0基XB解B-1bX1X2X3X4X5X6X7X441111000X61-21-10-110X790310001检验数 j00000-1-187线性规划 Linear Programming（LP）2、两阶段法第I 阶

56、段基XB解B-1bX1X2X3X4X5X6X7X441111000X61-21-10-110X790310001检验数 j00000-1-1基XB解B-1bX1X2X3X4X5X6X7X441111000X61-21-10-110X790310001检验数 j-2400-10088线性规划 Linear Programming（LP）2、两阶段法第I 阶段基XB解B-1bX1X2X3X4X5X6X7X4411110004X61-21-10-1101X7903100013检验数 j-2400-100基XB解B-1bX1X2X3X4X5X6X7X4330211-10X21-21-10-110X76

57、60403-31检验数 j60403-4089线性规划 Linear Programming（LP）2、两阶段法第I 阶段基XB解B-1bX1X2X3X4X5X6X7X4330211-101X21-21-10-110X7660403-311检验数 j60403-40基XB解B-1bX1X2X3X4X5X6X7X400001-1/21/2-1/2X23011/30001/3X11102/301/2-1/21/6检验数 j00000-1-190线性规划 Linear Programming（LP）2、两阶段法第II 阶段基XB解B-1bX1X2X3X4X5X6X7X400001-1/21/2-1/

58、2X23011/30001/3X11102/301/2-1/21/6检验数 j00000-1-1基XB解B-1bX1X2X3X4X5X400001-1/2X23011/300X11102/301/2检验数 j00303/2-3010091线性规划 Linear Programming（LP）2、两阶段法第II 阶段基XB解B-1bX1X2X3X4X5X400001-1/2X23011/3009X11102/301/23/2检验数 j00303/2基XB解B-1bX1X2X3X4X5X400001-1/2X25/2-1/2100-1/4X33/23/20103/4检验数 j-9/2000-3/4

59、92线性规划 Linear Programming（LP）单纯形法中的几个问题目标函数极小化时，解的最优判别 j 0退化 一个或几个基变量等于零，一个简单易行的避免退化的方法是1974年由勃兰德（Bland）提出的Bkand 法则。无可行解的判别 在采用人工变量求解线性规划问题得到最优解时，如果基变量中仍含有非零人工变量，则原问题无可行解。93线性规划 Linear Programming（LP）数据包络分析DEA （date envelopment analysis）引言 一种基于线性规划的用于评价同类型组织（或项目）工作绩效相对有效性的特殊工具手段。这类组织例如学校、医院、银行的分支机构、

60、超市的各个营业部等，各自具有相同的投入相同的产出。衡量这类组织之间的绩效高低，通常采用投入产出比这个指标，当各自的投入产出均可折算成同一单位计量时，容易计算出各自的投入产出比并按其大小进行绩效排序。但当被衡量的同类型组织有多项投入和多项产出，且不能折算成统一单位时，就无法算出投入产出比的数值，因而，需采用一种全新的方法进行绩效比较。这种方法就是二十世纪七十年代末产生的数据包络分析DEA。94线性规划 Linear Programming（LP）数据包络分析DEA （date envelopment analysis）引言 1978年，著名运筹学家、美国德克萨斯大学教授A.Charnes及W.W