物流运筹学单纯形法

《物流运筹学单纯形法》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、物流运筹学第一章：线性规划模型及单纯形法第五节：单纯形法本次课学习任务：1.5.1单纯形法原理1.5.2单纯形法计算步骤学习要求：理解单纯形法的原理，会用单纯形法求解线性规划问题。1.5.1单纯形法原理单纯形法原理顶点的转移：——单纯形法的每一步的可行解对应着图解法可行域中的一个顶点。即从可行域的一个顶点（基本可行解）开始，转移到另一个顶点（另一个基本可行解）的迭代过程，转移的条件是使目标函数值得到改善（逐步变优），当目标函数达到最优值时，问题也就得到了最优解。需要解决的问题：(1)为了使目标函

2、数逐步变优，怎么转移？(2)目标函数何时达到最优？判断标准是什么？1.5.1单纯形法原理单纯形法步骤确定初始基本可行解检验其是否为最优寻找更好的基本可行解停否是主要工作：最优性检验主要工作：1、基变换（将原来的基换成新的基）2、修正单纯形表，得到新的基本可行解1、首先引入松弛变量或剩余变量使线性规划模型化为标准形式，且标准形式的系数矩阵中含有一个单位矩阵。（“≤”型约束添加松弛变量，“≥”约束添加剩余变量变为等式约束）。1.5.2单纯形法计算步骤单纯形法步骤2、确定初始基和初始基本可行解。写出基

3、本可行解和目标函数值。3、最优性检验（1）计算机会成本行（2）计算检验数行σj（3）最优性检验：但所有检验数小于等于0时，得到最优解，计算结束。否则，转入下一步。4、基变换（1）用σj确定进基列向量和进基变量。（2）用θ规则确定出基列向量及出基变量。5、修正单纯形表。资源产品单耗资源甲乙资源限量煤(t)电(kw.h)油(t)9445310360200300单位产品价格712问题1:某工厂计划生产甲、乙两种产品，生产1kg的甲需耗煤9t、电力4kw.h、油3t；生产1kg的乙需耗煤4t、电力5

4、kw.h、油10t；该厂现有煤360t、电力200kw.h、油300t。已知甲产品每千克的售价为7万元、乙产品每千克的售价为12万元。在上述条件下决定生产方案，使得总收入最大，具体数据如表所示：1.5.2单纯形法计算步骤约束条件目标函数此问题的线性规划模型：非标准形式标准形式1.5.2单纯形法计算步骤第一步：引入松弛变量化为标准型。基非基向量矩阵基本解、基本可行解基变量非基变量初始基初始基本可行解1.5.2单纯形法计算步骤第二步：编制初始单纯形表并确定初始可行基、初始基本可行解。94100450

5、10310001A=为了求解初始基本可行解的方便，选择单位矩阵为初始基。1.5.2单纯形法计算步骤第二步：编制初始单纯形表并确定初始可行基、初始基本可行解。CBXBB-1b712000X1X2X3X4X50X3360941000X4200450100X5300310001CBB-1Pj00000σj=cj-CBB-1Pj712000基变量基变量的价值系数机会成本行（这一行可以省略）价值系数（目标函数中决策变量的系数）检验数行作用：检验当前可行解是否最优；如果不是最优解，确定入基变量。初始基本可行

6、解在以上基本可行解中，即：甲、乙各生产0件。总的收入为：这个基本可行解显然不是最优解，从目标函数来考虑，还可以通过增加甲、乙的产量，来增加总收入。下面介绍：如何检验现有基本可行解是否为最优解。CBXBB-1b712000X1X2X3X4X50X3360941000X4200450100X5300310001基本可行解1.5.2单纯形法计算步骤第三步：最优性检验，确定当前基本可行解是否是最优解。（σj检验数的计算）——如果所有的检验数都小于等于0，则当前解为最优解。CBXBB-1b712000θX

7、1X2X3X4X50X336094100900X420045010400X530031000130机会成本行00000σj712000基变量基变量的价值系数基本可行解因为基变量的检验数σ1和σ2都大于0，所以当前解不是最优。需要变换可行基，寻找新的解。即原来的非基变量x1、x2，要有一个被换为基变量，基变量中也要有一个被换为非基变量，以确定新的基、新的解。1.5.2单纯形法计算步骤第四步：基变换（1）如果经过检验不是最优解，确定如何换基，首先确定由哪个非基变量作为进基变量——检验数σj中最大的正

8、数对应的非基变量作为进基变量。（2）用θ检验数确定出基变量。——θ检验数中最小的正数对应的基变量作为出基变量。CBXBB-1b712000X1X2X3X4X50X336094100θ1=360/4=900X420045010θ2=200/5=400X5300310★001★θ3=300/10=30CBB-1Pj00000Z=σj=cj-CBB-1Pj712★000主元列（确定入基变量）主元行（确定出基变量）主元素θ检验数（用来确定出基变量）现分析，确定x1和x2谁入基，因为x2的系数最大，即单位