[运筹学整理.docVIP

运筹学知识点整理 1、运筹学研究的基本特点及步骤? 基本特点：多学科交叉、模型化（定量）、最优化 运筹学的工作步骤： 1、提出与表达问题。2、建立模型。3、求解。 4、解的检验。 5、解的分析。 6、解的实施。 2、线性规划问题的特点? 目标明确：要解决的问题的目标可以用数值 指标反映。Z=?(x1 … xn) 线性式，求Z极大或极小 多种方案：对于要实现的目标有多种方案可 选择 资源有限：有影响决策的若干约束条件 线性关系：约束条件及目标函数均保持线性关系 3、线性规划的数学模型共同特征及标准形式? 共同特征：决策变量：向量决策人要考虑和控制的因素非负 约束条件：线性等式或不等式 目标函数：Z=?(x1 … xn) 线性式，求Z极大或极小 标准形式 A一般型 其中bi =0 (i=1,2,…,m) B矩阵型 C向量型 4、线性规划问题解的概念：可行解、最优解、基本解、基本可行解? 可行解：满足约束条件的变量值 最优解：使目标函数取得最优值的可行解 基本解：对应于基B，X=为AX=b的一个解。 基本可行解：基B，基本解X=若，称基B为可行基。 5、线性规划问题解的性质？ A、课本上（几何意义） 凸集 凸组合 极点 B、PPT上 （1）若(LP)问题有可行解，则可行解集(可行域)是凸集(可能有界，也可能无界) 。 （2）基本可行解的个数是有限的，对应于极点的个数是有限的。 （3） (LP)问题的基本可行解可行域的极点。 （4） 若(LP)问题有最优解，必可以在基本可行解(极点)达到。 6、图解法及线性规划解结果的几种形式?PPT2-3 有解：唯一最优解、无穷多解；无解：无有限最优解、无可行解 单纯形算法的基本思想，单纯形的计算步骤，如何在单纯形表中去判断问题具有唯一的最优解、无穷多最优解、无界解？ 根据问题的标准型,从可行域中某个基本可行解(顶点)开始，转换到另一个基本可行解(顶点)，并使得每次的转换，目标函数值均有所改善，最终达到最大值时就得到最优解。 （4）确定换入变量（5）换基迭代 唯一最优解 无穷多最优解 无可行解 7、如果线性规划的标准形式变化为目标函数极小minZ，则单纯形计算时如何判断已得到最优解？PPT2-5P55 检验数全部大于或等于0 8、在确定初始可行基时，什么情况下要在约束条件中增添人工变量？ （重找不到初始可行基来回答） 9、在两阶段法中，如何根据第一阶段的计算结果来判断第二阶段的计算是否需要继续进行？PPT2-5,p66 第一阶段：解辅助问题 当进行到最优表时，①、若?w =0, 则得到原问题的一个基本可行解，转入第2阶段。 ②、若?w 0, 则判定原问题无可行解。 10、举例说明生产和生活中应用线性规划方面，并对如何应用进行必要的描述。PPT2-1，P1,7 市场营销(广告预算和媒介选择，竞争性定价，新产品开发，制定销售计划) 生产计划制定(合理下料，配料，“生产计划、库存、劳力综合”) 库存管理(合理物资库存量，停车场大小，设备容量) 运输问题 财政、会计(预算，贷款，成本分析，投资，证券管理) 人事(人员分配，人才评价，工资和奖金的确定) 设备管理(维修计划，设备更新) 城市管理(供水，污水管理，服务系统设计、运用) 11、根据线性规划的原问题写出对偶问题？PPT3-1 两模型的对应关系： （1）两问题的系数矩阵互为转置 （2）一个问题的变量个数等于另一个问题的约束条件个数 （3）一个问题的右端常数是另一个问题的目标函数的系数 （4）一个问题的目标函数为极大化，约束条件为“=?”类型，另一个问题的目标为极小化，约束条件为“?=”类型 12、对偶问题解的性质？PPT3-1，P28。课本P40 1)、对偶问题的对偶问题是原问题。 2)、弱对偶定理 3）最优性 4）无界性 5）对偶定理 6)互补松弛性 13、对偶问题的最优解？ 原问题的单纯形表中，原问题的松弛变量的检验数对应于对偶问题的决策变量，符号相反 原问题的决策变量的检验数对应于对偶问题的松弛变量，符号相反 例: 14、对偶单纯形法的运算步骤？p44较为易懂 思路：(max型) 单纯形法： ①找基B，满足B-1b30，但 C - CBB-1 A不全￡ 0，（即检验数）。 ②迭代→保持B-1b30，使C -CBB-1 A￡ 0，即CBB-1 A3 C 对偶单纯形法：①找基B，满足C - CBB-1 A￡ 0，但B-1b不全30 ②迭代→保持C -CBB-1 A￡ 0，使B-1b30 对偶单纯形法基本步骤 max型(min型) (1)、作初始表，要求全部 ￡ 0 (30) (2)、判定：全30，停