线性规划的运输问题求解示例
题目描述
假设有两个工厂（供应点）和三个仓库（需求点），需要制定一个运输计划，使得总运输成本最低。
- 工厂A的供应量为30吨，工厂B的供应量为25吨。
- 仓库1的需求量为20吨，仓库2的需求量为15吨，仓库3的需求量为20吨。
- 单位运输成本（元/吨）如下表：
仓库1 仓库2 仓库3 工厂A 4 2 5 工厂B 3 6 4
问题要求：在满足供需约束的前提下，最小化总运输成本。
解题过程
1. 问题建模
设 \(x_{ij}\) 表示从工厂i到仓库j的运输量（i=1,2；j=1,2,3），目标函数和约束条件如下：
- 目标函数：最小化总成本
\[ \min Z = 4x_{11} + 2x_{12} + 5x_{13} + 3x_{21} + 6x_{22} + 4x_{23} \]
- 供应约束（工厂发货量不超过供应量）：
\[ x_{11} + x_{12} + x_{13} = 30 \quad (\text{工厂A}) \]
\[ x_{21} + x_{22} + x_{23} = 25 \quad (\text{工厂B}) \]
- 需求约束（仓库收货量等于需求量）：
\[ x_{11} + x_{21} = 20 \quad (\text{仓库1}) \]
\[ x_{12} + x_{22} = 15 \quad (\text{仓库2}) \]
\[ x_{13} + x_{23} = 20 \quad (\text{仓库3}) \]
- 非负约束：\(x_{ij} \geq 0\)。
注意：总供应量（30+25=55）等于总需求量（20+15+20=55），此为平衡运输问题。
2. 初始解构造（西北角法）
西北角法从运输表的左上角（西北角）开始分配：
- 第一步：从工厂A向仓库1分配。供应量30 > 需求量20，因此分配 \(x_{11} = 20\)，仓库1需求满足，工厂A剩余10吨。
- 第二步：从工厂A向仓库2分配。仓库2需求15 > 工厂A剩余10，分配 \(x_{12} = 10\)，工厂A供应耗尽，仓库2剩余需求5吨。
- 第三步：从工厂B向仓库2分配。仓库2剩余需求5，工厂B供应25，分配 \(x_{22} = 5\)，仓库2需求满足，工厂B剩余20吨。
- 第四步：从工厂B向仓库3分配。仓库3需求20，工厂B剩余20，分配 \(x_{23} = 20\)。
得到初始解：
\[x_{11}=20, \ x_{12}=10, \ x_{13}=0, \ x_{21}=0, \ x_{22}=5, \ x_{23}=20 \]
总成本 \(Z = 4 \times 20 + 2 \times 10 + 5 \times 0 + 3 \times 0 + 6 \times 5 + 4 \times 20 = 80 + 20 + 0 + 0 + 30 + 80 = 210\)。
3. 最优性检验（位势法）
位势法通过计算行因子 \(u_i\) 和列因子 \(v_j\)，检验非基变量的减少成本是否非负（若存在负值，则当前解非最优）。
- 步骤1：设 \(u_1 = 0\)，根据基变量满足 \(c_{ij} = u_i + v_j\) 计算其他因子：
- \(x_{11}\) 为基变量：\(4 = 0 + v_1 \Rightarrow v_1 = 4\)
- \(x_{12}\) 为基变量：\(2 = 0 + v_2 \Rightarrow v_2 = 2\)
- \(x_{22}\) 为基变量：\(6 = u_2 + 2 \Rightarrow u_2 = 4\)
- \(x_{23}\) 为基变量：\(4 = 4 + v_3 \Rightarrow v_3 = 0\)
- 步骤2：计算非基变量的减少成本 \(\bar{c}_{ij} = c_{ij} - (u_i + v_j)\)：
- \(\bar{c}_{13} = 5 - (0 + 0) = 5\)
- \(\bar{c}_{21} = 3 - (4 + 4) = -5\)
- 由于 \(\bar{c}_{21} = -5 < 0\)，当前解非最优，需调整。
4. 解的改进（闭回路法）
以非基变量 \(x_{21}\) 为入口，构造闭回路：路径为 \(x_{21} \to x_{22} \to x_{12} \to x_{11} \to x_{21}\)。
- 调整量：回路中偶顶点（\(x_{22}, x_{11}\)）的最小值 = min(5, 20) = 5。
- 调整：偶顶点减5，奇顶点加5：
- \(x_{21} = 0 + 5 = 5\)
- \(x_{22} = 5 - 5 = 0\)
- \(x_{12} = 10 - 5 = 5\)
- \(x_{11} = 20 - 5 = 15\)
更新后的解：
\[x_{11}=15, \ x_{12}=5, \ x_{13}=0, \ x_{21}=5, \ x_{22}=0, \ x_{23}=20 \]
总成本 \(Z = 4 \times 15 + 2 \times 5 + 5 \times 0 + 3 \times 5 + 6 \times 0 + 4 \times 20 = 60 + 10 + 0 + 15 + 0 + 80 = 165\)。
5. 重新检验最优性
计算新的位势：
- \(u_1 = 0\)，由 \(x_{11}\) 得 \(v_1 = 4\)，由 \(x_{12}\) 得 \(v_2 = 2\)
- 由 \(x_{21}\) 得 \(3 = u_2 + 4 \Rightarrow u_2 = -1\)
- 由 \(x_{23}\) 得 \(4 = -1 + v_3 \Rightarrow v_3 = 5\)
计算非基变量减少成本： - \(\bar{c}_{13} = 5 - (0 + 5) = 0\)
- \(\bar{c}_{22} = 6 - (-1 + 2) = 5\)
所有 \(\bar{c}_{ij} \geq 0\)，当前解最优。
最终方案
- 工厂A向仓库1运15吨，向仓库2运5吨；
- 工厂B向仓库1运5吨，向仓库3运20吨；
- 最低总成本为165元。