第二章线性规划

第二章线性规划§1.2运筹学的数学模型模型的定义:模型是一件实际事物或情况的代表或抽象。实际事物是A，若B能够真实地描述A，则称B为A的模型。数学模型就是用字母、数字和运算符号将系统或过程的某些特征及相互关系表达出来，他试图定量地表示系统的各种关系，以便对系统和问题进行量化分析。第2章线性规划线性规划问题可行区域与基本可行解单纯形方法初始解对偶性及对偶单纯形方法灵敏度分析§2.1线性规划问题线性规划问题举例线性规划模型1线性规划问题举例生产计划问题运输问题营养配餐问题资金使用问题1线性规划问题举例（一）某工厂拥有A、B、C三种类型的设备，生产甲、乙两种产品。已知条件如下表所示：

产品甲产品乙设备能力设备A3265设备B2140设备C0375利润（元/件）15002500

问题：工厂应如何安排生产可获得最大的总利润？1线性规划问题举例（一）解：设生产两种产品的数量分别为x1,x2，总利润为z.目标函数约束条件1线性规划问题举例（二）设要从甲地调出物资2000吨，从乙地调出物资600吨，从丙地调出物资500吨，分别供应给A地1700吨、B地1100吨、C地200吨、D地100吨。已知每吨运费如下表所示。1726384315375151乙1572521甲DCBA销地产地单位：元/t丙假定运费与运量成正比例，问怎样才能找到一个总运费最省的调拨计划？2321341600500170011002001002000供应量供应地运价需求量需求地212571551513715433826171线性规划问题举例（二）1726384315375151乙1572521甲DCBA销地产地丙x22x11x12x13x21x23x31x32x33x14x24x341线性规划问题举例（二）用(i=1,2,3;j=1,2,3,4)分别表示从甲乙丙三个产地运往A,B,C,D四个销地的物资数量。1线性规划问题举例（二）1线性规划问题举例（二）简化表达式1线性规划问题举例（三）假定一个成年人每天需要从食物中获得3000千卡的热量、55克蛋白质和800毫克的钙。市场情况见下表。问如何选择才能在满足营养的前提下使购买食品的费用最小？食品名称热量(千卡)蛋白质(克)钙(毫克)价格(元)猪肉鸡蛋大米白菜100080090020050602010400200300500309631线性规划问题举例（三）解：设xj为第j种食品每天的购入量，则配餐问题的线性规划模型为：

minz=30x1+9x2+6x3+3x4s.t.1000x1+800x2+900x3+200x4300050x1+60x2+20x3+10x455400x1+200x2+300x3+500x4800

x1，x2，

x3，x401线性规划问题举例（四）设有400万元资金，要求4年内使用完，若在一年内使用资金万元，则可得到效益万元，（效益不能再次使用），当年未使用的资金可存入银行，年利率为10%，试制定出资金的使用计划，以使4年资金效益之和最大。1线性规划问题举例（四）设变量分别表示第年所使用的资金数解：1线性规划问题举例（四）线性规划问题的结构特征都有一组决策变量；都有一组约束条件，它们是线性等式或不等式；都有一个确定的目标，这个目标可以表示成决策变量的线性函数，根据问题不同，有的要求实现极大化，有的要求实现极小化。线性规划问题的本质：研究在一组线性约束下，一个线性函数的极值问题。2线性规划模型一般形式标准形式形式转换2线性规划模型（一般形式）目标函数约束条件2线性规划模型（标准形式）minz=c1x1+c2x2+…+cnxn

s.t.

a11x1

+a12x2

+…+a1nxn

=b1a21x1

+a22x2

+…+a2nxn

=b2…………am1x1

+am2x2

+…+amnxn

=bmx1

，x2

，…，xn

≥0目标函数约束条件2线性规划模型（标准形式）2线性规划模型（标准形式）

用向量表示

用矩阵表示2线性规划模型（标准形式）2线性规划模型（标准形式）标准形式的特点：

目标函数极小化

约束条件全部是等式

所有的变量都是非负的2线性规划模型（形式转换）令xj=xj-

