下载文档原格式
《运筹学》课程复习资料一、判断题：1.图解法与单纯形法虽然求解的形式不同，但从几何上理解，两者是一致的。
[ ]2.线性规划问题的每一个基本解对应可行解域的一个顶点。
[ ]3.任何线性规划问题存在并具有惟一的对偶问题。
[ ]4.已知y i*为线性规划的对偶问题的最优解，若y i*＞0，说明在最优生产计划中第i种资源已完全耗尽。
[ ] 5.运输问题是一种特殊的线性规划问题，因而其求解结果也可能出现下列四种情况之一：有惟一最优解，有无穷多最优解，无界解，无可行解。
[ ]6.动态规划的最优性原理保证了从某一状态开始的未来决策独立于先前已做出的决策。
[ ]7.如果线性规划问题存在最优解，则最优解一定可以在可行解域的顶点上获得。
[ ]8.用单纯形法求解Max型的线性规划问题时，检验数Rj＞0对应的变量都可以被选作入基变量。
[ ]9.对于原问题是求Min，若第i个约束是“＝”，则第i个对偶变量yi≤0。
[ ]10.用大M法或两阶段法单纯形迭代中若人工变量不能出基(人工变量的值不为0)，则问题无可行解。
[ ]11.如图中某点vi 有若干个相邻点,与其距离最远的相邻点为vj,则边[vi,vj]必不包含在最小支撑树内。
[ ]12.在允许缺货发生短缺的存贮模型中，订货批量的确定应使由于存贮量的减少带来的节约能抵消缺货时造成的损失。
[ ] 13.根据对偶问题的性质，当原问题为无界解时，其对偶问题无可行解，反之，当对偶问题无可行解时，其原问题具有无界解。
[ ] 14.在线性规划的最优解中，若某一变量xj为非基变量，则在原来问题中，改变其价值系数cj，反映到最终单纯形表中，除xj的检验数有变化外，对其它各数字无影响。
[ ]15.单纯形迭代中添加人工变量的目的是为了得到问题的一个基本可行解。
[ ]16.订购费为每订一次货所发生的费用，它同每次订货的数量无关。
[ ]17.一个动态规划问题若能用网络表达时，节点代表各阶段的状态值，各条弧代表了可行方案的选择。
运筹学复习题答案1. 线性规划问题的标准形式包括哪些条件？- 所有变量非负- 目标函数和约束条件均为线性- 约束条件为等式或不等式2. 请简述单纯形法的基本原理。
- 从一个初始可行解出发- 通过迭代选择进入基变量和离开基变量- 每次迭代都改进目标函数值- 直到找到最优解或确定问题无界3. 什么是敏感性分析？- 分析目标函数或约束条件参数变化对最优解的影响 - 确定哪些参数变化会导致最优解改变- 评估问题解的稳定性4. 整数线性规划与线性规划的主要区别是什么？- 整数线性规划要求至少一个变量为整数- 整数线性规划可能没有最优解或解的求解过程更复杂5. 请解释对偶理论在线性规划中的应用。
- 每个线性规划问题都有一个对偶问题- 对偶问题提供了原问题解的下界- 对偶问题可以用来检验原问题解的最优性6. 什么是运输问题，它有何特点？- 运输问题是一种特殊的线性规划问题- 涉及货物从多个供应点到多个需求点的分配- 目标是最小化总运输成本7. 请描述网络流问题的基本类型及其应用。
- 最大流问题：确定网络中的最大流量- 最小费用流问题：在满足流量约束的同时最小化费用- 应用包括物流、通信网络和交通规划8. 什么是动态规划，它与线性规划有何不同？- 动态规划是解决多阶段决策问题的算法- 它通过将问题分解为更小的子问题来求解- 与线性规划不同，动态规划问题通常涉及时间序列和决策过程9. 请简述排队论的基本概念及其在实际中的应用。
- 排队论研究等待服务的队列系统- 包括到达过程、服务过程和服务台数量等参数- 应用于银行、医院、电话系统等的效率分析10. 什么是库存管理，它在运筹学中的重要性是什么？- 库存管理涉及对存货的控制和优化- 目标是最小化库存成本和满足需求- 在供应链管理中起着核心作用，影响企业的整体效率和成本11. 请解释博弈论的基本概念及其在决策中的应用。
- 博弈论研究具有冲突和合作特征的决策者之间的策略互动- 包括零和博弈和非零和博弈- 应用于经济、政治、军事等领域的策略制定12. 什么是多目标优化问题，它与单目标优化有何不同？- 多目标优化问题需要同时考虑多个目标函数- 目标之间可能存在冲突，需要权衡和折中- 与单目标优化不同，多目标优化寻求的是一组最优解集，而非单个最优解13. 请简述遗传算法的工作原理及其在优化问题中的应用。
《运筹学》期末复习及答案(总14页)--本页仅作为文档封面，使用时请直接删除即可----内页可以根据需求调整合适字体及大小--运筹学概念部分一、填空题1．运筹学的主要研究对象是各种有组织系统的管理问题，经营活动。
2．运筹学的核心主要是运用数学方法研究各种系统的优化途径及方案，为决策者提供科学决策的依据。
3．模型是一件实际事物或现实情况的代表或抽象。
4通常对问题中变量值的限制称为约束条件，它可以表示成一个等式或不等式的集合。
5．运筹学研究和解决问题的基础是最优化技术，并强调系统整体优化功能。
6．运筹学用系统的观点研究功能之间的关系。
7．运筹学研究和解决问题的优势是应用各学科交叉的方法，具有典型综合应用特性。
8．运筹学的发展趋势是进一步依赖于_计算机的应用和发展。
9．运筹学解决问题时首先要观察待决策问题所处的环境。
10．用运筹学分析与解决问题，是一个科学决策的过程。
11.运筹学的主要目的在于求得一个合理运用人力、物力和财力的最佳方案。
12．运筹学中所使用的模型是数学模型。
用运筹学解决问题的核心是建立数学模型，并对模型求解。
13用运筹学解决问题时，要分析，定义待决策的问题。
14．运筹学的系统特征之一是用系统的观点研究功能关系。
15.数学模型中，“s·t”表示约束（subject to 的缩写）。
16．建立数学模型时，需要回答的问题有性能的客观量度，可控制因素，不可控因素。
17．运筹学的主要研究对象是各种有组织系统的管理问题及经营活动。
18. 1940年8月，英国管理部门成立了一个跨学科的11人的运筹学小组，该小组简称为OR。
二、单选题19．建立数学模型时，考虑可以由决策者控制的因素是（ A ）A．销售数量 B．销售价格 C．顾客的需求 D．竞争价格20．我们可以通过（ C）来验证模型最优解。
A．观察 B．应用 C．实验 D．调查21．建立运筹学模型的过程不包括（ A ）阶段。
A．观察环境 B．数据分析 C．模型设计 D．模型实施22.建立模型的一个基本理由是去揭晓那些重要的或有关的（B ）A数量 B变量 C约束条件 D 目标函数23.模型中要求变量取值（ D ）A可正 B可负 C非正 D非负24.运筹学研究和解决问题的效果具有（A ）A 连续性 B整体性 C 阶段性 D再生性25.运筹学运用数学方法分析与解决问题，以达到系统的最优目标。
《管理运筹学》总复习第一天：1)（★★★★★）课本Page59第5题（租赁问题）：某公司在今后四个月内需租用仓库堆放物资。
已知各个月所需的仓库面积数字如下所示：设第个月签订的打算租用个月合同仓库面积为，那么这个月共有可能有如下合同：第一个月：第二个月：第三个月：第一个月：因此目标函数为：约束条件为：2)（★★★）讲义Page8例1（人力资源问题）：福安商场是个中型百货商场，他对销售员的需求经过统计分析如下表。
为了保证售货人员充分的休息，售货人员每周工作5天，休息2天，并且要求休息的两天是连续的。
问如何安排售货人员的工作作息，才能做到既满足工作需要，又使配备的工作人员最少？解：设在星期开始休息的人数为，表示星期一到星期日那么，目标函数为：约束条件为：周一：周二：周三：周四：周五：周六：周日：非负约束：3)（★）【据说出题时会和整数规划相融合】讲义Page10例5（投资问题）：某部门现有资金200万，今后五年内考虑给以下项目投资。
已知，项目A：从第一年到第五年都每年年初都可以投资，当年末能收回本利110%；项目B：从第一年到第四年都每年年初都可以投资，次年末能收回本利125%，但规定每年最大投资额不能超过30万；项目C：需在第三年初投资，第五年末收回本利140%，但规定最大投资额不能超过80万；项目D：须知第二年初投资，第五年末能收回本利155%，但规定最大投资额不能超过100万；据测定每万元每次投资的风险指数如下表：1)应如何确定这些项目的每年投资额，使得第五年年末拥有资金的本利金额为最大？2)应如何确定这些项目的每年投资额，使得第五年年末拥有资金的本利在330万的基础上使得其投资总的风险系数最小？解：设第年初投资在项目上的金额为，其中，。
第一年初：，，不能浪费资金，所以有，第一年年末收回：第二年初：，，，用第一年年末的收回投资，所以有：，第二年年末收回：第三年初：，，，用第二年年末收回投资，所以有：，第三年年末收回：第四年初：，，用第三年年末收回进行投资，所以有：，第四年年末收回：第五年初：用第四年年末回收进行投资，所以有：，第五年年末收回：同时，根据项目的要求，有：第（1）问答如下：目标函数为：约束条件为：第（2）问答如下：目标函数为：约束条件为：4)（★★★★）讲义Page11分析讨论题3（工厂布局问题）：设有某种原料产地A1,A2,A3，把这种原料经过加工，制成成品，再运往销地。
《运筹学》复习资料注：如学员使用其他版本教材，请参考相关知识点一、客观部分：（单项选择、多项选择、判断）（一）多选题1．线性规划模型由下面哪几部分组成？（ABC）A决策变量 B约束条件 C目标函数 D 价值向量★考核知识点: 线性规划模型的构成.（1.1）附1.1.1（考核知识点解释）：线性规划模型的构成：实际上，所有的线性规划问题都包含这三个因素：（1）决策变量是问题中有待确定的未知因素。
例如决定企业经营目标的各产品的产量等。
（2）目标函数是指对问题所追求的目标的数学描述。
例如利润最大、成本最小等。
（3）约束条件是指实现问题目标的限制因素。
如原材料供应量、生产能力、市场需求等，它们限制了目标值所能到达的程度。
2．下面关于线性规划问题的说法正确的是（AB）A．线性规划问题是指在线性等式的限制条件下，使某一线性目标函数取得最大值（或最小值）的问题。
B．线性规划问题是指在线性不等式的限制条件下，使某一线性目标函数取得最大值（或最小值）的问题。
C．线性规划问题是指在一般不等式的限制条件下，使某一线性目标函数取得最大值（或最小值）的问题。
D．以上说法均不正确★考核知识点: 线性规划模型的线性含义.（1.1）附1.1.2（考核知识点解释）：所谓“线性”规划，是指如果目标函数是关于决策变量的线性函数，而且约束条件也都是关于决策变量的线性等式或线性不等式，则相应的规划问题就称为线性规划问题。
3．下面关于图解法解线性规划问题的说法不正确的是（ BC ）A在平面直角坐标系下，图解法只适用于两个决策变量的线性规划B 图解法适用于两个或两个以上决策变量的线性规划C 图解法解线性规划要求决策变量个数不要太多，一般都能得到满意解D 以上说法A正确，B，C不正确★考核知识点: 线性规划图解法的条件. （1.2）附 1.1.3（考核知识点解释）：线性规划图解法的条件：对于只有两个变量的线性规划问题，可以在二维直角坐标上作图.4．在下面电子表格模型中，“决策变量”的单元格地址为（ AB ）A . C12B . D12C . C4 D. D4★考核知识点: 电子表格中如何建立线性数学模型. （1.3）附1.1.4（考核知识点解释）：电子表格中的数学模型的建立：（1）要做出的决策是什么？（决策变量）；（2）在做出这些决策时有哪些约束条件？（约束条件）；（3）这些决策的目标是什么？（目标函数），将对应的问题数据放在相应的电子表格中即可.5．通常，在使用“给单元格命名”时，一般会给（ABCD ）有关的单元格命名A 公式B 决策变量C 目标函数D 约束右端值★考核知识点: 给单元格命名的原则. （1.3）附1.1.5（考核知识点解释）：给单元格命名的原则：一般给跟公式和模型有关的四类单元格命名。
第二章线性规划的基本概念一、填空题1．线性规划问题是求一个线性目标函数_在一组线性约束条件下的极值问题。
2．图解法适用于含有两个变量的线性规划问题。
3．线性规划问题的可行解是指满足所有约束条件的解。
4．在线性规划问题的基本解中，所有的非基变量等于零。
5．在线性规划问题中，基可行解的非零分量所对应的列向量线性无关6．若线性规划问题有最优解，则最优解一定可以在可行域的顶点（极点）达到。
7．线性规划问题有可行解，则必有基可行解。
8．如果线性规划问题存在目标函数为有限值的最优解，求解时只需在其基可行解_的集合中进行搜索即可得到最优解。
9．满足非负条件的基本解称为基本可行解。
10．在将线性规划问题的一般形式转化为标准形式时，引入的松驰数量在目标函数中的系数为零。
11．将线性规划模型化成标准形式时，“≤”的约束条件要在不等式左_端加入松弛变量。
12．线性规划模型包括决策（可控）变量，约束条件，目标函数三个要素。
13．线性规划问题可分为目标函数求极大值和极小_值两类。
14．线性规划问题的标准形式中，约束条件取等式，目标函数求极大值，而所有变量必须非负。
15．线性规划问题的基可行解与可行域顶点的关系是顶点多于基可行解16．在用图解法求解线性规划问题时，如果取得极值的等值线与可行域的一段边界重合，则这段边界上的一切点都是最优解。
17．求解线性规划问题可能的结果有无解，有唯一最优解，有无穷多个最优解。
18.如果某个约束条件是“≤”情形，若化为标准形式，需要引入一松弛变量。
19.如果某个变量X j为自由变量，则应引进两个非负变量X j′,X j〞,同时令X j＝X j′－X j。
20.表达线性规划的简式中目标函数为max(min)Z=∑c ij x ij。
21..(2.1 P5))线性规划一般表达式中，a ij表示该元素位置在i行j列。
二、单选题1．如果一个线性规划问题有n个变量，m个约束方程(m<n)，系数矩阵的数为m，则基可行解的个数最为_C_。
《运筹学》总复习第1章线性规划及其对偶问题• 基本概念基本要素：决策变量、目标函数、约束条件线性规划定义：决策变量为可控的连续变量，目标函数和约束条件为决策变量的线性函数。
标准形式：目标函数取“max ”、约束条件取“="、约束右端项非负、决策变量非负解的概念：凡满足约束条件的决策变量的取值称为线性规划的可行解,所有可行解的集合称 为线性规划的可行域，使目标函数达到最优值的可行解称为线性规划的最优解。
•数学建模与求解建模步骤：科学选择决策变量、找出所有约束条件、明确目标要求、非负变量的选择 单纯形法与对偶单纯形法：单纯形法对偶单纯形法原规划基本解是可行解原规划基本解的检验数小于等于零无可行解解无界计算：nr b । …b9 = min{-a\a > 0] = -i- a ka以a为中心元素进行迭代以a为中心元素进行迭代计算：o = max(o . o , > 0)计算：b = min(b\b < 0)计算:两阶段法：第一阶段：添加人工变量，构造人工变量之和为最小的目标函数辅助线性规划，由松驰变量和人工变量构成初始单纯形表，进行迭代。
在最终单纯形表中如果存在人工变量，由无可行解，否则转第二阶段。
第二阶段：在第一阶段求解的最终单纯形表中去掉人工变量，目标系数恢复为标准模型的目标系数，按单纯形法继续迭代。
•练习题：1.某厂利用原料A、B生产甲、乙、丙3种产品，已知生产单位产品所需原料数、单件利2.某旅馆在不同时段所需服务员数如表所示：每班服务员从开始上班到下班连续工作8小时，为满足每班所需要的最少服务员数，这个旅3.min w = x + 2 x + 3 x1 2 3x + 2 x + 3 x = 15s.t < 2x + x + 5x = 20x > 011~34.用对偶单纯形法求解线性规划问题：min w = 5 x + 2 x + 4 x1 2 33 x + x + 2 x > 4s .t < 6 x + 3 x + 5 x > 12x1 > 02 31 1~3第2章整数规划与分配问题•0-1变量的用法及建模理解0-1变量的9种用途，其中(1)(2)(4)(8)重点掌握(1)多个取1：¥x = 1，x,= 0,或 1.j=1(2) n 中取 k ：X % = k , x - 0,或 1.j =in 中至少取k ,改为E x > k , x = 0,或1.j -i n 中最多取k , 改为Yx < k , x = 0,或 1.j -i(3)变量取离散数值：x^^^cy.vi =1 i i£y = 1, y = 0或 1i i =1⑷选甲必须选乙，选乙不一定选甲：、 <久，、, 丁或1 （5）两个约束条件只需满足一个:（8）选了甲或乙，丙就不能入选，选了丙，甲、乙都不能入选■%+ x w <1< x + x < 1 x , x , x 丙=0或 1I 0,当 x = 0⑼对f (x )= 1 k + cx ,当x > 0可表述为:匈牙利法 步骤：x + x > 2 一 y M < 3 x + 2 x < 10 + y M/ + y 2 = 1,片 y 2 = 0或 1式中：M 为任意大正数 （6）n个约束条件中满足k 个：I x + x > 2 一(1 一 y ) M或1 12一 |3x + 2x < 10 + yM ,y =2ax < 嗔yM< j =1(i = 1,2,L , n )i =1⑺若x 2 < 4，则x 5 >；否则x 2> 4，। x < 4 + y M<x 5>0-y 1M, x 2 > 4- y2Mx 5 < 3 + y 2y 1 +y 2 = y। x < 4 + yMx ： > 0 - yM 或1 5 - x 2 > 4 - (1 - y ) M 「0I f (x ) = yk + cx< y < Mx x < My1.从每行中减去最小数2.再从每列中减去最小数3.⑴先看行,从第一行开始，如该行只有一个0,给该0打A,划去该为所在列,如有两个以上0或无0,转下一行,到最后一行；（2）再看列，如该列只有一个0,给该0打A，划去该0所在行，如无0或两个以上0,转下一列；⑶重复（1）（2）,可能出现三种结局：a.有m个打A的0,令对应A号的xij=1,即为最优.b.存在0的闭回路.对闭回路上的0按顺时针编号，任取单号或双号打A，分别对打A的0都划去所在行（或都划去所在列）返回3（1）C.打A的0的数＜m转44.从未被划去的数字中找出最小数字k,对未被划去的行分别减k;对被划去的列加k,回到3练习题：1.某公司有5000万元可用于投资，有6个投资方案，其投资额、安排员工数和年利润额如要求：（1）投资额不超过5000万元；（2）至少安排150人员就业；（3）年利润额尽可能地多。
运筹学复习题及答案一、一个毛纺厂用羊毛和涤纶生产A、B、C混纺毛料，生产1单位A、B、C分别需要羊毛和涤纶3、2；1、1；4、4单位，三种产品的单位利润分别为4、1、5。
每月购进的原料限额羊毛为8000单位，涤纶为3000单位，问此毛纺厂如何安排生产能获得最大利润？（要求：建立该问题的数学模型）解：设生产混纺毛料ABC各x1、x2、x3单位max z＝x1+x2+5x33x1+x2+4x3≤80002x1+x2+4x3≤3000x1,x2,x3≥0二、写出下述线性规划问题的对偶问题max s=2x1+3x2-5x3+x4x1+x2-3x3+x4≥52x1 +2x3-x4≤4x2 +x3+x4=6x1,x2,x3≥0；x4无约束解：先将原问题标准化为：max s=2x1+3x2-5x3+x4-x1-x2+3x3-x4≤-52x1 +2x3-x4≤4x2 +x3+x4=6x1,x2,x3≥0；x4无约束则对偶问题为：min z=-5y1+4y2+6y3-y1+2y2≥2-y1+ y2≥33y1+ 2y2+y3≥-5-y1-y2+y3=1y1,y2≥0,y3无约束三、求下述线性规划问题min S =2x1＋3x2－5x3x 1＋x 2－3x 3 ≥5 2x 1 ＋2x 3 ≤4x 1，x 2，x 3≥0解：引入松弛变量x4，x5，原问题化为标准型：max Z=-S =-2x 1-3x 2+5x 3x 1＋x 2－3x 3 －x 4=5 2x 1 ＋2x 3 +x 5=4x 1，x 2，x 3, x 4,x 5≥0 对应基B 0＝（P2,P5T(B 0)=x1的检验数为正，x1进基，由min ｛5/1,4/2｝=4/2知，x5出基，迭代得新基B1=(P2,P1),对应的单纯形表为T(B 1)=至此，检验数全为非正，已为最优单纯形表。
对应的最优解为： x1=2,x2=3,x3=x4=x5=0,max z=-13,故原问题的最优解为： x1=2,x2=3,x3 =0,min s=13。
一、单项选择题1、下列叙述正确的是（）。
A．线性规划问题，若有最优解，则必是一个基变量组的可行基解B．线性规划问题一定有可行基解C．线性规划问题的最优解只能在最低点上达到D．单纯形法求解线性规划问题时，每换基迭代一次必使目标函数值下降一次答案：A2、线性规划的变量个数与其对偶问题的（）相等。
A．变量目标函数B．变量约束条件C．约束条件个数D．不确定答案：C3、在利用表上作业法求各非基变量的检验数时，有闭回路法和（）两种方法。
A．西北角法B．位势法C．最低费用法D．元素差额法答案：B4、下列各项（）不是目标规划的特点。
A．多目标B．单一目标C．具有优先次序D．不求最优答案：B5、下列关于图的说法中，错误的为（）。
A．点表示所研究的事物对象B．边表示事物之间的联系C．无向图是由点及边所构成的图D．无环的图称为简单图答案：D6、利用单纯形法求解线性规划问题时，首先需要（）。
A．找初始基础可行基B．检验当前基础可行解是否为最优解C．确定改善方向D．确定入变量的最大值和出变量答案：A7、对偶问题最优解的剩余变量解值（）原问题对应变量的检验数的绝对值。
A．大于B．小于C．等于D．不能确定答案：C8、当某个非基变量检验数为零，则该问题有（）。
A．无解B．无穷多最优解C．退化解D．惟一最优解答案：B9、PERT 网络图中，（）表示一个工序。
A．节点B．弧C．权D．关键路线答案：B10、假设对于一个动态规划问题，应用顺推法以及逆推解法得出的最优解分别为P和D，则有（）。
A．P>D B．P<DC．P=D D．不确定答案：C11、下列有关线性规划问题的标准形式的叙述中错误的是（）。
A．目标函数求极大B．约束条件全为等式C．约束条件右端常数项全为正D．变量取值全为非负答案：C12、线性规划问题的数学模型由目标函数、约束条件和（）三个部分组成。
A．非负条件B．顶点集合C．最优解D．决策变量答案：D13、如果原问题有最优解，则对偶问题一定具有（）。
线性规划部分1. 试述线性规划问题的可行解、基础解、基可行解、最优解的概念及其相互关系2. 对偶问题和对偶变量(即影子价值)的经济意义是什么? 什么是资源的影子价格?它与相应的市场价格有什么区别?3. 如何根据原问题和对偶问题之间的对应关系,找出两个问题变量之间、解及检验数之间的关系?4. 试述整数规划分枝定界法的思路5.线性规划具有无界解是指 (C)A.可行解集合无界B.有相同的最小比值C.存在某个检验数0,0,(1,2,,)k ik a i m λ≥≤=LD.最优表中所有非基变量的检验数非零6.线性规划具有唯一最优解是指 (A)A.最优表中非基变量检验数全部非零B.不加入人工变量就可进行单纯形法计算C.最优表中存在非基变量的检验数为零D.可行解集合有界7.线性规划具有多重最优解是指 (B)A.目标函数系数与某约束系数对应成比例B.最优表中存在非基变量的检验数为零C.可行解集合无界D.基变量全部大于零8.线性规划的退化基可行解是指 (B)A.基可行解中存在为零的非基变量B.基可行解中存在为零的基变量C.非基变量的检验数为零D.所有基变量不等于零9.线性规划无可行解是指 (C)A.第一阶段最优目标函数值等于零B.进基列系数非正C.用大M 法求解时,最优解中还有非零的人工变量D.有两个相同的最小比值10.若线性规划不加入人工变量就可以进行单纯形法计算 (B)A.一定有最优解B.一定有可行解C.可能无可行解D.全部约束是小于等于的形式11.线性规划可行域的顶点一定是 (A)A.可行解B.非基本解C.非可行D.是最优解12.X 是线性规划的基本可行解则有 (A)A.X 中的基变量非负，非基变量为零B.X 中的基变量非零，非基变量为零C. X 不是基本解D.X 不一定满足约束条件13.下例错误的说法是 (C)A.标准型的目标函数是求最大值B.标准型的目标函数是求最小值C.标准型的常数项非正D.标准型的变量一定要非负14.为什么单纯形法迭代的每一个解都是可行解？答：因为遵循了下列规则 (A)A.按最小比值规则选择出基变量B.先进基后出基规则C.标准型要求变量非负规则D.按检验数最大的变量进基规则15.线性规划标准型的系数矩阵A m ×n ，要求 (B)A.秩(A)=m 并且m<nB.秩(A)=m 并且m<=nC.秩(A)=m 并且m=nD.秩(A)=n 并且n<m16.下例错误的结论是 (D)A.检验数是用来检验可行解是否是最优解的数B.检验数是目标函数用非基变量表达的系数C.不同检验数的定义其检验标准也不同D.检验数就是目标函数的系数17.对偶单纯形法的最小比值规划则是为了保证 (B)A.使原问题保持可行B.使对偶问题保持可行C.逐步消除原问题不可行性D.逐步消除对偶问题不可行性18.互为对偶的两个线性规划问题的解存在关系 (A)A.一个问题具有无界解，另一问题无可行解 B 原问题无可行解，对偶问题也无可行解C.若最优解存在，则最优解相同D.一个问题无可行解，则另一个问题具有无界解19.原问题与对偶问题都有可行解，则 (D)A. 原问题有最优解，对偶问题可能没有最优解B. 原问题与对偶问题可能都没有最优解C.可能一个问题有最优解，另一个问题具有无界解D.原问题与对偶问题都有最优解20.某个常数b i 波动时，最优表中引起变化的有 (A)A.B －1bB.1N B C C B N --C.B －1D.B －1N 21.当基变量x i 的系数c i 波动时，最优表中引起变化的有 (B)A. 最优基BB.所有非基变量的检验数C.第i 列的系数i ND.基变量X B 22.当非基变量x j 的系数c j 波动时，最优表中引起变化的有 (C )A.00单纯形乘子B.目标值C.非基变量的检验数D. 常数项23.若线性规划问题的最优解同时在可行解域的两个顶点处达到，那么该线性规划问题最优解为（ C ）A.两个B.零个C.无穷多个D.有限多个24.原问题与对偶问题的最优（B ）相同。
1. 运筹学 诞生于 20 世纪 30 年代。
2. 运筹学是一门研究如何有效地组织和管理人机系统的科学。
3. 对管理领域，运筹学也是对管理决策工作进行决策的计量方法。
4. 运筹学为管理人员制动决策提供了定量基础。
5. 运筹学利用计划方法和有关多学科的要求，把复杂功能关系表示成数学模型。
6. 在当今信息时代，运筹学和计算机方法的分界线将会消失，并将脱离各自原来的领域，组合成更通用更 广泛的管理科学的形式。
7. 决策方法的分类 ：定性决策 ：基本上根据决策人员的 主观经验或感受到的感觉或知识 而制定的决策。
定量决策 ：借助某些正规的计量方法而做出的决策。
混合性决策 ：必须运用定性和定量两种方法才能制定的决策。
8. 作为运筹应用者，接受管理部门的要求，去收集和阐明数据，建立和试验数学模型，预言未来作业，然 后制定方然，并推荐给经理部门。
9. 运筹学 ： Operations Research,简称 OR ，是一门研究如何有效地组织和管理人及系统的科学。
运筹学利用 计划方法和有关多学科的要求，把复杂功能关系表示成 数学模型 ，其目的就是通过 定量分析 为决策和揭露 新问题提供数量根据 10. 应用运筹学进行决策过程的几个步骤1、观察待决策问题所处的环境问题域的环境有 内部环境和外部环境内部环境 ：问题域内部人、财、物之间的交互活动。
外部环境 ：问题域界面与外界的人、财、物之间的交互活动。
注意两者的区别。
2、分析和定义待决策的问题3、拟定模型： 这个工作是 OR 项目中最费时的部分4、选择输入资料5、提出解并验证它的合理性敏感度实验 ：一旦有了模型的解答， 就要试图改变模型及输入， 并注视将要发生什么样的输出， 一般把这样的过程叫做敏感度实验。
6、实施最优解1. 预测就是对未来的不确定的事情惊醒估计或判断。
预测是决策的基础 。
2. 预测方法的分类。
宏观经济是指国民经济范围的经济预测。
微观经济预测经济预测 3—5 年的为长期，1—3年的为中期，年内的为短期。
《运筹学》总复习第1章线性规划及其对偶问题●基本概念基本要素：决策变量、目标函数、约束条件线性规划定义：决策变量为可控的连续变量，目标函数和约束条件为决策变量的线性函数。
标准形式：目标函数取“max”、约束条件取“=”、约束右端项非负、决策变量非负解的概念：凡满足约束条件的决策变量的取值称为线性规划的可行解,所有可行解的集合称为线性规划的可行域,使目标函数达到最优值的可行解称为线性规划的最优解。
●数学建模与求解建模步骤：科学选择决策变量、找出所有约束条件、明确目标要求、非负变量的选择单纯形法与对偶单纯形法：单纯形法对偶单纯形法两阶段法：第一阶段：添加人工变量，构造人工变量之和为最小的目标函数辅助线性规划，由松驰变量和人工变量构成初始单纯形表，进行迭代。
在最终单纯形表中如果存在人工变量，由无可行解，否则转第二阶段。
第二阶段：在第一阶段求解的最终单纯形表中去掉人工变量，目标系数恢复为标准模型的目标系数，按单纯形法继续迭代。
● 练习题：1.某厂利用原料A 、B 生产甲、乙、丙3种产品，已知生产单位产品所需原料数、单件2.每班服务员从开始上班到下班连续工作8小时，为满足每班所需要的最少服务员数，这个旅馆至少需要多少服务员？（列出该问题线性规划模型，不求解）3.1231231231~3min 232315..25200w x x x x x x s t x x x x =++++=⎧⎪++=⎨⎪≥⎩ 4.用对偶单纯形法求解线性规划问题：1231231231~3min 524324..635120w x x x x x x s t x x x x =++++≥⎧⎪++≥⎨⎪≥⎩第2章 整数规划与分配问题● 0-1变量的用法及建模理解0-1变量的9种用途，其中(1)(2)(4)(8)重点掌握 （1）多个取1：110, 1.nj j j x x ===∑，或（2）n 中取k ：10, 1.njj j xk x ===∑，或n 中至少取k ，改为10, 1.nj j j x k x =≥=∑，或n 中最多取k ，改为10, 1.nj j j x k x =≤=∑，或（3）变量取离散数值：111,01mi i i mi i i x c y y y ==⎧=⎪⎪⎨⎪==⎪⎩∑∑或（4）选甲必须选乙，选乙不一定选甲：,x x x x ≤乙乙甲甲,=0或1（5）两个约束条件只需满足一个：1211221212232101,,01x x y Mx x y M y y y y +≥-⎧⎪+≤+⎨⎪+==⎩或 或12122(1)3210,01x x y M x x yM y +≥--⎧⎨+≤+=⎩或 式中：M 为任意大正数（6）n 个约束条件中满足k 个：11(1,2,,)01mi j j i i j ni i i a x b y M i n y n k y ==⎧≤+=⎪⎪⎨⎪=-=⎪⎩∑∑L 或（7）若42≤x ，则05≥x ；否则42>x ，35≤x⎪⎪⎩⎪⎪⎨⎧+≤->-≥+≤My x M y x M y x M y x 252215123404，⎩⎨⎧==+1012,121y y y 或⎪⎪⎩⎪⎪⎨⎧-+≤-->-≥+≤My x M y x yMx yM x )1(3)1(4045252⎩⎨⎧=10y（8）选了甲或乙，丙就不能入选，选了丙，甲、乙都不能入选11x x x x x x x ⎧+≤⎪+≤⎨⎪⎩甲丙乙丙乙甲丙,,=0或1 （9）对0,0(),0x f x k cx x =⎧=⎨+>⎩当当 可表述为： ()f x yk cxy Mx x My=+⎧⎪≤⎨⎪≤⎩匈牙利法步骤：1.从每行中减去最小数2.再从每列中减去最小数3.(1)先看行,从第一行开始,如该行只有一个0,给该0打Δ,划去该为所在列,如有两个以上0或无0,转下一行,到最后一行;(2)再看列,如该列只有一个0,给该0打Δ,划去该0所在行,如无0或两个以上0,转下一列;(3)重复(1)(2),可能出现三种结局:a.有m个打Δ的0,令对应Δ号的xij=1,即为最优.b.存在0的闭回路.对闭回路上的0按顺时针编号,任取单号或双号打Δ,分别对打Δ的0都划去所在行(或都划去所在列)返回3(1)C.打Δ的0的数<m转44.从未被划去的数字中找出最小数字k,对未被划去的行分别减k;对被划去的列加k,回到3 练习题：1．某公司有5000万元可用于投资，有6个投资方案，其投资额、安排员工数和年利润额如表所示：要求：（1）投资额不超过5000万元；（2）至少安排150人员就业；（3）年利润额尽可能地多。
试建立该问题0-1规划数学模型（不求解）2.某校排球队准备从以下8名预备队员中选拔4名正式队员，并使平均身高尽可能高。
这8要求：（1）8名预备队员选4名；（2）最多补充1名主攻； （3）最多补充1名副攻； （4）至少补充1名二传； （5）至少补充1名接应； （6）A 和E 只能入选1名；（7）无论B 或D 入选，A 都不能入选。
（建立数学模型，不求解）3.企业如何组织生产才能使总成本最小？试列出该问题的整数规划数学模型（不求解）。
4.试利用0-1变量对下列各题分别表示成一般线性约束条件。
（1）x 1+x 2≤2或2x 1+3x 2≥8（2）变量x 3只能取0、5、9、12 （3）若x 2≤4，则x 5≥0，否则x 5≤3（4）以下四个约束条件中至少满足两个：1212122153x x x x x x +≤⎧⎪≤⎪⎨≤⎪⎪+≥⎩ 5.用匈牙利法求解分配问题：（1）85907390828778918382798886908085C ⎡⎤⎢⎥⎢⎥=⎢⎥⎢⎥⎣⎦（2）8969665878389746C ⎡⎤⎢⎥⎢⎥=⎢⎥⎢⎥⎣⎦第3章 运输问题数学模型1.产销平衡运输问题数学模型1111min (1,2,...,)..(1,2,...,),0m nij iji j nij i j mij j ij i z c x x a i m s t x b j n x =====⎧==⎪⎪⎨⎪==≥⎪⎩∑∑∑∑2.产销不平衡的运输问题转化为产销平衡的运输问题 产>销：添加一个假想销地，使其销量=∑产量-∑销量 产<销：添加一个假想产地，使其产量=∑销量-∑产量3.会将一般的非地理问题转化为运输问题数学模型● 表上作业法（1）用最小元素法给出初始方案 （2）用位势法求检验数（3）用闭回路法进行方案调整 重复（2）（3）步，直到得最优解。
● 练习题：1.某建筑公司6个工地（A 、B 、C 、D 、E 、F ）的物资需要运输，各工地起点、终点及所需车次如表（a ）所示，相关工地间路程如表（b ）所示。
（a ） （b ）试求最优调运方案（列出产销平衡表，并用表上作业法求解）。
第4章 目标规划● 基本概念偏差变量：用以表示实际值与超出或未达到目标值的差距的变量称为偏差变量； 正偏差变量：超出目标的差距称为正偏差变量；负偏差变量：未达到目标值的差距称为负偏差变量；优先级：对两个不同目标，如果其重要程度相差悬殊，为达到一个目标甚至可以牺牲另一目标，可将它们划分属不同优先级。
优先级是一个定性概念，规定：P k >>P k+1权系数：在同一优先级内，根据重要程度不同，用权系数确定其优先顺序。
权系数是一个具体的数字。
● 数学建模 建模步骤：（1）确定优先因子（2）列出目标要求（不等式）（3）约束转换（加减负正偏差变量变为等式）（4）由目标要求确定目标值偏差（允许超过目标：负偏差最小；允许不完成：正偏差最小；要求准确完成：正、负偏差之和最小）（5）将目标值偏差组合起来，加上系统约束和目标约束及变量非负约束构成目标规划数学模型●练习题：1．某广播电台每天开播12小时，其中广告节目用以赢利，每分钟可收入500元，新闻节目每分钟需支出50元，而音乐节目每分钟支出20元，依据规定：正常情况下广告节目不超过广播时间的15%，每小时至少安排5分钟的新闻节目，试问该电台每天应如何安排广播节目？其优先级如下：P1——满足规定要求，P2——每天的纯收入达到1千元并力争超过。
试建立此问题的目标规划模型（不求解）。
2．某公司计划生产甲、乙两种产品，它们分别要经过设备A和设备B两道工序的加工，其所需工时定额如下表：系统约束：两种设备已满负荷，不能加班。
目标要求：P1：盈利达到150元，并尽可能地超过；P2：两种产品的产量之和尽可能超过10千克；P3：产品乙不少于6千克。
试建立此问题的数学模型（不求解）第6章图与网络模型●基本概念图：点和连线的集合.不带箭头的连线称为边(edge).带箭头的连线称为弧(Arc).无向图：连线不带箭头的图,用为:G={V,E}式中：V={v1,v2,…}，E={e1,e2,…} 表示.（如图a）.有向图：连线带箭头的图,用D={V,A}表示,（如图b）边相邻：两条边有公共的端点点相邻：两点有公共的关联边环：两端点相重的边.多重边：两条以上边所连的端点相重简单图：无环、无多重边的图次(度)：某一点具有的关联边的数目孤立点：次为“0”的点, 悬挂点：次为“1”的点悬挂边：与悬挂点相连的边 奇点：次为奇数的点 偶点：次为偶数的点; 链：点、边的交错序列. 圈(或称路) ：封闭的链连通图：任两点至少存在一条链.基础图：有向图去掉箭头就变成了无向图,此无向图称为该有向图的基础图. 树：一个无圈的连通图称为树.● 基本方法最小支撑树的避圈法与破圈法。
最短路的dijkstra 标号算法。
最大流的Ford-Fulkerson 标号算法。
中国邮路问题：结论1:若无奇点,则邮递员可以走遍所有街道,做到每条街道只走一次而不重复. 结论2:(1)有奇点的连线的边最多重复一次;(2)在该网络图的每个回路上,有重复的边的长度不超过回路总长的一半.● 练习题1.用避圈法或破圈法求下图所示最小支撑树。
2.用dijkstra 标号算法求上图所示从v1到v8的最短路。
3.如图，圆圈代表网络节点，节点间的连线表示它们间有网线相连，连线上的数表示该网线传送10兆字节的信息所用时间(单位：秒)。
现需从点s 向点t 传送10兆字节的信息，问至少需多少时间？4v 454 33v 7v 8v 3v 5v 2 v 1v 62422222834.用Ford-Fulkerson标号算法求上图所示从s到t的网络最大流。
第8章对策论●对策模型三要素局中人、策略集、赢得矩阵●二人零和对策的条件：（1）有两个局中人；（2）每个局中人的策略都是有限的；（3）每一策略组合下，各局中人赢得之和始终为零。
●对策模型的假设前提：（1）对策双方的行为是理智的；（2）局中人选取策略的目标是收益最大或损失最小；（3）局中人同时选取各自的行动策略，且不知道对方选取哪一个策略；（4）对策中的有关规定和要求，局中人是知道的。
