第三章运输问题-ppt课件

1、第三章第三章 运输问题运输问题一、运输问题及其数学模型二、表上作业法三、运输问题的进一步讨论四、运用举例第三章2312341一、运输问题及其数学模型一、运输问题及其数学模型s2=27s3=19s1=14供应量供应地运价d1=22d2=13d3=12d4=13需求量需求地6753842759106 引例：引例：运输问题网络图第三章0 xxxxxxxxxxxx13xxx12xxx13xxx22xxx19xxxx27xxxx14xxxxs.t.x6x10 x9x5x7x2x4x8x3x5x7x6zmin3433323124232221141312113424143323133222123121113

2、43332312423222114131211343332312423222114131211供应地约束需求地约束一、运输问题及其数学模型一、运输问题及其数学模型第三章运输问题的描画： 设某种物品有m个产地A1,A2,.,Am，各产地的产量分别是a1,a2,.,am；有n个销地B1,B2,.,Bn，各销地的销量分别为b1,b2,.bn。假定从产地Ai(i=1,2,m)向销地出Bj(jl,2,.n)运输单位物品的运价是cij，问怎样调运这些物品才干使总运费最小?一、运输问题及其数学模型一、运输问题及其数学模型第三章运价表 销地产地B1B2Bn产量A1C11C12C1na1x11x12x1nA2C

3、12C22C2na2x21x22x2n.AmC1mC2mCmnamxm1xm2xmn销量b1b2bm一、运输问题及其数学模型一、运输问题及其数学模型第三章产销平衡运输问题的数学模型表示：j xciBA设ijij njmixnjbxmiaxxCzijmijijnjiijminjijij,.,2 , 1;,.,2 , 10,.2 , 1,.2 , 1min1111 0,ijjiCba其中jiba一、运输问题及其数学模型一、运输问题及其数学模型第三章该模型是一个线性规划模型，可以用单纯形法求解。但是变量数目非常多。如3个产地，4个销地。变量数目会有19个之多。因此应该寻求更简便的解法。为了阐明适于求

4、解运输问题的更好的解法，先分析运输问题数学模型的特点。一、运输问题及其数学模型一、运输问题及其数学模型第三章运输问题数学模型的特点：运输问题数学模型的特点：1运输问题有有限最优解运输问题有有限最优解jibaQnjmiQbaxjiij,.2,1;,.,2,1,是一个可行解。同时，目的函数有下界，且不会趋于负无穷。所以，必存在有限最优解。一、运输问题及其数学模型一、运输问题及其数学模型第三章2运输问题约束条件的系数矩阵运输问题约束条件的系数矩阵111.1111.1.1.11.1.1221111mnmnnxxxxxxA =n 行m 行jmiijeeP系数列向量：TijA)0,.,0,1 ,0,.,0

