运筹学 第四章 运输问题

1、运输问题v运输问题及其数学模型v运输问题的表上作业法v运输问题的进一步讨论例1：某部门有3个生产同类产品的工厂（产地），生产的产品由4个销售点（销地）出售，各工厂的生产量、各销售点的销售量（假定单位均为t）以及各工厂到各销售点的单位运价（元/t）示于下表中要求研究产品如何调运才能使总运费最小 4.1 运输问题及其数学模型单位 销地 运价产地产量2910291342584257销量38464321 BBBB321AAAA2A3B2A1B3B4B1s2=5s3=7d1=3d2=8d3=4d4=6s1=9供应量供应地运价需求量需求地2910213428425运输问题网络图运输问题网络图 )4 . 3

2、 . 2 . 1, 3 . 2 . 1(06483759524824371092min342414332313322212312111343332312423222114131211343332312423222114131211jixxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxZxijij 约约束束条条件件：目目标标函函数数：为为运运量量设设产量约束销量约束运输问题的一般提法是：设某种物资有 个产地m,1A,2A,mA各产地的产量是;,21maaa有 个销地,1B,2B,nBn各销地的销量是.,21nbbb假定从产地 ),2, 1(miAi到销地), 2 , 1(

3、njBj运输单位物品的运价是 ，问ijc怎样调运这些物品才能使总运费最小？ 销地产地产量销 量1A2AmA1B2BnB11c12cnc111x12xnx121c22cnc221x22xnx21mc2mcmnc1mx2mxmnx1b2bnb1a2ama运价表 ) ( 0min11ijjijijiijminjijijxbabxaxxcZ当产销平衡时，其模型如下：0,0,0ijijabc假设：当产大于销时，其模型是： ) ( 0min11ijjijijiijminjijijxbabxaxxcZ当产小于销时，其模型是：min ()0ijijijiijjijijZc xxaxbabx 1 1、平衡运输问

4、题必有可行解，也、平衡运输问题必有可行解，也必有最优解；必有最优解；运输问题数学模型的特点运输问题数学模型的特点证明 记.11dbaminjji则令dbaxjiij), 2 , 1;, 2 , 1(njmi则 为运输问题的一个可行解。事实上：ijxnjijinjnjjiijabdadbax111), 2 , 1(mimijijmimijiijbadbdbax111), 2 , 1(nj又因. 0, 0jiba所以. 0ijx故 是一组可行解。ijx又因为总费用不会为负值（存在下界）。这说明，运输问题既有可行解，又必然有下界存在，因此一定有最优解存在。 2 2、运输问题约束条件的系数矩阵、运输问

5、题约束条件的系数矩阵运输问题数学模型的特点运输问题数学模型的特点对运输问题数学模型的结构约束加以整理，可知其系数矩阵具有下述形式：m行n行1运输问题是一个具有mn个变量和n+m个等型约束的线性规划问题。 （41）mnmmnnxxxxxxxxx,;,212222111211jmiijeep), 2 , 1;, 2 , 1(njmi() 1() 1() 1000110000101000ijimjmnmnmnpee2运输问题约束方程组的系数矩阵是一个只有0和1两个数值的稀疏矩阵,其中1的总数为 2mn 个。3、约束条件系数矩阵的每一列有两个非零元素，这对应于每一个变量在前m个约束方程中出现一次，在后

6、n个约束方程中也出现一次4、约束条件系数矩阵的秩是m+n-1。即运输问题的基变量总数是m+n-1证明：因A的前m行对应元素的和与后n行对应元素的和相等，恰好都是：nmE) 1 , 1 , 1 (1所以A的行向量是线性相关的。从而 r(A)m+n.去掉A的第一行，并取如下m+n-1列，得到m+n-1阶子式1112121311|00010000001000000110100111010000001000nmDp pp ppp 所以 r(A)=m+n-1.对于产销平衡运输问题，除了上述特点外，还有以下特点： 1 所有结构约束条件都是等式约束 2 各产地产量之和等于各销地销量之和 3 3、运输问题的解

7、、运输问题的解运输问题数学模型的特点运输问题数学模型的特点运输问题是一种线性规划问题。前面讲述的单纯形法是求解线性规划问题十分有效的一般方法，因而可用单纯形法求解运输问题。但是当用单纯形法求解运输问题时，先得在每个约束条件中引入一个人工变量，这样一来，即使对于m=3、n=4这样简单的运输问题，变量数目也会达到19个之多。因此，我们利用运输问题数学模型的特点，引入了表上作业法来求解运输问题 4.2 用表上作业法求解运输问题表上作业法的基本思想：先设法给出一个初始方案,然后根据确定的判别准则对初始方案进行检查、调整、改进，直至求出最优方案，如下图所示。初始化最优性检验迭代（Iteration）最优

8、？yesSTOPno这和单纯形法的求解思想完全一致，但是具体的作法则更加简捷。例1 某部门有3个同类型的工厂（产地），生产的产品由4个销售点出售，各工厂的生产量、各销售点的销售量（假定单位为t）以及各工厂到销售点的单位运价（元/t）示于表4-2中，问如何调运才能使总运费最小？ 销地产地产量4124111621039108511622销 量8141214481A2A1B2B3B4B3A表 4-211x12x13x14x21x22x23x24x31x32x33x34x34333231242322213141141312116115893102114124minxxxxxxxxxxxxxczijij

9、ij4 , 3 , 2 , 1; 3 , 2, 1, 01412148221016342414332313322212312111343332312423222114131211jixxxxxxxxxxxxxxxxxxxxxxxxxij该运输问题的数学模型为：可以证明：约束矩阵的秩 r (A) = m +n -1.基变量的个数为 m+n-1.表上作业法v计算步骤：1、给出初始方案2、检验是否最优3、调整调运方案 , Go to 2表上作业法v计算步骤：1、给出初始方案2、检验是否最优3、调整调运方案 , Go to 2下面介绍三种常用的方法。一、给出运输问题的初始可行解（初始调运方案）l最小元

10、素法l西北角法l沃格尔(Vogel)法1。最小元素法思想：优先满足运价（或运距）最小的供销业务。 销地产地产量 4124111610398511622销 量141214481A2A1B2B3B4B3A表 3-2228810 销地产地产量 412411162109108511622销 量 81414481A2A1B2B3B4B3A表 3-23210128 销地产地产量 412112109108511622销 量 8141214481A2A1B2B3B4B3A表 3-232104161068 销地产地产量 4121182109108116销 量 81214481A2A1B2B3B4B3A表 3-2

11、321041610651422148 销地产地产量 412118210910811销 量 812481A2A1B2B3B4B3A表 3-23210416106514221486146 销地产地产量 4128210910811销 量 812481A2A1B2B3B4B3A表 3-2321041610651422148614611此时得到一个初始调运方案（初始可行解）：,1013x, 614x, 821x, 223x,1432x, 834x其余变量全等于零。总运费为（目标函数值）3141ijijijxcz246685143228116410此解满足所有约束条件，且基变量（非零变量）的个数为6（等于

12、m+n-1=3+4-1=6). 西北角法西北角法是优先满足运输表中西北角（左上角）上空格的供销需求。 销地产地产量41241121039108511622销 量141214481A2A1B2B3B4B3A表 3-281611x 销地产地产量 41241121039108511622销 量141214481A2A1B2B3B4B3A表 3-281688 销地产地产量 41241121039108511622销 量1214481A2A1B2B3B4B3A表 3-28168812x14 销地产地产量 41241121039108511622销 量141214481A2A1B2B3B4B3A表 3-2