xj，对模型中的进行变量代换。⑴目标函数为maxz=c1x1+c2x2++cnxn令z=-z

,变为minz=-c1x1-c2x2--cnxn⑵约束条件为a11x1+a12x2++a1nxn≤b1加入非负变量xn+1，称为松弛变量，有

a11x1+a12x2++a1nxn+xn+1=b1⑶约束条件为a11x1+a12x2++a1nxn≥b1减去非负变量xn+1，称为剩余变量，有

a11x1+a12x2++a1nxn-xn+1=b1⑷变量xj无约束。2线性规划模型（形式转换）例：将如下线性规划问题化成标准形式：§2.2可行区域与基本可行解基本概念图解法求解两个变量的线性规划问题可行区域的几何结构基本可行解及线性规划的基本定理1基本概念1基本概念对于标准的LP问题来说满足这两个条件的x是可行解或者可行点三者皆满足是最优解2图解法求解两个变量线性规划问题（1）max z=x1+3x2

s.t. x1+x2≤6 -x1+2x2≤8 x1,x2≥0可行域目标函数等值线最优解64-860x1x2最优解为x=(4/3,14/3)T最优值z=4/3+14=46/32图解法求解两个变量线性规划问题（2）max z=3x1+3x2

s.t. x1+x2≤6 -x1+2x2≤8 x1,x2≥0可行域目标函数等值线64-860x1x2最优解?最优值?2图解法求解两个变量线性规划问题（3）max z=3x1+3x2

s.t.-x1+2x2≤8 x1,x2≥0可行域目标函数等值线4-80x1x2最优解?最优值?min z=3x1+3x2?2图解法求解两个变量线性规划问题（4）max z=3x1+3x2

s.t.-x1+2x2≤8x1-2x2≤-9 x1,x2≥0可行域?2图解法求解两个变量线性规划问题——在边界，而且是在某个顶点获得。——多边形，而且是“凸”形的多边形。线性规划的可行域是一个什么形状？最优解(如果存在)在什么位置获得？两变量线性规划问题解的性质2图解法求解两个变量线性规划问题1）唯一解2）多重最优解3）无有限最优解4）无可行解求解线性规划问题可能出现哪些情况？3可行区域的几何结构基本假设凸集可行域的凸性问题3可行区域的几何结构（基本假设）3可行区域的几何结构（凸集）3可行区域的几何结构（凸集）3可行区域的几何结构（凸集）3可行区域的几何结构（凸集）定义2.2.4：设为凸集，如果对任意和任意，都有则称x为S的顶点。3可行区域的几何结构（可行域的凸性）定理2.2.1是凸集。定理任意多个凸集的交集还是凸集。3可行区域的几何结构（可行域的凸性）3可行区域的几何结构（问题）4基本可行解及线性规划的基本定理定义基本定理结论问题4基本可行解及线性规划的基本定理（定义）基(基阵)：设B是秩为m的约束矩阵ARmn中的一个m阶满秩子方阵，则称B为一个基（基阵）。基向量：B中m个线性无关的列向量称为基向量。基变量：变量x中与基向量对应的m个分量称为基变量.其余的分量称为非基变量。基本解：令所有的非基变量取值为零得到的解。基本可行解：既是基本解又是可行解。可行基：基本可行解对应的基B。=目标函数约束条件基矩阵右边常数=基变量4基本可行解及线性规划的基本定理（定义）基本解基本可行解可行基4基本可行解及线性规划的基本定理（定义）例：考虑如下线性规划问题，用图解法求解，并把它化成标准形式，且指出基、基解：4基本可行解及线性规划的基本定理（定义）0x1x24基本可行解及线性规划的基本定理（定义）4基本可行解及线性规划的基本定理（定义）0x1x2（0，0）（4，0）（4，2）（0，4）（8，0）4基本可行解及线性规划的基本定理（定理）4基本可行解及线性规划的基本定理（结论）线性规划问题的可行域是凸集。基本可行解与可行域的顶点对应，可行域有有限多个顶点(基本可行解)。最优解一定可以在某个顶点上(基本可行解)得到。非可行解可行解

