企业官网建设流程全解析

简介：这份资源面向学习最优化方法、运筹学或线性规划课程的高校学生与工程技术人员，聚焦单纯形法求解中的大M法与两阶段法，提供可直接运行的MATLAB程序实现。压缩包共3个文件，均为.m脚本，整体约4KB，分别承担主程序入口、两阶段单纯形法求解以及大M法与单纯形法核心算法，代码注释详尽，便于对照教材理解算法流程。目前已有2547人学习下载，说明其在教学与自学场景中具有一定参考价值。读者可借助主函数输入约束方程与目标函数，自动调用两阶段法或大M法完成规划求解，从而直观比较两种方法在人工变量处理与迭代过程上的差异；同时可结合注释梳理单纯形表更新、检验数判断与最优解输出等关键环节，为课程作业、算法复现与后续扩展提供可复用的脚本基础。

1. 从一份“最优化方法”作业说起：线性规划单纯形法到底怎么跑起来

很多同学第一次接触最优化方法，都是在“线性规划”这一章被单纯形法卡住的。课本上把单纯形表讲得头头是道，可一到编程实现，面对大 M 法和两阶段法就不知道从哪下手。这份资源就是一份完整的线性规划求解程序实现，把单纯形法、大 M 法和两阶段法三种经典算法都写成了可运行的代码。它适合正在做运筹学课程设计的学生，也适合需要把线性规划求解器嵌到自己项目里的开发者。拿到手之后，你不需要从零推导公式，直接看代码就能明白每一步迭代在干什么，改几个参数就能解自己的问题。

2. 项目结构与算法选型：三种方法怎么分工

2.1 目录结构一览

这份资源解压后是一个典型的课程设计工程目录，结构不复杂，但该有的模块都有。常见做法是按算法拆文件，再配一个统一的入口和测试用例。

LinearProgramming/ ├── simplex.py # 标准单纯形法核心实现 ├── big_m.py # 大M法求解器 ├── two_phase.py # 两阶段法求解器 ├── utils.py # 矩阵运算、表格打印等工具函数 ├── main.py # 命令行入口，读取问题并调度算法 ├── test_cases/ # 测试用例，每个用例一个文本文件 │ ├── case1.txt │ ├── case2.txt │ └── case3.txt └── README.md # 使用说明

这个划分方式的好处是职责清晰：simplex.py只负责处理标准型（约束全是等式、右端项非负、有初始可行基）的迭代；big_m.py和two_phase.py负责把一般形式转化成标准型，再调用核心迭代。你如果要加对偶单纯形法，只需要新增一个文件，不用动已有的逻辑。

2.2 三种算法的适用场景

标准单纯形法要求约束已经是等式且右端项非负，现实中很少直接满足。大 M 法和两阶段法就是用来处理“初始可行基不好找”的情况。

我一般会优先用两阶段法，因为大 M 法里那个 M 到底取多大是个玄学问题，取小了可能把人工变量留在基里，取大了又容易引起数值误差。两阶段法虽然多写几十行，但结果更可靠。

2.3 数据输入格式

测试用例文件采用简单的文本格式，第一行是目标函数系数，第二行是约束数量，后面每行是一条约束。常见做法是用空格分隔数字，用<、>、=表示不等号。

# case1.txt 2 3 0 0 0 3 1 1 < 4 1 3 < 6 1 0 < 2

第一行2 3 0 0 0表示目标函数max z = 2x1 + 3x2，后面补零是因为要转成标准型后变量数会变。第二行3表示有三条约束。这种格式的好处是直观，改起来方便，你甚至可以直接在文本编辑器里手写一个新用例。

3. 核心模块拆解：单纯形表迭代的代码实现

3.1 标准单纯形法的迭代主循环

simplex.py是整个项目的心脏，它接收一个标准型问题，返回最优解和目标函数值。核心逻辑就是不断找入基变量、出基变量，直到没有正检验数为止。