13、816886 销地产地产量 412411210398511622销 量141214481A2A1B2B3B4B3A表 3-281688622x10 销地产地产量 412411210398511622销 量141214481A2A1B2B3B4B3A表 3-28168861064 销地产地产量 412411210398511622销 量1414481A2A1B2B3B4B3A表 3-2816886106423x12 销地产地产量 412411210398511622销 量141214481A2A1B2B3B4B3A表 3-281688610648 销地产地产量 4124112103985116销

14、 量141214481A2A1B2B3B4B3A表 3-2816886106432x822 销地产地产量 4124112103985116销 量141214481A2A1B2B3B4B3A表 3-28168861064822814 销地产地产量 4124112103985116销 量1412481A2A1B2B3B4B3A表 3-2816886106482281434x14 销地产地产量 4124112103985116销 量141214481A2A1B2B3B4B3A表 3-28168861064822814此时得到一个初始调运方案（初始可行解）：, 811x, 812x, 622x, 42

15、3x, 833x,1434x其余变量全等于零。总运费为（目标函数值）3141ijijijxcz3726141183410612848此解满足所有约束条件，且基变量（非零变量）的个数为6（等于m+n-1=3+4-1=6). 沃格尔（Vogel)法初看起来，最小元素法十分合理。但是，有时按某一最小单位运价安排物品调运时，却可能导致不得不采用运费很高的其他供销点，从而使整个运输费用增加。沃格尔法的思想： 对每一个供应地或销售地，均可由它到各销售地或到各供应地的单位运价中找出最小单位运价和次小单位运价，并称这两个单位运价之差为该供应地或销售地的罚数。若罚数的值不大，当不能按最小运价安排运输时造成的运费

