BZOJ 3112 ZJOI 2013 防守戰線：單純形法解線性規劃

問題背景

給定 m 條約束、n 個變量的線性規劃問題，求最大值。數據規模要求用單純形法（單純形算法）求解。

單純形法核心思想

將不等式約束轉化為標準形：
max c^Tx s.t. A x ≤ b, x ≥ 0。
引入鬆弛變量轉為等式，構建單純形表。通過基變換（樞軸操作），沿著可行域頂點移動，每步增加目標函數值，直到無法改善（最優）。

關鍵步驟

1. 初始化：構建增廣矩陣，包含目標函數行、約束行、鬆弛變量單位矩陣。
2. 選入基變量：目標行中係數 > 0 的列（非基變量）。
3. 選出基變量：最小比率測試（b_i / a_ij），防止不可行。
4. 樞軸變換：高斯消元使樞軸列變為單位向量，更新表。
5. 重複直到目標行無正係數（最優）或無出基變量（無界）。

數值穩定性與 EPS

浮點運算需設 EPS = 1e-9 判斷零。避免除以極小數。對於整數輸入輸出，最終結果四捨五入到整數。

代碼框架（精簡版）

const double EPS = 1e-9, INF = 1e100;
double A[MAXM][MAXN], b[MAXM], c[MAXN], v;
int N, M; // N variables, M constraints

void pivot(int l, int e) { // l: leaving row, e: entering col
    b[l] /= A[l][e];
    for (int j=1;j<=N;++j) if (j!=e) A[l][j] /= A[l][e];
    A[l][e] = 1/A[l][e];
    for (int i=1;i<=M;++i) if (i!=l && fabs(A[i][e])>EPS) {
        b[i] -= A[i][e]*b[l];
        for (int j=1;j<=N;++j) if (j!=e) A[i][j] -= A[i][e]*A[l][j];
        A[i][e] = -A[i][e]*A[l][e];
    }
    v += c[e]*b[l];
    for (int j=1;j<=N;++j) if (j!=e) c[j] -= c[e]*A[l][j];
    c[e] = -c[e]*A[l][e];
}

double simplex() {
    while (true) {
        int e = 0;
        for (int j=1;j<=N;++j) if (c[j] > EPS) { e=j; break; }
        if (!e) return v; // optimal
        int l = 0; double minRatio = INF;
        for (int i=1;i<=M;++i)
            if (A[i][e] > EPS && b[i]/A[i][e] < minRatio) {
                minRatio = b[i]/A[i][e]; l = i;
            }
        if (!l) return INF; // unbounded
        pivot(l, e);
    }
}

總結

單純形法是線性規劃的標準算法，雖然最壞情況指數級，但實際極快。BZOJ 3112 要求精確實現樞軸操作與數值穩定性處理。掌握單純形表結構與基變換邏輯，是解決優化問題的核心技能。