线性规划单纯形法详解演示文稿

线性规划单纯形法详解演示文稿1现在是1页\一共有127页\编辑于星期三（优选）线性规划单纯形法2现在是2页\一共有127页\编辑于星期三绪论

历史，性质，应用20世纪整个世界参与规模最大的事件是什么？第二次世界大战！整个世界的资源都投入到了第二次世界大战中。如何才能更好地利用资源，分配有限的资源，这是一个值得研究的问题。当时在英国军队中率先成立了研究小组——运筹小组来研究这些问题，这就是著名的OR小组.很快美军中也相继成立了OR小组。战争——运筹学诞生的温床。3现在是3页\一共有127页\编辑于星期三绪论

历史，性质，应用二战中成功的运筹学案例：英国防空部门如何布置防空雷达，建立最有效的防空警报系统。英，美空军如何提高对地面目标轰炸的命中率。如何安排反潜飞机的巡逻飞行线路。深水炸弹的合理爆炸深度，摧毁德军潜艇数增加400%。商船如何编队，遭潜艇攻击时如何减少损失。使船只受敌机攻击时，中弹数由47%降到29%。这些研究大大提高了盟军的作战能力，为反法西斯战争的最后胜利作出了巨大的贡献！4现在是4页\一共有127页\编辑于星期三绪论

历史，性质，应用战争结束了！

整个世界投入到了战后的重建国家的经济之中。运筹学的方法相继在工业，农业，经济，社会问题等各个领域中展开了应用。与此同时，运筹数学有了飞快的发展，并形成了许多运筹学的分支。线性规划，非线性规划，整数规划，目标规划，动态规划，图与网络分析，统筹方法，排队论，存储论，对策论，决策论，多目标决策。5现在是5页\一共有127页\编辑于星期三绪论

历史，性质，应用运筹学的性质和特点一种哲学方法论;研究“事”而非“物”;科学性，实践性，系统性，综合性;模型的特点——系统优化模型。运筹学——为决策机构在对其控制下业务活动进行决策时，提供以数量化为基础的科学方法。运筹学——一门应用科学，它广泛应用现有的科学技术知识和数学方法，解决实际中提出的专门问题。运筹学——是一种给出问题坏的答案的艺术，否则问题的结果会更坏。6现在是6页\一共有127页\编辑于星期三绪论

历史，性质，应用运筹学的工作步骤

运筹学在解决大量实际问题的过程中形成了自己的工作步骤：提出和形成问题。即弄清问题的目标，可能的约束，问题的可控变量以及有关参数，搜集有关资料;建立模型。即把问题中可控变量，参数和目标与约束之间的关系用一定的模型表示出来;求解。用各种手段（主要是数学方法，也可用其他方法）将模型求解。解可以是最优解、次优解、满意解。复杂模型的求解需用计算机，解的精度要可由求决策者提出。7现在是7页\一共有127页\编辑于星期三绪论

历史，性质，应用运筹学的工作步骤解的检验。首先检查求解步骤和程序有无错误，然后检查解是否反映现实问题；解的控制。通过控制解的变化过程决定是否要作一定的改变；解的实施。是指将解用到实际中必须考虑到实施的问题，如向实际部门讲清解的用法，在实施中可能产生的问题和修改。8现在是8页\一共有127页\编辑于星期三绪论

历史，性质，应用运筹学的模型模型的三种基本形式：（1）形象模型，（2）模拟模型，（3）符号或数学模型。构造模型是一种创造性劳动，成功的模型往往是科学和艺术的结晶，构造模型的方法和思路通常有以下几种：9现在是9页\一共有127页\编辑于星期三绪论

历史，性质，应用直接分析法

按研究者对问题内在机理的认识直接构造出模型。类比法

有些问题可以用不同方法构造出模型；而这些模型的结构性质是类同的，这就可以互相类比。数据分析法

对有些问题的机理尚未了解清楚，若能搜集到与此问题密切有关的大量数据，或通过某些试验获得大量数据，这就可以用统计分析法建摸。10现在是10页\一共有127页\编辑于星期三绪论

历史，性质，应用试验分析法

有些问题的机理不清，又不能作大量试验来获得数据，这时只能通过做局部试验的数据加上分析来构造模型。想定（构想）法当有些问题的机理不清，又缺少数据，又不能作试验来获得数据时，人们只能在已有的知识、经验的基础上，对于未来可能发生的情况给出逻辑上合理的设想和描述。然后用已有的方法构造模型，并不断修正完善，直至比较满意为止。11现在是11页\一共有127页\编辑于星期三绪论

