第十讲 运输问题的表上作业法运输问题的表上作业法 §1 运输问题事例§2 运输问题的一般形式 §3 表上作业法 §1 运输问题事例 （1） 已知，有4个产地（源点）生产的产品需销售到4个需求地（目的地或汇点），其源点产量和目的地需求量见表1-5表1-5 运输问题的需求量及产量目的地 需求量 源点 产量 1234总计 2228172390 1234总计 2418123690 其源点到目的地的单位产品的运费价格见图1-7 §1 运输问题事例 （2）费 目 用 的源点 地12341③ ⑨ ⑤ ⑥ 2④ ① ⑦ ④3⑥⑧ ② ⑤4⑤⑤④③24181236 22 28 17 23图1-7 运输费用矩阵 表格旁边数字为产量和需要求量 §2 运输问题的一般形式 ri——源i产量，aj——目的地j的需求量 §3 表上作业法 （1）与单纯形表格法一样，该法亦分两步进行：·求出初始基础可行解·求出最优解 1． 用最小元素法求出满意的初始基础可解其方法是，按照费用矩阵元素Cij增长顺序逐个选择引入基本解的变量xij，非退化情况下，每选择1个，就必然排除1个源点或目的地，最后一步可一次排除1个源点和1个目的地，这样便可得到一个初始基础可行解。
§3 表上作业法 （2）以上例考察，观察图1-7①∵min{cij}=c22=1故优先分配源2和目的地2之间的产品图1-8 最小元素法第1步 ③⑨⑤⑥④18 ①⑦④⑥⑧②⑤⑤⑤④③24 01222171023361828 §3 表上作业法 （3）②余下元素中，最小值为c32=2 图1-9 最小元素法第2步 ③依此类推，最后获初始基础可行解示如图1-10中③⑨⑤⑥④18 ①⑦④⑥⑧12 ②⑤⑤⑤④③24 0122217102336182805 §3 表上作业法 （4） 图1-10 初始基础可行解 即基础解为：x11=22，x12=18，x33=12，x42=8，x43=5，x44=23此时总费用为22522③2⑨⑤⑥④18①⑦⑤⑥⑧12②⑤⑤8⑤5④23③ §3 表上作业法 （5） 2．求出最优解这有两种方法：闭回路法和位势法 ①闭回路法，其思路是令表中空格（即非基础解），对应的变量由0增加d单位，然后在保持产品供求平衡（即满足约束条件）情况下，使基础解参与变动，看其费有如何变化，若费用减少，则该非基变量可进入基，否则，加以排除，其思路与单纯形法一致现继上图继续改进基础解，直至达优。
i) 参见图1-11，分析非基变量x32增加d单位以后，其它基础解及费用变化 §3 表上作业法 （6） 22③2⑨⑤⑥24④18①⑦④18⑥⑧+d12②-d⑤12⑤8⑤-d5④+d23③3622281723 2．求出最优解图1-11 回路法原理 §3 表上作业法 （7）为使供求平衡，必须符合：x32+d→x42－d→x43+d→x33－d变动后，费用增加值为：8d－5d+4d－2d=5d，即费用增加，x32不能进基，为比较，把增加1个单位产品所引起的费用增加值填入相应的非基变量表格内，这又称检验值注意，在用回路法求解每个非基变量检验值时，在根据供求平衡寻找闭合回路过程中，其回路转折点必须是基础解！例如，分析非基解x31↑→x11↓→x12↑→x42↓→x43↑→x33↓→x31 §3 表上作业法 （8） 22 ③2 ⑨ ⑤ ⑥24 ④18① ⑦ ④18 ⑥ ⑧ 12 ② ⑤12 ⑤8 ⑤ 5 ④23 ③3622281723 9695-3745-1对每个非基变量计算后，将其检验值填入图1-12中 图1-12 回路法计算结果 其中： 内表示费用元素 内表示检验值 表内其它值为基础解。
§3 表上作业法 （9） ii) 观察表格，或检验值全部≥0，已达最优胜，结束否则，选取最负的检验值所对的非基变量，令其进基图1-12中，x13的检验值为最负，故令x13进基，应使x13尽量大，但又 必 须 使 其 它 变 量 非 负 观 察 x13变 化 规 律 ：x13↑→x12↓→x42↑→x43↓应取下降变量中的最小值作为x13的值此时min{x12 ，x43}=min{2，5}=2故令x13=2则x12=0，x42=10，x43=3将图1-12修正后，再求出当前非变量的检验值，示如图1-13非基础解的检验数合为正，故获最成解，总费用为249 §3 表上作业法 （10） 22 ③ ⑨ 2 ⑤ ⑥24 ④18① ⑦ ④18 ⑥ ⑧ 12 ② ⑤12 ⑤10⑤ 3 ④23 ③3622281723 636357452图1-13 回路法所得最优表格 §3 表上作业法 （11） ② 位势法（简捷法） 该法对运输费用矩阵表格每次可确定一组“行值”和“列值”确定原则为使得每个基础变量之费用cij等于相应得行、列值之和，根据该原则求出行列值之后，用这些值再去求解每个非基本变量的检验数。
结合本例阐述该步骤：（见图1-14） §3 表上作业法 （12）图1-14 用位势法求解实例 22 ③2 ⑨ ⑤ ⑥24 ④18① ⑦ ④18 ⑥ ⑧ 12 ② ⑤12 ⑤8 ⑤ 5 ④23 ③3622281723 969-35745-1S1S2S3S4 t1t2t3t4 §3 表上作业法 （13） i) 令si，tj分别为行值和列值 求解方程：si+tj=cij [xijB基集] 从方程知，共有m+n－1个方程和m+n个未知量由于我们感兴趣的是相对值，故可令任一个行值或列值等于某个固定值，例如令t1=0，即可求出各行、列值，可见“行”“列”值不是唯一的 对于本例，令t1=0后，解联立方程： §3 表上作业法 （14） ii)根据已得的si，tj值求出非基础的检验值（或成本变动值）ij： ij =cij－(si+tj) 例如：图1-14中，13=c13－(s1+t3)＝5－(3+5)=-3 若13<0,则可进入基，根据此法求出所有非基本变量对应的检验值（成本变动值）后，选取minij (ij <0)所对应的变量进入基础解。
图1-14中得知，13=-3为最小值，令x13进基，采用回路法找出应离开的基变量，重新调整后，仍按上述步骤反复运算，最后得出最优解 现在看位势法的对偶解释： 结合本例，示如表1-6中 §3 表上作业法 （15）表1-6 位势法的对偶解释x11+x12+x13+x14 =24 x21+x22+x23+x24 =18 x31+x32+x43+x44 =12 x41+x42+x43+x44 =36x11 +x21 + x31 + x41 =22 x12 +x22 +x32 +x42 =28 x13 +x23 +x33 +x43 =17 x14 +x24 +x34 +x44 =23 (r1)s1(r2)s2(r3)s3(r4)s4(a1)t1(a2)t2(a3)t3(a4)t4c11 c12 c13 c14 ……………………………….. c44 §3 表上作业法 （16） 表1-6列出了本例的供求关系的8个约束方程。
（由于 ，故只有7个独立约束方程） 该规划的对偶约束必为： §3 表上作业法 （17） 显然，si，tj即是对偶问题的对偶变量y共8个对偶变量， 每次送代时有7个基础解变量，可写出7平衡方程式：si + tj = cij(xij B) 这与上面分析完全一致因此，位势法实质每一步都是首 先求解对偶方程的平衡解，这与单纯形法思路相同 唯一差别是，本文在单纯形法引进的检验数为zs－cs，而运 输问题引进的检验值cs－zs，相差一符号，这并无本质差 别，只是判断时注意即可。