运筹学复习..docx

运筹学B复习大纲知识点：知道线性规划问题的数学模型线性规划问题的标准型知道线性规划问题解的几何意义，知道最优解，可行解，最优值等概念以及他们的一些基本性质，会用图解法求解会用单纯形法求解线性规划问题会建立生产计划问题、配料问题等数学模型会写出线性规划问题的对偶问题知道对偶理论掌握灵敏度分析的几个问题，会对软件计算结果进行灵敏度分析会建立运输问题的数学模型10、掌握运输问题的表上作业法，会用西北角法或者最小元素法建立初始调运方案，会用闭回路法或者位势法进行检验并调整，求最优解11、了解产销不平衡问题的解决思路12、掌握整数规划问题的建模方法，掌握分支定界法，0-1整数规划问题的解法，掌握指派问题的建模方法及匈牙利法13、掌握图与网络的基本概念14、会求最小生成树、最短路问题的Dijkstra算法、最大流算法15、了解动态规划问题的基本概念和基本思路复习题（二）1、某公司生产甲、乙两种产品，生产所需原材料、工时和零件等有关数据如下：甲 乙可用量原材料（吨/件）工时（工时/件）零件（套/件）2252.513000吨4000工时500套产品利润（元/件） 4 3建立使利润最大的生产计划的数学模型，不求解。2、一家工厂制造甲、乙、丙三种产品，需要三种资源——技术服务、劳动力和行政管理。每种产品的资源消耗量、单位产品销售后所能获得的利润值以及这三种资源的储备量如下表所示：　技术服务劳动力行政管理单位利润甲110210乙1426丙1564资源储备量100600300　建立使得该厂能获得最大利润的生产计划的线性规划模型，不求解。3、消费者购买某一时期需要的营养物（如大米、猪肉、牛奶等），希望获得其中的营养成分（如：蛋白质、脂肪、维生素等）。设市面上现有这3种营养物，其分别含有各种营养成分数量，以及各营养物价格和根据医生建议消费者这段时间至少需要的各种营养成分的数量（单位都略去）见下表。甲乙丙至少需要的营养成分数量A462080B11265C10370格252045问：消费者怎么购买营养物，才能既获得必要的营养成分，而花钱最少？只建立模型，不用计算。4、某公司生产的产品A，B，C和D都要经过下列工序：刨、立铣、钻孔和装配。已知每单位产品所需工时及本月四道工序可用生产时间如下表所示：刨立铣钻孔装配A0.52.00.53.0B1.01.0.0.51.0.C1.01.01.02.0D0.51.01.03.0可用生产时间（小时）1800280030006000又知四种产品对利润贡献及本月最少销售需要单位如下：产品最少销售需要单位元/单位A1002B6003C5001D4004问该公司该如何安排生产使利润收入为最大？（只需建立模型）解：设生产四种产品分别x1,x2,x3,x4单位则应满足的目标函数为：max z=2 x1+3 x2+ x3+ x4满足的约束条件为：5、将下列线性规划模型化为标准形式6、用图解法求解下面线性规划（1）min z =－3x1+2x2(2) min z =2x1+x2（3）7、用单纯型法求解下面线性规划问题的解（1）max z= 3x1+3x2+4x3s.t.（2）8、写出下列模型的对偶模型若其对偶问题的最优解是，求原问题的最优解及最优值。9、已知线性规划的标准形式为其最优单纯形表如下Cj－12100CBXBbx1x2x3x4x520x2x56101310111101-Z-12-30-1-20问：(1)当C1由－1变为4时，求新问题的最优解(2)讨论C2在什么范围内变化时，原有的最优解仍是最优解10、安排一个使总运费最低的运输计划，并求出最低运费。运销地价 产产 地A1A2A3A4产量161110950210761470312881130需求求：先用最小元素法求出一个初始方案，再用闭回路法，求检验数。如果不是最优，改进为最优。11、下列是将产品从三个产地运往四个销地的运输费用表。运销价 地产产 地A1A2A3A4产量19129650273776036591150需求求：⑴用最小费用法建立运输计划的初始方案；⑵用位势法做最优解检验；⑶求最优解和最优方案的运费。12、求解指派问题，并求出最小费用。Min z =（cij）4×4=13、有甲、乙、丙、丁四个人，要分别指派他们完成A、B、C、D四项不同的工作，每人做各项工作所消耗的时间如下表所示：　ABCD甲21097乙154148415139问：应该如何指派，才能使总的消耗时间为最少？14、用隐枚举法求解规模0－1规划问题15、求下图中从v1到v3短路。16、电信公司要在15个城市之间铺设光缆，这些城市的位置及相互之间的铺设光缆的费用如下图所示。试求出一个连