2019年春《运筹学》 期末考试复习题 ☆注意事项：本复习题满分共：400分。 一、单项选择题（本大题共28小题，每小题4分，共112分） 1、下列叙述正确的是（）。 A．线性规划问题，若有最优解，则必是一个基变量组的可行基解 B．线性规划问题一定有可行基解 C．线性规划问题的最优解只能在最低点上达到 D．单纯形法求解线性规划问题时，每换基迭代一次必使目标函数值下降一次 答案：A 2、数学规划的研究对象为（）。 A．数值最优化问题 B．最短路问题 C．整数规划问题 D．最大流问题 答案：A 3、下列方法中可以用来求解部分树的方法的为（）。 A．闭回路法 B．破圈法 C．踏石法 D．匈牙利算法 答案：B 4、把各种备选方案、可能出现的状态和概率以及产生的后果绘制在一张图上，称为（）。A．决策树 B．最大流 C．最小支撑树 D．连通图 答案：A 5、以下说法中，不属于无概率决策问题（不确定型决策问题）的特点的为（）。 A．决策人面临多种决策方案 B．对每个决策方案对应的几个不同决策状态无法估计其出现概率的大小 C．仅凭个人的主观倾向和偏好进行方案选择 D．未来情况和条件出现的概率已知 答案：D 6、线性规划问题中决策变量应为（）。 A．连续变量 B．离散变量 C．整数变量 D．随机变量
答案：A 7、线性规划问题的数学模型由目标函数、约束条件和（）三个部分组成。 A．非负条件 B．顶点集合 C．最优解 D．决策变量 答案：D 8、典型的无概率决策准则，不包括（）。 A．乐观准则 B．折中准则 C．等可能准则 D．最大后悔值准则 答案：D 9、以下说法中不正确的为（）。 A．完成各个作业需要的时间最长的路线为关键路线 B．关键路线上的作业称为关键作业 C．所有关键作业的总时差为0 D．以上说法均不正确 答案：D 10、（）也称小中取大准则。这是一种在不确定型决策问题中，充分考虑可能出现的最小收益后，在最小收益中再选取最大者的保守决策方法。 A．悲观准则 B．折中准则 C．等可能准则 D．后悔值准则 答案：A 11、当某个非基变量检验数为零，则该问题有（）。 A．无解B．无穷多最优解 C．退化解D．惟一最优解 答案：B 12、假设对于一个动态规划问题，应用顺推法以及逆推解法得出的最优解分别为P和D，则有（）。A．P>D B．P 运筹学-学习指南 一、名词解释 1松弛变量 为将线性规划问题的数学模型化为标准型而加入的变量。 2可行域 满足线性约束条件的解（x,y）叫做可行解，由所有可行解组成的集合叫做可行域。 3人工变量 亦称人造变量.求解线性规划问题时人为加入的变量。用单纯形法求解线性规划问题，都是在具有初始可行基的条件下进行的,但约束方程组的系数矩阵A中所含的单位向量常常不足m个，此时可加入若干(至多m)个新变量，称这些新变量为人工变量。 4对偶理论 每一个线性规划问题都存在一个与其对偶的问题，在求出一个问题解的同时，也给出了另一个问题的解。研究线性规划中原始问题与对偶问题之间关系的理论 5灵敏度分析 研究与分析一个系统（或模型）的状态或输出变化对系统参数或周围条件变化的敏感程度的方法。在最优化方法中经常利用灵敏度分析来研究原始数据不准确或发生变化时最优解的稳定性。通过灵敏度分析还可以决定哪些参数对系统或模型有较大的影响。 6影子价格 反映资源配置状况的价格。影子价格是指在其他资源投入不变的情况下,每增加一单位的某种资源的投入所带来的追加收益。即影子价格等于资源投入的边际收益。只有在资源短缺的情况下,每增加一单位的投入才能带来收益的增加 7产销平衡运输 一种特殊的线性规划问题。产品的销售过程中，产销平衡是指工厂产品的产量等于市场上的销售量。 8西北角法 是运筹学中制定运输问题的初始调运方案（即初始基可行解）的基本方法之一。也就是从运价表的西北角位置开始，依次安排m个产地和n个销地之间的运输业务，从而得到一个初始调运方案的方法。 9最优性检验 检验当前调运方案是不是最优方案的过程。 10动态规划 解决多阶段决策过程优化问题的方法：把多阶段过程转化为一系列单阶段问题，利用各阶段之间的关系，逐个求解 11状态转移方程 从阶段K到K+1的状态转移规律的表达式 常用无约束最优化方法评价准则 方法算法特点适用条件 最速下降法属于间接法之一。方法简便，但要计算一阶偏导 数，可靠性较好，能稳定地使函数下降，但收敛 速度较慢，尤其在极点值附近更为严重 适用于精度要求不高或用于对 复杂函数寻找一个好的初始 点。 Newton法属于间接法之一。需计算一、二阶偏导数和Hesse 矩阵的逆矩阵，准备工作量大，算法复杂，占用 内存量大。此法具有二次收敛性，在一定条件下 其收敛速度快，要求迭代点的Hesse矩阵必须非 奇异且定型（正定或负定）。对初始点要求较高， 可靠性较差。 目标函数存在一阶\二阶偏导 数，且维数不宜太高。 共轭方向法属于间接法之一。具有可靠性好，占用内存少， 收敛速度快的特点。 适用于维数较高的目标函数。 变尺度法属于间接法之一。具有二次收敛性，收敛速度快。 可靠性较好，只需计算一阶偏导数。对初始点要 求不高，优于Newton法。因此，目前认为此法是 最有效的方法之一，但需内存量大。对维数太高 的问题不太适宜。 适用维数较高的目标函数 （n=10～50）且具有一阶偏导 数。 坐标轮换法最简单的直接法之一。只需计算函数值，无需求 导，使用时准备工作量少。占用内存少。但计算 效率低，可靠性差。 用于维数较低（n<5）或目标函 数不易求导的情况。 单纯形法此法简单，直观，属直接法之一。上机计算过程 中占用内存少，规则单纯形法终止条件简单，而 不规则单纯形法终止条件复杂，应注意选择，才 可能保证计算的可靠性。 可用于维数较高的目标函数。 常用约束最优化方法评价标准 方法算法特点适用条件 外点法将约束优化问题转化为一系列无约束优化问题。 初始点可以任选，罚因子应取为单调递增数列。 初始罚因子及递增系数应取适当较大值。 可用于求解含有等式约束或不等 式约束的中等维数的约束最优化 问题。 内点法将约束优化问题转化为一系列无约束优化问题。 初始点应取为严格满足各个不等式约束的内点， 障碍因子应取为单调递减的正数序列。初始障碍 因子选择恰当与否对收敛速度和求解成败有较大 影响。 可用于求解只含有不等式约束的 中等维数约束优化问题。 混合罚函数法将约束优化问题转化为一系列无约束优化问题， 用内点形式的混合罚函数时，初始点及障碍因子 的取法同上；用外点形式的混合罚函数时，初始 点可任选，罚因子取法同外点法相同。 可用于求解既有等式约束又有不 等式约束的中等维数的约束化问 题。 约束坐标轮换法由可行点出发，分别沿各坐标轴方向以加步探索 法进行搜索，使每个搜索点在可行域内，且使目 标函数值下降。 可用于求解只含有不等式约束， 且维数较低（n<5），目标函数的 二次性较强的优化问题。 复合形法在可行域内构造一个具有n个顶点的复合形，然 后对复合形进行映射变化，逐次去掉目标函数值 最大的顶点。 可用于求解含不等式约束和边界 约束的低维优化问题。 无约束优化方法---鲍威尔方法 本实验用鲍威尔方法求函数f(x)=(x1-5)2+(x2-6)2 的最优解。 一、简述鲍威尔法的基本原理 从任选的初始点x⑴o出发，先按坐标轮换法的搜索方向依次沿e1.e2.e3进行一维搜索，得各自方向的一维极小点x⑴ x⑵ x⑶.连接初始点xo⑴和最末一个一维极小点x3⑴,产生一个新的矢量 S1=x3⑴-xo⑴ 再沿此方向作一维搜索，得该方向上的一维极小点x⑴. 从xo⑴出发知道获得x⑴点的搜索过程称为一环。S1是该环中产生的一个新方向，称为新生方向。 接着，以第一环迭代的终点x⑴作为第二环迭代的起点xo⑵,即 Xo⑵←x⑴ 弃去第一环方向组中的第一个方向e1，将第一环新生方向S1补在最后，构成第二环的基本搜索方向组e2,e3,S1，依次沿这些方向求得一维极小点x1⑵,x2⑵,x3⑵.连接 Xo⑵与x3⑵,又得第二环的新生方向 S2=x3⑵-xo⑵ 沿S2作一维搜索所得的极小点x⑵即为第二环的最终迭代点 二、鲍威尔法的程序 #include "stdafx.h" /* 文件包含*/ #include #include 项目三 常用无约束最优化方法（一） [实验目的] 编写最速下降法、Newton 法（修正Newton 法）的程序。 [实验学时] 2学时 [实验准备] 1．掌握最速下降法的思想及迭代步骤。 2．掌握Newton 法的思想及迭代步骤； 3．掌握修正Newton 法的思想及迭代步骤。 [实验内容及步骤] 编程解决以下问题：【选作一个】 1．用最速下降法求 22120min ()25[22]0.01T f X x x X ε=+==，，，． 2．用Newton 法求 22121212min ()60104f X x x x x x x =--++-， 初始点 0[00]0.01T X ε==，，． 最速下降法 Matlab 程序： clc;clear; syms x1 x2; X=[x1,x2]; fx=X(1)^2+X(2)^2-4*X(1)-6*X(2)+17; fxd1=[diff(fx,x1) diff(fx,x2)]; x=[2 3]; g=0; e=0.0005; a=1; fan=subs(fxd1,[x1 x2],[x(1) x(2)]); g=0; for i=1:length(fan) g=g+fan(i)^2; end g=sqrt(g); step=0; while g>e step=step+1; dk=-fan; %点x(k)处的搜索步长 ak=((2*x(1)-4)*dk(1)+(2*x(2)-6)*dk(2))/(dk(1)*dk(2)-2*dk(1)^2-2*dk(2)^2); xu=x+ak*dk; x=xu; %输出结果 optim_fx=subs(fx,[x1 x2],[x(1) x(2)]); fprintf(' x=[ %d %d ] optim_fx=%d\n',x(1),x(2),optim_fx); %计算目标函数点x(k+1)处一阶导数值 fan=subs(fxd1,[x1 x2],[x(1) x(2)]); g=0; for i=1:length(fan) g=g+fan(i)^2; end g=sqrt(g); end %输出结果 optim_fx=subs(fx,[x1 x2],[x(1) x(2)]); fprintf('\n最速下降法\n结果：\n x=[ %d %d ] optim_fx=%d\n',x(1),x(2),optim_fx); c++程序 #include 一．单纯性法 1.用单纯形法求解下列线性规划问题（共 15 分） 12 2121212max 2515 6224..5 ,0 z x x x x x s t x x x x =+≤??+≤??+≤??≥? 2.用单纯形法求解下列线性规划问题（共 15 分） 12 121212max 2322 ..2210 ,0 z x x x x s t x x x x =+-≥-??+≤??≥? 3.用单纯形法求解下列线性规划问题（共 15 分） 1234 123412341234max 24564282 ..2341 ,,,z x x x x x x x x s t x x x x x x x x =-+-+-+≤? ?-+++≤??≥ ? 4.用单纯形法求解下列线性规划问题（共 15 分） 123 123123123123max 2360 210..20 ,,0 z x x x x x x x x x s t x x x x x x =-+++≤??-+≤??+-≤??≥? 5.用单纯形法求解下列线性规划问题（共 15 分） 123 12312123max 224 ..26,,0 z x x x x x x s t x x x x x =-++++≤??+≤??≥? 6.用单纯形法求解下列线性规划问题（共 15 分） 12 121212 max 105349..528 ,0z x x x x s t x x x x =++≤??+≤??≥? 7.用单纯形法求解下列线性规划问题（共 16 分） 12 121212max 254 212..3218 ,0 z x x x x s t x x x x =+≤??≤??+≤??≥? 个人学习时间优化分配 设计总说明（摘要） 合理的安排时间方案，采取最优化的时间组合，有利于我们充分发挥各个时间阶段的学习效益。同时可以使我们的学习符合日常行为及自身特点，不仅使时间得到有效安排，也使得我们的身心得到和谐。此次，研究分配一天中四个阶段四门课程的学习时间，就是根据学生的身心特点，和各阶段对各课程学习的收获程度，采取获得程度量化的方法，设计出一个最优的时间组合方案，从而获得最大的收获效益。即获得学习的最大价值。 在这个过程中要将运筹学的各种理论知识与具体实际情况相结合。首先是确 定所要研究的问题，考虑所需要的各种数据，根据实际需求确定所需要的数据和模拟量化的数据。将数据整理形成分析和解决问题的具体模型。其次对已得模型利用计算机进行求解，得出方程的最优解。最后结合所研究问题的实际背景，对模型的解进行评价、分析以及调整，并对解的实施与控制提出合理化的建议。 关键词：时间优化，线性规化，最优解，获得效益最大 目录 1.绪论 1.1研究的背景 (3) 1.2研究的主要内容与目的 (3) 1.3研究的意义 (3) 1.4研究的主要方法与思路 (3) 2.理论方法的选择 2.1所研究的问题的特点 (4) 2.2拟采用的运筹学理论方法的特点 (4) 2.3理论方法的适用性及有效性论证 (5) 3.模型的建立 3.1 基础数据的确定 (5) 3.2变量的设定 (6) 3.3目标函数的建立 (6) 3.4限制条件的确定 (6) 3.5模型的建立 (7) 4.模型的求解及解的分析 4.1模型的求解 (7) 4.2解的分析与评价 (9) 5.结论与建议 5.1研究结论 (11) 案例：连续投资的优化问题 一、题目： 某企业在今后五年内考虑对下列项目投资，已知：，从第一年到第四年每年年初需要投资，并于次年末收回本利115%。项目A，但规定最大投资额不超B，第三年年初需要投资，到第五年末能收回本利125%项目40万元。过，但规定最大投资额不超，第二年年初需要投资，到第五年末能收回本利140%项目C 30万元。过6%。项目D，五年内每年年初可购买公债，于当年末归还，并加利息问它应如何确定给这些项目的每年投100万元，该企业5年内可用于投资的资金总额为资使得到第五年末获得的投资本利总额为最大？ 二、建立上述问题的数学模型的投资额，它们都是待定的年初给项目A,B,C,D, X （i=1.2.3.4.5）为第i设X,X , X iDiB1AiC每年年初均可投资，年末收回本利，固每年的投资额应该等于手中拥未知量。由于项目D 有的资金额。建立该问题的线性规划模型如下： +1.06X+1.40X+1.25XMax Z=1.15X5D 2C4A3B X+X=1000000 (1) 1D1A X+X+X=1.06X (2) 1D2C2A2D X+X+X=1.15X+1.06X (3) 3A 3B 3D 1A 2D s.t. X+X=1.15X+1.06X(4) 3D 4A 4D 2A X=1.15X+1.06X (5)5D 3A4D X<=400000 (6) 3B X<=300000 (7) 2C X , X , X, X>=0 i=1,2,3,4,5 iD1AiCiB 经过整理后如下： Max Z=1.15X+1.40X+1.25X+1.06X5D 2C4A3B X+X=1000000 1D1A-1.06X+ X+X+X =0 2D2A2C1D-1.15X-1.06X+ X+X+X=0 3D3A1A3B2D s.t. -1.15X-1.06X +X+X=0 4D3D4A2A-1.15X-1.06X+ X=0 5D4D3A X<=400000 3B X<=300000 2C i=1,2,3,4,5 , X , X, X>=0 X iDiBiC1A 求解过程以及相应的结果三、Excel中进行布局并输入相应的公式）在Excel1 （ max z = 5x, <15 6x 十2x^ < 24 X ■ X] + 兀 < 5 x >0 luax Z = +3A\ X] - 2 A, > -2 2x^ + 2x, <10 心兀> 0 niax z = 2Xj - 4兀 + 5屯-6屯兀+ 4.V, - 2Xj + 8兀 S 2 sjJ -Xj + 2Xy + SXj + 4耳 S1 [ 兀,?口,?5，兀> max z = 2x^- x, + .v, + X. + 屯 < 60 片.X' + ZXs <10 SjJ ■ X] +兀一兀 <20 >0 luax z = + 2x, + 尽 2兀 + X, + Xj < 4 兀 + 2兀 <6 XpA.,Xj >0 niax z = [Qx^ + 5Xy ■ 3屯 + 4土 S 9 5x^ + 2.V, < 8 -VpA. >0单纯性法 1 ?用单纯形法求解下列线性规划问 题 15 6?用单纯形法求解下列线性规划问题（ 共15 2?用单纯形法求解下列线性规划问题（共15 3?用单纯形法求解下列线性规划问题（共15 4?用单纯形法求解下列线性规划问题15 5?用单纯形法求解下列线性规划间题（共15 7?用单纯形法求解下列线性规划问题（共16分） max z = 2x^ + 5x, X, <4 2x. <12 sJ.i ■ 3X] +2兀 <18 -Vpj. >0 二-对偶单纯性法 1?灵活运用单纯形法和对偶单纯形法解下列问题（共15分） max z = \ + 6兀 F 兀 + X）> 2 5Z < 兀 + 3-V, < 3 心A >0 2.灵活利用单纯形法和对偶单纯形法求解下列线性规划问题（共15分）max乙=兀+ 3兀 Xv^-lO-r, S50 X] + A > 1 SJ.< X, <4 ApX, >0 3.用对偶单纯形法求解卜列线性规划问题（共15分） mm Z = 2-Vj + 3兀 2x^ + 3x, S 30 舌十2壬210 sJ.< Xj - Xy > 0 x^2 5 X、2 0 ? ■ 4?灵活运用单纯形法和对偶单纯形法求解下列线性规划问题（共15分） min z =召+ 2兀-兀 ?召 + X, + “s + 兀 < 6 5Z- 2x^ -“2 +- 3?口 > 5 [ 屯>0 5?运用对偶单纯形法解下列问题（共16分） max z = x^ + -V. 2Xi + X. > 4 A； +7x^ >7 >0 6?灵活运用单纯形法和对偶单纯形法解下列问题（共15分） luax乙=齐+ 6兀 兀+兀> 2 5J.<<3 丹A >0 第1章 最优化问题的基本概念 §1.1最优化的概念 最优化就是依据最优化原理和方法，在满足相关要求的前提下，以尽可能高的效率求得工程问题最优解决方案的过程。 §1.2最优化问题的数学模型 1.最优化问题的一般形式 ??? ????===≤q v x x x h p u x x x g t s x x x f x x x f i n d n v n u n n ,,2,10),,,(,,2,10),,,(..),,,(m i n ,,,21212121 2.最优化问题的向量表达式 ??? ? ???=≤0)(0)(..)(m i n X H X G t s X f X f i n d 式中：T n x x x X ],,,[21 = T p X g X g X g X G )](,),(),([)(21 = T p X h X h X h X H )](,),(),([)(21 = 3.优化模型的三要素 设计变量、约束条件、目标函数称为优化设计的三要素！ 设计空间：由设计变量所确定的空间。设计空间中的每一个点都代表一个设计方案。 §1.3优化问题的分类 按照优化模型中三要素的不同表现形式，优化问题有多种分类方法： 1按照模型中是否存在约束条件，分为约束优化和无约束优化问题 2按照目标函数和约束条件的性质分为线性优化和非线性优化问题 3按照目标函数个数分为单目标优化和多目标优化问题 4按照设计变量的性质不同分为连续变量优化和离散变量优化问题 第2章 最优化问题的数学基础 §2.1 n 元函数的可微性与梯度 一、可微与梯度的定义 1.可微的定义 设)(X f 是定义在n 维空间n R 的子集D 上的n 元实值函数，且D X ∈0。若存在n 维向量L ，对于任意n 维向量P ，都有 0)()(lim 000=--+→P P L X f P X f T P 则称)(X f 在0X 处可微。 2.梯度 设有函数)(X F ，T n x x x X ],,,[21 =，在其定义域内连续可导。我们把)(X F 在定义域内某点X 处的所有一阶偏导数构成的列向量，定义为)(X F 在点X 处的梯度。记为： T n k x F x F x F X F ????????????=?,,,)(21 梯度有3个性质： ⑴函数在某点的梯度方向为函数过该点的等值线的法线方向； ⑵函数值沿梯度方向增加最快，沿负梯度方向下降最快； ⑶梯度描述的只是函数某点邻域内的局部信息。 §2.2极小点及其判别条件 一、相关概念 1.极小点与最优解 设)(X f 是定义在n 维空间n R 的子集D 上的n 元实值函数，若存在D X ∈*及实数 0>δ，使得)(),(**X X D X N X ≠?∈?δ都有)()(*X f X f ≤，则称*X 为)(X f 的局部极小点；若)()(*X f X f <，则称*X 为)(X f 的严格局部极小点。 若D X ∈?，都有)()(*X f X f ≤，则称*X 为)(X f 的全局极小点，若)()(*X f X f <，则称*X 为)(X f 的全局严格极小点。 对最优化问题??? ? ???=≤0)(0)(..)(min X H X G t s X f X find 而言 满足所有约束条件的向量T n x x x X ],,,[21 =称为上述最优化问题的一个可行解，全体可行解组成的集合称为可行解集。在可行解集中，满足： )(m i n )(*X f X f =的解称为优化问题的最优解。 一、单选题 1．目标函数取极小（minZ ）的线性规划问题可以转化为目标函数取极大的线性规划问题求解，原问题的目标函数值等于（ ）。 A. maxZ B. max(-Z) C. –max(-Z) D.-maxZ 2． 下列说法中正确的是（ ）。 A ．基本解一定是可行解 B ．基本可行解的每个分量一定非负 C ．若B 是基，则B 一定是可逆 D ．非基变量的系数列向量一定是线性相关的 3．在线性规划模型中，没有非负约束的变量称为 （ ） A.多余变量 B ．松弛变量 C ．人工变量 D ．自由变量 4. 当满足最优解，且检验数为零的变量的个数大于基变量的个数时，可求得（ ）。 A ．多重解 B ．无解 C ．正则解 D ．退化解 5．对偶单纯型法与标准单纯型法的主要区别是每次迭代的基变量都满足最优检验但不完全满足 （ ）。 A ．等式约束 B ．“≤”型约束 C ．“≥”约束 D ．非负约束 6. 原问题的第ｉ个约束方程是“＝”型，则对偶问题的变量i y 是（ ）。 A ．多余变量 B ．自由变量 C ．松弛变量 D ．非负变量 7.在运输方案中出现退化现象，是指数字格的数目( )。 A.等于m+n B.大于m+n-1 C.小于m+n-1 D.等于m+n-1 二、判断题 1．线性规划问题的一般模型中不能有等式约束。 2．对偶问题的对偶一定是原问题。 3．产地数与销地数相等的运输问题是产销平衡运输问题。 4．对于一个动态规划问题，应用顺推或逆解法可能会得出不同的最优解。 5．线性规划问题的每一个基本可行解对应可行域上的一个顶点。 6．线性规划问题的基本解就是基本可行解。 三、填空题 1．如果某一整数规划：MaxZ=X 1+X 2 X 1+9/14X 2≤51/14 -2X 1+X 2≤1/3 X 1,X 2≥0且均为整数 所对应的线性规划（松弛问题）的最优解为X 1=3/2，X 2=10/3，MaxZ=6/29，我们现在要对X 1进行分枝，应该分为 和 。 2．如希望I 的2 倍产量21x 恰好等于II 的产量2x ，用目标规划约束可表为： 3. 线性规划解的情形有 4. 求解指派问题的方法是 。 5．美国的R.Bellman 根据动态规划的原理提出了求解动态规划的最优化原理 为 硕士研究生课程大纲 课程名称（中文）：运筹学与最优化理论 课程名称（英文）：Operations Research and Optimization Theory 课程编码：Y04020B 开课单位：电气信息学院 授课对象：管理科学与工程、控制理论与控制工程、电力系统及其自动化专业硕士研究生任课教师：游文霞 学时：48 学分： 3 学期：2 考核方式: 撰写论文 先修课程：线性代数、高等数学、概率论、数理统计 课程简介： 运筹学是以定量分析为主来研究经济管理与生产实践等问题。它将工程思想和管理思想相结合，应用系统的、科学的、数学分析的方法，通过建模、检验和求解数学模型获得最优决策方案。 一、教学目的与基本要求：（150字以内） 通过讲授和各种实践环节(作业、讨论)，使学生掌握运筹学整体优化的思想和若干定量分析的优化技术，能正确应用各类模型分析、解决各种实际问题，培养和提高学生科学思维、科学方法、实践技能和创新能力。 二、课程内容与学时分配 1、课程主要内容：（200字以内） 主要讲授线性规划，单纯形法，线性规划的对偶理论及灵敏度分析，非线性规划，整数规划，目标规划，动态规划，网络模型，决策理论等与经济、管理、控制领域密切相关的运筹学分支的基本模型、方法和应用。 2、课程具体安排：（按教学章节编写，重点章节下划线） 三、实验、实践环节及习题内容与要求 针对每个章节的内容，结合实际应用，布置相应的习题作业，要求学生在大量做练习题的过程中，学习如何采用定量的分析方法来分析、求解相关的实际问题，掌握相关的优化方法的基本思想与求解算法。 四、教材及主要参考文献（顺序为：文献名，作者，出版时间，出版单位）： 教材名称： Frederick S. Hillier, Gerald J. Lieberman. Introduction to Operation Research (8e) (运筹学导论，第八版). McGraw-Hill Press, 2005. 参考书： [1]Wayne L. Winston.《运筹学：数学规划》（影印版）[M]. 北京：清华大学出版社，2004. [2]Wayne L. Winston.《运筹学：决策方法》（影印版）[M]. 北京：清华大学出版社，2004. [3]V.G..Kulkarni.《运筹学：应用数学模型》（影印版）[M]. 北京：清华大学出版社，2006. [4]胡运权，郭耀煌. 运筹学教程（第二版）[M]. 北京：清华大学出版社，2003. [5]运筹学教材组编. 运筹学(修订版) [M]. 北京：清华大学出版社，2004. [6]徐渝，贾涛. 运筹学[M]. 北京：清华大学出版社，2005. [7]熊伟.运筹学[M].北京：机械工业出版社，2005. [8]胡运权.运筹学习题集[M].北京：清华大学出版社，2002. 撰写人：游文霞 学位分委员会签字： 学院主管研究生教学院长签字： 《运筹学》期末复习题 第一讲运筹学概念 一、填空题 1.运筹学的主要研究对象就是各种有组织系统的管理问题,经营活动。 2.运筹学的核心主要就是运用数学方法研究各种系统的优化途径及方案,为决策者提供科学决策的依据。 3.模型就是一件实际事物或现实情况的代表或抽象。 4通常对问题中变量值的限制称为约束条件,它可以表示成一个等式或不等式的集合。5.运筹学研究与解决问题的基础就是最优化技术,并强调系统整体优化功能。运筹学研究与解决问题的效果具有连续性。 6.运筹学用系统的观点研究功能之间的关系。 7.运筹学研究与解决问题的优势就是应用各学科交叉的方法,具有典型综合应用特性。 8.运筹学的发展趋势就是进一步依赖于_计算机的应用与发展。 9.运筹学解决问题时首先要观察待决策问题所处的环境。 10.用运筹学分析与解决问题,就是一个科学决策的过程。 11、运筹学的主要目的在于求得一个合理运用人力、物力与财力的最佳方案。 12.运筹学中所使用的模型就是数学模型。用运筹学解决问题的核心就是建立数学模型,并对模型求解。 13用运筹学解决问题时,要分析,定议待决策的问题。 14.运筹学的系统特征之一就是用系统的观点研究功能关系。 15、数学模型中,“s·t”表示约束。 16.建立数学模型时,需要回答的问题有性能的客观量度,可控制因素,不可控因素。 17.运筹学的主要研究对象就是各种有组织系统的管理问题及经营活动。 18、1940年8月,英国管理部门成立了一个跨学科的11人的运筹学小组,该小组简称为OR。 二、单选题 1．建立数学模型时,考虑可以由决策者控制的因素就是( A ) A.销售数量 B.销售价格 C.顾客的需求 D.竞争价格 2.我们可以通过( C )来验证模型最优解。 A.观察 B.应用 C.实验 D.调查 3.建立运筹学模型的过程不包括( A )阶段。 A.观察环境 B.数据分析 C.模型设计 D.模型实施 4、建立模型的一个基本理由就是去揭晓那些重要的或有关的( B ) A数量B变量 C 约束条件 D 目标函数 5、模型中要求变量取值( D ) A可正B可负C非正D非负 6、运筹学研究与解决问题的效果具有( A ) A 连续性 B 整体性 C 阶段性 D 再生性 7、运筹学运用数学方法分析与解决问题,以达到系统的最优目标。可以说这个过程就是一个(C) A解决问题过程B分析问题过程C科学决策过程D前期预策过程8、从趋势上瞧,运筹学的进一步发展依赖于一些外部条件及手段,其中最主要的就是 ( C ) 华南农业大学期末考试试卷（A 卷） 2010--2011学年第 1 学期 考试科目： 运筹学与最优化方法 考试类型：（闭卷）考试 考试时间： 120 分钟 学号 姓名 年级专业 一、 用单纯形法求解下列线性规划问题（共 15 分） 12121212max 105349 ..528,0z x x x x s t x x x x =++≤?? +≤??≥? 二、灵活运用单纯形法和对偶单纯形法解下列问题（共 15 分） 12121212max 62 ..33,0z x x x x s t x x x x =++≥?? +≤??≥? 三、解下列0-1型整数规划问题（共 10 分） 12345123451345124512345max 325232473438..116333,,,,01z x x x x x x x x x x x x x x s t x x x x x x x x x =+--+++++≤??+-+≤?? -+-≥??=?或 四、利用库恩-塔克（K-T ）条件求解以下问题（共 15 分） 22121122 121212 max ()104446..418,0f X x x x x x x x x s t x x x x =+-+-+≤??+≤??≥? 五、用内点法求解下列非线性约束最优化问题（共 15 分） 21 1212min ()6923..3 f X x x x x s t x =-++≥?? ≥? 六、给定初始点(0)(1,1)T X =，用最速下降法迭代一次研究下列函数的极大值。（共 15 分） 22 121122()46222f X x x x x x x =+--- 七、某人因工作需要购置了一辆摩托车,他可以连续使用或任一年末将旧车卖掉,换一辆新车,下表列出了于第i 年末购置或更新 的车至第j 年末的各项费用的累计(含更新所需费用、运行费用及维修费用等)，试据此确定该人最佳的更新策略，使从第一年至第五年末的各项费用的累计之和为最小。（共 15 分） 运筹学与最优化MATLAB编程 实验报告 院系： 专业： 姓名： 学号： 指导老师： 完成日期： 割平面法求解整数规划问题 一、引言： 通过对MATLAB实践设计的学习，学会使用MATLAB解决现实生活中的问题。该设计是在MATLAB程序设计语言的基础上，对实际问题建立数学模型并设计程序，使用割平面法解决一个整数规 划问题。经实验，该算法可成功运行并求解出最优整数解。 二、 算法说明： 割平面法有许多种类型，本次设计的原理是依据Gomory 的割平面法。Gomory 割平面法首先求解非整数约束的线性规划，再选择一个不是整数的基变量，定义新的约束，增加到原来的约束中，新的约束缩小了可行域，但是保留了原问题的全部整数可行解。 算法具体设计步骤如下： 1、首先，求解原整数规划对应的线性规划 ,*)(m i n x c x f =???≥≤0 ..x b Ax t s ，设最优解为x*。 2、如果最优解的分量均为整数，则x*为原整数规划的最优解；否则任选一个x*中不为整数的分量，设其对应的基变量为x p ，定义包含这个基变量的切割约束方程con j j ij p b x r x =+∑，其中x p 为非基变量。 3、令][ij ij ij r r r -=，][con con con b b b -=，其中[]为高斯函数符号，表示不大于某数的最大整数。将切割约束方程变换为 ∑∑-=-+j j ij con con j j ij p x r b b x r x ][][，由于0 第三章无约束最优化方法 本章内容及教学安排 第一节概述 第二节迭代终止原则 第三节常用的一维搜索方法 第四节梯度法 第五节牛顿法 第六节共轭方向法 第七节变尺度法 第八节坐标轮换法 第九节鲍威尔方法 第一节概述 优化问题可分为 无约束优化问题 有约束优化问题 无约束最优化问题求解基于古典极值理论的一种数值迭代方法，主要用来求解非线性规划问题 迭代法的基本思想： 所以迭代法要解决三个问题 1、如何选择搜索方向 2、如何确定步长 3、如何确定最优点（终止迭代） 第二节 迭代终止准则 1）1K K X X ε+-≤ 111/2 21K K K K n i i i X X X X ε++=??-=-≤???? ∑（） 2） 11()()()() () K K K K K f X f X f X f X or f X ε ε ++-≤-≤ 3）(1)()K f X ε+?≤ 第三节 常用的一维搜索方法 本节主要解决的是如何确定最优步长的问题。 从初始点(0)X 出发，以一定的步长沿某一个方向，可以找到一个新的迭代点，其公式如下： (1)(0)00(2)(1)11(1)() K K k k X X S X X S X X S ααα+=+=+= + 现在假设K S 已经确定，需要确定的是步长k α，就把求多维目标函数的极小值这个多维算过程中，当起步点和方向问题，变成求一个变量即步长的最优值的一维问题了。即 (1)()min ()min ()min ()K K K k k f X f X S f αα+=+= 由此可见，最佳步长*K α由一维搜索方法来确定 求*k α，使得()()()()()()min K K K K f f X S αα=+→ 一、一维搜索区间的确定 区间[,]a b 应满足 ()(*)()f a f f b α>< 无约束最优化直接方法和间接方法的异同 无约束最优化直接方法和间接方法的异同一、什么是无约束最优化 最优化方法（也称做运筹学方法）是近几十年形成的，它主要运用数学方法研究各种系统的优化途径及方案，为决策者提供科学决策的依据。最优化方法的主要研究对象是各种有组织系统的管理问题及其生产经营活动。其的目的在于针对所研究的系统，求得一个合理运用人力、物力和财力的最佳方案，发挥和提高系统的效能及效益，最终达到系统的最优目标。实践表明，随着科学技术的日益进步和生产经营的日益发展，最优化方法已成为现代管理科学的重要理论基础和不可缺少的方法，被人们广泛地应用到公共管理、经济管理、工程建设、国防等各个领域，发挥着越来越重要的作用。 最优化问题分为无约束最优化和约束最优化问题，约束最优化问题是具有辅助函数和形态约束条件的优化问题，而无约束优化问题则没有任何限制条件。无约束最优化问题实际上是一个多元函数无条件极值问题。 虽然在工程实践中，大多数问题都是具有约束的优化问题，但是优化问题的处理上可以将有约束的优化问题转化为无约束最优化问题，然后按无约束方法进行处理。或者是将约束优化问题部分转化为无约束优化问题，在远离极值点和约束边界处按无优化约束来处理，在接近极值点或者约束边界时按照约束最优化问题处理。所以无约束优化问题的解法不仅是优化设计方法的基本组成部分，也是优化方法的基础。 无约束最优化方法大致分为两类：一类是使用导数的间接方法，即在计算过程中要用到目标函数的导数；另一类是直接方法，即只要用到目标函数值，不需要计算导数。这里我们比较这两类方法的异同。 二、无约束最优化方法 1. 使用导数的间接方法 1.1 最速下降法 函数的负梯度方向是函数值在该点下降最快的方向。将n维问题转化为一系列沿负梯度方向用一维搜索方法寻优的问题，利用负梯度作为搜索方向，故称 无约束最优化直接方法和间接方法的异同一、什么是无约束最优化 最优化方法（也称做运筹学方法）是近几十年形成的，它主要运用数学方法研究各种系统的优化途径及方案，为决策者提供科学决策的依据。最优化方法的主要研究对象是各种有组织系统的管理问题及其生产经营活动。其的目的在于针对所研究的系统，求得一个合理运用人力、物力和财力的最佳方案，发挥和提高系统的效能及效益，最终达到系统的最优目标。实践表明，随着科学技术的日益进步和生产经营的日益发展，最优化方法已成为现代管理科学的重要理论基础和不可缺少的方法，被人们广泛地应用到公共管理、经济管理、工程建设、国防等各个领域，发挥着越来越重要的作用。 最优化问题分为无约束最优化和约束最优化问题，约束最优化问题是具有辅助函数和形态约束条件的优化问题，而无约束优化问题则没有任何限制条件。无约束最优化问题实际上是一个多元函数无条件极值问题。 虽然在工程实践中，大多数问题都是具有约束的优化问题，但是优化问题的处理上可以将有约束的优化问题转化为无约束最优化问题，然后按无约束方法进行处理。或者是将约束优化问题部分转化为无约束优化问题，在远离极值点和约束边界处按无优化约束来处理，在接近极值点或者约束边界时按照约束最优化问题处理。所以无约束优化问题的解法不仅是优化设计方法的基本组成部分，也是优化方法的基础。 无约束最优化方法大致分为两类：一类是使用导数的间接方法，即在计算过程中要用到目标函数的导数；另一类是直接方法，即只要用到目标函数值，不需要计算导数。这里我们比较这两类方法的异同。 二、无约束最优化方法 1. 使用导数的间接方法 1.1 最速下降法 函数的负梯度方向是函数值在该点下降最快的方向。将n维问题转化为一系列沿负梯度方向用一维搜索方法寻优的问题，利用负梯度作为搜索方向，故称最 09级数学专业《运筹学》复习题 线性规划 一、填空题 1. 线性规划模型包括决策变量、目标函数、约束条件三个要素。2．线性规划问题的标准形式中，约束条件取等式，目标函数求最大_，而所有决策变量必须非负。 3．线性规划问题是求一个线性目标函数在一组线性约束条件下的最值问题。 4．线性规划问题的可行解是指满足所有约束条件_ 的解。 5．在线性规划问题中，基本可行解的非零分量所对应的列向量线性无关。 6．在将线性规划问题的一般形式转化为标准形式时，引入的松驰变量在目标函数中的系数为正。 7．如果线性规划问题存在目标函数为有限值的最优解，求解时只需在其可行解的集合中进行搜索即可得到最优解。 8．若线性规划问题有最优解，则最优解一定可以在可行域的顶点_ 达到。 9．图解法适用于含有两个 _ 决策变量的线性规划问题。 10．求解线性规划问题可能的结果有唯一最优解，无穷多最优解，无界解，无可行解。 11．在用图解法求解线性规划问题时，如果取得最值的等值线与可行域的一段边界重合，则最优解不唯一。 12. 设线性规划模型的一般形式为， 其标准形式为， 其典式。 13 将线性规划模型化成标准形式时，"≤"的约束条件要在不等式左_端加入松弛变量。 14. 如果某个约束条件是" ≥ "情形，若化为标准形式，需要引入一个剩余变量。 15. 线性规划的典式对应的表格表示被称为单纯形表。 16、线性规划的代数解法只要运用了代数消去法的原理实现基可行解的转换，寻求最优解。 17、在线性规划问题中，基变量的系数列向量为单位列向量。 18、对于求目标函数极大值而言，人工变量在目标函数的系数应为 -1。 19、对偶问题的对偶问题为原问题。 20、在一对对偶问题中，原问题的约束条件的右端常数是对偶问题的目标函数系数。 21、在大M法中，M表示充分大的正数。 22、如果原问题的某个变量无约束，则对偶问题中对应的约束条件应为等式。 23、在现性规划问题的基本解中，所有的非基变量等于 0 。 24、线性规划问题的基可行解与可行域的顶点的关系是顶点多于基可行解。 25、在求运费最少的调度运输问题中，如果某一非基变量的检验数为4，则说明如果在该空格中增加一个运量运费加 4 。 26、最大化的线性规划问题为无界解时，则对偶问题无可行解__ 。 27、运筹学的主要研究对象是各种有组织系统的管理问题及生产经营活动，其主要研究方法是_量化和模型化方法__。 28、运筹学的目的在于针对所研究的系统__求得一个合理应用人力，物力和财力的最佳方案。发挥和提高系统的_效能及效益_，最终达到系统的__最优目标___。 29、在运输问题的表上作业中，位势方程是由基变量xij 确定。 30、在运输问题的表上作业中，非基变量xij的检验数σij= Ui + Vj - Cij 。二单选题 1. 线性规划问题是针对（ D ）求极值问题. A.约束 B.决策变量 C. 秩 D.目标函数 2. 若某个bk≤0, 化为标准形式时原不等式（ D ） A. 不变 B.左端乘负1 C .右端乘负1 D. 两边乘负1 3. 如果线性规划问题有可行解，那么该解必须满足（ A ） A.所有约束条件 B.变量取值非负 C.所有等式要求 D.所有不等式要求 4. 如果一个线性规划问题有n个变量，m个约束方程(m《运筹学》复习题
常用最优化方法评价准则
无约束优化方法程序
常用无约束最优化方法(一)
运筹学与最优化方法习题集
运筹学课程设计-个人学习时间优化分配
运筹学与最优化方法线性规划案例分析报告
运筹学与最优化方法习题集word文档良心出品
运筹学最优化方法复习
运筹学复习题目加答案
运筹学与最优化理论教学大纲doc - 三峡大学计算机与信息学院
《运筹学》期末复习题
最优化方法考试试题.
运筹学与最优化MATLAB编程
第三章 无约束最优化方法
无约束最优化直接方法和间接方
无约束最优化直接方法和间接方法的异同
09数学运筹学复习题
相关主题
文本预览