5、,1 ,0,.,0(第i个第m+ j个一、运输问题及其数学模型一、运输问题及其数学模型第三章由此可知，运输问题具有下述特点： (1)约束条件系数矩阵的元素等于0或1； (2)约束条件系数矩阵的每一列有两个非零元素，这对应于每一个变量在前m个约束方程中出现一次，在后n个约束方程中也出现一次；对产销平衡运输问题，除上述两个特点外，还有以下特点：(3)一切构造约束条件都是等式约束；(4)各产地产量之和等于各销地销量之和。 秩 ( A) =m+n-1运输问题的基可行解中应包含m+n-1个基变量.一、运输问题及其数学模型一、运输问题及其数学模型第三章3.运输问题的解运输问题的解(1)解解x必需满足模型中

6、的一切约束条件；必需满足模型中的一切约束条件；(2)基变量对应的约束方程组的系数列向量线性无关；基变量对应的约束方程组的系数列向量线性无关；(3)解中非零变量解中非零变量xij的个数不能大于的个数不能大于(m+n-1)个，缘由个，缘由是运输问题中虽有是运输问题中虽有(m+n)个构造约束条件，但由于总产量个构造约束条件，但由于总产量等于总销量，故只需等于总销量，故只需(m+n-1)个构造约束条件是线性独立个构造约束条件是线性独立的；的；(4)为使迭代顺利进展，基变量的个数在迭代过程中坚为使迭代顺利进展，基变量的个数在迭代过程中坚持为持为 (m+n-1)个。个。运输问题解的每一个分量，都独一对应其

7、运输表中的运输问题解的每一个分量，都独一对应其运输表中的一个格一个格 填有数字的格填有数字的格 或或 空格空格一、运输问题及其数学模型一、运输问题及其数学模型第三章 销地产地B1B2B3B4产量A141241116826A2210391010A38511622148销量814121448下表给出了例下表给出了例1的一个解。的一个解。一、运输问题及其数学模型一、运输问题及其数学模型第三章二、表上作业法二、表上作业法 表上作业法是一种迭代法，迭代步骤为： 1、先按某种规那么找出一个初始解(初始调运方案)； 2、再对现行解作最优性判别； 3、假设这个解不是最优解，就在运输表上对它进展调整改良，得出个

8、新解； 4、再判别，再改良； 5、直至得到运输问题的最优解为止。 迭代过程中得出的一切解都要求是运输问题的基可行解。第三章例1： 销地产地B1B2B3B4产量A141241116A22103910A38511622销量814121448二、表上作业法二、表上作业法第三章 思绪：为了减少运费，应优先思索单位运价最小(或运距员短)的供销业务，最大限制地满足其供销量。在可供物品已用完的产地或需求已全部满足的销地，以后将不再思索。然后，在余下的供、销点的供销关系中，继续按上述方法安排调运，直至安排完一切供销义务，得到一个完好的调运方案(完好的解)为止。这样就得到了运输问题的一个初始基可行解(初始调运方

9、案)。 由于该方法基于优先满足单位运价(或运距)最小的供销业务，故称为最小元素法。1、初始基可行解最小元素法、初始基可行解最小元素法二、表上作业法二、表上作业法第三章 销地产地B1B2B3B4产量A141241116A22103910A38511622销量81412144882101486所以，初始基可行解为：目的函数值Z246二、表上作业法二、表上作业法第三章练习 销地产地B1B2B3B4产量A1675314A2842727A35910619销量221312131213131912二、表上作业法二、表上作业法第三章在满足约束条件下尽能够的给最左上角的变量最大值. 销地产地B1B2B3B4产量

10、A141241116A22103910A38511622销量8141214488864814所以，初始基可行解为：目的函数值Z3721、初始基可行解西北角法、初始基可行解西北角法二、表上作业法二、表上作业法第三章练习练习 销地产地B1B2B3B4产量A1675314A2842727A35910619销量22131213813131466二、表上作业法二、表上作业法第三章最小元素法，有时按某一最小单位运价优先安排物品调运时，却能够导致不得不采用运费很高的其他供销点，从而使整个运输费用添加。6202455551、初始基可行解沃格尔法、初始基可行解沃格尔法二、表上作业法二、表上作业法第三章对每一个供

11、应地或销售地，均可由它到各销售地或到各供应地的单位运价中找出最小单位运价和次小单位运价，并称这两个单位运价之差为该供应地或销售地的罚数。沃格尔法根本思想： 在罚数最大处采用最小运费调运。 假设罚数的值不大，当不能按最小单位运价安排运输时呵斥的运费损失不大；反之，假设罚数的值很大，不按最小运价组织运输就会呵斥很大损失，故应尽量按最小单位运价安排运输。沃格尔法就是基于这种思索提出来的。二、表上作业法二、表上作业法第三章沃格尔法计算步骤：1) 分别算出各行、各列的罚数。2) 从行、列中选出差额最大者，选择它所在行、列中的最小元素，进展运量调整。3) 对剩余行、列再分别计算各行、列的差额。前往1)、2

