什么是線性規(guī)劃（Linear Programming，LP）？

目標函數(shù)為決策變量的線性函數(shù)，同時約束條件為線性等式或線性不等式約束。

線性規(guī)劃的標準形式

非標準形LP模型轉化為標準形LP模型

基本概念

基本解&基矩陣&基變量&非基變量

基本可行解&可行基矩陣&非退化的基本可行解&退化的基本可行解

基本可行解存在性

求基本可行解

求基本可行解<=>求極點<=>求可行基矩陣<=>$A_{m?n}$矩陣m個線性無關列

示例：求基本可行解

求最優(yōu)解

方法一（暴力枚舉）：求出所有基本可行解找最小

求出所有基本可行解（即求極點）。
代入目標函數(shù)找出最小極點（該最小極點即為最優(yōu)解，因為最優(yōu)解一定在極點取得）。

方法二（迭代）：從一個基本可行解跳轉到一個目標函數(shù)值更小的基本可行解

多面體

多面體基本性質

多面體的極點

x若是極點，正分量對應的A的列一定線性無關。

示例：求極點

多面體S有多少個極點？- 有限個 & 最多$C_n^m$

最多有$C_n^m$個極點，一般都少于$C_n^m$，有兩個原因。
原因1：從n個列中選出m列不一定線性無關。
原因2：即使這m列線性無關，其組成的B也不一定滿足$B^{?1}b\ge 0$。

多面體的方向

多面體的極方向

多面體的極方向有多少個？- 有限個

示例：求極方向

d≥0

多面體分解定理

多面體分解定理有什么作用？

重新表示可行集

重新定義線性規(guī)劃問題

為什么$\min \sum {\lambda }_i{C}^T{x}_i$等價于$\min C^T{x}_i,i=1,...,k$？

求$\min C^T{x}_i，i=1,...,k$，找到最小$x_r$就是最優(yōu)值點，令$\min \sum {\lambda }_i{C}^T{x}_i$中${\lambda }_r=1$其他的λ都為0，$C^T{x}_r$就是最優(yōu)值。

何時有最優(yōu)解？

$C^T{d}_j\ge 0$時，存在最優(yōu)解。

$C^T{d}_j<0$時，無解。

最優(yōu)解是什么？

最優(yōu)解一定在極點上取到。

$\min C^T{x}_i，i=1,...,k$，找到最小$x_r$就是最優(yōu)值點，$C^T{x}_r$就是最優(yōu)值。

單純形法

基本思想

原理

實現(xiàn)基本可行基的轉化

方法

從初始基本可行解出發(fā)，求一個改進的基本可行解。

1 確定出基變量和出基向量的下標

2 確定進基變量和進基向量的下標

3 確定進基變量的值

目標函數(shù)值只與非基變量有關。

終止條件

單純形法計算步驟

單純形法表格形式