16、损失不大；反之，如果罚数的值很大，不按最小运价组织运输就会造成很大的损失，故应尽量按最大罚数安排运输。销 地产地产量行罚数1234124111602103910181161销 量8121448列罚数12513231A2A1B2B3B4B3A51422148销 地产地产量行罚数123 412411160021039101185112212销 量8141248列罚数12513221331A2A1B2B3B4B3A8146146销 地产地产量行罚数123 41241116000103911185112212销 量141248列罚数125132213321 21A2A1B2B3B4B3A8146146

17、281082销 地产地产量行罚数456 41211710396851122销 量1448列罚数412561A2A1B2B3B4B3A814614628108241216124销 地产地产量行罚数456 412117010360851122销 量1448列罚数4125 261A2A1B2B3B4B3A81461462810824121612494此时得到一个初始调运方案（初始可行解）：,1213x, 414x, 821x, 224x3214,x, 834x其余变量全等于零。总运费为（目标函数值）3141ijijijxcz244685149228114412此解满足所有约束条件，且基变量（非零变量

18、）的个数为6（等于m+n-1=3+4-1=6).比较上述三种方法给出的初始基可行解，以沃格尔法给出的解的目标函数值最小，最小元素法次之，西北角法解的目标函数值最大。 一般说来，沃格尔法得出的初始解的质量最好，常用来作为运输问题最优解的近似值。 销地产地产量 414681250837514销 量6563201A2A1B2B3B4B3A课堂练习课堂练习表上作业法v计算步骤：1、给出初始方案2、检验是否最优3、调整调运方案 , Go to 2二、解的最优性检验前面得到了初始基可行解，一般来说此解并非最优。下面介绍最优性检验的两种方法。1 闭回路法(Cycle method)2 对偶变量法（dual

19、variable method）也称为位势法补充：闭回路的数学定义补充：闭回路的数学定义定义：定义：凡是能排成凡是能排成1 112222311 12 122321,.,.,ssssssi ji ji ji ji ji ji ji ji ji ji ji jxxxxxxxxxxxx或形式的变量的集合称为一个闭回路，并将这些变量称为这形式的变量的集合称为一个闭回路，并将这些变量称为这个闭回路的顶点。个闭回路的顶点。由此可以看出闭回路的几何特点：由此可以看出闭回路的几何特点： 闭回路都是一条封闭折线，每个顶点格子都是转角点闭回路都是一条封闭折线，每个顶点格子都是转角点 每一行或每一列只有且仅有两个顶

