运筹学基础复习一课件.ppt

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

2、是一种合理利用资源、合理调配资源的应用数学方法。一、线性规划问题的三个要素一、线性规划问题的三个要素 是指实际系统或决策问题中有待确定的因素，是系统中的可控因素。任何问题都是限定在一定的条件下求解，把各种限制条件表示为一组等式或不等式，称之为。是决策者对决策问题目标的数学描述。如时间最省、利润最大、成本最低。约束条件的基本类型：大于等于“”、等于“”、小于等于“” 目标函数是决策变量的线性函数。二、线性规划模型的构建二、线性规划模型的构建某厂生产甲乙两种产品，各自的零部件分别在A、B车间生产，最后都需在C车间装配，相关数据如表所示： 产品产品车间车间工时单耗工时单耗甲甲 乙乙生产能力生产能力A

3、BC 1 0 0 2 3 48 1236单位产品获利单位产品获利 3 5问如何安排甲、乙两产品的产量，使利润为最大。 要决策的问题是甲、乙两种产品的产量，因此有两个决策变量：设x1为甲产品产量，x2为乙产品产量。 则A车间的能力约束条件表述为 生产这两种产品受到现有生产能力的制约，用量不能突破。 同理，B和C车间能力约束条件为 产品产品车间车间工时单耗工时单耗甲甲 乙乙生产能力生产能力ABC 1 0 0 2 3 48 1236单位产品获利单位产品获利 3 5目标是利润最大化，用Z表示利润，则 甲乙产品的产量不应是负数，否则没有实际意义，这个要求表述为 maxZ= 3x1 +5 x2 x1 8