基可行解

基解

最优解？4基本可行解及线性规划的基本定理

（结论与问题）4基本可行解及线性规划的基本定理（总结）求解LP的基本思路1、构造初始可行基；2、求出一个基可行解（顶点）；3、最优性检验：判断是否最优解；4、基变换，转2。要保证目标函数值比原来更优。§2.3单纯形方法1947年由Dantzig提出，被称为20世纪最好的十个算法之一，是迄今为止解决线性规划问题的最成熟的方法。§2.3单纯形方法典式基本定理单纯形方法单纯形表（单纯形方法的实现）=1典式(定义)=1典式（定义）001100010=0001典式（定义）典式的特点：1、约束条件中含有一个单位矩阵；2、目标函数中不含基变量。000001100010=1典式（定义）000001100010=1典式（例）1典式（定义）问题：如何判断一个基本可行解是否为最优解呢？典则形式的LP问题中，目标函数中的变量系数的符号，对于判断某一个基本可行解是不是最优解非常重要。本例中是什么？典则形式的LP问题中，目标函数系数向量的负向量。称为检验数向量.2基本定理定理2.3.1例如：2基本定理例如：定理2.3.2则原问题无界。2基本定理例如：定理2.3.3对应则2基本定理定理对于任何非退化的线性规划问题，从任何基本可行解开始，经过有限多次迭代，或者得到一个基本可行解，或者作出该线性规划问题无界的判断。3单纯形方法Step1将线性规划问题化成典式,求出各个非基变量的检验数。Step2判断所有非基变量的检验数是否非正,若是,则结束；否则转step3。Step3选取一个检验数大于零的非基变量为进基变量；Step4若进基变量所对应的约束条件系数全为非正数,则原问题无界,结束；否则,按最小比值原则确定出基变量；Step5进行迭代(用方程组的初等行变换法确定新的基对应的典式及检验数),转step2。4单纯形表例1求解LP问题Z01-2000x1x4x51-210001-31001-101212x1x2x3x4x5RHSZ01-2000x1x4x51-210001-31001-101212x1x2x3x4x5RHSZ001-10-1x1x2x510-52001-310002-11411检验数转轴元Z001-10-1x1x2x510-52001-310002-11411Z000-0.5-0.5-1.5x1x2x3100-0.52.5010-0.51.5001-0.50.56.52.50.5最优解：x*=(6.5,2.5,0.5,0,0)T最优值：z*=-1.5例2：解LP问题4单纯形表Z012000x1x2x3100-0.52.5010-0.51.5001-0.50.56.52.50.5x1x2x3x4x5Z0001.5-2.5-3.5x1x2x3100-0.52.5010-0.51.5001-0.50.56.52.50.5此问题无界RHS例3：解LP问题4单纯形表Z0000-118x1x4x2101000031-101-3/201/2463x1x2x3x4x5Z0000-118x1x3x2100-1/31/30011/3-1/30101/20226此问题有多解。RHS§2.4初始解（两阶段法）问题：线性规划问题化为标准型时，若约束条件的系数矩阵中不存在单位矩阵，如何构造初始可行基？

§2.4初始解（两阶段法）第一阶段：加入人工变量,构造初始可行基.用单纯形法求解,若g=0,进入第二阶段,否则,原问题无可行解。第二阶段：去掉人工变量，还原目标函数系数，做出初始单纯形表。例：求解下列线性规划问题将原问题化成标准型：解:化标准型用两阶段方法来求解。第一阶段的线性规划问题为x1x2x3x4x5x6x7

g00000-1-10X4X6X71111000-21-10-1100310001419RHSx1x2x3x4x5x6x7RHSg-2400-10010X4X6X71111000-21-10-1100310001419

g60403-406X4X2X730211-10-21-10-11060403-31316g00000-1-10X4X2X10001-1/21/2-1/2011/30001/3102/301/2-1/21/6031x1x2x3x4x5x6x7

