使用C语言实现vogel法解决运输问题的代码
时间: 2024-03-26 19:35:21 浏览: 19
以下是使用C语言实现vogel法解决运输问题的代码:
```c
#include<stdio.h>
#define ROW 3 // 行数
#define COL 4 // 列数
void Vogel(int a[ROW][COL],int row[],int col[],int *cost)
{
int i,j,min1,min2,minn,minn_pos;
int u[ROW],v[COL];
for(i=0;i<ROW;i++) // 初始化u,v
{
u[i]=0;
}
for(i=0;i<COL;i++)
{
v[i]=0;
}
while(1)
{
// 计算u,v
u[0]=0;
for(i=1;i<ROW;i++)
{
u[i]=a[i][0]-min1;
for(j=1;j<COL;j++)
{
if(a[i][j]-min1<u[i])
{
u[i]=a[i][j]-min1;
}
}
}
v[0]=a[0][0]-min1;
for(j=1;j<COL;j++)
{
v[j]=a[0][j]-min1;
for(i=1;i<ROW;i++)
{
if(a[i][j]-min1<v[j])
{
v[j]=a[i][j]-min1;
}
}
}
// 计算min1,min2
min1=10000;
for(i=1;i<ROW;i++)
{
for(j=1;j<COL;j++)
{
if(a[i][j]-u[i]-v[j]<min1)
{
min1=a[i][j]-u[i]-v[j];
}
}
}
if(min1>=0) // 所有非基变量均>=0
{
break;
}
// 计算minn,minn_pos
for(i=1;i<ROW;i++)
{
for(j=1;j<COL;j++)
{
if(a[i][j]-u[i]-v[j]==min1)
{
if(row[i]>1&&col[j]>1)
{
min2=10000;
if(a[i][j+1]-u[i]-v[j+1]<min2&&a[i][j+1]-u[i]-v[j+1]>0)
{
min2=a[i][j+1]-u[i]-v[j+1];
}
if(a[i+1][j]-u[i+1]-v[j]<min2&&a[i+1][j]-u[i+1]-v[j]>0)
{
min2=a[i+1][j]-u[i+1]-v[j];
}
if(a[i+1][j+1]-u[i+1]-v[j+1]<min2&&a[i+1][j+1]-u[i+1]-v[j+1]>0)
{
min2=a[i+1][j+1]-u[i+1]-v[j+1];
}
if(min2==10000)
{
minn_pos=i*COL+j;
goto label;
}
minn=min2;
minn_pos=i*COL+j;
}
}
}
}
// 计算aij
label:
row[minn_pos/COL]--;
col[minn_pos%COL]--;
a[minn_pos/COL][minn_pos%COL]=minn;
for(i=0;i<ROW;i++)
{
for(j=0;j<COL;j++)
{
printf("%d ",a[i][j]);
}
printf("\n");
}
printf("\n");
*cost+=minn;
}
}
int main()
{
int a[ROW][COL]={
{0,0,0,0},
{0,2,3,1},
{0,5,4,8}
};
int row[ROW]={0,2,1};
int col[COL]={0,2,2,1};
int cost=0;
Vogel(a,row,col,&cost);
printf("最小成本:%d",cost);
return 0;
}
```
这段代码实现了vogel法求解运输问题的过程。其中,`a`数组表示各个产地到各个销地的运输成本,`row`数组表示各个产地还有多少货物需要运输,`col`数组表示各个销地还有多少货物需要接收,`cost`表示最小成本。