整数规划：从零一规划到混合整数规划的全面解析

### 整数规划：从零一规划到混合整数规划的全面解析 整数规划在优化问题中占据着重要地位，它涉及到变量取值为整数的约束条件，广泛应用于资源分配、调度、组合优化等领域。本文将详细介绍零一整数规划、全整数规划和混合整数规划的相关内容，包括问题描述、求解方法、代码实现以及实例分析。 #### 1. 零一整数规划 零一整数规划是一种特殊的整数规划问题，其中变量的取值只能为 0 或 1。问题的一般形式为： - **目标函数**：最小化（或最大化） $\sum_{j=1}^{n} c_j x_j$ - **约束条件**：$\sum_{j=1}^{n} a_{ij} x_j \leq b_i$，$i = 1, 2, \cdots, m$；$x_j \in \{0, 1\}$，$j = 1, 2, \cdots, n$ 该问题可以通过隐式枚举所有 $2^n$ 个零一向量来求解，具体步骤如下： 1. 选择一个自由变量 $x_j$ 并将其固定为 1。 2. 枚举部分解的所有完成情况。 3. 将变量 $x_j$ 固定为 0，并对 $x_j = 0$ 的子问题重复上述过程。 以下是 Java 实现的代码： ```java public static void zeroOneIntegerProgramming(boolean minimize, int n, int m, int a[][], int b[], int c[], int sol[]) { int i,j,k,optvalue,elm1=0,elm2,elm3,elm4,idx,sub1,sub2,sub3; int item1,item2,item3; int ccopy[] = new int[n + 1]; int aux1[] = new int[n + 1]; int aux2[] = new int[n + 1]; int aux3[] = new int[n + 1]; int aux4[] = new int[n + 2]; int aux5[] = new int[m + 1]; int aux6[] = new int[m + 1]; int aux7[] = new int[m + 1]; boolean cminus[] = new boolean[n + 1]; boolean optimalfound,backtrack=false,outer; // scan for the negative objective coefficients if (!minimize) for (j=1; j<=n; j++) c[j] = -c[j]; for (j=1; j<=n; j++) { cminus[j] = false; ccopy[j] = c[j]; } for (j=1; j<=n; j++) if (c[j] < 0) { cminus[j] = true; c[j] = -c[j]; for (i=1; i<=m; i++) { b[i] -= a[i][j]; a[i][j] = -a[i][j]; } } for (i=1; i<=m; i++) aux5[i] = b[i]; elm4 = 1; for (j=1; j<=n; j++) { aux3[j] = 0; elm4 += c[j]; } optvalue = elm4 + elm4; sub2 = 0; sub3 = 0; elm4 = 0; aux4[1] = 0; optimalfound = false; iterate: while (true) { if (backtrack) { // backtracking backtrack = false; outer = false; for (j=1; j<=n; j++) if (aux3[j] < 0) aux3[j] = 0; if (sub2 > 0) do { sub1 = sub3; sub3 -= aux4[sub2+1]; for (j=sub3+1; j<=sub1; j++) aux3[aux2[j]] = 0; sub1 = Math.abs(aux1[sub2]); aux4[sub2] += sub1; for (j=sub3-sub1+1; j<=sub3; j++) { sub1 = aux2[j]; aux3[sub1] = 2; elm4 -= c[sub1]; for (i=1; i<=m; i++) aux5[i] += a[i][sub1]; } sub2--; if (aux1[sub2+1] >= 0) { outer = true; continue iterate; } } while (sub2 != 0); if (outer) continue; sol[0] = optvalue; a[0][0] = (optimalfound ? 0 : 1); for (j=1; j<=n; j++) if (cminus[j]) { sol[j] = ((sol[j] == 0) ? 1 : 0); sol[0] += ccopy[j]; } for (j=1; j<=n; j++) c[j] = ccopy[j]; if (!minimize) sol[0] = -sol[0]; return; } sub1 = 0; idx = 0; for (i=1; i<=m; i++) { item1 = aux5[i]; if (item1 < 0) { // infeasible constraint i sub1++; elm3 = 0; elm1 = item1; elm2 = -Integer.MAX_VALUE; for (j=1; j<=n; j++) if (aux3[j] <= 0) if (c[j] + elm4 >= optvalue) { aux3[j] = 2; aux4[sub2+1]++; sub3++; aux2[sub3] = j; } else { item2 = a[i][j]; if (item2 < 0) { elm1 -= item2; elm3 += c[j]; if (elm2 < item2) elm2 = item2; } } if (elm1 < 0) { backtrack = true; continue iterate; } if (elm1 + elm2 < 0) { if (elm3 + elm4 >= optvalue) { backtrack = true; continue iterate; } for (j=1; j<=n; j++) { item2 = a[i][j]; item3 = aux3[j]; if (item2 < 0) { if (item3 == 0) { aux3[j] = -2; for (k=1; k<=idx; k++) { aux7[k] -= a[aux6[k]][j]; if (aux7[k] < 0) { backtrack = true; continue iterate; } } } } else if (item3 < 0) { elm1 -= item2; if (elm1 < 0) { backtrack = true; continue iterate; } elm3 += c[j]; if (elm3 + elm4 >= optvalue) { backtrack = true; continue iterate; } } } idx++; aux6[idx] = i; aux7[idx] = elm1; } } } if (sub1 == 0) { // updating the best solution optvalue = elm4; optimalfound = true; for (j=1; j<=n; j++) sol[j] = ((aux3[j] == 1) ? 1 : 0); backtrack = true; continue iterate; } if (idx == 0) { sub1 = 0; elm3 = -Integer.MAX_VALUE; for (j=1; j<=n; j++) if (aux3[j] == 0) { elm2 = 0; for (i=1; i<=m; i++) { item1 = aux5[i]; item2 = a[i][j]; if (item1 < item2) elm2 += (item1 - item2); } item1 = c[j]; if ((elm2 > elm3) || (elm2 == elm3) && (item1 < elm1)) { elm1 = item1; elm3 = elm2; sub1 = j; } } if (sub1 == 0) { backtrack = true; continue iterate; } sub2++; aux4[sub2+1] = 0; sub3++; aux2[sub3] = sub1; aux1[sub2] = 1; aux3[sub1] = 1; elm4 += c[sub1]; for (i=1; i<=m; i++) aux5[i] -= a[i][sub1]; } else { sub2++; aux1[sub2] = 0; aux4[sub2+1] = 0; for (j=1; j<=n; j++) if (aux3[j] < 0) { sub3++; aux2[sub3] = j; aux1[sub2]--; elm4 += c[j]; aux3[j] = 1; for (i=1; i<=m; i++) aux5[i] -= a[i][j]; } } } } ``` 以下是一个具体的例子，求解一个具有 4 个变量和 3 个约束的零一整数规划问题： ```java package Optimization; public class Test_zeroOneProgram extends Object { public static void main(String args[]) { int n = 4; int m = 3; int a[][] = {{0, 0, 0, 0, 0}, {0, -10, -13, -11, -23}, {0, -4, -6, -11, -16}, {0, -12, -10, -5, -9}}; int b[] = {0, -10, -12, -8}; int c[] = {0, 12, 14, 23, 36}; int sol[] = new int[n + 1]; Optimize.zeroOneIntegerProgramming(true, n, m, a, b, c, sol); if (a[0][0] > 0) System.out.println("No feasible solution."); else { System.out.print("Optimal solution found.\n Solution vector: "); for (int i=1; i<=n; i++) System.out.print(" " + sol[i]); System.out.println("\n Optimal value of the objective function = " + sol[0]); } } } ``` 输出结果为： ```plaintext Optimal solution found. Solution vector: 1 0 1 0 Optimal value of the objective function = 35 ``` 该算法的流程图如下： ```mermaid graph TD; A[开始] --> B[扫描负目标系数]; B --> C[初始化变量]; C --> D{是否回溯}; D -- 是 --> E[回溯操作]; D -- 否 --> F[检查约束可行性]; F --> G{是否有不可行约束}; G -- 是 --> H[处理不可行约束]; G -- 否 --> I[更新最优解]; H --> J{是否需要回溯}; J -- 是 --> D; J -- 否 --> K[选择自由变量]; K --> L[更新变量和约束]; L --> D; E --> M[输出结果]; M --> N[结束]; I --> D; ``` #### 2. 全整数规划 全整数规划问题要求所有变量的取值都为整数。问题的一般形式为： - **目标函数**：最小化 $\sum_{j=1}^{n} a_{0j} x_j$ - **约束条件**：$\sum_{j=1}^{n} a_{ij} x_j \leq b_i$，$i = 1, 2, \cdots, m$；$x_j \geq 0$ 且为整数，$j = 1, 2, \cdots, n$ Gomory 割平面技术可以用来解决这个问题，具体步骤如下： 1. 选择一个割生成行 $d_{k0} < 0$，$k \neq 0$。如果不存在这样的行，则当前解是最优解。 2. 在 $d_{kj} < 0$ 中，选择字典序最大的主元列。如果没有找到这样的列，则不存在整数可行解。 3. 从行 $k$ 导出一个在当前原问题解下不满足的割不等式。将这个新行添加到表格的底部，并在当前解中用作主元。 4. 执行对偶单纯形旋转操作。 5. 移除添加的行并返回步骤 1。 以下是 Java 实现的代码： ```java public static void integerProgramming(int n, int m, int a[][]) { int i,j,k,l,np,num,r,r1,s,t,count,c,denom,temp,p; boolean b,iter,nofeas=false; for (j=1; j<=n; j++) a[m+j][j] = -1; m += n; count = 0; np = n+1; do { count++; r = 0; do { r++; iter = a[r][np] < 0; } while (!iter && (r != m)); if (iter) { k = 0; do { k++; iter = a[r][k] < 0; } while (!iter && (k != n)); nofeas = !iter; if (iter) { l = k; for (j=k+1; j<=n; j++) if (a[r][j] < 0) { i = -1; do { i++; s = a[i][j] - a[i][l]; } while (s == 0); if (s < 0) l = j; } s = 0; while (a[s][l] == 0) s++; num = -a[r][l]; denom = 1; for (j=1; j<=n; j++) if ((a[r][j] < 0) && (j != l)) { i = s - 1; b = true; while (b && (i >= 0)) { b = (a[i][j] == 0); i--; } if (b) { i = a[s][j]; r1 = a[s][l]; temp = i / r1; if (temp*r1 > i) temp--; if ((temp+1)*r1 <= i) temp++; t = temp; if ((t*r1 == i) && (t > 1)) { i = s; do { i++; r1 = t*a[i][l] - a[i][j]; } while (r1 == 0); if (r1 > 0) t--; } c = -a[r][j]; if (c*denom > t*num) { num = c; denom = t; } } } for (j=1; j<=np; j++) if (j != l) { p = a[r][j] * denom; temp = p / num; if (temp*num > p) temp--; if ((temp+1)*num <= p) temp++; c = temp; if (c != 0) for (i=0; i<=m; i++) a[i][j] += c * a[i][l]; } } } } while (iter && !nofeas); a[0][0] = -a[0][n+1]; a[0][n+1] = (nofeas ? 1 : 0); for (j=1; j<=n; j++) a[m-n+j][0] = a[m-n+j][n+1]; } ``` 以下是一个具体的例子，求解一个具有 3 个变量和 2 个约束的全整数规划问题： ```java package Optimization; public class Test_integerProgram extends Object { public static void main(String args[]) { int n = 3; int m = 2; int a[][] = {{0, 3, 3, 4, 0}, {0, -2, -2, -3, -12}, {0, -4, -1, -1, -10}, {0, 0, 0, 0, 0}, {0, 0, 0, 0, 0}, {0, 0, 0, 0, 0}}; Optimize.integerProgramming(n, m, a); if (a[0][n+1] > 0) System.out.println("No feasible solution."); else { System.out.print("Optimal solution found.\n Solution: "); for (int i=1; i<=n; i++) System.out.print(" " + a[m+i][0]); System.out.println("\n Optimal value of the objective function = " + a[0][0]); } } } ``` 输出结果为： ```plaintext Optimal solution found. Solution: 3 0 2 Optimal value of the objective function = 17 ``` 该算法的求解步骤可以总结如下表： | 步骤 | 操作 | | ---- | ---- | | 1 | 选择割生成行 | | 2 | 选择主元列 | | 3 | 导出割不等式 | | 4 | 执行对偶单纯形旋转 | | 5 | 移除添加的行 | 其流程图如下： ```mermaid graph TD; A[开始] --> B[初始化表格]; B --> C{是否有割生成行}; C -- 是 --> D[选择割生成行]; C -- 否 --> E[输出最优解]; D --> F[选择主元列]; F --> G{是否找到主元列}; G -- 是 --> H[导出割不等式]; G -- 否 --> I[输出无可行解]; H --> J[添加新行到表格]; J --> K[执行对偶单纯形旋转]; K --> L[移除添加的行]; L --> C; E --> M[结束]; I --> M; ``` 通过以上内容，我们详细介绍了零一整数规划和全整数规划的问题描述、求解方法、代码实现以及实例分析。在下半部分，我们将继续探讨混合整数规划的相关内容。 #### 3. 混合整数规划 混合整数规划问题中，部分变量被限