20、点格子每一行或每一列只有且仅有两个顶点格子1. 每两个顶点格子的连线都是水平的或垂直的。每两个顶点格子的连线都是水平的或垂直的。可以证明的一个重要结论：可以证明的一个重要结论：m+n-1个变量构成基变量的充要条件是它不含闭回路，即个变量构成基变量的充要条件是它不含闭回路，即不存在以这些变量为顶点的闭回路不存在以这些变量为顶点的闭回路 闭回路法（闭回路法（cycle method)下面用最小元素法所确定的初始基本可行解来说明。下面用最小元素法所确定的初始基本可行解来说明。与单纯性原理相同，现目标是运费最少，故检验每一个非与单纯性原理相同，现目标是运费最少，故检验每一个非基变量（对应于运输表中的空

21、格）的检验数是否基变量（对应于运输表中的空格）的检验数是否. 0ij?ij若所有空格的检验数全非负，则不管怎样均不能使运输费若所有空格的检验数全非负，则不管怎样均不能使运输费用降低，即目标函数值已无法改进，这个解就是最优解用降低，即目标函数值已无法改进，这个解就是最优解 销地产地产量412104611168210239108145118622销 量8141214481A2A3A1B2B3B4B考虑空格考虑空格(A1,B1),设想由产地设想由产地A1供应一个单位的物品给销地供应一个单位的物品给销地B1，为，为使运入销地使运入销地B1的物品总量不大于它的销量，应将的物品总量不大于它的销量，应将A2

22、运到运到B1的物品的物品数量减数量减1，即将格子（，即将格子（A2,B1）中填入的数字）中填入的数字8改为改为7；另一方面，为使产地另一方面，为使产地A2运出的物品数量正好等于它的产量运出的物品数量正好等于它的产量(保证新保证新得到的解仍为基可行解得到的解仍为基可行解)，应将，应将A2运到运到B3的物品数量增的物品数量增1。同理同理A1运往运往B3的物品数量减的物品数量减1，A1运出的物品数量正好等于其产量运出的物品数量正好等于其产量按照上述设想，由产地按照上述设想，由产地A1供给供给1个单位物品给销地个单位物品给销地B1,由此由此引起的总运费变化是：引起的总运费变化是：11212313c -

