运筹学基础复习一课件

《运筹学基础复习一课件》由会员分享，可在线阅读，更多相关《运筹学基础复习一课件（75页珍藏版）》请在金锄头文库上搜索。

1、基本运算基本运算一、线性规划线性规划线性规划线性规划 线性规划建模（是否是整数规划、01规划需要自己判定，并加上相应约束条件）、线性规划的图解法、线性规划（包括整数规划、0-1规划）的EXCEL求解、求线性规划的对偶问题，目标规划的图解法和EXCEL求解二、运输问题运输问题运输问题运输问题 产销平衡、产大于销、产小于销的含义及解决方法、给出运输问题的初始方案（三种）、会判定是否最优、会求改进路线、改进量、会利用EXCEL求最优解三、图论图论图论图论 会求最小枝杈树、会求从起点到终点的最短路线（可利用EXCEL）、会求网络的最大流量（可用EXCEL），会画网络图、会求关键路线、作业的时间、会优化

2、四、库存管理库存管理库存管理库存管理会求经济批量（不许缺货）、会判定折扣方案的优劣第一章第一章 线性规划线性规划线性规划线性规划线性规划线性规划是一种合理利用资源、合理调配资源的应用数学方法。一、线性规划问题的三个要素一、线性规划问题的三个要素决策变量决策变量决策变量决策变量是指实际系统或决策问题中有待确定的因素，是系统中的可控因素。约束条件约束条件约束条件约束条件 任何问题都是限定在一定的条件下求解，把各种限制条件表示为一组等式或不等式，称之为约束条件约束条件约束条件约束条件。是决策者对决策问题目标的数学描述。如时间最省、利润最大、成本最低。约束条件的基本类型：大于等于“”、等于“”、小于等

3、于“” 目标函数目标函数目标函数目标函数 目标函数是决策变量的线性函数。二、线性规划模型的构建二、线性规划模型的构建例例例例1. 1.生产计划问题生产计划问题生产计划问题生产计划问题某厂生产甲乙两种产品，各自的零部件分别在A、B车间生产，最后都需在C车间装配，相关数据如表所示： 产品产品车间车间工时单耗工时单耗甲甲 乙乙生产能力生产能力ABC 1 0 0 2 3 48 1236单位产品获利单位产品获利 3 5问如何安排甲、乙两产品的产量，使利润为最大。 建立模型建立模型：(1)(1)决策变量决策变量决策变量决策变量: : : :要决策的问题是甲、乙两种产品的产量，因此有两个决策变量：设x1为甲

4、产品产量，x2为乙产品产量。 则A车间的能力约束条件表述为 (2)(2)约束条件约束条件约束条件约束条件 : : : :生产这两种产品受到现有生产能力的制约，用量不能突破。 x x1 18 8 同理，B和C车间能力约束条件为 2x2x2 2 12123x3x3x3x1 1 1 1 +4 x +4 x +4 x +4 x2 2 2 2 36 36 36 36 产品产品车间车间工时单耗工时单耗甲甲 乙乙生产能力生产能力ABC 1 0 0 2 3 48 1236单位产品获利单位产品获利 3 5(3)(3)目标函数目标函数目标函数目标函数 : : : :目标是利润最大化，用Z表示利润，则 (4)(4)

5、(4)(4)非负约束非负约束非负约束非负约束: : : :甲乙产品的产量不应是负数，否则没有实际意义，这个要求表述为 则该问题的数学模型表示为则该问题的数学模型表示为则该问题的数学模型表示为则该问题的数学模型表示为 maxZmaxZ=3x=3x1 1+5x+5x2 2 x x1 1 0 0，x x2 2 0 0 maxZ=3x1+5x2 x182x212 3x1+4x236 x1 0, x2 0目标函数约束条件产品产品车间车间工时单耗工时单耗甲甲 乙乙生产能力生产能力ABC 1 0 0 2 3 48 1236单位产品获利单位产品获利 3 5例例2、配比问题配比问题某养鸡场所用的混合饲料是由 n

