运筹学复习提纲.pptx

第一章线性规划与单纯形法基可行解的结构：非零元素的个数不超过约束矩阵的秩（行数）1、各种解的定义（基解、基可行解、最优解）2、单纯形法（以最大化目标函数为例）①掌握单纯表上各个元素的含义（以练习1.8为例说明）②检验数的计算；③换入变量的确定：检验数大于零的变量作为换入变量都可以使目标值增加（选最大的，目标增加的最快）

④换出变量的确定⑤掌握线性规划各种解的判别条件（唯一解、无穷多解、无界解，退化解）（以练习1.9为例说明）⑥B-的确定（在灵敏度分析时也要用到）

第二章对偶理论和灵敏度分析1、线性规划对偶性质及应用①利用对偶性质求线性规划的解，（分两步）要正确的写出线性规划的对偶规划（以对称形式为基准）利用互补松弛条件求出线性规划的解（例2.9，练习2.2）②原始问题与对偶问题解之间的关系

2、灵敏度分析（与单纯形方法、对偶单纯形方法接在一起）(以练习2.9,2.10为例说明)(1)bi的变化:①给出bi的变化范围，使最优基不变：B-b≥0②若最优基变了（至少有一个bi0），要用对偶单纯形方法求出新的最优解给出Cj的变化范围，使最优解不变-------所有检验数不大于零②若最优解变了（至少有一个检验数大于零），要用单纯形方法求出新的最优解(2)Cj的变化

补充例题：已知线性规划的最终单纯形表格为：,

cj2-11000cBxBbx1x2x3x4x5x60x4100011-1-22x115101/201/21/2-1x2501-3/20-1/21/2σj00-3/20-3/2-1/2确定x2的系数c2的变化范围，使原最优解保持最优；-2≤c2≤0若c2=-4，求新的最优计划。X*=(10,0,0),Z*=20b3在什么范围内变化，最优基不变？10≤b3≤25b3=30时，新的最优方案是什么？X*=(17.5,7.5,0),Z*=27.5

第三章运输问题1、运输问题是特殊的线性规划：mn个变量，m+n个约束，独立约束为m+n-1个，与一般线性规划的区别：一定有最优解（唯一或无穷多解）2、表上作业法（实质上是单纯形法）找出初始基可行解（最小元素法、伏格尔方法）②计算非基变量的检验数（闭回路方法、位势法\对偶变量法）③解的调整（闭回路方法）（注：运输问题是最小化问题，最优解的判别是所有检验数都大于等于零时得最优解）以往年考题为例

假设有两个生产地A1,A2和三个销售地B1,B2,B3,有关数据如图所示，假设A1,A2处允许物资存储地区加工厂B1B2B3供应量存储费加工厂工厂要出运输问题的数学模型；用最小元素法找出初始基本可行解;求出初始基本可行解的检验数，找出闭回路，确定调整量；求出最优运输方案和最小总运费。F=1050

第四章目标规划1、目标规划数学模型①正、负偏差变量均是非负的②目标规划中可以没有绝对约束，但必须有目标约束2、目标规划的图解法①每一步要正确分清d+0,d-=0和d+=0,d-0的区域②注：在考虑低级别目标时，不能破坏已经满足的高级别目标，这是目标规划的基本原则。但是，也不能因此而以为，当高级别目标不能满足时，其后的低级别目标也一定不能被满足。

第五章整数规划1、分支定界法求解整数规划①掌握分支定界法的步骤，特别是继续分支的条件及修改上下界的时机2、匈牙利方法（指派问题）人数和任务相等、目标是最小化步骤a.效率矩阵的行、列变化b.画出最少直线覆盖零元素c.零元素的调整指派问题扩展a.人数和任务不相等（例5.8）b.目标函数是最大化（例5.9）

任务人员EJGR甲215134乙1015144丙149913丁98117有一份说明书，需译成英、日、德、俄四种文字。现有甲、乙、丙、丁四个人，他们将说明书译成不同文字所需的时间如下表。问应指派哪个人完成哪项工作，使所需的总时间最少？例题

即：甲→英乙→俄丙→德丁→日最少的耗时数Z=2+4+9+8=23。

第六章图与网络规划1、图的节本概念2、最小支撑树的求解（以练习6.2为例）破圈法避圈法3、最短路的求法（以练习6.3为例）指定点到定点的最短路-------狄克斯屈拉(Dijkstra)算法任意两