物流运筹学完整版ppt教学课件全套教程

《物流运筹学完整版ppt教学课件全套教程》由会员分享，可在线阅读，更多相关《物流运筹学完整版ppt教学课件全套教程（651页珍藏版）》请在装配图网上搜索。

1、物流运筹学教学课件第1章线性规划初步与物流生产管理Contents Page目录页3 线性规划的一般定义1线性规划的图解法2线性规划的标准形式及矩阵表示3单纯型法4生产能力的合理分配5装卸作业调配6车载货物的装配74 1.1 1.1 线性规划的一般定义1.15 1.1.1 1.1.1 建立数学模型【例例1.1】某厂生产甲、乙两种产品，均需经过金工和装配两个车间加工，但每件利润却不相同，每件产品在两个车间的加工时间如表。金工和装配车间的总有效工时分别为400与500小时。甲、乙两产品所能获得的利润分别为：100元/件、80元/件。问如何安排生产，才能使所获得的利润最大？甲甲乙乙金金 工工42装装

2、 配配241.1线性规划的一线性规划的一般定义般定义6 1.1.1 1.1.1 建立数学模型12121242400245000,0 xxxxxx金工车间总有效工时的约束装配车间总有效工时的约束产量不能是负值（）（）（）解：解：设 分别表示产品甲、乙的产量。根据题意，必须满足：12,x x线性不等式1212()10080,f xxxx目标函数1.1线性规划的一线性规划的一般定义般定义7 1.1.1 1.1.1 建立数学模型这种含有决策变量、约束条件及目标函数的数学式子，并指明了求目标函数的最大值（或最小值），称为数学模型。上述式子中的约束条件是决策变量的线性不等式组，目标函数也是决策变量的线性函

3、数，像这样约束条件和目标函数都是用线性函数来描述的数学模型，我们称之为线性规划的数学模型，简称为线性规划。1.1线性规划的一线性规划的一般定义般定义8 1.1.1 1.1.1 建立数学模型【例例1.2】某学生食堂出售甲、乙两种食品，甲每份售价1.50元，乙每份售价2.10元。经检测食品中含有三种学生所需的营养物A、B、C，其中食品甲每份含A、B、C分别为10，3，4毫克，食品乙每份含A、B、C分别为2，3，9毫克，而营养师认为学生每餐至少需此三种营养物A、B、C分别为20，18，36毫克，问一学生进餐应对甲、乙食品各买几份，既能保证足够的营养要求，又花钱最少？甲甲乙乙营养最低要求营养最低要求A

4、10220B3318C4936单价（元单价（元/每份）每份）1.502.10 营养含量食品营养物1.1线性规划的一线性规划的一般定义般定义9 1.1.1 1.1.1 建立数学模型解解：设学生进餐者购买食品甲、乙分别为 份，根据题意，此问题的线性规划数学模型是：12,x x1212121210220331849360,0 xxxxxxxx12min1.502.10.fxx1.1线性规划的一线性规划的一般定义般定义10 1.1.1 1.1.1 建立数学模型【例例1.3】某建筑工地，需要直径相同、长度不同的成套钢筋。每套由7根2米与2根7米的钢筋组成。今有15米长的钢筋150根，问应怎样下料，才能使

5、废料最少？1.1线性规划的一线性规划的一般定义般定义11 1.1.1 1.1.1 建立数学模型把一根15米长的钢筋割成分别为7米和2米的两种规格，有三种比较经济的割法分割方法分割方法7米长米长2米长米长废料长废料长方法一方法一0根7根1米米方法二方法二1根4根0米米方法三方法三2根根0根根1米米1.1线性规划的一线性规划的一般定义般定义12 1.1.1 1.1.1 建立数学模型设决策变量 分别表示采用上述三种方法割料的15米长钢筋根数，则有123,x x x123150.xxx又考虑到每套由7根2米长和2根7米长的钢筋组成。而7米长有（）根，2米长有（）根。于是，由配套要求得123012xxx

6、 123740 xxx 2312(2):(74)2:7,xxxx12314140.xxx123101.fxxx 1.1线性规划的一线性规划的一般定义般定义13 1.1.1 1.1.1 建立数学模型123123150141400,(1,2,3)ixxxxxxxi13min.fxx1.1线性规划的一线性规划的一般定义般定义14 1.1.1 1.1.1 建立数学模型【例例1.4】设某种货物有 A1、A2、A3三个产地，四个销售地 B1、B2、B3、B4，从A1、A2、A3到地 B1、B2、B3、B4 的单位运价以及三个产地的供应量和四个销售地的需求量如表所示。问怎样安排调运方案，才能使总的运费最少？

7、B1B2B3B4产量产量A1311267A219474A3421059销量销量354820产地运价销地1.1线性规划的一线性规划的一般定义般定义15 1.1.1 1.1.1 建立数学模型解解：设由Aj到 Bj的运量为xij，所需总运费为f，则其数学模型为求 满足：(1,2,3;1,2,3,4)i jxij1.1线性规划的一线性规划的一般定义般定义16 1.1.2 1.1.2 线性规划的一般定义1.1线性规划的一般定义要确定决策变量（或），即确定优化的内容和对象。决策变量是不同方案赖以区分的根据。一般地，不同的决策变量表示着不同的方案。决策变量具有非负性。确定约束条件。约束条件是优化过程受限制的

8、条件，用含决策变量的一组线性等式或者线性不等式表示。确定目标函数。目标函数是决策变量的线性函数，并明确求其最大（小）值。在线性约束条件下，要求确定决策变量的一组线性目标函数达到最大值或最小值的问题，叫做线性规划问题，常用 LP表示。17 1.1.2 1.1.2 线性规划的一般定义1.1线性规划的一般定义一般地，的模型为求123,.,:nx x xx11 11221121 1222221 12212.().().(),.0.nnnnmmmnnmna xa xa xba xa xa xba xaxaxbx xxst 或或或1 122max(min).nnfc xc xc x或1()(1,2,.,)

