2014考研西安建筑科技大学《816运筹学》冲刺串讲讲义

《2014考研西安建筑科技大学《816运筹学》冲刺串讲讲义》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、西安建筑科技大学《８１６运筹学》冲刺串讲第１讲线性规划（一）线性规划内容（１）ＬＰ数学模型（２）ＬＰ各种解的概念：可行解（重点）基本概念基本解（难点）基本可行解（重点）最优解基本最优解解的基本性质：六个主要定理？条件实际问题→ＬＰ模型→图解法大Ｍ法基本方法单纯形法（原始单纯形法、人工变量法）{两阶段法对偶单纯形法（求解）前提？步骤？修正单纯形法进一步讨论对偶理论{灵敏度分析→参数规划经济管理方面的典型问题整数规划特殊ＬＰ{运输问题多目标规划一、线性规划的数学模

2、型及其几种常用的形式ｍａｘｆ（ｘ）＝ｃ１ｘ１＋ｃ２ｘ２＋…＋ｃｎｘｎ或ｍｉｎｆ（ｘ）＝ｃ１ｘ１＋ｃ２ｘ２＋…＋ｃｎｘｎ①ａ１１ｘ１＋ａ１２ｘ２＋…＋ａ１ｎｘｎ≥（≤或＝）ｂ１ａ２１ｘ１＋ａ２２ｘ２＋…＋ａ２ｎｘｎ≥（≤或＝）ｂ２……………………②ａｍ１ｘ１＋ａｍ２ｘ２＋…＋ａｍｎｘｎ≥（≤或＝）ｂｍｘｊ≥０（ｊ＝１，２，…，ｎ）—１—考试点（ｗｗｗｋａｏｓｈｉｄｉａｎｃｏｍ）名师精品课程电话：４００－６８８５－３６５①式称为线性规划的目标函数②式称为线性规划的约束条件ｘｊ称为线性规划的决策变量１．目标函数极大化２．约束方程等式化３．决策变量非负

3、化４．资源限值非负化５．代数形式ｍａｘｆ（ｘ）＝ｃ１ｘ１＋ｃ２ｘ２＋…＋ｃｎｘｎａ１１ｘ１＋ａ１２ｘ２＋…＋ａ１ｎｘｎ＝ｂ１ａ２１ｘ１＋ａ２２ｘ２＋…＋ａ２ｎｘｎ＝ｂ２………………………ｓ·ｔａｍ１ｘ１＋ａｍ２ｘ２＋…＋ａｍｎｘｎ＝ｂｍｘｊ≥０（ｊ＝１，２，…，ｎ）ｂｉ≥０（ｉ＝１，２，…，ｍ）矩阵形式ｍａｘｆ（ｘ）＝ＣＸＡＸ＝ｂｓ·ｔ{Ｘ≥０ｂ≥０Ｔ其中：Ｘ＝（ｘ１，ｘ２，…，ｘｎ）Ｃ＝（ｃ１，ｃ２，…，ｃｎ）Ｔｂ＝（ｂ１，ｂ２，…，ｂｍ）向量形式ｍａｘｆ（ｘ）＝ｃ１ｘ１＋ｃ２ｘ２＋……＋ｃｎｘｎＰ１ｘ１＋Ｐ２ｘ２＋……＋Ｐｎｘｎ＝ｂｓ·ｔ{

4、Ｘ≥０ｂ≥０Ｔ其中：Ｐｊ＝（ａ１ｊ，ａ２ｊ，…，ａｍｊ）ｊ＝（１，２，…，ｎ）Ｔｂ＝（ｂ１，ｂ２，…，ｂｍ）ａ１１ａ１２…ａ１ｎａ２１ａ２２…ａ２ｎＡ＝…………ａｍ１ａｍ２…ａｍｎ—２—西安建筑科技大学《８１６运筹学》冲刺串讲标准型的变换方法１．目标函数为极小化。将目标函数两边乘以“－１”２．约束条件为不等式。３．决策变量４．资源限值：ｂ≤０时，在约束函数两边同时乘以“－１”二、线性规划的几种解的定义及其关系。可行解：满足所有约束条件的解。最优解：使目标函数取得最大值的可行解。基本解：对某一确定的基Ｂ，令所有的非基变量为零，利用ＡＸ＝ｂ求解出基变量的值

5、，则这组解称为基Ｂ的基本解。基本可行解：若得到的基本解满足非负性约束，称为基本可行解。基本最优解：使目标函数取得最优的基本可行解称为基本最优解。其关系为：三、线性规划的解有如下几种情况：１．可行域为封闭的有界区域（ａ）有唯一的最优解；（ｂ）有无穷多个最优解；２．可行域为非封闭的无界区域（ｃ）有唯一的最优解；（ｄ）有无穷多个最优解；（ｅ）目标函数无界（即虽有可行解，但在可行域中，目标函数可以无限增大或无限减少），因而没有有限最优解。３．可行域为空集（ｆ）没有可行解，原问题无最优解四、关于线性规划的六个重要定理ｎ（１）（２）定理一设ＥＲ，若Ｅ中任意两点ｘ，ｘ的连线仍属

6、于Ｅ，即（１）（２）（１）（２）ｘ∈Ｅ，ｘ∈Ｅｘ＝ａｘ＋（１－ａ）ｘ∈Ｅ，（０!ａ!１），则称Ｅ为凸集。若对于凸集Ｅ中的点ｘ，不存在Ｅ中两个相异的点使下式成立：（１）（２）ｘ＝ａｘ＋（１－ａ）ｘ，（０＜ａ＜１），则称ｘ为Ｅ的极点或顶点。—３—考试点（ｗｗｗｋａｏｓｈｉｄｉａｎｃｏｍ）名师精品课程电话：４００－６８８５－３６５定理三线性规划问题的可行解集ｎ（即可行域）Ｄ＝{Ｘ∑Ｐｊｘｊ＝ｂ，ｘｊ０}是凸集。ｊ＝１定理四线性规划几何理论基本定理ｎ若Ｄ＝{Ｘ∑Ｐｊｘｊ＝ｂ，ｘｊ０}，则Ｘ是Ｄ的一个顶点的充分必要条件是Ｘ为线性规划的基本可ｊ＝１行解。定理五若目标函

7、数在ｋ个点处达到最优值（ｋ≥２），则在这些顶点的凸组合上也达到最优值。定理六若可行域非空有界，则线性规划问题的目标函数一定可以在可行域的顶点上达到最优值。引理：可行域非空有界就肯定有最优解要求：此六个定理必需熟记，且会证明。五、关于线性规划的解法１．图解法适用范围：利用直角坐标系及其原理设计出来的一种解法，所以仅适用于二维或三维的线性规划问题的求解。解题步骤：（１）画出各约束条件直线，确定可行域（２）画出目标函数直线，使其朝目标值优化方向平移，找出最后与可行域相接触的顶点（３）连立通过最优顶点的方程，求解出最优解（４）将最优解代入目标函数，求得最优目标值２．单纯