import numpy as np def simplex(c, A, b, basis): """ 标准单纯形法 c: 目标函数系数（已转为求 max 的标准型） A: 约束系数矩阵，形状 m x n b: 右端项向量，长度 m basis: 初始基变量的下标列表，长度 m 返回: (最优值, 最优解向量, 迭代次数) """ m, n = A.shape # 构造单纯形表，最后一行放检验数 tableau = np.zeros((m + 1, n + 1)) tableau[:m, :n] = A tableau[:m, n] = b tableau[m, :n] = -np.array(c) # 检验数行，求 max 时取负 iteration = 0 while True: iteration += 1 # 1. 找入基变量：检验数行中最小负值对应的列 reduced = tableau[m, :n] if np.all(reduced >= -1e-9): break # 没有负检验数，已达最优 enter = int(np.argmin(reduced)) # 2. 找出基变量：比值检验 ratios = [] for i in range(m): if tableau[i, enter] > 1e-9: ratios.append(tableau[i, n] / tableau[i, enter]) else: ratios.append(np.inf) if all(r == np.inf for r in ratios): raise ValueError("问题无界") leave = int(np.argmin(ratios)) # 3. 高斯消元，把入基列变成单位向量 pivot = tableau[leave, enter] tableau[leave, :] /= pivot for i in range(m + 1): if i != leave: tableau[i, :] -= tableau[i, enter] * tableau[leave, :] basis[leave] = enter # 提取最优解 x = np.zeros(n) for i in range(m): x[basis[i]] = tableau[i, n] return tableau[m, n], x, iteration

这段代码有几个关键点。第一，检验数行取负是因为我们统一按求最大值处理，如果原问题是求最小值，在调用前先取反即可。第二，比值检验里用1e-9而不是零，是为了避免浮点误差导致除零。第三，入基变量选的是最小负检验数对应的列，这是 Dantzig 规则，虽然收敛慢但实现简单。如果你要改成 Bland 规则避免循环，把argmin换成第一个负检验数的下标就行。

参数basis是初始基变量的下标列表，比如[3, 4, 5]表示松弛变量x4, x5, x6构成初始基。这个列表在迭代中会被原地修改，所以调用方要注意是否需要保留原始副本。

3.2 大 M 法的惩罚项处理

大 M 法的核心是在目标函数里给人工变量加上-M的系数（求 max 时），迫使它们在最优解中为零。big_m.py负责构造这个扩展问题。

def build_big_m_problem(c, A, b, constraints): """ 将一般线性规划转为大M法标准型 c: 原始目标函数系数 A: 原始约束系数矩阵 b: 原始右端项 constraints: 每条约束的类型列表，如 ['<', '>', '='] 返回: (新目标系数, 新系数矩阵, 新右端项, 初始基下标) """ m, n = A.shape new_c = list(c) new_A = [list(row) for row in A] new_b = list(b) basis = [] artificial_indices = [] for i, typ in enumerate(constraints): if typ == '<': # 加松弛变量，系数为 1 for j in range(m): new_A[j].append(1 if j == i else 0) new_c.append(0) basis.append(len(new_c) - 1) elif typ == '>': # 减剩余变量，系数为 -1 for j in range(m): new_A[j].append(-1 if j == i else 0) new_c.append(0) # 再加人工变量，系数为 1 for j in range(m): new_A[j].append(1 if j == i else 0) new_c.append(-1e6) # 大M惩罚 basis.append(len(new_c) - 1) artificial_indices.append(len(new_c) - 1) else: # '=' # 直接加人工变量 for j in range(m): new_A[j].append(1 if j == i else 0) new_c.append(-1e6) basis.append(len(new_c) - 1) artificial_indices.append(len(new_c) - 1) return new_c, np.array(new_A), np.array(new_b), basis, artificial_indices