4、2x2 12 3x1 +4 x2 36 x1 0, x2 0目标函数约束条件产品产品车间车间工时单耗工时单耗甲甲 乙乙生产能力生产能力ABC 1 0 0 2 3 48 1236单位产品获利单位产品获利 3 5某养鸡场所用的混合饲料是由 n 种配料组成。要求这种混合饲料必须含有 m 种不同的营养成份，而且要求每单位混合饲料中第 i 种营养成份的含量不能低于 bi ( i= 1,2, , m）。已知第 i 种营养成份在每单位的第 j 种配料中的含量为 aij , j = 1,2, , n，每单位的第 j 种配料的价格为 cj 。现在要求在保证营养条件的前提下，应采用何种配方，使混合饲料的成本最小.

5、配料配料营养成份营养成份B1 B2 Bn含量含量A1A2Am a11 a12 a1n a21 a22 a2n am1 am2 amnb1b2bm销量销量 c1 c2 cn1x1 + 2x2 + + nxn 设xj 表示在单位混合饲料中，第j 种配料的含量（ j =1,2,n）则有如下的数学模型：配料配料营养成份营养成份B1 B2 Bn含量含量A1A2Am a11 a12 a1n a21 a22 a2n am1 am2 amnb1b2bm价格价格 c1 c2 cn11x1 + 12x2 + + 1nxn b1 21x1 + 22x2 + + 2nxn b2m1x1 + m2x2 + + mnxn

6、 bmx1 0, x2 0 , , xn0 若资料为百分比，则变量也可设为百分比，但要满足：x1 + x2 + + xn线性规划问题的数学模型有各种不同的形式，如 目标函数有和； 约束条件有“”、“”和“”三种情况； 决策变量一般有要求，有的则没有，没有符号要求的称为自由变量。为了求解方便，特规定一种线性规划的标准形式，非标准型可以转化为标准型计算 目标函数 约束条件为， 右端常数项 决策变量 maxZ=c1x1+c2x2+cnxna11x1+a12x2+a1nxn b1a21x1+a22x2+a2nxn b2 am1x1+am2x2+amnxnbmx1,x2,xn 0只需将等式两端乘以-1即

7、问题。因为minZ=max(Z)=CTX，令Z= -Z，则两端同乘以 -1 当约束方程为“”时，左端加入一个非负的，就把不等式变成了等式；当约束条件为“”时，不等式左端减去一个非负的，就把不等式变成了等式。 令xk=xk-xk， 其中令xk，xk 0，用xk、xk 取代模型中xk即是用图示的方法来求解线性规划问题。图解法简单直观，有助于了解线性规划问题求解的基本原理。适用于两个决策变量的线性规划问题满足所有约束条件的解叫可行解，解的集合称之为。即所有约束条件共同围成的区域。x1 =82x2 =123x1 +4 x2 =36x1x24812369五边形OABCD内(含边界)的任意一点 (x1，x

8、2) 都是满足所有约束条件的一个解，称之 。maxZ= 3x1 +5 x2 x1 8 2x2 12 3x1 +4 x2 36 x1 0, x2 02. 最优解的确定最优解的确定确定x1、x2希望目标函数 Z= 3x1 +5 x2达到最大，图形中Z= 3x1 +5 x2 代表以Z为参数的一族平行线，即等值线。等值线：位于同一直线上的点的目标函数值相同。 Z=3x1+5x20 x1 =82x2 =123x1 +4 x2 =36x1x24812369最优解：可行解中使目标函数最优(极大或极小)的解本题中：满足目标函数最大的极点是离原点距离最远的点（4,6）Z=3x1+5x224Z=3x1+5x230

9、Z=39Z=42即x1=4，x2=6时Z的值最大为42。 . 解的几种可能性解的几种可能性只有一个最优点。在可行域的一个顶点处达到无穷多个最优解。若在两个顶点同时得到最优解，则它们连线上的每一点都是最优解。x1 =82x2 =123x1 +4 x2 =36x1x24812369如例如例1的数学模型变为的数学模型变为 maxZ= 3x1 +4 x2 x1 8 2x2 12 3x1 +4 x2 36 x1 0, x2 0S.t.Z=24Z=36Z=12任一问题都存在另一与之伴随的线性规划问题是，他们从不同角度对一个实际问题是提出并描述，组成一对互惠为对偶的线性规划问题。第二章第二章 线性规划的对偶

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

11、束个个 00m原问题原问题(maxZ)与对偶之关系与对偶之关系：原问题原问题对偶问题对偶问题目标函数目标函数min 目标函数目标函数max无无约约束束个个量量变变00n件件条条束束约约个个n个个件件条条束束约约m量量变变无无约约束束个个00m原问题原问题(minS) 与对偶之关系与对偶之关系：解：依线性规划问题的对偶关系，有：（还可依对偶问题写出原问题）例1 写出下列问题的对偶问题：max Z=2x1+x2 5x2 15 6x1 +2x2 24 x1+x2 5 x1 , x2 0min w=15y1+24y2+5y3 6y2+y3 2 5y1 +2y2 +y3 1 y1 , y2 , y3 0

12、s.t. 解：依线性规划问题的对偶关系，有：32134maxyyyZ+-s.t. 1232 1-yy2y-332 1 +-y4y42321+yyy01y，02y（还可依对偶问题写出原问题）例2 写出下列问题的对偶问题：32143MinxxxS+- s.t. 1321+-4xx2x423321-+-xxx3-23 1+ x xx1,x2,x3 003y，线性规划的对偶理论包括以下几个基本定理。定理1 （对称性定理）定理2 （弱对偶定理）即对偶问题的对偶是原问题。设x和y分别是原问题和对偶问题的可行解，则必有cxyb定理3 （无界性） 若原问题(对偶问题)为无界解，则其对偶问题(原问题)无可行解。

13、 若原问题有可行解对偶问题无可行解，则原问题一定无界；反之，如对偶问题有可行解原问题无可行解，则对偶问题一定无界。定理4 （可行解是最优解的性质）定理5 （强对偶定理） 设X*是原问题的可行解，Y*是对偶问题的可行解，当CX*=Y*b时， X*与Y*是最优解 。 若原问题有最优解，那么对偶问题也有最优解，且目标函数值相等定理6（互补松弛定理） 在线性规划问题的最优解中，如果对应某一约束条件的，则该约束条件取；反之如果，则其对应的。定理6（互补松弛定理） 线性规划原问题及其对偶问题之间存在一对互补的基解，用单纯形法求解线性规划时，迭代的每一步在得到原问题一个基本可行解基本可行解的同时，其：检验数

14、行的-(cj-zj)值是其对偶问题的一个yi ；Cj比值CBXBb检验数j= cj-zjx1x2x3x4x52100015/20 0 15/4-15/27/21001/4-1/23/2010-1/43/2x3x1x2021-17/2000-1/4-1/2原问题变量原问题松驰变量对偶问题剩余变量y4、y5对偶问题变量y1、y2 、y3检验数行的-(cj-zj)值是其对偶问题的一个yi ； 灵敏度分析灵敏度分析，是指对系统或事物因周围条件变化所表现出的敏感性程度的分析。、分析cj变化的影响 目标函数中的系数cj的变化仅仅影响到检验数(cj-zi)的变化。所以将cj 的变化直接反映到最终单纯形表中，

15、只可能出现表中的前两种情况。【例】已知线性规划问题： maxZ=2x1 +x2 5x2 15 6x1 + 2x2 24 x1 + x2 5 x1 , x2 0用单纯形法求得最终单纯形表如下Cj比值CBXBb检验数jx1x2x3x4x52100015/20015/4-15/27/21001/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)将目标函数系数的

