第一章线性规划20140313四川大学

1、第一章 线性规划1.1线性规划模型 1.1.1线性规划数学模型共同特征 1.1.2线性规划的一般形式 1.1.3线性规划的标准式 1.1.4如何化标准型的问题1.2线性规划的图法解1.3单纯形法 1.3.1线性规划的基本概念 1.3.2单纯形原理 1.3.3单纯形法及软件实现法 1.3.4解的判别1.4对偶理论1.5灵敏度分析运筹学史慧萍22022-3-251.1线性规划模型1.1.1线性规划数学模型共同特征1.1.2线性规划的一般形式1.1.3线性规划的标准式1.1.4如何化标准型的问题运筹学史慧萍32022-3-25问题的提出问题的提出在生产管理和经营活动中，组织者常常必须对在生产管理和经

2、营活动中，组织者常常必须对如何向不同的活动如何向不同的活动分配资源分配资源的问题做出决策，以便的问题做出决策，以便最好地达成组织的目标。最好地达成组织的目标。这样的问题通常有两类，一类是如何合理地使用这样的问题通常有两类，一类是如何合理地使用有限的劳动力、设备、资金等资源，有限的劳动力、设备、资金等资源，以最大化效益以最大化效益；另一类是为了达到一定的目标，应如何组织生产，或另一类是为了达到一定的目标，应如何组织生产，或合理安排工艺流程，或调整产品的成分合理安排工艺流程，或调整产品的成分以使资源以使资源消耗最少。消耗最少。运筹学史慧萍42022-3-25线性规划是运筹学的重要组成部分，也是最基

3、础的线性规划是运筹学的重要组成部分，也是最基础的部分。自部分。自1947年丹齐格（年丹齐格（G.B.Dantzig）提出了求解线性提出了求解线性规划的一般方法单纯形法以来，线性规划在理论上规划的一般方法单纯形法以来，线性规划在理论上趋向成熟，日臻完善，尤其是计算机处理问题的规模及趋向成熟，日臻完善，尤其是计算机处理问题的规模及运算速度提高后，线性规划的应用领域更加广泛。无论运算速度提高后，线性规划的应用领域更加广泛。无论工业、农业、商业、交通运输、军事、经济计划和管理工业、农业、商业、交通运输、军事、经济计划和管理决策等领域都有应用。大到一个国家、一个地区，小到决策等领域都有应用。大到一个国家

4、、一个地区，小到一个企业、一个车间、一个班组都有运用线性规划后提一个企业、一个车间、一个班组都有运用线性规划后提高经济效益的例子。高经济效益的例子。简介简介运筹学史慧萍52022-3-25向不同的活动分配的资源可以是资金、不同的人员以及向不同的活动分配的资源可以是资金、不同的人员以及机器、设备。而需要这些资源的活动也可以是各类生产活动，机器、设备。而需要这些资源的活动也可以是各类生产活动，例如产品生产、营销、在不同媒体做广告、金融活动、进行例如产品生产、营销、在不同媒体做广告、金融活动、进行资金投资或其他一些活动。资金投资或其他一些活动。由于所有活动都要求一定资源作支撑，而资源却是有限由于所有

5、活动都要求一定资源作支撑，而资源却是有限的，这必然导致活动间的冲突与矛盾。这就需要管理者利用的，这必然导致活动间的冲突与矛盾。这就需要管理者利用一些科学的方法进行协调，以使资源达到最大的效用。一些科学的方法进行协调，以使资源达到最大的效用。运筹学史慧萍62022-3-25显然，上述活动所引起的问题是一类显然，上述活动所引起的问题是一类有约束的有约束的最优化问题（最优化问题（Constrained Optimization）。线性规划线性规划正是解决有约束的最优化问题的一种正是解决有约束的最优化问题的一种常用的方法，其涉及的主要概念包括：常用的方法，其涉及的主要概念包括：目标（目标（Object

6、ive）:所要达到的最优结果（最所要达到的最优结果（最或最小）；或最小）；约束条件（约束条件（Constraints）:对所能产生结果的对所能产生结果的限制。限制。运筹学史慧萍72022-3-25解决线性规划问题的一般步骤解决线性规划问题的一般步骤定义问题和定义问题和收集数据收集数据。必须向管理者咨询所要考虑问必须向管理者咨询所要考虑问题涉及到的数据及确定研究的合理目标。题涉及到的数据及确定研究的合理目标。建立模型建立模型，用恰当的数学式表示问题。，用恰当的数学式表示问题。求求出问题的出问题的最优解最优解。进行进行敏感性分析敏感性分析，检查条件发生变化时可能发生的，检查条件发生变化时可能发生的

