物流运筹学物流运筹学第一章：线性规划模型及单纯形法第一章：线性规划模型及单纯形法第五节：单纯形法第五节：单纯形法本次课学习任务：本次课学习任务： 1.5.11.5.1单纯形法原理单纯形法原理 1.5.21.5.2单纯形法计算步骤单纯形法计算步骤学习要求：理解单纯形法的原理，会用单纯形法求解线性规划问题。学习要求：理解单纯形法的原理，会用单纯形法求解线性规划问题。1.5.11.5.1单纯形法原理单纯形法原理单纯形法原理顶点的转移：顶点的转移： 单纯形法的每一步的可行解对应着图解法可行域中的一个顶单纯形法的每一步的可行解对应着图解法可行域中的一个顶点。点。即从可行域的一个顶点（基本可行解）开始，转移到另一个顶点即从可行域的一个顶点（基本可行解）开始，转移到另一个顶点（另一个基本可行解）的迭代过程，（另一个基本可行解）的迭代过程，转移的条件转移的条件是使目标函数值是使目标函数值得到改善（逐步变优），当目标函数达到最优值时，问题也就得得到改善（逐步变优），当目标函数达到最优值时，问题也就得到了最优解。到了最优解。需要解决的问题：需要解决的问题： (1)为了使目标函数逐步变优，怎么转移？为了使目标函数逐步变优，怎么转移？ (2)目标函数何时达到最优？判断标准是什么？目标函数何时达到最优？判断标准是什么？ 1.5.11.5.1单纯形法原理单纯形法原理单纯形法步骤确定初始基本可行解确定初始基本可行解检验其检验其是否为最优是否为最优寻找更好的寻找更好的基本可行解基本可行解停否否是是主要工作：主要工作：最优性检验最优性检验主要工作：主要工作：1、基变换（将原来的基换成新的基）、基变换（将原来的基换成新的基）2、修正单纯形表，得到新的基本可行解、修正单纯形表，得到新的基本可行解1、首先引入松弛变量或剩余变量使线性规划模型化为标准形式，且标准形式的系数、首先引入松弛变量或剩余变量使线性规划模型化为标准形式，且标准形式的系数矩阵中含有一个单位矩阵。（矩阵中含有一个单位矩阵。（ “”型约束添加松弛变量，型约束添加松弛变量， “”约束添加剩余变量变为约束添加剩余变量变为等式约束等式约束 ）。）。1.5.21.5.2单纯形法计算步骤单纯形法计算步骤单纯形法步骤2、确定初始基和初始基本可行解。写出基本可行解和目标函数值。、确定初始基和初始基本可行解。写出基本可行解和目标函数值。3、最优性检验、最优性检验（1）计算机会成本行）计算机会成本行 （2）计算检验数行）计算检验数行 j（3）最优性检验：但所有检验数小于等于）最优性检验：但所有检验数小于等于0时，得到最优解，计算结束。否则，转入时，得到最优解，计算结束。否则，转入下一步。下一步。4、基变换、基变换 （1） 用用j确定进基列向量和进基变量。确定进基列向量和进基变量。 （2）用）用规则确定出基列向量及出基变量。规则确定出基列向量及出基变量。5、修正单纯形表。、修正单纯形表。资源资源 产品产品单耗单耗资源资源甲甲 乙乙资源限量资源限量煤煤(t)电电(kw.h)油油(t)9 44 5 3 10360200300单位产品价格单位产品价格 7 12问题问题1 1: :某工厂计划生产甲、乙两种产品，某工厂计划生产甲、乙两种产品， 生产生产1kg1kg的甲需耗煤的甲需耗煤9t9t、 电力电力4kw.h4kw.h、 油油3t3t； 生产生产1kg1kg的乙需耗煤的乙需耗煤4t4t、 电力电力5kw.h5kw.h、 油油10t10t； 该厂现有煤该厂现有煤360t360t、电力、电力200kw.h200kw.h、油、油300t300t。 已知甲产品每千克的售价为已知甲产品每千克的售价为7 7万元、乙产品每千克的售价为万元、乙产品每千克的售价为1212万元。万元。 在上述条件下决定生产方案，使得总收入最大，具体数据如表所在上述条件下决定生产方案，使得总收入最大，具体数据如表所示示：1.5.21.5.2单纯形法计算步骤单纯形法计算步骤约束约束条件条件目标目标函数函数此问题的线性规划模型：此问题的线性规划模型：非标准形式非标准形式标准形式标准形式1.5.21.5.2单纯形法计算步骤单纯形法计算步骤第一步：引入松弛变量化为标准型。第一步：引入松弛变量化为标准型。基基非非基基向向量量矩矩阵阵基基本本解、解、基基本本可可行行解解基基变变量量非非基基变变量量初始基初始基初始基本初始基本可行解可行解1.5.21.5.2单纯形法计算步骤单纯形法计算步骤第二步：编制初始单纯形表并确定初始可行基、初始基本可行解。第二步：编制初始单纯形表并确定初始可行基、初始基本可行解。9410045010310001A =为了求解初始基本可行解的方为了求解初始基本可行解的方便，选择单位矩阵为初始基。便，选择单位矩阵为初始基。1.5.21.5.2单纯形法计算步骤单纯形法计算步骤第二步：编制初始单纯形表并确定初始可行基、初始基本可行解。第二步：编制初始单纯形表并确定初始可行基、初始基本可行解。CBXBB-1b712000X1X2X3X4X50X3360941000X4200450100X5300310001CB B-1Pj00000j = cj-CB B-1Pj712000基变量基变量基变量的基变量的价值系数价值系数机会成本行机会成本行（这一行可以省（这一行可以省略）略）价值系数价值系数（目标函数中决策变（目标函数中决策变量的系数）量的系数）检验数行检验数行作用：检验当前可行解是否最优；作用：检验当前可行解是否最优；如果不是最优解，确定如果不是最优解，确定入基变量入基变量。初始基本初始基本 可可行解行解在以上基本可行解中，在以上基本可行解中，即：甲、乙各生产即：甲、乙各生产0件。件。总的收入为：总的收入为：这个基本可行解显然不是最优解，从目标函这个基本可行解显然不是最优解，从目标函数来考虑，还可以通过增加甲、乙的产量，数来考虑，还可以通过增加甲、乙的产量，来增加总收入。来增加总收入。下面介绍：如何检验现有基本可行解是否为下面介绍：如何检验现有基本可行解是否为最优解。最优解。CBXBB-1b712000X1X2X3X4X50X3360941000X4200450100X5300310001基本可行解1.5.21.5.2单纯形法计算步骤单纯形法计算步骤第三步：最优性检验，确定当前基本可行解是否是最优解。（第三步：最优性检验，确定当前基本可行解是否是最优解。（ j 检验数的检验数的计算）计算）如果所有的检验数都小于等于如果所有的检验数都小于等于0，则当前解为最优解。，则当前解为最优解。CBXBB-1b712000X1X2X3X4X50X336094100900X420045010400X530031000130机会成本行机会成本行00000j 712000基变量基变量基变量的基变量的价值系数价值系数基本基本 可行解可行解因为基变量的检验数因为基变量的检验数1和和2都大于都大于0，所以当前解不是最优。需要变换可行基，所以当前解不是最优。需要变换可行基，寻找新的解。即原来的非基变量寻找新的解。即原来的非基变量x1 、x2，要有一个被换为基变量，基变量中，要有一个被换为基变量，基变量中也要有一个被换为非基变量，以确定新的基、新的解。也要有一个被换为非基变量，以确定新的基、新的解。1.5.21.5.2单纯形法计算步骤单纯形法计算步骤第四步：基变换第四步：基变换（1）如果经过检验不是最优解，确定如何换基，首先确定由哪个非基变量作为）如果经过检验不是最优解，确定如何换基，首先确定由哪个非基变量作为进基变量进基变量检验数检验数j中最大的正数对应的非基变量作为进基变量中最大的正数对应的非基变量作为进基变量。（2）用）用检验数确定出基变量。检验数确定出基变量。检验数中最小的正数对应的基变量作为出检验数中最小的正数对应的基变量作为出基变量。基变量。CBXBB-1b712000X1X2X3X4X50X3360941001 =360/4=900X4200450102 =200/5=40 0X5300310 001 3 =300/10=30CB B-1Pj00000Z=j = cj-CB B-1Pj712 000主元列主元列（确定入基变量）（确定入基变量）主元行主元行（确定（确定出基变出基变量）量）主元素主元素检验数（用来检验数（用来确定出基变量）确定出基变量）现分析，确定现分析，确定x1和和 x2谁入基，因为谁入基，因为x2的系数最大，即单位收入的系数最大，即单位收入最高，自然先考虑增加乙的产量，固确定最高，自然先考虑增加乙的产量，固确定x2为入基变量。为入基变量。如何确定入基变量如何确定入基变量（可以按照下述方法来理解）（可以按照下述方法来理解）当当x2定为入基变量后，必须从定为入基变量后，必须从x3 、 x4 、 x5中换出来一个，并保中换出来一个，并保证其余的变量在新可行解中还都是非负，即：证其余的变量在新可行解中还都是非负，即： x30 、 x4 0 、 x5 0 如何确定出基变量（可以按照下述方法来理解）如何确定出基变量（可以按照下述方法来理解）因为因为x1 仍为基变量，仍为基变量，所以将所以将x1=0，带入约，带入约束条件，得到：束条件，得到：只能选只能选x5 作为出基变作为出基变量，令量，令x5 =0，请思考，请思考为什么？为什么？因为：如果选取因为：如果选取x3 或或x4 作为出基变量，则会出作为出基变量，则会出现有的变量为负值。现有的变量为负值。第五步：第五步： 进行矩阵的初等变换，修正单纯形表继续进行最优性检验计算。进行矩阵的初等变换，修正单纯形表继续进行最优性检验计算。CBXBB-1b712000X1X2X3X4X50X336094100900X420045010400X5300310 00130 检验数检验数j712 0000X32407.8010-0.430.80X4502.5001-0.520 12X2300.31000.1100检验数检验数j3.4 000-1.2X(1)=0, 30, 240, 50, 0TX(0)=0, 0, 360, 200,300TZ(1)=360Z(0)=0B(1)=P3, P4, P2B(0)=P3, P4, P5初等变换过程：初等变换过程：第第行除以行除以10，变为，变为；乘上乘上-5，加上第，加上第行，变为行，变为；乘上乘上-4，加上第，加上第行，变为行，变为。因为因为10，所以当前解所以当前解仍不是最优解。需要继仍不是最优解。需要继续进行基变换。续进行基变换。1.5.21.5.2单纯形法计算步骤单纯形法计算步骤第五步：第五步： 进行矩阵的初等变换，修正单纯形表继续进行最优性检验计算。进行矩阵的初等变换，修正单纯形表继续进行最优性检验计算。CBXBB-1b712000X1X2X3X4X50X336094100900X420045010400X5300310 00130 机会成本（此行可省略）机会成本（此行可省略）00000检验数检验数j712 0000X32407.8010-0.430.80X4502.5001-0.520 12X2300.31000.1100机会成本（此行可省略）机会成本（此行可省略）3.612001.2检验数检验数j3.4 000-1.20X384001-3.121.167X1201000.4-0.212X224010-0.120.16机会成本（此行可省略）机会成本（此行可省略）0001.360.52检验数检验数j000-1.36-0.52”X(1)=0, 30, 240, 50, 0TX(2)=20, 24, 84, 0, 0TX(0)=0, 0, 360, 200,300TZ(1)=360Z(2)=428Z(0)=0B(1)=P3, P4, P2B(2)=P3, P1, P2B(0)=P3, P4, P51.5.21.5.2单纯形法计算步骤单纯形法计算步骤第六步：得到最优解，及目标函数最优值，写出结果。第六步：得到最优解，及目标函数最优值，写出结果。最优解为：最优解为：X(2)=20, 24, 84, 0, 0T目标函数最优值为：目标函数最优值为：Z(2)=428即最优生产计划为：甲生产即最优生产计划为：甲生产20件，乙生产件，乙生产24件，最大收入为：件，最大收入为：428万元。万元。在最后的单纯形表中，所有非基变量的检验数在最后的单纯形表中，所有非基变量的检验数j 0，可以可以判断已得到最优解，此表即为最终单纯形表，对应的基判断已得到最优解，此表即为最终单纯形表，对应的基P3，P1，P2为最优基。为最优基。练习题练习题21000CB基基bx1x2x3x4x50x315051000x424620100x5511001Zj00000j=Cj-Zj210000x315051002x1411/301/600x5102/30-1/61Zj22/301/30j=Cj-Zj01/30-1/300x315/20015/4 -15/22x17/21001/4-1/21x23/2010-1/43/2Zj2101/41/2j =Cj-Zj000-1/4 -1/2453123/2X(0)=0, 0, 15, 24, 5TX(1)=4, 0, 15, 0, 1TX(2)=7/2, 3/2, 15/2, 0, 0TZ(0)=0Z(1)=8Z(2)=8.5B(0)=P3, P4, P5B(1)=P3, P1, P5B(2)=P3, P1, P2”练习题练习题