《运筹学复习笔记.doc》由会员分享，可在线阅读，更多相关《运筹学复习笔记.doc（25页珍藏版）》请在金锄头文库上搜索。
1、运筹学复习笔记Part 1 题型1. 选择题（20分）2. 填空题（40分）3. 建模题（40分）4. 决策问题（20分）5. 运输问题（10分）计算Part 2 需要掌握的知识点Chapter 2 线性规划与单纯型法1、 线性规划问题（建模）2、 求解两个变量的线性规划模型图解法 附：图解法的启示1) 图解法求解结果的几种可能情况： 唯一最优解 无穷多最优解 无界解（并不是说可行域是无界的线性规划问题的解就一定是无界解） 无可行解2) 若线性规划问题的可行域非空，则可行域是一个凸集。3) 若线性规划问题的最优解存在，则一定可以在可行域的凸集的某个顶点达到。（线性规划问题的基可行解X对应于可行
2、域D的顶点。）3、 单纯形法准备知识标准型1) 标准型的四个条件 目标函数为极大（max） 所有的约束条件满足等式 所有的决策变量非负 右端常数均为非负数2) 化为标准型的方法 若要求目标函数实现最大化，即max z=CX。这时只需将目标函数最小化变换求目标函数最大化，即令 z=-z，于是得到max z= CX。这就同标准型的目标函数的形式一致了。 约束方程为不等式。这里有两种情况： 一种是约束方程为不等式，则可在不等式的左端加入非负松弛变量，把原不等式变为等式，； 另一种是约束方程为不等式，则可在不等式的左端减去一个非负剩余变量（也可称松弛变量），把不等式约束条件变为等式约束条件,目标函数中
3、加上 (松弛变量). 若变量约束中：，则令，得到；若，则令 ，其中，用 、分别代替、后得到线性规划的变量约束均为非负约束。 资源限量bi 0。4、 单纯型法准备知识线性规划问题解的概念1) 可行解：满足约束条件式（等式约束、非负约束）的解。2) 最优解：使目标函数达到最大值的可行解。3) 基：约束方程组的系数矩阵的一个满秩的子矩阵，B称为线性规划问题的一个基。附：基向量：B矩阵中每一个列向量都称为基向量。基变量：选定的向量（基向量）对应的变量（可以不止一个）称为基变量，其他的变量称为非基变量。4) 基解：有一个基就可以求出一个基解（运用克莱姆法则）。5) 基可行解：满足非负条件式的基解（基解是
4、根据等式约束条件得到的，还没有涉及目标函数和变量非负的约束条件，相当于对一个非齐次线性方程组求解。当这样的基解满足变量非负的约束条件时，我们称它为基可行解。PS：并不一定是最优解。）6) 可行基：与基可行解相对应的基称为可行基。7) 可行域（可行空间）8) 几何性质凸集的概念 考题：求基解、判断是否为基可行解、是否为最优解5、 线性规划问题的一些性质6、 单纯形表（了解，知道如何寻找主元）口诀：最大最小找主元初行变换得新解（新的基可行解）目标函数有改善 例题：1. 例2-1线性规划问题建模2. 用图解法求解例2-1中建立的线性规划模型3. 把例2-1中建立的线性规划模型化为标准型4. 指出例2
5、-1中建立模型的基、基变量、基解、基可行解和可行基5. 单纯型表相关的题型230000812100401640010-01204001323000进行一轮计算以后得到下表230006. 一个更为复杂的建模题某工厂明年根据合同，每个季度末向销售公司提供产品，有关信息如表，若当季生产的产品过多，季末有积余，则一个季度每积压一吨产品需支付存贮费0.2万元。现该厂考虑明年的最佳生产方案，使该厂在完成合同的情况下，全年的生产费用最低。试建立线性规划模型。季度生产能力生产成本需求量1301520240142032015.33041014.810Chapter 3 对偶理论与灵敏度分析（4分）1、 影子价格
6、1) 含义：代表在资源最优利用条件下，对第i种资源一单位的估价，这种估价不是资源的市场价格，而是根据资源在生产中做出的贡献而做的估价。2) 经济意义 影子价格反映资源对目标函数的边际贡献，即资源转化成经济效益的效率。 影子价格反映了资源的稀缺程度。 影子价格反映了资源的边际使用价值。Chapter 4 运输问题（10分）1、 确定初始基可行解最小元素法、伏格尔法确定初始可行解的方法考试不要求，但是对于理解最优解的判别很有帮助。单位运价表产地销地B1B2B3B4A1311310A21928A374105产销平衡表产地销地产量B1B2B3B4A17A24A39销地3656- 最小元素法思想：从单价
7、中最小的运价开始确定供销关系，然后次小，一直到给出初始基可行解为止。Step 1 产地销地B1B2B3B4A1311310A21928A374105产地销地产量B1B2B3B4A17A234A39销地3656-Step 2 产地销地B1B2B3B4A1311310A21928A374105产地销地产量B1B2B3B4A17A2314A39销地3656-Step 3 产地销地B1B2B3B4A1311310A21928A374105产地销地产量B1B2B3B4A1437A2314A3639销地3656- 口诀：最小运价定方向，需求满足便退出，供给耗尽线划去；余下运价找最小，直到运价全划去，所得必
8、是可行解。 伏格尔法最小元素法的缺点：可能开始节省一处的费用，但随后在其他几处要多花几倍的运费。伏格尔法的思想：对差额最大处采用最小运费调运。Step 1 根据单位运价表分别算出各行和各列的最小运费和次小运费的差额。产地销地行差额B1B2B3B4A13113100A219281A3741051列差额2513-Step 2 从行和列差额中选出最大者，选择它所在的行或列中的最小元素，确定供给方向。（这一步是对伏格尔法思想的体现）产地销地行差额B1B2B3B4A13113100A219281A3741051列差额2513-产地销地行差额B1B2B3B4A13113100A219281A3741051
9、列差额2512-产地销地行差额B1B2B3B4A13113107A219281A3741051列差额25310-产地销地行差额B1B2B3B4A13113103A219281A3741051列差额25310-产地销地产量B1B2B3B4A1527A2314A3639销地3656- 口诀：行列运价求差额，差额最大找最小（差额最大行、列处找最小的运价），最小运价定方向；需求满足便退出，供给耗尽线划去；余下步骤均相同，直到运价全划去，所得必是可行解。2、 最优解的判别方法闭回路法要求：求检验数、调整方案、往下进行一步（46分）（选填题）最优解的判别方法：计算空格（非基变量）的检验数。当检验数还存在负
10、数时，说明原方案不是最优解，需要继续改进。 例题：用闭回路法检验上一步中最小元素法得到的初始基可行解是否为最优解。产地销地产量B1B2B3B4A1437A2314A3639销地3656-闭回路法计算检验数的经济解释：在已给出初始解的上表中，可以从任一空格出发，如（A1，B1），若让A1的产品调匀一吨给B1。为了保持产销平衡，就要依次做调整：在（A1，B3）处减少一吨，（A2，B3）处增加一吨，（A2，B1）处减少一吨，即构成（A1，B1）空格为起点，其他为数字格的闭回路。检验数调整后运费的增减数本例中的检验数为：，以其他空格为起点可以得到更多的检验数。如果得到的检验数全为正，则说明初始方案无法
11、得到进一步改进，即初始方案为最优解；反之，初始基可行解不为最优，还存在改进的空间。3、 运输问题的一些性质 基变量的个数（上一个知识点中，通过最小元素法得到的初始基可行解的基变量的个数为6） PS：在产销平衡的运输问题中，。 闭回路的顶点数永远是偶数（只有这样才能保证产销的均衡）Chapter 5 整数线性规划（20分）1、 整数规划问题（建模）：把文字描述分析转化为数学模型整数规划问题：是一类特殊的线性规划问题，是指要求部分或全部决策变量的取值为整数的规划问题。其中，重点掌握整数线性规划问题。2、 整数规划问题的决策3、 整数线性规划问题的类型 纯整数线性规划（重点掌握）全部决策变量都必须取整数值 混合整数线性规划决策变量中一部分必须取整数值，另一部分可以不取整数值 0-1型整数线性规划（重点掌握指派问题）决策变量只能取0或1（用于表现分析投资还是不投资这类问题）4、 人力资源的分配问题（选填题）要求：明白求解的逻辑和方法，求解的结果不要求给出 标准指派问题的数学模型 1 指派第 i 个
