☰
运筹学单纯形法对偶理论详解:从手算到Python代码验证
2026/10/21 15:09:11 网站建设 项目流程

简介:这份《单纯形及其对偶》课件面向学习线性规划、最优化理论与运筹学课程的高校学生及备考人员,系统讲解单纯形法这一求解线性规划问题的核心工具。内容围绕线性规划标准型的定义与转化展开,涵盖目标函数最大化转最小化、不等式约束引入松弛变量与剩余变量、无约束变量拆分等关键步骤,并配有完整例题演示;同时梳理可行解、最优解、基、基本解、基本可行解与可行基等解的概念,延伸至凸集、顶点与基本定理的几何意义。资源包内含1个PDF文件,约1.23MB,页面结构清晰,公式推导与图示结合,便于打印或电子阅读。目前已有173人学习,适合作为课堂笔记补充或期末复习提纲,帮助读者理清标准型转化流程与单纯形法的迭代思路。

1. 从一份课件说起:单纯形法和对偶理论到底该怎么学

很多人第一次接触线性规划,都是在运筹学课上被单纯形表支配的恐惧。老师讲完基变量、检验数、出基入基,你好像听懂了,但真给你一道题,手算三遍三遍答案不一样。这份《单纯形及其对偶》课件,本质上就是帮你把“会算”和“算对”之间的鸿沟填上。它适合两类人:一类是正在学运筹学、被单纯形表折磨的学生;另一类是做优化相关工程、需要快速判断线性规划模型是否可行、对偶问题怎么构造的从业者。单纯形法解决的是“怎么在可行域顶点上迭代找到最优解”,对偶理论解决的是“原问题和对偶问题之间到底什么关系、怎么用对偶信息做灵敏度分析”。这两件事合在一起,才构成线性规划真正能落地的完整工具链。课件本身不是代码库,但它的价值在于把算法步骤、表格操作、对偶转换规则讲清楚,让你能自己写代码复现,或者至少能看懂求解器输出的对偶变量。

2. 单纯形法的表格操作:从标准型到第一次迭代

2.1 为什么一定要先转标准型

线性规划问题千变万化,但单纯形法只认一种格式:标准型。标准型要求目标函数求最大值、约束全是等式、右端项非负、所有变量非负。你拿到的原始问题大概率长这样:目标函数有min有max,约束有小于等于有大于等于,变量可能无约束。不转标准型直接上单纯形表,第一步就卡住。

转换规则其实就四条,但每条都有坑。目标函数min转max,直接把系数取反,最后最优值再取反回去。小于等于约束加松弛变量,大于等于约束减剩余变量再加人工变量,等式约束直接加人工变量。右端项为负的,两边同乘-1,注意不等号方向要翻转。变量无约束的,拆成两个非负变量相减。

我一般会让学生先做十道转换题,不要求解,只要求把标准型写对。因为后面单纯形表算错,八成是标准型就错了。课件里给了一个转换对照表,我把它整理成更直观的版本:

原形式转换动作新增变量目标函数系数
max z = cx不变无保持
min z = cx取反无全部变号
≤ 约束加松弛变量s0
≥ 约束减剩余变量,加人工变量e, a0, -M
= 约束加人工变量a-M
右端项 < 0两边乘-1无不等号翻转
变量 x 无约束x = x' - x''x', x''系数分别对应

大M法里M取多大?理论上取无穷大,实际手算取一个比所有系数绝对值大两个数量级的值就行。比如系数最大是10,M取1000足够。但要注意,M太大在计算机浮点运算里会引发数值不稳定,这也是为什么实际求解器用两阶段法而不是大M法。

2.2 单纯形表的迭代逻辑与停止条件

标准型写对之后,填初始单纯形表。初始基变量就是松弛变量和人工变量。检验数σ_j = c_j - z_j,其中z_j = Σ c_B * a_ij。如果所有σ_j ≤ 0,当前解就是最优解。如果有σ_j > 0,选最大的那个对应的变量入基。然后做最小比值检验:用右端项b_i除以入基列的正系数a_ik,选最小的那个对应的基变量出基。如果入基列所有系数都≤0,说明问题无界。

这个流程说起来简单,手算的时候最容易在三个地方翻车:一是检验数算错符号,二是最小比值检验忘了只考虑正系数,三是换基之后没有正确做行变换。行变换的目标是把入基列变成单位向量,也就是主元位置变成1,其他位置变成0。