RHS得原问题的基可行解X=(1,3,0,0,0,)T。第二阶段：将上表中的人工变量去除，目标函数换成原问题的目标函数从上表的最后一个单纯形表出发，继续计算。Z-301000X4X2X10001-1/2011/300102/301/2031x1x2x3x4x5RHSZ00303/23X4X2X10001-1/2011/300102/301/2031Z-9/2000-3/4-3/2X4X2X30001-1/2-1/2100-1/43/20103/405/23/2x1x2x3x4x5RHS得原标准线性规划问题的最优解X=（0，5/2，3/2，0，0）T，最优值是-3/2。所以最初的线性规划问题的最优解X=（0，5/2，3/2）T，最优值是3/2。例：求解下列线性规划问题将原问题化成标准型：解:化标准型用两阶段方法来求解。第一阶段的线性规划问题为x1x2x3x4x5x6RHS

g0000-1-10X5X6X431001043-1001120100363x1x2x3x4x5x6RHS

g74-10009X5X6X431001043-1001120100363g05/3-10-7/302X1X6X411/3001/3005/3-10-4/3105/301-1/30122x1x2x3x4x5x6RHS

g05/3-10-7/302X1X6X411/3001/3005/3-10-4/3105/301-1/30122g00-1-1-200X1X6X2100-1/52/5000-1-1-110103/5-1/503/506/5g00-1-1-200X1X6X2100-1/52/5000-1-1-110103/5-1/503/506/5x1x2x3x4x5x6RHS

g0000-1-10X1X3X2100-1/52/5000111-10103/5-1/503/506/5第二阶段：将上表中的人工变量去除，目标函数换成原问题的目标函数从上表的最后一个单纯形表出发，继续计算。z-4-1000X1X3X2100-1/500110103/53/506/5x1x2x3x4

RHS

z000-1/518/5X1X3X2100-1/500110103/53/506/5所以最初的线性规划问题的最优解X=(3/5，6/5)T，最优值是18/5。例：求解下列线性规划问题将原问题化成标准型：解:化标准型用两阶段方法来求解。第一阶段的线性规划问题为x1x2x3x4x5x6RHS

g0000-1-10X5X62-3-1010-110-10123x1x2x3x4x5x6RHS

g1-2-1-1005X5X62-3-1010-110-10123g0-1/2-1/2-1-1/204X1X61-3/2-1/201/200-1/2-1/2-11/2114原问题无解。两阶段方法总结第一阶段结束时，辅助问题目标函数值大于0，原问题无解；第一阶段结束时，辅助问题目标函数值等于0，且人工变量都是非基变量，那末，所得基本可行解为原问题初始基本可行解，去掉人工变量，目标函数行换为原问题目标函数，继续求解。第一阶段结束时，辅助问题目标函数值等于0，但是人工变量不都是非基变量，那么令其强行出基，然后继续求解。小结线性规划问题图解法只有两个变量约束矩阵A中含有一个m阶的单位矩阵右端向量非负单纯形方法约束矩阵A中没有一个m阶的单位矩阵两阶段法§2.5对偶性及对偶单纯形方法对偶问题的提出原问题与对偶问题的数学模型原问题与对偶问题的关系对偶单纯形法1对偶问题的提出例：某家电厂生产两种产品，有关数据如下表：设备A设备B调试工序售价（元）0612521115245产品Ⅰ产品Ⅱ资源如何安排生产，使获利最多？厂家1对偶问题的提出设备A设备B调试工序售价（元）0612521115245产品Ⅰ产品Ⅱ资源收购