12、)。二、表上作业法二、表上作业法第三章 销地产地B1B2B3B4产量A141241116A22103910A38511622销量81412144814所以，初始基可行解为：目的函数值Z244881224二、表上作业法二、表上作业法第三章练习练习 销地产地B1B2B3B4产量A1675314113A284272721312A3591061919销量22131213 销地产地B1B2B3B4产量A1675314A2842727A35910619销量22131213二、表上作业法二、表上作业法第三章 思绪：要断定运输问题的某个解能否为最优解，可仿照普通单纯形法，检验这个解的各非基变量(对应于运输表中

13、的空格)的检验数，假设有某空格(Ai,Bj)的检验数为负，阐明将xij变为基变量将使运输费用减少，故当前这个解不是最优解。假设一切空格的检验数全非负，那么不论怎样变换解均不能使运输费用降低，即目的函数值已无法改良，这个解就是最优解。 以最小元素法的初始解为例。假设产地A1供应1个单位的物品给销地B1。那么解的变化和目的函数的变化如何。2、解的最优性检验闭回路法、解的最优性检验闭回路法二、表上作业法二、表上作业法第三章 销地产地B1B2B3B4产量A141241116A22103910A38511622销量814121448821014861211012-1二、表上作业法二、表上作业法第三章 由

14、此可知，为了求某个空格(非基变量)的检验数，先要找出它在运输表上的闭回路，这个闭回路的顶点，除这个空格外，其它均为填有数字的格(基变量格)，它是由程度线段和竖直线段依次联接这些顶点构成的一封锁多边形。每个空格都独一存在这样的一条闭回路。二、表上作业法二、表上作业法第三章某空格的检验数是以该空格为第一个顶点，某回路的某空格的检验数是以该空格为第一个顶点，某回路的奇数顶点运价和减去其偶数顶点运价和。奇数顶点运价和减去其偶数顶点运价和。二、表上作业法二、表上作业法B1B2B3B4A1A2A3特征特征:1. 每个顶点都是转角点每个顶点都是转角点.2. 每一边都是程度或垂直的每一边都是程度或垂直的.3.

15、 每一行每一行(或列或列)假设有闭回路的顶假设有闭回路的顶点点,那么必有两个那么必有两个.第三章 位于闭回路上的一组变量，它们对应的运输问题约束条件的系数列向量线性相关，因此在运输问题基可行解的迭代过程中，不允许出现全部顶点由填有数字的格构成的闭回路。 这就是说，在确定运输问题的基可行解时，除要求非零变量的个数为(mn1)个外，还要求运输表中填有数字的格不构成闭回路。二、表上作业法二、表上作业法第三章 销地产地B1B2B3B4产量A167531414557A284272781369A35910619-11-3613销量22131213 销地产地B1B2B3B4产量A167531414A2842