9、0nijjjjja xbimx或1m ax(m in).njjjfc x或18 1.2 1.2 线性规划的图解法1.219 1.2.1 1.2.1 线性规划模型的解的基本概念(1,2,3,.,):jxjn求求1()(1,2,.,)(13)0(14)nijjjjja xbimx或1m ax(m in).njjjfc x或(1 5)20 1.2.1 1.2.1 线性规划模型的解的基本概念可行解：我们把满足约束条件（1-3）式和（1-4）式的一组变量，称为 线性规划的一组可行解；所有可行解的集合叫做可行解集，或称可行域。最优解：满足目标函数（1-5）的可行解图称为线性规划的最优解；最优值：最优解对应

10、的目标函数值称为最优值。凸集：设R是n维空间的一个点集，如果R中任意两点的连线仍在集R中，称集R为凸集。用数学式子描述是：对于R中的任意两点x1,x2，对于参数 ，若x1与x2连线上的点为 +（1 仍在集R中，称集R为凸集。顶点：设R是凸集，；若x不能用 ，两点的连线组合表示为 则x为R的一个顶点，或称极点。即凸集的顶点是不处于凸集中任何两个不同点的连线上的点。它与过去所说的几何体的顶点的含义是一致的。(1,2,3,.,)jxjn(01)1 x2)xxR1xR2xR12(1)(01)xxx21 1.2.2 1.2.2 二元一次不等式的区域图解法图解法任何一个二元一次方程Ax1+Bx2+C=0，

11、在平面直角坐标系中都表示一条直线，此直线把平面分成两个半平面：其中一个半平面包括直线 l的点的坐标总满足二元一次不等式 Ax1+Bx2+C0（或 0），此时另一半平面上的点（含直线l上的点）就总满足Ax1+Bx2+C0（或 0），两半平面的边界线就是直线Ax1+Bx2+C=0。如何确定半平面 Ax1+Bx2+C0（或 0）呢？具体做法是：在直线Ax1+Bx2+C=0外任取一点（x1，x2），对于不经过原点的直线，一般取原点（0,0），视其坐标是否满足不等式，若满足不等式，则该点所在的一侧的半平面就是不等式所表示的半平面区域；否则，另一半平面为不等式所表示的区域。22 1.2.2 1.2.2 二

12、元一次不等式的区域【例例1.5】求下列二元一次不等式所表示的区域：（1）x2 0 （2）x1 0（3）4x1+2x2400 （4）2x1+4x2500 23 1.2.2 1.2.2 二元一次不等式的区域解：解：（1）表示x1包括 轴和它上面的半平面，如图所示24 1.2.2 1.2.2 二元一次不等式的区域（2）表示x2包括 轴和它右半侧的半平面，如图所示25 1.2.2 1.2.2 二元一次不等式的区域（3）先画出直线：4x1+2x2=400 再“试点”：把原点 代入原不等式，发现不等式成立，则原点所在一侧即直线的左下方为不等式所表示的区域。26 1.2.2 1.2.2 二元一次不等式的区域

13、（4）作直线：2x1+4x2=500 的图像。把原点（0,0）代入不等式2x1+4x2500结果不等式成立。表明 2x1+4x2500的区域为直线与原点所在一侧，即直线的左下方半平面；另一半平面为2x1+4x2 500所表示的区域27 1.2.3 1.2.3 两个变量的线性规划问题的解法【例例1.6 】生产安排问题：某工厂生产甲、乙两种产品，所耗用的原料A、原料B数量，单件利润值及库存原料数如下表所示。试确定甲、乙两种产品应各生产多少件才能使该工厂利润最大。单件产品耗用原料数单件产品耗用原料数库存原料总数（库存原料总数（kg）甲乙A51060B4440单件利润值（元单件利润值（元/件）件）68

14、 原料产品28 1.2.3 1.2.3 两个变量的线性规划问题的解法先建立数学模型：设产品甲计划生产x1件，产品乙计划生产x2件，求x1、x2的值（称x1、x2为决策变量），使得f=2x1+4x2（称之为目标函数）达到最大值。约束条件为：12121251060,4440,0,0.xxxxxx29 1.2.3 1.2.3 两个变量的线性规划问题的解法首先画出可行解域，再令目标函数 f=2x1+4x2=h（常数）得到一条直线2x1+4x2=h（称为目标函数的一条等值线）在此直线上的点的坐标（x1，x2）都能使目标函数的值等于h 这条直线若穿过可行解域k，那么k中在这条等值线上的点的坐标都满足2x1

15、+4x2=h 12121251060,4440,0,0 xxxxxx121212212,10,0,0,xxxxxx30 1.2.3 1.2.3 两个变量的线性规划问题的解法画出可行解域过O（0,0）点的等值线为：6x1+8x2=0过A（0,6）点的等值线为：6x1+8x2=48等值线2x1+4x2=h 向右平行移动时，h 的值增加，到通过顶点B（8,2）时，得到最大值6431 1.2.3 1.2.3 两个变量的线性规划问题的解法【例例1.7】求x，y，使其满足约束条件,且使目标函数 f（x，y）=3x+y 达到最大。5,0,6221,0,0,xyxyxyxy 32 1.2.3 1.2.3 两个

16、变量的线性规划问题的解法解：解：画出可行解域k k是凸四边形OABC的内部及其边界线 直线3x+y=h从左向右平行移动，h增大 到与AB边重合所得的h最大，即3x+y=10.5 此时得最优解 实际上线段AB上任何一点的坐标都是最优解119,44xy33 1.2.3 1.2.3 两个变量的线性规划问题的解法【例例1.8】求x，y，使其满足约束条件,且使目标函数 f（x，y）=-2x+y 达到最大。1,33,0,0,xyxyxy 虽然有可行解，但没有最优解34 1.2.3 1.2.3 两个变量的线性规划问题的解法【例例1.9】求x，y，使其满足约束条件,且使目标函数 f（x，y）=3x+y 达到最