下面这段Python代码用numpy实现了一个最简单纯形法,只处理标准型,不做自动转换。你可以拿它验证手算结果:

import numpy as np def simplex(c, A, b, basis): """ c: 目标函数系数向量 (max问题) A: 约束系数矩阵 b: 右端项向量 basis: 初始基变量索引列表 """ m, n = A.shape c = np.array(c, dtype=float) A = np.array(A, dtype=float) b = np.array(b, dtype=float) basis = list(basis) for iteration in range(100): # 防止死循环 # 构造基矩阵B和基变量系数c_B B = A[:, basis] c_B = c[basis] # 计算当前基可行解 x_B = np.linalg.solve(B, b) # 计算检验数 sigma_j = c_j - c_B^T * B^{-1} * A_j B_inv = np.linalg.inv(B) sigma = c - c_B @ B_inv @ A # 检查是否最优 if np.all(sigma <= 1e-9): print(f"第{iteration}次迭代达到最优") x = np.zeros(n) x[basis] = x_B return x, c @ x # 选入基变量:最大正检验数 enter = np.argmax(sigma) # 计算入基列的方向向量 d = B^{-1} * A_enter d = B_inv @ A[:, enter] # 最小比值检验 ratios = [] for i in range(m): if d[i] > 1e-9: ratios.append(x_B[i] / d[i]) else: ratios.append(np.inf) if all(r == np.inf for r in ratios): print("问题无界") return None, None leave_idx = np.argmin(ratios) leave = basis[leave_idx] # 换基 basis[leave_idx] = enter print(f"迭代{iteration}: 入基x{enter}, 出基x{leave}, 当前目标值{c_B @ x_B:.4f}") print("超过最大迭代次数") return None, None # 测试:max z = 3x1 + 2x2 # s.t. x1 + x2 <= 4 # 2x1 + x2 <= 5 # x1, x2 >= 0 # 标准型:加松弛变量x3, x4 c = [3, 2, 0, 0] A = [[1, 1, 1, 0], [2, 1, 0, 1]] b = [4, 5] basis = [2, 3] # x3, x4为初始基变量 x, z = simplex(c, A, b, basis) print(f"最优解: {x}") print(f"最优值: {z}")

这段代码的关键点在于:用矩阵求逆的方式计算检验数和方向向量,而不是手算行变换。这样做的好处是逻辑清晰,坏处是数值稳定性不如直接做行变换。实际工程中,求解器会用LU分解而不是显式求逆。参数方面,basis列表必须对应初始可行基,通常就是松弛变量和人工变量的索引。1e-9这个容差是为了处理浮点误差,太小会误判,太大会提前停止。迭代上限设100是防止退化问题导致循环,虽然Bland规则可以理论上避免循环,但工程上直接设上限更省事。

2.3 退化、循环与Bland规则

退化是指基可行解中出现了零分量,也就是某个基变量取值为0。退化本身不是问题,但它可能导致单纯形法在几个基之间循环,永远停不下来。我见过最极端的例子是一个6变量的问题,迭代了20多次目标值一直没变,最后发现是在两个退化基之间来回跳。

Bland规则是理论上能保证有限步终止的选元策略:入基选下标最小的正检验数变量,出基在最小比值相同的情况下选下标最小的基变量。这个规则在实际中很少用,因为收敛速度慢,但当你发现程序死循环时,加上Bland规则至少能保证跑出结果。

课件里通常会提一句“退化时可以用摄动法”,但摄动法在计算机实现里不实用。我的建议是:手算时遇到退化,检查一下是不是约束有冗余;写代码时,直接设迭代上限,超了就报错,别硬等。

3. 对偶理论:从原问题到对偶问题的机械转换

3.1 对偶问题的构造规则与记忆方法

对偶问题的构造有一套对称规则,但很多人记不住谁对谁。我教学生用一个口诀:“原问题约束个数等于对偶变量个数,原问题变量个数等于对偶约束个数。原问题max对应对偶min,原问题≤对应对偶≥,原问题变量≥0对应对偶约束≤。”

具体来说,如果原问题是标准型max z = cx, Ax ≤ b, x ≥ 0,那么对偶问题是min w = b^T y, A^T y ≥ c^T, y ≥ 0。注意这里A^T y ≥ c^T,不是≤。很多人在这里翻车,因为直觉上觉得max对应≤,min对应≥,但转置之后方向会变。

更一般的情况,原问题有等式约束、有自由变量,对偶规则会复杂一些。我整理了一个完整的对照表:

原问题(max)对偶问题(min)
第i个约束是 ≤y_i ≥ 0
第i个约束是 ≥y_i ≤ 0
第i个约束是 =y_i 无约束
x_j ≥ 0第j个约束是 ≥
x_j ≤ 0第j个约束是 ≤
x_j 无约束第j个约束是 =

这个表的用法是:先确定原问题的类型(max还是min),然后逐条对照。如果原问题是min,把上表左右对调,max换成min,≤换成≥,以此类推。

3.2 对偶问题的经济解释与灵敏度分析

对偶变量y_i的 economic interpretation 是第i种资源的影子价格。影子价格表示资源增加一个单位时,目标函数最优值的改变量。这个解释在工程上非常有用:如果你知道某种资源的影子价格是5,而市场上这种资源的单价是3,那你就应该买进这种资源来扩大生产,因为每增加一个单位资源,利润增加5,成本只增加3,净赚2。

灵敏度分析就是基于影子价格做的。课件里通常会讲目标函数系数变化范围、右端项变化范围、增加新变量、增加新约束这四种情况。其中右端项变化范围最常用,因为它直接对应资源可获取量的波动。

我一般会让学生用Python的scipy.optimize.linprog来验证手算的影子价格:

from scipy.optimize import linprog import numpy as np # 原问题:max z = 3x1 + 2x2 # s.t. x1 + x2 <= 4 # 2x1 + x2 <= 5 # x1, x2 >= 0 # scipy的linprog默认求min,所以目标函数取反 c = [-3, -2] # 取反 A = [[1, 1], [2, 1]] b = [4, 5] bounds = [(0, None), (0, None)] res = linprog(c, A_ub=A, b_ub=b, bounds=bounds, method='highs') print(f"最优解: x1={res.x[0]:.4f}, x2={res.x[1]:.4f}") print(f"最优值: z={-res.fun:.4f}") # 对偶变量(影子价格)在res.ineqlin.marginals里 # 注意scipy的符号约定:对于A_ub x <= b_ub,marginals是负的 print(f"影子价格: y1={-res.ineqlin.marginals[0]:.4f}, y2={-res.ineqlin.marginals[1]:.4f}") # 验证:右端项b1增加1,最优值应该增加y1 b_new = [5, 5] res_new = linprog(c, A_ub=A, b_ub=b_new, bounds=bounds, method='highs') print(f"b1增加1后最优值: z={-res_new.fun:.4f}") print(f"实际增量: {-res_new.fun - (-res.fun):.4f}")

这段代码的关键在于理解scipy的符号约定。res.ineqlin.marginals返回的是对偶变量的值,但对于≤约束,scipy返回的是负值,所以取负号才是影子价格。另外,method='highs'是scipy目前推荐的求解器,比旧的'simplex'更稳定。如果你用'simplex',可能会遇到数值问题。

3.3 对偶单纯形法与原始-对偶关系

对偶单纯形法不是用来解对偶问题的,而是用来解原问题的一种变体。它的适用场景是:原问题的初始基不是可行基(检验数满足最优条件但右端项有负值),这时候用对偶单纯形法比重新构造初始可行基更高效。

对偶单纯形法的步骤和原始单纯形法对称:先检查右端项是否全非负,如果不是,选最小的负右端项对应的基变量出基;然后计算比值σ_j / a_rj(只考虑a_rj < 0的),选最小的对应的变量入基;做行变换,重复直到右端项全非负。

原始-对偶关系最核心的定理是弱对偶定理和强对偶定理。弱对偶定理说:原问题的任意可行解的目标值 ≤ 对偶问题的任意可行解的目标值。强对偶定理说:如果原问题有最优解,那么对偶问题也有最优解,且两者目标值相等。这两个定理是灵敏度分析和影子价格的理论基础。

课件里通常会给出互补松弛条件的证明,但工程上你只需要记住:如果原问题第i个约束是松的(也就是没有取等号),那么对偶变量y_i = 0;如果对偶问题第j个约束是松的,那么原变量x_j = 0。这个条件在验证解的时候非常有用。

4. 避坑与排查:单纯形和对偶计算中的五个血泪教训

4.1 检验数符号搞反导致迭代方向错误

现象:手算时目标值越迭代越小,或者程序跑出来的解明显不是最优。

原因:检验数公式是σ_j = c_j - z_j,其中z_j = Σ c_B * a_ij。很多人记成σ_j = z_j - c_j,这样符号全反,选入基变量时就会选错。