16、7278136A35910619613销量22131213例：确定以下可行解的检验数例：确定以下可行解的检验数二、表上作业法二、表上作业法第三章原问题设其对偶变量为：njmixnjbxmiaxxCzijmijijnjiijminjijij,.,2 , 1;,.,2 , 10,.2 , 1,.2 , 1min1111),.,.,(2121nmvvvuuuY 2、解的最优性检验对偶变量法、解的最优性检验对偶变量法二、表上作业法二、表上作业法第三章原问题系数矩阵：原问题系数矩阵：111.1111.1.1.11.1.1221111mnmnnxxxxxxA =m 行行n 行行u1。umv1。 vn二、表

17、上作业法二、表上作业法第三章对偶问题:思索原问题变量xj的检验数为：符号不限,.2 , 1,.2 , 1max11jiijjiminjjjiivunjmicvuvbuazjjjBjjjjYPcPBCczc1jmiijeeP二、表上作业法二、表上作业法第三章假设已得到一个基可行解，其基变量为：那么有：ssjijijixxx,.,2211s=m+n-1ssssjijijijijijicvucvucvu.22221111那么运输问题变量xij的检验数为：)(),.,.,(2121jiijijnmijijijijijijvucPvvvuuucYPczc二、表上作业法二、表上作业法第三章方程组有m+n-

18、1个方程。由于运输表中每行和每列均有基变量，因此上面方程组含有全部m+n个对偶变量。故解不独一，其解称为位势。假设上述方程的某组解满足对偶问题的一切条件，即：此时，原问题与对偶问题均可行，故到达最优。其解分别为：0)(jiijijvucTjijijiTNBssxxxXXX)0,.,0 , 0 ,.,(),(2211二、表上作业法二、表上作业法第三章例：例： 销地产地B1B2B3B4产量UiA141241116A22103910A38511622销量814121448Vj82101486二、表上作业法二、表上作业法第三章练习题练习题 销地产地B1B2B3B4产量A167531414557A284

19、272781369A35910619-11-3613销量22131213 销地产地B1B2B3B4产量A167531414A28427278136A35910619613销量22131213二、表上作业法二、表上作业法第三章 改良的方法是在运输表中找出这个空格对应的闭回路，在满足一切约束条件的前提下，使xij尽量增大并相应调整此闭回路上其它顶点的运输量，以得到另一个更好的基可行解。3、解的改良闭回路调整法、解的改良闭回路调整法二、表上作业法二、表上作业法第三章 解改良的详细步骤解改良的详细步骤(1)以以xij为换入变量，找出它在运输表中的闭回路；为换入变量，找出它在运输表中的闭回路；(2)以空

20、格以空格(Ai,Bj)为第一个奇数顶点，沿闭回路的顺为第一个奇数顶点，沿闭回路的顺(或或逆逆)时针方向前进，对闭回路上的顶点依次编号；时针方向前进，对闭回路上的顶点依次编号；(3)在闭回路上的一切偶数顶点中，找出运输量最小的顶在闭回路上的一切偶数顶点中，找出运输量最小的顶点点(格子格子)，以该格中的变量为换出变量；，以该格中的变量为换出变量；(4)以换出变量的运输量为调整量，将该闭回路上一切奇以换出变量的运输量为调整量，将该闭回路上一切奇数顶点处的运输量都添加这一数值，一切偶数顶点处的运输数顶点处的运输量都添加这一数值，一切偶数顶点处的运输量都减去这一数值，从而得出一新的运输方案。该运输方案量

21、都减去这一数值，从而得出一新的运输方案。该运输方案的总运费比原运输方案减少，改动量等于换出变量的检验数。的总运费比原运输方案减少，改动量等于换出变量的检验数。 然后，再对得到的新解进展最优性检验，加不是最优然后，再对得到的新解进展最优性检验，加不是最优解，就反复以上步骤继续进展调整，不断到得出最优解为止。解，就反复以上步骤继续进展调整，不断到得出最优解为止。二、表上作业法二、表上作业法第三章 销地产地B1B2B3B4产量A141241116A22103910A38511622销量814121448例：821014861211012-1二、表上作业法二、表上作业法第三章 销地产地B1B2B3B4

22、产量A141241116A22103910A38511622销量814121448例：821214840229121由于一切非基变量的检验数全非负，故这个解为最优解。又由于非基变量有零检验数，所以有无穷多最优解。二、表上作业法二、表上作业法第三章练习题练习题 销地产地B1B2B3B4产量A167531414A28427278136A35910619613销量22131213二、表上作业法二、表上作业法练习题练习题第三章练习题练习题 销地产地B1B2B3B4产量A167531414557A284272781369A35910619-11-3613销量22131213二、表上作业法二、表上作业法练

23、习题练习题第三章练习题练习题 销地产地B1B2B3B4产量A16753141455-4A284272721312-2A35910619681113销量22131213二、表上作业法二、表上作业法第三章 销地产地B1B2B3B4产量A167531415513A2842727213122A35910619198114销量22131213 销地产地B1B2B3B4产量A1675314113A284272721312A3591061919销量22131213答案答案二、表上作业法二、表上作业法第三章1假设运输问题的某一基可行解有几个非基变量的检验数均为负，在继续进展迭代时，取它们中的任一变量为换入变量

24、均可使目的函数值得到改善，但通常取小于零的检验数中最小者对应的变量为换入变量。 2当迭代到运输问题的最优解时，假设有某非基变量的检验数等于零，那么阐明该运输问题有多重(无穷多)最优解。 4、需求阐明的几个问题、需求阐明的几个问题二、表上作业法二、表上作业法第三章3二 退化 某一基变量 的值为0初始解 在确定初始解的供需关系时，假设在确定i, j 的数字时，要划去第i行,第j列。为使在产销平衡表上有m+n-1个数字格，须在第i 行或j列中 非i,j ) 选一数字格为0。退化解 闭回路中有 - 标志中有两个或以上相等的最小数。调整后出现退化解，必需在一数字格中填入0，以阐明其为基变量。二、表上作业