历史，性质，应用运筹学的主要应用

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

历史，性质，应用运输问题涉及空运、水运、公路、铁路运输、管道运输等。公路网的设计和分析，市内公共汽车路线的选择和行车时刻表的安排，出租车的调度等。人事管理需求估计，教育和培训，人员分配（各种指派问题），合理利用，人才评价等。设备维修，更新和可靠性等。13现在是13页\一共有127页\编辑于星期三绪论

历史，性质，应用计算机和信息系统内存分配研究，网络设计分析等。城市管理紧急服务系统的设计和运用，区域布局规划，管道网络设计等。（美）曾用排队论确定纽约市紧急电话站的值班人数，（加）设计城市警车配置和负责范围、指挥接警后的行走路线等。对策研究价格竞争，中央与地方政府投资分配博弈，工会与雇主间的博弈。14现在是14页\一共有127页\编辑于星期三第一讲线性规划LinearProgramming(LP)目标规划GoalProgramming(GP)整数规划IntegerProgramming(IP)15现在是15页\一共有127页\编辑于星期三第一章线性规划及单纯形法线性规划LinearProgramming（LP）16现在是16页\一共有127页\编辑于星期三引言线性规划是运筹学的一个重要分支，也是运筹学中应用最广泛的方法之一。调查表明，在世界500家最大的企业中，有85%的企业都曾使用线性规划解决经营管理中遇到的复杂问题。线性规划的使用为应用者节约了数以亿万计的资金。解决有限资源在有竞争的使用方向中如何进行最佳分配。线性规划LinearProgramming（LP）17现在是17页\一共有127页\编辑于星期三本讲中我们将讨论什么是线性规划问题，线性规划问题的数学表示，基本理论、概念和求解方法。线性规划问题是什么样的一类问题呢？请看案例线性规划LinearProgramming（LP）18现在是18页\一共有127页\编辑于星期三线性规划LinearProgramming（LP）曾几何时长江水，哺育华夏代代人;谁知后代疏珍惜，清清江水黑如泥。案例河流污染治理规划问题19现在是19页\一共有127页\编辑于星期三线性规划LinearProgramming（LP）曾几何时长江水，哺育华夏代代人;谁知后代疏珍惜，清清江水黑如泥。工厂2工厂3工厂1工厂4工厂5工厂6工厂9工厂8工厂7案例河流污染治理规划问题20现在是20页\一共有127页\编辑于星期三线性规划LinearProgramming（LP）曾几何时长江水，哺育华夏代代人;谁知后代疏珍惜，清清江水黑如泥。今日认识未为晚，吾辈齐心治环境;线性规划大有用，定让江水绿如蓝。工厂2工厂3工厂1工厂4工厂5工厂6工厂9工厂8工厂7案例河流污染治理规划问题21现在是21页\一共有127页\编辑于星期三线性规划LinearProgramming（LP）今日认识未为晚，吾辈齐心治环境;线性规划大有用，定让江水绿如蓝。曾几何时长江水，哺育华夏代代人;谁知后代疏珍惜，清清江水黑如泥。工厂2工厂3工厂1工厂4工厂5工厂6工厂9工厂8工厂7案例河流污染治理规划问题22现在是22页\一共有127页\编辑于星期三线性规划LinearProgramming（LP）案例河流污染治理规划问题背景资料:长江流域某区域内有9化工厂，各厂每月产生的工业污水量如表-1，流经各化工厂的河流流量如表-2，各化工厂治理工业污水的成本如表-3。上游厂排放的污水流到相邻下游厂以前，有20%可自然净化。根据环保标准河流中此种工业污水的含量不应超过0.2%。从该区域整体考虑，各化工厂应该分别处理多少工业污水才能既满足环保要求，又使9化工厂治理工业污水的总费用最少。23现在是23页\一共有127页\编辑于星期三背景资料:线性规划LinearProgramming（LP）化工厂11.2化工厂42化工厂72化工厂21化工厂51化工厂80.8化工厂33化工厂61化工厂91.5表-1污水产生量单位：万m3表-2流经各化工厂的河流流量单位：万m3表-3治理工业污水的成本单位：百万元/万m3化工厂1500化工厂41200化工厂71200化工厂2300化工厂5600化工厂8200化工厂31800化工厂6400化工厂9700化工厂13化工厂44化工厂71化工厂25化工厂55化工厂82化工厂32化工厂66化工厂9324现在是24页\一共有127页\编辑于星期三线性规划LinearProgramming（LP）194582637问题分析：区域污染治理的决策——各个化工厂应处理的工业污水量（或应排放的工业污水量）。区域污染治理的约束——即满足环保要求排放工业污水（区域内河流中任何点检测都应符合环保标准）。区域污染治理的目标——总治理成本最少。这类问题的共同特点：三大要素决策，目标，约束25现在是25页\一共有127页\编辑于星期三线性规划LinearProgramming（LP）194582637建模分析：设第i个化工厂应处理的工业污水量为Xi万m3，则根据问题描述的情况以化工厂1、2、…、9加以分析则可得如下近似关系式对化工厂2应有（1-X2）/300≦0.2%对化工厂8应有（0.8-X8）/200≦0.2%对化工厂1应有｛（1.2-X1）+0.8（1-X2）+（0.8-X8）｝/500≦0.2%26现在是26页\一共有127页\编辑于星期三线性规划LinearProgramming（LP）194582637对化工厂9应有——（1.5-X9）/700≦0.2%对化工厂7应有——

