线性规划算法

1. 前言

重点介绍Seidel’s线性规划算法，适用于低纬度线性规划

完整代码详见github

2. 代码详解

2.1 linprog函数

求解的问题为

$$\begin{gather*} \min \bm{C}^{\top}\bm{x} \\ s.t. \bm{Ax} \leq \bm{b} \end{gather*}$$

prev存储的是链表中第i个元素的前一个元素的索引

next存储的是链表中第i个元素的后一个元素的索引

perm存储的是随机排列数列

2.2 rand_permutation函数

随机排列，参考随机排列算法博客