25、法二、表上作业法第三章三、运输问题的进一步讨论三、运输问题的进一步讨论 上一节讲述的运输问题的算法，是以总产量等于总销量(产销平衡)为前提的。实践上，在很多运输问题中，总产量不等于总销量。 第三章0,ijjiCba其中njmixnjbxmiaxxCzijmijijnjiijminjijij1 ,10,.2 , 1,.2 , 1min1111 表上作业法 以产销平衡 为前提。jiba1、产销不平衡的运输问题、产销不平衡的运输问题三、运输问题的进一步讨论三、运输问题的进一步讨论第三章2321341s2=27s3=19d1=22d2=13d3=12d4=13s1=14供应量供应地运价需求量需求地67

26、53842759106 例：假设供应量大于需求量例：假设供应量大于需求量+55d5=5 假想销地0 0 0s3=24三、运输问题的进一步讨论三、运输问题的进一步讨论第三章0,.2 , 1,.2 , 1min1111ijmijijnjiijminjijijxnjbxmiaxxCzjiba 产大于销 产销不平衡产销平衡模型：三、运输问题的进一步讨论三、运输问题的进一步讨论第三章设 为Ai的储存量。1, nixmiaxxxinjijninjij,.,2 , 1111,1jininijmiijbaxnjbx11,1,.,2 , 1将多余物原地储存。令：101njnjCCijij三、运输问题的进一步讨论

27、三、运输问题的进一步讨论第三章111njjmiiba了解： 产 销 假想有一销地 j=n+1 销量为 运价 njjmiiba1101,niC01,.2, 1,.2, 1min111111 ijmijijnjiijminjijijxnjbxmiaxxCz模型：三、运输问题的进一步讨论三、运输问题的进一步讨论第三章 销地产地B1B2BnBn+1 （贮存） 产量A1C11C12C1n0a1x11x12x1nx1,n+1A2C12C22C2n0a2x21x22x2nx2 ,n+1.AmC1mC2mCmn0amxm1xm2xmnxm ,n+1销量b1b2bma- b三、运输问题的进一步讨论三、运输问题的

28、进一步讨论第三章例： 某市有三个造纸厂A1，A2，A3，其纸的产量分别为8，5和9个单位，有4个集中用户B1，B2，B3，B4，其需用量分别为4，3，5和6个单位。由各造纸厂到各用户的单位运价如表315所示，请确定总运费最少的调运方案。 销地产地B1B2B3B4产量A1312348A2112595A367159销量4356三、运输问题的进一步讨论三、运输问题的进一步讨论第三章 解：由于总产量22大于总销量18，故本问题是个产销不平衡运输问题。添加一假想销地B5，用表上作业法求解。 销地产地B1B2B3B4B5(贮存) 产量A13123408A21125905A3671509销量43564三、运