（2-X7）+0.8（1.5-X9）/1200≦0.2%……此外显然还应有Xi≧0（i=1，2，3…8，9）综上所述决策者所需考虑的区域内各个化工厂应处理的工业污水量Xi应满足上述所有不等式方程。我们将这些不等式方程构成的方程组称为污水治理的约束条件。27现在是27页\一共有127页\编辑于星期三线性规划LinearProgramming（LP）194582637另一方面污水治理的总成本可表示为ZZ=3X1+5X2+2X3+4X4+5X5+6X6+1X7+2X8+3X9而决策者的目标是确定满足约束条件的Xi使得Z取得最小值。将上述分析归纳后即可得如下数学符合模型：28现在是28页\一共有127页\编辑于星期三线性规划LinearProgramming（LP）河流污染治理规划问题数学模型（整理之后）194582637MinZ=3X1+5X2+2X3+4X4+5X5+6X6+1X7+2X8+3X9X2≧0.4X8≧0.4X1+0.8X2+0.8X8≧1.64X9≧0.1X7+0.8X9≧0.8X4+0.8X7+0.64X9≧2.16X6≧0.2X5+0.8X6≧0.6X3+0.8X4+0.8X5+0.64X6+0.64X7+5.12X9≧9.4Xi≧0（i=1，2，3，4，5，6，7，8，9）s.t.29现在是29页\一共有127页\编辑于星期三线性规划LinearProgramming（LP）基本概念

线性规划模型——LinearProgrammingModel或LinearOptimizationModel用线性规划方法解决实际经济与管理问题的第一步是分析建立能够完整描述和反映实际问题的线性规划模型。30现在是30页\一共有127页\编辑于星期三线性规划LinearProgramming（LP）基本概念通常建立LP模型有以下几个基本步骤：确定决策变量：决策变量是模型要确定的未知变量，也是模型最重要的参数，是决策者解决实际问题的控制变量。确定目标函数：目标函数决定线性规划问题的优化方向，是模型的重要组成部分。实际问题的目标可表示为决策变量的一个线性函数，并根据实际问题的优化方向求其最大化（max）或最小化（min）。31现在是31页\一共有127页\编辑于星期三线性规划LinearProgramming（LP）基本概念

通常建立LP模型有以下几个步骤：确定约束方程：一个正确的线性规划模型应能通过约束方程来描述和反映一系列客观条件或环境的限制，这些限制通过一系列线性等式或不等式方程组来描述。变量取值限制：一般情况下，决策变量取正值（非负值）。因此，模型中应有变量的非负约束即Xj≥0，但要注意也存在例外的情形。32现在是32页\一共有127页\编辑于星期三线性规划LinearProgramming（LP）基本概念线性规划的一般形式:

max（或min）z=c1x1

+c2x2+…+cnxna11x1+a12x2+…+a1nxn（≤=≥）b1a21x1+a22x2+…+a2nxn

（≤=≥）b2s.t.………………am1x1+am2x2+…+amnxn（≤=≥）bm

xj≥0（j=1，2…n）33现在是33页\一共有127页\编辑于星期三线性规划LinearProgramming（LP）基本概念线性规划问题的标准形式1、目标函数极大化——“max”2、等式约束条件——“=”且右端常数bi非负3、变量非负——“xj≥0”maxz=c1x1