解决:记住一个简单判断——对于max问题,如果所有σ_j ≤ 0,当前解最优。如果你算出来所有σ_j ≥ 0,那大概率是符号反了。另外,初始单纯形表里松弛变量的检验数应该是0,因为c_j = 0且z_j = 0。如果松弛变量检验数不是0,说明基变量系数或者矩阵填错了。

4.2 最小比值检验忽略负系数导致无界误判

现象:程序报“问题无界”,但原问题明明有有限最优解。

原因:最小比值检验时,只应该考虑入基列中系数为正的行。如果某行系数为负,对应的比值是负数,不应该参与比较。如果所有系数都≤0,才是真正的无界。

解决:在代码里加一个判断,只对d[i] > 1e-9的行计算比值。手算时,在入基列旁边标注哪些是正系数,只对这些行做除法。我见过一个案例,入基列有一个-0.5的系数,学生没注意,算出来比值是-8,然后选了这一行出基,结果基变量变成负值,后面全乱套。

4.3 大M法里M取值不当引发数值问题

现象:程序跑出来的解有很小的负数,或者检验数在0附近震荡。

原因:M取太大,比如1e10,导致系数矩阵条件数爆炸,浮点运算误差被放大。M取太小,比如100,又可能无法正确惩罚人工变量,导致人工变量留在基里。

解决:手算时M取比系数绝对值大两个数量级即可。写代码时,建议用两阶段法代替大M法。两阶段法第一阶段只最小化人工变量之和,第二阶段再优化原目标。这样不需要选M,数值稳定性更好。scipy的linprog内部就是用两阶段法。

4.4 对偶变量符号与约束类型不匹配

现象:用scipy算出来的影子价格和手算对不上,或者符号相反。

原因:scipy的linprog对于≤约束返回的marginals是负值,对于≥约束返回的是正值。而手算时,我们通常定义影子价格为正值。另外,如果原问题是min,对偶问题是max,符号约定又不一样。

解决:统一符号约定。我一般建议:不管scipy返回什么,先取绝对值,然后根据经济含义判断正负。如果资源增加时目标值增加,影子价格为正;如果资源增加时目标值减少,影子价格为负。对于≤约束的max问题,影子价格通常为正。

4.5 退化问题导致死循环

现象:程序迭代次数超过上限,目标值一直不变。

原因:退化导致基可行解中有零分量,单纯形法可能在几个基之间循环。

解决:加Bland规则,或者设迭代上限直接报错。实际工程中,更常见的做法是加一个微小的随机扰动,打破退化。比如在右端项上加1e-8的随机数。但这样会引入误差,所以只适合对精度要求不高的场景。如果精度要求高,还是用Bland规则。

5. 用Python验证课件里的每个例题:从手算到代码的闭环

5.1 搭建一个可复用的单纯形验证脚本

课件里的例题通常只有答案,没有中间过程。你手算完之后,怎么知道对不对?最可靠的方法是用代码复现。我一般会写一个通用的验证脚本,输入标准型的c、A、b和初始基,输出每次迭代的基变量、目标值、检验数。这样你可以逐步对照手算的单纯形表。

下面这个脚本在之前的基础上增加了迭代日志,方便对照:

import numpy as np def simplex_verbose(c, A, b, basis, max_iter=50): """ 带详细日志的单纯形法,用于对照手算过程 """ m, n = A.shape c = np.array(c, dtype=float) A = np.array(A, dtype=float) b = np.array(b, dtype=float) basis = list(basis) print("初始基变量:", [f"x{i}" for i in basis]) print("初始目标值:", c[basis] @ np.linalg.solve(A[:, basis], b)) print("-" * 60) for it in range(max_iter): B = A[:, basis] c_B = c[basis] x_B = np.linalg.solve(B, b) B_inv = np.linalg.inv(B) sigma = c - c_B @ B_inv @ A print(f"\n第{it}次迭代:") print(f"基变量: {[f'x{i}' for i in basis]}") print(f"基可行解: {dict(zip([f'x{i}' for i in basis], np.round(x_B, 4)))}") print(f"检验数: {dict(zip([f'x{i}' for i in range(n)], np.round(sigma, 4)))}") print(f"目标值: {c_B @ x_B:.4f}") if np.all(sigma <= 1e-9): print("\n达到最优条件") x = np.zeros(n) x[basis] = x_B return x, c @ x enter = np.argmax(sigma) d = B_inv @ A[:, enter] ratios = [] for i in range(m): if d[i] > 1e-9: ratios.append(x_B[i] / d[i]) else: ratios.append(np.inf) if all(r == np.inf for r in ratios): print("问题无界") return None, None leave_idx = np.argmin(ratios) leave = basis[leave_idx] print(f"入基: x{enter}, 出基: x{leave}") print(f"方向向量: {np.round(d, 4)}") print(f"比值: {[round(r, 4) if r != np.inf else 'inf' for r in ratios]}") basis[leave_idx] = enter print("超过最大迭代次数") return None, None # 课件例题:max z = 5x1 + 4x2 + 3x3 # s.t. 2x1 + 3x2 + x3 <= 5 # 4x1 + x2 + 2x3 <= 11 # 3x1 + 4x2 + 2x3 <= 8 # x1, x2, x3 >= 0 c = [5, 4, 3, 0, 0, 0] A = [[2, 3, 1, 1, 0, 0], [4, 1, 2, 0, 1, 0], [3, 4, 2, 0, 0, 1]] b = [5, 11, 8] basis = [3, 4, 5] x, z = simplex_verbose(c, A, b, basis) print(f"\n最终最优解: {np.round(x, 4)}") print(f"最终最优值: {z:.4f}")