7、情况。情况。运筹学史慧萍82022-3-25n教材P9例1.1.1： 某公司有三条生产线来生产两种产品，其主要数据如下表（时间单位为小时，利润单位为百元）。请问，如何生产可以让公司每周利润最大？生产线生产每批产品所需时间生产每周可用时间资源单位成本产品产品11041百元/小时202121百元/小时332181百元/小时产品售价(百元)79运筹学史慧萍92022-3-25数学模型n解：设x1为每周生产产品的数量；x2为每周生产产品的数量。线性规划模型为0, 01823122 4 .53max21212121xxxxxxtsxxz运筹学史慧萍102022-3-251.1.1线性规划数学模型共同特征

8、：n(1)一组决策变量x1,x2,xn 。n(2)存在一定的约束条件。n(3)目标函数，要求目标函数实现最大化或最小化 。 以上三个条件（决策变量、约束条件、目标函数）称为数学模型称为线性规划(Linear Programming)的数学模型的三要素。 即在一定的约束条件（限制条件）下，使得某一目标函数取得最大或最小值。当规划问题的目标函数与约束条件都是线性函数，便称为线性规划问题。运筹学史慧萍112022-3-251.1.2线性规划的一般形式)21 (3)-(1 0),( ),( ),( . .1)-(1 )(k21j221122222121112121112211，满足约束条件：目标函数x

9、xxbxaxaxabxaxaxabxaxaxatsxcxcxczminmaxjjmnmnmmnnnnnn运筹学史慧萍122022-3-251.1.3线性规划的标准式0, 0, 0, 0, 018 2312 24 .00053max54321521423154321xxxxxxxxxxxxtsxxxxxz100230102000101A运筹学史慧萍132022-3-25一般线性规划问题的标准型为), 2 , 1( , 0), 2 , 1( ,.max11njxmibxatsxczjinjjijjnjj)51 (6)-(1 , 1, 2 , 1, 0 . .4)-(1 22112222212111

10、2121112211nnjxbxaxaxabxaxaxabxaxaxatsxcxcxcmaxzjmnmnmmnnnnnn1.求目标函数最大值。2.所有的资源约束都用等式表示。3.资源约束等式的右端常数是非负数。4.所有决策变量是非负的，且全部变量出现在非负约束中。运筹学史慧萍142022-3-25线性规划的矩阵式：0 . max21212121222211121121212211XxxxbAXbbbxxxaaaaaaaaatsXCxxxcccxcxcxczTnmnmnmmnnTnnnn0.maxXbAXtsXCzT运筹学史慧萍152022-3-25 (1)最小化问题的转化。 若目标函数min

11、zCTX，即令zz，于是得到max z CTX。 (2)不等式的处理。 约束方程为不等式有两种情况：一种是约束方程为不等式，则可在不等式的左端加入非负松弛变量，把原不等式变为等式；另一种是约束方程为不等式，则可在不等式的左端减去一个非负剩余变量，把不等式约束条件变成等式约束条件。松弛变量与剩余变量在目标函数中的系数为0。 (注：人工变量是为了始系数矩阵中容易找到一个基而在方程等式中加的一个人造变量。) 1.1.4如何化标准型的问题运筹学史慧萍162022-3-25 (3)非正变量与符号无限制变量的处理。 某个变量xj0，令xjxj ，则新变量xj0；若存在取值无约束变量xk，可令xkxkxk，

12、其中xk、xk0。 (4)约束条件中带有绝对值不等式ax1+bx2d (d 0)，则可把它化为一个不等式组ax1+bx2d ，ax1bx2d，再按(2)化为等式约束。 (5)某个变量有上、下界ej xj fj，只要令xjxjej引入新变量，便可化ej xj fj为 0 xj fj-ej，最后将上限不等式约束条件变成等式约束条件。运筹学史慧萍172022-3-25解 令x3x3x3再引入松弛变量x4、剩余变量x5，则有如下标准型：010)(36)(427)(3.)00)(5(max5433213325332143321543321xxxxxxxxxxxxxxxxxxxtsxxxxxxz、例 将下

13、面LP问题化为标准型：无符号限制、32132321321321, 010364273.5minxxxxxxxxxxxtsxxxz运筹学史慧萍182022-3-251.2图解法 现对例1.1.1进行图解。该计划问题可用数学模型表示为： 目标函数 满足约束条件0, 018231224.53max21212121xxxxxxtsxxz运筹学史慧萍192022-3-25图解法的主要步骤是：n第一步：在直角坐标系中分别做出各约束条件，从而确定可行域(线性规划问题的解的集合)。n第二步：做出一条目标函数等值线。n第三步；将目标函数等值线沿目标函数值增大(或减小)方向移动，以求得最优解或确定线性规划无解。

14、图解法的几种情况： 1.唯一解 2.无穷解 3.无界解 4.无解max zx1+3x2s.t. x1+ x26-x1+2x28x1 0, x20可行域目标函数等值线最优解(4/3,14/3)(6,0)(0,4)(-8,0)(0,6)0 x1x2例1：线性规划的图解例题(唯一解)2022-3-2520运筹学史慧萍运筹学史慧萍212022-3-250, 01823122 4 .53max21212121xxxxxxtsxxz例2：线性规划的图解例题(唯一解)(4,0)(0,6)(6,0)(0,9)(4,3)(2,6)(4,6)(0,0)x1x2可行域目标函数等值线最优解运筹学史慧萍222022-3

15、-250, 01823122 4 .23max21212121xxxxxxtsxxz例3：线性规划的图解例题(无穷解)(4,0)(0,6)(6,0)(0,9)(4,3)(2,6)(4,6)(0,0)x1x2可行域目标函数等值线最优解运筹学史慧萍232022-3-250, 04 .53max21121xxxtsxxz例4：线性规划的图解例题(无界解)(4,0)(0,0)x1x2目标函数等值线可行域运筹学史慧萍242022-3-250, 050531823122 4 .53max2121212121xxxxxxxxtsxxz例5：线性规划的图解例题(无解)(4,0)(0,6)(6,0)(0,9)(

16、4,3)(2,6) (4,6)(0,0)x2目标函数等值线(0,10)(16.67,0)无可行域！x1运筹学史慧萍252022-3-25线形规划问题最优解的情况：n有最优解1)有唯一的最优解2)有无穷多的最优解n无最优解1)无界解（有可行解但无有最优解）2)无可行解运筹学史慧萍262022-3-25图解法基本要求n能正确地按图解法的步骤画出图来解答题目，并会判定解的类型。运筹学史慧萍272022-3-253.3单纯形法3.3.1线性规划的基本概念3.3.2单纯形原理3.3.3单纯形法及软件实现法3.3.4解的判别运筹学史慧萍282022-3-253.3.1线性规划的基本概念可行解： 满足约束条