付出代价最小，且对方能接受。出让代价应不低于用同等数量的资源自己生产的收益。1对偶问题的提出收购厂家一对对偶问题2原问题与对偶问题的数学模型其它形式的对偶?2原问题与对偶问题的数学模型原问题（P）对偶问题（D）例写出线性规划问题的对偶问题：2原问题与对偶问题的数学模型3原问题与对偶问题的关系收购厂家一对对偶问题3原问题与对偶问题的关系z000-1/4-1/2-17/2x3x1x20015/4-15/21001/4-1/2010-1/43/215/27/23/2y-15/200-7/2-3/217/2w2w3-5/410-1/41/415/2011/2-3/21/41/23原问题与对偶问题的关系原问题与对偶问题在某种意义上来说，实质上是一样的，因为第二个问题仅仅在第一个问题的另一种表达而已。理论证明：原问题与对偶问题解的关系3原问题与对偶问题的关系定理对偶的对偶为原始问题。（对称性）3原问题与对偶问题的关系定理弱对偶定理（弱对偶性）：设和分别是问题（P）和（D）的可行解，则必有3原问题与对偶问题的关系定理如果一个LP问题有最优解，则它的对偶问题也有最优解，且它们的最优值相等。（强对偶定理）推论（最优性判别定理）原始问题和对偶问题的可行解x,w分别是最优解的充要条件是cTx=wTb。无界（对偶）无可行解（原始）3原问题与对偶问题的关系3原问题与对偶问题的关系显然，这两个问题都无可行解。综上所述，一对对偶问题的关系，只能有下面三种情况之一出现：都有最优解，分别设为X*和Y*，则必有CTX*=bTY*；一个问题无界，则另一个问题无可行解；两个都无可行解。3原问题与对偶问题的关系定理原始LP与其对偶必为下面三种情况之一出现PD有最优解问题无界无可行解有最优解(1)

问题无界

(3)无可行解(3)(2)3原问题与对偶问题的关系定理设x和w分别是原始问题和对偶问题的可行解，则它们是原始问题和对偶问题的最优解的充要条件是对一切i=1,2,…,m和一切的j=1,2,…,n有3原问题与对偶问题的关系4对偶单纯形方法基本思路对偶单纯形方法计算步骤4对偶单纯形方法（基本思路）对偶单纯形法是求解线性规划的另一种基本方法。它是根据对偶原理和单纯形法的原理而设计出来的，因此称为对偶单纯形法。不要简单理解为是求解对偶问题的单纯形法。4对偶单纯形方法（计算步骤）例：解：将原问题化成标准形：0-6-110-2-15-24-5004对偶单纯形方法（计算步骤）z

2-5-2-101-1x4x5x1x2x3x4x5RHS4对偶单纯形方法（计算步骤）z-15-24-5002x4x50-6-110-5-2-101-2-1z

x5

011/6-1/601/3-50-2/3-1/31-1/3x2-150-1-4010x1x2x3x4x5RHS4对偶单纯形方法（计算步骤）z-150-1-4010x2x5011/6-1/60-50-2/3-1/31

1/3-1/3z-15/200-7/2-3/221/2x2x3-5/410-1/41/415/2011/2-3/2

1/41/2x1x2x3x4x5RHS§2.6灵敏度分析灵敏度分析概念如何进行灵敏度分析价值向量的灵敏度分析右端向量的灵敏度分析

Cj——市场条件aij——工艺技术条件bi——根据资源投入后能产生经济效果来决定的一种决策选择灵敏度分析是指对系统或事物因周围条件变化显示出来的敏感程度的分析。1灵敏度分析概念灵敏度分析解决什么问题？当线性规划问题的参数aij，bi，cj中一个或几个发生改变时，线性规划问题最优解变化的分析；或上述参数在多大范围内变化时，线性规划问题最优解不变的分析。1灵敏度分析概念2如何进行灵敏度分析1、根据改变后的参数生成新的问题，用单纯形法从头计算，看最优解是否改变；2、将改变后的参数直接反映到原线性规划问题的最终单纯形表中，看最优解是否改变。（采用此方法）2如何进行灵敏度分析3价值向量的灵敏度分析例线性规划最优单纯形表：z0-1/20-11/4-9/431/4x3x10-1/21-1/41/41201/2-3/2

1/41/2x1x2x3x4x5RHS1、若c2=1，求新的最优解；若c3=5，求新的最优解。2、确定x1的系数c1的变化范围，使原最优解保持最优。3价值向量的灵敏度分析z-5-1-21000x3x10-1/21-1/41/41201/2-3/2

1/41/2x1x2x3x4x5RHSz0-3/20-11/4-9/431/4x3x10-1/21-1/41/41