17、大。3,2,0,0,xyxyxy 可行解域K是空的，没有可行解，也没有最优解35 1.2.3 1.2.3 两个变量的线性规划问题的解法（1）有唯一最优解，它必是可行解域 的一个顶点的坐标。（2）有最优解，但不唯一，最优解必是可行解域的某条边上任何一点的坐标。（3）有可行解，但无最优解。可行解中的点能够使目标函数值之绝对值无限增大（或无限减小）。（4）无可行解，即可行解域k是空的。36 1.2.3 1.2.3 两个变量的线性规划问题的解法【例例1.10】某企业承包种植甲、乙两种蔬菜，生产1t甲种蔬菜要消耗肥料9t，消耗电力4kWh（浇水等用电力），劳动量3人日；生产1t乙种蔬菜要消耗肥料4t，消

18、耗电力5kWh，劳动量10人日。但基地能够使用的肥料只有360t，电力200 kWh，劳动量300人日，不能超过这个范围。甲种蔬菜1t供应7个单位，乙种蔬菜1t供应12个单位。在上述肥料、电力、劳动量的限制下，希望能供应单位越多越好，求生产甲、乙蔬菜各多少t为最好？甲种甲种蔬菜生产蔬菜生产1t乙乙种蔬菜生产种蔬菜生产1t条件条件限制限制肥料（肥料（t）94360电力（电力（kWh）45200劳动量（人劳动量（人日）日）310300供应单位（个）供应单位（个）712 条件活动37 1.2.3 1.2.3 两个变量的线性规划问题的解法解：解：设生产甲种蔬菜x t，乙种蔬菜y t.求x,y，使其满足

19、约束条件，且使目标函数f（x，y）=7x+12y 达到最大值94360,45200,310300,0,0,xyxyxyxy38 1.2.3 1.2.3 两个变量的线性规划问题的解法 k是凸五边形OABCD的内部及其边界线 直线7x+12y=h从下向上平行移动，h增大 移动到点B时h最大，即7x+12y=428 此时得最优解 x=20，y=2439 1.3 1.3 线性规划的标准形式及矩阵表示1.340 1.3.1 1.3.1 线性规划问题的标准形式 为了便于讨论一般解法，常将线性规划问题的约束条件归结为变量非负变量非负且其它约束条件是线性方程线性方程，并且对目标函数统一成求最大值最大值，称为线

20、性规划问题的标准形式，即1 122maxnnzc xc xc x11 11221121 1222221 12212,.,0,0,0.nnnnmmmnnmna xa xa xba xa xa xbsta xaxaxbxxx0(1,2,)jbjm41 1.3.1 1.3.1 线性规划问题的标准形式若目标函数求 ，可通过求其相反数的方法将最小值问题转化为最大值问题 ，非线性方程表示的约束条件可通过加一个非负变量或减一个非负变量 的方法转化为标准形式，xi称为松弛变量1 122minnnzc xc xc x1 122max()nnzc xc xc x 0ix 42 1.3.1 1.3.1 线性规划问题

21、的标准形式【例例1.11】将线性规划化为标准形式：123min23zxxx12312312336,235,.2316,0(1,2,3).ixxxxxxstxxxxi 解解:引进松弛变量 ，于是所给问题化为标准形式：450,0 xx123max()23zxxx 1231234123536,235,.2316,0(1,2,3,4,5).ixxxxxxxstxxxxxi 43 1.3.1 1.3.1 线性规划问题的标准形式【例例1.12】将线性规划化为标准形式.1234max34,zxxxx12312422,.1,0(1,2,3,4).ixxxstxxxxi 1234max34,zxxxx12312

22、422,.1,0(1,2,3,4).ixxxstxxxxi乘以乘以-144 1.3.1 1.3.1 线性规划问题的标准形式【例例1.13】将线性规划化为标准形式.12max3,zxx 1231242,.231,0(2,3,4).ixxxstxxxxi引进两个新的非负变量x50，x60将x1表示为x1=x5-x6256max3,zxxx235624562,.3221,0(2,3,4,5,6).ixxxxstxxxxxi45 1.3.1 1.3.1 线性规划问题的标准形式（1）对目标函数，若求 minz，可令 便化为标准形式；（2）若约束条件中有“”关系，可加上非松弛变量化为“=”关系，若有“”关

23、系，则减去非松弛变量化为“=”关系；（3）若有某个 bk0，可在不等式（或等式）两边同乘以-1；（4）若有无正负约束决策变量 xk，可令 xk=xk+1 xk+t+1(xk+1,xk+t+1 0).,zz 46 1.3.2 1.3.2 线性规划的矩阵表示标准形式的线性规划问题可以用矩阵记号表示max,zCX,.0,AXbstX111212122212nnmmmnaaaaaaAaaaA为构成约束条件的线性规划方程组的系数矩阵1122,nmxbxbXbxbX和b为构成约束条件的线性规划方程组变量矩阵与常数项矩阵12,nCcccC为目标函数中变量系数构成的1行 n列矩阵47 1.3.2 1.3.2

24、线性规划的矩阵表示设约束方程组AX=b中的系数矩阵A的秩r(A)=m，B是矩阵A中任一阶的非奇异矩阵，则称B为该线性规划问题的一个基.若设A=(B,N)，其中B是一个基，且 ，B的列向量Pi（i=1,2,m）称为基向量，N的列向量 Pi（i=m+1,m+2,n）称为非基向量，对应的变量称为基变量和非基变量.非基变量取零值时所得的解称为基本解，如果基本解又满足非负条件，则称为基本可行解，简称为基可行解，能使目标函数达到最优的基可行解，称为最优基可行解.1212(,),(,)mmmnBP PPNPPP48 1.3.2 1.3.2 线性规划的矩阵表示【例例1.14】写出下列线性规划问题的所有基阵：1

