2016运筹学总复习综述.ppt

第1章 绪论 用科学方法分析管理及工程问题，为决策提供依据。 目标：在企业经营内外环境的限制下，实现资源效用最大。 1、线性规划的标准形式 目标函数： 约束条件： 2、非标准形式的标准化方法 1、min Z=CX — max Z= -CX 2、约束条件为“≤” 转换为“=”方法： 在s.t.中左端加上一个“松弛变量”，使“≤”变为“=”。同时，在目标函数中，令松弛变量的目标系数为0。 3、约束条件为“≥”转换为“=”方法： 在s.t.中左端减去一个“剩余变量”，使“≥”变为“=”。同时，在目标函数中，令剩余变量的目标系数为0。 4、单纯形法的计算步骤 （1）将问题化为标准型； （2）求出线性规划的初始基可行解，列出初始单纯形表； （3）进行最优性检验： 如果表中所有检验数 ，则表中的基可行解就是问题的最优解，计算停止。否则继续下一步。 用换入变量xk替换基变量中的换出变量，得到一个新的基。对应新的基可以找出一个新的基可行解，并相应地可以画出一个新的单纯形表。 （5）重复（3）、（4）步直到计算结束为止。 第4章 运输问题 1、运输问题的数学模型的建立； 2、产销平衡下运输问题的基变量个数与产地、销地之间的关系（m+n-1），即（m+n-1）个独立约束方程； 3、约束方程都是等式。 1、最小元素法的精髓（就近供应，从单位运价表中最小的运价开始确定供销关系，依次类推，只到给出全部方案为止）； 2、Vogel法的核心（最大差额处，优先按最小运价进行调整）； 3、位势法求检验数、闭回路法进行调整； 4、产销不平衡时的调整方法。 第5章 目标规划 1、目标规划的组成与特点； 2、目标规划的模型（如何建立目标函数、目标约束建立等）； 3、目标函数中偏差变量的取舍（利润型目标、成本型目标和合同型目标中偏差变量的取舍）； 4、掌握目标规划应用方法（不用求解）。 分枝定界法：将原整数规划问题分枝—分为两个子规划,再解子规划的伴随规划……通过求解一系列子规划的伴随规划及不断地定界。最后得到原整数规划问题的整数最优解。 匈牙利算法。 算法主要依据以下事实：如果将系数矩阵C=（Cij）中一行（或一列）的每一元素都加上或减去同一个数，得到一个新矩阵B=（bij），则以C和B为系数矩阵的指派问题具有相同的最优指派。 系数矩阵中独立 0 元素的最多个数等于能覆盖所有 0 元素的最少直线数。 第7章 动态规划 1、熟悉关于动态规划的一些基本概念； 2、状态转移方程的建立方法； 3、动态规划的解题步骤； 4、动态规划的求解方法（确定型、逆序法，P169例7-3之类）； 练习题 单项选择题 1、最早运用运筹学理论的是（ ） A 二次世界大战期间，英国军事部门将运筹学运用到军事战略部署； B 美国最早将运筹学运用到农业和人口规划问题上； C 二次世界大战期间，英国政府将运筹学运用到政府制定计划； D 50年代，运筹学运用到研究人口，能源，粮食，第三世界经济发展等问题上。 2、在产销平衡运输问题中，设产地为个，销地为个，那么基可行解中非零变量的个数（ ） A. 不能大于(m+n-1)； B. 不能小于(m+n-1)； C. 等于(m+n-1)； D. 不确定。 3、在求解运输问题的过程中运用到下列哪些方法（ ） A 最小元素法 B 位势法 C 闭回路法 D 伏格尔法 E 以上都是 10.产销平衡的运输问题解的情况有四种：无可行解；无界解；唯一最优解；无穷多最优解。 填空题 1、用大M法求解Max型线性规划时，人工变量在目标中的系数均为 ,若最优解的 中含有人工变量，则原问题无可行解。 2、若某种资源的影子价格为零，则表明该种资源 （应该或不应该）被买进；又当资源的影子价格不为零时，说明该种资源消耗 （完毕或剩余） 3、线性规划原问题中的变量个数与其对偶问题中的 个数相等。因此，当原问题增加一个变量时，对偶问题就增加一个 ，从而对偶可行域将可能变 (小还是大)。 建立线性规划模型（利润最大或者成本最小） 线性规划化为标准型 写出问题的对偶规划 第三阶段：k=3，（求解x3） 从(LP)的最优解中，任选一个不为整数的分量xr,,将最优单纯形表中该行的系数arj′和 br′分解为整数部分和非负真分数部分之和， 并以该行为源行，按作割平面方程。 将所得的割平面方程，作为一个新的约束条件置于最优单纯形表中同时增加一个单位列向量），用对偶单纯形法求出新的最优解。 割平面法 指