《线性规划》复习提纲2011.ppt

《《线性规划》复习提纲2011.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、《线性规划》复习提纲授课：万飚时间：2021年8月6日1．线性规划的描述知识点内容数学模型一般型式；组成部分图解法作图：2个变量；解的形式：唯一解；无穷解；无界解；无可行解。标准型型式；一般型化标准型2．基本概念知识点内容解的概念可行解；最优解基与基解基；（非）基变量；基解基可行解基可行解；可行基；解之间的关系（图）凸集凸集；凸组合顶点顶点3．基本理论——线性规划的理论基础知识点内容定理1线性规划的可行域是凸集（描述了可行域的特征）定理2基可行解对应可行域顶点（描述了顶点与基可行解的关系）定理3在某个顶点可达到最优解

2、（描述了最优解在可行域中的位置）4．基本方法知识点内容单纯形法原理：最优解在顶点上，从一个可行基迭代到下一个可行基步骤：①确定初始基可行解；②最优性检验③基变换（最大σ规则；最小θ规则）④迭代单纯形表；列表计算人工变量法大M法：对人工变量在目标函数中加惩罚两阶段法：第一阶段辅助问题最小化退化解改进单纯形法单纯形法的矩阵描述计算步骤：用矩阵形式表示换基过程5．对偶理论知识点内容对偶问题原问题与对偶问题的关系；相互转换基本性质对称性：对偶问题的对偶问题是原问题弱对偶性：对max，CX<=Yb无界性：原问题无界，对偶问题无

3、可行解最优性：CX*＝Y*b时，X*、Y*为最优解对偶定理：原问题有最优解，对偶问题也有最优解，且目标值相等互补松弛性：X*、Y*为可行解，则Y*Xs＝0和YsX*＝0<==>X*、Y*为最优解单纯形表中的对应关系：①原问题单纯形表的检验数行对应其对偶问题的一个基解②最优单纯形表中，原问题松弛变量对应检验数的相反数是对偶问题的最优解。5．对偶理论（续）知识点内容影子价格对偶问题最优解的经济意义对偶单纯形法原理：保持对偶问题可行，从原问题的非基可行解开始迭代步骤：先定换出变量(minb<0)，再定换入变量(minθ)6

4、．灵敏度分析知识点内容问题的提出待求问题：系数A、b、C发生变化时，解如何变化？需要解决：解的变化；最优解不变的范围；如何求解？灵敏度分析资源数量b变化分析目标函数价值系数cj变化分析技术系数aij的变化分析