分支定界法求整数规划c语言代码
时间: 2023-07-30 15:12:53 浏览: 116
以下是一个简单的分支定界法求解整数规划的C语言代码:
```c
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#define MAXN 100 // 最大维数
#define INF 1e9 // 无限大
int n; // 变量数
double a[MAXN][MAXN], b[MAXN], c[MAXN]; // 约束系数、常数、目标函数系数
double ans[MAXN], bestans[MAXN]; // 当前解、最优解
double best; // 最优值
int vis[MAXN]; // 标记变量是否取整
int msk; // 当前搜索的二进制状态
// 计算当前解的目标函数值
double calc() {
double res = 0;
for (int i = 0; i < n; i++) res += ans[i] * c[i];
return res;
}
// 判断是否满足当前状态下的所有约束条件
bool check() {
for (int i = 0; i < n; i++) {
double sum = 0;
for (int j = 0; j < n; j++) sum += a[i][j] * ans[j];
if (sum > b[i]) return false;
}
return true;
}
// 求解整数规划
void dfs(int k) {
if (k == n) {
if (check()) { // 当前解可行
double val = calc(); // 计算目标函数值
if (val < best) { // 更新最优解
best = val;
for (int i = 0; i < n; i++) bestans[i] = ans[i];
}
}
return;
}
int x = vis[k] = msk >> k & 1; // 取整或不取整
ans[k] = x ? floor(ans[k]) : ceil(ans[k]); // 更新当前解
if (check()) dfs(k + 1); // 继续搜索
if (x ^ 1) { // 如果当前变量未取整,可以尝试取整
ans[k] = floor(ans[k]);
if (check()) dfs(k + 1);
}
if (x ^ 0) { // 如果当前变量已取整,可以尝试不取整
ans[k] = ceil(ans[k]);
if (check()) dfs(k + 1);
}
vis[k] = -1; // 回溯
}
// 初始化
void init() {
scanf("%d", &n);
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) scanf("%lf", &a[i][j]);
scanf("%lf", &b[i]);
}
for (int i = 0; i < n; i++) scanf("%lf", &c[i]);
best = INF;
}
int main() {
init();
for (int i = 0; i < n; i++) ans[i] = c[i] / a[i][i]; // 初值
dfs(0);
printf("最优解为:%.2lf,取整后为:\n", best);
for (int i = 0; i < n; i++) printf("%d ", (int)bestans[i]);
printf("\n");
return 0;
}
```
其中,`dfs`函数实现了分支定界算法的递归搜索过程,`check`函数用于判断当前解是否满足所有约束条件,`calc`函数用于计算当前解的目标函数值。在搜索过程中,我们使用一个二进制状态 `msk` 来记录每个变量是否已经取整,从而实现分支的过程。最终,我们输出最优解及其取整后的结果。