引入

3、用分支与限界策略求解货物调运问题
某大型集团公司在全国有m (1 < m 20) 个产品生产基地(通称产地)，用Ai 表示(i = 1, 2, …, m)，需要分别将这些物质调运到n (1 < n 20) 个集中消费的地区(通称销地)，用Bj 表示(j = 1, 2, …, n)。
已知这m 个产地的产量分别为a1, a2, …, am(简写为ai)，n 个销地的销量分别为b1, b2, …, bn(简写为bj)，从第i 个产地到第j 个销地的单位货运价格为cij，并且总产量和总销量不一定相等。
应当如何制定调运方案，在尽可能地满足销量的前提下，使得总的运输费用为最小。
例：某集团公司的产量和销量以及单位运价表(千元/吨)

讯享网
其总运费最小的调运方案为：

运费总计：5 3 + 2 10 + 3 1 + 1 8 + 6 4 + 3 5 = 85(千元)。

思路

这类运输问题要分为两种情况讨论：
1当a[]=b[]时，运输问题的总产量等于其总销量时，这样的运输问题称为产销平衡的运输问题
2当a[]/=b[]时，运输问题的总产量不等于其总销量时，这样的运输问题称为产销不平衡的运输问题

数学模型

产销平衡条件

用X_ij表示从A _j 到B_j 的总运量，C[i][j]*X[i][j]就表示从第i 个产地到第j 个销地的总价格，即数学模型为：
$$minZ=\sum _{i=1}^m\sum _{j=1}^n{C}_{ij}{X}_{ij}$$