17、件(b)、(c)的解X=（x1， ，xn)T，称为线性规划问题的可行解。全部可行解的集合称为可行域。最优解：使目标函数(a)达到最大值的可行解称为最优解。njxmibxatsxczjnjijijnjjj,.,2 , 10,.,2 , 1. .max11 （a） （b） （c）运筹学史慧萍292022-3-25线性规划的可行域是凸集线性规划的最优解在顶点(极点)上凸集凸集不是凸集顶点不是凸集运筹学史慧萍302022-3-25u 几何意义 P15凸集：设K是n维欧氏空间的一点集，若对任意的x1，x2K， 有 ，则称K为凸集。) 10()1 (21Kxx的凸组合。，为则称使得且，若存在个点，中的维欧

18、式空间的是凸组合：设kkkkiiikkxxxxxxxxkiknxxx212211121n21,1);, 2 , 1( 10,E,。的一个顶点（或极点）为，则称线性组合表示为的中的两点不能用。若是凸集，顶点：设KxxxxxxKxKxK) 10()1 (:,2121运筹学史慧萍312022-3-25定义1基：设Amn (nm)为约束方程组(b)的系数矩阵，其秩为m。Bmm 是矩阵A 中的一个mm 阶的满秩子矩阵，称B 是线性规划问题的一个基。不失一般性，设mmmmmmmPPPaaaaaaaaaB,.,21212222111211 B 中的每一个列向量Pj（j=1,2,m）称为基向量，与基向量Pj

19、对应的变量xj 称为基变量。除基变量以外的其它变量称为非基变量。运筹学史慧萍322022-3-25定义2：基解：假设系数矩阵A 的秩为m，不妨设A 中前m 个列向量线性独立，方程可以写为nmnnnmmmmmmmmmmmmmxaaaxaaabbbxaaaxaaaxaaa211112112121222212112111令所有非基变量xm+1= =xn=0， 由|B|0，根据克莱姆规则，可得m个基变量的唯一解xb=(x1,x2,xm)加上所有取值为0 的非基变量，得：x=(x1,x2,xm,0,0)称x 为线性规划问题的基解。运筹学史慧萍332022-3-25定义3：基可行解： 满足变量非负约束条件

20、(c)的基解称为基可行解。定义4：可行基：对应于基可行解的基称为可行基。可行解基 解基可行解退化基可行解与非退化基可行解: 称含零值基变量的可行解为退化基可行解,对应的基为退化可行基。 称基变量都不为零的基可行解为非退化基可行解,对应的基为非退化可行基。),(运筹学史慧萍342022-3-25引理1.1:若线性规划问题存在可行域,则其可行域是凸集。引理1.2:线性规划问题的可行解X=(x1,x2,xn)T为基可行解的充要条件是X的正分量所对应的系数列向量是线性独立的。定理1.1:线性规划问题的基可行解X对应于可行域D的顶点。定理1.2:若可行域有界,线性规划问题的目标函数一定在其可行域的顶点上

21、达到最优,即一定存在一个基可行解是最优解。定理1.3 线性规划问题的一般形式与标准形式等价。若可行域无界,则线性规划问题可能无最优解,也可能有最优解。若有也一定在某个顶点上得到。定理1.2给我们的启示 1.存在性 2.最优解(若有)一定在某个顶点上得到njxmibxatsxczjnjijijnjjj,.,2 , 10,.,2 , 1. .max11线性规划问题：运筹学史慧萍352022-3-25例题：试求下例线性规划问题的一个基(向量)及其对应的基变量、非基变量，一个基解和一个基可行解。543211001030105400149PPPPPA543100010001PPPB基解：x1 0， x2

22、0，x3360，x4200，x5300基变量x3，x4，x5。非基变量x1，x2。x1 0， x20，x3360，x4200，x5300是基可行解5421010015004PPPB基变量x2，x4，x5。非基变量x1，x3。基解：x1 0， x290，x30，x4250，x5600 x1 0， x290，x30，x4 250 ，x5 600不是基可行解 x1 x2 x3 x4 x5 03001032005436049.00012070max5432152142132154321xxxxxxxxxxxxxxtsxxxxxz、mnC?最多能有多少个基解基解、基可行解(基解是否实际可行解？)max

23、zx1+3x2s.t. x1+ x26-x1+2x28x1 0, x20max z x1+3x2+0 x3+0 x4s.t. x1+ x2+x3 =6 -x1+2x2 +x4=8 x1, x2,x3,x40 x1A(6,0)C(0,4)E(-8,0)D(0,6)O(0,0)x2Bx3=0 x4=02022-3-2536运筹学史慧萍几何概念代数概念约束直线满足一个等式约束的解约束半平面满足一个不等式约束的解约束半平面的交集：凸多边形满足一组不等式约束的解约束直线的交点基解可行域的顶点(极点)基可行解目标函数等值线：一组平行线 目标函数值等于一个常数的解2022-3-2537运筹学史慧萍运筹学史慧

24、萍382022-3-25线性规划模型基本要求n 1理解线性规划的概念。n 2理解线性规划的一般形式与标准形式，能够把前者转化为居者。n 3掌握线性规划问题的可行解、最优解和标准形式的线性规划问题的基、基解、基可行解、可行基等重要概念。运筹学史慧萍392022-3-251.3.2单纯形法原理（用代数方法求解LP）图解法的局限性？ 1947年G.B.Dantzig提出的单纯形法提供了方便、有效的通用算法求解线性规划。一、单纯形法的基本思想1、顶点的逐步转移 即从可行域的一个顶点（基本可行解）开始，转移到另一个顶点（另一个基本可行解）的迭代过程，转移的条件是使目标函数值得到改善（逐步变优），当目标函

25、数达到最优值时，问题也就得到了最优解。运筹学史慧萍402022-3-25 线性规划问题的可行域是凸集，一个线性规划问题有最优解，就一定可以在可行域的顶点上找到。 于是，若某线性规划只有唯一的一个最优解，这个最优解所对应的点一定是可行域的一个顶点；若该线性规划有多个最优解，那么肯定在可行域的顶点中可以找到至少一个最优解。顶点转移的依据？ 转移条件？ 转移结果？ 使目标函数值得到改善 得到LP最优解，目标函数达到最优值 2需要解决的问题： (1)为了使目标函数逐步变优，怎么转移？ (2)目标函数何时达到最优 判断标准是什么？ 运筹学史慧萍412022-3-25第一步：引入非负的松弛变量x3,x4,

26、x5, 将该LP化为标准型0,18231224.5321212121xxxxxxtsxxz max)5 , 4 , 3 , 2 , 1(018231224. .00053521423154321jxxxxxxxxtsxxxxxz maxj运筹学史慧萍422022-3-25对应的基变量是 x3, x4 ,x5 第二步：寻求初始可行基，确定基变量100230102000101A100010001543PPPB运筹学史慧萍432022-3-25第三步：写出初始基本可行解和相应的目标函数值两个关键的基本表达式：(1) 用非基变量表示基变量的表达式TXxxxxxxx)18,12, 4 , 0 , 0(2

27、3182124)0(2152413初始基可行解0 53021）（当前的目标函数值ZxxZ(2) 用非基变量表示目标函数的表达式运筹学史慧萍442022-3-25第四步：分析两个基本表达式，看看目标函数是否可以改善？(1)分析用非基变量表示目标函数的表达式 z=3x1+5x2 非基变量前面的系数均为正数，所以任何一个非基变量进基都能使Z值增加 通常把非基变量前面的系数叫“检验数”；(2) 选哪一个非基变量进基？ 选x2为进基变量（换入变量）运筹学史慧萍452022-3-25(3) 确定出基变量 x2进基意味着其取值从0变成一个正数，能否无限增大？ 当x2增加时，x3，x4，x5如何变化？ 现在的

28、非基变量是哪些？ 具体如何确定换出变量？由用非基变量表示基变量的表达式215241323182124xxxxxxx 当x2增加时，x4，x5会减小，但有限度必须大于等于0，以保持解的可行性！（这时x1仍是非基变量，取值为0）于是运筹学史慧萍462022-3-256218,212min2182120218021223182124222222152413xxxxxxxxxxxx 当x2的值从0增加到6时，x4首先变为0，此时x5=60,因此选x4为出基变量（换出变量）。这种用来确定出基变量的规则称为 “最小比值原则”。(4) 基变换新的基变量x3,x2,x5；新的非基变量x1,x4；写出用非基变量

29、表示基变量的表达式：215421323182164xxxxxxx215241323182124xxxxxxx4154213362164xxxxxxx运筹学史慧萍472022-3-25可得新的基可行解(5) 写出用非基变量表示目标函数的表达式 ：414121x25x330)x216(5x3x5x3Z可得相应的目标函数值为Z（1）=30检验数仍有正的返回(1)进行讨论。第五步：上述过程何时停止？当用非基变量表示目标函数的表达式中，非基变量的系数（检验数）全部非正时，当前的基本可行解就是最优解!TX)6 , 0 , 4 , 6 , 0()1(运筹学史慧萍482022-3-251.3.3单纯形法及软件

30、实现求单纯形表法解线性规划问题:0,36 2 2 25 .00243max6543216432254321654321xxxxxxxxxxxxxxxxtsxxxxxxz解：标准型0,362 2 25 .243max4321432243214321xxxxxxxxxxxxtsxxxxz运筹学史慧萍492022-3-25初始单纯形表x2进基。方程BV系数右边比值zx1x2x3x4x5x6z - 3x1-4x2+x3-2x4 =0z1-3-41-2000 x1 +x2 +x3 +x4 +x5 25 x5011111025x1 +2x2 +x3 +2x4 +x6 36 x6012120136 x6出基

31、。25/1=2536/2=18运筹学史慧萍502022-3-25单纯形表第一次迭代(以a22为中心)x2进基。方程BV系数右边比值zx1x2x3x4x5x6z - 3x1-4x2+x3-2x4 =0z1-3-41-2000 x1 +x2 +x3 +x4 +x5 25 x5011111025x1 +2x2 +x3 +2x4 +x6 36 x6012120136 x6出基。x20-132272z-x1+3x3+2x4 +2x6 =721001/21/201-1/27(1/2)x1 +(1/2)x3 +x5-( 1/2)x6 7101/21/2101/218(1/2)x1 +x2 +(1/2)x3

32、+x4+(1/2)x618 检验数10，故不是最优解。0运筹学史慧萍512022-3-25换入变量与换出变量的确定x1进基。方程BV系数右边比值zx1x2x3x4x5x6z-x1+3x3+2x4 +2x6 =72z1-10320272(1/2)x1+(1/2)x3+x5- (1/2)x6 7x501/201/201-1/27(1/2)x1 +x2 +(1/2)x3+x4+(1/2)x6 18 x201/211/2101/218 x5出基。2172118运筹学史慧萍522022-3-25单纯形表第二次迭代(以a11为中心)x1进基。方程BV系数右边比值zx1x2x3x4x5x6z-x1+3x3+

33、2x4 +2x6 =72z1-10320272(1/2)x1+(1/2)x3 +x5- (1/2)x6 7x501/201/201-1/27(1/2)x1+x2 +(1/2)x3+x4+(1/2)x6 18 x201/211/2101/218 x5出基。010422186z+4x3+2x4+2x5+x6 =8600101-1111x2+x4 x5+x611100102-114 x1+x3 +2x5- x6 14最优解为(x1， x2， x3， x4， x5 ， x6) (14, 11,0,0, 0,0)最优值为86。检验数i0，故是最优解。x1 运筹学史慧萍532022-3-25单纯形法软件实

34、现（例单1）运筹学史慧萍542022-3-250,182312245321212121xxxxxxxxz max用WINQSB求解下列线性规划问题：（例灵敏度分析）运筹学史慧萍552022-3-251.3.4解的判别（1）退化现象(经过几次迭代后会出现循环)防止循环的方法： 勃兰特规则：1、选取检验数j 0中下标最小的非基变量xk 为换入变量，即： k=minj|j 02、当有两个或两个以上的最小比值时，选取下标最小的基变量为换出变量。运筹学史慧萍562022-3-25BVEq系 数右边-zx1x2x3x4x5x6x7-z(0)1000-3/420-1/260 x1(1)01001/4-8-1

35、90 x2(2)00101/2-12-1/230 x3(3)000100101-z(0)13000-4-7/2330 x4(1)04001-32-4360 x2(2)0-210043/2-150 x3(3)000100101-z(0)111000-2180 x4(1)0-1280108-840 x5(2)0-1/21/40013/8-15/40 x3(3)000100101-z(0)1-2301/400-30 x6(1)0-3/2101/801-21/20 x5(2)01/16-1/80-3/64103/160 x3(3)03/2-11-1/80021/21-z(0)1-110-1/21600

36、0 x6(1)02-60-5/256100 x7(2)01/3-2/30-1/416/3010 x3(3)0-2615/2-56001-z(0)10-20-7/4441/200 x1(1)01-30-5/4281/200 x7(2)001/301/6-4-1/610 x3(3)000100101-z(0)1000-3/420-1/260 x1(1)01001/4-8-190 x2(2)00101/2-12-1/230 x3(3)0001001017 , 6 , 5 , 4 , 3 , 2 , 1, 01 035 . 0125 . 0 09 825. 0 65 . 02075. 0 637654

37、2765417654jxxxxxxxxxxxxxstxxxxzminj运筹学史慧萍572022-3-25BVEq系 数右边-zx1x2x3x4x5x6x7-z(0)1000-3/420-1/260 x1(1)01001/4-8-190 x2(2)00101/2-12-1/230 x3(3)000100101-z(0)13000-4-7/2330 x4(1)04001-32-4360 x2(2)0-210043/2-150 x3(3)000100101-z(0)111000-2180 x4(1)0-1280108-840 x5(2)0-1/21/40013/8-15/40 x3(3)000100

38、101-z(0)1-2301/400-30 x6(1)0-3/2101/801-21/20 x5(2)01/16-1/80-3/64103/160 x3(3)03/2-11-1/80021/21-z(0)10-10-5/432030 x6(1)00-20-1241-60 x1(2)01-20-3/416030 x3(3)00211-24061-z(0)1001/2-3/420061/2x6(1)000100101x1(2)01011/4-8091x2(3)0011/21/2-12031/2-z(0)103/25/402021/25/4x6(1)000100101x1(2)01-1/23/40-

39、2015/23/4x4(3)00211-24061注：选取j 0中下标最小的非基变量xk 为换入变量经过几次迭代后会出现循环运筹学史慧萍582022-3-25BVEq系 数右边-zx1x2x3x4x5x6x7-z(0)1000-3/420-1/260 x1(1)01001/4-8-190 x2(2)00101/2-12-1/230 x3(3)000100101BVEq-zx1x2x3x4x5x6x7-z(0)13000-4-7/2330 x4(1)04001-32-4360 x2(2)0-210043/2-150 x3(3)000100101遵循勃兰特规则：选取j 0中下标最小的非基变量xk

40、为换入变量。避免循环出现。7 , 6 , 5 , 4 , 3 , 2 , 1, 01 035 . 0125 . 0 09 825. 0 65 . 02075. 0 6376542765417654jxxxxxxxxxxxxxstxxxxzminj运筹学史慧萍592022-3-25BVEq-zx1x2x3x4x5x6x7-z(0)111000-2180 x4(1)0-1280108-840 x5(2)0-1/21/40013/8-15/40 x3(3)000100101BVEq-zx1x2x3x4x5x6x7-z(0)1-2301/400-30 x6(1)0-3/2101/801-21/20 x

41、5(2)01/16-1/80-3/64103/160 x3(3)03/2-11-1/80021/21选取j 0中下标最小的非基变量xk 为换入变量运筹学史慧萍602022-3-25BVEq-zx1x2x3x4x5x6x7-z(0)10-10-5/432030 x6(1)00-20-1241-60 x1(2)01-20-3/416030 x3(3)00211-24061BVEq-zx1x2x3x4x5x6x7-z(0)1001/2-3/420061/2x6(1)000100101x1(2)01011/4-8091x2(3)0011/21/2-12031/2选取j 0中下标最小的非基变量xk 为换

42、入变量运筹学史慧萍612022-3-25BVEq-zx1x2x3x4x5x6x7-z(0)103/25/402021/25/4x6(1)000100101x1(2)01-1/23/40-2015/23/4x4(3)00211-24061注：退化基本可行解中的非零分量个数一定小于m,非退化解中的非零分量个数一定等于m。 运筹学史慧萍622022-3-25例：单纯形法运筹学史慧萍632022-3-25(2)无穷多最优解BVEqzx1x2x3x4右边比值z(0)1-1-1000 x3(1)01-11011x4(2)01101220,21-. . 21212121xxxxxxtsxxzmax解线性规划

43、问题运筹学史慧萍642022-3-25BVEqzx1x2x3x4右边比值z(0)10-2101x1(1)01-1101x4(2)002-1111/2BVEqzx1x2x3x4右边比值z(0)100012x1(1)0101/21/23/23x2(2)001-1/21/21/2检验数i0，故是最优解。最优解：x(1)=(3/2，1/2） x(2)=(0，2），最优值为2。运筹学史慧萍652022-3-25BVEqzx1x2x3x4右边z(0)100012x3(1)020113x2(2)011012最优解：x(1)=(3/2，1/2） x(2)=(0，2）)232,23()2,0)(1 ()21,2

44、3(10)1 ()2()1(xxx是最优解检验数中非基变量的系数中有零,可能存在无穷多最优解右边的值与上步单纯形法结果相比一样运筹学史慧萍662022-3-25当所有检验数均小于或等于零且某个非基变量的检验数等于零并且对应变量的系数中有正数，则表明该线性规划问题有无穷多最优解；运筹学史慧萍672022-3-25运筹学史慧萍682022-3-25（3）无界解用单纯形法求解下列线性规划问题：0,82442.42121212121xxxxxxxxtsxxz max运筹学史慧萍692022-3-25BVEqzx1x2x3x4x5右边比值z（0）1-4-10000 x3(1)0-111002-x4(2)

45、01-401044x5(3)01-200188（0）10-1704016x3(1)00-31106-x1(2)01-40104-x5(3)0020-1142（0）1000-9/217/250 x3(1)0001-1/23/212x1(2)0100-1212x2(3)0010-1/21/22 存在j0, 但此时迭代中无换出变量，则目标函数值可任意大。0,82442.42121212121xxxxxxxxtsxxz max运筹学史慧萍702022-3-25-x1+x2=2x1-4x2=4x1-2x2=8x1x2无界解0248可行域0,82442. .42121212121xxxxxxxxtsxxz

46、 max运筹学史慧萍712022-3-25从两次迭代的单纯形表中，得到约束方程组：5425415435425415432121221223211222121122122321xxxxxxxxxxxxxxxxxx02/1122/12120,5432154xMxMxMxMxxMx，可得一组解：令经验证，该组解是可行解，此时目标函数z=4x1+x2=50+4.5M由于M可以是任意大的正数，因此目标函数值无界解。0,82442.42121212121xxxxxxxxtsxxz max线性规划问题运筹学史慧萍722022-3-25无界解线性规划的软件实现过程如果存在某个正的检验数，而相应变量的系数中没有

47、正数，则表明该线性规划问题有无界解。运筹学史慧萍732022-3-25（4）无可行解0, 050531823122 4 .53max2121212121xxxxxxxxtsxxz运筹学史慧萍742022-3-25基变量中含有非零的人工变量。这时无可行解。0,50531823122 4 .532121212121xxxxxxxxtsxxz max运筹学史慧萍752022-3-25n 大大M法法 大大M法首先将线性规划问题化为标准型。如果约束方程组中包含法首先将线性规划问题化为标准型。如果约束方程组中包含有一个单位矩阵有一个单位矩阵I，那么已经得到了一个初始可行基。否则在约束方，那么已经得到了一个

48、初始可行基。否则在约束方程组的左边加上若干个非负的人工变量，使人工变量对应的系数列向程组的左边加上若干个非负的人工变量，使人工变量对应的系数列向量与其它变量的系数列向量共同构成一个单位矩阵。以单位矩阵为初量与其它变量的系数列向量共同构成一个单位矩阵。以单位矩阵为初始基，即可求得一个初始的基本可行解。始基，即可求得一个初始的基本可行解。 为了求得原问题的初始基本可行解，必须尽快通过迭代过程把人为了求得原问题的初始基本可行解，必须尽快通过迭代过程把人工变量从基变量中替换出来成为非基变量。为此可以在目标函数中赋工变量从基变量中替换出来成为非基变量。为此可以在目标函数中赋予人工变量一个绝对值很大的负系

49、数予人工变量一个绝对值很大的负系数-。这样只要基变量中还存在。这样只要基变量中还存在人工变量，目标函数就不可能实现极大化。人工变量，目标函数就不可能实现极大化。 以后的计算与单纯形表解法相同，只需认定是一个很大的正数以后的计算与单纯形表解法相同，只需认定是一个很大的正数即可。假如在单纯形最优表的基变量中还包含人工变量，则说明原问即可。假如在单纯形最优表的基变量中还包含人工变量，则说明原问题无可行解。否则最优解中剔除人工变量的剩余部分即为原问题的初题无可行解。否则最优解中剔除人工变量的剩余部分即为原问题的初始基本可行解。始基本可行解。运筹学史慧萍762022-3-25用大用大M M法求解下面的线

50、性规划问题法求解下面的线性规划问题: :解：解： 首先将原问题化为标准型首先将原问题化为标准型 0,3 12 .2212212121xxxxxxxtsxxz max)5 , 4 , 3 , 2 , 1(03 12 .25242132154321jxxxxxxxxxtsxxxxxz maxj)7 , 6 , 5 , 4 , 3 , 2 , 1(03 1 2 .-2-5274216321765432176jxxxxxxxxxxxtsMxMxxxxxxz maxMxxj赋予，并在目标函数中分别，添加人工变量运筹学史慧萍772022-3-25 0 1 -1/2 -1/2 0 1/2 1/23/2x22

51、 1 0 -1/2 1/2 0 1/2 -1/21/2x1-1- -1 1 0 -1 0 0 11x221/2 2 0 -1 1 0 1 -11x6-M1/1 -1 1 0 -1 0 0 11x7-M2/1 1 1 -1 0 0 1 02x6-M 0 0 1/2 3/2 0 -1/2-M -3/2-M5/2Z 0 0 1/2 1/2 1 -1/2 -1/23/2x50 1+2M 0 -M 2+M 0 0 -2-2M2-MZ2/1 1 0 0 1 1 0 -12x50 -1 2+2M -M -M 0 0 0-3MZ3/1 0 1 0 0 1 0 03x50 x1 x2 x3 x4 x5 x6 x

52、7bXBCB比值比值i -1 2 0 0 0 -M -MCj值是怎么得来的？与只在左端加入松弛变量时获得的标准型有何不同？大M单纯形法：运筹学史慧萍782022-3-25最优解最优解X*=(0,3,1,2,0)T 最优值最优值Z*=6 0 1 0 0 1 0 03x22 1 0 0 1 1 0 -12x40 1 1 -1 0 0 1 02x22 2 0 -1 1 0 1 -11x40- 0 1 -1/2 -1/2 0 1/2 1/23/2x221/2/1/2 1 0 -1/2 1/2 0 1/2 -1/21/2x1-1 -1 0 0 0 -2 -M -M6Z -1 0 1 0 1 -1 01x

53、30 -3 0 2 0 0 -2-M -M4Z -1 0 1 0 1 -1 01x50 0 0 1/2 3/2 0 -1/2-M -3/2-M5/2Z3/2 /1/2 0 0 1/2 1/2 1 -1/2 -1/23/2x50 x1 x2 x3 x4 x5 x6 x7bXBCB比值比值i -1 2 0 0 0 -M -MC运筹学史慧萍792022-3-25检验准则(适用于无人工变量的问题)（目标准则：最大值；判断系数：为cj-zj）(注：与课件代数法一致P47，但与课件P52的判断系数正好相反)n (1)当所有检验数均小于或等于零时，表明现有顶点(基可行解)即为最优解；n (2)当所有检验数均小于或等于零且某个非基变量的检验数等于零并且对应变量的系数中有正数，则表明该线性规划问题有无穷多最优解；n (3)如果存在某个正的检验数，而相应变量的系数中没有正数，则表明该线性规划问题有无界解。运筹学史慧萍802022-3-25目标函数为max的线型规划问题的单纯形法的计算步骤（软件linear programming (LP)这里检验数规定为cjzj ，则当所有cjzj 0时