16、变化直接反映到最终单纯形表中 为使表中解为最优，应有 -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的变化在实际问题中表明可用资源的数量发生变化，其变化b反映到最终单纯形表上只引起基变量列数字变化b*。因此灵敏度分析的步骤为：1.由b*=B-1b算出b*，将其加到最终表基变量列的数字上；2.由于其对偶问题仍为可行解（检验行没变），故只需检查原问题是否仍为可行解，再按相应步骤进行。注:此公式是单纯形法利用公式求解的推导结果

17、!问题：问题：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/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-

18、zjx1x2x3x4x52100015/20 0 15/4-15/27/21001/4-1/23/2010-1/43/2x3x1x2021-17/200 0-1/4-1/2B*B-1110260501B【例】上例中Cj比值CBXBb检验数jx1x2x3x4x52100015/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

19、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检验数jx1x2x3x4x52100015/20015/4-15/27/21001/4-1/23/2010-1/43/2x3x1x2021-17/2000-1/4-1/2因 因表中原问题为非可行解，故用对偶单纯形法继续计算将其加到最终单纯形表的基变量b这一列上得下表-080024320b-222100802/14/102/34/102/14/102/154/51*b注：

20、 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，x3=15，x4=2 ，x5=0 (b)若第2个约束条件变为 6x x1 1+2+2x x2 224+lCj比值CBXBb检验数jx1x2x3x4x52100015/2 0 0 15/4-15/27/21001/4-1/23/2010-1/43/2x3x1x20

21、21-17/2 0 0 0-1/4-1/2因将其加到最终单纯形表的基变量b这一数列上得下表00lb-44445002/14/102/34/102/14/102/154/51*lllllb15/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第四章：整数规划与分配问题maxZ=3x1 +2x22x1 +3x2 142x1 +x2 9x1 0, x2 0 x1, x2 整数maxZ= 3x1x23x1 -2x2 35x1 4x2 10 2x1 x2 5x1 0, x2 0 x1, x2 整数m

22、axZ= 8x1+2x2 -4x3-7x4 -5x53x1 +3x2+x3 +2x4 +3x5 4 5x1 +3x2-2x3 -x4 +x5 4x1 , x2 , x3 , x4 , x5 =0或或 1maxZ= 12x1+12x2 +9x3 +16x4 +30 x53x1 +4x2+3x3 +4x4 +6x5 16 x1 , x2 , x3 ,x4 ,x5 =0或或 1有一份中文说明书，需译成英、日、德、俄四种文字，分别记作：E、J、G、R，现在有甲、乙、丙、丁四人，他们将中文说明书翻译成不同的语种的说明书所需时间如表所示，问应指派何人去完成何工作，使所需总时间最少？任务人员EJGR甲215

23、134乙1041415丙9141613丁78119时间表任务人员EJGR合计甲x11x12x13x141乙x21x22x23x241丙x31x32x33x341丁x41x42x43x441合计1111分配表 匈牙利算法的基本思路：根据定理 1 变换效率矩阵，使矩阵中有足够多的零。若矩阵中存在 m 个不同行不同列的零，就找到了最优解若覆盖变换后的效率矩阵零元素的直线少于m 条，就尚未找到最优解，设法进一步变换矩阵，增加新的零794291187131614915144104131522400min24104750111006211130min0010235096060713000102350960

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

