第一章线性规划(,)

1、 第一章 线性规划1 1 线性规划问题及模型线性规划问题及模型2 2 线性规划的解线性规划的解3 3 线性规划的单纯形法线性规划的单纯形法4 4 单纯形表单纯形表5 5 单纯形法的进一步讨论单纯形法的进一步讨论 6 6 线性规划建模举例线性规划建模举例蔡笑晚蔡笑晚- - 做父亲是我的事业做父亲是我的事业 蔡天文，美国康奈尔大学博士毕业，现为宾夕法尼亚大学蔡天文，美国康奈尔大学博士毕业，现为宾夕法尼亚大学最年轻的终身教授；最年轻的终身教授； 蔡天武，蔡天武，14岁考入中国科技大学少年班，岁考入中国科技大学少年班，25岁获得美国岁获得美国罗切斯特大学博士学位（诺贝尔奖获得者李政道的博士罗切斯特大学

2、博士学位（诺贝尔奖获得者李政道的博士生），现为美国最大的金融公司高盛公司的副总裁；生），现为美国最大的金融公司高盛公司的副总裁； 蔡天师，北京外国语学院毕业，曾被美国圣约翰大学录取蔡天师，北京外国语学院毕业，曾被美国圣约翰大学录取为博士生，现在经营实业；为博士生，现在经营实业； 蔡天润，华西医科大学毕业，曾被美国阿肯色州立大学录蔡天润，华西医科大学毕业，曾被美国阿肯色州立大学录取为博士生，现在创办私立医院；取为博士生，现在创办私立医院； 蔡天君，中国科技大学硕士，中国建设银行大客户部经理蔡天君，中国科技大学硕士，中国建设银行大客户部经理 蔡天西，蔡天西， 14岁入中科大少年班，岁入中科大少年班

3、， 18岁成为麻省理工学院岁成为麻省理工学院博士生，博士生， 22岁获得哈佛大学博士学位，岁获得哈佛大学博士学位， 28岁成为哈佛大岁成为哈佛大学最年轻教授，指导的博士生比她本人大学最年轻教授，指导的博士生比她本人大12岁。岁。 问 题 利润=价格-成本 如何应用线性规划的方法提高企业的利润？线性规划经典应用线性规划经典应用 为潘德罗索工业公司选择产品组合为潘德罗索工业公司选择产品组合 联合航空公司工作人员排程联合航空公司工作人员排程 Citgo石油集团供应、配送与营销的规划石油集团供应、配送与营销的规划 潘德罗索工业公司潘德罗索工业公司u潘德罗索工业公司（Ponderosa Industri

4、al）是一家墨西哥公司，截止到1998年的销售，公司生产了全国胶合板产量的1/4。与其他胶合板生产厂商一样，潘得罗索工业公司的许多产品根据厚度和所用木材的质量而有所不同。因为产品在一个竞争的环境中进行销售，产品的价格由市场决定，所以产品的价格每月都有很大的变化。结果导致每项产品对公司整体利润的贡献也有很大的变动。这样，在某个月中一个产品比另一个产品能赚取更多的利润，而在下个月的情况可能正好相反。所以每个月管理层面临的一个关键问题是选择产品组合（Product MIX） 每项产品各生产多少 以获取尽可能多的利润。u这一选择是很复杂的，因为它需要考虑当前生产产品必须的各种资源的可得数量。六项最重要

5、的资源为 1）四种类型的原木（根据原木的质量区分）和 2）生产胶合板的两项关键作业的生产能力（模压作业和刨光作业)。u从1980年开始，潘得罗索工业公司管理部门每个月使用线性规划指导下个月的产品组合决策。线性规划的数学模型考虑了这一决策的所有相关限制条件，包括生产产品所需的有限的资源可得数量。然后对模型求解，找出可行并且最大可能利润（possible profit）的产品组合。u一旦数据输人模型，包括下个月产品的估计价格，可能获得的最大利润会被准确地计算出来。u但是，管理层知道哪怕仅仅只提前一个月的产品价格预测也是危险的，所以检验在其他似乎可信的价格预测下产品组合决策是如何发生改变就很重要。幸

6、运的是，线性规划计算机系统是交互式的，管理者能够对市场决定的不同情景很快地再对模型进行求解。这种对感兴趣的各种情景进行考察的能力证明，在准确做出产品组合的决策上是无可限价的。u在潘得罗索工业公司，线性规划的影响被报道是“惊人的”。它导致公司强调生产的原木产品类型有巨大的转换，改进的产品组合决策使公司的总利润增加了 20，线性规划的其他一些贡献包括更好的原材料利用、更好的资本投资和更好的人员使用。 潘德罗索应用成功的因素：潘德罗索应用成功的因素： 以自然语言自然语言为用户界面的财务计划系统，使用自然语言而不是数学符号来显示线性规划模型各个组成部分以及输出的结果，使得做决策的管理者能够很容易看懂整

7、个过程。 最优化系统是互动的互动的（interactive），管理者在从一个版本的模型中获得一组最优解之后，可以提出一系列的what-if问题，并能立即得到回应。 联合航空公司人员排程联合航空公司人员排程u尽管1983年和1984年经历了史无前例的行业竞争，联合航空公司（United Airlines）还是开通了 48个新机场的服务，取得了很大的增长。1984年，它是唯一的一家在美国全部50个州开通服务的公司，1984年的收人比1983年增加了6个百分点达到了62亿美元，而同时成本的增长少于 2，因此营运利润提高达到了 564亿美元。在航空行业生存，成本控制是关键。作为公司扩展的一部分，198

