讲一下 两阶段单纯形算法 的实现思路。

接口

定义类 SimplexTwoPhase，它的输入是 A, b, c。跟单纯形算法相比，它不再需要指定起点。方法 solve 用来求解线性规划问题，结果和状态保存在成员变量中。

  import numpy as np


class SimplexTwoPhase:

    def __init__(self, A, b, c):
        """
        A: matrix of coefficients of the constraints
        b: vector of right-hand side values
        c: vector of coefficients of the objective function
        """
        self.A = np.array(A)
        self.b = np.array(b)
        self.c = np.array(c)
        self.objective = None
        self.solution = None
        self.status = None

    def solve(self):
        """
        Solve the linear program.
        """
        pass

实现

回顾两阶段法，我们把它拆成三个步骤：

  1. 求解一阶段问题；
  2. 得到基本可行解；
  3. 求解二阶段问题。

可以定义三个函数：

  • _solve_phase_one：返回一阶段问题的解。如果最优目标函数值不等于 0，意味着原问题没有可行解，则返回空。
  • _get_basic_feasible_solution：输入一阶段问题的解，返回基本可行解对应的基矩阵的列，以及冗余的行。
  • _solve_phase_two：已知基本可行解以及冗余的行，求解二阶段问题。
  class SimplexTwoPhase:
    
    # ...
    
    def _solve_phase_one(self):
        """
        Solve phase one instance. 
        If OPT != 0, then the original problem is infeasible and return None.
        """
        # Format A, b, c, s of phase one instance
        # simplex = SimplexDegen(A, b, c, s)
        # simplex.solve()
        return simplex
        
    def _get_basic_feasible_solution(self, simplex):
        """
        Given phase one solution, get the basic feasible solution of phase two instance.
        Args:
            simplex: SimplexDegen instance of phase one solution
        Returns:
            basic_vars: list of basic variables w.r.t. phase two instance
            redundant_rows: list of redundant rows of the original instance
        """
        
    def _solve_phase_two(self, basic_vars, redundant_rows):
        """
        Solve phase two instance.
        Args:
            basic_vars: list of basic variables w.r.t. phase two instance
            redundant_rows: list of redundant rows of the original instance
        """
        pass

利用这三个函数，我们可以实现 solve。

  class SimplexTwoPhase:

    # ...
    
    def solve(self):
        """
        Solve the linear program.
        """
        # 1. Solve phase one instance
        simplex = self._solve_phase_one()
        
        # In case of infeasible
        if simplex is None:
            self.status = Status.INFEASIBLE
            return
        
        # 2. Get basic feasible solution of phase two instance
        basic_vars, redundant_rows = self._get_basic_feasible_solution(simplex)
        
        # 3. Solve phase two instance
        simplex = self._solve_phase_two(basic_vars, redundant_rows)
        
        # Set the solution
        self.status = simplex.status
        self.objective = simplex.objective
        self.solution = simplex.solution

接下来就是上面三个函数的实现。其中 _solve_phase_one 和 _solve_phase_two 就是调用单纯形算法，实现相对简单。前面我们已经实现了单纯形算法，且能够 处理退化 的例子，因此算法能在有限步内收敛。

函数 _get_basic_feasible_solution 的实现参照 两阶段法 和 两阶段法示例。

代码

相关代码在 codes/simplex-algorithms 文件夹。

Edit this page

Last updated 12 Apr 2025, 17:15 +0800 . history