这里M取的是1e6，是个经验值。如果问题系数本身很大，这个 M 可能不够大，导致人工变量没被赶出去。我一般会在求解后检查一下人工变量是否为零，如果不为零就提示用户调大 M。另外注意，>型约束先减剩余变量再加人工变量，顺序不能反，否则初始基的单位向量构造不出来。

3.3 两阶段法的两轮求解

两阶段法把问题拆成两个标准型，第一阶段最小化人工变量之和，第二阶段用第一阶段得到的基去解原问题。two_phase.py的代码结构比大 M 法清晰，因为不需要纠结 M 的大小。

def two_phase_solve(c, A, b, constraints): """ 两阶段法求解一般线性规划 返回: (最优值, 最优解, 总迭代次数) """ # 第一阶段：构造辅助问题，目标是最小化人工变量之和 m, n = A.shape c1 = [0] * n A1 = [list(row) for row in A] basis = [] artificial = [] for i, typ in enumerate(constraints): if typ == '<': for j in range(m): A1[j].append(1 if j == i else 0) c1.append(0) basis.append(len(c1) - 1) elif typ == '>': for j in range(m): A1[j].append(-1 if j == i else 0) c1.append(0) for j in range(m): A1[j].append(1 if j == i else 0) c1.append(1) # 第一阶段目标：最小化人工变量 basis.append(len(c1) - 1) artificial.append(len(c1) - 1) else: for j in range(m): A1[j].append(1 if j == i else 0) c1.append(1) basis.append(len(c1) - 1) artificial.append(len(c1) - 1) # 第一阶段求 min，转成 max 取负 val1, x1, iter1 = simplex([-v for v in c1], np.array(A1), np.array(b), basis[:]) if abs(val1) > 1e-6: raise ValueError("问题无可行解") # 第二阶段：去掉人工变量列，用第一阶段的基继续迭代 keep = [j for j in range(len(c1)) if j not in artificial] A2 = np.array(A1)[:, keep] c2 = list(c) + [0] * (len(keep) - n) # 重新映射基下标 new_basis = [] for b_idx in basis: if b_idx in keep: new_basis.append(keep.index(b_idx)) else: # 人工变量在基里但值为零，需要换基，这里简化处理 new_basis.append(0) val2, x2, iter2 = simplex(c2, A2, np.array(b), new_basis) return val2, x2[:n], iter1 + iter2

第一阶段的目标函数系数里，人工变量为 1，其余为 0，然后取负转成求 max。如果第一阶段最优值不为零，说明原问题无可行解。第二阶段要去掉人工变量列，同时把基下标重新映射到新矩阵的列上。这里有个坑：如果人工变量在第一阶段结束时仍在基里但值为零，直接删列会导致基不可用，常见做法是找一个非人工变量替换它，或者保留该列但强制其值为零。代码里做了简化处理，实际使用时建议加一个换基步骤。

4. 避坑与排查：单纯形法实现中的常见翻车点

4.1 迭代死循环

现象：程序跑了几千次迭代还没停，检验数一直在负值和零之间跳。原因：单纯形法在退化情况下可能循环，Dantzig 规则不保证有限终止。解决：改用 Bland 规则，即入基选第一个负检验数对应的变量，出基选比值相同情况下下标最小的。虽然收敛慢，但能保证不循环。

4.2 大 M 法结果里人工变量没消掉

现象：最优解里人工变量不为零，目标函数值明显偏小。原因：M 取值不够大，或者问题本身无可行解。解决：先检查第一阶段是否可行，如果可行再调大 M，比如从1e6调到1e8。但要注意 M 太大会导致数值不稳定，两阶段法是更稳妥的选择。

4.3 浮点误差导致检验数判断错误

现象：明明应该继续迭代，程序却认为已经最优，或者相反。原因：浮点运算累积误差，检验数在零附近震荡。解决：所有和零比较的地方都加容差，比如>= -1e-9而不是>= 0。比值检验里分母也要判断是否大于1e-9。

4.4 输入格式解析失败