8、2年联合航空公司的高层管理部门实施了一个成本控制项目，目标是通过更紧密地根据消费者的需求进行工作排程，以改进航班订票处和机场工作人员的利用率。 u那时，联航在其11个航班订票处有超过4000名的机票销售代表和支持人员，在10个最大的机场大约有1000名客户服务代表，有些是兼职的，每班28个小时不等，大部分是全职的，每班8小时或10小时，有许多个不同的上班时间。每个订票处都一天24小时营业（通过电话订票）。各个重要的机场也如此。然而，每个地点提供所需水平服务的雇员数量在一天24小时中的变化很大，或许每过半个小时就会有很大的变化。u为了更有效率地满足服务需求，在每个地点为所有雇员设计工作排程是一个

9、组合的梦魇。一旦一名雇员上了班，他（或她）就会工作一个班次（根据雇员2-10个小时不等），只有就餐和每隔两小时的短暂的休息时间。给定24小时的一天中每半个小时间隔的服务所需的最小雇员数（每周七天里这个最小值天天有变化），在一周七天、一天24小时中每个班次需要多少雇员并且何时上班呢？幸运的是，线性规划能解决这些组合梦魇问题。u本课程将要讲的预测和排队模型都可以用来确定每半小时间隔任务的最少雇员数。整数规划可确定班次何时开始。但是，规划系统的核心是线性规划，它能进行所有实际的排程以在最小的劳动力成本下提供所需的服务，每个月会产生一个新的工作排程以反映实际情况的变化。u线性规划的这个应用据报道“不仅

10、对联航的管理层和项目小组成员，而且对许多未曾听说过管理科学或数学模型的人有压倒一切的影响”。它获得了高级管理层、运营经理、相关雇员等等人员的强烈好评。例如，一位经理描述排程系统为“魔术般的，就好像消费者的排队正要变长的时候，新的工作人员就进来提供服务；就好像你认为工作强度在增大时，消费者就开始回家了”。u据有形估计，建立在线性规划基础上的计算机规划系统每年为联合航空公司在直接薪酬和津贴成本上节省了600万美元，得到的其他好处包括改善客户服务以及降低雇员的工作负担。1990年代早期经过一些升级以后，系统今天还在提供与过去同样的好处。 联合航空公司联合航空公司 利用线性规划，来为其在主要的机场和定

11、票点的上万个工作人员安排每周的工作时间表。目标是为了能够在满足客户的服务需要的同时，将一周内每天每半个小时的人员成本最小化。联合航空公司一些地点的规划模型却包括20,000个决策变量。 应用成功最主要的因素是因为得到了运营经理以及其它员工的大力支持。 第一节第一节 线性规划问题及其数学模型线性规划问题及其数学模型一一 、线性规划问题、线性规划问题原形范例Wyndor Glass 公司生产高质量的玻璃门窗，拥有公司生产高质量的玻璃门窗，拥有3个工厂。铝框架个工厂。铝框架和硬件在工厂和硬件在工厂1生产，木质框架在工厂生产，木质框架在工厂2生产，玻璃生产和产品组装在生产，玻璃生产和产品组装在工厂工厂

12、3完成。完成。由于收入下降，高层管理者决定修整公司的生产线。不盈利的产品将由于收入下降，高层管理者决定修整公司的生产线。不盈利的产品将停止生产，将生产能力转移到有较大销售潜力的两个新产品：停止生产，将生产能力转移到有较大销售潜力的两个新产品： 1、具有铝框架的、具有铝框架的8英尺玻璃门；英尺玻璃门； 2、具有双悬木质框架的、具有双悬木质框架的4x6英尺窗英尺窗 产品产品1需要工厂需要工厂1和和3的生产能力，而不需要工厂的生产能力，而不需要工厂2的生产能力。产的生产能力。产品品2需要工厂需要工厂2和和3的生产能力，而不需要工厂的生产能力，而不需要工厂1的生产能力。进行市的生产能力。进行市场研究得

13、到结论：公司能够销售掉工厂所能生产的全部产品。然而，场研究得到结论：公司能够销售掉工厂所能生产的全部产品。然而，由于两种产品都为使用工厂由于两种产品都为使用工厂3的生产能力而竞争，不清楚如何确定两的生产能力而竞争，不清楚如何确定两种产品的组合可以实现利润最大化，因此，组织了一个运筹小组来研种产品的组合可以实现利润最大化，因此，组织了一个运筹小组来研究这个问题。究这个问题。 运筹小组开始与高层管理者进行讨论，以明确管理目标，并定义运筹小组开始与高层管理者进行讨论，以明确管理目标，并定义出了下面的问题出了下面的问题 ： 决定两种产品生产率的目标是总利润最大化。限制条件是三个工决定两种产品生产率的目