这个脚本的输出格式是专门为对照手算设计的。每次迭代打印基变量、基可行解、检验数、目标值、入基出基变量、方向向量和比值。你手算完一次迭代,就对照一次输出,很快就能定位到哪一步算错了。

参数方面,max_iter设50足够应付大多数课件例题。如果超过50次还没收敛,要么是退化循环,要么是代码有bug。1e-9的容差可以根据问题规模调整,变量多的时候可以放宽到1e-7。

5.2 对偶问题的自动构造与验证

手算对偶问题容易出错,尤其是约束类型和变量符号的对应。我写了一个函数,输入原问题的系数矩阵和约束类型,自动输出对偶问题的标准型:

def construct_dual(c, A, b, constraint_types, var_signs): """ 自动构造对偶问题 c: 原问题目标函数系数 (max问题) A: 原问题约束系数矩阵 b: 原问题右端项 constraint_types: 每个约束的类型列表,'<=' 或 '>=' 或 '=' var_signs: 每个变量的符号列表,'>=' 表示非负,'<=' 表示非正,'free' 表示无约束 返回对偶问题的c_dual, A_dual, b_dual, 以及约束类型和变量符号 """ m, n = A.shape A = np.array(A, dtype=float) c = np.array(c, dtype=float) b = np.array(b, dtype=float) # 对偶问题的变量个数 = 原问题约束个数 # 对偶问题的约束个数 = 原问题变量个数 # 对偶目标函数系数 = 原问题右端项 c_dual = b.copy() # 对偶约束系数矩阵 = 原问题系数矩阵的转置 A_dual = A.T.copy() # 对偶右端项 = 原问题目标函数系数 b_dual = c.copy() # 确定对偶变量的符号 dual_var_signs = [] for ct in constraint_types: if ct == '<=': dual_var_signs.append('>=') elif ct == '>=': dual_var_signs.append('<=') else: dual_var_signs.append('free') # 确定对偶约束的类型 dual_constraint_types = [] for vs in var_signs: if vs == '>=': dual_constraint_types.append('>=') elif vs == '<=': dual_constraint_types.append('<=') else: dual_constraint_types.append('=') return c_dual, A_dual, b_dual, dual_constraint_types, dual_var_signs # 测试:原问题 max z = 3x1 + 2x2 # s.t. x1 + x2 <= 4 # 2x1 + x2 <= 5 # x1, x2 >= 0 c = [3, 2] A = [[1, 1], [2, 1]] b = [4, 5] constraint_types = ['<=', '<='] var_signs = ['>=', '>='] c_dual, A_dual, b_dual, dual_ct, dual_vs = construct_dual(c, A, b, constraint_types, var_signs) print("对偶问题:") print(f"目标函数: min w = {c_dual[0]}y1 + {c_dual[1]}y2") print(f"约束1: {A_dual[0][0]}y1 + {A_dual[0][1]}y2 {dual_ct[0]} {b_dual[0]}") print(f"约束2: {A_dual[1][0]}y1 + {A_dual[1][1]}y2 {dual_ct[1]} {b_dual[1]}") print(f"变量符号: y1 {dual_vs[0]} 0, y2 {dual_vs[1]} 0")

