《物流运筹方法与工具》课件-模块三 物流资源配置规划

物流运筹方法与工具（第3版）目录

CONTENTS物流运筹方法与工具概述物流决策分析物流资源配置规划物流任务指派运输方案优化运输路径规划物流项目计划技术物流需求预测库存水平控制模块三模块二模块四模块五模块六模块七模块八模块九模块一模块三物流资源配置规划资源配置规划概述线性规划模型及求解图解法单纯形法应用举例单元一单元三单元五单元四单元二知识点1．知道线性规划问题的基本概念及其数学模型的形式。2．掌握线性规划模型的建立方法及应注意的问题。3．理解线性规划图解法的基本原理。4．掌握图解法求解线性规划模型的基本方法。5．理解单纯形法求解线性规划问题的基本原理。6．掌握单纯形法求解线性规划模型的基本方法。本单元知识点能力点、素质点能力点：能够对一些相对简单的物流资源配置问题建立线性规划模型。能够运用线性规划模型解决一些简单的物流资源优化配置问题。素质点：拥有资源节约意识和可持续发展观。拥有全局观念和大局意识。引导案例物流网络结构布局方案的确定引导案例物流网络结构布局方案的确定单元一物流资源配置规划概述一、资源配置规划的含义二、线性规划的含义及应用资源配置规划的目的：资源配置规划的含义：一、资源配置规划的含义规划的目的，就是在现有的人力、物力和财力等资源条件下，如何合理地加以利用和调配，使我们在实现预期目标的过程中，耗费的资源最少，获得的收益最大。资源配置规划是指使用某种数学方法使有效资源的运用达到最优化。它是运筹学的一个重要分支，在运筹学中称之为规划论。二、线性规划的含义及应用线性规划是运筹学中一个重要分支。其研究内容，总起来说是解决资源合理利用和资源合理调配问题。它涉及到两个方面的具体问题：这方面的问题涉及到系统的投入和求极小值问题。（1）计划任务确定，如何统筹安排，精心策划，用最少的资源来实现这个任务。（2）资源的数量确定，如何合理利用，合理调度，使得完成的任务最大。这方面的问题涉及到系统的产出和求最大值问题。二、线性规划的含义及应用特点线性规划的基本特点是模型中的线性函数。含义线性规划是一种合理利用资源、合理调配资源的应用数学方法。二、线性规划的含义及应用例3-1

某工厂在计划期内安排生产甲、乙两种产品，已知生产单位产品所需的设备台时及A、B两种原材料的消耗情况如表3-1所示，同时已知该厂每生产一件甲产品可获利2元，每生产一件乙产品可获利3元，问应如何安排生产计划，才能使该厂获利最多？表3-1甲、乙产品资料甲乙设备128台时原材料A4016kg原材料B0412kg单元二

线性规划模型及求解一、线性规划的模型结构1．变量。变量是指实际系统或决策问题中有待确定的未知因素，也是指系统中的可控因素，又称决策变量。2．目标函数。线性规划模型的目标是求系统目标的极值，是一个极值问题，即极大值或极小值。3．约束条件。约束条件是指实现目标的限制因素。4．线性规划的变量应为正值。单元二

线性规划模型及求解二、线性规划模型的数学表达式单元二

线性规划模型及求解三、线性规划建模的步骤（一）设置决策变量如x1，x2，x3，┄来表示。（二）建立目标函数最大化（max）或最小化（min）。（三）列出约束条件需要满足的基本条件，即约束方程。（四）设立非负限制单元二

线性规划模型及求解三、线性规划建模的步骤例3-3

某物流生产车间生产甲、乙两种产品，每件产品都要经过两道工序，即在设备A和设备B上加工，但两种产品的单位利润却不相同。已知生产单位产品所需的设备台时、A和B两种设备在计划期的有效台时及单位产品的利润，见表3-2。问如何安排生产，所获利润最大？表3-2甲、乙产品资料甲乙设备有效台时设备A2324设备B3226单位产品利润4元/件3元/件单元二

线性规划模型及求解三、线性规划建模的步骤解：设x1、x2分别表示产品甲和乙的产量。根据问题所给的条件有以Z表示利润，则得一线性函数式单元二

线性规划模型及求解三、线性规划建模的步骤综上所述，本例的数学模型可归结为：

“s.t.”是“subjectto”的缩写，表示“在…约束条件之下”，单元二