25、234max232,zxxxx235624562,.3221,0(2,3,4,5,6).ixxxxstxxxxxi49 1.3.2 1.3.2 线性规划的矩阵表示解解:约束方程组的系数矩阵及各列向量分别为2342211211,1123123APPP 112213314222121,111213BP PBP PBP P423524634212111,.121323BP PBP PBP P1234560,5,5,5,5,5,BBBBBB 50 1.4 1.4 单纯型法1.451 1.4.1 1.4.1 引例求线性规划问题12max23,zxx1231241528,37,1.6,0(1,2,3,4,

26、5).ixxxxxxstxxxi（）52 1.4.1 1.4.1 引例解解：在式（1）中 x3，x4，x5的系数列向量组成的一个基为:1345100,010.001BP P P由约束条件得：3124125182,73,(2).6,0(1,2,3,4,5).ixxxxxxstxxxi53 1.4.1 1.4.1 引例当非基变量x1=x2=0时便得基本可行解X0=（0,0,8,7,6）目标函数z=0，由于z=2x1+3x2是非基变量的函数且x1，x2的系数为正，增加x1，x2可增加目标函数的值，故X0不是最优解一般选择增加系数大的而非基变量的值以得到一个新的基本可行解，所以 x2增加后被选为新的基

27、变量（称为换入变量），当 x1=0时，由于非负，约束条件（2）化为32425820,70,.60,0(1,2,3,4,5).ixxxxstxxi228,27.1xx54 1.4.1 1.4.1 引例把x1=0，x2=4代人式（2）的第1个方程，得x3=0，所以 x3应该被换出为非基变量（称为换出变量）.为了获得以x2 x4 x5 为基变量的一个基本可行解，用主元素消去法对式（1）中的约束方程组的增广矩阵施行初等行变把 代入目标函数，变为：11=-=22，1313max12,22zxx12313415114,22513,.(3)226,0(1,2,3,4,5).ixxxxxxstxxxi2245

28、100,010.001BP P P55 1.4.1 1.4.1 引例令x1=x3=0得基本可行解X0=（0,4,0,3,6），这时目标函数z=12，其值增加了。是非基变量x1 x3的函数，x1的系数为正，增加x1可增加目标函数 z的值，故X1也不是最优解.同理x1最多可增加到 代入第2个约束条件 ，所以x1进基，x4出基，同样进行基变换得13131222zxx1366min,1 2 5 2 15136,05xx40 x 346371max,555zxx2341343453117,555146,.5551224,5550(1,2,3,4,5).ixxxxxxstxxxxi56 1.4.1 1.4

29、.1 引例26 1724(,0,0,),555X635z 346371555zxx是非基变量x3 x4的函数且它们的系数均为负数最优解26 1724(,0,0,),555X63max.5z 单纯型法：把线性规划模型化为标准形式，从一个基本可行解开始，用换基迭代方法，转换到另一个基本可行解，使目标函数值逐步增加，当目标函数达到最大值时，也就得到最优解.57 1.4.2 1.4.2 表格单纯型法58 1.4.2 1.4.2 表格单纯型法（1）第一列的中间三行填写基变量 x3 x4 x5；（2）xi列填写约束方程组中xi的系数.b列填写约束方程组右边的常数项；（3）z行填写目标函数中xi的系数，称为

30、检验数.当检验数全部小于等于0时，目标函数取得最优值，最大正检验数所在的列称为主元素列，现在是x2列的3最大，它就是主元素列，x2就成为进基变量；(4)用主元素列中的正分量去除b列对应的分量，取得最小比值对应的行称为主元素行，现在是在x3行.变量就成为出基变量；（5）给主元素行和主元素列的交点2加上中括号，它就称为轴心项；（6）下一步就是进行换基迭代，利用矩阵的初等行变换，将轴心项化为“1”，主元素列的其它元素化为“0”.重复上述过程，直到检验数全部非正.59 1.4.2 1.4.2 表格单纯型法60 1.4.2 1.4.2 表格单纯型法61 1.4.2 1.4.2 表格单纯型法【例例1.15

31、】解线性规划问题123max2,zxxx 12312214,.216,0(1,2,3,4,5).ixxxstxxxi62 1.4.2 1.4.2 表格单纯型法解：解：引进新的目标函数z=-z，且引进松弛变量 ，把所给的线性规划问题化为标准形式：450,0 xx123max2,zxxx 1234125214,.216,0(1,2,3,4,5).ixxxxstxxxxi63 1.4.2 1.4.2 表格单纯型法用单纯型表作换基迭代64 1.4.2 1.4.2 表格单纯型法所有检验数非正，去掉松弛变量，得最优解*(6,0,0)X 16z minmax6.zz 65 1.4.2 1.4.2 表格单纯型

32、法【例例1.16】解线性规划问题12max2,zxx1231245,.2510,0(1,2,3,4,).ixxxstxxxxi66 1.4.2 1.4.2 表格单纯型法解解：这个线性规划问题已经是标准形式，可直接用单纯型表作换基迭代：67 1.4.2 1.4.2 表格单纯型法还有一个证检验数6，而对应列元素全部为负，无法进行下一步的迭代将其变量 x3 x1即目标函数z用非基变量x2 x4 表示为324124243110,22515,22610.xxxxxxzxx令非基变量x2无限增大，x4 =0，此时基变量仍满足非负的约束条件，但目标函数z却无限增大，即无最大值，所以这个线性规划问题有可行解而

33、没有最优解.68 1.5 1.5 生产能力的合理分配1.569 1.5.1 1.5.1 一般性的问题设有n台机床，在这些机床上制造由m个不同的零件组成的产品。假设在第i台机床上加工第k种零件，一天能生产Qik个零件，这些是已知的注意：如果在第i台机床上不能加工第k种零件，则认为Qik=0 问怎样来分配零件的加工，可以使制造出来的零件组成的产品最多？70 1.5.1 1.5.1 一般性的问题设tik表示在第i台机床上生产第k种零件的时间（用占一个工作日的份额表示）10,1(1,2,)mikikkttin第i台机床上生产所有零件的时间总计为1个工作日是 Qik tik 在第 i 台机床上生产第 k

