Linear Programming最大化问题精确求解：优化C#代码求助

问题背景 #

需要求解以下线性规划最大化问题的精确解：

max 𝑧 = 141𝑥₁ + 393𝑥₂ + 273𝑥₃ + 804𝑥₄ + 175𝑥₅
约束条件：

1. 3𝑥₁ + 5𝑥₂ + 2𝑥₃ + 5𝑥₄ + 4𝑥₅ ≤ 36
2. 7𝑥₁ + 12𝑥₂ + 11𝑥₃ + 10𝑥₄ ≤ 21
3. −3𝑥₂ + 12𝑥₃ + 7𝑥₄ + 2𝑥₅ ≤ 17
4. 0 ≤ 𝑥₁, 𝑥₂, 𝑥₃, 𝑥₄, 𝑥₅ ≤ 20

原代码使用Google OR-Tools的GLOP浮点求解器，因浮点数近似误差，转换为分数后结果偏离精确值：例如x₂的计算结果为8635342404774617/9007199254740992，而正确精确解应为209/218。

解决方案 #

GLOP基于浮点数运算，本身会引入精度损失。以下是两种可靠的精确解实现方案：

方案1：变量缩放转换为整数规划求解 #

由于原问题所有系数均为整数，最优解的分数分母必然是约束矩阵基行列式的因数。通过将变量缩放为整数，将连续线性规划转换为整数规划，求解后还原为分数即可得到精确解。

转换逻辑

设缩放因子为218（已知x₂的分母为218，且218是所有可能分母的公倍数），定义整数变量yᵢ = 218 * xᵢ，转换后的问题如下：

• 目标函数：max z' = 141y₁ + 393y₂ + 273y₃ + 804y₄ + 175y₅
• 约束条件：
  1. 3y₁ +5y₂ +2y₃ +5y₄ +4y₅ ≤ 36×218=7848
  2. 7y₁ +12y₂ +11y₃ +10y₄ ≤21×218=4578
  3. -3y₂ +12y₃ +7y₄ +2y₅ ≤17×218=3706
  4. 0 ≤ y₁,y₂,y₃,y₄,y₅ ≤20×218=4360

完整C#代码

using System;
using Google.OrTools.LinearSolver;
using Fractions;

public class ExactLinearSolver
{
    static void Main()
    {
        // 初始化CBC整数规划求解器
        Solver solver = Solver.CreateSolver("CBC");
        if (solver == null)
        {
            Console.WriteLine("无法创建CBC求解器，请确认OR-Tools已正确安装并支持CBC组件");
            return;
        }

        const long ScaleFactor = 218;
        // 定义整数变量y_i = ScaleFactor * x_i
        Variable y1 = solver.MakeIntVar(0, 20 * ScaleFactor, "y1");
        Variable y2 = solver.MakeIntVar(0, 20 * ScaleFactor, "y2");
        Variable y3 = solver.MakeIntVar(0, 20 * ScaleFactor, "y3");
        Variable y4 = solver.MakeIntVar(0, 20 * ScaleFactor, "y4");
        Variable y5 = solver.MakeIntVar(0, 20 * ScaleFactor, "y5");

        // 添加转换后的约束
        solver.Add(3 * y1 + 5 * y2 + 2 * y3 + 5 * y4 + 4 * y5 <= 36 * ScaleFactor);
        solver.Add(7 * y1 + 12 * y2 + 11 * y3 + 10 * y4 <= 21 * ScaleFactor);
        solver.Add(-3 * y2 + 12 * y3 + 7 * y4 + 2 * y5 <= 17 * ScaleFactor);

        // 设置最大化目标函数
        solver.Maximize(141 * y1 + 393 * y2 + 273 * y3 + 804 * y4 + 175 * y5);

        // 执行求解
        Solver.ResultStatus resultStatus = solver.Solve();

        if (resultStatus != Solver.ResultStatus.OPTIMAL)
        {
            Console.WriteLine("未找到最优解");
            return;
        }

        // 将整数解转换为精确分数
        Fraction x1 = new Fraction(y1.SolutionValue(), ScaleFactor).Reduce();
        Fraction x2 = new Fraction(y2.SolutionValue(), ScaleFactor).Reduce();
        Fraction x3 = new Fraction(y3.SolutionValue(), ScaleFactor).Reduce();
        Fraction x4 = new Fraction(y4.SolutionValue(), ScaleFactor).Reduce();
        Fraction x5 = new Fraction(y5.SolutionValue(), ScaleFactor).Reduce();
        Fraction z = new Fraction(solver.Objective().Value(), ScaleFactor).Reduce();

        // 输出结果
        Console.WriteLine("========================================================================");
        Console.WriteLine();
        Console.WriteLine("   精确最优解: z = " + z);
        Console.WriteLine("   x1 = " + x1);
        Console.WriteLine("   x2 = " + x2);
        Console.WriteLine("   x3 = " + x3);
        Console.WriteLine("   x4 = " + x4);
        Console.WriteLine("   x5 = " + x5);
        Console.WriteLine();
        Console.WriteLine("========================================================================");
    }
}

方案2：实现基于分数运算的单纯形法 #

如果无法确定缩放因子，可手动实现基于Fraction类的单纯形法，所有运算均使用精确有理数，彻底避免浮点数误差。这种方法适合通用场景，但代码量较大，需要自行实现单纯形法的核心逻辑。

注意事项 #

• 使用CBC求解器前，需确保OR-Tools安装包包含CBC组件（默认安装通常已包含）。
• 若不知道缩放因子，可计算所有约束系数和右侧常数的最小公倍数，确保转换后的约束均为整数。

内容的提问来源于stack exchange，提问作者Gqrsw