最优化及其运用 学习笔记（一）

【定义】线性规划是研究线性不等式组的理论，或者收是研究（高维空间中）凸多面体的理论，是线性代数的应用和发展。

【解决的问题】

1、max  总收入或总利润，

              总成本 ≤ b

2、min  总成本 

              总收入 ≥ b

【运筹学解决问题的主要程序】

生产管理问题--->线性规划数学模型--->图解法与单纯形法求解--->对偶问题与灵敏度分析--->指导生产管理

【模型要素】决策变量、目标函数、约束条件+符号约束、可行域、最优解

（约束了决策变量的取值范围）

1、决策变量取什么（设决策变量的原则）

2、定义目标函数       Max Z =2x1+3x2

3、表示约束条件

【线性规划的标准型】

1、求解目标函数的最小值

2、约束条件为等式约束(右端值非负）

3、变量非负

【标准化 方法】

1、Max ---> Min

2、>或<   --->  =   ±s松弛变量

3、自由变量x1 <> 0  ---> x1= x1'-x1'' （x1', x1'' > 0）

【图解法】两个决策变量才能做

可行解：满足约束条件的变量值

可行域：同时满足所有约束条件的变量值域

最优解：是目标函数取得最优质的可行解

<重要结论1>满足约束条件的可行域一般都构成凸多边形。

<重要结论2>最优解必定再凸多边形的某一个顶点上取得。

最优解是唯一的或者无穷的。

<解的情况>

 

线性规划标准型的<矩阵形式>

Min     S = CX

s.t.       AX = b

      X ≥ 0

 

 

 

满足约束条件（ 1-10） 的X，称为 线性规划问题的可行解

满足目标函数（1-9）的可行解X，称为 线性规划的问题最优解。

 

基、基向量、基变量

⊙设 r(A) = m，并且 B 是 A 的 m 阶非奇异的子矩阵（det(B) <> 0)，

    则矩阵 B 称为线性规划问题的一个基。

⊙矩阵 B =（P1，P2….Pm) ，其列向量 Pj 称为 对应基 B 的基向量。

    A中其余列向量称为 非基向量。

⊙与基向量 Pj 相对应的变量xj就称为

    基变量，其余的就称为非基变量。

基本解、基本可行解、可行基

⊙对于某一特定的基B，非基变量取 0 值的解，称

    为 基本解。

⊙满足非负约束条件的基本解，称

    为 基本可行解。

⊙与基本可行解对应的基，称

    为 可行基。