34、 种零件的数量11(1,2,)nkik ikizQ tkm12kmzzzz71 1.5.1 1.5.1 一般性的问题(1,2,;1,2,)iktin km0ikt 11(1,2,)mikktin11(1,2,)nkik ikizQ tkmtik应使 最大。12mzzzz72 1.5.2 1.5.2 效率比法【例例1.17】设有两种零件，在单位时间内工人甲生产50个第I种零件，60个第II种零件；工人乙生产30个第I种零件，90个第II种零件；工人丙生产20个第I种零件，80个第II种零件。每种零件各一个就能配成套，问如何分配任务，可在单位时间内生产出最多的套数。73 1.5.2 1.5.2 效

35、率比法解：解：将甲、乙、丙三个工人在单位时间内生产各种零件的个数（生产效率）列表如下：甲甲乙乙丙丙I503020II609080零件工人74 1.5.2 1.5.2 效率比法（1）工人甲单独成套生产。设工人甲单独生产零件I所占的时间份额为x，那么1x则是工人甲单独生产零件II所占的时间份额，则有5060(1)xx65,11111xx工人甲在单位时间内可生产()655060271111套75 1.5.2 1.5.2 效率比法（2）工人乙单独成套生产。设工人乙单独生产零件I所占的时间份额为y，那么1y为他生产零件II占用的时间份额，于是有：3090(1)yy31,144yy工人乙在单位时间内可生产