+c2x2+…+cnxna11x1+a12x2+…+a1nxn=b1a21x1+a22x2+…+a2nxn=b2s.t.……………am1x1+am2x2+…+amnxn=bmxj≥0（j=1，2…n）34现在是34页\一共有127页\编辑于星期三线性规划LinearProgramming（LP）基本概念化标准形式的一般步骤目标函数极小化“极大化”约束条件的右端项bi≤0“bi≥0”约束条件为不等式≤或≥“=”取值无约束（自由）变量“非负变量”取值非正变量“非负变量”35现在是35页\一共有127页\编辑于星期三线性规划LinearProgramming（LP）基本概念线性规划问题的求解解：（图解）如何求解一般的线性规划呢？下面我们分析一下简单的情况——只有两个决策变量的线性规划问题，这时可以通过图解的方法来求解。图解法具有简单、直观、便于初学者窥探线性规划基本原理和几何意义等优点。36现在是36页\一共有127页\编辑于星期三线性规划LinearProgramming（LP）基本概念例1（page11）maxz=2x1+x25x2

≤15s.t.6x1+2x2

≤24x1+x2

≤5x1，x2

≥037现在是37页\一共有127页\编辑于星期三线性规划LinearProgramming（LP）基本概念maxz=2x1+x25x2≤15s.t.6x1+2x2≤24x1+x2≤5x1，x2≥0唯一最优解X=（9/2，3/2）38现在是38页\一共有127页\编辑于星期三线性规划LinearProgramming（LP）基本概念例maxZ=2X1+X2

X1+1.9X2≥3.8X1-1.9X2≤3.8s.t.X1+1.9X2≤10.2X1-1.9X2≥-3.8X1，X2≥039现在是39页\一共有127页\编辑于星期三线性规划LinearProgramming（LP）基本概念maxZ=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）DmaxZminZ此点是唯一最优解，且最优目标函数值maxZ=17.2可行域40现在是40页\一共有127页\编辑于星期三线性规划LinearProgramming（LP）基本概念maxZ=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

maxZminZ（3.8，4）34.2=3X1+5.7X2

绿色线段上的所有点都是最优解这种情形为有无穷多最优解，但是最优目标函数值maxZ=34.2是唯一的。可行域41现在是41页\一共有127页\编辑于星期三线性规划LinearProgramming（LP）基本概念minZ=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

maxZminZ8=5X1+4X2

43=5X1+4X2

（0，2）可行域此点是唯一最优解42现在是42页\一共有127页\编辑于星期三线性规划LinearProgramming（LP）基本概念minZ=5X1+4X2x1x2oD可行域43现在是43页\一共有127页\编辑于星期三线性规划LinearProgramming（LP）基本概念maxZ=5X1+4X2x1x2oD可行域maxZminZ最优解目标值Z趋于无穷44现在是44页\一共有127页\编辑于星期三线性规划LinearProgramming（LP）基本概念maxZ=5X1+4X2x1x2o可行解域为空45现在是45页\一共有127页\编辑于星期三线性规划LinearProgramming（LP）基本概念图解法的启示线性规划问题解的可能情况a.唯一最优解b.无穷多最优解c.无解（没有有界最优解，无可行解）若线性规划问题的可行域非空，则可行域是一个凸集；若线性规划问题的最优解存在，则一定可以在可行域的凸集的某个顶点上达到。46现在是46页\一共有127页\编辑于星期三线性规划LinearProgramming（LP）单纯形法

单纯形方法是于1947年首先发明的。近50年来，一直是求解线性规划的最有效的方法之一，被广泛应用于各种线性规划问题的求解。本节讨论单纯形法的基本概念、原理及算法。47现在是47页\一共有127页\编辑于星期三线性规划LinearProgramming（LP）单纯形法给定线性规划问题（标准形式）maxz=c1x1

+c2x2+…+cnxna11x1+a12x2+…+a1nxn

=b1a21x1+a22x2+…+a2nxn

=b2s.t.……………am1x1+am2x2+…+amnxn

=bmxj≥0（j=1，2…n）48现在是48页\一共有127页\编辑于星期三线性规划LinearProgramming（LP）单纯形法一、线性规划问题的解的概念