29、输问题的进一步讨论三、运输问题的进一步讨论第三章 销地产地B1B2B3B4B5(贮存)产量A13123408418634A211259050302-8A3671509-2954-4销量43564 销地产地B1B2B3B4B5(贮存)产量A1312340844A21125905032A367150954销量43564三、运输问题的进一步讨论三、运输问题的进一步讨论第三章2、有转运的运输问题、有转运的运输问题在以上讨论中，假定物品由产地直接运送到销售目的地，不经中间转运。但是，经常会遇到这种情形：需先将物品由产地运列某个中间转运站(能够是另外的产地、销地或中间转运仓库)，然后再转运到销售目的地。有

30、时，经转运比直接运到目的地更为经济。因此，在决议运输方案时有必要把转运也思索进去。三、运输问题的进一步讨论三、运输问题的进一步讨论第三章2、有转运的运输问题、有转运的运输问题第三章转运量 t1t2t3t4t5t6t7A2A3A1a2=27a3=19a1=14供应量需求量B2B3B4B1a5=0a6=0a4=0a7=0A2A3A1b4=22b5=13b6=12b7=13B2B3B4B1b1=0b2=0b3=0转运量 t1t2t3t4t5t6t7第三章假设单位运转费用为ti，那么线性规划模型为：7711767623232121171713131212.mintctcxcxcxcxcxcxcz717

31、171iiijiiijjijijtcxc7,.,2 , 1, 022144746454342414171615141312144746454342411171615141312jixtxxxxxxtxxxxxxtxxxxxxtxxxxxxij三、运输问题的进一步讨论三、运输问题的进一步讨论第三章7711767623232121171713131212.mintctcxcxcxcxcxcxcz717171iiijiiijjijijtcxc7,.,2 , 1, 022144746454342414171615141312144746454342411171615141312jixtxxxxxxtx