36、)31309022(44套76 1.5.2 1.5.2 效率比法（3）工人丙单独成套生产。设工人丙单独生产零件I所占的时间份额为z，那么1z为他生产零件II占用的时间份额，因此有：2080(1)zz41,155zz工人丙在单位时间内可生产()4120801655套77 1.5.2 1.5.2 效率比法 甲甲乙乙丙丙I272216II272216零件工人方案方案一一：三个工人分别单独成套生产，共可生产65套/单位时间。但是这种分配任务的方法未必能得到最多的套数。78 1.5.2 1.5.2 效率比法依经验，可以采用谁加工哪种零件最快谁就加工哪种零件的方法：让工人甲加工零件I 50个，工人丙加工零

37、件I 20个，工人乙加工I与II两种零件。设t与1t为乙分别加工I与II两种零件占用的时间份额，则有50203090(1)tt15,166tt 15305,9015 57566 79 甲甲乙乙丙丙I50520II 75 1.5.2 1.5.2 效率比法零件工人方案二方案二：共生产了75套，比前面的分配方法多出10套80 1.5.2 1.5.2 效率比法效率比法：效率比法：先求出甲、乙、丙三位工人生产这两种零件的效率比，见下表：81 1.5.2 1.5.2 效率比法甲生产零件I的效率最高，丙生产零件II的效率最高。因此，让工人甲生产零件I，工人丙生产零件II82 1.5.2 1.5.2 效率比法

38、让工人乙生产零件I和II以便调配成套。设乙生产零件I x个，零件II y个。那么乙生产这x个零件I要占用时间份额 ，而生产y个零件II占用的时间份额为 ，从而有30 x90y508013090 xyxy，解得：x=30 y=030390 xyxy，83 1.5.2 1.5.2 效率比法方案三方案三：共可生产80套，比第二个分配方案又多出5套。甲甲乙乙丙丙I5030 II 80零件工人84 1.5.2 1.5.2 效率比法【例例1.18】某物流企业有四个生产组，A组有11人，每人每天生产甲产品1.1吨或生产乙产品2吨；B组有5人，每人每天生产甲产品1.5吨或生产乙产品3吨；C组有16人，每人每天

39、生产甲产品1.1吨或生产乙产品1.5吨；D组有8人，每人每天生产甲产品0.8吨或生产乙产品1吨；求在生产甲产品26吨的情况下，生产乙产品越多越好的人员分配方案。85 1.5.2 1.5.2 效率比法解：解：先列出各组人员的生产效率表 A组组11人人 B 组组5人人C组组16人人D组组8人人生产甲产品生产甲产品1.11.51.10.8生产乙产品生产乙产品231.51任务劳动力86 1.5.2 1.5.2 效率比法先要完成种26吨甲产品的任务，再分配生产乙产品的任务。可按下表分配任务 A组组11人人 B 组组5人人C组组16人人D组组8人人生产甲产品生产甲产品1156生产乙产品生产乙产品108任务

40、劳动力11 1.1 5 1.56 1.126.2()t 10 1.58 123()t 甲产品：乙产品：87 1.5.2 1.5.2 效率比法效率比法：先求各组人员的效率比：A组组B组组C组组D组组1.821.361.25乙产品甲产品任务劳动力D组人员的效率比最低，B组人员的效率比最高。8位D组人员生产甲产品：8 0.86.4()t16位C组人员也生产甲产品：16 1.1 17.6()t共24吨，还差2吨再分配2位B组人员去生产甲产品：2 1.12.2()t剩下的人员全生产乙产品925 333 88 1.5.2 1.5.2 效率比法 A组组B组组C组组D组组生产甲产品生产甲产品2 168生产乙产

41、品生产乙产品95 任务劳动力89 1.6 装卸作业调配1.690 1.6.1 1.6.1 装卸任务分配问题【例例1.19】某运输仓库有4项装卸任务必须在二天内完成，该仓库有3个装卸队，均可以单独完成其中任一项任务.如表所示，列出了各装卸队单独完成各项任务所需要的时间，每小时的装卸成本及可用的小时数，各项任务均可以分开由两个或三个队完成（这也是与一般指派问题的区别）.试问怎样分配这些任务才能使装卸成本达到最低.装卸队装卸队每每任务所需任务所需时间时间 单位成本单位成本 可用时间可用时间123412320202073757736302859636019018015580808091 1.6.1 1

42、.6.1 装卸任务分配问题解解：设Xsr表示第r项任务由第s队所做的小时数，其完成任务的最小成本的线型规划问题可表达为:11121314max.()190()f XXXXX21222324180()XXXX31323334170()XXXXS.t：1112131480XXXX2122232480XXXX3132333480XXXX1222327375771XXX1323333630281XXX1424345963601XXX0arX92 1.6.1 1.6.1 装卸任务分配问题用单纯型法求解，得出：12142122333414.7,14.7,20,60,28,52XXXXXX按照Xij的定义，

43、第1队承担第2项任务14.7小时（占该项任务的14.7/73=20），又承担第4任务7.8小时（占该项任务的7.8/59=13.3）；第2队承担第1项任务20小时（占100），又承担第2任务60小时（占80）；第3队承担第3项任务28小时（占100），又承担第4任务52小时（占该任务的86.7）.也就是说，第4项任务由第1、第3队承担；第2项任务由第2队承担；第3项任务由第3队承担；第1项任务由第2队承担.93 1.6.2 1.6.2 装卸工人的调配问题在汽车运输中，为了减少空驶里程，提高汽车的里程利用率，往往要组织巡回运输。这样，一辆汽车从车场开出之后，中途就会经过若干个装卸点，每个装卸点因

44、货物不同，需要的装卸工人的人数也不相同，于是就产生了怎样调配装卸工人，才能充分发挥他们的效率的问题。94 1.6.2 1.6.2 装卸工人的调配问题方法方法1：调配调配装卸工人的简易方法装卸工人的简易方法编号计算编号计算法法当车辆比装卸点多时，装卸工人固定在装卸点处/车辆比装卸点少时，采用编号法。其步骤是:按装卸点所需要的装卸工人数目，由多到少把相应的装卸点编上号码，按次序排列起来。若有n辆车，就从排列好的需要装卸工人数最多的装卸点一端开始数n个装卸点的号码，看数到的第n个装卸点需要多少装卸工人，就派多少装卸工人在车上。在需要更多装卸工人的装卸点派出相应数目的装卸工人固定到装卸点上，跟车装卸工

45、人数与固定在装卸点上的装卸工人数之和应该等于该点所需要的装卸工人数。95 1.6.2 1.6.2 装卸工人的调配问题【例例1.20】某物流企业的车场每天有4辆货车经过6个装卸点A1，A2，A3，A4，A5，A6，组织巡回运输。在A1点装货，需要8个装卸工人；在A1点卸货，需要5个装卸工人；在A5点装货，需要3个装卸工人；在A5点卸货，需要4个装卸工人。试制定合理调配装卸工人的方案。96 1.6.2 1.6.2 装卸工人的调配问题解解：此例中，车辆数为4，装卸点为6个，是车比装卸点少的情况，因此不要把装卸工人全固定到装卸点上。按照编号计算法，把所有装卸点按需要装卸工人的数目由多到少排列起来：A3

46、（8人），A1（6人），A4（5人），A2（4人），A6（4人），A5（3人），再根据车辆数4，从多的一端开始数到排好的第四个点（这里是A2）。又A2需要4个装卸工人，就派4个装卸工跟车；A3需要8人，就派4个装卸工固定在A3；A1需要6人，就派2人固定在A1；A4需要5人，则派1人固定在A4；A2，A6，A5就不需派人了。这样，总共用了44+4+2+1=23个装卸工人。97 1.6.2 1.6.2 装卸工人的调配问题车比点多，人往点上搁；车比点少，编号方法好；按点需要人多少，由大到小编编号，车数是几数到几，几个人数跟车跑。98 1.6.2 1.6.2 装卸工人的调配问题方法方法2：调配调配装

47、卸工人的一般方法装卸工人的一般方法推导求解方法推导求解方法假定有m个装卸点，各点所需要装卸工人人数分别为b1，b2 bm，汽车数目为n，由于所需要人数与各点的顺序无关，所以我们规定12mbbb设X表示跟车人数，存在某一个整数k，使1kkbXb循环运输所需要安装工人人数为：1()()kif XbiXnX1()kibink X为了求f(X)的极小值，我们对X求导，并令其为零，即()0fXnk99 1.6.2 1.6.2 装卸工人的调配问题由此可见，当k=n时，f(X)达到极值，因此可按如下办法确定跟车人数：1.如果nm，则取X=0，即无人跟车，所有装卸工人均固定在各个装卸点上.2.如果nm，则X取

48、bn与bn+1之间的整数.装卸作业所需的装卸工人人数为：1kiifb0bsXbsXGbsX当当100 1.6.2 1.6.2 装卸工人的调配问题【例例1.21】某车场每天有4 辆汽车经过A1，A2，A3，A4，A5，A6六个点组织循环运输，在A1装货需要6个工人；在A2装货需要9个工人；在A3装货需要8个工人；在A4卸货需要6个工人；在A5卸货需要两个工人；在A6卸货需要4个工人。试制定合理调配装卸工人的方案。101 1.6.2 1.6.2 装卸工人的调配问题解解：因为m=6，n=4，各装卸点所需人数按递降顺序排列成9，8，6，6，4，2。所以跟车人数为6与4之间的整数，即X=6或X=5或X=

49、4均可.故所需装卸工人的总人数为：986629()f 人如果取X=5，则各点固定人数分别为：1122334456651()954()853()651()0()0()GbXGbXGbXGbXGG人人人人人人102 1.6.3 1.6.3 装卸服务顺序问题【例例1.22】5个货主需要在甲、乙两台设备上安排装卸（例如先在甲卸货，再到乙装货），所需时间如表1-23所示。T（甲）表示货主在甲台设备上的作业时间，T（乙）表示货主在乙台设备上的作业时间。货主ABCDET(甲)0*8*103*7T（乙)1195*34*安排顺序一三四二五103 1.6.3 1.6.3 装卸服务顺序问题第一步，比较表中的各个数值

50、，找出其中的最小值，本例的最小值为0，这个最小值如果在T（甲）行，则该货主（本例为A货主）最先装卸。如果，在T（乙）行，则该货主安排在最后装卸。第二步，把已经安排装卸顺序的货主消去，转第三步。第三步，在剩余的货主中，继续安排装卸顺序，在表中各数值中，寻找最小值。如果该最小值在T（甲）行，则该货主安排在前面，如果最小值在T（乙）行，则该货主安排在后面。重复第二步和第三步，直至全部安排完为止。注意，如果同一货主在两台设备上所需装卸时间均为最小值时，应首先选择T（甲）行的最小值。如果几个货主同台设备装卸时间均为最小值时，应比较在另一台设备上的对应装卸时间。必须把对应装卸时间较少的货主排在前面。对应装