可行解最优解基基解（基本解）基可行解可行基49现在是49页\一共有127页\编辑于星期三线性规划LinearProgramming（LP）单纯形法二、凸集及其顶点凸集顶点（极点）凸集凹集50现在是50页\一共有127页\编辑于星期三线性规划LinearProgramming（LP）12345678基解（可行）基解（不可行）51现在是51页\一共有127页\编辑于星期三线性规划LinearProgramming（LP）单纯形法三、线性规划基本定理基本定理1

线性规划所有可行解组成的集合S={X|AX=b，X≥0}是凸集。基本定理2

X是线性规划问题的基本可行解的充要条件为是X是凸集S={X|AX=b，X≥0}的极点。基本定理3

给定线性规划问题，A是秩为m的mn矩阵，

（i）若线性规划问题存在可行解，则必存在基本可行解（ii）若线性规划问题存在有界最优解，则必存在有界最优基本可行解。52现在是52页\一共有127页\编辑于星期三线性规划LinearProgramming（LP）单纯形法单纯形法迭代原理及其思路单纯形法的初步讨论例1.8求解LP问题

化为标准型MaxZ=50X1+30X2s.t.4X1+3X2≤

1202X1+X2≤50X1，X2≥0MaxZ=50X1+30X2s.t.4X1+3X2+X3

=

1202X1+X2

+X4

=50X1，X2，X3，X4

≥0（1.18）53现在是53页\一共有127页\编辑于星期三线性规划LinearProgramming（LP）单纯形法此线性规划问题转化为了一个含有四个变量的标准形线性规划问题，X3，X4为松弛变量。为求解上面的LP问题，我们要考虑满足约束条件s.t.并使Z取得Max的X1，X2，X3，X4的值，由此分析如下54现在是54页\一共有127页\编辑于星期三线性规划LinearProgramming（LP）单纯形法确定初始基可行解：通过观察可以发现，松弛变量X3和X4对应的等式约束条件中的系数矩阵为单位矩阵可以作为初始可行基矩阵。因此取X3，X4为基变量；X1，X2为非基变量。则（1.18）可变为：

Max

Z

=50X1+30X2s.t.X3=120-4X1-3X2X4=50-2X1-X2（1.19）X1，X2，X3，X4≥055现在是55页\一共有127页\编辑于星期三线性规划LinearProgramming（LP）单纯形法典式（1.19）或（1.18）称为关于基的典式——1、等式约束条件中显含基可行解2、目标函数中不含基变量MaxZ=50X1+30X2s.t.4X1+3X2+X3

=

1202X1+X2

+X4

=50(1.18)X1，X2，X3，X4≥0MaxZ

=50X1+30X2s.t.X3

=120-4X1-3X2

X4=50-2X1-X2（1.19）X1，X2，X3，X4≥056现在是56页\一共有127页\编辑于星期三线性规划LinearProgramming（LP）单纯形法在典式（1.19）中令：X1=X2

=0，我们得到一个基本可行解

X1=（X1，X2，X3，X4）T=（0，0，120，50）T

，其对应的目标函数值Z1=50X1+30X2=057现在是57页\一共有127页\编辑于星期三线性规划LinearProgramming（LP）单纯形法最优性检验：基本可行解X1是最优解吗？显然不是。应寻找更好的解。从问题的数学角度分析，在典式（1.19）的目标函数中，非基变量X1，X2前的系数都为正，而此时的X1，X2均取零值，表明只要增加其值，则目标函数值有增加的可能。因此，将目标函数中系数为正的某一非基变量与某一基变量地位对换。58现在是58页\一共有127页\编辑于星期三线性规划LinearProgramming（LP）单纯形法换基迭代：进行换基就是要从非基变量中选一个变量入基，再从基变量中选一个变量出基。并且换基后仍需满足：

新的解仍是基本可行解；目标函数值将得到改善。59现在是59页\一共有127页\编辑于星期三线性规划LinearProgramming（LP）单纯形法选择入基变量：

由于在目标函数Z1

=50X1+30X2中X1，X2的系数都为正，哪一个入基都可使目标函数值得到改善。对于求目标函数极大化的问题，我们希望目标值增加得越快越好，因此系数最大的X1入基。选择出基变量：

X1入基后，其值从零增加并由于约束条件的原因会引起其他变量的变化。由典式（1.19）以及变量必须取正值（可行）的条件，我们可以得到下列不等式关系：X3=120-4X1-3X2≥0X4=50-2X1-X2≥060现在是60页\一共有127页\编辑于星期三线性规划LinearProgramming（LP）单纯形法