14、标是总利润最大化。限制条件是三个工厂有限的生产能力（每种产品将以厂有限的生产能力（每种产品将以2020个为一批进行生产）满足这些限个为一批进行生产）满足这些限定条件的任何生产组合都是可行的。定条件的任何生产组合都是可行的。 运筹小组还确定出需要收集的下列数据：运筹小组还确定出需要收集的下列数据： 1.每周在每个工厂能为生产这些新产品所提供的生产每周在每个工厂能为生产这些新产品所提供的生产时间（小时）数；时间（小时）数； 2.每一个工厂生产一个批次新产品所消耗的时间每一个工厂生产一个批次新产品所消耗的时间（小时）数；（小时）数；3.每生产一批新产品的盈利。每生产一批新产品的盈利。工工 厂厂每批的

15、生产时间每批的生产时间（小时）（小时）每周可用的生产时间每周可用的生产时间（小时）（小时）产品产品1 21231 00 23 241218每批利润（元）每批利润（元）3000 50000, 01823122453max21212121xxxxxxxxz范例模型：结 论 运筹学小组使用这个方法找到了最优解： Wyndor Glass 公司每周生产产品公司每周生产产品1和产品和产品2的数量分别是的数量分别是2批和批和6批，带来的总利润是批，带来的总利润是36000元。根据这个模型两种产品生产的其元。根据这个模型两种产品生产的其它组合都没有这种组合的盈利多。它组合都没有这种组合的盈利多。例例1 生产

16、决策问题生产决策问题 某厂生产甲乙两种产品，巳知制成一吨产品甲需某厂生产甲乙两种产品，巳知制成一吨产品甲需用资源用资源A 3吨，资源吨，资源B 4m2；制成一吨产品乙需用资源；制成一吨产品乙需用资源A 2吨，资源吨，资源B 6m2，资源，资源C 7个单位若一吨产品甲个单位若一吨产品甲和乙的经济价值分别为和乙的经济价值分别为7万元和万元和5万元，三种资源的限万元，三种资源的限制量分别为制量分别为90吨、吨、200rn2和和210个单位，试决定应生个单位，试决定应生产这两种产品各多少吨才能使创造的总经济价值最产这两种产品各多少吨才能使创造的总经济价值最高高?例2 投资问题 某单位有一批资金用于四个

17、工程项目的投资，某单位有一批资金用于四个工程项目的投资，用于各工程项目时所得之净收益用于各工程项目时所得之净收益(投入资金的百分投入资金的百分比比)如下表所示；如下表所示；工程项目ABCD收益()1510812 由于某种原因，决定用于项目由于某种原因，决定用于项目A的投资不大于的投资不大于其它各项投资之和；而用于项目其它各项投资之和；而用于项目B的和的和C 的投的投资不小于项目资不小于项目D的投资。试确定使该单位收益的投资。试确定使该单位收益最大的投资分配方案。最大的投资分配方案。 例例3 营养问题营养问题 某动物饲养场利用某动物饲养场利用n种天然饲料来配制混合饲料种天然饲料来配制混合饲料使用

18、，已知单位第使用，已知单位第j种天然饲料的价格为种天然饲料的价格为cj，它含有，它含有第第i种营养成份的量为种营养成份的量为aij；根据动物生长的需要，要求根据动物生长的需要，要求具有具有rn种营养成份，且第种营养成份，且第i种营养成份的含量不得低于种营养成份的含量不得低于bi。试确定在保证动物营养需要的条件下费用最低的。试确定在保证动物营养需要的条件下费用最低的饲料配合法。饲料配合法。 0, 0102720064092357max1212212121xxxxxxxxxz：例0, 01823122453max21212121xxxxxxxxz范例：0, 0, 0, 010012. 008. 0

19、1 . 015. 0max24321432143243214221xxxxxxxxxxxxxxxxxxxz：例njxbxaxczjijnjijnjjj,.,2 , 1, 0max311：例上面例子从数学上具有以下几点共同特征上面例子从数学上具有以下几点共同特征 1.用未知自变量表示某种重要的可变因素，变量的一组数据代表一种解决方案，通常求这些变量取非负值。 2存在一定的限制条件，它们可以自变量的线性方程(等式)或线性不等式来表示。这些条件称为约束条件。 3都有一个要达到的目标，它也是自变量的线性函数，称为目标函数。根据需要，要目标函数极大化或极小化。 二、线性规划的数学模型二、线性规划的数学模