线性规划模型及求解四、线性规划模型的求解1947年，美国数学家丹齐格（GeorgeBernardDantzig）在研究美国空军资源配置问题时，提出了求解线性规划问题的一般解法——单纯形法（SimplexMethod），从而为线性规划这门学科奠定了基础，使求解大规模决策问题成为可能。模块三物流资源配置规划资源配置规划概述线性规划模型及求解图解法单纯形法应用举例单元五单元四单元二单元一单元三知识点1．知道线性规划问题的基本概念及其数学模型的形式。2．掌握线性规划模型的建立方法及应注意的问题。3．理解线性规划图解法的基本原理。4．掌握图解法求解线性规划模型的基本方法。5．理解单纯形法求解线性规划问题的基本原理。6．掌握单纯形法求解线性规划模型的基本方法。本单元知识点能力点、素质点能力点：能够对一些相对简单的物流资源配置问题建立线性规划模型。能够运用线性规划模型解决一些简单的物流资源优化配置问题。素质点：拥有资源节约意识和可持续发展观。拥有全局观念和大局意识。单元三图解法一、图解法的基本步骤二、线性规划解的几种形式一、图解法的基本步骤图解法的基本思想是先将约束条件加以图解，求得满足约束条件的可行域，然后结合目标要求从可行域中求得最优解。一般步骤如下：第一步，建立直角坐标系。第二步，根据约束条件和非负条件画出可行域。第三步，作出目标函数等值线，确定使目标函数递增（减）的方向，然后结合目标要求平移等值线到可行域的最远点，即可求得该线性规划的最优解。例3-5用图解法求解线性规划问题一、图解法的基本步骤解：在x1ox2直角坐标平面上作直线一、图解法的基本步骤约束条件的每一个不等式都表示一个半平面，满足约束条件的点集是四个不等式所对应的四个半平面的公共部分，即图中三条直线及两条坐标轴的边界所围成的凸多边形OABCD的内部及边界。

满足所有约束条件的点称为可行点。

每一点代表该线性规划问题的一个可行方案，即一个可行解。

所有可行点的集合，是该问题的可行域.

使目标函数值达到最优值（最大值或最小值）的可行解，这种解称为最优可行解，简称最优解。一、图解法的基本步骤为寻找最优解，将目标函数写成：3x1+5x2=k，其中k为任意常数。当k为不同值时，此函数表示相互平行的等值线。

令k=0，先作通过原点的等值线l4：3x1+5x2=0它与可行域有交点。将这条直线沿目标函数增大的右上方平移，过顶点C时，Z在可行域中取最大值；如继续向右上方平移，则等值线将离开可行域。故C点坐标就是最优解。求l3和l2交点C坐标，得到x1=4，x2=6，这时最优值Z=42。一、图解法的基本步骤线性规划问题可能有以下四种结果。（一）唯一最优解如例题3-5，其可行域为凸多边形，只有一个最优点，且是顶点。（二）无穷多个最优解如例题3-6，其可行域为凸多边形，等值线与可行域的边界发生重合，边界上所有的点都是最优解。（三）无可行解如果约束条件中存在相互矛盾的约束条件，则导致可行域是空集，此时问题无可行解。（四）无有限最优解如果可行域无界，在可行域中找不到最大极值点，目标函数值可以增大到无穷大（或减少到无穷小），称这种情况为无有限最优解或无界解。二、线性规划解的几种形式例3-6用图解法求解下列线性规划问题二、线性规划解的几种形式解：在x1ox2直角坐标系中作直线：二、线性规划解的几种形式得可行域OABCD。当等值线向右上方平移到与边界线BC重合时，目标函数值最大。故边界BC上的所有点，包括两个端点B（8，3）和C（4，6）都是此问题的最优解，此时目标函数的最优值为：Z（8，3）=Z（4，6）=72二、线性规划解的几种形式例3-7

用图解法求解下列线性规划问题二、线性规划解的几种形式解：在x1ox2

直角坐标系中作直线，得可行域OABCD。二、线性规划解的几种形式当等值线向右上方平移到与边界线BC重合时，目标函数值最大。故边界BC上的所有点，包括两个端点B（8，3）和C（4，6）都是此问题的最优解，此时目标函数的最优值为：Z（8，3）=Z（4，6）=72二、线性规划解的几种形式例3-8

用图解法求解下列线性规划问题二、线性规划解的几种形式解：在x1ox2

