物流运筹学单纯形法.ppt

物流运筹学,第一章：线性规划模型及单纯形法,第五节：单纯形法,1.5.1单纯形法原理,1.5.2单纯形法计算步骤,学习要求：理解单纯形法的原理，会用单纯形法求解线性规划问题。,1.5.1单纯形法原理,单纯形法原理,顶点的转移： 单纯形法的每一步的可行解对应着图解法可行域中的一个顶点。 即从可行域的一个顶点（基本可行解）开始，转移到另一个顶点（另一个基本可行解）的迭代过程，转移的条件是使目标函数值得到改善（逐步变优），当目标函数达到最优值时，问题也就得到了最优解。,需要解决的问题： (1)为了使目标函数逐步变优，怎么转移？ (2)目标函数何时达到最优？判断标准是什么？,1.5.1单纯形法原理,单纯形法步骤,确定初始基本可行解,检验其 是否为最优,寻找更好的 基本可行解,停,否,是,主要工作： 最优性检验,主要工作： 1、基变换（将原来的基换成新的基） 2、修正单纯形表，得到新的基本可行解,1、首先引入松弛变量或剩余变量使线性规划模型化为标准形式，且标准形式的系数矩阵中含有一个单位矩阵。（ “”型约束添加松弛变量， “”约束添加剩余变量变为等式约束 ）。,1.5.2单纯形法计算步骤,单纯形法步骤,2、确定初始基和初始基本可行解。写出基本可行解和目标函数值。,3、最优性检验 （1）计算机会成本行 （2）计算检验数行 j （3）最优性检验：但所有检验数小于等于0时，得到最优解，计算结束。否则，转入下一步。,4、基变换 （1） 用j确定进基列向量和进基变量。 （2）用规则确定出基列向量及出基变量。,5、修正单纯形表。,问题1:某工厂计划生产甲、乙两种产品， 生产1kg的甲需耗煤9t、 电力4kw.h、 油3t； 生产1kg的乙需耗煤4t、 电力5kw.h、 油10t； 该厂现有煤360t、电力200kw.h、油300t。 已知甲产品每千克的售价为7万元、乙产品每千克的售价为12万元。 在上述条件下决定生产方案，使得总收入最大，具体数据如表所示：,1.5.2单纯形法计算步骤,约束条件,目标函数,此问题的线性规划模型：,非标准形式,标准形式,1.5.2单纯形法计算步骤,第一步：引入松弛变量化为标准型。,初始基,初始基本可行解,1.5.2单纯形法计算步骤,第二步：编制初始单纯形表并确定初始可行基、初始基本可行解。,A =,为了求解初始基本可行解的方便，选择单位矩阵为初始基。,1.5.2单纯形法计算步骤,第二步：编制初始单纯形表并确定初始可行基、初始基本可行解。,基变量,基变量的价值系数,机会成本行 （这一行可以省略）,价值系数 （目标函数中决策变量的系数）,检验数行 作用：检验当前可行解是否最优； 如果不是最优解，确定入基变量。,初始基本 可行解,在以上基本可行解中，,即：甲、乙各生产0件。,总的收入为：,这个基本可行解显然不是最优解，从目标函数来考虑，还可以通过增加甲、乙的产量，来增加总收入。 下面介绍：如何检验现有基本可行解是否为最优解。,基本可行解,1.5.2单纯形法计算步骤,第三步：最优性检验，确定当前基本可行解是否是最优解。（ j 检验数的计算）如果所有的检验数都小于等于0，则当前解为最优解。,基变量,基变量的价值系数,基本 可行解,因为基变量的检验数1和2都大于0，所以当前解不是最优。需要变换可行基，寻找新的解。即原来的非基变量x1 、x2，要有一个被换为基变量，基变量中也要有一个被换为非基变量，以确定新的基、新的解。,1.5.2单纯形法计算步骤,第四步：基变换 （1）如果经过检验不是最优解，确定如何换基，首先确定由哪个非基变量作为进基变量检验数j中最大的正数对应的非基变量作为进基变量。 （2）用检验数确定出基变量。检验数中最小的正数对应的基变量作为出基变量。,主元列 （确定入基变量）,主元行 （确定出基变量）,主元素,检验数（用来确定出基变量）,现分析，确定x1和 x2谁入基，因为x2的系数最大，即单位收入最高，自然先考虑增加乙的产量，固确定x2为入基变量。,如何确定入基变量 （可以按照下述方法来理解）,当x2定为入基变量后，必须从x3 、 x4 、 x5中换出来一个，并保证其余的变量在新可行解中还都是非负，即： x30 、 x4 0 、 x5 0,如何确定出基变量（可以按照下述方法来理解）,因为x1 仍为基变量，所以将x1=0，带入约束条件，得到：,只能选x5 作为出基变量，令x5 =0，请思考为什么？,因为：如果选取x3 或x4 作为出基变量，则会出现有的变量为负值。,第五步： 进行矩阵的初等变换，修正单纯形表继续进行最优性检验计算。,X(1)=0, 30, 240, 50, 0T,X(0)=0, 0, 360, 200,300T,Z(1)=360,Z(0)=0,B(1)=P3, P4, P2,B(0)=P3, P4, P5,初等变换过程： 第行除以10，变为； 乘上-5，加上第行，变为； 乘上-4，加上第行，变为。,因为10，所以当前解仍不是最优解。需要继续进行基变换。,1.5.2单纯形法计算步骤,第五步： 进行矩阵的初等变换，修正单纯形表继续进行最优性检验计算。,”,”,”,X(1)=0, 30, 240, 50, 0T,X(2)=20, 24, 84, 0, 0T,X(0)=0, 0, 360, 200,300T,Z(1)=360,Z(2)=428,Z(0)=0,B(1)=P3, P4, P2,B(2)=P3, P1, P2,B(0)=P3, P4, P5,1.5.2单纯形法计算步骤,第六步：得到最优解，及目标函数最优值，写出结果。,最优解为：X(2)=20, 24, 84, 0, 0T,目标函数最优值为：Z(2)=428,即最优生产计划为：甲生产20件，乙生产24件，最大收入为：428万元。,在最后的单纯形表中，所有非基变量的检验数j 0，可以判断已得到最优解，此表即为最终单纯形表，对应的基P3，P1，P2为最优基。,练习题,X(0)=0, 0, 15, 24, 5T