# 线性规划

## 标准型

• 一个需要极大化的线性函数，例如
${\displaystyle c_{1}x_{1}+c_{2}x_{2}}$
• 以下形式的问题约束，例如：
${\displaystyle a_{11}x_{1}+a_{12}x_{2}\leq b_{1}}$
${\displaystyle a_{21}x_{1}+a_{22}x_{2}\leq b_{2}}$
${\displaystyle a_{31}x_{1}+a_{32}x_{2}\leq b_{3}}$
• 和非负变量，例如：
${\displaystyle x_{1}\geq 0}$
${\displaystyle x_{2}\geq 0}$

maximize ${\displaystyle \mathbf {c} ^{T}\mathbf {x} }$
subject to ${\displaystyle \mathbf {A} \mathbf {x} \leq \mathbf {b} ,\,\mathbf {x} \geq 0}$

### 例子

 ${\displaystyle \max Z=S_{1}x_{1}+S_{2}x_{2}}$ (最大化利潤 - 目標函數) ${\displaystyle s.t.}$ ${\displaystyle x_{1}+x_{2}\leq A}$ (種植面積的限制) ${\displaystyle F_{1}x_{1}+F_{2}x_{2}\leq F}$ (肥料數量的限制) ${\displaystyle P_{1}x_{1}+P_{2}x_{2}\leq P}$ (農藥數量的限制) ${\displaystyle x_{1}\geq 0,\,x_{2}\geq 0}$ （不可以栽種負數的面積）

## 增广矩阵（松弛型）

Maximize ${\displaystyle Z}$ in:
${\displaystyle {\begin{bmatrix}1&-\mathbf {c} ^{T}&0\\0&\mathbf {A} &\mathbf {I} \end{bmatrix}}{\begin{bmatrix}Z\\\mathbf {x} \\\mathbf {x} _{s}\end{bmatrix}}={\begin{bmatrix}0\\\mathbf {b} \end{bmatrix}}}$
${\displaystyle \mathbf {x} ,\,\mathbf {x} _{s}\geq 0}$

### 例子

 maximize ${\displaystyle S_{1}x_{1}+S_{2}x_{2}}$， (目标函数) subject to ${\displaystyle x_{1}+x_{2}+x_{3}=A}$， (限制式) ${\displaystyle F_{1}x_{1}+F_{2}x_{2}+x_{4}=F}$， (限制式) ${\displaystyle P_{1}x_{1}+P_{2}x_{2}+x_{5}=P}$， (限制式) ${\displaystyle x_{1},x_{2},x_{3},x_{4},x_{5}\geq 0}$

Maximize ${\displaystyle Z}$ in:
${\displaystyle {\begin{bmatrix}1&-S_{1}&-S_{2}&0&0&0\\0&1&1&1&0&0\\0&F_{1}&F_{2}&0&1&0\\0&P_{1}&P_{2}&0&0&1\\\end{bmatrix}}{\begin{bmatrix}Z\\x_{1}\\x_{2}\\x_{3}\\x_{4}\\x_{5}\end{bmatrix}}={\begin{bmatrix}0\\A\\F\\P\end{bmatrix}},\,{\begin{bmatrix}x_{1}\\x_{2}\\x_{3}\\x_{4}\\x_{5}\end{bmatrix}}\geq 0}$

## 对偶

maximize ${\displaystyle \mathbf {c} ^{T}\mathbf {x} }$
subject to ${\displaystyle \mathbf {A} \mathbf {x} \leq \mathbf {b} ,\,\mathbf {x} \geq 0}$

minimize ${\displaystyle \mathbf {y} ^{T}\mathbf {b} }$
subject to ${\displaystyle \mathbf {y} ^{T}\mathbf {A} \geq \mathbf {c} ^{T},\,\mathbf {y} \geq 0}$

### 例子

 ${\displaystyle \min E=Fy_{1}+Py_{2}}$ ${\displaystyle s.t.}$ ${\displaystyle F_{1}y_{1}+P_{1}y_{2}\geq S_{1}}$ (控制肥料與農藥的價格，使得农夫觉得比起拿那些肥料和農藥去種植小麥，賣給園主更有利可图) ${\displaystyle F_{2}y_{1}+P_{2}y_{2}\geq S_{2}}$ (與上相似，但改為大麥) ${\displaystyle y_{1}\geq 0,\,y_{2}\geq 0}$ （不可用负数单位金額购买）

## 演算法

1984年，貝爾實驗室印度裔數學家提出了投影尺度法（又名）。這是第一個在理論上和實際上都表現良好的算法：它的最壞情況僅為多項式時間，且在實際問題中它比單純形演算法有顯著的效率提升。自此之後，很多內點演算法被提出來並進行分析。一個常見的內點演算法為Mehrotra predictor-corrector method。儘管在理論上對它所知甚少，在實際應用中它卻表現出色。

• LP存在强多项式时间算法吗？
• LP存在多项式时间算法以得到一个严格互补解吗?
• LP在实数（单位成本）模型下存在多项式时间算法吗?

• Are there pivot rules which lead to polynomial-time Simplex variants?
• Do all polytopal graphs have polynomially-bounded diameter?

## 整數規劃

0-1整數規劃是整數規劃的特殊情況，所有的變量都要是0或1（而非任意整數）。這類問題亦被分類為NP困難問題