23、c +c -c= 4-2+3-4 =1根据检验数的定义，它正是非基变量根据检验数的定义，它正是非基变量x11(或者说空格或者说空格(A1,B1)的检验数的检验数定义定义1：基变量（有数字的）对应的格为基格；非基变量（空格）基变量（有数字的）对应的格为基格；非基变量（空格）对应的顶点为非基格。对应的顶点为非基格。定义定义2：从每一空格（非基格）出发，沿水平或垂直方向前进，每从每一空格（非基格）出发，沿水平或垂直方向前进，每碰到数字格转碰到数字格转90o（有些情况也可以不改变方向）继续前（有些情况也可以不改变方向）继续前进，直到回到出发的空格为止，由此形成的封闭的折线称进，直到回到出发的空格为止，

24、由此形成的封闭的折线称为闭回路。为闭回路。规定：起始顶点的空格为第一顶点，则规定：起始顶点的空格为第一顶点，则 =闭回路上奇数次顶点运价之和闭回路上奇数次顶点运价之和 闭回路上偶数次顶点运价之和闭回路上偶数次顶点运价之和 ij 销地产地产量412104611168210239108145118622销 量8141214481A2A1B2B3B4B3A表 3-2143241323211111cccc1 销地产地产量 412104611168210239108145118622销 量8141214481A2A1B2B3B4B3A表 3-221165121434321212cccc21 销地产地产量

25、 412104611168210239108145118622销 量8141214481A2A1B2B3B4B3A表 3-213411651023131434322222cccccc121 销地产地产量 412104611168210239108145118622销 量8141214481A2A1B2B3B4B3A表 3-21341192313142424cccc1121 销地产地产量 412104611168210239108145118622销 量8141214481A2A1B2B3B4B3A表 3-210611432834141323213131cccccc102111 销地产地产量 4

26、12104611168210239108145118622销 量8141214481A2A1B2B3B4B3A表 3-2124116111314343333cccc12101121 销地产地产量 412104611168210239108145118622销 量8141214481A2A1B2B3B4B3A表 3-212111012检验数中有负数，说明原方案不是最优解。 对偶变量法（位势法）(dual variable method) 用闭回路法判定一个运输方案是否最优，需要找出所有空格的闭回路，并计算其检验数。当运输问题的产地和销地很多时，空格的数目很大，计算检验数的工作量很大，而用对偶变量

27、法就简便得多。nmvvvuuuY.2121 对产销平衡运输问题，若用u1,u2,um分别表示前m个约束等式相对应的对偶变量，用v1,v2vn 分别表示后n个等式相对应的对偶变量，即有对偶向量这时可将运输问题的对偶规划写成：的符号不限jiijjinjjjmiiivunjmicvustvbuaZ,.1,.1.max11前面学习知道，线性规划问题变量xj的检验数可表示为：1jjjBjjjjczcc B PcYP由此可写出运输问题某变量xij(对应于运输表中(Ai,Bj)的检验数如下：1212(,., ,.)()ijijijijijmijijjjniiczcYPcu uuv vvPcuv其中 分别称为

28、行位势、列位势。jivu ,有基变量所对应的检验数为零，可从m+n-1个等式0)(jiijvuc（2.2）解出所有的行位势、列位势。（2.1）可以证明，不论令 为何值， 始终不变。avi)(jivu 即 将不会随 的取值而改变。 ijiv为此，在求解方程组（2.2）时，为计算简便，可指定一个位势等于一个较小的整数或零。 销地产地产量412104611168210239108145118622销 量8141214481A2A1B2B3B4B3A表 3-2iujv10410392jiijvuc行位势列位势设u1=1当然，也可用采用解方程组的办法来求位势：1314212332344112356uvu

29、vuvuvuvuv两种方法任选一种 销地产地产量 412104611168210239108145118622销 量8141214481A2A1B2B3B4B3A表 3-2iujv1041039212111012)(jiijijvuc三。解的改进（用闭回路法调整）选择进基变量的原则：,min|0Nklijiji j J即选择非基变量中检验数最小的一个进基。在进基格点所对应的闭回路上，定义顶点的序号：自进基格点起选定一个方向（比如顺时针方向），依次为第一格、第二格、在奇数格点上减少调整量 ，在偶数格点上增加调整量 。其中调整量为),( |minjixij为闭回路中偶数格点 销地产地产量 4124

30、1116821039108145118622销 量8141214481A2A1B2B3B4B3A表 3-2iujv104103921211012210602222 销地产地产量 412124411168210329108145118622销 量8141214481A2A1B2B3B4B3A表 3-2iujv141039221121309jiijvuc)(jiijijvuc四。表上作业法计算中的两个问题 无穷多个最优解若在最优解中，某个非基变量的检验数为零，则该问题有无穷多个最优解此时得到一个最优解：,1213x, 414x, 821x, 224x,1432x, 834x其余变量全等于零。总运费

31、为（目标函数值）3141ijijijxcz244685149228114412 销地产地产量 412124411168210329108145118622销 量8141214481A2A1B2B3B4B3A表 3-2iujv141039221121309 销地产地产量 412124111621039108145118622销 量8141214481A2A1B2B3B4B3A表 3-2iujv141039134284444 销地产地产量 441212411164210369108145118622销 量8141214481A2A1B2B3B4B3A表 3-2iujv141039221121390

32、此时得另一个最优解：, 411x,1213x, 421x, 624x,1432x, 834x其余变量全等于零。总运费为（目标函数值）3141ijijijxcz24468514962441244 退化情况与一般LP问题类似，运输问题也可能出现退化了的基本可行解。有以下两种情况：（1）在确定初始基本可行解时，若已确定在空格）在确定初始基本可行解时，若已确定在空格 处处),(ji要添上调运量要添上调运量 ，而此时发点的当前可发送量与收点的当，而此时发点的当前可发送量与收点的当前需求量恰好相等。即发点的当前发送量已全部用完，而收前需求量恰好相等。即发点的当前发送量已全部用完，而收点的需求量已全部满足。

33、因此应同时划掉发送的行及接受的点的需求量已全部满足。因此应同时划掉发送的行及接受的列。为了使调运表上确保有列。为了使调运表上确保有(m+n-1)个基变量的值，就需要个基变量的值，就需要在在所划掉的行（或列）的任一空格添上调运量所划掉的行（或列）的任一空格添上调运量0。这样就得到。这样就得到有有一个基变量取值为一个基变量取值为0的基本可行解的基本可行解退化解。退化解。ijx例如：下表给出一个例如：下表给出一个34运输的运价及发送量与需求量。运输的运价及发送量与需求量。试用最小元素法求该问题的一个初始基本可行解。试用最小元素法求该问题的一个初始基本可行解。 销地产地产量31145777381210

34、69销 量3656481A2A1B2B3B4B3A表 4-26011634此时得到一个退化了的初始基本可行解：, 012x, 113x, 614x, 423x, 331x, 632x其余变量全等于零。 在用闭回路调整当前基本可行解时，有多个偶数格值相等且都是极小值点 。此时只能取一个离基，其余的仍作为基格。例如：下表给出一个34运输问题的基本可行解及发送量与需求量、基本可行解的检验数。试用闭回路法对其做出调整。 销地产地产量 317339销 量3646481A2A1B2B3B4B3A表 4-514112311633333333 销地产地产量 347369销 量3646481A2A1B2B3B4

35、B3A表 4-514112110333 运输问题的进一步讨论运输问题的进一步讨论一、产销不平衡运输问题一、产销不平衡运输问题对产销不平衡问题，可转化为平衡问题，然后按表上作业对产销不平衡问题，可转化为平衡问题，然后按表上作业法求解。转换办法：法求解。转换办法： 若产大于销，增加一个假想的销地（可视为库存地）其销若产大于销，增加一个假想的销地（可视为库存地）其销量设定为余量，相应的运价设为量设定为余量，相应的运价设为0 0。 若销大于产，增加一个虚拟的产地，其产量设定为不足若销大于产，增加一个虚拟的产地，其产量设定为不足量，相应的运价也设为量，相应的运价也设为0 0。例例4 某市有某市有3个造纸

36、厂个造纸厂 ， 和和 ，有，有4个集中用户个集中用户 和和 ，各工厂的生产量、各用户的需用量以及各，各工厂的生产量、各用户的需用量以及各工厂到用户的单位运价（元工厂到用户的单位运价（元/t）示于表）示于表3-14中，问如何调运中，问如何调运才能使总运费最小？才能使总运费最小？1A2A3A1B,2B,3B4B 销地产地产量31234811259567159销 量43561A2A1B2B3B4B3A表 3-142218可增加一个假想的销地可增加一个假想的销地5B 销地产地产量 31234081125905671509销 量435641A2A1B2B3B4B3A表 3-145B例题例题5：弹性需求问

37、题：弹性需求问题v设有三煤矿供应四地区，资料如下：设有三煤矿供应四地区，资料如下：运价运价 地区地区煤矿煤矿甲甲乙乙丙丙丁丁产量产量 A B C161419131320221923171525506050最低需求最低需求最高需求最高需求3050707003010不限不限解题思路：v设法转化为标准型设法转化为标准型v本题产量本题产量160万吨，最低需求万吨，最低需求110万吨，最高需求无万吨，最高需求无限。实质上比较现实的最高需求限。实质上比较现实的最高需求210万吨万吨v产量大于最小需求；小于最大需求。而标准型是：产量大于最小需求；小于最大需求。而标准型是：产量产量=销量。销量。v处理办法：设

38、想一个虚拟煤矿处理办法：设想一个虚拟煤矿D，生产，生产50万吨，但万吨，但这个产量只能供应可有可无的最高需求部分，于是这个产量只能供应可有可无的最高需求部分，于是各地的需求也应分为两个部分：基本需求、机动需各地的需求也应分为两个部分：基本需求、机动需求求v虚拟产量的运输费用为零，但它对于基本需求来讲，虚拟产量的运输费用为零，但它对于基本需求来讲，运费为无穷大。运费为无穷大。建模：运价 地区煤矿甲1甲2乙丙丁1丁2产量 A B C D161419M1614190131320M2219230171225M1712250 50 60 50 50需求量302070301050 210210最优解：运价

39、 地区煤矿甲1甲2乙丙丁1丁2产量 A B C D30205020030103020 50 60 50 50 需求量302070301050 210210v例例6 6、有三个产地、有三个产地3A1,A23A1,A2和和A3A3生产同一种物品，使用者为生产同一种物品，使用者为B1,B2B1,B2和和B3B3，各产地到各使用者的单位运价于下表中。这三，各产地到各使用者的单位运价于下表中。这三个的需用量分别为个的需用量分别为1010、4 4和和6 6个单位，由于销售需要和客观条个单位，由于销售需要和客观条件的限制，产地件的限制，产地A1A1至少要发出至少要发出6 6个单位的产品，它最多只能个单位的产

40、品，它最多只能生产生产1111个单位的产品；个单位的产品；A2A2必须发出必须发出7 7个单位的产品；个单位的产品；A3A3至少至少要发出要发出4 4个单位的产品。试根据上述条件用表上作业法求解个单位的产品。试根据上述条件用表上作业法求解该问题。该问题。B1B1B2B2B3B3产量产量A1A12 24 43 36 6a111a111A2A21 15 56 6a2=7a2=7A3A33 32 24 4a3a34 4用量用量10104 46 6运输模型的应用运输模型的应用v例题例题7 7：某机床厂定下一年：某机床厂定下一年合同分别于各季度末交货。合同分别于各季度末交货。已知各季度生产成本不同，已知

41、各季度生产成本不同，允许存货，存储费允许存货，存储费0.120.12万万元元/ /台季，三、四季度可以台季，三、四季度可以加班生产，加班生产能力加班生产，加班生产能力8 8台台/ /季，加班费用季，加班费用3 3万元万元/ /台台季季度度正常生正常生产能力产能力单位成本单位成本（万元）（万元）交货交货台数台数1 12 23 34 4303032322020282810.5510.5510.810.8111111.111.12525303015154545分析：分析：v可用线性规划，但用运输问题更简单可用线性规划，但用运输问题更简单v要决策的问题是各季度生产量和交货量设要决策的问题是各季度生产量

42、和交货量设xijxij表示第表示第i i季度生季度生产第产第j j季度交货的台数季度交货的台数v因加班时间生产成本不同，故要区别开来，三四季度可加班，因加班时间生产成本不同，故要区别开来，三四季度可加班，视同增加两个季度视同增加两个季度v需求量合计需求量合计115115台，生产能力合计台，生产能力合计126126台，供需不平衡，因此，台，供需不平衡，因此，增加一项闲置能力。增加一项闲置能力。建模：建模： 成本成本 交货交货生产生产 闲置闲置 1 2 3 4 能力能力产量产量1季度正常生产季度正常生产2季度正常生产季度正常生产3季度正常生产季度正常生产3季度加班生产季度加班生产4季度正常生产季度正常生产4季度加班生产季度加班生产10.55 10.67 10.79 10.91 0 M 10.8 10.92 11.04 0 M M 11 11.12 0 M M 14 14.12 0 M M M 11.1 0