直角坐标系中作直线二、线性规划解的几种形式因可行域无界，目标函数趋于无穷，该线性规划问题无有限最优解。模块三物流资源配置规划资源配置规划概述线性规划模型及求解图解法单纯形法应用举例单元五单元三单元二单元一单元四知识点1．知道线性规划问题的基本概念及其数学模型的形式。2．掌握线性规划模型的建立方法及应注意的问题。3．理解线性规划图解法的基本原理。4．掌握图解法求解线性规划模型的基本方法。5．理解单纯形法求解线性规划问题的基本原理。6．掌握单纯形法求解线性规划模型的基本方法。本单元知识点能力点、素质点能力点：能够对一些相对简单的物流资源配置问题建立线性规划模型。能够运用线性规划模型解决一些简单的物流资源优化配置问题。素质点：拥有资源节约意识和可持续发展观。拥有全局观念和大局意识。单元四单纯形法一、线性规划标准形式二、表格单纯形法的求解步骤一、线性规划标准形式（一）标准形式线性规划模型的标准形式要求：1．所有决策变量全大于或等于零；2．约束条件全为线性等式；3．约束条件右端的常数全部为非负；4．目标函数求最大值。一、线性规划标准形式线性规划模型的标准形式为：（二）一般形式化为标准形式的方法1．若所给问题是求目标函数的最小值（如成本、消耗），可用-1乘目标函数，化为求最大值；2．若约束条件有不等式时，可在不等式的左边加上或减去一个非负变量，使之成为等式。加入的变量叫松弛变量，减去的变量则叫剩余变量，它们在目标函数中系数为0；3．某变量没有非负限制，可采取新增加两个非负决策变量相减替代该变量的方式。4．转化为标准型的约束条件，在等号右边的取值要求是非负。若不是非负，则在等号两边同时乘以-1，将其变成非负。一、线性规划标准形式

例3-9

将线性规划问题化为标准形式maxZ=一、线性规划标准形式s.t.解：引入松弛变量x3、x4，可得标准形式：一、线性规划标准形式例3-12

用单纯形法求解线性规划问题二、表格单纯形法的求解步骤解：先引入松弛变量

，将问题化为标准形式：二、表格单纯形法的求解步骤将约束条件的增广矩阵和目标函数的系数填入表3-4中：二、表格单纯形法的求解步骤表3-4单纯形表基变量x1

x2

x3

x4bx3x4231032012426Z43000单纯形表中，约束条件的系数矩阵中出现一个m阶单矩阵，b列非负，Z行对应于单位矩阵的元素为0，这时其余的元素即为检验数。二、表格单纯形法的求解步骤最优解判定准则：当所有检验数非正时，这个解就是最优解，否则解仍可改善。由表3-4可看出，系数矩阵中已有2阶单位矩阵，其所在的列对应的变量x3，x4叫基变量，置于左列，x1，x2叫非基变量，令x1=0，x2=0，由标准形式等式可得x3=24，x4=26，于是得到一个基本可行解，记为X（0）=（0，0，24，26）T，这是初始可行解，其对应的目标函数值Z(0)=0二、表格单纯形法的求解步骤确定主元及离基变量，因

，故3为主元，其所在行为主元行，主元行对应的基变量x4为离基变量。先将x1转变为基变量，这时称之为进基变量，之后有一个基变量被换出，称为离基变量。变量调换完成之时，即可得到一个改善后的基本可行解。具体调换程序如下：确定x1为进基变量后，用最小比值法则二、表格单纯形法的求解步骤对主元行作初等变换，使主元变为1，得表3-6。表3-5单纯形表的迭代基变量x1

x2

x3

x4bx3x42310[3]2012426Z43000二、表格单纯形法的求解步骤作行初等变换，将主元列其余元素变为0，得表3-7。表3-6单纯形表的迭代基变量x1

x2

x3

x4bx3x4231012/301/32426/3Z43000二、表格单纯形法的求解步骤新基变量为x3，x1，令非基变量x2，x3为0，得一基本可行解：X(1)=(26/3，0，20/3，0)T，对应目标函数值Z(1)=104/3。观察表3-7中检验数，仍有正数1/3，故其所在列对应变量x2确定为进基变量。表3-7单纯形表的迭代基变量x1

x2

x3

