表上作业法和伏格尔法解决运输问题的c语言代码
时间: 2024-01-27 09:42:49 浏览: 114
表上作业法和伏格尔法是两种经典的求解运输问题的算法。下面分别给出它们的 C 语言代码实现。
1. 表上作业法
```c
#include<stdio.h>
#include<limits.h>
#define N 3 // 供应地数量
#define M 4 // 需求地数量
#define INF INT_MAX // 表示无穷大
int main() {
int supply[N] = {10, 20, 30}; // 各个供应地的供应量
int demand[M] = {15, 10, 20, 15}; // 各个需求地的需求量
int cost[N][M] = {{2, 3, 1, 4},
{4, 2, 5, 1},
{3, 4, 2, 3}}; // 运输成本
int allocated[N][M] = {0}; // 分配矩阵
int i, j, k, min, flag;
while (1) {
// 找到未分配的最小元素
min = INF;
flag = 0;
for (i = 0; i < N; i++) {
for (j = 0; j < M; j++) {
if (allocated[i][j] == 0 && cost[i][j] < min) {
min = cost[i][j];
k = i;
flag = 1;
}
}
}
if (flag == 0) {
break;
}
// 进行分配
flag = 0;
for (j = 0; j < M; j++) {
if (allocated[k][j] == 0 && demand[j] > 0) {
allocated[k][j] = supply[k] < demand[j] ? supply[k] : demand[j];
supply[k] -= allocated[k][j];
demand[j] -= allocated[k][j];
flag = 1;
}
if (supply[k] == 0) {
break;
}
}
if (flag == 0) {
break;
}
}
// 输出最终结果
printf("最优解:\n");
for (i = 0; i < N; i++) {
for (j = 0; j < M; j++) {
printf("%d ", allocated[i][j]);
}
printf("\n");
}
return 0;
}
```
2. 伏格尔法
```c
#include<stdio.h>
#include<limits.h>
#define N 3 // 供应地数量
#define M 4 // 需求地数量
#define INF INT_MAX // 表示无穷大
int main() {
int supply[N] = {10, 20, 30}; // 各个供应地的供应量
int demand[M] = {15, 10, 20, 15}; // 各个需求地的需求量
int cost[N][M] = {{2, 3, 1, 4},
{4, 2, 5, 1},
{3, 4, 2, 3}}; // 运输成本
int allocated[N][M] = {0}; // 分配矩阵
int i, j, k, min, flag;
while (1) {
// 找到未分配的最小元素
min = INF;
flag = 0;
for (i = 0; i < N; i++) {
for (j = 0; j < M; j++) {
if (allocated[i][j] == 0 && cost[i][j] < min) {
min = cost[i][j];
k = i;
flag = 1;
}
}
}
if (flag == 0) {
break;
}
// 找到最小元素所在的行或列,进行分配
flag = 0;
for (j = 0; j < M; j++) {
if (allocated[k][j] == 0 && demand[j] > 0) {
allocated[k][j] = supply[k] < demand[j] ? supply[k] : demand[j];
supply[k] -= allocated[k][j];
demand[j] -= allocated[k][j];
flag = 1;
}
if (supply[k] == 0) {
break;
}
}
if (flag == 0) {
for (i = 0; i < N; i++) {
if (allocated[i][j] == 0 && supply[i] > 0) {
allocated[i][j] = supply[i] < demand[j] ? supply[i] : demand[j];
supply[i] -= allocated[i][j];
demand[j] -= allocated[i][j];
flag = 1;
}
if (demand[j] == 0) {
break;
}
}
}
if (flag == 0) {
break;
}
}
// 输出最终结果
printf("最优解:\n");
for (i = 0; i < N; i++) {
for (j = 0; j < M; j++) {
printf("%d ", allocated[i][j]);
}
printf("\n");
}
return 0;
}
```