51、卸时间较多的货主排在后面。按上述步骤对本例排序的结果是：A货主第一；D货主第二；B货主第三；C货主第四；E货主第五。104 1.6.3 1.6.3 装卸服务顺序问题货主作业时间等待时间完成时间ABCDE11-0=1123-3=2028-11=1714-0=1432-21=110+0=03+0=38+3=110+0=010+11=211123281432合计7335108105 1.6.3 1.6.3 装卸服务顺序问题106 1.7 车载货物的装配1.7107 1.7.11.7.1 两种货物的装配问题【例例1.23】设某物流企业有甲货物每件a1 吨，体积为a2 m3；乙货物每件b1吨，体积为b2

52、 m3。每辆车的载重量为k吨，有效容积为v m3。求怎样配装这两种货物，既能使车辆载满，又能充分利用车辆的有效容积。108 1.7.11.7.1 两种货物的装配问题解解：可设每辆车装甲货x件，装乙货y件。由题意知：1122.a xb yka xb yv（1）方程组有正数的解x00，y00且x0和y0又都是整数时，配装方案是装甲货x0件，装乙货y0件。而x0，y0有一个不是整数时，则应在图（1）所示的四边形中选一个离点（x0，y0）最近的坐标为正整数的点（x1，y1），这时近似最佳配装方案为装甲货x1件，装乙货y1件。109 1.7.11.7.1 两种货物的装配问题直线l1：a1x+b1y=k和

53、与l2：a2x+b2y=v 的交点不在第一象限，这时交点坐标x和y必有一个是负数，不合要求。此时应该在图（2）（3）中画阴影的三角形上找一个离斜边最近的在斜边上的坐标是正整数的点（x2，y2）近似最佳装配方案为：装甲货 x2件，装乙货y2件。110 1.7.11.7.1 两种货物的装配问题【例例1.24 】某物流企业有甲、乙两种货物，甲货每件重10kg，体积为0.02 m3；乙货每件重2kg，体积为0.005 m3。汽车的载重量为4 t，有效容积为5.4 m3。求最优配装方案。111 1.7.11.7.1 两种货物的装配问题解：解：设装甲货x件，装乙货y件，则有1024000,0.020.00

54、55.4,xyxy52000,41080,xyxy920,2600,xy y 0，不符合要求52000,0400 xyx41080,0270 xyx0y 0270 x112 1.7.11.7.1 两种货物的装配问题直线4x+y=1080上任何一个坐标为非负整数的点，其坐标（x，y）（0 x 270）都是较好的配装方案。这样的点也应尽量靠近直线5x+y=2000 上述问题，我们既考虑载重量又考虑有效容积，若再考虑使装载的货物总价值最大，则问题就变成了二元背包问题，解起来就复杂多了。在这里我们不讨论这样的问题。113 1.7.2 1.7.2 装箱问题装箱装箱问题：问题：有体积分别为v1，v2，vn

55、的n种物品u1，u2，un，将其装到容量为L的箱子里，要求使装尽这n种物品的箱子数目达到最小。114 1.7.2 1.7.2 装箱问题对n种物品u1，u2，un，先按体积从大到小排序。不妨设：u1u2un设箱子的次序为B1，B2，Bn对于某一个物品ui，它总是被装到第一个能装下ui的箱子里。也就是说，对未装满的箱子，既不封住，也不搬走，对于物品ui，对所有未装满的箱子Bj，从j=1开始顺序检查，只要有Bj能装下ui，且标号小于j的箱子均装不进ui，则把ui装进Bj115 1.7.2 1.7.2 装箱问题116 1.7.3 1.7.3 运用动态规划解装货问题设货车的载重量上限为G，用于运送n种不

56、同的货物（物品），物品的重量分别为W1，W2，,Wn每一种物品对应于一个价值系数，分别用P1，P2，,Pn表示.它表示价值、运费或重量等.设Xk表示第k种物品的装入数量，装货问题可以表述为：1max()nkkkf XP X1nkkkW XG0kX s.t117 1.7.3 1.7.3 运用动态规划解装货问题可以把装入一件物品作为一个阶段，把装货问题化为动态规划问题.动态规划问题求解过程是从最后一个阶段开始由后向前推进.由于装入物品的先后次序不影响最优解，所以我们的求解过程可从第一阶段开始，由前向后逐步进行.第一步：装入第1种物品X1件，其最大价值为111()max.f WPX110/XG W第

57、二步：装入第2种物品X2件，其最大价值为222122()max.()f WP Xf WW X220/XG W118 1.7.3 1.7.3 运用动态规划解装货问题第三步：装入第3种物品X3件，其最大价值为333233()max.()f WP Xf WW X330/XG W第n步：装入第n种物品Xn件，其最大价值为1()max.()nnnnnnf WP XfWW X0/nnXG W119 1.7.3 1.7.3 运用动态规划解装货问题【例例1.25】载重量为8吨的载重汽车，运输4种机电产品，其重量分别为3,3,4,5吨，试问如何配装才能充分利用货车的运载能力?物品号重量（吨）价值系数123433

