运筹学规划复习.doc

运筹学线性规划问题复习补充一、 简答题1. 试述运筹学模型应用的基本流程。2. 简述运筹学学科的性质和特点。1.运筹学已被广泛应用于工商企业、军事部门、民政事业等研究组织内的统筹协调问题， 2.运筹学既对各种经营进行创造性的科学研究，它具有很强的实践性，最终应能向决策者提供建设性意见，并应收到实效；3.它以整体最优为目标，从系统的观点出发，力图以整个系统最佳的方式来解决该系统各部门之间的利害冲突。3. 试述线性规划问题以及单纯形法求解的几何意义。4. 如果max 型线性规划问题有无界解，则其对偶问题无可行解， 为什么？弱对偶性5. 试述影子价格和一般市场价格的区别。6. 简述单纯形法出现退化的现象, 原因和措施。7. 目标规划模型有什么特点?相同点：都有决策变量、目标函数和约束条件线性规划模型存在的局限性：（不同点）1）要求问题的解必须满足全部约束条件，实际问题中并非所有约束都需要严格满足。2）只能处理单目标的优化问题。实际问题中，目标和约束可以相互转化。3）线性规划中各个约束条件都处于同等重要地位，但现实问题中，各目标的重要性即有层次上的差别，同一层次中又可以有权重上的区分。4）线性规划寻求最优解，但很多实际问题中只需找出满意解就可以。8. 整数规划问题分支定界法的直观解释和基本过程是什么? 分支终止条件是什么?二、 建模题1 运输工具的配载问题。有一辆运输卡车，载重2.5吨，容积18米3，用来装载如下两种货物：箱装件0.4米3，125公斤；包装件1.5米3，125公斤。请问：如何装，卡车所装物件个数最多？2 从甲、乙、丙三种矿石中提炼A、B两种金属，每种矿石的金属含量、所需金属总量以及矿石价格如下表所示，欲决定每种矿石各用多少吨可以使总费用最省，试建立相应的线性规划模型。每吨矿石金属含量 (克/吨)所需金属总量甲乙丙A3002006048 公斤B20024032056 公斤每吨矿石价格(元吨)6048503三、 证明题1. 证明线性规划问题的可行域是凸集。所有的线性规划约束都可以化成：AX=b假设可行域为S,从中任意取两个点X1,X2,则AX1=b,AX2=b则A(a*X1+(1-a)*X2)=a*AX1+(1-a)*AX2=a*b+(1-a)*b=b 其中0=a=1所以A(a*X1+(1-a)*X2)=b所以a*X1+(1-a)*X2属于S据凸集的定义可知：S凸集。即线性规划问题的可靠域一定是凸集。2. 线性规划问题 设, 为问题的两个最优解，证明也是其最优解， 即该问题有无穷多最优解。线性规划有解，解集必为凸集，x1，x2是两顶点，两点连线上任何一点都可以表成两点的凸组合，既然x1和x2都是最优解，哪么他们的凸组合也必是最优解3线性规划问题 设为问题的最优解， 若目标函数中C用C* 代替后， 问题的最优解变为X*， 求证：.将不等式化开为C*(X*-X)-C(X*-X),因为当等于C*时，最优解为X*,所以X*-X定大于0，而当等于C时，最优解为X，所以X*-X定小于0，所以整个式子大于0 ，什么时候能取到0，应该是当X=0时吧！四、 计算题1 考虑线性规划问题试讨论在什么取值范围时, 该问题:(1) 有唯一最优解;(2) 有无穷多最优解(3) 为无界解。2 求线性规划问题的所有基解， 并指出哪些是基可行解。3 请分别给出下列线性规划问题的标准型和对偶问题。 4 应用对偶理论证明下述线性规划问题无最优解。5 已知线性规划的最优单纯形表如表下，求原线性规划矩阵C、A、及b，最优基B及 Cjc1c2c3c4c5bCBXBx1x2x3x4x5C1x11041/61/156C2x201301/52j00123总体要求: (1) 牢固掌握课本和作业的基本知识点(2) 理解所学习模型所针对的问题类型(3) 能够对比较简单的问题建立模型