运筹学教学|运输问题代码分享（Java代码及详细注释）
2023-02-19 12:22:45 时间
Part1算法流程
- 最小元素法求得初始可行解：
- 行元素较大，则划去该列中所有未被处理的元素，并将基变量设为列元素的值；
- 行元素较小，则划去该行中所有未被处理的元素，并将基变量设为行元素的值；
- 大小相等，将基变量设为行元素的值，并在该行和列中再找一个最小且未被处理的元素，标记为基变量，值设为0，然后则划去该列和该列中其它未被处理的元素。
- 找到矩阵中花费最小且未被处理的元素，标记为基变量；
- 判断该元素的行元素（产量）与列元素（需求）的大小关系：
- 循环(行数 + 列数 - 1)次后得到(行数 + 列数 - 1)个基变量；
- 闭回路法求检验数：
- 对每一个非基变量NBV，用回溯法找出其回路：
- 先进行行搜索，找到NBV所在行的一个基变量BV1，记录其位置；
- 接着进行列搜索，尝试找到BV1所在行的另一个基变量BV2：
- 如果找不到，则说明BV1不在非基变量的回路当中，回到第1步，寻找另一个基变量再次进行列搜索；
- 如果找到了，则再进行行搜索，尝试找到BV2所在行的另一个基变量BV3：
- 如果找不到，则说明BV2不在非基变量的回路当中，回到找到BV2的那一步，寻找另一个基变量再次进行行搜索；
- 如果找到了，则再进行列搜索，尝试找到BV3所在列的另一个基变量BV4，或非基变量NBV：
- 如果找不到，则说明BV3不在非基变量的回路当中，回到找到BV3的那一步，寻找另一个基变量再次进行列搜索；
- 如果找到了非基变量NBV，则说明找到了回路，回溯记录所有找到的基变量即可得到回路；
- 如果找到了另一个基变量BV4，则再次进行行搜索，规则与找到BV2后相同。
- 根据找到的回路确定NBV的检验数；
- 对每一个非基变量NBV，用回溯法找出其回路：
- 判断非基变量的检验数是否全为正：
- 若是，则说明已经找到最优解；
- 若否，则将检验数最小的非基变量NBV入基，根据回路，将相应的一个基变量出基，回到第2步，再次用闭回路法求检验数；
Part2代码展示
import java.io.FileNotFoundException;
import java.io.FileOutputStream;
import java.io.FileReader;
import java.io.IOException;
import java.io.OutputStream;
import java.io.OutputStreamWriter;
import java.util.Scanner;
public class TP
{
public static final int maxsize = 10000;
public static final int maxsize_n = 100;
public static final int max = 1000; //实际问题中出现的运费不能超过max，即max为最大运费
public static class Node
{
public int x;
public int y;
public int pre; //pre表示指向它的前一结点
public int flag; //flag表示搜索行（或列）的状态，取值为0、1,其中1表示行搜索，0表示列搜索。
}
public static class Node1
{
public int x; //x用于记录最小元素所在位置的行坐标
public int y; //y用于记录最小元素所在位置的列坐标
public int min_flag; //min_flag用于记录最小元素所在位置的状态，数值上等于flag数组里的对应元素
}
private static Node[] sq;
private static int[][] circle; //二维数组存储数据
private static int[][] flag; //用于存储判断circle对应位置的状态，0为初始状态，1表示基变量所在位置，2表示在进行最小元素法时被划去。
private static int[][] base_array; //base_array矩阵用于物品的调运方案
private static int front;
private static int rear;
private static int m;
private static int n;
static void min_method(int m,int n) //求初始基，方法为最小元素法
{
int i,j,k;
Node1 temp_min = new Node1(),temp_min1 = new Node1();
for (i=1;i<=m;i++) //初始化
{
for (j=1;j<=n;j++)
{
base_array[i][j]=0;
flag[i][j]=0; //标记每个位置的元素都没有被处理
}
}
for (k=1;k<=m+n-1;k++) //最多循环m+n-1次，因为基变量的个数为m+n-1；
{
temp_min.min_flag=max;
temp_min.x=0;
temp_min.y=0;
//下面的两重循环的作用是找到没有处理元素中的最小元素
for (i=1;i<=m;i++)
{
for (j=1;j<=n;j++)
{
if ( (flag[i][j]==0) && (circle[i][j]<temp_min.min_flag) ) //该点所在位置没有处理，并且该点所在位置的运费比记录的小
{
temp_min.x=i;
temp_min.y=j;
temp_min.min_flag=circle[i][j];
}
}
}
//下面对前面找到的最小元素所在的行或列进行处理
if (circle[temp_min.x][n+1]>circle[m+1][temp_min.y]) //该最小元素所在位置的行元素（销量）比列元素（产量）大
{
for (i=1;i<=m;i++)
{
if (flag[i][temp_min.y]==0) //表示该位置没有被处理
{
flag[i][temp_min.y]=2; //标记该列的所有元素划去
}
}
flag[temp_min.x][temp_min.y]=1; //标记最小元素所在位置为基变量所在位置
base_array[temp_min.x][temp_min.y]=circle[m+1][temp_min.y]; //更新调运方案矩阵
circle[temp_min.x][n+1]-=circle[m+1][temp_min.y];
circle[m+1][temp_min.y]=0;
}
else if (circle[temp_min.x][n+1]<circle[m+1][temp_min.y]) //该最小元素所在位置的行元素（销量）比列元素（产量）小
{
for (j=1;j<=n;j++)
{
if (flag[temp_min.x][j]==0) //表示该位置没有被处理
{
flag[temp_min.x][j]=2; //标记该行的所有元素划去
}
}
flag[temp_min.x][temp_min.y]=1; //标记最小元素所在位置为基变量所在位置
base_array[temp_min.x][temp_min.y]=circle[temp_min.x][n+1]; //更新调运方案矩阵
circle[m+1][temp_min.y]-=circle[temp_min.x][n+1];
circle[temp_min.x][n+1]=0;
}
else //该最小元素所在位置的行元素（销量）与行元素（产量）相同
{
flag[temp_min.x][temp_min.y]=1; //标记最小元素所在位置为基变量所在位置
base_array[temp_min.x][temp_min.y]=circle[m+1][temp_min.y]; //更新调运方案矩阵
circle[m+1][temp_min.y]=0;
circle[temp_min.x][n+1]=0;
//为了减少调整次数，应该在最小运费上添加0,一种理念，减少迭代次数
temp_min1.min_flag=max;
temp_min1.x=0;
temp_min1.y=0;
for (i=1;i<=m;i++)
{
if ( (circle[i][temp_min.y]<temp_min1.min_flag) && (flag[i][temp_min.y]==0) )
{
temp_min1.min_flag=circle[i][temp_min.y];
temp_min1.x=i;
temp_min1.y=temp_min.y;
}
}
for (j=1;j<=n;j++)
{
if ( (circle[temp_min.x][j]<temp_min1.min_flag) && (flag[temp_min.x][j]==0) )
{
temp_min1.min_flag=circle[temp_min.x][j];
temp_min1.x=temp_min.x;
temp_min1.y=j;
}
}
flag[temp_min1.x][temp_min1.y]=1; //在最小元素所在的位置上画0，即flag的相应位置赋值1
for (i=1;i<=m;i++)
{
if (flag[i][temp_min.y]==0) //表示该位置没有被处理
{
flag[i][temp_min.y]=2; //标记该列的所有元素划去
}
}
for (j=1;j<=n;j++)
{
if (flag[temp_min.x][j]==0) //表示该位置没有被处理
{
flag[temp_min.x][j]=2; //标记该列的所有元素划去
}
}
}
}
}
static void restore(int m,int n) //将求闭回路后flag数组中改变的状态复原
{
int i,j;
for (i=1;i<=m;i++)
{
for (j=0;j<=n;j++)
{
if (flag[i][j]==-1)
{
flag[i][j]=1;
}
}
}
}
static void printpath() //将求得的闭回路写到输出文件中并输出到缓存文件temp_close中
{
int i;
try
{
OutputStream out = new FileOutputStream("./temp_close.txt");
OutputStreamWriter writer = new OutputStreamWriter(out, "UTF-8");
System.out.println();
i=rear;
writer.write("\r\n");
do
{
System.out.println("(" + sq[i].x + "," + sq[i].y + ")");
writer.write(sq[i].x + " " + sq[i].y + "\r\n");
i=sq[i].pre; //找前一个结点
}while(i!=0);
System.out.println("上面的点构成一个闭回路，是起点为最后一个点。");
writer.close();
out.close(); //i=0为入口
}
catch (IOException e)
{
// File not found
System.out.println("Temp File not found!");
System.exit(-1);
}
}
static int close_loop(int m,int n,int m1,int n1) //利用回溯法确定从已知结点出发的闭回路，m,n表示矩阵的规模，m1,n1表示开始结点
{
int i,j,x,y;
sq[1].x=m1;sq[1].y=n1;sq[1].pre=0;sq[1].flag=1; //开始结点
front=1;rear=1;
while(front<=rear) //队列非空
{
x=sq[front].x;y=sq[front].y; //开始结点
if (sq[front].flag==1) //表示进行行搜索
{
i=x;
for (j=1;j<=n;j++)
{
if (flag[i][j]==1)
{
rear++;
sq[rear].x=i;//记录数据
sq[rear].y=j;
sq[rear].pre=front;//记录前一个节点
sq[rear].flag=0; //标志为下次进行列搜索
flag[i][j]=-1; //标记(i,j)已经达到，防止再重复
if (sq[rear].y==n1)
{
printpath();
restore(m,n);
return 1;
}
}
}
}
else //表示进行列搜索
{
j=y;
for (i=1;i<=m;i++)
{
if (flag[i][j]==1)
{
rear++;
sq[rear].x=i;
sq[rear].y=j;
sq[rear].pre=front;
sq[rear].flag=1; //标志为下次进行行搜索
flag[i][j]=-1; //标记(i,j)已经达到，防止再重复
}
}
}
front++;
}
return -1;
}
static void close_method() //利用闭回路法确定非基变量的检验数
{
int i,j,sum,x = 0,y = 0,flag1;
try
{
for (i=1;i<=m;i++)
{
for (j=1;j<=n;j++)
{
if (flag[i][j]==2)
{
int rtn = close_loop(m,n,i,j);
if (rtn==1) //如果为非基变量，则找出其闭回路，并计算检验数
{
sum=0;
flag1=1;
Scanner in = new Scanner(new FileReader("temp_close.txt"));
while(in.hasNext())
{
x = in.nextInt();
if(!in.hasNext())
{
break;
}
y = in.nextInt();
if (flag1==1) //设非基变量为1，依次对检验数进行增减操作
{
sum+=circle[x][y];
flag1=0;
}
else
{
sum-=circle[x][y];
flag1=1;
}
}
sum+=circle[x][y];
base_array[i][j]=circle[i][j]-sum;
in.close();
}
}
}
}
} catch (FileNotFoundException e)
{
// File not found
System.out.println("Instance File not found!");
System.exit(-1);
}
}
static Node1 if_negative() //判断非基变量的检验数是否全为正，函数返回检验数最小的数以及它所在的位置
{
int i,j;
Node1 nege_min = new Node1();
nege_min.min_flag=max; //初始化最小检验数记录值
nege_min.x=0;
nege_min.y=0;
for (i=1;i<=m;i++)
{
for (j=1;j<=n;j++)
{
if ( (flag[i][j]==2) && (base_array[i][j]<nege_min.min_flag) )
{
nege_min.x=i;
nege_min.y=j;
nege_min.min_flag=base_array[i][j]; //出现更小的检验数的点，更新nege_min
}
}
}
return nege_min;
}
static void close_adjust(int i,int j) //close_adjust()函数的作用是利用闭回路法调整基变量，使其更接近最优解
{
int x,y,flag1=1,num1=-1,num2=-1,main_flag=1; //num1用于存储闭回路中的结点个数
//main_flag的作用是作为基变量变为非基变量的一个状态位，取值为0或1，设置这个状态位是为了保证只有一个非基变量变为基变量
Node1 temp = new Node1();
temp.min_flag=max; //初始化
temp.x=0;
temp.y=0;
close_loop(m,n,i,j);
try
{
FileReader fileReader = new FileReader("temp_close.txt");
Scanner in = new Scanner(fileReader);
while(in.hasNext())
{
num1++; //统计闭回路中结点的个数
x = in.nextInt();
if(!in.hasNext())
{
break;
}
y = in.nextInt();
if ( (flag1==1) && (flag[x][y]==1) )
{
if(base_array[x][y]<=temp.min_flag)
{
temp.min_flag=base_array[x][y];
temp.x=x;
temp.y=y;
}
flag1=0;
}
else
{
flag1=1;
}
}
num1++;
in.close();
fileReader = new FileReader("temp_close.txt");
in = new Scanner(fileReader);
//在前面找到的最小值和位置的基础上利用闭回路进行调整
flag1=1;
while(in.hasNext())
{
num2++;
x = in.nextInt();
if(!in.hasNext())
{
break;
}
y = in.nextInt();
if (flag1==1)
{
base_array[x][y]-=temp.min_flag;
flag1=0;
if ( (base_array[x][y]==0) && (main_flag==1) )
{
flag[x][y]=2; //基变量变为非基变量
main_flag=0; //状态从1变为0，表示已经有一个基变量变为非基变量，其它的基变量即使满足条件也不能变为非基变量
}
}
else
{
if (num2==num1-1)
{
flag[x][y]=1;
base_array[x][y]=temp.min_flag;
}
else
{
base_array[x][y]+=temp.min_flag;
}
flag1=1;
}
}
in.reset();
in.close();
}
catch (FileNotFoundException e)
{
// File not found
System.out.println("Instance File not found!");
System.exit(-1);
}
catch (IOException e)
{
System.out.println(e);
System.exit(-1);
}
}
public static void main(String[] args)
{
sq = new Node[maxsize];
for(int q=0;q<maxsize;q++)
{
sq[q] = new Node();
}
circle = new int[maxsize_n][maxsize_n];
flag = new int[maxsize_n][maxsize_n];
for(int q=0;q<maxsize_n;q++)
{
for(int w=0;w<maxsize_n;w++)
{
flag[q][w]=0;
}
}
base_array = new int[maxsize_n][maxsize_n];
try
{
int i,j,sum;
Node1 min = new Node1();
boolean c;
Scanner f1 = new Scanner(new FileReader("in.txt"));
System.out.println();
OutputStream f2out = new FileOutputStream("out.txt");
OutputStreamWriter f2writer = new OutputStreamWriter(f2out, "UTF-8");
c = f1.next().equals("#"); //文件读入
if(c)
{
m = f1.nextInt();
n = f1.nextInt();
System.out.println("m=" + m +" n=" + n);
sum=0;
for (i=1;i<=m;i++)
{
for (j=1;j<=n;j++)
{
circle[i][j] = f1.nextInt();;
}
}
for (i=1;i<=m;i++)
{
circle[i][n+1] = f1.nextInt();
}
for (j=1;j<=n;j++)
{
circle[m+1][j] = f1.nextInt();;
}
circle[m+1][n+1]=0; //完成运输问题矩阵的建立，包括运价与供应量需求量
for (i=1;i<=m+1;i++)
{
for (j=1;j<=n+1;j++)
{
System.out.print(circle[i][j] + "\t");
}
System.out.println();
}
min_method(m,n);
close_method();
min=if_negative();
while ( min.min_flag<0 ) //如果存在最小检验数小于0，继续进行调整
{
close_adjust(min.x,min.y);
close_method();
min=if_negative();
}
f2writer.write("最终调运方案为：\r\n");
System.out.println("最终调运方案为：");
for (i=1;i<=m;i++)
{
for (j=1;j<=n;j++)
{
if (flag[i][j]==1)
{
f2writer.write(base_array[i][j] + "\t");
System.out.print(base_array[i][j] + "\t"); //输出最终结果
}
else
{
f2writer.write("0\t");
System.out.print("0\t");
}
}
f2writer.write("\r\n");
System.out.println();
}
f2writer.write("最优值为：\r\n");
System.out.println("最优值为：");
for (i=1;i<=m;i++)
{
for (j=1;j<=n;j++)
{
if (flag[i][j]==1)
{
sum+=base_array[i][j]*circle[i][j];//计算总价格：数量*单位运价
}
}
}
System.out.println(sum);
f2writer.write(sum + "\r\n");
}
f1.close();
f2writer.close();
f2out.close();
}
catch (FileNotFoundException e)
{
// File not found
System.out.println("Input File not found!");
System.exit(-1);
}
catch (IOException e)
{
System.out.println(e);
System.exit(-1);
}
}
}
样例输入
# 3 4 10 2 20 11 12 7 9 20 2 14 16 18 15 25 5 5 15 15 10 第一行两个数字分别表示供应方数量和需求方数量 后面三行通过二维表的方式记录每个供应方到需求方的运价 最后两行分别表示每个供应方的最大供应量和每个需求方的最大需求量
样例输出
m=3 n=4 10 2 20 11 15 12 7 9 20 25 2 14 16 18 5 5 15 15 10 0
(2,1) (2,2) (1,2) (1,1) 上面的点构成一个闭回路，是起点为最后一个点。
(2,3) (2,2) (1,2) (1,3) 上面的点构成一个闭回路，是起点为最后一个点。
(2,4) (2,2) (1,2) (1,4) 上面的点构成一个闭回路，是起点为最后一个点。
(2,2) (2,1) (3,1) (3,2) 上面的点构成一个闭回路，是起点为最后一个点。
(2,3) (2,1) (3,1) (3,3) 上面的点构成一个闭回路，是起点为最后一个点。
(2,4) (2,1) (3,1) (3,4) 上面的点构成一个闭回路，是起点为最后一个点。
(2,4) (2,2) (1,2) (1,4) 上面的点构成一个闭回路，是起点为最后一个点。
(2,1) (2,2) (1,2) (1,1) 上面的点构成一个闭回路，是起点为最后一个点。
(2,3) (2,2) (1,2) (1,3) 上面的点构成一个闭回路，是起点为最后一个点。
(1,4) (1,2) (2,2) (2,4) 上面的点构成一个闭回路，是起点为最后一个点。
(2,2) (2,1) (3,1) (3,2) 上面的点构成一个闭回路，是起点为最后一个点。
(2,3) (2,1) (3,1) (3,3) 上面的点构成一个闭回路，是起点为最后一个点。
(1,4) (1,2) (2,2) (2,1) (3,1) (3,4) 上面的点构成一个闭回路，是起点为最后一个点。 最终调运方案为： 0 5 0 10 0 10 15 0 5 0 0 0 最优值为： 335
上面列出了每一次迭代时用来调整解的环（闭回路）。
以上即为运输问题算法及代码的全部内容，你看明白了吗？
-The End-
文案&排版&代码改写：吕其乐（华中科技大学管理学院本科二年级）
指导老师：秦虎老师 （华中科技大学管理学院）
如对文中内容有疑问，欢迎交流。PS：部分资料来自网络。
相关文章
- Java强制类型转换异常
- Java中类型的转化
- Java中创建对象的方式
- Java中Scanner类的使用
- 关于Java判断字符串相等的常见问题
- 通过Java实现双色球原理
- 消息队列：第三章：在Java中使用消息队列
- Java从键盘上输入与输出
- Java家教系统家教网站家教兼职系统
- java家装网装修网站装修系统源码
- java开发的考研系统大学生考研推荐网站考研网站源码
- Maven插件方式执行CheckStyle并自定义风格文件
- JAVA中使用最广泛的本地缓存？Ehcache的自信从何而来 —— 感受来自Ehcache的强大实力
- SpringBoot自动装配原理分析，手写starter组件
- 惊艳！Alibaba内部流行的“Java突击宝典”，程序员升职加薪必备
- 用javascript分类刷leetcode20.字符串(图文视频讲解)2
- JavaScript刷LeetCode模板技巧篇（一）2
- JavaScript刷LeetCode心得
- 用javascript分类刷leetcode22.字典树(图文视频讲解)
- 2.4K star，一个高性能、无侵入的Java性能监控和统计工具，有点东西！