### Python 实现单纯形法解决线性规划问题 #### 方法概述 单纯形法是一种用于求解线性规划问题的经典算法。它通过迭代的方式，在可行域的顶点之间移动，逐步逼近最优解。Python 中可以通过 `scipy.optimize` 库或者手动编写代码来实现这一过程。 --- #### 使用 SciPy 的 Optimize 包 SciPy 提供了一个内置函数 `linprog()` 来快速求解线性规划问题。以下是基于此库的一个简单示例： ```python from scipy.optimize import linprog # 定义目标函数系数 (最小化 c^T * x) c = [-3, -2] # 定义不等式约束矩阵 A_ub 和右侧向量 b_ub (A_ub @ x <= b_ub) A_ub = [[2, 1], [1, 2]] b_ub = [10, 8] # 定义变量范围 (x >= 0 默认设置) x_bounds = [(0, None), (0, None)] # 调用 linprog 函数求解 result = linprog(c, A_ub=A_ub, b_ub=b_ub, bounds=x_bounds) print(result) ``` 上述代码实现了最大化 \( z = 3x_1 + 2x_2 \)，并受制于以下条件： \[ 2x_1 + x_2 \leq 10,\quad x_1 + 2x_2 \leq 8,\quad x_1, x_2 \geq 0. \] 注意：由于 `linprog()` 只支持最小化问题，因此需将原目标函数乘以 -1 后再调用[^1]。 --- #### 手动实现单纯形法 对于更深入的学习需求，可以尝试手写单纯形法的核心逻辑。下面展示了一种简化版本的手动实现方式： ```python import numpy as np def simplex_method(tableau): while True: # 寻找进入基的列索引（最负的目标行元素） entering_col = np.argmin(tableau[-1, :-1]) if tableau[-1, entering_col] >= 0: # 如果无负数，则已达到最优解 break # 计算离开基的行索引（最小比率测试） ratios = [] for i in range(len(tableau[:-1])): if tableau[i, entering_col] > 0: ratio = tableau[i, -1] / tableau[i, entering_col] ratios.append(ratio) else: ratios.append(np.inf) leaving_row = np.argmin(ratios) if any(r < np.inf for r in ratios) else -1 if leaving_row == -1: # 若无法找到有效离基变量，则无界 raise ValueError("Problem is unbounded.") # 更新表格（枢轴操作） pivot_element = tableau[leaving_row, entering_col] tableau[leaving_row, :] /= pivot_element for i in range(len(tableau)): if i != leaving_row: multiplier = tableau[i, entering_col] tableau[i, :] -= multiplier * tableau[leaving_row, :] return tableau # 初始化单纯形表 tableau = np.array([ [2, 1, 1, 0, 0, 10], [1, 2, 0, 1, 0, 8], [-3, -2, 0, 0, 1, 0] ]) final_tableau = simplex_method(tableau.copy()) optimal_solution = final_tableau[:, -1][:-1].tolist()[:len(final_tableau)-1] objective_value = -final_tableau[-1][-1] print(f"Optimal Solution: {optimal_solution}") print(f"Objective Value: {objective_value}") ``` 这段代码模拟了单纯形法的过程，其中初始单纯形表包含了所有约束和目标函数的信息。程序会自动寻找最优解，并返回对应的结果[^2]。 --- #### 关键概念解析 - **单纯形表** 是一种结构化的数据存储形式，用来记录当前状态下的决策变量、松弛变量以及目标值。 - **进基与离基选择** 遵循特定规则：通常选取目标函数中最负的系数作为进基候选；而对于离基，则采用最小比例法则决定。 - 当前方法假设问题是标准化后的形式，即所有的约束均为小于等于关系且右端项非负[^3]。 ---