gpt4 book ai didi

algorithm - 单纯形 - 规范形式基础背后的代数直觉

转载 作者:塔克拉玛干 更新时间:2023-11-03 05:13:45 26 4
gpt4 key购买 nike

我试图通过遵循此 text 来理解具有 n 变量和 m 技术约束的问题的单纯形迭代.我非常理解迭代的几何解释 - 在相邻顶点之间移动。

但是,我无法理解代数直觉。现在我们在相邻的基本可行解 = bfs 之间旋转AX + IS = b 的标准形式, X,S >= 0 :

  1. 为什么 bfs 必须有 n 变量等于 0?
  2. 为什么其余的变量应该形成一个基础?基不是一组跨越子空间的线性独立向量吗?我们在这里跨越什么,我们只是在寻找一个顶点,不是吗?

谢谢!

最佳答案

  1. BFS 应该正确地将 n-m 非基本变量设置为 0。一些 m 基本变量本身可能是 0,但这是退化的解决方案。

  2. 基础确实是跨越向量 b 的最小线性独立变量集。请注意,b 是一个 m-vector。因此,m 个变量对应的向量可以组成一个BFS。变量总数为 n。因此碱基数是指数级的n选择m

从一个顶点旋转或移动到另一个顶点只不过是将一个非基本变量(关联的列向量)替换为基础并从基础中删除一个预先存在的变量。因此,基础将始终具有 m(列)向量。

在任何一个时间点,将 A 划分为基本变量和非基本变量,例如 A = [B|N],则 Bx = b 和因此,x 变量是 B 范围内的系数,它给出了 b

有界线性约束线性规划的可行多面体的每个顶点对应于基本解,反之亦然,这是线性规划的一个基本结果。引用:https://press.princeton.edu/titles/413.html

关于algorithm - 单纯形 - 规范形式基础背后的代数直觉,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/53246360/

26 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com