20、型0,),(),(),(.)(max(min)21221122222121112121112211nmnmnmmnnnnnnxxxbxaxaxabxaxaxabxaxaxatsxcxcxcxf线性规划数学模型的一般表示方式: 1、和式njxmibxatsxcxfjinjjijnjjj, 2 , 1 , 0, 2 , 1 ,. .)(max11 2、向量式0000 P ),( );,( . .)(max210212121010bXC0XbCXmmjjjjTnnnjjjbbbaaaxxxcccxPtsxf 3、矩阵式 ),(),();,(.)(max212121212222111211TmTnnm

21、nmmnnbbbbxxxXcccCaaaaaaaaaA0XbAXtsCXxf三三 、线性规划的标准型、线性规划的标准型njxmibxatsxcxfjinjjijnjjj,2, 1 ),0(0,2, 1 ,),(.)(max(min)11不不限限njmixmibxatsxcxfjimnjjijmnjjj,2, 1 ,2, 1 ,0,2, 1 ,.)(max11 变换的方法变换的方法 1 . 第i 个约束为 型，在不等式左边增加一个非负的变量xn+i ，称为松弛变量；第i 个约束为 型，在不等式左边减去一个非负的变量xn+i ，称为剩余变量； 2. 目标函数为min型，可将该目标函数乘以“-1”变

22、为极大化问题求解。 3. 若xj 不限，令 xj= xj - xj， xj 0，xj 0.XX*Z=f（X）Z=-f（X）（极小化）（极小化）（极大化）（极大化）OZ 变换举例：0, ,20040065300432.423)(min:213321321321321xxxxxxxxxxxxtsxxxxf不限不限原非标准型原非标准型 0,2004006653004432.0004423)(max:65433216332153321433216543321xxxxxxxxxxxxxxxxxxxxxxtsxxxxxxxxf标准型标准型第二节第二节 线性规划问题的解线性规划问题的解max z=x1+3x

23、2s.t. x1+ x26-x1+2x28x1 0, x20可行域目标函数等值线最优解(4/3,14/3)64-860 x1x2一、一、 图解法图解法例1max z=46/32 用图解法求解线性规划问题：用图解法求解线性规划问题：0, 0212236243max212212121xxxxxxxxxz1 2 3 4 2 134ABCD0X1X2122321 xx22x6221 xx最优解：最优解： B（3，3/2），），Z= 153 用图解法求解线性规划问题：用图解法求解线性规划问题：0, 021223622max212212121xxxxxxxxxz1 2 3 4 2 1343x1+2x2=1

24、2X2=2X1+2x2=6ABCD0最优解： C（2，2）B（3，3/2）- Z= 6（无穷多个）X1X24 用图解法求解线性规划问题：用图解法求解线性规划问题：0, 0122min21212121xxxxxxxxzB0 CAD最优解： B（0，1）- Z=1X1X2121 xx2221 xx5 用图解法求解线性规划问题：用图解法求解线性规划问题：0, 0122max21212121xxxxxxxxzB0 CAD无无 上界上界X1X2121 xx2221 xx6 用图解法求解线性规划问题：用图解法求解线性规划问题：0, 0632123min21212121xxxxxxxxz1 2 3 4 2

25、1342x1+3x2=6X1+x2=10无可行解和无可行解和 最优解最优解X1X2线性规划问题解的几种情况：线性规划问题解的几种情况：1。有唯一最优解；。有唯一最优解；2。有多重最优解；。有多重最优解；3。 目标函数无界；目标函数无界；4。无解。无解。二二 、 线性规划解的概念线性规划解的概念2 . 13 . 10,.1 . 1)(max21221122222121112121112211 nmnmnmmnnnnnnxxxbxaxaxabxaxaxabxaxaxatsxcxcxcxf线性规划数学模型的标准型:aaaaaaaaamnmmnnA.212222111211m)B( rBmmA,m)A

