下载文档原格式
* 位势法的计算过程令u1=0 按ui+vj=cij相继确定其他数字格的ui 和vj 计算空格的检验数。
如λ11=3-(0+2)=1 因为λ11=-1 0,因而该问题至此尚未达到最优解. 销地产地 B1 B2 B3 B4 A1 3 11 3 10 A2 1 9 2 8 A3 7 4 10 5 ③④①⑥③③ ui vj 0 3 10 -1 -5 2 9 1 2 1 -1 10 12 * 位势法的理论依据（互补松弛定理） * 位势法的理论依据运输问题设B为一可行基，则相应的基可行解的各变量的检验数为运输问题的对偶问题由对偶理论有Y=CBB-1 基变量的检验数等于0 （I：基变量下标集） * 位势法的步骤对于每一个基变量（数字格）都按照公式 ui+vj=cij 列出一个位势方程，形成位势方程组（m+n－1个）；任意决定其中一个位势的数值，然后求出其他位势的数值；按照公式计算非基变量（空格处）的检验数（m×n-(m+n－1)个）。
* 从最小负检验数所对应的空格进行调整例7 对由最小元素法得出的初始解进行调整调整方法： 1）找出负检验数所在空格处的闭回路 2）在闭回<a name=baidusnap0></a>路上</B>找到偶数点所对应的基变量的最小值再按调整后的解由位势法计算空格的检验数四、调整销地产地 B1 B2 B3 B4 A13 11 3 10 A2 1 9 2 8 A3 74 105 ③④①⑥③③ 1 2 1 -1 10 12 ⑤①② x23 x14 x24 x13 3）以此最小值θ为调整量，在奇数格加上该调整量，在偶数格上减去该调整量换入变量：x24 换出变量：x23 * 1.由最小元素法求得初始基可行解五、典型运输问题解题步骤示例销地产地 B1 B2 B3 B4 ai A1 3 11 3 10 7 A2 1 9 2 8 4 A3 7 4 10 5 9 bj 3 6 5 6 20 ③④①⑥③③ * 2.由位势法求检验数令u1=0 按ui+vj=cij相继确定其他数字格的ui和vj 计算空格的检验数因为λ24=-1 0,因而该问题至此尚未达到最优解. 销地产地 B1 B2 B3 B4 A1 3 11 3 10 A2 1 9 2 8 A3 7 4 10 5 ③④①⑥③③ ui vj 0 3 10 -1 -5 2 9 1 2 1 -1 10 12 如λ11=3-(0+2)=1 * 3.从最小负检验数所对应的空格进行调整调整方法： 1）找出闭回路 2）使最小负检验数所对应的空格达到最大的调整量1 销地产地 B1 B2 B3 B4 A1 3 11 3 10 A2 1 9 2 8 A3 7 4 10 5 ③④①⑥③③ 1 2 1 -1 10 12 ⑤①② * 令u1=0 按ui+vj=cij相继确定其他数字格的ui和vj 计算空格的检验数。
第三章 运输问题主要内容 运输问题的模型、算法 讲授重点 运输问题的模型、算法 讲授方式讲授式、启发式第一节 运输问题及其数学模型一、运输问题的数学模型设某种物品有m 个产地A 1,A 2,…,A m ，各产地的产量分别是a 1,a 2,…,a m ；有n 个销地B l ,B 2,…,B n ,各销地的销量分别为b l ,b 2,…,b n 。
假定从产地A i (i ＝1,2,…,m)向销地B j (j ＝1,2,…,n)运输单位物品的运价是c ij ，问怎样调运这些物品才能使总运费最小?这是由多个产地供应多个销地的单品种物品运输问题。
为直观清楚起见，可列出该出该问题的运输表，如表3-1所示。
设ij表示从A i 运往B j 的物品数量，ij表示从A i 运往B j 的单位物品的运价。
则对于平衡运输问题（∑∑===nj jm i i ba 11），其数学模型的一般形式可表示为：∑∑===n j mi ijij x c s 11min()()()⎪⎪⎪⎩⎪⎪⎪⎨⎧==≥====∑∑==n j m i x n j b x m i a x ij j m i ij inj ij ,2,1;,2,10,,2,1,,2,111 (3.1)二、运输问题数学模型的特点对于平衡运输问题(∑∑===nj jm i iba 11)，可以证明其有如下两个特点： (1)矩阵A 的秩R(A)＝m+n-1。
(2)问题必有最优解，而且当ji b a ,皆为整数时，其最优解必为整数最优解。
第二节 表上作业法求解运输问题一、给出运输问题的初始可行解（初始调运方案） 1、最小元素法 解题步骤：⑴在运价表中找到最小运价c 1k ； ⑵将的A L 产品给B k ；①若a L>b k，则将a L改写为a L-b k，划掉b k，同时将运价表中K列的运价划掉；②若a L<b k，则将a L改写为b k-a L，划掉a L，同时将运价表中L列的运价划掉。
第三章运输问题一、建立下列问题的数学模型1、P119, 3.6某厂按照合同规定须于当年每季度末分别提供10，15，25，20台同一规格的柴油机。
已知该厂各季度的生产能力及生产每台柴油机的成本如表所示。
又如果生产出来的柴油机当季不交货，每台每积压一个季度，存储维护费用0.15万元。
要求在完成合同的情况下，使得全年生产（存储）费用最小的决策。
将此问题归结为运输问题，试建立该问题的产销平衡及单位运价表。
解：以四个季度为产地和销地，建立产销平衡运输表如下：2、P119, 3.7上题中若允许某些季度末交货时发生短缺，但全部合同必须于Ⅳ季度末完成。
又缺货时，每台每晚交一个季度，罚款0.1万元。
为使总的生产、存储和缺货罚款损失费用最小，重新列出用运输问题求解时的产销平衡和单位运价表。
解：以四个季度为产地和销地，建立产销平衡运输表如下：3、P119, 3.8某造船厂在某年算起的连续三年的年末各提供三条规格相同的货轮，已知该厂今后三年的的生产能力及生产成本如下表所示。
已知加班生产时每条货轮成本比正常生产时高70万元，又知造出的货轮如当年不交货，每条每积压一年增加维护费用40万元。
在签订合同时，已有以前积压的两条，该厂希望在第三年末交货后多留一条备用。
问该厂应如何安排生产计划，满足上述要求，并使得总费用最小。
请列出产销平衡表和单位运价表。
解4、P120, 3.9为确保飞行的安全，飞机上的发动机每半年必须强迫更换进行大修。
某维修厂估计某种型号的战斗机从下一个半年起的今后三年内每半年需更换的发动机数量分别为：100,70,80,120,150,140（台）。
更换发动机时，可以换上新的，也可以用经过大修的旧的发动机。
已知每台新发动机的购置费是10万元，而旧发动机的维修方式有两种：快修，每台2万元，半年交货（本期拆下，下期即可用上，半年为一期）；慢修，每台1万元，一年才能交货（本期拆下，下下期可用上）。
该厂新接手该项发动机的更换维修任务，又知三年后这种战斗机将退役，退役后这种发动机将报废。
