运筹学期末复习提纲

《运筹学期末复习提纲》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、运筹学复习1线性规划线性规划问题及其数学模型图解法单纯形法原理单纯形法计算步骤单纯形法的进一步讨论线性规划的概念目标能表成求MAX或MIN达到目标有多种方案实现目标有一定条件目标和条件都能用线性函数表示例如，对于线性规划问题其系数矩阵为则下面两个矩阵都是该线性规划问题的基。和还能找出其它基吗？基解：令非基变量等于0的解。基可行解：基解+可行解例如，对于上面的线性规划问题，如果取x1，x2为基变量，则令非基变量x3，x4为零，约束方程组为解之得。故我们得到基解注意到这个基解还是一个可行解。是否所有的基解都是基可行解？（选x1,x3作为基变量）解的概念

2、解2.3(1)x1x2x3x4x5z是否可行12620036y24306027y34600-642n460-612018n5094-6045n60640630y740012612y800412180y(2)线性规划要注意的几点图解法对只包含两个决策变量的线性规划问题，可以用图解法来求解。图解法顾名思义就是通过作图来求解的方法，它简单直观、并有助于说明一般线性规划问题求解的基本原理。线性规划的标准形式它具有如下四个特征：目标函数求max；约束方程符号取“=”；bi非负；所有决策变量xj非负。线性规划解的存在性线性规划问题的所有可行解构成的集合是凸集，

3、也可能为无限集。他们有有限个顶点，线性规划问题的每个基可行解对应可行域一个顶点，反之亦然。若线性规划问题有最优解，必在某顶点达到。大M法将人工变量在目标函数中反映出来得到如下形式的线性规划：因此最优解为最优目标函数值为需要说明的是，如果在用大M法求解线性规划问题时，最终表的基变量中还含有人工变量，那么这个最终表并没有给出原来问题的基可行解，从而没有给出原来的线性规划问题最优解。这时原来线性规划问题为无可行解。用EXCEL执行该计算过程故原来问题的最优解为最优目标函数值这一结果与大M法得到的结果是一致的。无可行解的判别：在用大M法求解线性规划问题时，

4、若最终单纯形表的基变量中含人工变量；或用两阶段法求解时，第一阶段最终表的基变量中含非零的人工变量，也就是第一阶段最优目标函数值不等于零，则线性规划问题无可行解。2.8单纯形法小结2线性规划对偶理论及其应用规范形式的线性规划与对偶规划问题原问题（LP）对偶问题（DLP）对偶规划的基本性质3.2.2弱对偶性定理：如果X、Y分别是原问题和对偶问题的一个可行解，则其对应的原问题的目标函数值不大于对偶问题的目标函数值，也即证明：因为X、Y分别是原问题（3.1）与对偶问题（3.2）的可行解，故：所以推论一：原问题任一可行解的目标函数值是其对偶问题目标函数值的下

5、界；反之对偶问题任一可行解的目标函数值是起原问题目标函数值的上界。推论二：如果原问题存在无界解，则对偶问题一定无可行解；反之，如果对偶问题存在无界解，原问题也一定不存在可行解。注意，该推论的逆反定理并不成立。注意，该推论的逆反定理并不成立。推论三：如果原问题无解，且对偶问题有可行解，则对偶问题具有无解解，；反之，如果对偶问题无解，且原问题有可行解，则对偶问题具有无界解。最优性定理互补松弛定理约束方程也分为两种情况：，约束条件比较松；，约束条件比较紧；yi>=0,分为两种情况：yi>0，约束条件比较松；yi=0，约束条件比较紧；互补松弛定理的解释变量

6、同其对偶问题的约束方程之间至多只能够有一个取松弛的情况，当其中一个取松弛的情况时，另外一个比较紧，即取严格等号。例已知下面的LP1和LP2为一组对偶规划，且已知LP1的最优解为X=（1.5，1）’。试运用互补松弛定理求出对偶问题的最优解Y。生产计划问题（LP1）资源定价问题（LP2）解：由X=（1.5，1）’得联立求解得：解：由X=（1.5，1）’得联立求解得：解：由X=（1.5，1）’得联立求解得：灵敏度分析约束条件右端向量b的变化3目标规划目标规划基本概念（1）偏差变量d+：正偏差变量，表示决策值超出目标值的部分d-：负偏差变量，表示决策值未达

7、到目标值的部分按定义有：d+≥0，d-≥0，d+•d-=0（2）绝对约束和目标约束绝对约束（硬约束）：必须严格满足的约束条件目标约束（软约束）：目标规划特有（3）优先因子（P）和权系数（W）优先因子用P1，P2，…，Pl表示，规定Pl>>Pl+1，表示Pl比Pl+1有更大的优先权。（4）目标函数决策值=目标值min{f(d++d-)}决策值<目标值min{f(d+)}决策值>目标值min{f(d-)}目标规划模型的建立例4.1某企业计划生产甲、乙两种产品。已知有关数据见表4-1。问如何安排生产使获得的总利润最大？项目甲乙拥有量原材料（kg）2111

8、设备（台时)1210利润（元/件）810表4-1设x1、x2分别表示计划生产产品甲、乙的产量，它的数学模型为：它的最优解为