26、( r，使得矩阵子中至少有一个显然1 基基。过但数目不超基矩阵就可能有多个，时，时，基矩阵唯一，当当或基矩阵）。是线性规划的一个基（则称满足子矩阵中mnCnmnmB,m)B( rBmmA求所有基矩阵。已知线性规划例 5,.,2 , 1j , 0 x2x2x6x10 x-3x x- x5x x-2x-4xzmax .j53214321321解：个，阶子矩阵有10C2 , 2)A( r1026100111525A基矩阵只有9个.0B. 0BB,1001B,1201-B,0211-B,1601B,0611B,261-1B,11005B,01015B,61015B987654321就不是基当即必为非奇

27、异矩阵基矩阵由线性代数知2 基向量、基变量、非基变量基向量、基变量、非基变量 当确定某一子矩阵为基矩阵时，则基矩当确定某一子矩阵为基矩阵时，则基矩阵对应的列向量称为阵对应的列向量称为基向量，基向量，其余列其余列向量称为向量称为非基向量非基向量 ，基向量对应的，基向量对应的变量称为基变量。变量称为基变量。),.,(.m21212222111211PPPBaaaaaaaaammmmmm称称Pj (j=1,2,m)为为基向量基向量，与基向量，与基向量Aj相应的相应的变量变量Xj (j=1,2,m)为为基变量基变量。其它变量称为。其它变量称为非基变非基变量量。 3 可行解、最优解可行解、最优解 例如，

28、最优解例的可行解。都是与TTT8, 0, 0, 0,53X2, 3, 0, 0, 0X1,27,21, 0, 0X4. 基解、基可行解、可行基基解、基可行解、可行基 基解：对某一确定的基基解：对某一确定的基B，令非基变量，令非基变量 等于等于0，利用式，利用式1.2解出基变量解出基变量 则这组解称为基则这组解称为基B的基解。的基解。 基可行解：满足非负要求的基解。基可行解：满足非负要求的基解。 可行基：可行基： 对应于基可行解的基。如上例中对应于基可行解的基。如上例中 B3在上例中，对B1，基解为：解。但不是任何基矩阵的基可行不可行是基可行解，基解为对TTTXXXXBX1,27,21, 0,

29、000, 4, 0, 0,51,0, 0, 0, 1,52)2()1()2(2)1( 可行解、基解和基可行解举例可行解、基解和基可行解举例.36)(max, 6, 2:0,78102. .46)(max21543215242132121xfxxxxxxxxxxxxxxxtsxxxf最优解 可行解、基解和基可行解举例可行解、基解和基可行解举例1187654322x1876543O109x2A BCEDFGH123f(x)=36K非非基基变变量量 基基变变量量 图图中中的的点点 解解 x1, x2 x3 =10 x4 =8 x5 =7 O 基基可可行行解解 x1, x3 x2 =10 x4 =-

30、-2 x5 =- -3 F 基基解解 x1, x4 x2 =8 x3 =2 x5 =- -1 E 基基解解 x1, x5 x2 =7 x3 =3 x4 =1 1 A 基基可可行行解解 x2, x3 x1 =5 x4 =3 x5 =7 7 D 基基可可行行解解 x2, x4 x1 =8 x3 =- -6 x5 =7 7 H 基基解解 x3, x4 x1 =2 x2 =6 x5 =1 1 C 基基可可行行解解 最最优优解解 x3, x5 x1 =1.5 x2 =7 x4 =- -0.5 G 基基解解 x4, x5 x1 =1 x2 =7 x3 =1 1 B 基基可可行行解解 x1 =2, x2 =

31、2, x3 =4, x4 =4, x5 =3 3 K 可可行行解解 二 凸集及其顶点 P 20 ),.,(21xxX 定理定理2：线性规划问题的基可行解：线性规划问题的基可行解X对应线性规划问题可行域的顶点。对应线性规划问题可行域的顶点。 定理定理3：若线性规划问题有最优解，：若线性规划问题有最优解，一定存在一个基可行解是最优解。一定存在一个基可行解是最优解。 上述定理给了我们一个启示：求最优解上述定理给了我们一个启示：求最优解不是在无限个可行解中去寻找，而是在有不是在无限个可行解中去寻找，而是在有限个基本可行解中去求得。限个基本可行解中去求得。 但用这种方法求最优解的前提是该线性规但用这种方

32、法求最优解的前提是该线性规划存在最优解。划存在最优解。 4,.,2 , 1j , 0 x37x6x2xx-84x x- 3x2x 7x4x3x2xzmax .j432143214321已知线性规划如T)6(T)5(T)4(T)3(T)2(T)1()31/45,31/68, 0 , 0(X)29/7, 0 ,68/29, 0(X)0 ,7/16,45/16, 0(X)5/7 , 0 , 0 , 5/34(X)0 ,13/14, 0 ,13/45(X )0 , 0 , 2 , 1 (X六个基解：基矩阵有六个，对应有界解。最大，但此线性规划无使4 .23z)5/7 , 0 , 0 , 5/34(XT

33、)3(练习；1 用图解法求下列LP问题：（1）Max z = 2x1+2x2 x1-x2 -1 -0.5x1+x2 2 x1 0,x2 02 把下列LP问题化成标准型（1）min z =2x1+3x2+5x3 X1-X2 X3 - 5 -6X1+7X2 9X3=15 19X1+7X2+5X3 13 X10，X2 0 第三节第三节 线性规划的单纯形法线性规划的单纯形法 单纯形法的基本思路是单纯形法的基本思路是: 根据问题的标准根据问题的标准,从可行域中某个基可从可行域中某个基可行解行解(一个顶点一个顶点)开始开始,转换到另一个基可行转换到另一个基可行解解(一个顶点一个顶点)并且使目标函数达到最大

34、值并且使目标函数达到最大值时时,问题就得到了最优解。问题就得到了最优解。一一 、分析一个例子。、分析一个例子。 解解 该问题的线性规划模型为该问题的线性规划模型为:其标准型为其标准型为:0, 0210720064902357max212212121xxxxxxxxxz5 , 4 , 3 , 2 , 1, 0210720064902357max5242132121jxxxxxxxxxxxzj其约束条件的系数矩阵为：其约束条件的系数矩阵为： A= (A1 , A2 , A3 , A4 , A5)=3 2 1 0 04 6 0 1 00 7 0 0 1线性规划问题的一个基（初始基）：线性规划问题的一

35、个基（初始基）： B（0）=（ A3 ，A4，A5)=1 0 00 1 00 0 1X3 ，X4，X5为基变量，得：为基变量，得： X3 =90-3X1-2X2 X4 =200-4X1-6X2 X5 =210-0X1-7X2 （1.13） 将（将（1.13）代入目标函数）代入目标函数 得得: Z=7X1+5X2+0令非基变量令非基变量X1=X2=0,便得到便得到Z=0，这时得到一个基可行解，这时得到一个基可行解X（0）X（0）=（0，0，90，200，210）T 从从 (1.15)中中 可以看出可以看出 ，只有选择。，只有选择。才能使才能使(1.15)成立成立,用用X1去替换去替换X3， 00

