介绍几种常用的确定初始基本可行解的方法

时间：2023-06-01 理论教育 版权反馈

【摘要】：下面介绍几种常用的确定初始基本可行解的方法。试用西北角法求解例4.2的初始基本可行解。

介绍几种常用的确定初始基本可行解的方法

与一般线性规划问题不同，任何运输问题都有基本可行解，也有最优解，根据具体情况，可能有唯一最优解也可能有多重最优解，如果供应量和需求量都是整数，则一定可以得到整数最优解。下面介绍几种常用的确定初始基本可行解的方法。

1.最小元素法

这种方法的基本思想是就近优先供应，即对单位运价表中最小运价c_ij对应的变量x_ij优先赋值x_ij=min{a_i，b_j}，然后对次小运价对应的变量赋值并满足约束，依次下去，直到最后得到一个初始基本可行解。

【例4.2】某建筑公司拟从A₁、A₂、A₃三个管桩厂购买管桩，供应B₁、B₂、B₃、B₄四个工地使用。已知各管桩厂可供应管桩的数量（百根）、各工地需要的数量（百根）及从各管桩厂到各工地的运输单价（千元/百根）如表4-2所示，试用最小元素法求解该运输问题。

表4-2

解表4-2中最小元素是c₂₁=1，令x₂₁=min{a₂，b₁}=min{4，3}=3，将3填在c₂₁的下方，并在x₁₁和x₃₁的位置分别打上“×”，表示A₂供应3个单位给B₁，且B₁已经满足需求，如表4-3所示。

表4-3

在表4-3没有分配的元素中，最小元素是c₂₃=2，令x₂₃=min{4-3，5}=1，将1填在c₂₃的下方，在x₂₂、x₂₄处打上“×”，表示A₂供应1个单位给B₃，且A₂已经没有剩余量，B₃还差4个单位没有达到需求量，如表4-4所示。

表4-4

按照上述步骤依次进行下去，结果见表4-5。表4-5

表4-5中除了打“×”的变量共有m+n-1=3+4-1=6个，且不构成闭回路，因此{x₁₃，x₁₄，x₂₁，x₂₃，x₃₂，x₃₄}是一组基变量，打“×”的变量是非基变量。得到一组基本可行解为：

则目标值：

Z=3×4+10×3+1×3+2×1+4×6+5×3=86

2.元素差额法（Vogel近似法）

最小元素法的缺点是：可能开始时节省一处的费用，但随后在其他处要多花几倍的运费。元素差额法对最小元素法进行了改进。如果不能按最小运费就近供应，就考虑次小运费，这就有一个差额，差额越大，说明不能按最小运费调运时，运费增加就越多，因此对差额最大处就应当采用最小运费调运。基于此，元素差额法的步骤是：

1）求出每行和每列次小运价和最小运价之差，分别记为u_i（i=1，2，…，m）和v_j（j=1，2，…，n）。

2）找出所有行或列差额的最大值L=max{u_i，v_j}，并且安排差额L对应行或列的最小运价处优先调运。

3）在剩下的运价中重复进行步骤1）和2），直到最后全部调运完毕。

【例4.3】某市区交通愿望图有三个始点和四个终点，始点发生的出行交通量a_i、终点吸引的交通量b_j及始终点之间的旅行费用如表4-6所示。问如何安排出行交通量才能使总的旅行费用最小。

表4-6

解求行差额u_i=（3，1，2），求列差额v_j=（4，1，7，4），则max{u_i，v_j}=max{3，1，2；4，1，7，4}=7，即v₃=7最大，第三列的最小运价c₂₃=2，先调运。令x₃₂=min{a₂，b₃}=min{25，5}=5，在x₁₃及x₃₃处打“×”，结果如表4-7所示。(www.daowen.com)

表4-7

在表4-7中，因为B₃已经满足需求，所以只求u₁、u₂、u₃以及v₁、v₂、v₄即可。这时发现有两个最大差额，即v₁、v₄，任选一个，如选v₁=4（若选择v₄=4，初始解的结果会不同），第一列的最小运价c₂₁=1，故x₂₁=min{25-5，20}=20，这时A₂与B₁同时满足约束，若同时将x₁₁、x₃₁、x₂₂及x₂₄都打上“×”，最后基变量的个数必定小于3+4-1=6个，因而应在x₁₁、x₃₁、x₂₂及x₂₄中任选一个变量作为基变量，运量为零，这里选x₁₁=0，计算结果见表4-8。