下载文档原格式
运筹学（Operational Research）复习资料第一章绪论一、名词解释1.运筹学：运筹学是应用分析、试验、量化的方法，对经济管理系统中的人力、物力、财力等资源进行统筹安排，为决策者提供有依据的最优方案，以实现最有效的管理。
二、选择题1.运筹学的主要分支包括（ABDE ）A图论B线性规划C非线性规划D整数规划E目标规划2. 最早运用运筹学理论的是（ A ）A . 二次世界大战期间，英国军事部门将运筹学运用到军事战略部署B . 美国最早将运筹学运用到农业和人口规划问题上C . 二次世界大战期间，英国政府将运筹学运用到政府制定计划D . 50年代，运筹学运用到研究人口，能源，粮食，第三世界经济发展等问题上第二章线性规划的图解法一、选择题/填空题1.线性规划标准式的特点：（1）目标函数最大化（2）约束条件为等式（3 决策变量为非负（4 ) 右端常数项为非负2. 在一定范围内，约束条件右边常数项增加一个单位：（1）如果对偶价格大于0，则其最优目标函数值得到改进，即求最大值时，最优目标函数值变得更大，求最小值时最优目标函数值变得更小。
（2）如果对偶价格小于0，则其最优目标函数值变坏，即求最大值时，最优目标函数值变小了；求最小值时，最优目标函数值变大了。
（3）如果对偶价格等于0，则其最优目标函数值不变。
3.LP模型（线性规划模型）三要素：（1）决策变量（2）约束条件（3）目标函数4. 数学模型中，“s·t”表示约束条件。
5. 将线性规划模型化成标准形式时，“≤”的约束条件要在不等式左端加上松弛变量。
6. 将线性规划模型化成标准形式时，“≥”的约束条件要在不等式左端减去剩余变量。
7．下列图形中阴影部分构成的集合是凸集的是A【解析】：如何判断是凸集？凸集：两点之间连线在图内凹集：两点之间连线在图外8. 线性规划问题有可行解且凸多边形无界，这时CA没有无界解 B 没有可行解 C 有无界解 D 有有限最优解9. 对于线性规划问题，下列说法正确的是（ D ）A. 线性规划问题可能没有可行解B. 在图解法上，线性规划问题的可行解区域都是“凸”区域C. 线性规划问题如有最优解，则最优解可在可行解区域顶点上到达D. 上述说法都正确第三章线性规划问题的计算机求解一、名词解释1.相差值：相应的决策变量的目标系数需要改进的数量，使得决策变量为正值。
《运筹学》重要知识点解析和例题分析第六部分一．图的基本概念 定义一个图G 是指一个二元组(V(G),E(G)).即图是由点及点之间的联线所组成。
其中: 1）图中的点称为图的顶点(vertex).记为：v2）图中的连线称为图的边(edge).记为：,i j e v v ⎡⎤=⎣⎦.,i j v v 是边 e 的端点。
3）图中带箭头的连线称为图的弧(arc).记为：(),i j a v v =.,i j v v 是弧 a 的端点。
—— 要研究某些对象间的二元关系时.就可以借助于图进行研究 分类▪ 无向图：点集V 和边集E 构成的图称为无向图(undirected graph).记为： G(V.E)—— 若这种二元关系是对称的.则可以用无向图进行研究▪ 有向图：点集V 和弧集A 构成的图称为有向图(directed graph) .记为：D(V.A)—— 若这种二元关系是非对称的.则可以用有向图进行研究▪ 有限图: 若一个图的顶点集和边集都是有限集.则称为有限图.只有一个顶点的图称为平凡图.其他的所有图都称为非平凡图.图的特点：1 图反映对象之间关系的一种工具.与几何图形不同。
2 图中任何两条边只可能在顶点交叉.在别的地方是立体交叉.不是图的顶点。
3 图的连线不用按比例画.线段不代表真正的长度.点和线的位置有任意性。
4 图的表示不唯一。
如：以下两个图都可以描述“七桥问题”。
点(vertex)的概念1 端点：若e =[u.v] ∈E.则称u.v 是 e 的端点。
2 点的次：以点 v 为端点的边的个数称为点 v 的次.记为：()d v 。
在无向图G 中.与顶点v 关联的边的数目(环算两次),称为顶点v 的度或次数.记为()d v 或 dG(v).在有向图中.从顶点v 引出的边的数目称为顶点v 的出度.记为d+(v).从顶点v 引入的边的数目称为v 的入度.记为d -(v). 称()d v = d+(v)+d -(v)为顶点v 的度或次数． 3 奇点：次为奇数的点。
《运筹学基础》名词解释运筹学：缩写OR，是利用计划方法和有关多学科的要求。
把复杂功能关系。
表示成数学模型，其目的是通过定量分析为决策和揭露新问题提供数量根据。
定性决策：基本上根据决策人员的主观经验或感受到的感觉或只是而制定的决策。
定量决策：借助于某些正规的计量方法而作出的决策。
混合性决策：必须运用定性和定量两种方法才能制定的决策。
预测：是对未来的不确定的事物进行估计或判断。
专家小组法：是在介绍咨询的专家之间组成一个小组，面对面的进行讨论与磋商，最后对需要预测的课题得出比较一致的意见指数平滑预测法：是定量与定性方法相结合的一种预测方法决策：从狭义方面来说，决策可以解释为对一些可供选择的方案作出抉择。
广义的决策过程包括4个程序：明确决策项目的目的，寻求可行的方案，在诸可行方案中进行抉择，对选定的决策方案经过实施后的结果进行总结评价常规性决策：它是例行的，重复性的决策。
做这类决策的个人或组织。
又要需要他们决策的问题不是新问题，一般来说已经有管理和经验作参考。
因而进行决策是就比较容易。
特殊性决策：是对特殊的，先例可循的新问题的决策。
做这类决策的个人或组织只有认真履行决策过程的四个阶段，才能作出满意的决策。
计划性决策：有些类似法治系统中的立法工作。
国家或组织的方针政策以及较长期的计划等都可视为计划性较长的对象。
最大最大决策标准：可称为乐观主义者的决策标准，采用这种决策标准，决策者比较谨慎小心。
总是从未来的销售情况可能较差的状态考虑。
然后在选择最优的可行方案、最小最小遗憾值决策标准：也叫最小最大后悔值决策标准。
它运用计算遗憾值的逻辑原则，求得在不同的销售状态下选用不同的方案所能造成的遗憾值，然后在根据最小最大以后标准进行决策。
选取最优方案。
现实主义决策标准：也称折衷主义决策标准。
所谓现实主义或折衷主义，就是说既不是从最乐观的角度。
也不说从最保守的角度来估计未来可能出现才自然状态存货台套：它的英文原名为stockkeepinggunit，在某些企业中可以译成存货储备单元，简称存货单元ABC分析法是按各种存货台套或存货单元的年度需用价值，将它们分成A，B，C三类。
运筹学
请在以下五组题目中任选一组作答，满分100分。
第一组：
计算题（每小题25分，共100分）
1.福安商场是个中型的百货商场，它对售货人员的需求经过统计分析如下表所示，为了保证售货人员充分休息，售货人员每周工作五天，休息两天，并要求休息的两天是连续的，问该如何安排售货人员的休息，既满足了工作需要，又使配备的售货人员的人数最少，请列出此问题的数学模型。
2、某厂生产甲、乙两种产品，这两种产品均需在A 、B 、C 三种不同的设备上加工，每种产品在不同设备上加工所需的工时不同，这些产品销售后所能获得利润以及这三种加工设备
问：该厂应如何组织生产，即生产多少甲、乙产品使得该厂的总利润为最大？
3、用图解法求解 min z =－3x1+x2 s.t.
⎪⎪⎪⎩⎪
⎪⎪⎨⎧≥≤+≥+≤≤0
8
2125234212
12121
x x x x x x x x ，
⑵ ⑶ ⑷ ⑸
⑹、⑺
⑴
4、用单纯形法求解 max z =7x1+12x2 s.t.
⎪⎪⎩⎪⎪⎨
⎧≥≤+≤+≤+0300103200543604921212121x x x x x x x x ，
第二组：
计算题（每小题25分，共100分）
1.A 、B 两人分别有10分(1角)、5分、1分的硬币各一枚，双方都不知道的情况下各出一枚，规定和为偶数，A 赢得8所出硬币，和为奇数，8赢得A 所出硬币，试据此列出二人零和对策模型，并说明此游戏对双方是否公平。
2、用图解法求解 max z = 6x1+4x2 s.t.
3、用单纯形法求解
max z =70x1+30x2 s.t.
⎪⎪⎩⎪⎪⎨
⎧≥≤+≤+≤+072039450555409321212121x x x x x x x x ，
4.某企业要用三种原材料A 、B 、C 生产出出三种不同规格的产品甲、乙、丙。
已知产品的规格要求，产品单价，每天能供应的原材料数量及原材料单价，分别见表1和表2。
该企业应如何安排生产，使利润收入为最大?
⑵ ⑶ ⑷ ⑸、⑹
1212212
210870x x x x x x x +≤⎧⎪+≤⎪⎨
≤⎪
⎪≥⎩， ⑴
表1
第三组：
计算题（每小题25分，共100分）
1、用标号法求下列网络V 1→V 7的最短路径及路长。
2、某企业生产三种产品A 1、A 2、A 3。
每种产品在销售时可能出现销路好(S 1)，销路一般(S 2)
和销路差(S 3)三种状态，每种产品在不同销售状态的获利情况(效益值)如表所示，请按乐观法则进行决策，选取生产哪种产品最为合适。
V 1 V 7 V 5
V 6 V 4
V 3 V 2 5
4 3
5 3 1 7
6 1
7 3 1
表
3、下列表是一个指派问题的效率表(工作时间表)，其中A i 为工作人员(i=1, 2, 3, 4)、B j 为工作项目(j=1, 2, 3, 4)，请作工作安排，使总的工作时间最小。
表
4、下列表是三个不同模型的线性规划单纯形表，请根据单纯形法原理和算法，分别在表中括号中填上适当的数字。
1. 计算该规划的目标函数值
2、确定上表中输入，输出变量。
第四组：
计算题（每小题25分，共100分）
1、下图是某一工程施工网络图(统筹图)，图中边上的数字为工序时间(天)，请求出各事项的最早时间和最迟时间，求出关键路线，确定计划工期。
C j → 20 15 20 0 0 Ci x B b
x 1 x 2 x 3 x 4 x 5 20 x 1 2 20 x 3 1 0 x 5 3
z j c j －z j
0 -15 0 10 0
B 1 B 2 B 3 B 4
A 1
A 2 A 3 A 4
2、已知运输问题的运价表和发量和收量如表所示，请用最小元素法求出运输问题的一组解。
表
3、有一化肥厂用两种原料A,B 生产C,D,E 三种化肥，根据市场调查某地区各种化肥每天最少需求分别为100吨，60吨，130吨。
该厂每天可供的原料分别为200吨和240吨。
单位成品化肥所耗费的原料及销售利润如下表。
问每天应生产多少各类化肥，使该厂利润最大。
要求建立线性规划模型，不作具体计算。
4、已知一个线性规划原问题如下，请写出对应的对偶模型
max 12
25S x x =+
121212
438,0x x x x x x ≤⎧⎪≤⎪⎨
+≤⎪⎪≥⎩
第五组：
计算题（每小题25分，共100分）
B 1 B 2 B 3 B 4 A 1 9 A 2 4 A 3 5 3
5
4
6
1、下图为动态规划的一个图示模型，边上的数字为两点间的距离，请用逆推法求出S 至F 点的最短路径及最短路长。
2、自已选用适当的方法，对下图求最小(生成树)。
3、设有某种肥料共6个单位，准备给4块粮田用，其每块粮田施肥数量与增产粮食的关系如下表所示。
试求对每块田施多少单位重量的肥料，才能使总的粮食增产最多。
4、求下面问题的对偶规划 极大化
1234
3257z x x x x =--+
1234134123423272+223248
x x x x x x x x x x x ⎧⎪
⎨⎪
⎩+-+≥---≤--+-≥
V 1 2 3 3 5
2 3
3
5
6
V 3 V 2 V 4 V 5 V 6
12340,0,0,x x x x ≥≥≤无非负限制。
要求：
1. 独立完成，作答时要写明题型、题号；
2. 作答方式：手写作答或电脑录入，使用A4格式白纸；
3. 提交方式：以下两种方式任选其一，
1) 手写作答的同学可以将作业以图片形式打包压缩上传； 2) 提交电子文档的同学可以将作业以word 文档格式上传；
4. 上传文件命名为“中心-学号-姓名-科目.rar ” 或“中心-学号-姓名-科目.doc ”；
5. 文件容量大小：不得超过20MB 。