36、210)15. 1 (042000390151413xxxxxx时30), 4/200, 3/90min(1x253243217210)17. 1 (3431080313230 xxxxxxxx再将再将(1.17）代入目标函数得：）代入目标函数得： 323731210 xxzTXzxx)210,80, 0 , 0 ,30(210, 0)1(32：并得到另一个基可行解得令目标函数还可以增大目标函数还可以增大,继续迭代得继续迭代得:43)2(1 . 02 . 2218)42, 0 , 0 ,24,14(xxzXT此时，目标函数取此时，目标函数取得最大利润。得最大利润。01020304050AX3=

37、0X4=0Bx2x1X5=01020304050该例的图解该例的图解例例 用单纯形法求下列线性规划的最优解用单纯形法求下列线性规划的最优解 0 x , 0 x0 x , 0 x303x x40 x x2x4x3xmax Z0 x , 0 x303x x40 x2x4x3xmax Z21213212121212121，解：标准型为初始基可行解：初始基可行解：目标函数TX)30,40, 0 , 0()0(检验数：目标函数用非基变量表示，其检验数：目标函数用非基变量表示，其 变量的系数为检验数。变量的系数为检验数。j最优解判断标准最优解判断标准 当所有检验数当所有检验数 基可行解为最优解基可行解为最

38、优解0j 通过观测得到一个基可行解并判断通过观测得到一个基可行解并判断其是否为最优解：其是否为最优解： （1）、约束条件系数矩阵存在）、约束条件系数矩阵存在m个个不相关的单位向量；不相关的单位向量； （2）、目标函数中不含有基变量。）、目标函数中不含有基变量。 单纯形法的开始和后面就是：寻找基单纯形法的开始和后面就是：寻找基可行解和求检验数。可行解和求检验数。X2 为引入变量，由约束条件0 x , 0 x0 x , 0 x303x x40 x x2x2121321，X2,x3基变量，解出： 0131xx31 30 x31x x3521431基可行解为：X（1）=（0，10，30，0）T检验未达

39、最优：41x34x3540z继续迭代 X1引入变量，X3为退出变量，通过初等变换得到：)0 , 0 , 4 ,18(X:452x51 x81x51x53 x(2)32431基可行解为检验达最优：43xx70z 上述全过程计算方法就是单纯形法，实际将用列表的方法进行计算。确定初始基础可行解确定初始基础可行解求最优解的目标函数值求最优解的目标函数值确定改善方向确定改善方向求新的基础可行解求新的基础可行解检查是否为检查是否为最优解？最优解？是是否否二、初始基可行解二、初始基可行解1、 “”形约束形约束a11x1+a12x2+a1nxn b1a21x1+a22x2+a2nxn b2am1x1+am2x

40、2+amnxn bma11x1+a12x2+a1nxn +xn+1= b1a21x1+a22x2+a2nxn +xn+2= b2am1x1+am2x2+amnxn +xn+m= bm得一基可行解如下（已设得一基可行解如下（已设bibi 0 0）：）： X=X=（x x1 1 , , ,x , , ,xn+1n+1,x,xn+mn+m) )T T=(0,0,0,b=(0,0,0,b1 1,b,bm m) )T T 显然，基变量对应的系数列向量全为单位列显然，基变量对应的系数列向量全为单位列向量。向量。2、等式约束、等式约束 考虑等式约束线性规划：考虑等式约束线性规划：MaxZ=c1x1+c2x2

41、+cnxna11x1+a12x2+a1nxn = b1a21x1+a22x2+a2nxn = b2 (1-24)am1x1+am2x2+amnxn = bmxj 0 j=1,2,na11x1+a12x2+a1nxn +xn+1= b1a21x1+a22x2+a2nxn +xn+2= b2 (1-25)am1x1+am2x2+amnxn +xn+m= bmxj 0 j=1,2,n+mMaxZ= c1x1+c2x2+cnxn-mxn+1-mxn+2-mxn+m3、“”型约束型约束 设有如下线性规划问题：设有如下线性规划问题：MaxZ= c1x1+c2x2+cnxna11x1+a12x2+a1nxn

42、 b1a21x1+a22x2+a2nxn b2 （1-26）am1x1+am2x2+amnxn bmxj 0 j=1,2,nMaxZ= c1x1+c2x2+cnxn-mxn+m+1-mxn+m+2-mxn+2ma11x1+a12x2+a1nxn -xn+1+xn+m+1= b1a21x1+a22x2+a2nxn -xn+2 +xn+m+2 = b2am1x1+am2x2+amnxn -xn+m +xn+2m = bmxj 0 j=1,2,n+m令人工变量为基变量，立刻得一基可行解如下：令人工变量为基变量，立刻得一基可行解如下：X=（x1 , x2 ,xn ,xn+1 , , xn+m , n+

43、m+1 , , xn+2m）T =（0 , 0 , , 0 , 0 , , 0 , b1 , , bm）T例例.用上述方法为下面的线性规划问题构成初始用上述方法为下面的线性规划问题构成初始基可行解：基可行解：0, 0502340425 . 23min21212121xxxxxxxxz例例.写出下述线性规划问题的初始基可行解：写出下述线性规划问题的初始基可行解：3 , 2 , 1, 032294328323max3132131321jxxxxxxxxxxxzj例例.写出下述线性规划问题的初始基可行解：写出下述线性规划问题的初始基可行解：3 , 2 , 1, 011127334232min3213