$$s.t.\{\begin{array}{ll}\sum _{i=1}^m{x}_{ij}=b_j,& j=1,2,...,n\\ & \\ {\sum }_{j=1}^n{x}_{ij}=a_i,& i=1,2,...,m\\ & \\ x_{ij}>=0& \end{array}$$
其中，ai和bj满足：$\sum _{i=1}^m{a}_i=\sum _{j=1}^n{b}_j$ 称为产销平衡条件。

产销不平衡条件

产量大于销量
用X_ij表示从A _j 到B_j 的总运量，C[i][j]*X[i][j]就表示从第i 个产地到第j 个销地的总价格，即数学模型为：
$$minZ=\sum _{i=1}^m\sum _{j=1}^n{C}_{ij}{X}_{ij}$$

$$s.t.\{\begin{array}{ll}\sum _{j=1}^n{x}_{ij}<=a_i,& i=1,2,...,m\\ & \\ \sum _{i=1}^m{x}_{ij}=b_j,& j=1,2,...,n\\ & \\ x_{ij}>=0,& i=1,2,...,mj=1,2,..,n\end{array}$$

解法：增加一个假想的销地$B_{n+1}$,其销量为：$b_{n+1}=\sum _{i=1}^m{a}_i-\sum _{j=1}^n{b}_j$
数学模型就改为了$minZ=\sum _{i=1}^m\sum _{j=1}^{n+1}{C}_{ij}{X}_{ij}$

产量小于销量
和上面的解法类似，增加一个假想的产地$A_{m+1}$，起产量为：$a_{m+1}=\sum _{j=1}^n{b}_j-\sum _{i=1}^m{a}_i$
就将不平衡问题转化为了平衡问题$minZ=\sum _{i=1}^{m+1}\sum _{j=1}^n{C}_{ij}{X}_{ij}$

表上作业法

在讲解上别人用的表上作业法，先确定一个可行解，然后检验当前可行方案是否最优，采用闭回路法从当前方案出发寻找更好的方案。
可行解是一定存在的，可以用最小元素法（贪心法求解），西北角法，Vogel法。
我用的最小元素法求的解这里只说明这一种求解思路，其他方案大家可以看看下方我给的链接。

最小元素法求可行解

基本思路是优先满足单位运价最小的供销业务。首先找出运价最小的，并以最大限度满足其供销量为原则确定供销业务。同样的方法反复进行直到确定了所有的供销业务，得到一个完整的调运方案跳出，即找到一组可行解。

闭回路法检验可行解是否为最优解

求出每个空格位置的检验数，当所有的检验数都大于或等于零的时候该调运方案就是最优方案。

使用分支限界法求解运输问题

理解了上述表上作业法求解运输问题之后，就可以根据表上作业法的思路，找出关系函数去限定上下界，加快判断当前方案是否为最优的节奏。
数学模型和上面的一样$minZ={\sum }_{i=1}^m{\sum }_{j=1}^n{C}_{ij}{X}_{ij}$
利用贪心法求一个可行的近似解，然后用广度优先遍历，找出**解出队

代码

#include <iostream>  #include <queue>  #include<limits> #define min(x,y) (x<y?x:y)  using namespace std; //存放运费 int freight[3][4] = { 
    { 
   3,11,3,10},{ 
   1,9,2,8},{ 
   7,4,10,5} }; //存放销售价格 int sales[4] = { 
    3,6,5,6 }; //存放产量 int production[3] = { 
    7,4,9 }; //记录最小运输费用 int mincost =INT_MAX; //闭回路法所需数组，探寻周围空格是否存在回路 int key[5][3] = { 
    { 
   1,3,2},{ 
   2,1,3},{ 
   2,3,1},{ 
   3,2,1},{ 
   3,1,2} }; //为了方便，将查询出来的可行解放到一个结构体中 struct NodeType { 
    int r[4]; int lb; int pro[3][4] = { 
    0 }; bool operator <(const NodeType& s) const { 
    return s.lb<lb; } }; //分支回溯的复原函数 void ret() { 
    sales[0] = 3, sales[1] = 6, sales[2] = 5, sales[3] = 6; production[0] = 7, production[1] = 4, production[2] = 9; } //分支限界的约束函数 void bound(NodeType& e) { 
    int sum = 0, j; for (int m = 0; m < 4; m++) { 
    //先用贪心法求一个可行解 j = e.r[m]; int temp, i = 0; //min为最大小界，max为最小上界 int min = 100, max = 0, x[3] = { 
    0 }; for (int k = 0; k < 3; k++) { 
    if (min > freight[k][j]) { 
    x[0] = k; min = freight[k][j]; } } for (int k = 0; k < 3; k++) { 
    if (max < freight[k][j]) { 
    x[2] = k; max = freight[k][j]; } } x[1] = 3 - x[0] - x[2]; while (sales[j] > 0) { 
    temp = sales[j]; e.pro[x[i]][j] = min(sales[j], production[x[i]]); sales[j] -= production[x[i]]; if (sales[j] > 0) { 
    sum = sum + production[x[i]] * freight[x[i]][j]; production[x[i]] = 0; i++; } else { 
    sales[j] = 0; sum = sum + freight[x[i]][j] * temp; production[x[i]] -= temp; } } } e.lb = sum; //再将上界赋给可行解的结构体中 } //广度优先遍历，找出**解 void bfs() { 
    priority_queue<NodeType> qu; NodeType e, e1; e.r[4] = { 
    0 }; for (int m = 0; m < 4; m++) e.r[m] = m; bound(e);//求出一个可行解，然后进行检验 ret(); qu.push(e); int j = 0; while (!qu.empty()) { 
    e = qu.top(); qu.pop(); if (mincost > e.lb) { 
    mincost = e.lb; } e1.r[0] = e.r[0]; //闭回路法求解检验方案是否为最优 for (int k = 1; k < 4; k++) { 
    e1.r[k] = key[j][k - 1]; } j++; bound(e1);//在循环中，求出一个可行解，然后进行检验 ret(); if (e1.lb <= mincost) qu.push(e1); } //队列为空之后，全部出队保存在pro中值就是**解 cout << "总运费最小的调运方案为：" << endl; cout << "\tB1\tB2\tB3\tB4" << endl; cout << endl; for (int i = 0; i < 3; i++) { 
    cout << "A" << i + 1 << "\t"; for (int j = 0; j < 4; j++) { 
    cout << e.pro[i][j] << "\t"; } cout << endl; cout << endl; } cout << endl; } int main() { 
    bfs(); cout << "\t 运输的最小费用为:"; cout << mincost << endl; return 0; } 

参考

在豆丁上有讲具体算法思路的，这一题我自己琢磨了三天都没搞明白，看别人详解数学模型才看懂的，学都可以学~
https://www.docin.com/p-624702741.html