58、453345120 1.7.3 1.7.3 运用动态规划解装货问题在第四阶段计算表第四阶段计算表中，价值（本例为载重量）最大值 f4(W)=8，对应两组数据.其中，一组中X4=0，另一组中X4=1 当 X4=1时，即第四种物品装入1件.表中第3列数字表示其余种类物品的装载量.当X4=1时，其他三种物品装载量为3；WX4W-W4X4 f4(W)8 0081 0+8=8*5+3=8*8 44344(-)P Xf W W X121 1.7.3 1.7.3 运用动态规划解装货问题在第第三三阶段阶段计算表计算表中，查W=3，X3=0，其2种物品装载量为3在第第二二阶段阶段计算表计算表中，查W=3，f3(

59、W)=3，对应两组数据 X2=1，余量为0 X2=0，余量为3在第第一一阶段阶段计算表计算表中，查W=3，X1=1；查W=0，X1=0；1234=1,=0,=0,=1XXXX1234=0,=1,=0,=1XXXX()1 3+1 5=8f X 122 1.7.3 1.7.3 运用动态规划解装货问题在第四阶段计算表第四阶段计算表中，取X4=0，余项W-W4X4=8在第第三三阶段阶段计算表计算表中，查W=8，对应X3=21234=0,=0,=2,=0XXXX()2 4=8f X 123 1.7.4 1.7.4 运用动态规划解品种混装问题整装零担车内装有多少个客户的货物，要分别在同一站或多站卸货。一些

60、外观相近的货物容易混淆，到站卸货容易出现错卸现象.为了减少或避免这种差错，可以把外观相近、容易混淆的货物分开装卸，尽量不要配装在一个货车内。为了解决这个问题，可以把货物进行分类，按品种、形状、颜色和规格把货物分为若干类，分别称为1类，2类，m类。假设共有N件（捆）待运货物，其中1类货物有N1件（捆），它们的重量分别为G11,G12,G1N1；2类货物有N2件（捆），它们的重量分别为G21,G22,G2N2；124 1.7.4 1.7.4 运用动态规划解品种混装问题1msSNN1,0rsssrXr类第 件货物装入类第 件货物不装入，设品种混装要求在同一货车内每类货物至多装入一件（捆），同一客户的

61、多件（捆）同类货物可以记作1件（捆）。品种混装问题可以表示为：11max.GrNmrsrsrSG X 111,2,rNrsSXrm011rNmrsrsrSG XG 125 1.7.4 1.7.4 运用动态规划解品种混装问题8件货物分别为4类，在图中同一列的方框表示同一类货物.方框内的数字（符号）表示货物重量.上述品种混装问题就是在网络中自左向右寻找一条路线，使路线所经过的方框中的重量之和达到极大，但又不超过货物的装载量的上限G0 126 1.7.4 1.7.4 运用动态规划解品种混装问题【例例1.26】设货车载重量G0=50；第一类货物2件，G11=20，G12=11；第二类货物1件，G21=

62、13；第三类货物3件，G31=6，G32=11，G33=8；第四类货物2件，G41=19，G42=17.怎样组合装卸方法最好？127 1.7.4 1.7.4 运用动态规划解品种混装问题W50G401917W-G45031 33128 1.7.4 1.7.4 运用动态规划解品种混装问题W503133 G3061180611806118W-G3504439423125202333272225129 1.7.4 1.7.4 运用动态规划解品种混装问题W504439423125G2013013013013013013W-G2503744313926422931182512W2023332722G201

63、30130130130 13W-G220723103320271722 9130 1.7.4 1.7.4 运用动态规划解品种混装问题W5037443139264229182512G12020202020202020112011W-G130172411196229751W2071033271422G12013013201120W-G10374431732131 1.7.4 1.7.4 运用动态规划解品种混装问题1234123420011192013017GGGGGGGG谢 谢 大家物流运筹学教学课件第2章物流配送方案的选择Contents Page目录页135 物流配送方式的选择1物资的调运问题

64、的数学模型2物资调运中的表上作业法3产销平衡物资调运问题的图上作业法4车辆调度问题5136 2.1 2.1 物流配送方式的选择2.1137 2.1 2.1 物流配送方式的选择在物流管理过程中，组织物流配送与运输工作应该以及时以及时、准确准确、经济经济、安安全全为原则，在选择配送与运输方式（铁路、公路、水路、航空、管道等）时都应该以上述原则为依据。138 2.1 2.1 物流配送方式的选择1.经济性指标经济性指标设F1（*）表示某种物流配送方式的经济性指标，例如 F1（空）表示航空运输的经济性指标；C（*）表示某种配送与运输方式的费用支出。铁路、公路、水路、航空这四种运输方式的平均费用支出为：1

65、4CCCCC铁公）（水）（空）（）（1(*)(*)CFC139 2.1 2.1 物流配送方式的选择2.迅速迅速性性指标指标设F2（*）表示某种物流配送方式的迅速性指标；D（*）表示用某种物流配送方式运输所需要的时间。用铁路、公路、水路、航空这四种运输方式运输平均需要的时间为:14DDDDD铁公水空（）（）（）（）2(*)(*)DFD140 2.1 2.1 物流配送方式的选择3.安全安全性性指标指标设F3（*）表示某种物流配送方式的安全性指标；E（*）表示用某种物流配送方式的损坏率。用铁路、公路、水路、航空这四种运输方式运输平均损坏率为:14EEEEE（铁）（公）（水）（空）3(*)(*)EFE

66、141 2.1 2.1 物流配送方式的选择4.便利便利性性指标指标设F4（*）表示某种物流配送方式的便利性指标；L（*）表示用某种物流配送方式的发货地到收货地的距离。用铁路、公路、水路、航空这四种运输方式运输平均距离为:14LLLLL铁公水空（）（）（）（）4(*)(*)LFL142 2.1 2.1 物流配送方式的选择其中b1，b2，b3，b4为大于等于0的实数，且 。即为综合考察某种运输方式的经济性、迅速性、安全性和便利性的综合指标数值越少，其对应的运输方式越好。411iib11223344(*)(*)(*)(*)(*)Fb Fb Fb Fb F143 2.2 2.2 物资的调运问题的数学模型2.2144 2.2 2.2 物资的调运问题的数学模型有某种物资需要调运有m个地点可以供应该种物资（以后通称产地，用i=1,2，m 表示）这m个产地的可供量（以后通称产量）为a1,a2,am（可通写为ai）n个销地的需要量（以后通称销量）分别为b1,b2,bn（可通写为bi）从第i个产地到第j个销地的单位物资运价为cij145 2.2 2.2 物资的调运问题的数学模型产销平衡表销地产地146 2