下载文档原格式
运筹学思考练习题答案第⼀章 L.P 及单纯形法练习题答案⼀、判断下列说法是否正确1. 线性规划模型中增加⼀个约束条件，可⾏域的范围⼀般将缩⼩，减少⼀个约束条件，可⾏域的范围⼀般将扩⼤。
(?)2. 线性规划问题的每⼀个基解对应可⾏域的⼀个顶点。
(?)3. 如线性规划问题存在某个最优解，则该最优解⼀定对应可⾏域边界上的⼀个点。
(?)4. 单纯形法计算中，如不按最⼩⽐值原则选取换出变量，则在下⼀个基可⾏解中⾄少有⼀个基变量的值为负。
(?)5. ⼀旦⼀个⼈⼯变量在迭代中变为⾮基变量后，该变量及相应列的数字可以从单纯形表中删除，⽽不影响计算结果。
(?)6. 若1X 、2X 分别是某⼀线性规划问题的最优解，则1212X X X λλ=+也是该线性规划问题的最优解，其中1λ、2λ为正的实数。
(?)7. 线性规划⽤两阶段法求解时，第⼀阶段的⽬标函数通常写为ai iMinZ x =∑(x ai 为⼈⼯变量)，但也可写为i ai iMinZ k x =∑，只要所有k i 均为⼤于零的常数。
(?)8. 对⼀个有n 个变量、m 个约束的标准型的线性规划问题，其可⾏域的顶点恰好为m n C 个。
(?)9. 线性规划问题的可⾏解如为最优解，则该可⾏解⼀定是基可⾏解。
(?)10. 若线性规划问题具有可⾏解，且其可⾏域有界，则该线性规划问题最多具有有限个数的最优解。
(?)⼆、求得L.P 问题121231425j MaxZ 2x 3x x 2x x 84x x 164x x 12x 0;j 1,2,,5=+++=??+=??+=?≥=的解如下： X ⑴=(0,3,2,16,0)T ;X ⑵=(4,3,-2,0,0)T ;X ⑶=(3.5,2,0.5,2,4)T ;X ⑷=(8,0,0,-16,12)T ; =(4.5,2,-0.5,-2,4)T ; X ⑹=(3,2,1,4,4)T ;X ⑺=(4,2,0,0,4)T 。
要求：分别指出其中的基解、可⾏解、基可⾏解、⾮基可⾏解。
运筹学：应用分析、试验、量化的方法，对经济管理系统中人力、物力、财力等资源进行统筹安排，为决策者提供有依据的最优方案，以实现最有效的管理。
第一章、线性规划的图解法1.基本概念线性规划：是一种解决在线性约束条件下追求最大或最小的线性目标函数的方法。
线性规划的三要素：变量或决策变量、目标函数、约束条件。
目标函数：是变量的线性函数。
约束条件：变量的线性等式或不等式。
可行解：满足所有约束条件的解称为该线性规划的可行解。
可行域：可行解的集合称为可行域。
最优解：使得目标函数值最大的可行解称为该线性规划的最优解。
唯一最优解、无穷最优解、无界解（可行域无界）或无可行解（可行域为空域）。
凸集：要求集合中任意两点的连线段落在这个集合中。
等值线：目标函数z，对于z的某一取值所得的直线上的每一点都具有相同的目标函数值，故称之为等值线。
松弛变量：对于“≤”约束条件，可增加一些代表没使用的资源或能力的变量，称之为松弛变量。
剩余变量：对于“≥”约束条件，可增加一些代表最低限约束的超过量的变量，称之为剩余变量。
2.线性规划的标准形式约束条件为等式（=）约束条件的常数项非负（b j≥0）决策变量非负（x j≥0）3.灵敏度分析：是在建立数学模型和求得最优解之后，研究线性规划的一些系数的变化对最优解产生什么影响。
4.目标函数中的系数c i的灵敏度分析目标函数的斜率在形成最优解顶点的两条直线的斜率之间变化时，最优解不变。
5.约束条件中常数项b i的灵敏度分析对偶价格：约束条件常数项中增加一个单位而使最优目标函数值得到改进的数量。
当某约束条件中的松弛变量（或剩余变量）不为零时，这个约束条件的对偶价格为零。
第二章、线性规划问题在工商管理中的应用1.人力资源分配问题（P41）设x i为第i班次开始上班的人数。
2.生产计划问题（P44）3.套材下料问题（P48）下料方案表（P48）设x i为按各下料方式下料的原材料数量。
4.配料问题（P49）设x ij为第i种产品需要第j种原料的量。
《运筹学》2014年秋学期在线作业（三）
一,单选题
1. （第6章)关于动态规划的如下说法中错误的是()；
A. 状态转移方程表明了各阶段之间状态的联系
B. 过程指标函数必须由阶段指标函数相加得到
C. 动态规划基本方程必须有边界条件
D. 动态规划中决策变量可以为连续变量也可以为离散变量
?
正确答案：B
2. (第5章)下列关于整数规划问题的说法，正确的是()；
A. 整数规划问题解的目标函数值优于其对应的线性规划问题的解的目标函数值
B. 部分变量都取整数的问题称之为纯整数规划问题
C. 全部变量都取整数的问题称之为纯整数规划问题
D. 分配问题不是整数规划问题
?
正确答案：C
3. 题目和选项如下图所示：
A.
B.
C.
D.
?
正确答案：B
4. (第5章)在用匈牙利法求解指派问题时，当独立零元素个数小于任务数（人数）时：下列说法正确的是()；
A. 用最少的直线划去所有的非独立的零元素
B. 剩余的元素非零元素都减去本行的最小元素
C. 为保证所有元素大于零，应在横线和竖线交汇格元素加上最小元素
D. 用最少的直线划去所有的独立零元素
?
正确答案：C
5. (第6章)用逆序法求解资源分配问题时，为保证独立性，状态变量取值一般为()；
A. 各阶段分配的资源数
B. 当前阶段开始时前部过程已分配的资源数
C. 当前阶段开始时剩余给后部过程的资源数
D. 资源的总数量
?。
第六章动态规划法• P137 2 ,3, 4•2.解答:cost[i]表示从顶点i 到终点n-1 的最短路径，path[i]表示从顶点i 到终点n-1 的路径上顶点i 的下一个顶点。
cost[i]=min{cij+cost[j]}3 有5 个物品，其重量分别是{3, 2, 1, 4,5}，价值分别为{25, 20, 15, 40, 50}，背包的容量为6。
V[i][j]表示把前i 个物品装入容量为j 的背包中获得的最大价值。
最优解为（0，0，1，0，1）最优值为65. 4.序列A =(x, z , y , z , z , y,x )，B =(z , x , y , y , z , x , z )，建立两个(m+1)×(n+1)的二 维表L 和表S ，分别存放搜索过程中得到的子序列的长度和状态。
z , x , y , y , z,x , z )path[i]= 使 cij+cost[j] 最小的 j i 012345678 9 10 11 12 13 14 15 Cost[i] 18 13 16 13 10 9 12 7 6875943Path[i]145778911 11 11 13 14 14 15 15 0得到最短路径 0->1->4->7->11->14->15 , 长度为 18(a)长度矩阵L(b)状态矩阵S 。
第七章贪心算法2.背包问题:有7 个物品，背包容量W=15。
将给定物品按单位重量价值从大到小排序，结果如下：个物品，物品重量存放在数组w[n]中，价值存放在数组放在数组x[n]中。
按算法7.6——背包问题1．改变数组w 和v 的排列顺序，使其按单位重量价值v[i]/w[i]降序排列；2．将数组x[n]初始化为0；//初始化解向量3．i=1;4．循环直到( w[i]>C )4.1 x[i]=1; //将第i个物品放入背包4.2 C=C-w[i];4.3 i++;5. x[i]=C/w[i];得出,该背包问题的求解过程为:: x[1]=1;c=15-1=14 v=6 x[2]=1; c=14-2=12V=6+10=10 x[3]=1; c=12-4=8V=16+18=34 x[4]=1; c=8-5=3V=34+15=49 x[5]=1; c=3-1=2 V=49+3=52x[6]=2/3 ; c=0; V=52+5*2/3=156/3 最优值为156/3 最优解为(1,1,1,1,1,2/3,0)) (x[i]按排序后物品的顺序构造)5.可以将该问题抽象为图的着色问题,活动抽象为顶点,不相容的活动用边相连(也可以将该问题理解为最大相容子集问题,重复查找剩余活动的最大相容子集,子集个数为所求).具体参见算法7.3 算法7.3——图着色问题1．color[1]=1; //顶点1着颜色12．for (i=2; i<=n; i++) //其他所有顶点置未着色状态color[i]=0;3．k=0;4．循环直到所有顶点均着色4.1k++; //取下一个颜色4.2for (i=2; i<=n; i++) //用颜色k 为尽量多的顶点着色4.2.1 若顶点i已着色，则转步骤4.2，考虑下一个顶点;4.2.2 若图中与顶点i邻接的顶点着色与顶点i着颜色k 不冲突，则color[i]=k;5．输出k;第八章回溯法4.搜索空间(a) 一个无向图(b) 回溯法搜索空间最优解为（1，2，1，2，3）5.0-1 背包问题n∑w i x i≤c 1• 可行性约束函数：i =1• 上界函数：nr =∑Vi5 = 3A B *CD8 ** * 131 =12 =23 = 14 = 2 34215课后答案网（）i=k+1 1第九章分支限界法5，解：应用贪心法求得近似解：(1,4,2,3)，其路径代价为：3+5+7+6=21，这可以作为该问题的上界。
教学基本文件模板课程教学大纲：《运筹学》课程教学大纲课程编号：课程名称：运筹学/Operational Research课程总学时/学分：72/4 （其中理论60学时，实验12学时）适用专业：适用本科四年制信息管理与信息系统专业一、课程简介本课程的授课对象是信息管理与信息系统专业本科生，属管理类专业专业基础必修课。
《运筹学》是以定量分析为主来研究经济管理问题，将工程思想和管理思想相结合，应用系统的、科学的、数学分析的方法，通过建模、检验和求解数学模型获得最优决策方案。
本课程的主要内容包括线性规划、运输问题、整数规划、目标规划、动态规划、网络分析等与经济、管理和工程领域密切相关的运筹学分支的基本模型、方法和应用。
运用科学的模型化方法来描述、求解和分析问题，从而支持决策。
二、教学目的和任务本课程旨在使同学们正确、全面地掌握各级管理工作中已被广泛应用、发展比较成熟的最优化理论与方法，并能运用所学理论和方法解决管理工作中出现的各种优化问题，为后续课程奠定定量分析基础。
在已学过高等数学、微积分、线性代数等课程基础上学习本课程，通过教授、自学、复习、作业练习、辅导、上机等教学环节达到上述目的。
学习中要注意到学科系统性，数学概念和逻辑的严密性、准确性和完整性，但不偏重纯数学方法论证。
注重基本概念、基本思路、基本方法、算法步骤的掌握，了解各种方法特点和实用价值，提高建立模型、分析求解能力和技巧。
应注重实际应用中建立模型，选择可行求解的理论方法，运用计算机工具求解这三方面训练的有机结合。
三、教学基本要求信息管理与信息系统专业的学生应系统地学习《运筹学》的全部内容。
系统掌握线性规划、运输问题、目标规划、整数规划、动态规划、图与网络分析的理论和方法；能借助Excel、Lingo等电子计算手段，运用所学理论和方法解决实际问题。
通过该课程的学习，进一步培养学生的分析问题和解决问题的能力。
四、教学内容与学时分配绪论（2学时）第一节运筹学的定义与发展简史1、运筹学名称的来历；2、运筹学的发展简史。
第6章 动态规划动态规划（Dynamic Programming ）是解决多阶段决策过程最优化的一种有用的数学方法。
它是由美国学者Richard .Bellman 在1951年提出的，1957年他的专著《动态规划》一书问世，标志着运筹学的一个重要分支－动态规划的诞生.动态规划也是一种将多变量问题转化为单变量问题的一种方法。
在动态规划中，把困难的多阶段决策问题变换成一系列相互联系的比较容易的单阶段问题一个个地求解。
动态规划是考察解决问题的一种途径 ,而不是一种特殊的算法，不像线性规划那样有统一的数学模型和算法（如单纯形法）.事实上，在运用其解决问题的过程中还需要运用其它的优化算法。
因此，动态规划不像其它方法局限于解决某一类问题,它可以解决各类多阶段决策问题。
动态规划在工程技术、经济管理等社会各个领域都有着广泛的应用，并且获得了显著的效果。
在经济管理方面,动态规划可以用来解决最优路径问题、资源分配问题、生产调度问题、库存管理问题、排序问题、设备更新问题以及生产过程最优控制问题等，是经济管理中一种重要的决策技术。
许多规划问题用动态规划的方法来处理,常比线性规划或非线性规划更有效。
特别是对于离散的问题，由于解析数学无法发挥作用，动态规划便成为了一种非常有用的工具。
动态规划可以按照决策过程的演变是否确定分为确定性动态规划和随机性动态规划；也可以按照决策变量的取值是否连续分为连续性动态规划和离散性动态规划。
本教材主要介绍动态规划的基本概念、理论和方法,并通过典型的案例说明这些理论和方法的应用。
6.1动态规划的基本理论6.1.1多阶段决策过程的数学描述有这样一类活动过程,其整个过程可分为若干相互联系的阶段，每一阶段都要作出相应的决策,以使整个过程达到最佳的活动效果。
任何一个阶段(stage ，即决策点)都是由输入(input ）、决策（decision ）、状态转移律（transformation function )和输出(output )构成的，如图6-1（a ）所示.其中输入和输出也称为状态(state ）,输入称为输入状态，输出称为输出状态。
由于每一阶段都有一个决策，所以每一阶段都应存在一个衡量决策效益大小的指标函数，这一指标函数称为阶段指标函数,用k v 表示.显然),(k k k u S v v =，如图6—1（b ）所示.显然，输出是输入和决策的函数，即：),(1k k k u S r S =+ (6-1）式(6—1）为状态转移方程。
在由n 个阶段构成的过程里，前一个阶段的输出即为后一个阶段的输入。
6。
1.2动态规划的基本概念动态规划的数学描述离不开它的一些基本概念与符号,因此有必要在介绍多阶段决策过程的数学描述的基础上，系统地介绍动态规划的一些基本概念。
（1）阶段、阶段变量阶段是过程中需要做出决策的决策点。
描述阶段的变量称为阶段变量，常用k 来表示。
阶段的划分一般是根据时间和空间的自然特征来进行的，但要便于将问题的过程转化为多阶段决策的过程。
对于具有n 个阶段的决策过程，其阶段变量k ＝1，2，…，n 。
（2）状态、状态变量状态表示每个阶段开始所处的自然状况或客观条件,它描述了研究问题过程的状况。
状态既反映前面各阶段系列决策的结局,又是本阶段决策的一个出发点和依据；它是各阶段信息的传递点和结合点。
各阶段的状态通常用状态变量Sk 来加以描述。
作为状态应具有这样的性质：如果某阶段状态给定后，则该阶段以后过程的发展不受此阶段以前各阶段状态的影响。
换句话说，过程的历史只能通过当前的状态来影响未来,当前的状态是以往历史的一个总结.这个性质称为无后效性(the future is independent of the past ）。
状态变量的取值有一定的允许集合或范围，此集合称为状态允许集合。
（3） 决策、决策变量过程的某一阶段、某个状态,可以做出不同的决定（选择)，决定下一阶段的状态，这种决定称为决策.描述决策的变量，称为决策变量.决策变量是状态变量的函数，常用u k （s k )表示第k 阶段当状态为s k 时的决策变量。
在实际问题中决策变量的取值往往在某一范围之内，此范围称为允许决策集合.常用D k (s k ）表示第k 阶段从状态s k 出发的允许决策集合，显然有 u k (s k ）∈D k （s k )（4)状态转移方程多阶段决策过程可以在各个阶段进行决策，去控制过程发展的多段过程；其发展是通过一系列的状态转移来实现的；系统在某一阶段的状态转移不但与系统的当前的状态和决策有关，而且还与系统过去的历史状态和决策有关。
其状态转移方程如下（一般形式)),,,,,,(),,,(),(221112*********k k k k u s u s u s T s u s u s T s u s T s===+能用动态规划方法求解的多阶段决策过程是一类特殊的多阶段决策过程，即具有无后效性的多阶段决策过程。
（5） 策略策略是一个按顺序排列的决策组成的集合。
由过程的第k 阶段开始到终止状态为止的过程,称为问题的后部子过程（或称为k 子过程)。
由每段的决策按顺序排列组成的决策函数序列称为k 子过程策略，简称子策略，记为)(,k n k s p ,即{})(,),(),()(11,n n k k k k k n k s u s u s u s p ++=当k=1时，此决策函数序列成为全过程的一个策略，简称策略,记为)(1,1s p n 即{})(,),(),()(22111,1n n n s u s u s u s p =在实际问题中，可供选择的策略有一定范围，此范围称为允许策略集合，用p 表示.从允许策略集合中找出达到最优效果的策略称为最优策略。
（6）函数和最优值函数用来衡量所实现过程优劣的一种数量指标，称为指标函数，它是定义在全过程或所有后部子过程上确定的数量函数.V k, n 表示之.即n k s u s u s V V n k k k k n k n k ,,2,1),,,,,,(111,, ==+++动态规划模型的指标函数，应具有可分离性，并满足递推关系。
即n k V ,可以表示为k s k u n k V ,1+的函数.即有如下式子)],,,(,,[),,,,,(111,1111,+++++++=n k k n k k k k n k k k k n k s u s V u s s u s u s V ϕ常见的指标函数的形式有以下两种情况：情形1 过程和它的任一子过程的指标是它所包含的各阶段的指标和。
即()()u s v s us V jjnkj jn kknk ,,,,1,∑=+=其中),(u s v j j j 表示第j 阶段的阶段指标。
情形2过程和它的任意子过程的指标是它所包含的各阶段的指标的乘积。
即),(),,,(1,u s v s u s V j j j nkj n k k n k =+∏=最优值函数:表示从第k 阶段的状态s k 开始到第n 阶段的终止状态的过程,采取最优策略所得到的指标函数值。
即{}),,,()(1,,,sus V opt sf n kknk kku u nk+=(7）多阶段决策过程的数学模型 具有无后效性的多阶段决策过程⎪⎪⎩⎪⎪⎨⎧-=∈∈==+=+∑1,,1,),(..),(),,,(111,},,,{21 n n k U u S s u s T s t s u s v s u s V opt k k kkk k k k nj j j j n k k n k u u u n所谓求解多阶段决策过程问题,就是要求出① 最优策略，即最优决策序列},,,{**2*1n u u u②最优目标函数值),,,,(***1*1*,1*,1n n n n u s u s V V =(){}()s us v opt s f n kkn k kku u nk1,,,,,,+= （6—2）6.1.3动态规划的数学模型动态规划的数学模型除包括式（6—2）外,还包括阶段的划分、各阶段的状态变量和决策变量的选取、允许决策集合和状态转移律的确定等。
如何获得最优指标函数呢?一个n 阶段的决策过程,具有如下一些特性: （1）刚好有n 个决策点；（2）对阶段k 而言，除了其所处的状态k S 和所选择的决策k u 外,再没有任何其它因素影响决策的最优性了；（3) 阶段k 仅影响阶段1+k 的决策,这一影响是通过1+k S 来实现的；（4）贝尔曼（Bellman )最优化原理：在最优策略的任意一阶段上，无论过去的状态和决策如何，对过去决策所形成的当前状态而言，余下的诸决策必须构成最优子策略。
根据贝尔曼（Bellman ）最优化原理，可以将式（6-2)表示为递推最优指标函数关系式（6—3）或式(6—4）：)}({}{)(111~++++=⊕⊕⊕=k k k u N k k u k k S f v opt v v v opt S f kNk (6—3） )}({}{)(111~+++⨯=⊗⊗⊗=k k k u N k k u k k S f v opt v v v opt S f kNk （6—4)利用式（6—3)和式(6-4）可表示出最后一个阶段(第n 个阶段，即k=n ）的最优指标函数:)}({)(11+++=n n n u n n S f v opt S f n（6—5))}({)(11++⨯=n n n u n n S f v opt S f n（6-6）其中)(11++n n S f 称为边界条件。
一般情况下，第n 阶段的输出状态1+n S 已经不再影响本过程的策略，即式（6-5）中的边界条件0)(11=++n n S f ，式（6-6）中的边界条件1)(11=++n n S f ；但当问题第n 阶段的输出状态1+n S 对本过程的策略产生某种影响时，边界条件)(11++n n S f 就要根据问题的具体情况取适当的值，这一情况将在后续例题中加以反映。
已知边界条件)(11++n n S f ，利用式（6-3）或式（6-4）即可求得最后一个阶段的最优指标函数)(n n S f ;有了)(n n S f ，继续利用式（6—3）或式(6—4）即可求得最后两个阶段的最优指标函数)(11--n n S f ；有了)(11--n n S f ，进一步又可以求得最后三个阶段的最优指标函数)(22--n n S f ;反复递推下去，最终即可求得全过程n 个阶段的最优指标函数)(11S f ，从而使问题得到解决。
由于上述最优指标函数的构建是按阶段的逆序从后向前进行的，所以也称为动态规划的逆序算法.通过上述分析可以看出，任何一个多阶段决策过程的最优化问题，都可以用非线性规划（特殊的可以用线性规划)模型来描述；因此，从原则上讲，一般也可以用非线性规划（或线性规划）的方法来求解。