25、（）的零元素个数小于m，但未被划去的零元素之间存在闭合回路，此时沿着闭合回路的走向，对每个间隔的零元素找一（），然后对所有打（）零元素在所在行，在所在列画一条直线。 矩阵中所有零元素元素或被划去，或打上（）号，但打（）的零元素个数小于m；此时令x14=1,x22=1,x31=1,x43=1,其余xij=0任务人员EJGR甲215134乙1041415丙9141613丁78119时间表0(0)10235(0)96(0)6(0)7130Z4+4+9+1128（小时）任务人员EJGR合计甲00011乙01001丙10001丁00101合计1111分配表此题为第此题为第种情况：位于不同行不同列的零元素

26、有四个。种情况：位于不同行不同列的零元素有四个。4123104646151252335330000min6020504003010200min1046(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（小时）如果分配问题的效率矩阵为任务人员EJGR甲21097乙154148丙13141611丁415139时间表

27、任务人员EJGR合计甲x11x12x13x141乙x21x22x23x241丙x31x32x33x341丁x41x42x43x441合计1111分配表01, 2 , 1, 1, 2 , 1, 1min或ijjijiijijijijxnixnjxxCz项任务个人去完成第，不分配第项任务个人去完成第，分配第令jijixij014114291315411161413814415791020500min5911005324100115780min54110003245011528054110003245011528091315(4)(11)161413814(4)157910(2)59110(0)(5

28、)32410(0)11578(0)(0)(0)(0)当矩阵中所有零元素都被划去或打上( )号，但打( )号的零元素个数小于m，则需对矩阵做进一步变换：202200-2-23211000542301130803211000542301130803211(0)(0)05423(0)113(0)8054110003245011528(0)(0)(0)(0)(0)(0)54110003245011528(0)(0)(0)（1）在未被直线覆盖的数字中找一个最小的k（2）对有直线覆盖的行，令ui0，未被直线覆盖的行，令uik（3）对有直线覆盖的列，令vj-k，未被直线覆盖的行，令vj0(0)此时令x13=

29、1,x22=1,x34=1,x41=1,其余xij=0任务人员EJGR甲21097乙154148丙13141611丁415139时间表Z9+4+11+428（小时）3211(0)(0)05423(0)113(0)80任务人员EJGR合计甲00101乙01001丙00011丁10001合计1111分配表1.分配问题甲、乙、丙、丁完成A、B、C、D、E五项任务、要求：（1）E必须完成，其他四项任选三项；（2）其中一人完成两项，其他每人完成一项问：如何安排，总时间最少？ABCDE甲2529314237乙3938262033丙3427284032丁2442362345第三章运输问题运输问题是线性规划问

30、题的特例。是在几个供应点与几个需求点之间，运输品种、规格、质量等相同的货物时，选择最佳的运输方案，以达到总的运输费用最低或获利的利润最大等目标：货物发出的地点。：货物接收的地点。：各产地的可供货量。：各销地的需求数量。 运输问题就是研究如何组织调运，既满足各销地的需求，又使总运费最小。 销地产地A1A2AmB1B2Bnc11c12c1nc21 c22c2ncm1cm2cmn 销地产地A1A2Am产量a1a2amB1B2Bn销地b1b2bn x11 x12 x1n x21 x22 x2n xm1 xm xmn 销地产地A1A2Am产量a1a2amB1B2Bn销地b1b2bnc11c12c1nc2

31、1 c22c2ncm1cm2cmn x11 x12 x1n x21 x22 x2n xm1 xm xmnminjjiba110,.,2 , 1,.,2 , 1,min1111ijmijijnjiijminjijijxnjbxmiaxxcZ 销地产地AmA2A1ama2a1产量BnB2B1bnb2b1销地cmn cm2cm1c2nc22c21 c1nc12c11 xmn xm xm1 x2n x22 x21 x1n x12 x11 minjjiba110,.,2 , 1,.,2 , 1,min1111ijmijijnjiijminjijijxnjbxmiaxxcZ 销地产地AmA2A1ama2a

32、1产量BnB2B1bnb2b1销地cmn cm2cm1c2nc22c21 c1nc12c11 xmn xm xm1 x2n x22 x21 x1n x12 x11 minjjiba110,.,2 , 1,.,2 , 1,min1111ijmijijnjiijminjijijxnjbxmiaxxcZ 销地产地AmA2A1ama2a1产量BnB2B1bnb2b1销地cmn cm2cm1c2nc22c21 c1nc12c11 xmn xm xm1 x2n x22 x21 x1n x12 x11 建立运输模型表 找出初始方案（初始基可行解）：（一般来说这个方案不是最优的） 最优性检验 方案调整与改进某

33、饮料在国内有三个生产厂，分布在城市A1、A2、A3,其一级承销商有4个，分布在城市B1、B2、B3、B4，已知各厂的产量、各承销商的销售量及从Ai到Bj的每吨饮料运费为Cij，为发挥集团优势，公司要统一筹划运销问题，求运费最小的调运方案。 例题销地产地B1B2B3B4产量A1 63255A2 75842A3 32973销量 2 314销地销地产地产地B1B2B3B4产量产量A163255A275 842A332973销量销量2314 从单位运价表中逐次挑选最小元素，安排运量minai,bj。然后，划去该元素所在行或列： 销地销地产地产地B1B2B3B4产量产量A163255A275842A33

34、2973销量销量2314 用次小运价与最小运价之差求出行差与列差。 销地销地产地产地B1B2B3B4产量产量行差行差A163255A275842A332973销量销量2314列差列差销地销地产地产地B1B2B3B4产量产量A163255A275842A332973销量销量2314 ij= cij ui vj =0，即cij =ui +vj ，且令u1 =0，计算位势量ui和vj销地销地产地产地B1B2B3B4产量产量A163255A275842A332973销量销量2314uivj0 6 2 5-1-35销地销地产地产地B1B2B3B4产量产量A16 3 x122 5 5A27584 2A33

35、 2 973销量销量2314 ij= cij ui vj =0，即cij =ui +vj ，且令u1 =0，计算位势量ui和vj 销地销地产地产地B1B2B3B4产量产量A163255A275842A332973销量销量2314vj 即所求初始基变量的个数少于 m+n-1。必须补足基变量的个数，否则不能正常解出 m+n个ui 和vj所补基变量的值为所补基变量的值为 0 0 ，补充的原则：，补充的原则：(1)(1)尽量先选运费小的实变量；尽量先选运费小的实变量；(2)(2)补充后不能有某个基变量独占一行一列补充后不能有某个基变量独占一行一列闭合回路中标有闭合回路中标有“- -”的基变量同时有多个

36、达到最小的基变量同时有多个达到最小变换后，有多个原基变量变为变换后，有多个原基变量变为 0 0，选运费最大者为，选运费最大者为出基变量出基变量，其余，其余保留在新的基础解中保留在新的基础解中退化较严重时，可能会出现多次迭代只有值为退化较严重时，可能会出现多次迭代只有值为 0 0 的基变量在转移。的基变量在转移。此时，一要耐心，二要正确选择出变量此时，一要耐心，二要正确选择出变量vj销地产地A段B段C段供应量W厂407014056X厂12024011057Y厂8013016077销售量727741215215ui销地产地A段B段C段供应量W厂407014056X厂12024011057Y厂801

37、3016077需求量727741215215 虚设一个销地 Bk (多于物资在产地存储)，其运价为0， 销量(存储量)为产销量之差 bk =ai- bj。 虚设一个产地 Al (不足物资的脱销量)，其运价为0，产量(脱销量)为销产量之差 ak = bj - ai 。销地销地产地产地A段段B段段C段段产量产量W厂407014076X厂12024011082Y厂8013016077销量销量7210241235215销地销地产地产地A段段B段段C段段产量产量W厂407014076X厂12024011082Y厂8013016077销量销量7210241235-215D段段00020235235销地销地

38、产地产地B1B2B3产量产量W厂407014056X厂12024011082Y厂8013016077虚设虚设Z厂厂销量销量8210261245-21500030销地销地产地产地A段段B段段C段段产量产量W厂407014056X厂12024011082Y厂8013016077销量销量8210261215245245245销地销地产地产地B1B2B3B4产量产量A19 18 1 10 9A2116818 10A314 12 2166销量销量4975精品课件精品课件！精品课件精品课件！例1：某仪器公司经销的主要产品之一是糖果。它下面设有三个加工厂，每天的糖果A17t， A24t， A39t， 该公司把这些糖果分别运往四个地区的门市部销售，各地区每天的销售量为： B13t， B26t， B35t ，B46t 。已知从每个加工厂到销售门市部每吨糖果的运价如下表，问如何调动，在满足各门市部销售需要的情况下，使总的运费支出为最少？销地产地B1B2B3B4供应量A1 3113107A2 19284A3741059销售量36562020 x11x12x13x14x21x22x23x24x31x32x33x34