因为迭代后X2仍为非基变量（仍会令其取值为零），则上式可简化为：120-4X1≥0，且50-2X1≥0，由此可以看出，虽然我们希望X1入基后取正值，取值越大目标值增加越大，但是X1又得受到以上约束（保证其可行）。显然，当取X1=min（120/4，50/2）=25时，才能使上述不等式成立，且此时恰使基变量X4变为零，这正好满足非基变量必须取值零的条件，所以可令X4出基，这样，新的基变量变为X3，X1，而X2，X4成了非基变量，则61现在是61页\一共有127页\编辑于星期三线性规划LinearProgramming（LP）单纯形法约束方程变为：4X1+X3=120-3X22X1=50-X2-X4化简后得：新的典式方程X3=20-X2+2X4X1=25-0.5X2-0.5X462现在是62页\一共有127页\编辑于星期三线性规划LinearProgramming（LP）单纯形法代入目标函数可得：Z2

=1250+5X2-25X4

令非基变量X2=X4=0，即可得一个新的基本可行解X2=（25，0，20，0）T，其对应的目标函数值Z2

=1250，并完成了第一次迭代。由于目标函数Z2=1250+5X2-25X4中X2的系数仍为正，该解X2仍不是最优解。重复上述迭代过程得到：X2入基，X3出基，则新的典式方程变为：X1=15+0.5X3

-1.5X4X2=20-X3+2X4

Z3

=1350-5X3-15X463现在是63页\一共有127页\编辑于星期三线性规划LinearProgramming（LP）单纯形法第三个基本可行解X3

=（15，20，0，0）T，其对应的目标函数值Z3

=1350。此时松弛变量都是非基变量（取值为零），这表明资源已用尽；并且目标函数值Z3

=1350-5X3-15X4中非基变量X3，X4的系数全为负值，说明目标函数已无法进一步改善，因此该解已是最优解。64现在是64页\一共有127页\编辑于星期三线性规划LinearProgramming（LP）单纯形法小结：

单纯形法是这样一种迭代算法——如下图…当Zk

中非基变量的系数的系数全为负值时，这时的基本可行解Xk

即是线性规划问题的最优解，迭代结束。X1Z1保持单调增保持可行性保持可行性保持可行性保持可行性保持单调增保持单调增保持单调增X2X3...XkZ2Z3...Zk

当Zk

中非基变量的系数的系数全为负值时，这时的基本可行解Xk

即是线性规划问题的最优解，迭代结束。65现在是65页\一共有127页\编辑于星期三线性规划LinearProgramming（LP）单纯形表对于给定的线性规划问题：maxZ=c1x1

+c2x2+…+cnxna11x1+a12x2+…+a1nxn≤b1a21x1+a22x2+…+a2nxn≤b2s.t.………am1x1+am2x2+…+amnxn≤bmxj≥0（j=1，2…n）对此问题添加m个松弛变量后，可得下面线性规划问题并且是典式的形式。66现在是66页\一共有127页\编辑于星期三线性规划LinearProgramming（LP）单纯形表线性规划的典式maxZ=c1x1

+c2x2+…+cnxna11x1+a12x2+…+a1nxn+xn+1=b1a21x1+a22x2+…+a2nxn+

xn+2=b2s.t.…am1x1+am2x2+…+amnxn+

xn+m=bmxj≥0（j=1，2…n，n+1，n+2，…n+m）67现在是67页\一共有127页\编辑于星期三线性规划LinearProgramming（LP）单纯形表：

将上面典式中各变量及系数填写在一张表格中就形成下面的单纯形表cj

c1

c2…cn00…0CB基变量基解x1x2…xnxn+1xn+2…xn+m0xn+1

b1a11a12…a1n1…10xn+2

b2a21a22…a2n1…2………………………………0xn+m

bmam1am2…amn…1j=cj–zjc1

c2…cn00…012…nn+1n+2…n+m基矩阵B=I非基矩阵N=ACNCBB-1b注意：在今后的迭代中基矩阵B会不断地发生变化！！XB68现在是68页\一共有127页\编辑于星期三线性规划LinearProgramming（LP）单纯形表：

上面的单纯形表还可以表示成矩阵的形式基解X

XSXSbAIj

C

0基解XB

XN

XSXSbBNIj

CB

CN

0或69现在是69页\一共有127页\编辑于星期三线性规划LinearProgramming（LP）单纯形法由单纯形表进行迭代步骤：选择Xj入基：当j行中

