运筹学期末复习.doc

运筹学期末复习第二章一、标准化特点：目标最大化；约束为等式；决策变量均非负；右端项非负。二、松弛量：在线性规划中，一个“”约束条件中没有使用的资源或能力； 剩余量：在线性规划中，对于“”约束条件中，可以增加一些代表最低约束的超过量。三、对偶价格：在约束条件常数项中增加一个单位而使最优目标函数值得到改进数量。四、当约束条件常数项增加一个单位时，有以下三种情况： 、如果对偶价格大于零，则其最优目标函数值得到改进，即求最大值时，最优目标函数值变得更大；求其最小值时，最优目标函数值变得更小。 、如果对偶价格小于零，则其最优目标函数值变坏，即求最大值，最优目标函数值变小了；求其最小值时，最优目标函数值变大了。 、如果对偶价格等于零，则其最优目标函数值不变。第三章一、百分之一百法则：对于所有变化的约束条件中的常数项，当其所有允许增加百分比和允许减少百分比之和不超过百分之一百时，其对偶价格不变。即：100%时，其对偶价格不变；100%时，其对偶价格变化。二、在使用百分之一百法则进行灵敏度分析时，要注意一下三点：1、当语序增加量（减少量）为无穷大时，则对于任一个增加量（减少量），其允许增加（减少）百分比都看成零。2、百分之一百法则是判断最优解或对偶价格是否发生变化的充分条件，但不是必要条件。3、百分之一百法则不能应用于目标函数决策变量系数和约束条件中常数项同时变化的情况，在这种情况下，只有重新求解。三、影子价格：当约束条件中的常数项增加一个单位时，最优目标函数值增加的数量称之为影子价格。对照对偶价格定义：当约束条件中常数项增加一个单位时最优目标函数值改进的数量，可知当球目标函数最大值时，增加的数量就是改进的数量，所以影子价格等于对偶价格；而当目标函数的最小值时，改进的数量应该是减少的数量，所以影子价格即位负的对偶价格。第八章在整数规划中，如果所有的变量为非负，则称之为纯整数规划问题；如果只有一部分变量为非负整数，则称之为混合整数规划问题。在整数规划和总，如果变量的取值只限于0和1，这样的变量我们称之为0-1变量。在纯正式规划和混合整数规划问题中，常常会有一些变量时0，1变量，如果所有变量都是0，1变量，则称之为0-1规划。第十四章排队系统的符号表示:一个排队系统的特征可以用五个参数表示，形式为：ABCDE其中A 顾客到达的概率分布；B 服务时间的概率分布；C 服务台个数，取正整数；D 排队系统的最大容量，可取正整数或；E 顾客源的最大容量，可取正整数或。 例如 M / M / 1 / / 表示顾客到达过程服从泊松分布，服务时间服从负指数分布，一个服务台，排队的长度无限制和顾客的来源无限制。M / M / 1 / / 单位时间顾客平均到达数 l，单位平均服务顾客数 m (l m)数量指标公式: 1. 系统中无顾客的概率 P0 =1- l /m 2. 平均排队的顾客数 Lq =l2/m(m - l) 3. 系统中的平均顾客数 Ls = Lq + l /m 4. 顾客花在排队上的平均等待时间 Wq = Lq / l 5. 顾客在系统中的平均逗留时间 Ws = Wq+ 1/m 6. 顾客得不到及时服务必须排队等待的概率 Pw =l /m 7. 系统中恰好有 n 个顾客的概率 Pn =(l /m)n P0计算题：1、将以下线性规划问题化成标准形式，并用图解法求解。约束条件：2、用双标号法求出下图中v1到v7的最短路。3、某糖果厂用原料A、B、C加工成三种不同牌号的糖果甲、乙、丙。已知各种牌号糖果中A、B、C含量，原料成本，各种原料的每月限制用量，三种牌号糖果的单位加工费及售价如下表所示。问该厂每月生产这三种牌号糖果各多少公斤，使该厂获利最大。试建立这个问题的线性规划的数学模型。甲乙丙原料成本（元/kg）每月限制用量（kg）ABC 60%20%30%50%60%21.51200025001200加工费（元/kg)0.50.40.3售价（元/kg）3.42.852.254、某昼夜服务的公交线路每天各时间段内所需司机和乘务人员数如下设司机和乘务人员分别在各时间段一开始时上班，并连续工作八小时，问该公交线路怎样安排司机和乘务人员，既能满足工作需要，又配备最少司机和乘务人员?5、某公司在今后四个月内需租用仓库堆放物资。已知各个月所需的仓库面积数字如下所示：月份1234所需仓库面积（百平方米）18201612仓库的租借费用，当租借期限越长时，享受的折扣优惠越大，具体数字如下：合同租借期限1个月2个月3个月4个月合同期限内每百平方米仓库面积的租借费用2600440061007500租借仓库的合同每月初都可办理，每份合同具体规定租用面积数和期限。因此该厂可根据需要在任何一个月初办理租借合同，且每次办理，可签一份，也可同时签定若干份租用面积和租借期不同的合同。请建立求解出一个所付租借费为最小的租借方案的线性规划模型。5、某地区有三个化肥厂，除供应外地区需要外，估计每年可供应本地区的数字为：化肥厂 A 7 万吨， B 8 万吨， C 3 万吨。有四个产粮区需要该种化肥，需要量为：甲地区6 万吨，乙地区6 万吨，丙地区8 万吨，丁地区5 万吨，其中甲地区需要量应全部满足，乙和丙地区只要求不超过需求量，丁地区至少供应4万吨。已知从各化肥厂到各产粮区的每吨化肥的运价如下表所示（单位：元 / 吨）： 产粮区 化肥厂 甲 乙 丙 丁 A 5 8 7 3 B 4 9 10 7 C 8 4 2 9 根据上述资料指定一个使总的运费最小的化肥调拨方案。 （画出产销平衡表，写出此问题的数学模型）6、需要分配 5 人去做 5 项工作，每人做各项工作的能力评分见下表。应如何分派，才能使总的得分最大？ （列出此指派问题的数学模型） B1 B2 B3 B4 B5 A1 1.3 0.8 0 0 1.0 A2 0 1.2 1.3 1.3 0 A3 1.0 0 0 1.2 0 A4 0 1.05 0 0.2 1.4 A5 1.0 0.9 0.6 0 1.1 7、求出下图的最小生成树。8、求出下图所示各网络中从V1到V8的最大流量，图中弧旁数字为容量Cij。9、某工厂生产某种商品，其生产率与需求率都为常量，年生产率为50000件。年需求率为30000件；生产准备费用每次为1000元，每件产品的成本为130元，而每年的存储成本率为21%，假设该公司每年工作日为250天，要组织一次生产的准备时间为5天。请用不允许缺货的经济生产批量的模型，求出：（1）最优经济生产批量；（2）再订货点（当商品存储量降为多少时，应该再生产）；（3）两次生产间隔时间；（4）生产和存储的全年总成本。10、某工程队承担一座桥梁的施工任务。由于施工地区夏季多雨，需停工三个月，在停工期间该工程队可将施工机械搬走或留在原处。如搬走，需搬运费2600元。如留原处，一种方案是花400