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

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

線性規(guī)劃的標(biāo)準(zhǔn)形式

非標(biāo)準(zhǔn)形LP模型轉(zhuǎn)化為標(biāo)準(zhǔn)形LP模型

基本概念

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

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

基本可行解存在性

求基本可行解

求基本可行解<=>求極點(diǎn)<=>求可行基矩陣<=>$A_{m?n}$矩陣m個(gè)線性無(wú)關(guān)列

示例：求基本可行解

求最優(yōu)解

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

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

方法二（迭代）：從一個(gè)基本可行解跳轉(zhuǎn)到一個(gè)目標(biāo)函數(shù)值更小的基本可行解

多面體

多面體基本性質(zhì)

多面體的極點(diǎn)

x若是極點(diǎn)，正分量對(duì)應(yīng)的A的列一定線性無(wú)關(guān)。

示例：求極點(diǎn)

多面體S有多少個(gè)極點(diǎn)？- 有限個(gè) & 最多$C_n^m$

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

多面體的方向

多面體的極方向

多面體的極方向有多少個(gè)？- 有限個(gè)

示例：求極方向

d≥0

多面體分解定理

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

重新表示可行集

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

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

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

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

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

$C^T{d}_j<0$時(shí)，無(wú)解。

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

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

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

單純形法

基本思想

原理

實(shí)現(xiàn)基本可行基的轉(zhuǎn)化

方法

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

1 確定出基變量和出基向量的下標(biāo)

2 確定進(jìn)基變量和進(jìn)基向量的下標(biāo)

3 確定進(jìn)基變量的值

目標(biāo)函數(shù)值只與非基變量有關(guān)。

終止條件

單純形法計(jì)算步驟

單純形法表格形式