x4bx3x105/31-2/312/301/320/326/3Z01/30-4/3-104/3二、表格单纯形法的求解步骤对主元行作初等变换，使主元变为1，得表3-9。表3-9单纯形表的迭代表3-8单纯形表的迭代基变量x1

x2

x3

x4bx3x10[5/3]1-2/312/301/320/326/3Z01/30-4/3-104/3基变量x1

x2

x3

x4bx3x1013/5-2/512/301/3426/3Z01/30-4/3-104/3二、表格单纯形法的求解步骤表3-10中检验数非正，得最优解：X(2)=(6，4，0，0)T，对应目标函数值Z(2)=36。它表示：甲产品生产6件，乙产品生产4件时，利润最大，最大利润为36元。作行初等变换，将主元列其余元素变为0，得表3-10。表3-10单纯形表基变量x1

x2

x3

x4bx2x1013/5-2/510-2/53/546Z00-1/5-6/5-36二、表格单纯形法的求解步骤上述求解过程可用表3-11综述之：表3-11单纯形表序号基变量x1

x2

x3

x4bⅠx3x42310[3]2012426Z43000Ⅱx3x10[5/3]1-2/312/301/320/326/3Z01/30-4/3-104/3Ⅲx2x1013/5-2/510-2/53/546Z00-1/5-6/5-36模块三物流资源配置规划资源配置规划概述线性规划模型及求解图解法单纯形法应用举例单元三单元四单元二单元一单元五知识点1．知道线性规划问题的基本概念及其数学模型的形式。2．掌握线性规划模型的建立方法及应注意的问题。3．理解线性规划图解法的基本原理。4．掌握图解法求解线性规划模型的基本方法。5．理解单纯形法求解线性规划问题的基本原理。6．掌握单纯形法求解线性规划模型的基本方法。能力点、素质点能力点：能够对一些相对简单的物流资源配置问题建立线性规划模型。能够运用线性规划模型解决一些简单的物流资源优化配置问题。素质点：拥有资源节约意识和可持续发展观。拥有全局观念和大局意识。单元五应用举例一、运输生产计划安排问题二、流通加工中心加工作业优化问题三、物流网络配送优化问题四、仓储产品布局问题一、运输生产计划安排问题某煤炭集团有A1、A2、A3三个煤矿，下属的煤炭物流公司每天都要把生产的煤炭运往B1、B2、B3、B4四个地区。各煤炭的产量、各地区的需求量以及各厂矿之间的单位运价如表3-13所示。问：如何组织调运才能使总运费最少？表3-13

地区煤矿B1B2B3B4产量A163255A275842A332973需求量2314一、运输生产计划安排问题设xij为每天从Ai矿运往Bj地区的煤炭数量，z为总运费，每个煤矿的产量分别为ai，每个地区的需求量分别为bj，可建立数学模型如下：二、流通加工中心加工作业优化问题某流通加工中心开展钢材的裁剪加工业务，定点供应某机床厂使用。机床厂成批生产一种机床，需要甲、乙、丙三种型号相同而不同规格（尺寸）的圆钢作为轴的毛坯，其规格和需要量如表3-14所示。机床厂一次向流通加工中心订购100台机床的材料，而圆钢的原有长度是5.5米，如何裁断，才能使所用圆钢最少？表3-14每台机床所需的三种毛坯的规格和数量毛坯的种类规格/米数量/件甲3.11乙2.12丙1.24二、流通加工中心加工作业优化问题一根刚才（圆钢）截成所需的甲、乙、丙三种毛坯具有多种截法，如表3-15所示。表3-15每台机床所需的三种毛坯的规格和数量序号截3.1米/根（甲）截2.1米/根（乙）截1.2米/根（丙）剩余尺寸/米11100.321020302107二、流通加工中心加工作业优化问题设

表示用方式j下料的根数，可得该问题数学模型：

minZ=三、物流网络配送优化问题某销售系统需确定一种产品的最优配送策略。有两个工厂P1和P2生产该产品，工厂P2年生产能力为60000单位；两个工厂具有相同的生产成本；两个现行仓库W1和W2，这两个仓库具有相同的搬运成本；三个市场C1、C2和C3，其需求量分别为50000单位，90000单位和50000单位。表3-18提供了每单位产品的配送成本。试找出在不违背工厂P2生产能力的约束条件下，确定从供应商到仓库到市场的产品流量的最优配送策略。表3-18P1P2C1C2C