AOR3 近似算法
许多问题都可以用线性整数规划表示，但是极少数可以由线性规划直接求解。其中，大多数问题是NP-Hard的，所以近似算法是一种重要的求解方法。本节我们要介绍的就是LP Rounding Based近似算法。
概念引入
对于一个极小化问题，称一个实例为III，近似算法为AAA，则A(I)A(I)A(I)表示算法AAA的目标函数值，OPT(I)OPT(I)OPT(I)表示最优目标函数值。
近似比： 若对于任何实例，都有A(I)≤r∗OPT(I),r≥1A(I) \leq r * OPT(I), r \ge 1A(I)≤r∗OPT(I),r≥1，那么称ρ=inf{r}\rho = inf\{r\}ρ=inf{r}为近似比。
等价定义：ρ=supA(I)OPT(I)\rho = \sup{\frac{A(I)}{OPT(I)} }ρ=supOPT(I)A(I)
对于极大化问题，取ρ=supOPT(I)A(I)\rho = \sup{\frac{OPT(I)}{A(I)} }ρ=supA(I)OPT(I)。
所以一般地，我们有：ρ=sup{OPT(I)A(I),A(I)OPT(I)}\rh ...
AOR2 原始对偶方法、整数规划
原始对偶方法、整数规划
原始对偶方法
原始对偶方法的基本思路是利用前面讲过的互补松弛定理。
互补松弛定理：若 x∗x^*x∗，y∗y^*y∗分别是P、D的可行解，则：x∗,y∗x^*,y^*x∗,y∗最优 ⇔\Leftrightarrow⇔(y∗TA−cT)x∗=0y∗T(Ax∗−b)=0\begin{aligned} (y^{*^T}A-c^T)x^*=0 \\ y^{*^T}(Ax^*-b)=0 \end{aligned}(y∗TA−cT)x∗=0y∗T(Ax∗−b)=0。
所以，我们从D的一个可行解 yyy出发，尝试寻找P的可行解 xxx，使得 xxx、yyy能够满足互补松弛条件。如果能够找到这样的 xxx，则 xxx、yyy就分别是P、D的最优解；如果找不到这样的 xxx，说明 yyy还不是最优解，我们需要调整使之成为最优解。这个思路就是原始对偶方法。
判断最优解
考虑 （P） mincTxs.t.Ax=bx≥0\begin{aligned} \min \quad & c^Tx \\ \text{s.t.} \quad & Ax = b \\ & ...
AOR1 线性规划、单纯形法、对偶单纯形法
本部分为应用运筹学基础笔记整理Part 1。由于有部分内容课上没来得及记下，用学长的博客补充了部分定理证明的内容。
latex被我修好了，可喜可贺。
参考博客
1. 优化问题的基本概念
基本模型
基本模型：变量，变量限制和一个需要优化的目标函数。
数学表示：min(max) f(x)min(max)\ f(x)min(max) f(x), s.t.s.t.s.t. x∈Ωx\in\Omegax∈Ω. 这里 Ω\OmegaΩ 为变量限制（Feasible Set），通常是一些等式或不等式。
例子：LP，TSP
邻域、局部最优与全局最优
邻域（Neighborhood）：给定一个优化问题 (Ω,f)(\Omega, f)(Ω,f) ，邻域是 Ω\OmegaΩ 到其幂集 2Ω2^\Omega2Ω 的映射，即 N:Ω→2ΩN: \Omega \rightarrow 2^\OmegaN:Ω→2Ω 。
TSP：对一个可行解，去掉两条不相邻的边，交叉相连，即可得到一个邻域解（2-change，N2N_2N2）。
MST：改变一条边。
对某一个邻域，如果其局部最优就是全局最优 ...
TinyXML2 获取信息方面的使用
主要是为了oop大程学一下方便记录……
（可能用不到就删了）
用户数据表设计如下：
变量名
描述
类型
长度（字节）
不为空
主键
UserName
用户名
Vchar
3-20
Y
Y
Password
密码
Char
32
Y
N
Gender
性别
Int
1
N
N
Mobile
电话
Char
11
N
N
Email
电子邮箱
Varchar
1-50
N
N
对应XML文件实现：
查询xml文件的指定节点
Xml文件中，一个用户节点存储一个用户的信息。因此，对用户信息的增删查改，即无论查询节点、删除节点、修改节点和增加节点，都需要获取需要操作的节点。那么先实现一个根据用户名获取节点指针的函数：
//function:根据用户名获取用户节点//param:root:xml文件根节点；userName：用户名//return：用户节点XMLElement* queryUserNodeByName(XMLElement* root,const string& userName){ XMLElement* userNod ...