6、 种配料组成。要求这种混合饲料必须含有 m 种不同的营养成份，而且要求每单位混合饲料中第 i 种营养成份的含量不能低于 bi ( i= 1,2, , m）。已知第 i 种营养成份在每单位的第 j 种配料中的含量为 aij , j = 1,2, , n，每单位的第 j 种配料的价格为 cj 。现在要求在保证营养条件的前提下，应采用何种配方，使混合饲料的成本最小.配料配料营养成份营养成份B1 B2 Bn含量含量A1A2Am a11 a12 a1n a21 a22 a2n am1 am2 amnb1b2bm销量销量 c1 c2 cn建立模型建立模型：MinZMinZ= =c c1x1 +c c2x2

7、 +c cnxn 设xj 表示在单位混合饲料中，第j 种配料的含量（ j =1,2,n）则有如下的数学模型：配料配料营养成份营养成份B1 B2 Bn含量含量A1A2Am a11 a12 a1n a21 a22 a2n am1 am2 amnb1b2bm价格价格 c1 c2 cna a11x1 +a a12x2 +a a1nxn b1 a a21x1 +a a22x2 +a a2nxn b2a am1x1 +a am2x2 +a amnxn bmx1 0, x2 0 , , xn0 若资料为百分比，则变量也可设为百分比，但要满足：x1 +x2 +xn三、线性规划问题的标准形式三、线性规划问题的标

8、准形式 线性规划问题的数学模型有各种不同的形式，如 目标函数有极大化极大化极大化极大化和极小化极小化极小化极小化； 约束条件有“”、“”和“”三种情况； 决策变量一般有非负性非负性非负性非负性要求，有的则没有，没有符号要求的称为自由变量。为了求解方便，特规定一种线性规划的标准形式，非标准型可以转化为标准型计算 标准形式为：标准形式为：标准形式为：标准形式为： （一）标准形式（一）标准形式 目标函数最大化最大化最大化最大化 约束条件为等式等式等式等式， 右端常数项b bi i0 0 决策变量非负非负非负非负 maxZ=c1x1+c2x2+cnxna11x1+a12x2+a1nxn b1a21x1

9、+a22x2+a2nxn b2 am1x1+am2x2+amnxnbmx1,x2,xn0（二）（二）非非标准型向准型向标准型准型转化化 目标函数极小化问题目标函数极小化问题目标函数极小化问题目标函数极小化问题只需将等式两端乘以-1即变变变变为为为为极极极极大大大大化化化化问题。因为minZ=max(Z)=CTX，令Z= -Z，则maxZmaxZ= = C CT TX XminZminZ=C=CT TX X约束条件中右端常数项非正约束条件中右端常数项非正约束条件中右端常数项非正约束条件中右端常数项非正 两端同乘以 -1 约束条件为不等式约束条件为不等式约束条件为不等式约束条件为不等式 当约束方程

10、为“”时，左端加入一个非负的松松松松弛弛弛弛变变变变量量量量，就把不等式变成了等式；当约束条件为“”时，不等式左端减去一个非负的剩剩剩剩余余余余变变变变量量量量，就把不等式变成了等式。 决策变量决策变量决策变量决策变量x xk k没有非负性要求没有非负性要求没有非负性要求没有非负性要求 令xk=xk-xk， 其中令xk，xk 0，用xk、xk 取代模型中xk四、四、线性性规划划问题的的图解法解法 图解法图解法图解法图解法即是用图示的方法来求解线性规划问题。图解法简单直观，有助于了解线性规划问题求解的基本原理。适用于两个决策变量的线性规划问题满足所有约束条件的解叫可行解，解的集合称之为可行域可行

11、域可行域可行域。即所有约束条件共同围成的区域。1.1.可行域可行域可行域可行域 的确定的确定的确定的确定例例例例1 1的数学模型为的数学模型为的数学模型为的数学模型为：x1=82x2=123x1+4x2=36五边形OABCD内(含边界)的任意一点 (x1，x2) 都是满足所有约束条件的一个解，称之可行解可行解可行解可行解 。maxZ=3x1+5x2 x182x212 3x1+4x236 x1 0, x2 02.最优解的确定最优解的确定确定x1、x2希望目标函数Z=3x1+5x2达到最大，图形中Z=3x1+5x2 代表以Z为参数的一族平行线，即等值线。等值线：位于同一直线上的点的目标函数值相同。

12、 Z=3x1+5x20x1=82x2=123x1+4x2=36最优解：可行解中使目标函数最优(极大或极小)的解本题中：满足目标函数最大的极点是离原点距离最远的点（4,6）Z=3x1+5x224Z=3x1+5x230Z=39Z=42即x1=4，x2=6时Z的值最大为42。 C(4,6)C(4,6)C(4,6)C(4,6)为最优解为最优解为最优解为最优解.解的几种可能性解的几种可能性唯一最优解唯一最优解唯一最优解唯一最优解：只有一个最优点。在可行域的一个顶点处达到 多重最优解多重最优解多重最优解多重最优解：无穷多个最优解。若在两个顶点同时得到最优解，则它们连线上的每一点都是最优解。x1=82x2=

13、123x1+4x2=36如例如例1的数学模型变为的数学模型变为 maxZ=3x1+4x2 x182x212 3x1+4x236 x1 0, x2 0Z=24Z=36Z=12无界解：无界解：无界解：无界解：无可行解：无可行解：无可行解：无可行解：六、线性规划单六、线性规划单纯形纯形法法六、线性规划单六、线性规划单纯形纯形法法1 1 1 1、线性规划单纯形法解的判定（判定方法见课件）：、线性规划单纯形法解的判定（判定方法见课件）：、线性规划单纯形法解的判定（判定方法见课件）：、线性规划单纯形法解的判定（判定方法见课件）： 最优解、无穷多解、无界解、无可行解最优解、无穷多解、无界解、无可行解最优解、

14、无穷多解、无界解、无可行解最优解、无穷多解、无界解、无可行解 2 2 2 2、利用求解、利用求解、利用求解、利用求解 单纯形法小结单纯形法小结1.1.根据实际问题给出数学模型，列出初始单纯形表，进行标准化根据实际问题给出数学模型，列出初始单纯形表，进行标准化根据实际问题给出数学模型，列出初始单纯形表，进行标准化根据实际问题给出数学模型，列出初始单纯形表，进行标准化任一线线线线性性性性规规规规划划划划问题都存在另一与之伴随的线性规划问题是，他们从不同角度对一个实际问题是提出并描述，组成一对互惠为对偶的线性规划问题。第二章第二章 线性规划的对偶理论线性规划的对偶理论一、原问题与对偶问题的对应关系一

15、、原问题与对偶问题的对应关系一、原问题与对偶问题的对应关系一、原问题与对偶问题的对应关系(1) 一个问题中的约束条件个数约束条件个数等于另一个问题的变量数。变量数。(2) 一个问题的目目标标函函数数中中的的系系数数是另外一个问题中约约束束不不等等式式的右端项。的右端项。(3) 约束条件在一个问题是“”，在另一个问题是“”。(4) 目标在一个问题是求极小求极小，在另一个问题是求极大。求极大。 下列的表给出了原问题模型和模型的对应关系，这些也可以看作是一个线性规划原问题转化为对偶问题的一般规律。原问题原问题对偶问题对偶问题目标函数目标函数max目标函数目标函数min原问题原问题(maxZ)与对偶之

16、关系与对偶之关系：原问题原问题原问题原问题( (maxZmaxZ) )口诀口诀口诀口诀: :约束决定变量是反号约束决定变量是反号约束决定变量是反号约束决定变量是反号原问题原问题原问题原问题( (maxZmaxZ) )口诀口诀口诀口诀:变量决定约束是同号变量决定约束是同号变量决定约束是同号变量决定约束是同号原问题原问题对偶问题对偶问题目标函数目标函数min目标函数目标函数max原问题原问题(minS)与对偶之关系与对偶之关系：原问题原问题原问题原问题( (minSminS) )口诀口诀口诀口诀: :约束决定变量是同号约束决定变量是同号约束决定变量是同号约束决定变量是同号原问题原问题原问题原问题(

17、 (minSminS) )口诀口诀口诀口诀:变量决定约束是反号变量决定约束是反号变量决定约束是反号变量决定约束是反号解：依线性规划问题的对偶关系，有：（还可依对偶问题写出原问题）例1 写出下列问题的对偶问题：变量决定约束是同号变量决定约束是同号变量决定约束是同号变量决定约束是同号, ,约束决定变量是反号约束决定变量是反号约束决定变量是反号约束决定变量是反号 max Z=2x1+x2 5x2 15 6x1+2x2 24 x1+x2 5 x1 , x2 0 min w=15y1+24y2+5y3 6y2+y3 2 5y1+2y2+y3 1 y1 , y2 , y3 0s.t. 解：依线性规划问题的

18、对偶关系，有：32134maxyyyZ+=s.t. 1232 1yy2y-332 1 +y4y42321+yyy01y，02y（还可依对偶问题写出原问题）例2 写出下列问题的对偶问题：32143MinxxxS+= s.t. 1321+4xx2x423321+xxx3-23 1+ x xx1,x2,x3 0变量决定约束是反号变量决定约束是反号变量决定约束是反号变量决定约束是反号, ,约束决定变量是同号约束决定变量是同号约束决定变量是同号约束决定变量是同号03y，线性规划的对偶理论包括以下几个基本定理。定理1 （对称性定理）二、二、线性规划的对偶理论线性规划的对偶理论定理2 （弱对偶定理）即对偶问

19、题的对偶是原问题。设x和y分别是原问题和对偶问题的可行解，则必有cxyb定理3 （无界性） 若原问题(对偶问题)为无界解，则其对偶问题(原问题)无可行解。 若原问题有可行解对偶问题无可行解，则原问题一定无界；反之，如对偶问题有可行解原问题无可行解，则对偶问题一定无界。定理4 （可行解是最优解的性质）定理5 （强对偶定理） 设X*是原问题的可行解，Y*是对偶问题的可行解，当CX*=Y*b时， X*与Y*是最优解 。 若原问题有最优解，那么对偶问题也有最优解，且目标函数值相等定理6（互补松弛定理） 在线性规划问题的最优解中，如果对应某一约束条件的对偶对偶对偶对偶变量值为非零变量值为非零变量值为非零

20、变量值为非零，则该约束条件取严格等式严格等式严格等式严格等式；反之如果约束条件取约束条件取约束条件取约束条件取严格不等式严格不等式严格不等式严格不等式，则其对应的对偶变量一定为零对偶变量一定为零对偶变量一定为零对偶变量一定为零。定理6（互补松弛定理） 线性规划原问题及其对偶问题之间存在一对互补的基解，用单纯形法求解线性规划时，迭代的每一步在得到原问题一个基本可行解基本可行解的同时，其：检验数行的-(cj-zj)值是其对偶问题的一个基本解基本解基本解基本解yi ；变换单纯形表变换单纯形表Cj比值CBXBb检验数j= cj-zjx1x2x3x4x52100015/20 0 15/4-15/27/2

21、1001/4-1/23/2010-1/43/2x3x1x2021-17/2000-1/4-1/2此时得原问题最优解此时得原问题最优解此时得原问题最优解此时得原问题最优解: :X X* *=(7/2,3/2,15/2,0,0)=(7/2,3/2,15/2,0,0)T T，Z Z* *=17/2=17/2原问题变量原问题松驰变量对偶问题剩余变量y4、y5对偶问题变量y1、y2 、y3则对偶问题最优解则对偶问题最优解则对偶问题最优解则对偶问题最优解: :Y Y* *=(0,1/4,1/2,0,0)=(0,1/4,1/2,0,0)T T，S S* *=17/2=17/2检验数行的-(cj-zj)值是其

22、对偶问题的一个基本解基本解基本解基本解yi ； 灵敏度分析灵敏度分析，是指对系统或事物因周围条件变化所表现出的敏感性程度的分析。三、灵敏度分析三、灵敏度分析、分析cj变化的影响 目标函数中的系数cj的变化仅仅影响到检验数(cj-zi)的变化。所以将cj 的变化直接反映到最终单纯形表中，只可能出现表中的前两种情况。【例】已知线性规划问题： maxZ=2x1 +x2 5x2 15 6x1 + 2x2 24 x1 + x2 5 x1 , x2 0用单纯形法求得最终单纯形表如下最终单纯形表最终单纯形表Cj比值CBXBb检验数jx1x2x3x4x52100015/20015/4-15/27/21001/

23、4-1/23/2010-1/43/2x3x1x2021-17/2000-1/4-1/2试确定： 目标函数变为max Z=(2+l) x1+x2时， l在什么范围变化，最优解不变； maxZ=2x1 + x2 5x2 15 6x1 + 2x2 24 x1 + x2 5 x1 , x2 0【解】【解】 (b)将目标函数系数的变化直接反映到最终单纯形表中 为使表中解为最优，应有 -1/4-1/4l0 ， -1/2+1/2l0 即得 -1 l12+l100002+l1-17/2l00-1/4-1/2-17/2-7/2l l0 00-1/4-1/4l l-1/2+1/2l l二、分析bi变化的影响 bi

24、的变化在实际问题中表明可用资源的数量发生变化，其变化b反映到最终单纯形表上只引起基变量列数字变化b*。因此灵敏度分析的步骤为：1.由b*=B-1b算出b*，将其加到最终表基变量列的数字上；2.由于其对偶问题仍为可行解（检验行没变），故只需检查原问题是否仍为可行解，再按相应步骤进行。注:此公式是单纯形法利用公式求解的推导结果!问题：问题：B与与B-1分别是什么？分别是什么？以此题为例以此题为例Cj比值CBXBb检验数jy1y2y3y4y5-15-24-500-20-6-110-1-5-2-101y4Y5000-15-24-500检验数j1/4-5/410-1/41/41/215/2011/2-3

25、/2Y2y3-24-517/2-15/200-7/2-3/2初始单纯形表最终单纯形表BB-1原理是：(B|I)经过初等变换可化为(I|B-1)，其中I是单位阵，参见36页又例又例Cj比值CBXBb检验数jx1x2x3x4x52100015051002462010511001x3x4x5000021000初始单纯形表Cj比值CBXBb检验数j= cj-zjx1x2x3x4x52100015/20 0 15/4-15/27/21001/4-1/23/2010-1/43/2x3x1x2021-17/200 0-1/4-1/2B*B-1【例】上例中最终单纯形表最终单纯形表Cj比值CBXBb检验数jx1

26、x2x3x4x52100015/20 015/4-15/27/21001/4-1/23/2010-1/43/2x3x1x2021-17/2000-1/4-1/2 (a)若第2个约束条件右端项增大到32，分析最优解变化； (b)若第2个约束条件变为 6x1+2x224+l，分析l在什么范围内变化，表中基为最优解； maxZ=2x1 + x2 5x2 15 6x1 + 2x2 24 x1 + x2 5 x1 , x2 0 maxZ=2x1 + x2 5x2 15 6x1 + 2x2 32 x1 + x2 5 x1 , x2 0【解解】 (a)第2个约束条件右端项增大到32Cj比值CBXBb检验数j

27、x1x2x3x4x52100015/20015/4-15/27/21001/4-1/23/2010-1/43/2x3x1x2021-17/2000-1/4-1/2因 因表中原问题为非可行解，故用对偶单纯形法继续计算将其加到最终单纯形表的基变量b这一列上得下表注： B-1扩充了检验行，目标值的变化b*=B-1b35/2+1011/2+2-1/2-2-21/2-235/211/2-1/2-21/2 继续迭代得下表Cj比值CBXBb检验数jx1x2x3x4x521000150510 051100120-401-6x3x1x4020-100-100-2最优值maxz*=10即得新解x1=5，x2=0，

28、x3=15，x4=2 ，x5=0【解解】 (b)若第2个约束条件变为 6x1+2x224+lCj比值CBXBb检验数jx1x2x3x4x52100015/2 0 0 15/4-15/27/21001/4-1/23/2010-1/43/2x3x1x2021-17/2 0 0 0-1/4-1/2因将其加到最终单纯形表的基变量b这一数列上得下表15/2+5l/47/2+l/43/2-l/4-17/2-l/4 15/2+5/4l0 l-67/2+1/4l0 l-14 3/2-1/4l0 l6得-6 l6第四章：整数规划与分配问题一、整数规划问题一、整数规划问题一、整数规划问题一、整数规划问题二、规划问

29、题二、规划问题二、规划问题二、规划问题三、分配问题三、分配问题三、分配问题三、分配问题匈牙利法匈牙利法匈牙利法匈牙利法定枝分解法和割平面法定枝分解法和割平面法定枝分解法和割平面法定枝分解法和割平面法整数规划练习整数规划练习1.1.整数规划整数规划整数规划整数规划maxZ=3x1 +2x22x1 +3x2 142x1 +x2 9x1 0, x2 0x1, x2 整数maxZ= 3x1x23x1 -2x2 35x1 4x2 10 2x1 x2 5x1 0, x2 0x1, x2 整数01型整数规划练习型整数规划练习2 2、0 01 1型整数规划模型为：型整数规划模型为：型整数规划模型为：型整数规划

30、模型为： maxZ=8x1+2x2 -4x3-7x4 -5x53x1+3x2+x3 +2x4 +3x5 4 5x1+3x2-2x3 -x4 +x5 4x1 , x2 , x3 , x4 ,x5 =0或或 1【例【例【例【例1 1】背包问题】背包问题】背包问题】背包问题 maxZ=12x1+12x2 +9x3 +16x4 +30x53x1+4x2+3x3 +4x4 +6x5 16 x1 , x2 , x3 ,x4 ,x5 =0或或 1三、分配问题三、分配问题有一份中文说明书，需译成英、日、德、俄四种文字，分别记作：E、J、G、R，现在有甲、乙、丙、丁四人，他们将中文说明书翻译成不同的语种的说明书

31、所需时间如表所示，问应指派何人去完成何工作，使所需总时间最少？指派问题的解法匈牙利法指派问题的解法匈牙利法 匈牙利算法的基本思路：根据定理 1 变换效率矩阵，使矩阵中有足够多的零。若矩阵中存在 m 个不同行不同列的零，就找到了最优解若覆盖变换后的效率矩阵零元素的直线少于m 条，就尚未找到最优解，设法进一步变换矩阵，增加新的零指派问题的解法匈牙利法指派问题的解法匈牙利法794291187131614915144104131522400min24104750111006211130min00102350960607130001023509606071309118(7)131614(9)1514(4

32、)1041315(2)2(4)1047501110(0)6(2)1113(0) (0)(0)(0)(0)第一步：找出效率矩阵行的最小元素，并分别从每行中减去；再找出效率矩阵列中的最小元素，并分别从每列中减去；第二步：看覆盖该矩阵中的所有零元素，至少要多少条直线；（a）从行开始，对只有一个的零元素，打上（），用直线划去所在列（b）再从行开始，对只有一个的零元素，打上（），用直线划去所在行重复（a）（b），可能出现三种情况：重复效率矩阵的每行都有一个打（）的零元素，且位于不同行不同列，只要令对应打（）零元素的xij1，就找到了问题的最优解：打（）的零元素个数小于m，但未被划去的零元素之间存在闭合回

33、路，此时沿着闭合回路的走向，对每个间隔的零元素找一（），然后对所有打（）零元素在所在行，在所在列画一条直线。 矩阵中所有零元素元素或被划去，或打上（）号，但打（）的零元素个数小于m；第第种情况种情况此时令x14=1,x22=1,x31=1,x43=1,其余xij=00(0)10235(0)96(0)6(0)7130Z4+4+9+1128（小时）得问题的最优解为：得问题的最优解为：得问题的最优解为：得问题的最优解为：此题为第此题为第种情况：位于不同行不同列的零元素有四个。种情况：位于不同行不同列的零元素有四个。第第种情况种情况4123104646151252335330000min6020504

34、003010200min1046(4)615(1)25(2)3353(3)6(0)20504003(0)1(0)20(0)打（）的零元素个数小于m，但未被划去的零元素之间存在闭合回路，此时沿着闭合回路的走向，对每个间隔的零元素找一（），然后对所有打（）零元素在所在行，在所在列画一条直线。6020504003010200(0)(0)(0)(0)minZ3+2+1+410（小时）第第种情况（另例）种情况（另例）如果分配问题的效率矩阵为建立线性规划模型为：建立线性规划模型为：建立线性规划模型为：建立线性规划模型为：指派问题的解法匈牙利法指派问题的解法匈牙利法411429131541116141381

35、4415791020500min5911005324100115780min54110003245011528054110003245011528091315(4)(11)161413814(4)157910(2)59110(0)(5)32410(0)11578(0)(0)(0)(0)第第种情况种情况当矩阵中所有零元素都被划去或打上( )号，但打( )号的零元素个数小于m，则需对矩阵做进一步变换：202200-2-23211000542301130803211000542301130803211(0)(0)05423(0)113(0)8054110003245011528(0)(0)(0)a

36、aij ij-u-ui i-v-vj ju ui iv vj j(0)(0)(0)54110003245011528(0)(0)(0)（1）在未被直线覆盖的数字中找一个最小的k（2）对有直线覆盖的行，令ui0，未被直线覆盖的行，令uik（3）对有直线覆盖的列，令vj-k，未被直线覆盖的行，令vj0(0) 此时令x13=1,x22=1,x34=1,x41=1,其余xij=0Z9+4+11+428（小时）得问题的最优解为：得问题的最优解为：得问题的最优解为：得问题的最优解为：3211(0)(0)05423(0)113(0)80补充题补充题1.分配问题甲、乙、丙、丁完成A、B、C、D、E五项任务、要

37、求：（1）E必须完成，其他四项任选三项；（2）其中一人完成两项，其他每人完成一项问：如何安排，总时间最少？第三章运输问题运输问题是线性规划问题的特例。是在几个供应点与几个需求点之间，运输品种、规格、质量等相同的货物时，选择最佳的运输方案，以达到总的运输费用最低或获利的利润最大等目标X XY YZ ZA AB BC C产地产地产地产地：货物发出的地点。销地销地销地销地：货物接收的地点。产量产量产量产量：各产地的可供货量。销量销量销量销量：各销地的需求数量。 运输问题就是研究如何组织调运，既满足各销地的需求，又使总运费最小。一、表式运输模型一、表式运输模型 销地产地A1A2AmB1B2Bnc11c

38、12c1nc21 c22c2ncm1cm2cmn 运价表运价表运价表运价表单位运价单位运价单位运价单位运价 销地产地A1A2Am产量a1a2amB1B2Bn销地b1b2bn x11 x12 x1n x21 x22 x2n xm1 xm xmn产销平衡表产销平衡表产销平衡表产销平衡表运量运量运量运量运输模型表合二为一运输模型表合二为一 销地产地A1A2Am产量a1a2amB1B2Bn销地b1b2bnc11c12c1nc21 c22c2ncm1cm2cmn x11 x12 x1n x21 x22 x2n xm1 xm xmn二、二、运输问题的三种类型运输问题的三种类型 产销平衡产销平衡产销平衡产销

39、平衡 销地产地AmA2A1ama2a1产量BnB2B1bnb2b1销地cmn cm2cm1c2nc22c21 c1nc12c11 xmn xm xm1 x2n x22 x21 x1n x12 x11产大于销产大于销产大于销产大于销 销地产地AmA2A1ama2a1产量BnB2B1bnb2b1销地cmn cm2cm1c2nc22c21 c1nc12c11 xmn xm xm1 x2n x22 x21 x1n x12 x11产小于销产小于销产小于销产小于销 销地产地AmA2A1ama2a1产量BnB2B1bnb2b1销地cmn cm2cm1c2nc22c21 c1nc12c11 xmn xm xm

40、1 x2n x22 x21 x1n x12 x11三、运输问题的求解方法表上作业法三、运输问题的求解方法表上作业法 表上作业法适合于产销平衡的运输问题表上作业法适合于产销平衡的运输问题表上作业法适合于产销平衡的运输问题表上作业法适合于产销平衡的运输问题 求解步骤：求解步骤：求解步骤：求解步骤： 建立运输模型表 找出初始方案（初始基可行解）：（一般来说这个方案不是最优的） 最优性检验 方案调整与改进某饮料在国内有三个生产厂，分布在城市A1、A2、A3,其一级承销商有4个，分布在城市B1、B2、B3、B4，已知各厂的产量、各承销商的销售量及从Ai到Bj的每吨饮料运费为Cij，为发挥集团优势，公司要

41、统一筹划运销问题，求运费最小的调运方案。 例题销地产地B1B2B3B4产量A1 63255A2 75842A3 32973销量 2 314（一）寻求初始方案（一）寻求初始方案 1 1 1 1、西北角法、西北角法、西北角法、西北角法 销地销地产地产地B1B2B3B4产量产量A163255A275 842A332973销量销量2314 初始基可行解：初始基可行解：初始基可行解：初始基可行解：x x1111=2,x=2,x1212=3,x=3,x2323=1,x=1,x2424=1,x=1,x3434=3 =3 ，Z=54Z=542 23 31 11 13 30 0此时出现此时出现此时出现此时出现退

42、化现象退化现象退化现象退化现象2 2、最小元素法、最小元素法 从单位运价表中逐次挑选最小元素，安排运量minai,bj。然后，划去该元素所在行或列： 当产大于销，划去该元素所在列；当产大于销，划去该元素所在列；当产大于销，划去该元素所在列；当产大于销，划去该元素所在列； 当产小于销，划去该元素所在行。当产小于销，划去该元素所在行。当产小于销，划去该元素所在行。当产小于销，划去该元素所在行。 销地销地产地产地B1B2B3B4产量产量A163255A275842A332973销量销量2314 初始基可行解：初始基可行解：初始基可行解：初始基可行解：x x1111=2,x=2,x1313=1,x=1

43、,x1414=2,x=2,x2424=2,x=2,x3131=0,x=0,x3232=3=3，Z=38Z=381 13 30 02 22 22 2此时出现此时出现此时出现此时出现退化现象退化现象退化现象退化现象3 3、伏格尔法、伏格尔法 用次小运价与最小运价之差求出行差与列差。 销地销地产地产地B1B2B3B4产量产量行差行差A163255A275842A332973销量销量2314列差列差 初始基可行解：初始基可行解：初始基可行解：初始基可行解：x x1212=2,x=2,x1313=1,x=1,x1414=2,x=2,x2424=2,x=2,x3131=2,x=2,x3232=1=1，Z=

44、34Z=341 11 11 11 13 31 16 61 11 12 22 25 5 5 51 12 2 2 22 22 22 2（二）判定是否最优，确定调整方案（二）判定是否最优，确定调整方案 销地销地产地产地B1B2B3B4产量产量A163255A275842A332973销量销量23142 2 2 21 1 1 12 2 2 20 0 0 03 3 3 32 2 2 2-21 1 1 1、闭合回路法判定是否最优，确定调整方案、闭合回路法判定是否最优，确定调整方案、闭合回路法判定是否最优，确定调整方案、闭合回路法判定是否最优，确定调整方案2171052 2、位势法判定是否最优，确定调整方案

45、、位势法判定是否最优，确定调整方案 基变量的检验数基变量的检验数基变量的检验数基变量的检验数 ij=cij uivj =0，即cij =ui+vj ，且令u1 =0，计算位势量ui和vj销地销地产地产地B1B2B3B4产量产量A163255A275842A332973销量销量2314uivj0 6 2 5-1-352 2 2 21 1 1 12 2 2 20 0 0 03 3 3 32 2 2 2-2-22 21 17 710105 5销地销地产地产地B1B2B3B4产量产量A16 3 x122 5 5A27584 2A33 2 973销量销量2314+ + + x x12 12 进基，进基，

46、进基，进基，A A1 1B B2 2格增加运量格增加运量格增加运量格增加运量2 2 2 21 1 1 12 2 2 20 0 0 03 3 3 32 2 2 22 2 2 20 0 0 0 2 2 2 23 3 3 31 1 1 12 2 2 2（三）（三）非最非最优方案的方案的调整（不要求）整（不要求） 所有偶点的值都加上调整量；所有偶点的值都加上调整量；所有偶点的值都加上调整量；所有偶点的值都加上调整量； 所有奇点的值都减去调整量；所有奇点的值都减去调整量；所有奇点的值都减去调整量；所有奇点的值都减去调整量； 最小调整量为最小调整量为最小调整量为最小调整量为2 2， x x11 11 离基

47、离基离基离基 获得一个新的运输方案。获得一个新的运输方案。获得一个新的运输方案。获得一个新的运输方案。Z Z3434位势法判定是否最优，确定调整方案位势法判定是否最优，确定调整方案 基变量的检验数基变量的检验数基变量的检验数基变量的检验数 ij=cij uivj =0，即cij =ui+vj ，且令u1 =0，计算位势量ui和vj 销地销地产地产地B1B2B3B4产量产量A163255A275842A332973销量销量2314u ui ivj0 04 43 23 25 5-1-1-1-12 2 2 21 1 1 12 2 2 22 2 2 21 1 1 12 2 2 2243783所有非基变

48、量所有非基变量所有非基变量所有非基变量x xij ij的检验数的检验数的检验数的检验数 ij ij=c cij ij u ui i v vj j00，即得最优解。即得最优解。即得最优解。即得最优解。初始基可行解：初始基可行解：初始基可行解：初始基可行解：x x1212=2,x=2,x1313=1,x=1,x1414=2,x=2,x3131=2,x=2,x3232=1,x=1,x2323=2=2，Z=34Z=34（四）（四）关于退化问题关于退化问题1 1 1 1、初始解退化、初始解退化、初始解退化、初始解退化 即所求初始基变量的个数少于 m+n1。必须补足基变量的个数，否则不能正常解出 m+n个

49、ui 和vj所补基变量的值为所补基变量的值为 0 0 ，补充的原则：，补充的原则：(1)(1)尽量先选运费小的实变量；尽量先选运费小的实变量；(2)(2)补充后不能有某个基变量独占一行一列补充后不能有某个基变量独占一行一列2 2 2 2、迭代过程中出现退化、迭代过程中出现退化、迭代过程中出现退化、迭代过程中出现退化闭合回路中标有闭合回路中标有“ ”的基变量同时有多个达到最小的基变量同时有多个达到最小变换后，有多个原基变量变为变换后，有多个原基变量变为 0 0，选运费最大者为，选运费最大者为出基变量出基变量，其余，其余保留在新的基础解中保留在新的基础解中退化较严重时，可能会出现多次迭代只有值为退

50、化较严重时，可能会出现多次迭代只有值为 0 0 的基变量在转移。的基变量在转移。此时，一要耐心，二要正确选择出变量此时，一要耐心，二要正确选择出变量例：调整运输方案（最小元素法初始方案）例：调整运输方案（最小元素法初始方案）vj销地产地A段B段C段供应量W厂407014056X厂12024011057Y厂8013016077销售量72774121521540401 16 61 16 64 41 1ui5 56 66 61 10 040409090150150-40-402020180180-70-70160160调整运量调整运量销地产地A段B段C段供应量W厂407014056X厂1202401

51、1057Y厂8013016077需求量7277412152156161161641415656161616166161777716161616新方案：新方案：新方案：新方案：x x1111=56,x=56,x2121=16, x=16, x2323=41, x=41, x3131=0,x=0,x3232=77=77，Z=18680Z=186800 0四、产销不平衡问题四、产销不平衡问题 产销平衡的运输问题采取表上作业法求解。产销平衡的运输问题采取表上作业法求解。产销平衡的运输问题采取表上作业法求解。产销平衡的运输问题采取表上作业法求解。 产销不平衡的运输问题需划成产销平衡问题再求解。产销不平衡

52、的运输问题需划成产销平衡问题再求解。产销不平衡的运输问题需划成产销平衡问题再求解。产销不平衡的运输问题需划成产销平衡问题再求解。 产大于销：产大于销：产大于销：产大于销： 产小于销：产小于销：产小于销：产小于销： 虚设一个销地 Bk (多于物资在产地存储)，其运价为0， 销量(存储量)为产销量之差 bk =ai- bj。 虚设一个产地 Al (不足物资的脱销量)，其运价为0，产量(脱销量)为销产量之差 ak = bj - ai 。（一）（一） 产大于大于销（需要量小于供应量）（需要量小于供应量） 增加一个销地增加一个销地增加一个销地增加一个销地 销地销地产地产地A段段B段段C段段产量产量W厂4

53、07014076X厂12024011082Y厂8013016077销量销量7210241235215销地销地产地产地A段段B段段C段段产量产量W厂407014076X厂12024011082Y厂8013016077销量销量7210241235-215D段段00020235235 虚设的需求点虚设的需求点虚设的需求点虚设的需求点需求量总供应量总需求量总供应量总需求量总供应量总需求量总供应量总需求量需求量需求量需求量 （二）（二）产小于销产小于销 增加一个产地增加一个产地增加一个产地增加一个产地销地销地产地产地B1B2B3产量产量W厂407014056X厂12024011082Y厂80130160

54、77虚设虚设Z厂厂销量销量8210261245-21500030 虚设的产地虚设的产地虚设的产地虚设的产地供应量总需求量总供应量总需求量总供应量总需求量总供应量总需求量总供应量供应量供应量供应量 销地销地产地产地A段段B段段C段段产量产量W厂407014056X厂12024011082Y厂8013016077销量销量8210261215245245245销地销地产地产地B1B2B3B4产量产量A19 18 1 10 9A2116818 10A314 12 2166销量销量4975要求：要求：要求：要求：1.1.三种方法寻求初始方案三种方法寻求初始方案三种方法寻求初始方案三种方法寻求初始方案2.

55、2.判定最小元素法是否最优，如不是，找出调整格及调整量；判定最小元素法是否最优，如不是，找出调整格及调整量；判定最小元素法是否最优，如不是，找出调整格及调整量；判定最小元素法是否最优，如不是，找出调整格及调整量；3.3.调整后重复第调整后重复第调整后重复第调整后重复第2 2步骤步骤步骤步骤练习一练习一精品课件精品课件！精品课件精品课件！例1：某仪器公司经销的主要产品之一是糖果。它下面设有三个加工厂，每天的糖果A17t， A24t， A39t， 该公司把这些糖果分别运往四个地区的门市部销售，各地区每天的销售量为： B13t， B26t， B35t ，B46t 。已知从每个加工厂到销售门市部每吨糖果的运价如下表，问如何调动，在满足各门市部销售需要的情况下，使总的运费支出为最少？练习二练习二销地产地B1B2B3B4供应量A1 3113107A2 19284A3741059销售量36562020x11x12x13x14x21x22x23x24x31x32x33x34