图5-12 建立新运输问题
此处问题类型（Problem Type）共有7种：
⑴ Network Flow 网络流问题
⑵ Transportation Problem 运输问题 ⑶ Assignment Problem 指派问题 ⑷ Shortest Path Problem 最短路问题 ⑸ Maximal Flow Problem 最大流问题 ⑹ Minimal Spanning Tree 最小支撑树问题
⑺ Travel Salesman Problem 旅行销售员问题（中国邮递员问题）
输入运输问题在此处应当选⑵ Transportation Problem。本例中有三个生产点（Number of Sources）和四个销售点（Number of Destinations），也在此处输入。本例为求最小运费，所以在Objective Criterion（目标函数标准）中选择Minimization。此外，数据输入格式Data Entry Format可以选择电子表格模式（Spreadsheet Matrix Form）与图形模式（Graphic Model Form）。
3. 输入数据。在选择数据输入格式时，选择Spreadsheet Matrix Form则以电子表格矩阵形式输入单位运价系数矩阵和各地产量与销量，是固定格式，如表5-4所示。
表5-4 电子表格矩阵形式输入数据
数据输入方法与其它规划问题输入数据时相同，请参看实验二的相应内容。另外，数据输入后，如果需要修改、增减等处理，也可以实现，同样请参看实验二中的相关内容。 4. 求解模型。
点击菜单栏Solve and Analyze，下拉菜单有四个选项： ① 直接求解（Solve the Problem）、
② 用网络图形式求解并显示求解步骤（Solve and Display Steps-Network）、 ③ 用表上作业法求解并显示求解步骤（Solve and Display Steps-Tableau） ④ 选择求初始解的方法（Select Initial Solution Method）。
本例可以先选择求初始解的方法，具体过程参看5.4.2相关内容。可以选择伏格尔法
6
（Vogel’s Approximation Method）来求解初始解。点击OK后，即可进入下面的计算过程。
以下可以选择①、②、③三种方法来求解这个运输问题的最优解。 （1）直接求最优解。选择Solve the Problem或直接点击工具栏上的求解的综合报告如表5-5所示，表中的各项含义见常见术语表5-9。
，系统直接显示
表5-5 最优解综合报告表
本例得到最小运费支出为85，运输方案见表5-5。
（2）用网络图形式求解并显示求解步骤。用网络图形式分步求解可以明确每一步的优化结果。选择Solve and Analyze?Solve and Display Steps-Network，系统显示网络图形解题第一步的求解结果，如图5-13所示。
图5-13 Graphic Solution—Iteration 1
继续选择Iteration?Next Iteration或点击工具栏
5-14所示。
，得到第二步的求解结果，如图
7
图5-14 Graphic Solution—Iteration 2
虽然只进行了两步运算，但由于选择了伏格尔法寻找初始解，第二步显示的结果已是最终结果（Final）了，再次选择Iteration?Next Iteration或点击工具栏的求解结果，如表5-3所示。
，即可得到表格式
（3）用表上作业法求解并显示求解步骤。点击Solve and Analyze?Solve and Display
Steps-Tableau，软件将用表上作业法求解问题。第一步得到如图5-15的结果。
图5-15 Transportation Tableau —Iteration 1
这里得到了一个目标函数值86，即运费，但它还不是最小运费，图5-15中显示了对
8
运量的调整，即将Source 2运到Destination 3的运量1转运到Destination 1，其周边运量也相应调整，运费还能下降。继续选择Iteration?Next Iteration或点击工具栏步的求解结果，如图5-16所示。
，得到第二
图5-16 Transportation Tableau —Iteration 2
第二步显示的结果已是最终结果（Final）了，再次选择Iteration?Next Iteration或点击工具栏
，即可得到表格式的求解结果，如表5-5所示。
至此，本运输问题求解完毕，最小运费为85。
1. 用WinQSB软件求解下列运输问题的最优解： ① 销售点 加工厂 A1 A2 A3 销 量 ② 销售点 加工厂 A1 A2 A3 A4 销 量
B1 3 2 4 3 B2 7 4 3 3 B3 6 3 8 2 B4 4 2 5 2 产 量 5 2 3 B1 10 2 1 8 4 B2 20 10 20 6 4 B3 5 8 7 3 6 9
B4 9 30 10 7 2 B5 10 6 4 5 4 产 量 5 6 2 9 ※运输问题的解法表上作业法
一、解题步骤
第1步：用西北角法或最小元素法确定初始基本可行解。 第2步：位势法求非基变量的检验数(解的最优性检验)，若最优准则σij≥0，则当前解最优，计算停止，否则转第3步。
第3步：取一个检验数最小的非基变量做进基变量。 第4步：用闭回路法调整当前基本可行解，转第2步 1. 确定初始基本可行解（初始调运方案）
例 某公司生产糖果，它有三个加工厂A1,A2,A3,每月产量分别为7t,6t,5t,6t。已知从第i个加工厂到第j个销售店的每吨糖果的运价Cij见表，试设计在满足各销售店需求量的前提下，各加工厂到各销售店的每月调运方案，使总的运费最小。 运价表
A 西北角法 B 最小元素法
2．解的最优性判别（位势法，也称对偶变量法） 3．用闭回路法调整当前基可行解 二、表上作业法计算中的几个问题
1、某个基本可行解有几个非基变量的检验数为负
若运输问题的某个基可行解有几个非基变量的检验数均为负，在继续进行迭代时，取它们中的任一变量均可使目标函数值得到改善，但通常取σij<0中最小者对应的变量为换入变量。
2、无穷多个最优解
当迭代到运输问题的最优解时，如果有某非基变量的检验数＝0，则说明该运输问题有无穷多最优解。（如上例，为得到另一个最优解，只需让σij＝0的非基变量进基） 3、退化问题
当运输问题某部分产地的产量和与另一部分销地的销量和相等时，在迭代过程中有可能在某个格填入一个运量时需同时划去运输表的一行和一列，这时就出现了退化。
在运输问题中，退化解是时常发生的，为了使表上作业法的迭代工作进行下去，退化解应在同时划去的一行或一列中的某个空格中填入数字0，表示这个格中的变量是取值为0的基变量，使迭代过程中基可行解的分量恰好为m+n-1个。
b.在用闭回路法调整当前基本可行解时，调整量θ的取值应为θ＝min{xij/( i,j )为闭回路上所有偶数号格点}。这时可能出现有两个（或以上）偶数号格点的xij都相等且都为极小值，只能取其中一个为离基格，其余的仍作为基格，而在作运输量调整时，运输量与θ相等的那些偶数号格点的xij都将调整为0，因此得到的也是一个退化了的基可行解。 三、总销量大于总产量
例 1 某市有三个造纸厂A1,A2,A3,其纸产量分别为8，5，9个单位，有4个集中用户B1,B2,B3,B4,其需用量为4，3，5，6个单位，由各厂到各用户的单位运价如表所示，试确
10