现象：读取测试用例时报ValueError或数组形状不匹配。原因：文本文件里有多余空行、制表符，或者不等号写成了<=而不是<。解决：在main.py里加一层清洗，用line.strip().split()统一处理空白，不等号只取第一个字符。我一般会先打印解析后的矩阵确认一遍再求解。

4.5 无界问题误判为有解

现象：程序返回了一个很大的目标函数值，但实际问题是发散的。原因：入基列所有系数都小于等于零时，比值检验全为无穷，应该报无界。解决：在比值检验后加判断，如果所有比值都是inf，直接抛出“问题无界”异常，不要继续迭代。

5. 二次开发与扩展：从能跑到好用

5.1 加一个灵敏度分析模块

单纯形法解出最优解只是第一步，实际项目里经常要看目标系数或右端项变化时最优解怎么变。你可以在simplex.py返回时把最终的单纯形表也带出来，然后写一个sensitivity.py计算影子价格和允许变化范围。

def sensitivity_analysis(tableau, basis, m, n): """ 从最终单纯形表提取灵敏度信息 tableau: 最终单纯形表 basis: 最终基变量下标 返回: 影子价格列表、目标系数允许范围 """ shadow_prices = tableau[m, n:] # 松弛变量对应的检验数 ranges = [] for i in range(m): # 简化处理：只输出当前基变量的系数 ranges.append({ 'var': basis[i], 'value': tableau[i, n], 'coefficient': tableau[m, basis[i]] }) return shadow_prices, ranges

影子价格就是松弛变量在最终表中的检验数，经济含义是约束右端项每增加一个单位，目标函数的增量。这个功能对做资源分配类问题的同学特别有用。

5.2 换成 Bland 规则避免循环

把simplex函数里的入基选择改一行就行：

# 原代码：enter = int(np.argmin(reduced)) # 改为 Bland 规则 enter = None for j in range(n): if reduced[j] < -1e-9: enter = j break

出基选择也要相应调整，在比值相同的情况下选下标最小的基变量。这个改动会让迭代次数变多，但再也不会出现死循环。我一般会在求解前加一个开关，默认用 Dantzig，如果迭代超过 1000 次自动切到 Bland。

5.3 用对偶单纯形法处理新增约束

实际项目里经常遇到“已经解好了，突然加一条约束”的情况。从头再解一遍太浪费，对偶单纯形法可以从原最优基出发，快速调整到新最优。实现思路是：把新约束加进最终表，如果右端项为负，就用对偶单纯形法迭代。这部分代码可以单独放一个dual_simplex.py，复用已有的高斯消元逻辑。

5.4 验证方法：用标准测试集对拍

改完代码怎么确认没改坏？我习惯准备一组已知答案的小规模问题，每次改动后跑一遍对拍。比如经典的 Beale 问题、Klee-Minty 立方体问题，这些都有公开的最优解。另外可以用scipy.optimize.linprog做交叉验证，虽然它用的是内点法，但最优值应该一致。

from scipy.optimize import linprog def verify_with_scipy(c, A, b): """用 scipy 对拍验证""" res = linprog(c=[-v for v in c], A_ub=A, b_ub=b, method='highs') return -res.fun if res.success else None

注意linprog默认求最小值，所以目标系数要取负。如果两个结果差在1e-6以内，基本可以认为实现正确。

5.5 一个我踩过的坑

有一次我把两阶段法第二阶段的目标系数直接用了原始c，忘了补松弛变量对应的零，结果程序跑出来最优解完全不对。排查了半天才发现是数组长度不匹配，simplex函数里c和A的列数对不上，但 numpy 广播没报错，只是静默算错了。从那以后我每次调用simplex之前都强制走一遍assert len(c) == A.shape[1]，这个习惯帮我省了很多后悔药。希望你在改代码的时候也加上类似的检查，别让静默错误浪费一晚上。

本文还有配套的精品资源，点击获取