44、21321jxxxxxxxxxxzj三、最优性检验三、最优性检验设前设前m个系数列向量为单位列向量，个系数列向量为单位列向量，它们构成基。它们构成基。 4).(1n,.,2 , 1j, 0.Zmaxjmm1m1m,mm221m1m,22111m1m, 112211xbxaxaxbxaxaxbxaxaxxcxcxcnnnnnnnn对应的基可行解对应的基可行解:0.00.0.100.01),.,(21mPPPBTmTmbbbxxxX)0,.,0 ,.,()0,.,0 ,.,(2121将基变量由（将基变量由（1.4）的约束条件解出，得：）的约束条件解出，得：)5 . 1 (m,.,2 , 1i,xa

45、bxn1mjjijii将（将（1.5）代入（）代入（1.4）中的目标函数表达式，）中的目标函数表达式，得得 m1iijijm1iii0n1mjm1ijijijim1iim1in1mjn1mjjjjijiim1iiacZbcZx)acc (bcxcxacbc令Zn1mjjjj0 x)zc (ZZ则有Z0是现行解是现行解XB=( x1 ,x2 , , xm ) T = ( b1 , b2 , , bm ) T 的目标函数值。的目标函数值。Ci（i=1,2,m）为基变量的价值系数。）为基变量的价值系数。（有时为避免混淆，（有时为避免混淆，特特以下标以下标B标明，记为标明，记为CBi）,xj为非基变量

46、，为非基变量， Cj 为非基变量的价值为非基变量的价值系数，系数，j=m+1 n Zj 的意义是：当引入非基变量的意义是：当引入非基变量xj时，时，单位单位xj使原来目标函数的减少值。使原来目标函数的减少值。.xx,xxZZn,.,1mj,zcjjjjn1mjjj0jjj函数值带来的净增长函数值带来的净增长给目标给目标为引入变量时单位为引入变量时单位以以其值等于其值等于的检验数的检验数为变量为变量则得则得再令再令 1.若所有非基变量的若所有非基变量的 （皆非正），（皆非正），则这个解为最优解：则这个解为最优解： （1） ，最优解唯一。，最优解唯一。 （2） ，有多重最优解。，有多重最优解。 2

47、 若存在某个或某些若存在某个或某些 的非基变量，的非基变量， 且其系数且其系数列向量含有正分量。列向量含有正分量。0j0j0j0j通常选通常选 最大的变量为引入变量。最大的变量为引入变量。 3 若存在若存在 为正的某非基变量为正的某非基变量xj,其其系数列向量的所有分量皆非正（即系数列向量的所有分量皆非正（即aij 0,i=1,2,3,-,m)则该线性规划目标函则该线性规划目标函数值无界。数值无界。 jj四四 、基可行解的转换、基可行解的转换 1、根据检验数确定引入变量、根据检验数确定引入变量2、根据、根据 规则确定退出变量规则确定退出变量 确定主元素确定主元素alklklikikiab0aa