这个函数的逻辑是:对偶问题的目标函数系数是原问题的右端项,对偶问题的右端项是原问题的目标函数系数,对偶问题的系数矩阵是原问题系数矩阵的转置。约束类型和变量符号的对应关系按照之前表格里的规则自动生成。

参数说明:constraint_types列表长度必须等于约束个数,每个元素是'<=', '>=', '='之一。var_signs列表长度必须等于变量个数,每个元素是'>=', '<=', 'free'之一。如果原问题是min,需要先把目标函数取反变成max,构造完对偶后再把对偶目标函数取反变回min。

5.3 用对偶信息做灵敏度分析的实操

灵敏度分析最常用的场景是:右端项b_i变化多少,最优基不变?这个范围可以通过对偶变量和基矩阵的逆来计算。具体来说,b_i的变化范围是[max(-x_B[i] / B_inv[i][i], ...), ...],但更简单的做法是直接用代码扫描。

def sensitivity_analysis(c, A, b, basis, delta_range=(-5, 5), steps=21): """ 扫描右端项b[0]的变化对最优值的影响 """ import numpy as np from scipy.optimize import linprog c_neg = [-x for x in c] # scipy求min bounds = [(0, None)] * len(c) results = [] for delta in np.linspace(delta_range[0], delta_range[1], steps): b_new = b.copy() b_new[0] += delta res = linprog(c_neg, A_ub=A, b_ub=b_new, bounds=bounds, method='highs') if res.success: results.append((delta, -res.fun)) else: results.append((delta, None)) # 打印结果 print("b1变化量\t最优值") for delta, z in results: if z is not None: print(f"{delta:.2f}\t\t{z:.4f}") else: print(f"{delta:.2f}\t\t不可行") return results # 测试 c = [3, 2] A = [[1, 1], [2, 1]] b = [4, 5] basis = [2, 3] results = sensitivity_analysis(c, A, b, basis)

这个脚本扫描b1从-5到+5的变化,每次调用linprog求解,记录最优值。你可以从输出里看到:在某个范围内,最优值随b1线性增加,斜率就是影子价格;超出这个范围后,斜率改变,说明最优基变了。

实际工程中,你不需要扫描整个范围,只需要计算当前基下的允许变化范围。公式是:b_i的变化量Δb_i必须满足B_inv * (b + Δb) ≥ 0,也就是Δb_i ≥ -x_B[i] / B_inv[i][i](如果B_inv[i][i] > 0)。这个范围就是保持当前最优基不变的最大范围。

我一般会把这个扫描脚本和课件里的灵敏度分析例题对照,看看手算的范围和代码扫描的拐点是否一致。如果不一致,大概率是手算时符号或者矩阵求逆算错了。

5.4 从课件到工程:什么时候该用单纯形法,什么时候不该用

单纯形法的时间复杂度在最坏情况下是指数级的,虽然实际中通常很快。对于大规模问题(变量数超过10000),建议用内点法。scipy的linprog默认用highs,内部会根据问题规模自动选择单纯形法或内点法。

如果你只是做课件里的例题,变量数不超过10个,手算加代码验证足够了。如果你要做工程优化,比如生产计划、物流调度,变量数可能上百,这时候直接用求解器,不要自己写单纯形法。自己写的代码在数值稳定性和性能上都比不过成熟求解器。

但理解单纯形法和对偶理论仍然重要,因为求解器输出的对偶变量、灵敏度报告,都需要你懂原理才能正确解读。我见过有人拿到影子价格是负的,直接懵了,不知道该怎么调整资源。其实负的影子价格意味着这个约束是≥类型的,或者原问题是min问题,符号约定不同而已。

最后一个技巧:当你用求解器得到结果后,把最优解代回原约束,检查哪些约束是紧的(取等号),哪些是松的。紧约束对应的对偶变量通常非零,松约束对应的对偶变量为零。这个互补松弛条件是你验证求解器输出是否合理的最快方法。如果发现紧约束的对偶变量是零,或者松约束的对偶变量非零,那要么是退化,要么是求解器有数值问题。

我自己刚开始学的时候,总觉得对偶理论很抽象,直到用代码把原问题和对偶问题都解了一遍,发现目标值确实相等,才真正信了。后来做工程,每次看到影子价格,都会下意识地想:这个资源值不值得多买一点。这个习惯帮我省了不少成本。希望帮到你。

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

需要专业的网站建设服务?

联系我们获取免费的网站建设咨询和方案报价,让我们帮助您实现业务目标

立即咨询