j=max{

i∣

i0}选择Xi出基：当i

=min{bi/aij∣aij0}换基迭代：当确定了入基变量Xj、出基变量Xi后，以aij作为主元对单纯形表进行取主运算，取主运算——即采用初等行变换将主元aij所在列，除将aii变换为1而外，该列中的其余元素都变换为0。注意这种变换只能采用初等行变换!70现在是70页\一共有127页\编辑于星期三线性规划LinearProgramming（LP）单纯形法最优解检验：当迭代进行至某一步时，j行中所有检验数均小于等于零，则迭代结束。表中当前所指基本可行解即为最优解。当迭代进行至某一步时，j行中所有检验数均小于等于零，且此时至少有一个非基变量所对应的检验数k等于零，则原线性规划问题有无穷多个最优解。当迭代进行至某一步时，j行中至少有一个检验数k大于零，且该检验数对应的列中a1k，a2k，…amk，均小于等于零，则原线性规划问题最优解无界（maxZ→+∞）。71现在是71页\一共有127页\编辑于星期三线性规划LinearProgramming（LP）单纯形方法的矩阵描述：设线性规划问题maxZ=CXmaxZ=CX+0XS

s.t.AX≤bs.t.AX+IXS=b（I式）

X≥0X，XS≥0其中b≥0，I是mm单位矩阵。对上面（I式）经过迭代，并设最终的最优基矩阵为B（不妨设B

为A的首m列，则将（I式）改写后有72现在是72页\一共有127页\编辑于星期三线性规划LinearProgramming（LP）单纯形方法的矩阵描述：maxZ=CBXB+CNXN+0XS

s.t.BXB+NXN+IXS=bXB，XN，XS≥0

maxZ=CBB-1+（CN-CBB-1）XN-

CBB-1XS

s.t.XB+B-1NXN+B-1XS=B-1bXB，XN，XS≥0

B式中最优目标函数值Z*=CBB

-1，检验数CN-CBB

-1≤0

，-

CBB

-1≤0单纯形方法迭代（I式）（B式）73现在是73页\一共有127页\编辑于星期三线性规划LinearProgramming（LP）单纯形方法的矩阵描述：基解XB

XN

XSXSb

BNIj

CB

CN

0基解XB

XN

XSXBB-1b

IB-1NB-1j

0

CN-CBB

–1N-

CBB

-1对应I式的单纯形表——

I

表对应B

式的单纯形表——B

表迭代74现在是74页\一共有127页\编辑于星期三线性规划LinearProgramming（LP）单纯形表计算步骤举例给定线性规划问题maxz=50X1+30X2s.t.4X1+3X2≤

1202X1+X2

≤50X1，X2

≥0maxz=50X1+30X2s.t.4X1+3X2+X3=

1202X1+X2+X4=50X1，X2，X3，X4

≥075现在是75页\一共有127页\编辑于星期三线性规划LinearProgramming（LP）单纯形表计算步骤举例maxz=50X1+30X2s.t.4X1+3X2+X3=

1202X1+X2+X4=50X1，X2，X3，X4≥0Cj503000基XB解B-1bX1X2X3X4X31204310X4502101检验数j

503000初始单纯形表：基矩阵B非基矩阵NCBCNB-1b基变量非基变量76现在是76页\一共有127页\编辑于星期三线性规划LinearProgramming（LP）单纯形表计算步骤举例maxz=50X1+30X2s.t.4X1+3X2+X3=

1202X1+X2+X4=50X1，X2，X3，X4≥0基XB解B-1bX1X2X3X4X31204310X4502101检验数j

5030002120/450/2X111/201/2250201-2050-2520/125×211X2150-1/23/210-5-1577现在是77页\一共有127页\编辑于星期三线性规划LinearProgramming（LP）单纯形法的进一步讨论人工变量法：当一般线性规划问题标准化之后，我们或可得到一个显然的基本可行解（如松弛变量作为基变量的一个初始基本可行解），这样我们就可以马上进入单纯形表的运算步骤。然而，并非所有问题标准化之后我们都可得到一个显然的初始基本可行解，这时就需要我们首先确定出一个基本可行解作为初始基本可行解。通常采用的是人工变量法来确定这样的初始基本可行解。这种情况下一般有两种方法：