48、bmin （2）、其余的利用下列公式计算）、其余的利用下列公式计算3、系数变换、系数变换 （1）将主元素所在的）将主元素所在的L行数字除以主元素行数字除以主元素 alk得变换后的第得变换后的第L个约束方程系数个约束方程系数 )7 . 1() li (a .aaaa) li (a .abbbiklkljijijiklklii 1 建模建模 2 给出初始基可行解。（引入松弛和人给出初始基可行解。（引入松弛和人工变量）工变量） 3 计算非基变量的计算非基变量的 。 若所有若所有 均非均非 正，这个解就是最优解。正，这个解就是最优解。 否则，转下一步。否则，转下一步。 4 在检验数为正的那些非基变量中

49、，选在检验数为正的那些非基变量中，选检验数最大的那检验数最大的那 j0j五五 用单纯形法求解线性规划问题的用单纯形法求解线性规划问题的步骤步骤个变量为引入变量，例如说这个变量是个变量为引入变量，例如说这个变量是xk ，它对应系数列向量为它对应系数列向量为Pk. 5 查看查看 Pk 的各个分量的各个分量aij ，i =1，2，-,m ，若所有若所有 aik0 ，则该线性规划问题无界。否则，则该线性规划问题无界。否则，转下一步。转下一步。 6 按最小比值规则确定按最小比值规则确定 即即: = min= min |aik0,i=1,2,m= (1.40) 7 以相应于以相应于的那个变量的那个变量xB

50、l （基变量中（基变量中的第的第l个变量）为退出变量，以个变量）为退出变量，以alk为主元素，为主元素，对约束方程组按式（对约束方程组按式（1.7）进行变换，从而）进行变换，从而得一新的基可行解。得一新的基可行解。 8 转回第转回第3步，继续进行检验和变换，直步，继续进行检验和变换，直至得出最优解或查明目标函数无界。至得出最优解或查明目标函数无界。第四节第四节 单纯形表单纯形表单纯形表格式如下：单纯形表格式如下：cjcBixBic1c2.cmc1 cmx1 xmx1x2.xm1 00 1. .0 1cm+1 cnxm+1 xna1 , m+1 a1na2 , m+1 a2n. .am , m+

51、1 amnbibi/aikb1b2.bmb1/a1kb2/a2k.bm/amk0 0zcjjj m m1 1i im m1 1i iininBiBin n1 1m mi iBiBi1 1m ma ac cc ca ac cc c., m m1 1i ii iBiBib bc c a ab b 00a a| | a ab b minmin 2 2a ac cc cz zc clklkl likikikiki im m1 1i iijiji ij jj jj jj j . 1 )(.)(. 3l li ia aa aa aa aa al li ia aa ab bb bb bikiklklkljl

52、jijijijijikiklklkl li ii i矩形交叉相乘示意图矩形交叉相乘示意图-aij-aik- i行行-alj-alk- l行行 (退出）退出）j列列k列（引入）列（引入）主元素主元素欲计算欲计算之元素之元素 ) li (a .aaaaiklkljijij用单纯形法求解线性规划：用单纯形法求解线性规划：Max z=12x1+16x2+12x3 2x1+4x2+x3 2 2x1+2x2+3x3 3 x1 , x2 , x3 = 0解：解：c cj j1212161612120 00 0b bi ib bi i/a/aikikc cBiBix xBiBix1x1x2x2x3x3x4x4

53、x5x50 0 x4x42 24 41 11 10 02 21/21/20 0 x5x52 22 23 30 01 13 33/23/21212161612120 00 00 01616x2x21/21/21 11/41/41/41/40 01/21/22 20 0 x5x51 10 05/25/2-1/2-1/21 12 24/54/54 40 08 8-4-40 0-8-81616x2x22/52/51 10 03/103/10-1/10-1/103/103/103/43/41212x3x32/52/50 01 1-1/5-1/52/52/54/54/52 24/54/50 00 0-12

54、/5-12/5-16/5-16/5-72/5-72/51212x1x11 15/25/20 03/43/4-1/4-1/43/43/41212x3x30 0-1-11 1-1/2-1/21/21/21/21/20 0-2-20 0-3-3-3-3-15-15jjjzc jjjzc jjjzc jjjzc 15Z2143xxTT31,),(*BXMax z= 7x1+5x2 3x1+2x290 4x1+6x2 200 7x2 210 x10,x20例例.用单纯形法求解线性规划用单纯形法求解线性规划Max z = 7x1+5x2+0 x3+0 x4+0 x5 3x1+2x2+x3 =90 4x1+

55、6x2 +x4 =200 7x2 +x5 =210 xj0, j=1,2,3,4,5其标准型为:cj750 00 00bibi/aikcBixBix1x2x3x4x50 0 x3 3*2 21 10 00 09090300 x44 46 60 01 10 020020050500 x50 07 70 00 01 1210210- -7500 00 007 7x112/31/31/30 00 030450 x4010/3*4/34/31 10 080240 x5070 00 01 1210-01/3-7/3-7/30 00 0-2107 7x1101/151/15-1/5-1/50145x201

56、2/52/53/103/100240 x500-14/5-14/5-21/10-21/1014200-7/15-7/15-1/10-1/100-218jjjzc jjjzc jjjzc 21824514,),(*7Z422414xxxTT52,1BX例例.用单纯形法求解线性规划用单纯形法求解线性规划 解解: 0 x,x,x1x2x-32xx4x-11x2xxxx3xZmin32131321321321cjyj=cj-zjyj=cj-zjyj=cj-zjyj=cj-zj3 -1 -1 0 0 -M -M x1 x2 x3 x4 x5 x6 x71 -2 1 1 0 0 03-6M -1+M -1

57、+3M 0 -M 0 0cBixBi0 x4-M x6 0 x4-M x6-1 x3bi4Mbiaik113/21-4 1 2 0 -1 1 0-M x7-2 0 0 0 0 111131 3 -2 0 1 0 0 -1 0 0 0 -1 1 -2-2 0 1 0 0 0 111011-1-1 -1+M 0 0 -M 0 1-3M0 x4-1 x2-1 x3 0 0 1 -2 2 -5 0 1 0 0 -1 1 -2-2 0 1 0 0 0 131+M12114-1 0 0 0 -1 1-M -1-M23 x1-1 x2-1 x3 1 0 0 1/3 -2/3 2/3 -5/3 0 1 0 0

58、 -1 1 -2 0 0 1 2/3 - 4/3 4/3 -7/34190 0 0 -1/3 -1/3 1/3 - M 2/3 - M-22,),(*Z914xxxTT32,1BX用单纯形法求解线性规划：用单纯形法求解线性规划：Max z = 2x1-x2+x3 3x1+x2+ x3 60 x1- x2+2x3 10 x1+x2 - x3 20 x1 , x2 , x3 0解：解：用单纯形法求解线性规划：用单纯形法求解线性规划：Max z = 3x1+2x2+3x3 2x1+ x2+ x3 2 3x1- 4x2+2x3 8 x1 , x2 , x3 0解：解：用单纯形法求解线性规划：用单纯形法

59、求解线性规划：Min z = 3x1+x2+x3+x4 - 2x1+ 2x2+ x3 = 4 3x1 + x2+ x4 = 6 x1 , x2 , x3 ,x4 0解：解：第五节第五节 单纯形法的进一步讨论单纯形法的进一步讨论 0 0m ma ax x0 0m mi in n0 0m mi in n0 0m ma ax xj jj jj jj j 0j0j0j0j所有所有所有所有jjjjjjjjjjjjczzcczzc目标函数目标函数 类型类型填入单纯形表中的填入单纯形表中的目标函数值目标函数值最优性判定最优性判定准则准则选取引入变量的选取引入变量的准则准则检验数检验数-zz-zz极大化极大化

60、极小化极小化1目标函数类型，检验数和最优性判定准则之间目标函数类型，检验数和最优性判定准则之间 的关系。的关系。现将有关组合情况列于下表中：现将有关组合情况列于下表中：二、退化二、退化 当解的非零分量的个数不足当解的非零分量的个数不足m个，或者説个，或者説基变量有取值为零的变量时，这样的解就基变量有取值为零的变量时，这样的解就称为退化解。称为退化解。三、两阶段法（三、两阶段法（Two-Phase Method) 0 0 x xx xx xb bx xa ax xa ax xa ab bx xa ax xa ax xa ab bx xa ax xa ax xa ax xc cx xc cx xc