产销平衡运输问题
class 产销平衡运输问题
{
public static DataTable 沃格尔法生成初始基可行解(DataTable 运费表)
{
DataTable 初始解 = 运费表.Copy();
for (int i = 1; i
{
for (int j = 1; j
{
初始解.Rows[j][i] = 0;
}
}
DataTable temp = 运费表.Copy();
int 最小运价, 次小运价, 罚数, 最大行罚数所在行号, 最大列罚数所在列号, 最大行罚数, 最大列罚数;
int 最大行罚数所在行的最小运价列号 = 1, 最大列罚数所在列的最小运价行号 = 1;
while (temp.Rows.Count > 2)
{
最大行罚数 = 0; 最大行罚数所在行号 = 1;
for (int row = 1; row
{
最小运价 = 次小运价 = Convert.ToInt32(temp.Rows[row][1]); 最大行罚数所在行的最小运价列号 = 1;
int 行最小运价列号 = 1;
for (int col = 2; col
{
if (最小运价 >= Convert.ToInt32(temp.Rows[row][col]))
{
次小运价 = 最小运价;
最小运价 = Convert.ToInt32(temp.Rows[row][col]);
行最小运价列号 = col;
}
}
罚数 = 次小运价 - 最小运价;
if (最大行罚数
{
最大行罚数 = 罚数;
最大行罚数所在行号 = row;
最大行罚数所在行的最小运价列号 = 行最小运价列号;
}
}
最大列罚数 = 0; 最大列罚数所在列号 = 1;
int 列最小运价行号 = 1;
for (int col = 1; col
{
最小运价 = 次小运价 = Convert.ToInt32(temp.Rows[1][col]); 最大列罚数所在列的最小运价行号 = 1;
for (int row = 2; row
{
if (最小运价 >= Convert.ToInt32(temp.Rows[row][col]))
{
次小运价 = 最小运价;
最小运价 = Convert.ToInt32(temp.Rows[row][col]);
列最小运价行号 = row;
}
}
罚数 = 次小运价 - 最小运价;
if (最大列罚数
{
最大列罚数 = 罚数;
最大列罚数所在列号 = col;
最大列罚数所在列的最小运价行号 = 列最小运价行号;
}
}
int 行号, 列号;
if (最大行罚数 > 最大列罚数)
{
行号 = 最大行罚数所在行号;
列号 = 最大行罚数所在行的最小运价列号;
}
else
{
列号 = 最大列罚数所在列号;
行号 = 最大列罚数所在列的最小运价行号;
}
int 产量 = Convert.ToInt32(temp.Rows[行号][temp.Columns.Count - 1]);
int 销量 = Convert.ToInt32(temp.Rows[temp.Rows.Count - 1][列号]);
if (产量 == 销量)
{
初始解.Rows[Convert.ToInt32(temp.Rows[行号][0])][Convert.ToInt32(temp.Rows[0][列号])] = 产量;
temp.Rows.RemoveAt(行号);
temp.Columns.RemoveAt(列号);
}
else if (产量 > 销量)
{
初始解.Rows[Convert.ToInt32(temp.Rows[行号][0])][Convert.ToInt32(temp.Rows[0][列号])] = 销量;
temp.Columns.RemoveAt(列号);
temp.Rows[行号][temp.Columns.Count - 1] = 产量 - 销量;
}
else
{
初始解.Rows[Convert.ToInt32(temp.Rows[行号][0])][Convert.ToInt32(temp.Rows[0][列号])] = 产量;
temp.Rows.RemoveAt(行号);
temp.Rows[temp.Rows.Count - 1][列号] = 销量 - 产量;
}
}
初始解.Rows[初始解.Rows.Count - 1][初始解.Columns.Count - 1] = 计算总运费(初始解, 运费表);
return 初始解;
}
public static int 计算总运费(DataTable 运量表,DataTable 运费表)
{
int s = 0;
for (int i = 1; i
{
for (int j = 1; j
{
s += Convert.ToInt32(运量表.Rows[i][j]) * Convert.ToInt32(运费表.Rows[i][j]);
}
}
return s;
}
public static bool 寻找闭回路(DataTable 运量表, List 闭回路)
{
Point 起点 = 闭回路[0];
Point 当前点 = 闭回路[闭回路.Count - 1];
if (当前点.X == 起点.X && 当前点.Y != 起点.Y) return true; //X：行号，Y：列号
else
{
if (闭回路.Count % 2 == 1)
{
for (int i = 1; i
{
int row = (当前点.X - 1 + i) % (
运量表.Rows.Count - 2) + 1;
if (Convert.ToInt32(运量表.Rows[row][当前点.Y]) != 0)
{
闭回路.Add(new Point(row, 当前点.Y));
if (寻找闭回路(运量表, 闭回路))
{
return true;
}
else
{
闭回路.RemoveAt(闭回路.Count - 1);
}
}
}
return false;
}
else
{
for (int i = 1; i
{
int col = (当前点.Y - 1 + i) % (运量表.Columns.Count - 2) + 1;
if (Convert.ToInt32(运量表.Rows[当前点.X][col]) != 0)
{
闭回路.Add(new Point(当前点.X, col));
if (寻找闭回路(运量表, 闭回路))
{
return true;
}
else
{
闭回路.RemoveAt(闭回路.Count - 1);
}
}
}
return false;
}
}
}
public static void 求最优解(DataTable 运量表, DataTable 运费表)
{
List 闭回路 = new List();
int min = 0; List 检验数最小的闭回路 = new List();
while (true)
{
for (int i = 1; i
{
for (int j = 1; j
{
if (Convert.ToInt32(运量表.Rows[i][j]) == 0)
{
闭回路 = new List();
闭回路.Add(new Point(i, j));
寻找闭回路(运量表, 闭回路);
int s = 0; int k = 1;
foreach (Point pt in 闭回路)
{
s += k * Convert.ToInt32(运费表.Rows[pt.X][pt.Y]);
k *= -1;
}
if (s
{
检验数最小的闭回路 = 闭回路;
min = s;
}
}
}
}
if (min >= 0)
{
break;
}
else
{
min = int.MaxValue;
for (int i = 0; i
{
if (i % 2 == 1)
{
int row = 检验数最小的闭回路[i].X;
int col = 检验数最小的闭回路[i].Y;
int val = Convert.ToInt32(运量表.Rows[row][col]);
if (min > val)
{
min = val;
}
}
}
for (int i = 0; i
{
int row = 检验数最小的闭回路[i].X;
int col = 检验数最小的闭回路[i].Y;
int val = Convert.ToInt32(运量表.Rows[row][col]);
if (i % 2 == 0)
{
运量表.Rows[row][col] = val + min;
}
else
{
运量表.Rows[row][col] = val - min;
}
}
}
}
运量表.Rows[运量表.Rows.Count - 1][运量表.Columns.Count - 1] = 计算总运费(运量表, 运费表);
}
}