《261#——管理运筹学》由会员分享，可在线阅读，更多相关《261#——管理运筹学（7页珍藏版）》请在金锄头文库上搜索。
1、山东大学 管理运筹学 课程试卷 试卷一 一、名词解释1. 可行解：满足所有约束条件的解。2. 指标函数：衡量全过程策略或k子过程策略优劣的数量指标。支撑子图：图G=(V,E)和,若且 ，则称G为G的支撑子图。增广链：f为一可行流，u为vs至vt的链，令u+= 正向弧，u-= 反向弧 。若u+中弧皆非饱，且u-中弧皆非零，则称u为关于f的一条增广链。5 最优解6非劣解判断题1.可行解是满足约束方程和非负条件的解。（ ）2 .线性规划问题的最优解如果存在一定是唯一的。（）3.状态变量满足无后效性是指系统从某阶段往后的发展，完全由本阶段所处的状态及其之后的决策决定，与系统以前的状态和决策无关。（ ）
2、4.决策树是一种由结点和分支构成的由左向右展开的树状图形。（ ）三、选择题1. 判断线性规划模型是否有最优解主要是根据（ ）A.非基变量的检验数是否大于0 B.基变量的检验数是否大于0 C.非基变量的检验数是否小于等于0 D.基变量的检验数是否小于等于02. 目标规划的目标函数的基本形式是( )A.minz= f(d+,d-) B.minz= f(d+) C.minz= f(d-) D.maxz= f(d+,d-)3. 目标规划的解是( )A.非劣解 B.最优解 C.满意解 D.可行解4. 整数规划解的特点是( )A.最优解不一定在顶点上达到 B.最优解不一定是松弛问题最优解的邻近整数解C.整
3、数规划的最大函数值小于或等于相应的线性规划的最大目标函数值D.整数规划的最小目标函数值大于或等于相应的线性规划的最小目标函数值二、简答题简述单纯形法的基本步骤；答：（1）把一般线形规划模型转换成标准型；（2）确定初始基可行解；（3）利用检验数对初始基可行解进行最优性检验，若 ，则求得最优解，否则，进行基变换；（4）基变换找新的可行基，通过确定入基变量和出基变量，求得新的基本可行解；（5）重复步骤（3）、（4）直至，求得最优解为止。 简述整数规划解的特点；简述动态规划的基本方程；答：对于n阶段的动态规划问题，在求子过程上的最优指标函数时，k子过程与k+1过程有如下递推关系： 对于可加性指标函数，
4、基本方程可以写为终端条件：fn+1 (sn+1) = 0对于可乘性指标函数，基本方程可以写为终端条件：fn+1 (sn+1) = 1如何找计划网络图的关键路线？答：（1）绘制计划网络图；（2）从网络的始点开始，按顺序计算出每个工序的最早开始时间（ES )和最早结束时间（EF) ；（3）从网络的终点开始，计算出在不影响整个工程最早结束时间的情况下，各个工序的最晚开始时间(缩写为LS)和最晚结束时间（缩写为LF)；（4）计算出每一个工序的时差TS；（5）时差等于零的工序为关键工序。把关键工序到终点连接成的路线确定为关键线路。三、计算题1.解：（1）加入松弛变量 得到该线形规划问题的标准型（2）利用
5、单纯形表逐步迭代Cj2100比值CBXBbx1x2x3x40x315351050x4246201421000x33041-1/23/42x1411/301/61201/30-1/31x23/4011/4-1/82x115/410-1/125/2400-1/12-7/24最优解，管理运筹学 试卷二一、名词解释1. 最优解：在可行域中使目标函数达到最优的可行解。2. 策略：一个按时间或空间次序排列的决策序列的集合。连通图：任何两点之间至少存在一条链的图称为连通图。增广链：f为一可行流，u为vs至vt的链，令u+= 正向弧，u-= 反向弧 。若u+中弧皆非饱，且u-中弧皆非零，则称u为关于f的一条增
6、广链。指标函数非劣解二、判断题1.目标规划中的解一定是最优解。（ ）2 .线性规划问题的最优解如果存在一定是唯一的。（ ）3.状态变量满足无后效性是指系统从某阶段往后的发展，完全由本阶段所处的状态及其之后的决策决定，与系统以前的状态和决策无关。（ ）4.决策树是一种由结点和分支构成的由左向右展开的树状图形。（ ）选择题1. 判断线性规划模型是否有最优解主要是根据（ ）A.非基变量的检验数是否大于0 B.基变量的检验数是否大于0 C.非基变量的检验数是否小于等于0 D.基变量的检验数是否小于等于02. 目标规划的目标函数的基本形式是( )A.minz= f(d+,d-) B.minz= f(d+
7、) C.minz= f(d-) D.maxz= f(d+,d-)3. 目标规划的解是( )A.非劣解 B.最优解 C.满意解 D.可行解4. 整数规划解的特点是( )A.最优解不一定在顶点上达到 B.最优解不一定是松弛问题最优解的邻近整数解C.整数规划的最大函数值小于或等于相应的线性规划的最大目标函数值D.整数规划的最小目标函数值大于或等于相应的线性规划的最小目标函数值二、简答题答：（1）把一般线形规划模型转换成标准型；（2）确定初始基可行解；（3）利用检验数对初始基可行解进行最优性检验，若 ，则求得最优解，否则，进行基变换；（4）基变换找新的可行基，通过确定入基变量和出基变量，求得新的基本可
8、行解；（5）重复步骤（3）、（4）直至，求得最优解为止。 简述分枝定界法的基本思想。答：分枝定界法是先求解整数规划的线性规划问题。如果其最优解不符合整数条件，则求出整数规划的上下界，用增加约束条件的办法，把相应的线性规划的可行域分成子区域（称为分枝），再求解这些子区域上的线性规划问题，不断缩小整数规划的上下界的距离，最后得整数规划的最优解。3、 简述动态规划的基本方程答：对于n阶段的动态规划问题，在求子过程上的最优指标函数时，k子过程与k+1过程有如下递推关系： 对于可加性指标函数，基本方程可以写为终端条件：fn+1 (sn+1) = 0对于可乘性指标函数，基本方程可以写为终端条件：fn+1
9、(sn+1) = 14答：（1）绘制计划网络图；（2）从网络的始点开始，按顺序计算出每个工序的最早开始时间（ES )和最早结束时间（EF) ；（3）从网络的终点开始，计算出在不影响整个工程最早结束时间的情况下，各个工序的最晚开始时间(缩写为LS)和最晚结束时间（缩写为LF)；（4）计算出每一个工序的时差TS；（5）时差等于零的工序为关键工序。把关键工序依次从始点到终点连接成的路线确定为关键线路。三、计算题1.解：（1）加入松弛变量, 得到该线形规划问题的标准型 （2）利用单纯形表逐步迭代Cj25000比值CBXBbx1x2x3x4x50x3410100-0x4120201060x5183200
10、19250000x341010045x260101/20-0x56300-112200-5/200x320011/3-1/35x260101/202x12100-1/31/3000-11/6-2/3管理运筹学 试卷三名词解释可行域：所有可行解的集合。策略：一个按时间或空间次序排列的决策序列的集合。连通图：任何两点之间至少存在一条链的图称为连通图。截量：截集上的容量和称为截量，记为C(V1 ,V2)。5、指标函数6、非劣解二、判断题1.目标规划中的解一定是最优解。（ ）2 .线性规划问题的最优解如果存在一定是唯一的。（ ）3.状态变量满足无后效性是指系统从某阶段往后的发展，完全由本阶段所处的状态
11、及其之后的决策决定，与系统以前的状态和决策无关。（ ）4.决策树是一种由结点和分支构成的由左向右展开的树状图形。（ ）选择题1. 判断线性规划模型是否有最优解主要是根据（ ）A.非基变量的检验数是否大于0 B.基变量的检验数是否大于0 C.非基变量的检验数是否小于等于0 D.基变量的检验数是否小于等于02. 目标规划的目标函数的基本形式是( )A.minz= f(d+,d-) B.minz= f(d+) C.minz= f(d-) D.maxz= f(d+,d-)3. 目标规划的解是( )A.非劣解 B.最优解 C.满意解 D.可行解4. 整数规划解的特点是( )A.最优解不一定在顶点上达到
12、B.最优解不一定是松弛问题最优解的邻近整数解C.整数规划的最大函数值小于或等于相应的线性规划的最大目标函数值D.整数规划的最小目标函数值大于或等于相应的线性规划的最小目标函数值简答题简述单纯形法的基本步骤答：（1）把一般线形规划模型转换成标准型；（2）确定初始基可行解；（3）利用检验数对初始基可行解进行最优性检验，若 ，则求得最优解，否则，进行基变换；（4）基变换找新的可行嬀入基变量和出基变量，求得新的基本可行解；（5）重复步骤（3）、（4）直至，求得最优解为止。 简述分枝定界法的基本思想。答：分枝定界法是先求解整数规划的线性规划问题。如果其最优解不符合整数条件，则求出整数规划的上下界，用增加
13、约束条件的办法，把相应的线性规划的可行域分成子区域（称为分枝），再求解这些子区域上的线性规划问题，不断缩小整数规划的上下界的距离，最后得整数规划的最优解。3.答：（1）最优解不一定在顶点上达到；（2）最优解不一定是松弛问题最优解的邻近整数解；（3）整数可行解远多余于顶点，枚举法不可取；（4）整数规划的最大函数值小于或等于相应的线性规划的最大目标函数值；（5）整数规划的最小目标函数值大于或等于相应的线性规划的最小目标函数值。4答：（1）绘制计划网络图；（2）从网络的始点开始，按顺序计算出每个工序的最早开始时间（ES )和最早结束时间（EF) ；（3）从网络的终点开始，计算出在不影响整个工程最早结束时间的情况下，各个工序的最晚开始时间(缩写为LS)和最晚结束时间（缩写为LF)；（4）计算出每一个工序的时差TS；（5）时差等于零的工序为关键工序。把关键工序依次从始点到终点连接成的路线确定为关键线路。三、计算题1.解：（1）加入人工变量 ，减去剩余变量 得到该线形规划问题的标准型（2）利用单纯形表逐步迭代Cj23-5-M0-M比值CBXBbx1x2x3x4x5x6-Mx471111007-Mx6102-510-1153M+23-4M2M-50-M0-Mx4207/2