32、xxxxxtxxxxxxtxxxxxxij141716151413121xxxxxxt141716151413121QxxxxxxtQ1417161514131211QxxxxxxxQxxxxxxxQxxxxxxxQxxxxxxx22746454443424147161514131211147464544434241717171iiijijijQcxciiicx的系数为注意717171)(iiiijiiijjijijxQcxc第二项为常数，对求解结果无影响，可去掉。第三章7171minijijijxcz1417161514131211QxxxxxxxQxxxxxxxQxxxxxxxQxxxxx

33、xx227464544434241471615141312111474645444342417,.,2 , 1, 0jixij模型变为以下方式：这是一个产销平衡运输问题的数学模型。可以列出其运价表，用表上作业法求解。 销地产地A1A2A3B1B2B3B4产量A1A2A3B1B2B3B4销量其运价表方式如下留意其中对角线上的运价值：第三章建立普通意义上的数学模型，设：建立普通意义上的数学模型，设：ai：第：第i个产地的产量个产地的产量(净供应量净供应量)；bj：第：第j个销地的销量个销地的销量(净需求量净需求量)；xij：由第：由第i个发送地运到第个发送地运到第j个接纳地的物品数量；个接纳地的物

34、品数量；cij：由第：由第i个发送地到第个发送地到第j个接纳地的单位运价，个接纳地的单位运价，ti：第：第i个地点转运物品的数量；个地点转运物品的数量；ci：第：第i个地点转运单位物品的费用。个地点转运单位物品的费用。 将产地和销地一致编号，并把产地排在前面。销地排在将产地和销地一致编号，并把产地排在前面。销地排在后面，那么有：后面，那么有：第三章nmiiinmjiinmijjijijtcxcz111min令：令：iiitQxjjjtQx建立数学模型：建立数学模型：)(,.,2 , 1, 0,.,2, 1,.,.,.,2 , 1,.,.,.,2, 1,.,.,.,2 , 1,.,., 1, 1

35、21, 1, 121,1,1,21,1,1,21jinmjixnmmmitbxxxxxmjtxxxxxnmmmitxxxxxmitaxxxxxijjjjnmjjjjjjjjnmjjjjjjinmiiiiiiiiinmiiiiiii第三章注：一切i=j，cij=-ci第三章第三章a1a5b1b5Qc1c5c11c55 例：如下图是一个运输系统，它包括二个产地例：如下图是一个运输系统，它包括二个产地1和和2、二个、二个销地销地(4和和5)及一个中间转运站及一个中间转运站(3)，各产地的产量和各销地的销，各产地的产量和各销地的销量用相应节点处箭线旁的数字表示，节点联线上的数字表示其量用相应节点处箭线

36、旁的数字表示，节点联线上的数字表示其间的运输单价，节点旁的数字为该地的转运单价，试确定最优间的运输单价，节点旁的数字为该地的转运单价，试确定最优运输方案。运输方案。第三章 销地产地A1A2B3C4C5产量A1A2B3C4C5销量第三章 销地产地A1A2B3C4C5产量A1-4532M60A25-12M490B332-35550C42M5-3650C5M456-550销量5050508070第三章运用最小元素法，求初始运输方案，如下表：最优运输方案如下表：302020第三章一、回答以下问题1、在运输问题数学模型中，为什么模型的(m+n)个约束中最多只需(m+n-1)个是独立的?2试述用最小元素法

37、确定运输问题的初始基可行解的根本思绪。3如何用闭回路法求检验数？4 沃格尔法的根本思想是什么？什么是罚数？5在解的改良过程中，如何确定调整量？6如何把一个产销不平衡的运输问题(含产大于销和销大于产)转化为产销平衡的运输问题。练习题练习题第三章二、判别以下说法能否正确(1)运输问题是一种特殊的线性规划模型，因此求解结果也能够出现以下四种情况之一：有独一最优解，有无穷多最优解，无界解，无可行解；(2)在运输问题中，只需给出一组合(m+n-1)个非零的xij，且满足xij=ai， xij=bj，就可以作为一个初始基可行解；(3)表上作业法本质上就是求解运输问题的单纯形法；(4)按最小元素法(或伏格尔

38、法)给出的初始基可行解，从每一空格出发可以找出而且仅能找出独一的闭回路；练习题练习题第三章(5)假设运输问题单位运价表的某一行(或某一列)元素分别加上一个常数k，最优调运方案将不会发生变化；(6)假设运输问题单位运价表的某一行(或某一列)元素分别乘上一个常数k，最优调运方案将不会发生变化；(7)当一切产地产量和销地的销量均为整数值时，运输问题的最优解也为整数值1，2，6不对练习题练习题第三章三、用位势法对偶变量法求其检验数。三、用位势法对偶变量法求其检验数。练习题练习题第三章四、运用举例四、运用举例例 1 、某飞机制造厂消费一种民用喷气式飞机，消费的最后阶段是制造喷气发动机，以及把发动机安装到

39、已完成的飞机骨架上一种很快的操作。为了不误合同规定的交货期，第一.二.三.四月必需安装发动机的台数分别为：10 ,15, 25 ,20。但受消费才干等条件的限制，这些月份的最高消费台数分别为：25,35 ,30 , 10。每月单台发动机的存储费用为1.5万元。知一、二、三、四月份的单台消费费用各为：108 、111、 110、113万元。试安排这四个月的消费方案，使消费费用和存储费用之和最小。 1建立此问题的普通LP模型。 2把此问题作为运输问题来处置，试建立相应的运输表格。 3求此“运输问题的最优解。第三章 解：1设xi表示第i个月消费发动机的台数，yi表示第个月的存储台数，那么普通LP模型为：0,1030352570502510)(5 . 1113110111108min43214432133212211143214321iiyxxxxxyxxxxyxxxyxxyxyyyyxxxx四、运用举例四、运用举例第三章个月发动机的安装。第收点个月发动机的生产。第设发点jjii、)2(用之和。月的单台发动机存储费存储到第月生产第个月的单台生产费用与第数。个月安装的发动机的台个月生产供第第j、iicjixijij 由于不能缺货，并思索到是不平衡问题虚设收点5建立如下运输表格四、运用举例四、运用举例第三章：计算得最优生产安排为1041020352