2015年运筹学复习资料
运筹学复习
一、 填空题
1、线性规划中，满足非负条件的基本解称为基本可行解，对应的基称为可行基线.
2、性规划的目标函数的系数是其对偶问题的右端常数；而若线性规划为最大化问题，则
3、对偶问题为最小化问题。
4、在运输问题模型中，1m n +-个变量构成基变量的充要条件是不含闭回路。
5、动态规划方法的步骤可以总结为：逆序求解最优目标函数，顺序求__最优策略、最优路线和最优目标函数值。
6、工程路线问题也称为最短路问题，根据问题的不同分为定步数问题和不定步数问题；
7、对不定步数问题，用迭代法求解，有函数迭代法和策略迭代法两种方法。
8、在图论方法中，通常用点表示人们研究的对象，用边表示对象之间的某种联系。
9、一个无圈且连通的图称为树。
10、图解法提供了求解只含有两个决策变量的线性规划问题的方法．
11、图解法求解生产成本最小线性规划问题时，等成本线越往左下角移动，成本越低．
12、如果线性规划问题有有限最优解，则该最优解一定在可行域的边界上上达到。
13、线性规划中，任何基对应的决策变量称为基变量．
14、原问题与对偶问题是相互对应的． 线性规划中，对偶问题的对偶问题是原问题．
15、在线性规划问题中，若某种资源的影子价格为10，则适当增加该资源量，企业的收益将_会 (“会”或“不会”)提高．
16、表上作业法实质上就是求解运输问题的单纯形法．
17、产销平衡运输问题的基变量共有m+n-1个．
18、动态规划不仅可以用来解决和时间有关的多阶段决策问题，也可以处理与时间无关的多阶段决策问题．
19、构成动态规划模型，需要进行以下几方面的工作：正确选择阶段（k ）变量，正确选择状态（Sk ）变量，正确选择_ 决策（UK ）变量，列出状态转移方程, 列出_阶段指标函数_，建立函数基本方程．
20、动态规划方法可以用来解决和某些与时间有关的问题，但也可以用来解决和某些与时间无关的问题.在图论方法中，图是指由点与边和点与弧组成的示意图．
21、网络最短路径是指从网络起点至终点的一条权之和最小的路线．
简述单纯形法的计算步骤：
第一步：找出初始可行解，建立初始单纯形表。
第二步：判断最优，检验各非基变量 的检验数 。
1若所有的 ，则基B 为最优基，相应的基可行解即为基本最优解，计算停止。
2若所有的检验数 ，又存在某个非基变量的检验数所有的 ，则线性规划问题有无穷多最优解。
3若有某个非基变量的检验数 ，并且所对应的列向量的全部分量都非正，则该线性规划问题的目标函数值无上界，既无界解，停止计算。
第三步：换基迭代
（1） 当存在 ，选 进基来改善目标函数。若检验数大于0的非基变量不止一个，则可以任选其中之一来作为进基变量。
（2） 进基变量 确定后，按最小比值原则选择出基变量 。若比值最小的不止一个，选择其中之一出基。（3）做主元变换。
反复进行上述过程就可以找到最优解或判断出没有有限最优解。
二、 选择题
1.甲、乙、丙、丁四个球队进行比赛，任两个队都有一场比赛，且没有和局，用来表示这四个队比赛状况的图是（ D ）。
A 、一棵树
B 、没有圈
C 、连通图
D 、任两点之间有一条带有方向的线
2．minZ=3x 1+4x 2, x 1+x2≥4, 2x1+x2≤2, x1、x2≥0，则（ A ）。
A.无可行解
B.有唯一最优解
C.有多重最优解
D.有无界解
3．互为对偶的两个线性规划问题的解存在关系（ D ）。
A.原问题无可行解，对偶问题也无可行解
B.对偶问题有可行解，原问题也有可行解
C.若最优解存在，则最优解相同
D.一个问题有无界解，则另一个问题无可行解
5．如果某种资源的影子价格大于其市场价格，则说明（ B ）。
A ．该资源过剩
B ．该资源稀缺
C ．企业应尽快处理该资源
D ．企业应充分利用该资源，开僻新的生产途径
6. 运输问题中分配运量的格所对应的变量为 （ A ）。
A 基变量
B 非基变量
C 松弛变量
D 剩余变量
7．maxZ=4x1-x2, 4x1+3x2≤24, x2≤5, x1、x2≥0，则（ B ）。
A.无可行解
B.有唯一最优解
C.有多重最优解
D.有无界解
8．对偶单纯形法的最小比值规划则是为了保证（ D ）。
A.使原问题保持可行
B.逐步消除对偶问题不可行性
C.使原问题有最优解
D.使对偶问题保持可行
9. 线性规划模型不包括下列（ D ）要素。
A．目标函数 B．约束条件 C．决策变量 D．状态变量
10.在约束方程中引入人工变量的目的是（ D ）。
A 体现变量的多样性
B 变不等式为等式
C 使目标函数为最优
D 形成一个单位阵
11. 求目标函数为极大的线性规划问题时，若全部非基变量的检验数≤O，且基变量中有人工变量时该问题有（ B ）。
A无界解 B无可行解 C 唯一最优解 D无穷多最优解
12.线性规划最优解不唯一是指（ D ）。
A.可行解集合无界
B.存在某个检验数λk>0且aik≤0(i=1,2,?,m)
C.可行解集合是空集
D.最优表中存在非基变量的检验数为零
13.minZ=4x1+6x2，4x1+3x2≤24，x2≥9，x1，x2≥0，则（ A ）。
A.无可行解
B.有唯一最优解
C.有无界解
D.有多重解
14.原问题有5个变量3个约束，其对偶问题（ C ）。
A.有3个变量3个约束
B.有5个变量3个约束
C.有3个变量5个约束
D.有5个变量5个约束
15.下列错误的结论是（ B ）。
A.原问题没有最优解，对偶问题也没有最优解
B.对偶问题有可行解，原问题也有可行解
C.原问题有最优解，对偶问题也有最优解
D.原问题无界解，对偶问题无可行解
16.maxZ=3x1+2x2,2x1+3x2≤14,x1+0.5x2≤4.5,x1,x2≥0且为整数，对应线性规划的最优解是（3.25，2.5），它的整数规划的最优解是（ A ）。
A．(4，1) B．(4，3) C．(3，2) D．(2，4)
19．若线性规划存在可行解，则（ B ）。
A.一定有最优解
B.可行域非空
C.有多重解
D.具有无界解
20．有4个产地5个销地的平衡运输问题模型具有特征（ C ）。
A.有9个变量9个约束
B.有9个变量20个约束
C.有20个变量9个约束
D.有9个基变量
21．互为对偶的两个线性规划问题的解存在关系（ D ）。
A.若最优解存在，则最优解相同
B.原问题无可行解，对偶问题也无可行解
C.一个问题无界，则另一个问题也无界
D.若最优解存在，则最优值相同
22．在分枝定界法中（ B ）。
A.最大值问题的目标值是各分枝的下界
B.最大值问题的目标值是各分枝的上界
C.最小值问题的目标值是各分枝的上界
D.以上结论都不对
23．对于线性规划标准型下例错误的说法是（ C ）。
A.标准型的目标函数是求最大值
C.标准型的常数项非正 B.标准型的目标函数是求最小值
D.标准型的变量一定要非负
24．表上作业法中初始方案均为（A ）。
A 可行解
B 非可行解
C 待改进解
D 最优解
25．minZ=3x1+4x2，x1+x2≥4，2x1+x2≤2，x1、x2≥0，则（A ）。
A．无可行解 B．有唯一最优解 C．有多重最优解 D．有无界解
26. 下列方法中用于求解分配问题的是（ D ）。
A．单纯形表B．分枝定界法C．表上作业法D．匈牙利法
27．minZ=x1-x2，2x1+x2≥1，x1+4x2≤4，x1，x2=0或1，最优解是（ B ）。
A．(0,0） B．(0,1） C．(1,0） D．(1,1)
28、最早运用运筹学理论的是（ A ）
A 二次世界大战期间，英国军事部门将运筹学运用到军事战略部署
B 美国最早将运筹学运用到农业和人口规划问题上
C 二次世界大战期间，英国政府将运筹学运用到政府制定计划
D 50年代，运筹学运用到研究人口，能源，粮食，第三世界经济发展等问题上
29、下列哪些不是运筹学的研究范围（ D ）
A 质量控制
B 动态规划
C 排队论
D 系统设计
30、对于线性规划问题，下列说法正确的是（ D ）
A 线性规划问题可能没有可行解
B 在图解法上，线性规划问题的可行解区域都是“凸”区域
C 线性规划问题如果有最优解，则最优解可以在可行解区域的顶点上到达
D 上述说法都正确
31、下面哪些不是线性规划问题的标准形式所具备的（ C ）
A 所有的变量必须是非负的
B 所有的约束条件（变量的非负约束除外）必须是等式
C 添加新变量时，可以不考虑变量的正负性
D 求目标函数的最小值
32、在求解运输问题的过程中运用到下列哪些方法（ D ）
A 西北角法
B 位势法
C 闭回路法
D 以上都是
33、在用单纯形法求解线性规划问题时，下列说法错误的是（ D ）
A 如果在单纯形表中，所有检验数都非正，则对应的基本可行解就是
最优解
B 如果在单纯形表中，某一检验数大于零，而且对应变量所在列中没有正数，则线性规划问题没有最优解
C 利用单纯形表进行迭代，我们一定可以求出线性规划问题的最优解或是判断线性规划问题无最优解
D 如果在单纯形表中，某一检验数大于零，则线性规划问题没有最优解
34、为了在各住宅之间安装一条供暖管道，若要求所用材料最省，则应采用（ B ）。
A．求最大流量法 B.求最小支撑树法
C．求最短路线法 D.树的逐步生成法
35、下列图形中是一棵树的为：(B )
A B C D
36、若T是图G的最小支撑树，则（ C ）
A．T必唯一 B. G不一定是连通图
C．T中必不含圈 D.G中不含圈
三、判断题
1. 线性规划问题的每一个基本可行解对应可行域的一个顶点。( √ )
2. 如果在单纯形表中，所有的检验数都为正，则对应的基本可行解就是最优解。（×）
3. 在可行解的状态下，原问题与对偶问题的目标函数值是相等的。×
4．可行解集非空时,则在极点上至少有一点达到最优值。（×）
5．原问题具有无界解，则对偶问题不可行。（√）
6．互为对偶问题，或者同时都有最优解，或者同时都无最优解。（ .√）
7．求最小值问题的目标函数值是各分枝函数值的下界。（√）
8．对偶问题无可行解，原问题具有无界解。（×）
9．对偶问题具有无界解，则原问题无最优解。（ .√）
10．匈牙利法求解指派问题的条件是效率矩阵的元素非负。（√）
11．变量取0或1的规划是整数规划。（√）
12．图解法提供了求解线性规划问题的通用方法。×
13．产地数为3，销地数为4的平衡运输中，变量组{x11, x13, x22, x33, x34}可作为一组基变量。（×）
14. 在单纯形表中，基变量对应的系数矩阵往往为单位矩阵。√
15.若线性规划存在两个不同的最优解,则必有无穷个最优解。（√）
16．若原问题具有m个约束，则它的对偶问题具有m个变量。（√）
17．动态规划只是用来解决和时间有关的问题。（×）
18. 线性规划问题的最优解一定在可行域的顶点达到。（×）
19. 如果一个线性规划问题有可行解，那么它必有最优解。（×）
20. 用单纯形法求解一般线性规划时，当目标函数求最大值时，若所有的检验数Cj-Zj≤0，则问题达到最优。( .√ )
21．线性规划的最优解是可行解。（ .√）
22．运输问题一定存在最优解。（√）
23．人工变量出基后还可能再进基。（×）
24．对于一个动态规划问题，应用顺推法和逆推法可能会得到不同的最优解。（×）
25．线性规划可行域无界,则具有无界解。（×）
26. 对于线性规划的原问题和其对偶问题，若其中一个有最优解，另一个也一定有最优解。( √ )
27. 表上作业法实质上就是求解运输问题的单纯形法。( √ )
28. 指派问题的解中基变量的个数为m＋n。( × )
29. 整数规划的可行解集合是离散型集合。（√）
30. 在解静态规划模型时，线性与非线性规划中约束条件的个数，相当于动态规划中状态变量的维数。（ .√）
31．在用割平面法求解整数规划时，经过有限次迭代一定可以割出极点为整数的点。（√）
32.在任一图G中，当点集V确定后，树图是G中边数最少的连通图。（√）
三、填空
1.原问题的第1个约束方程是“=”型，则对偶问题相应的变量是自由变量。
2．可以作为表上作业法的初始调运方案的填有数字的方格数应为m+n-1 个(设问题中含有m个供应地和n个需求地)
3. 调运方案的调整是要在检验数出现负值的点为顶点所对应的闭回路内进行运量的调整。
4．用分枝定界法求极大化的整数规划问题时，任何一个可行解的目标函数值是该问题目标函数值的下界。
5．在0 - 1整数规划中变量的取值可能是 0或。
6. 分枝定界法一般每次分枝数量为 2 个。
7．线性规划题中，如果在约束条件中出现等式约束，我们通常用增加人工变量的方法来产生初始可行基。
8. 若线性规划问题有最优解，则最优解一定可以在可行域的顶点（极点）达到。
9. 如果原问题的某个变量无约束，则对偶问题中对应的约束条件应为等式。
10. 若X、Y分别是线性规划的原问题和对偶问题的可行解，则有CX ≤Yb。
11．如果线性规划的原问题增加一个约束条件，相当于其对偶问题增加一个变量。
12．按照表上作业法给出的初始调运方案，从每一空格出发可以找到且仅能找到 1 条闭回路。
13. 对于一个有n项任务需要有n个人去完成的分配问题，其解中取值为1的变量数为 n 个。
14.经由静态的数学规划模型转换为动态规划模型时，常取静态规划中变量的个数为动态规划的阶段数。
15、求支撑树有破圈法和避圈法两种方法。
大学运筹学课程知识点总结
1. 用图解法求解下列线性规划问题，并指出问题具有惟一最优解、无穷多最优解、无界解还 是 无可行解。 max Z = X i + X 2 6x i +10x 2 "20 * 5兰x 1兰10 【3乞X 2乞8 惟一最优解 最优点(10, 6)最优值Z 二16 戸 5 si = 10 / 2. 将下述线性规划问题化成标准形式。 min Z = -3x ^ 4X 2 - 2x ^ 5x 4 M x 1 - x 2 + 2x 3 - X 4 = -2 为中 X 2 — X3 + 2x 4 兰 14 （1） j - 2x 1 + 3x 2 + X 3 - X 4 A 2 1x1, x2, x3 H 0,x4无约束 解：令 z' = —Z ，X 4 =X 4 — x ； max z^ 3X ] - 4x ^ 2X 3 - 5x 4 5x 4 [—4X ] + X 2 - 2X 3 + x 4 - x ； = 2 j X ] + X 2 - X 3 + 2x 4 - 2x 4 十 X 5 = 14 |- 2x 1 + 3x 2 + X 3 - X 4 + x 4 - X e = 2 _X 1，X 2，X 3，X 4，X 4，X 5，X 6 k 0 3. 分别用图解法和单纯形法求解下述线性规划问题，并对照指出单纯形表中的各基可行解对应 、 、 1 、 1 ^2=? 0X|+1O Z 2-12O 护 ____________ 寸 v/ max Li 10
图解法中的可行域的哪个顶点。 max =10x
中南大学研究生入学考试运筹学考试大纲
中南大学2012年全国硕士研究生入学考试 《运筹学（B）》考试大纲 本考试大纲由商学院教授委员会于2011年7月7日通过。 I.考试性质 运筹学考试是为高等院校和科研院所招收硕士研究生而设置的具有选拔性质的入学考试科目，其目的是科学、公平、有效地测试学生掌握大学本科阶段运筹学的基本知识、基本理论，以及运用运筹学的原理、模型和方法分析和解决实际问题的能力，评价的标准是高等学校本科毕业生能达到的及格或及格以上水平，以保证被录取者具有基本的运筹学专业素质，并有利于高等院校和科研院所在专业上择优选拔。 II.考查目标 运筹学科考试涵盖线性规划基础、线性规划专题、整数规划、动态规划、图与网络分析、存贮论、决策论、排队论。要求考生： （1）准确地再认或再现学科的有关知识。 （2）准确、恰当地使用本学科的基本原理，正确理解和掌握学科的有关理论、模型、方法和应用。 （3）运用运筹学模型和方法，分析和解决实际问题。 （4）运用运筹学的原理、模型和方法，分析和解决经济管理领域常见决策问题，并给出经济学解析或管理策略。 Ⅲ.考试形式和试卷结构 1、试卷满分及考试时间 本试卷满分为150 分，考试时间为180 分钟 2、答题方式 答题方式为闭卷，笔试。 3、试卷内容结构 线性规划基础约25 % 线性规划专题约10 %
整数规划约10 % 动态规划约15 % 图与网络分析约15 % 存贮论约15 % 决策论约5 % 排队论约5 % Ⅳ.考查内容 一、线性规划基础 （一）线性规划及其数学模型 线性规划问题、线性规划数学模型、数学模型的事理含义、数学模型的解、线性规划数学模型的一般形式、线性规划问题求解过程。 （二）线性规划问题建模 资源合理利用问题、合理下料问题、运输问题、分派问题、投资方案选择问题等经济管理领域常见问题建模。 （三）线性规划图解法及其几何意义 图解法求解步骤、图解法几何意义、几种特殊的数学模型。 （四）线性规划单纯形法 单纯形法基本原理、线性规划数学模型的标准型、线性规划数学模型的规范型、最优解寻求过程、单纯形表迭代。 （五）单纯形的经济信息 最优决策变量的解、松弛变量的解、相关价值系数、影子（潜在）价格及其应用。 （六）单纯形理论分析 线性规划一般形式、数模的标准型形式、数模的规范型形式、入基的非基变量确定方法、出基的基变量确定方法、主元素确定、旋转运算过程、最优解确定方法等。 （七）单纯形法进一步讨论 线性规划数模的基本类型、两阶段法、大M法。
运筹学复习重点
运筹学复习重点 第1章线性规划与单纯形法 （1）化线形规划标准形的手法 （2）线性规划解的概念、解的情形、解的判定 （3）单纯形法的计算过程、迭代逻辑。 （4）熟练运用单纯形表求解问题；若给出单纯形表，要会解读，会基于单纯形法基本原理反推出表中一些参数。 （5）两阶段法、大M法 第2章对偶理论和灵敏度分析 （1）会写对偶问题，掌握对偶性质，原问题与对偶问题之间的关系。 （2）互补松弛定理的应用：知道一个问题的最优解，求另一个问题的最优解。（3）对偶单纯形法 （4）当目标函数系数和右端项变化时灵敏度分析的简便方法 第3章目标规划 （1）根据问题的特征和对多个目标的追求，通过引入偏离量，正确构建所需的目标规划数学模型 （2）会用图解法求目标规划的最优解或满意解 第4章整数规划 （1）分支定界法：如何构造分支子问题，如何更新目标函数最优值上下界，何时终止。 （2）割平面法：如何写对源约束方程；如何拆分、组装割平面方程；如何利用对偶单纯形法继续求解。 第5章无约束优化 （1）凸函数与凸规划的定义与判别 （2）一维搜索的0.618法基本原理和迭代过程 （3）无约束优化的最速下降法的基本原理、迭代过程 第6章约束极值优化 （1）可行下降方向的含义、满足什么代数条件、几何意义 （2）正确写出Kuhn-Tucker条件，理解K-T条件与最优解的关系 （3）利用Kuhn-Tucker条件，求出K-T点和最优解。
（4）外点法和内点法的基本原理、无约束优化目标函数的一般构造手法 第7章动态规划 （1）动态规划的基本原理和基本方程 （2）动态规划的逆推解法 （3）动态规划求静态规划问题的套路 第8章图与网络优化 （1）图的基本概念、树的基本性质、最小支撑树的求法 （2）求最短路的Dijkstra算法 （3）增广链的概念、用途，求网络最大流的标号法 第9章网络计划 （1）遵循网络计划图的绘制规则，正确画出网络计划图。 （2）会计算网络计划的各种时间参数，确定关键线路 （3）不同目标下网络计划优化的方法 第10章排队论 （1）排队系统基本性能指标的含义、关系 （2）泊松流与负指数分布的关系，排队系统中基本参数λ和μ含义的多维解读。（3）系统状态概率Pn的含义、它在推导系统基本性能指标中的基础地位，推导它自身所依据的状态转移图。 （4）标准M/M/1模型的系统状态概率、基本性能指标的表达式。 第11章对策论 （1）矩阵对策中鞍点、最优纯策略、对策的值 （2）矩阵对策的混合策略和图解法 （3）矩阵对策局中人各自对应的线性规划问题之间的关系（理解互补松弛定理在对策论中的应用） 第12章决策论 （1）风险决策的EMV准则，EOL准则，二者之间的关系 （2）多级风险决策的图形工具：决策树，以及基于决策树的EMV决策套路（3）会利用决策树计算抽样信息的期望价值、完全信息的期望价值 题型：计算题和证明题。计算量不大，不必带计算器，可带尺子画图。
(完整版)学习运筹学的体会与心得
学习运筹学的总结与心得体会古人云“夫运筹帷幄之中，决胜千里之外”，怀着对运筹学的憧憬与崇拜之情，这学期我选择了运筹学这门课程。通过学习，我知道了运筹学是一门具有多科学交叉特点的边缘科学，是一门以数学为主要工具，寻求各种问题最优方案的优化学科。 经过一个学期的学习，我们应该熟练地掌握、运用运筹学的精髓，用运筹学的思维思考问题，即：应用分析、试验、量化的方法，对实际生活中的人力、财力、物力等有限资源进行合理的统筹安排。本着这样的心态，在本学期运筹学课程将结束之际，我对本学期所学知识作出如下总结。 一、线性规划 线性规划解决的是：在资源有限的条件下，为达到预期目标最优，而寻找资源消耗最少的方案。而线性规划问题指的是在一组线性等式或不等式的约束下，求解一个线性函数的最大或最小值的问题。其数学模型有目标函数和约束条件组成。 解决线性规划问题的关键是找出他的目标函数和约束方程，并将它们转化为标准形式。解决线性规划问题的主要方法有：图解法、单纯型法、两阶段法、对偶单纯型法、计算机软件求解等方法。简单的设计2个变量的线性规划问题可以直接运用图解法得到。但是往往在现实生活中，线性规划问题涉及到的变量很多，很难用作图法实现，但是运用单纯形法记比较方便。单纯形法的发展很成熟应用也很广泛，在运用单纯形法时，需要先将问题化为标准形式，求出基可行解，列出单纯形表，进行单纯形迭代，当所有的变量检验数不大于零，且基变量中不含人工变量，计算结束。将所得的量的值代入目标函数，得出最优值。 利用单纯形表我们可以（1）直接找出基本可行解与对应的目标函数值；（2）通过检验数判断原问题解的性质以及是否为最优解。 每一个线性规划问题都有和它伴随的另一个问题，若一个问题称为原问题，则另一个称为其对偶问题，原问题和对偶问题有着非常密切的关系，以至于可以根据一个问题的最优解，得出另一个问题的最优解的全部信息。 对偶问题有：对称形式下的对偶问题和非对称形式下的对偶问题。非对称形式下的对偶问题需要将原问题变形为标准形式，然后找出标准形式的对偶问题。因为对偶问题存在特殊的基本性质，所以我们在解决实际问题比较困难时可以将其转化成其对偶问题进行求解。 在解决线性规划问题时，我们往往会在求出最优解后，对问题进行灵敏度分
运筹学期末试题
《运筹学》课程考试试卷( A卷) 专业：管理大类年级：2007考试方式：闭卷学分：3 考试时间：120 分钟
二、已知如下的运输问题（20分） 用表上作业法求该运输问题的最优调运方案 三、已知线性规划问题（15分） max z ＝3x1＋4x2 －x1＋2x2≤8 x1＋2x2≤12 2x1＋ x2≤16 x1, x2≥0 （1）写出其对偶问题 (2)若其该问题的最优解为，x 1*=20/3, x 2 *=8/3，试用对偶问题的性质，求对偶问题的最优解。 四、求如下图网络的最大流，并找出最小截集和截量。每弧旁的数字是（C ij ,f ij）(15分) v1（7，4）v3 （8，8）（3，1）（8，6） v s（3，3）（3，0）v t （9，4）（2，2）（9，6） v2（5，5）v4 五、用动态规划方法求解下列非线性规划问题(15分) max z ＝x1 x22x3 x1＋x2＋x3 =8 x j≥0 （j＝1,2,3）
六、用匈牙利法求解下列指派问题（10分） 有四份工作，分别记作A 、B 、C 、D 。现有甲、乙、丙、丁四人，他们每人做各项工作所需时间如下表所示，问若每份工作只能一人完成，每人只能完成一份工作，如 何分派任务，可使总时间最少？ 《运筹学》A 卷标准答案 一、解：(1)单纯形法 （10分） 建立模型：max z = 3x 1+4x 2 2x 1+x 2 ≤ 40 x 1 +3x 2≤30 xj ≥ 0 j = 1,2 首先，将问题化为标准型。加松弛变量x 3，x 4，得 ??? ??=≥=++=+++=4,...,1,030340 243max 42132121j x x x x x x x st x x z j 其次，列出初始单纯形表，计算最优值。 任务 人员 A B C D 甲 4 5 9 8 乙 7 8 11 2 丙 5 9 8 2 丁 3 1 11 4
运筹学课程总结
运筹学课程总结 总结内容： 一、运筹学简述 （一）运筹学定义 （二）运筹学工作步骤 （三）运筹学的应用 二、运筹学相关理论与方法 （一）线性规划 （二）运输问题 （三）目标规划 （四）整数规划 （五）动态规划 三、运筹学应用案例分析（用matlab求解）
一、运筹学简述 （一）运筹学的定义 运筹学是一门应用科学，至今还没有统一且确切的定义。莫斯和金博尔曾对运筹学的定义是：“为决策机构在对其控制下业务活动进行决策时，提供以数量化为基础的科学方法。”它强调科学方法，以量化为基础。 另一定义是：“运筹学是一门应用科学，它广泛应用现有的科学技术知识和数学方法，解决实际中提出的专门问题，为决策者选择最优决策提供定量依据。” 中国百科全书给出的定义是：“运筹学是用数学方法研究经济、民政和国防等部门在内外环境约束的条件下合理分配人力、物力、财力等资源，使实际系统有效运行的技术科学，它可以用来预测发展趋势，制定行动规划或优选可行方案。” 如论如何定义，都表明着，运筹学是为提供最优化方法、最佳解决方案的科学。 （二）运筹学的工作步骤 1、建立数学模型：认清目标和约束； 2、寻求可行方案：求解； 3、评估各个方案：解的检验、灵敏度分析等； 4、选择最优方案：决策； 5、方案实施：回到实践中； 6、后评估：考察问题是否得到完满解决。 （三）运筹学的应用 运筹学在各个领域的应用非常广泛，主要有以下几个方面： 1、生产计划：生产作业的计划、日程表的编排、合理下料、配料问题、物料管理等； 2、库存管理：多种物资库存量的管理，库存方式、库存量等； 3、运输问题：确定最小成本的运输线路、物资的调拨、运输、工具的调度
运筹学考试重点(精简后的)
运筹学考试重点 考试题型： 1、填空题30分 2、判断题10分 3、原问题转化为对偶问题10分/15分 4、M 法单纯线性规划计算20分/15分 5、图解法、单纯性法计算30分 绪论 运筹学的工作步骤——P3 （1）提出和形成问题；（2）建立模型；（3）求解；（4）解的检验；（5）解的控制；（6）解的实施。 运筹学模型的三种基本形式——P3 (1)形象模型；(2)模拟模型；(3)符号或数学模型,目前用得最多的是符号或数学模型。 线性规划的三个特征——P9（ 必考） （1）每一个问题都用一组决策变量（x 1，x 2，x 3，……x n ）表示某一方案，这组决策变量的值就代表一个具体方案。一般这些变量取值是非负且连续的。 （2）存在有关的数据，同决策变量构成互不矛盾的约束条件，这些约束条件可以用一组线性等式或线性不等式来表示。 （3）都有一个要求达到的目标，它可用决策变量及其有关的价值系数构成的线性函数（称为目标函数）来表示。按问题的不同，要求目标函数实现最大化或最小化。 线性规划的数学模型（一般式形式），以及c j 、a ij 、b i 含义、——P10 m ax (min)Z=c 1x 1＋c 2x n +……c n x n ——目标函数，c j 为价值系数； a 11x 1＋a 12x 2＋……a 1n x n ≤（=,≥）b 1 ——约束条件 a 21x 1＋a 22x 2＋……a 2n x n ≤（=,≥）b 2 ——约束条件 ……………………… a m1x 1＋a m2x 2＋……a mn x n ≤（=,≥） b m ——约束条件 x 1 , x 2 …… x n ≥0 ——变量的非负约束条件 a ij 技术系数， b i 限额系数 勃兰特规则：1）选取Cj-Zj ＞0中下标最小的非基变量X k 为换入变量。即 () 0min ＞j j z c j k -=。 2）当按θ规则计算存在两个和两个以上最小比值时，选择下标最小 的基变量为换出变量。 线性规划问题的所有可行解构成的集合为 凸集 集合，也可能为 无界域 集合，它有有限个顶点，每个顶点对应于线性规划问题的 基可行解 ，若它有最优解，则必在集
运筹学期末考试题
二、单项选择题（每题3分，共15分） 1、 下面哪一个表达式可以作为目标规划的目标函数 A 、{}-++11min d d B 、{} -++11max d d C 、{}-+-11min d d D 、{} -+-11max d d 2、 线性规划问题可行域的每一个顶点，对应的是一个 。 A 、基本可行解 B 、非可行解 C 、最优解 D 、基 本解 3、 在整数规划割平面方法最终单纯形表中得到的一个各变量之间关系式为 5 8 4154321=+-x x x ，则其确定的割平面方程为 。
A 、53415132-≤+-x x B 、53435132-≤+-x x C 、53415132-≥--x x D 、53415132-≤--x x 4、 已知某个含10个节点的树，其中9个节点的次为1，1，3，1，1，1，3，1，3，另一个节点的次为 。 A 、1 B 、4 C 、3 D 、2 5、 用标号法寻找网络最大流时，发生标号中断（没有增广链），这时若用V 表 示已标号的节点的集合，用V 表示未标号的节点集合，则在网络中所有V → V 方向上的弧有 。（f 为当前流，c 为弧的容量） A 、 f c ≥ B 、c f ≤ C 、c f = D 、0=f 三、已知线性规划问题（第一问8分，第二问7分，共15分） ??? ??≥≤≤-+-=++-+-=无约束 321 3 21321321,0,064 22min x x x x x x x x x x x x z （1） 写出其对偶问题。 （2） 其原问题的最优解为1,0,5321-==-=x x x ，根据对偶性质直接求解 对偶问题的最优解。 四、（共20分，其中第1、3问各7分，第2问6分） 某厂用两种原材料生产 两种产品，已知数据见表1，根据该表列出的数学模型如下，加松弛变量，
大学运筹学课程知识点总结
1. 2. 3.用图解法求解下列线性规划问题，并指出问题具有惟一最优解、无穷多最优解、无界解还是无可行解。 ?? ???≤≤≤≤≤++=8 3105120106max 21212 1x x x x x x z 2.将下述线性规划问题化成标准形式。 （1）?????? ?≥≥-++-≤+-+-=-+-+-+-=无约束 4,03,2,12321422245243min 43214 32143214 321x x x x x x x x x x x x x x x x x x x x z 解：令z z -='，' '4' 44x x x -=
???????≥=-+-++-=+-+-+=-+-+-+-+-=0,,,,,,23214 2222455243'max 6 5''4'43216' '4'43215''4'4321''4'4321' '4'4321x x x x x x x x x x x x x x x x x x x x x x x x x x x x x z 3.分别用图解法和单纯形法求解下述线性规划问题，并对照指出单纯形表中的各基可行解对应图解法中的可行域的哪个顶点。 ??? ??≥≤+≤++=0,825943510max 2 121212 1x x x x x x x x z 解：①图解法： ②单纯形法：将原问题标准化： ??? ??≥=++=+++=0,,,825943510max 4213 212 1x x x x x x x x x x x x z C j 10 5 θ 对应图解法
单纯型法步骤：转化为标准线性规划问题；找到一个初始可行解，列出初始单纯型表；最优性检验，求cj-zj ，若所有的值都小于0，则表中的解便是最优解，否则，找出最大的值的那一列，求出bi/aij ，选取最小的相对应的xij ，作为换入基进行初等行变换，重复此步骤。 4.写出下列线性规划问题的对偶问题。 （1）()()()?? ???? ?????==≥===== ∑∑∑∑====n j m i x n j b x m i a x t s x c z ij j m i ij i n j ij m i n j ij ij ,,1;,,10 ,,1,,1..min 11 11 ()?????==≤++=+=+=∑∑无约束 j i ij j m i n i m j j m i i i y x n j m i c y y t s y b y a w ,,,1;,,1..max 1 1
运筹学复习资料
《运筹学》综合复习资料 一、判断题 1、LP 问题的可行域是凸集。 2、LP 问题的基可行解对应可行域的顶点。 3、LP 问题的最优解一定是可行域的顶点,可行域的顶点也一定是最优解。 4、若LP 问题有两个最优解,则它一定有无穷多个最优解. 5、求解LP 问题时,对取值无约束的自由变量，通常令"-'=j j j x x x ,其中∶0≥" ' j j x x , 在用单纯形法求得的最优解中,有可能同时出现0>" ' j j x x . 6、在PERT 计算中，将最早节点时刻等于最迟节点时刻、且满足0)(),()(=--i t j i t j t E L 节点连接而成的线路是关键线路 7、在一个随机服务系统中，当其输入过程是一普阿松流时，即有 (){}()t n e n t n t N P λλ-==! ， 则同一时间区间，相继两名顾客到达的时间间隔是相互独立且服从参数为λ的负指数分 布，即有()t e t X p λλ-== 8、分枝定界求解整数规划时,分枝问题的最优解不会优于原(上一级)问题的最优解. 9、对偶问题的对偶问题一定是原问题。 10、运输问题是一种特殊的LP 问题，因而其求解结果也可能会有唯一的最优解或无穷多个最优解。 11、动态规划中，定义状态变量时应保证在各个阶段中所做决策的相互独立性。 12、用割平面法求解整数规划时，每次增加一个割平面／线性约束条件后，在新的线性规划可行域中，除了割去一些不属于整数解的可行解外，还割去了上级问题不属于整数解的最优解。 13、在求解目标规划时，遵循的基本原则就是在考虑低级目标时，不能破坏已经满足的高级目标。 14、根据对偶问题的性质，当原问题为无界解时，其对偶问题无可行解，反之，当对偶问题无可行解时，其原问题具有无界解。
《运筹学》-期末考试-试卷A-答案
《运筹学》-期末考试-试卷A-答案
《运筹学》试题样卷（一） 题号一二三四五六七八九十总 分 得 分 一、判断题（共计10分，每小题1分，对的打√，错的打X） 1.无孤立点的图一定是连通图。 2.对于线性规划的原问题和其对偶问题，若 其中一个有最优解， 另一个也一定有最优解。 3.如果一个线性规划问题有可行解，那么它必有最优解。 4．对偶问题的对偶问题一定是原问题。 5．用单纯形法求解标准形式（求最小值）的线性规划问题时，与0>jσ对应的变量都可以被选作换入变量。 6．若线性规划的原问题有无穷多个最优解时，其对偶问题也有无穷 多个最优解。 7. 度为0的点称为悬挂点。 8. 表上作业法实质上就是求解运输问题的单纯形法。 9. 一个图G 是树的充分必要条件是边数最 少的无孤立点的图。 10.任何线性规划问题都存在且有唯一的对 ①②③④⑤⑥⑦⑧⑨ 二、建立下面问题的线性规划模型（8分） 某农场有100公顷土地及15000元资金可用于发展生产。农场劳动力情况为秋冬季3500人日；春夏季4000人日。如劳动力本身用不了
时可外出打工，春秋季收入为25元 / 人日，秋冬季收入为20元 / 人日。该农场种植三种作物：大豆、玉米、小麦，并饲养奶牛和鸡。种作物时不需要专门投资，而饲养每头奶牛需投资800元，每只鸡投资3元。养奶牛时每头需拨出1.5公顷土地种饲料，并占用人工秋冬季为100人日，春夏季为50人日，年净收入900元 / 每头奶牛。养鸡时不占用土地，需人工为每只鸡秋冬季0.6人日，春夏季为0.3人日，年净收入2元 / 每只鸡。农场现有鸡舍允许最多养1500只鸡，牛栏允许最多养200头。三种作物每年需要的人工及收入情况如下表所示： 大豆 玉米 麦子 秋冬季需人日数 春夏季需人日数 年净收入（元/公顷） 20 50 3000 35 75 4100 10 40 4600 试决定该农场的经营方案，使年净收入为最大。 三、已知下表为求解某目标函数为极大化线性规划问题的最终单纯形表，表中54,x x 为松弛变量，问题的约束为 形式（共8分）
大学运筹学课程知识点总结
1.用图解法求解下列线性规划问题，并指出问题具有惟一最优解、无穷多最优解、无界解还是无可行解。 ?? ???≤≤≤≤≤++=8 3105120106max 21212 1x x x x x x z 2.将下述线性规划问题化成标准形式。 （1）?????? ?≥≥-++-≤+-+-=-+-+-+-=无约束 4,03,2,12321422245243min 43214 32143214 321x x x x x x x x x x x x x x x x x x x x z 解：令z z -='，' '4'44x x x -= ???????≥=-+-++-=+-+-+=-+-+-+-+-=0,,,,,,23214 2222455243'max 6 5''4'43216' '4'43215' '4'4321''4'4321' '4'4321x x x x x x x x x x x x x x x x x x x x x x x x x x x x x z 3.分别用图解法和单纯形法求解下述线性规划问题，并对照指出单纯形表中的各基可行解对应
图解法中的可行域的哪个顶点。 ??? ??≥≤+≤++=0,825943510max 2 121212 1x x x x x x x x z 解：①图解法： ②单纯形法：将原问题标准化： ??? ??≥=++=+++=0,,,825943510max 4 3214213 212 1x x x x x x x x x x x x z C j 10 5 0 0 θ 对应图解法中的点 C B B b x 1 x 2 x 3 x 4 0 x 3 9 3 4 1 0 3 O 点 0 x 4 8 [5] 2 0 1 8/5 σj 0 10 5 0 0 0 x 3 21/5 0 [14/5] 1 -3/5 3/2 C 点 10 x 1 8/5 1 2/5 0 1/5 4 σj -16 0 1 0 -2 5 x 2 3/2 0 1 5/14 -3/14 B 点 10 x 1 1 1 0 -1/7 2/7 σj 35/2 -5/14 -25/14 最优解为（1,3/2,0,0），最优值Z=35/2。
物流运筹学答案 期末复习重点
1、某车间有两台机床甲和乙，可用于加工三种工件。假定这两台机床的可用台时数分别为700和800，三种工件的数量分别为300、500和400，且已知用三种不同机床加工单位数量的不同工件所需的台时数和加工费用（如下表所示），问怎样分配机床的加工任务，才能既满足加工工件的要求，又使总加工费用最低？ 机床加工情况表 机床类型单位工作所需加工台时数单位工件的加工费用可用台时数工件1 工件2 工件3 工件1 工件2 工件3 甲0.4 1.1 1.0 13 9 10 700 乙0.5 1.2 1.3 11 12 8 800 解：因使总加工费用最低（用min表示）故甲乙机床生产工件1、2、3分别设为x1、x2、x3、x4、x5、x6 则数学模型 列得目标函数：minz=13x1+9x2+10x3+11x4+12x5+8x6 s.t: x1+x4≥300 x2+x5≥500 x3+x6≥400 0.4x1+1.1x2+1.0x3≤700 0.5x4+1.2x5+1.3x6≤800 x1≥0 x2≥0 x3≥0 x4≥0 x5≥0 x6≥0 根据上图通过运筹管理软件解得： 答：甲型机床生产0件工件1 乙型机床生产300件工件1 甲型机床生产500件工件2 乙型机床生产0件工件2 甲型机床生产0件工件3 乙型机床生产400件工件3 加工费用最低为11000元
2. 解:根据题可知这是一个供需不平衡表，需要使产量和销量平衡。 MinF=15X11+15X12+20X13+20X14+20X15+15X21+40X22+15X23+30X24+30X25+25X31+3 5X32+40X33+55X34+25x35 求解，输入相应的软件里结果输出为：
《运筹学》复习参考资料知识点及习题
第一部分线性规划问题的求解 一、两个变量的线性规划问题的图解法： ㈠概念准备：定义：满足所有约束条件的解为可行解；可行解的全体称为可行（解）域。 定义：达到目标的可行解为最优解。 ㈡图解法： 图解法采用直角坐标求解：x1——横轴；x2——竖轴。1、将约束条件（取等号）用直线绘出； 2、确定可行解域； 3、绘出目标函数的图形（等值线），确定它向最优解的移动方向； 注：求极大值沿价值系数向量的正向移动；求极小值沿价值系数向量的反向移动。 4、确定最优解及目标函数值。 ㈢参考例题：（只要求下面这些有唯一最优解的类型） 例1：某厂生产甲、乙两种产品，这两种产品均需在A、B、C三种不同的设备上加工，每种产品在不同设备上加工所需的工时不同，这些产品销售后所能获得利润以及这三种加工设备因各种条件限制所能使用的有效加工总时数如下表所示： 问：该厂应如何组织生产，即生产多少甲、乙产品使得该厂的总利润为最大？ （此题也可用“单纯形法”或化“对偶问题”用大M法求解）
解：设x 1、x 2为生产甲、乙产品的数量。 max z = 70x 1+30x 2 s.t. ???????≥≤+≤+≤+0 72039450555409321212121x x x x x x x x ， 可行解域为oabcd0，最优解为b 点。 由方程组 ???=+=+72039450 5521 21x x x x 解出x 1=75，x 2=15 ∴X * =??? ? ??21x x =（75，15） T ∴max z =Z *= 70×75+30×15=5700 ⑴ ⑵ ⑶ ⑷ ⑸、⑹
max z = 6x 1+4x 2 s.t. ???????≥≤≤+≤+0781022122121x x x x x x x ， 解： 可行解域为oabcd0，最优解为b 点。 由方程组 ???=+=+810 22 121x x x x 解出x 1=2，x 2=6 ∴X * =? ?? ? ??21x x =（2，6）T ∴max z = 6×2+4×6=36 ⑴ ⑵ ⑶ ⑷ ⑸、⑹
运筹学期末试题
一、判断题（共计10分，每小题1分，对的打√，错的打X） 1.无孤立点的图一定是连通图。 2.对于线性规划的原问题和其对偶问题，若其中一个有最优解， 另一个也一定有最优解。 3.如果一个线性规划问题有可行解，那么它必有最优解。 4．对偶问题的对偶问题一定是原问题。 5．用单纯形法求解标准形式（求最小值）的线性规划问题时，与 > j σ 对应的变量都可以被选作换入变量。 6．若线性规划的原问题有无穷多个最优解时，其对偶问题也有无穷 多个最优解。 7. 度为0的点称为悬挂点。 8. 表上作业法实质上就是求解运输问题的单纯形法。 9. 一个图G 是树的充分必要条件是边数最少的无孤立点的图。 二、建立下面问题的线性规划模型（8分） 某农场有100公顷土地及15000元资金可用于发展生产。农场劳动力情况为秋冬季3500人日；春夏季4000人日。如劳动力本身用不了时可外出打工，春秋季收入为25元/ 人日，秋冬季收入为20元/ 人日。该农场种植三种作物：大豆、玉米、小麦，并饲养奶牛和鸡。种作物时不需要专门投资，而饲养每头奶牛需投资800元，每只鸡投资3元。 养奶牛时每头需拨出1.5公顷土地种饲料，并占用人工秋冬季为100人日，春夏季为50人日，年净收入900元 / 每头奶牛。养鸡时不占用土地，需人工为每只鸡秋冬季0.6人日，春夏季为0.3人日，年净收入2元 / 每只鸡。农场现有鸡舍允许最多养1500只 三、已知下表为求解某目标函数为极大化线性规划问题的最终单纯形表，表中5 4 ,x x 为松弛变量，问题的约束为?形式（共8分）
(1)写出原线性规划问题；（4分） (2)写出原问题的对偶问题；（3分） (3)直接由上表写出对偶问题的最优解。（1分） 四、用单纯形法解下列线性规划问题（16分） 3212max x x x Z +-= s. t. 3 x 1 + x 2 + x 3 ≤ 60 x 1- x 2 +2 x 3 ≤ 10 x 1+ x 2- x 3 ≤ 20 x 1, x 2 , x 3 ≥0 五、求解下面运输问题。 （18分） 某公司从三个产地A 1、A 2、A 3 将物品运往四个销地B 1、B 2、B 3、B 4，各产地的产量、各销地的销量和各产地运往各销地每件物品的运费如表所示： 六、灵敏度分析（共8分） 线性规划max z = 10x 1 + 6x 2 + 4x 3 s.t. x 1 + x 2 + x 3 ≤ 100 10x 1 +4 x 2 + 5 x 3 ≤ 600 2x 1 +2 x 2 + 6 x 3 ≤ 300 x 1 , x 2 , x 3 ≥ 0 的最优单纯形表如下：
运筹学指派问题实验报告
运筹学实践报告指派问题
第一部分问题背景 泰泽公司（Tazer）是一家制药公司。它进入医药市场已经有12年的历史了，并且推出了6种新药。这6种新药中5种是市场上已经存在药物的同类产品，所以销售的情况并不是很乐观。然而，主治高血压的第6种药物却获得了巨大的成功。由于泰泽公司拥有生产治疗高血压药物的专利权，所以公司并没有遇到什么竞争对手。仅仅从第6种药物中所获得的利润就可以使泰泽公司正常运营下去。 在过去的12年中，泰泽公司不断地进行适量的研究和发展工作，但是却并没有发现有哪一种药物能够获得像高血压药物一样的成功。一个原因是公司没有大量投资进行创新研究开发的动力。公司依赖高血压药物，觉得没有必要花费大量的资源寻找新药物的突破。 但是现在泰泽公司不得不面对竞争的压力了。高血压药物的专利保护期还有5年1。泰泽公司知道只要专利期限一到，大量药品制造公司就会像秃鹰一样涌进市场。历史数据表明普通药物会降低品牌药物75%的销售量。 今年泰泽公司投入大量的资金进行研究和开发工作以求能够取得突破，给公司带来像高血压药物一样的巨大成功。泰泽公司相信如果现在就开始进行大量的研究和开发工作，在高血压药物专利到期之后能够发明一种成功药物的概率是很高的。作为泰泽公司研究和开发的负责人，你将负责选择项目并为每一个项目指派项目负责人。在研究了市场的需要，分析了当前药物的不足并且拜会了大量在有良好前景的医药领域进行研究的科学家之后，你决定你的部门进行五个项目，如下所示： Up项目：开发一种更加有效的抗忧郁剂，这种新药并不会带来使用者情绪的急剧变化。 Stable项目：开发一种治疗躁狂抑郁病的新药。 Choice项目：为女性开发一种副作用更小的节育方法。 Hope项目：开发一种预防HIV的疫苗。 Release项目：开发一种更有效的降压药。 对于这5个项目之中的任何一个来说，由于在进行研究之前你并不知道使用的配方以及哪种配方是有效的，所以你只能明确研究所要解决的疾病。 你还有5位资深的科学家来领导进行这5个项目。有一点你十分清楚，那就是科学家都是一些喜怒无常的人，而且他们只有在受到项目所带来的挑战和激励的时候才会努力工作。为了保证这些科学家都能够到他们感兴趣的项目中去，你为这个项目建立了一个投标系统。这5位科学家每个人都有1000点的投标点。 1一般来说，专利权保护发明的期限为17年。在1995年，GATT立法拓展专利权的保护期限到20年。在本案例之中，泰泽公司的高血压药物的注册时间是在1995年之前，所以专利权只能够保护这种药物17年。
运筹学基础复习要点
《运筹学基础》复习要点 一、基本概念与理论 1．任意多个凸集的交集还是凸集。 2．任意多个凸集的并集不一定是凸集 3．给定1R b ∈及非零向量n R a ∈，称集合}|{b x a R x H T n =∈=是n R 的一个超平面。 4．由超平面}|{b x a R x H T n =∈=的两个半平面 }|{b x a R x H T n ≥∈=+和}|{1b x a R x H T n ≤∈= 都是凸集。 5．设S 是凸集，S x ∈。若对任何z y S z S y ≠∈∈,,，以及任何10<<λ，都有 z y x )1(λλ-+≠，则称x 为S 的顶点。 6．如果一个LP 问题无界，则它的对偶问题必无可行解。 7．设w x ,分别为原始LP 问题、对偶问题的可行解，若b w x c T T =，则原始LP 问题、对偶问题的最优解分别为w x ,。 8.可行解x 是基本可行解的充分必要条件是x 的正分量，所对应的A 中列向量线性无关。 9.写出LP 问题的对偶问题 0..min ≥≥?????x b Ax x c t s T 的对偶问题是： 0..min ≥≤?????w c w A w b t s T T 10．设一个标准形式的LP 问题的基为B ，右端向量为b ，则对应的基本解是??? ? ??=-01b B x 。 11．线性规划问题的可行域是凸集。 12．设线性规划问题LP 为 0..min ≥=?? ? ??x b Ax t s x c T B 为一个基，对应的典式为 0..min 111≥=+?? ? ? ?-=---x b B Nx B x t s x b B c z N B T T B ζ 其中),0(1T N T B T c N B c -=-ζ 。
2012--2013运筹学期末考试试题及答案
楚大 2012---2013上学期 经济信息管理及计算机应用系 《运筹学》期末考试试题及答案 班级： 学号 一、单项选择题： 1、在下面的数学模型中，属于线性规划模型的为（ A ）。 ?????≥-≥-+=0Y ,X 1Y X 2.t .s Y X 3S min .B ?????≥≤+=0Y ,X 3XY . t .s Y X 4S max .A ?? ???≥≤-+=0Y ,X 2Y X .t .s Y X S max .C 22?????≥≥+=0Y ,X 3Y X .t .s XY 2S min .D 2、线性规划问题若有最优解，则一定可以在可行域的 （ A ）上 达到。 A ．顶点 B ．内点 C ．外点 D ．几何点 3、在线性规划模型中，没有非负约束的变量称为 （ C ） A ．多余变量 B ．松弛变量 C.自由变量 D ．人工变量 4、若线性规划问题的最优解同时在可行解域的两个顶点处达到，那 么该线性规划问题最优解为（ C ）。 A.两个 B.零个 C.无穷多个 D.有限多个 5、线性规划具有唯一最优解是指（ B ） A ．最优表中存在常数项为零 B ．最优表中非基变量检验数全部非零 C ．最优表中存在非基变量的检验数为零 D ．可行解集合有界 6、设线性规划的约束条件为
?????≥=++=++0,,422341 421321x x x x x x x x 则基本可行解为（ C ）。 A ．(0, 0, 4, 3) B ． (3, 4, 0, 0) C ．(2, 0, 1, 0) D ． (3, 0, 4, 0) 7、若运输问题已求得最优解，此时所求出的检验数一定是全部 （ D ） A 、小于或等于零 B ．大于零 C ．小于零 D ．大 于或等于零 8、对于m 个发点、n 个收点的运输问题，叙述错误的是( D ) A ．该问题的系数矩阵有m ×n 列 B ．该问题的系数矩 阵有m+n 行 C ．该问题的系数矩阵的秩必为m+n-1 D ．该问题的最优解必唯一 9、关于动态规划问题的下列命题中错误的是（ A ） A 、动态规划分阶段顺序不同，则结果不同 B 、状态对决策有影响 C 、动态规划中，定义状态时应保证在各个阶段中所做决策的相对独 立性 D 、动态规划的求解过程都可以用列表形式实现 10、若P 为网络G 的一条流量增广链，则P 中所有正向弧都为G 的 （ D ）
运筹学课程设计实验报告
运筹学课程设计实验报告
目录 ①线性规划（一） (3) 线性规划（二） (5) ②整数规划（一） (8) 整数规划（二） (9) ③目标规划 (11) ④运输问题（一） (20) 运输问题（二） (22) ⑤指派问题 (24) ⑥图与网络分析 最短路径 (26) 最大流量（一） (28) 最大流量（二） (31) ⑦网络计划（一） (33) 网络计划（二） (34)
（一）线性规划问题: 1.用EXCEL 表求解下面各题，并从求解结果中读出下面要求的各项，明确写出结果。例如：原问题最优解为X*=（4，2）T ① 原问题的最优解（包括决策变量和松弛变量）、最优值； ② 对偶问题的最优解； ③ 目标函数价值系数的变化范围； ④ 右端常数的变化范围。 解： 50 10521≤+x x 1 21≥+x x 42≤x 0 ,21≥x x 2 13max x x z + =
由报告可知，①原问题最优解为产品甲生产2台，产品乙生产4台，原问题有最优值，即总利润最大为14元。 ②对偶问题的最优解为影子价格由灵敏度表可知y*=（0.2，0，1） ③目标函数价值系数的变化范围是灵敏度分析表中的允许的增量和减量，0≤X 甲≤1.5, 2 ≤X乙≤1E+33。
④右端常数的变化范围为40≤bA ≤1E+80, -1E-29≤bB ≤6,0≤bC ≤5 2. ????? ? ?≥≤++≤++≤++++=0 ,,42010132400851030010289.223max 3213213213213 21x x x x x x x x x x x x x x x z （1）求解：① 原问题的最优解（包括决策变量和松弛变量）、最优值； ② 对偶问题的最优解； ③ 目标函数价值系数的变化范围； ④ 右端常数的变化范围。 解：
运筹学课程论文
运筹学案例建模、算法与分析 作者； 日期: 2012年02月29日 摘要: 先是对一个学期的课程学习的总结，然后是分别对“人力资源分配问题”和“最优投资策略问题”的两个案例的分析与建模，并得出其最优方案，以及对案例职场规划的方案设计。 关键词: 运筹学；数学模型；目标函数；人力资源分配；职场规划；最优投资策略。 正文: 记得当初怀着好奇和对数学的兴趣旋律这堂课，转眼一个学期结束了，时间见证了我当初的选择是正确的。在这儿，她让我学到了新的数学解题方法和思维方式；使我对数学的兴趣更加浓厚；当然，她还让我学到了很多有关运筹学方面的很多知识。 在“运筹帷幄-为解决问题提供最佳决策”这堂课上，老师通过“1.资环争夺——运筹学的摇篮；2.追求完美——运筹优化无处不在；3.制胜法宝——运筹学成功应用范例；4.寓理于算——运筹学问题数学模型；5.追求极致——最优决策的特征；6.好谋善断——优化方法设计；7.步步为营——迭代算法特征；8.神机妙算——计算机实现；9.追求效率——提高计算效率；10.永无止境——改善与发展”这十个话题，给我们讲解了运筹学的起源、特点、分支、研究方法、涉及重点领域，对运筹学应用案例的数学模型建立于分析，以及解决运筹学问题的方法和对待运筹学问题的大概思维方式等有关运筹学的各方面知识。总之，在这堂课上我收获许许多多有形或无形的财富，让我受益匪浅。 通过一个学期在老师生动详细的讲解，以及阅读一些有关运筹学的书籍等方式的学习下，我已经掌握了一些对问题进行分析、建模等处理方法。下面是对三个案例的简单分析及处理。
案例1： 人力资源分配问题 “好又美”超市是个建在大学城边上的大型百货商场，每周对收银人员的需求，统计如下表 为了保证收银人员充分休息，收银人员每周工作5天，休息2天。问应如何安排收银人员的工作时间，使得所配收银人员的总费用最小？ 解：为了让员工们休息更愉快、方便，可将每位员工的休息时间安排在连续的两天；则可设 i x （i=1,2,3，…，7)表示星期一至日开始休息的人数，依题 意我们可建立如下数学模型： 目标函数：Min Z = 1234567x x x x x x x ++++++ 约束条件： 1234x x x x x ++++≥6 23456 x x x x x ++++≥5 34567 x x x x x ++++≥8 45671x x x x x ++++≥7 56712x x x x x ++++≥10 67123x x x x x ++++≥18 71234 x x x x x ++++≥15 (1,2,3,4,5,6,7) i x N i ∈= 于以上数学模型，通过计算可得： 当：1x = 9；2x = 1；3x = 0；4x = 5；5x = 0；6x = 0；7x =3； 时，Z 取最小值18。 即安排18位收银人员即可供应百货商场收银员需求。 具体人员安排如下： 假设有18位收银人员编号分别为1、2、3、4、…、18，星期六18为收银