数学线性规划本页总览线性规划阐述 mincTx, s.t. x∈P\min c^Tx,~\mathrm{s.t.}~x\in PmincTx, s.t. x∈P PPP 是一个多面体, 标准形式:Ax=b,x≥0Ax=b,x\ge0Ax=b,x≥0 几何形式:Ax≥bAx\ge bAx≥b 其中 c,x∈Rn,b∈Rm,A∈Rm×nc,x\in\mathbb R^n, b\in\mathbb R^m, A\in\mathbb R^{m\times n}c,x∈Rn,b∈Rm,A∈Rm×n。 形式化 一个好的线性规划描述应该具有比较少的变量数量和约束数量,并且矩阵 A 尽可能稀疏。 非标准情形 最大化:翻转 ccc 的符号 变量 xix_ixi 可正可负:替换为 xi+−xi−x_i^+-x_i^-xi+−xi− 相等约束:替换为两个等于的约束 …… 实例 性质 凸性