大M法（罚因子法）两阶段法78现在是78页\一共有127页\编辑于星期三线性规划LinearProgramming（LP）单纯形法的进一步讨论1、大M法（罚因子法）maxz=-3X1+X3

x1+x2+x3

≤4-2x1+x2–x3

≥13x2+x3=9x1，x2，x3

≥0LPMmaxz=-3x1+x3+0x4+0x5–Mx6–Mx7

x1+x2+x3+x4=4-2x1+x2–x3-x5+x6=13x2+x3+x7=9x1，x2，x3，x4，x5，x6，x7

≥079现在是79页\一共有127页\编辑于星期三线性规划LinearProgramming（LP）1、大M法LPMmaxz=-3x1+x3+0x4+0x5–Mx6–Mx7

x1+x2+x3+x4=4-2x1+x2–x3-x5+x6=13x2+x3+x7=9x1，x2，x3，x4，x5，x6，x7≥0基XB解B-1bX1X2X3X4X5X6X7X441111000X61-21-10-110X790310001检验数j-30100-M-M80现在是80页\一共有127页\编辑于星期三线性规划LinearProgramming（LP）1、大M法基XB解B-1bX1X2X3X4X5X6X7X441111000X61-21-10-110X790310001检验数j-3-2MM1-M0-M0-M基XB解B-1bX1X2X3X4X5X6X7X441111000X61-21-10-110X790310001检验数j-3-2M4M10-M0081现在是81页\一共有127页\编辑于星期三线性规划LinearProgramming（LP）1、大M法基XB解B-1bX1X2X3X4X5X6X7X4411110004X61-21-10-1101X7903100013检验数j-3-2M4M10-M00基XB解B-1bX1X2X3X4X5X6X7X4330211-10X21-21-10-110X7660403-31检验数j-3+6M01+4M03M-4M082现在是82页\一共有127页\编辑于星期三线性规划LinearProgramming（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现在是83页\一共有127页\编辑于星期三线性规划LinearProgramming（LP）1、大M法基XB解B-1bX1X2X3X4X5X6X7X400001-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现在是84页\一共有127页\编辑于星期三线性规划LinearProgramming（LP）采用大M法求解线性规划问题时可能出现的几种情况：当采用单纯形法求解LPM得到最优解时，基变量不含任何人工变量，则所得到的最优解就是原问题的最优解；当采用单纯形法求解LPM得到最优解时，基变量至少含有一个人工变量且非零，则原问题无可行解；当采用单纯形法求解LPM得到最优解时，基变量至少含有一个人工变量且人工变量都为零，则通过变换得到原问题最优解；85现在是85页\一共有127页\编辑于星期三线性规划LinearProgramming（LP）2、两阶段法maxz=-3X1+X3

x1+x2+x3≤4-2x1+x2–x3≥13x2+x3=9x1，x2，x3≥0I阶段问题maxz=–x6–x7

x1+x2+x3+x4=4-2x1+x2–x3-x5+x6=13x2+x3+x7=9x1，x2，x3，x4，x5，x6，x7

≥086现在是86页\一共有127页\编辑于星期三线性规划LinearProgramming（LP）2、两阶段法I阶段问题maxz=–x6–x7

x1+x2+x3+x4=4-2x1+x2–x3-x5+x6=13x2+x3+x7=9x1，x2，x3，x4，x5，x6，x7≥0基XB解B-1bX1X2X3X4X5X6X7X441111000X61-21-10-110X790310001检验数j00000-1-187现在是87页\一共有127页\编辑于星期三线性规划LinearProgramming（LP）2、两阶段法——第I阶段基XB解B-1bX1X2X3X4X5X6X7X441111000X61-21-10-110X790310001检验数j00000-1-1基XB解B-1bX1X2X3X4X5X6X7X441111000X61-21-10-110X790310001检验数j-2400-10088现在是88页\一共有127页\编辑于星期三线性规划LinearProgramming（LP）2、两阶段法——第I阶段基XB解B-1bX1X2X3X4X5X6X7X4411110004X61-21-10-1101X7903100013检验数j-2400-100基XB解B-1bX1X2X3X4X5X6X7X4330211-10X21-21-10-110X7660403-31检验数j60403-4089现在是89页\一共有127页\编辑于星期三线性规划LinearProgramming（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现在是90页\一共有127页\编辑于星期三线性规划LinearProgramming（LP）2、两阶段法——第II阶段基XB解B-1bX1X2X3X4X5X6X7X400001-1/21/2-1/2X23011/30001/3X11102/30