运筹学试题含答案

运筹学 试题 中考模拟试题doc幼小衔接 数学试题 下载云南高中历年会考数学试题下载N4真题下载党史题库下载 含答案 一、 简述惩罚函数法的基本思想，并给出其典型形式。(10分) ,nn12,xR,二、证明: 设在点处的Hesse矩阵存在，若,fx()fRR:, ,,2,x，并且正定，则是的严格局部最优解。(10min ()fx,,fx()0,fx()nxR, 分) 三、用两阶段法求解下列线性规划问题:(20分) min3zxxx,,，，123 xxx,，,211,123,,，，,423xxx ,123st..,,，,21xx13, ,xj,,01,2,3j, 四、运用分枝定界方法求解下列整数规划问题:(20分) max zxx,，(1) 12 951,xx，, 12(2) ,1414 ,1, ,，,2 xx(3) 12,3 ,(4) xx,0 ,, 12 ,(5) 取整数xx, ,12 五、试写出用动态规划方法求解下列问题时的基本方程(20分) 设有一个外贸公司 计划 项目进度计划表范例计划下载计划下载计划下载课程教学计划下载 在1月至4月份从事某种商品的经营。已知它的仓库最多可存储1000件这种商品，该公司开业时有存货500件，并根据预测知道，该种商品1月至4 月的进价和售价如 表 关于同志近三年现实表现材料材料类招标技术评分表图表与交易pdf视力表打印pdf用图表说话 pdf 5所示。 表5 月份 1 2 3 4 进价c(百元/10 9 11 15 件) 售价p(百元/12 9 13 17 件) 问如何安排进货量和销售量，使该公司获得最大利润。(假设四月底库存为零。) 1 六、已知有6个村子，相互间道路的距离如图1所示。拟合建一所 小学 小学生如何制作手抄报课件柳垭小学关于三违自查自纠报告小学英语获奖优质说课课件小学足球课教案全集小学语文新课程标准测试题 ，已知A处有小学生50人，B处40人，C处60人，D处20人，E处70人，F处90人，问小学应建在哪一个村子，使学生上学最方便(走的总路程最短)。(20分) B 6 D 6 2 8 F 4 1 A 1 7 3 C 3 E 图1 2 二、 简述惩罚函数法的基本思想，并给出其典型形式。 答:罚函数类方法的基本思想是:通过构造惩罚函数，将带有约束的非线性 规划问题转化为无约束优化问题的求解。 由不同的构造罚函数的思路就可以导出不同的具体罚函数算法，因此， 有下列典型形式: (1)等式约束问题的平方罚函数: min ()fx ,,s.t.()0, 1,,hxjqj q 2,,,,，,罚因子pxfxhx(,)()[()], 0,j,1j ,k,, (,)pxxx,,kk (2)不等式约束问题的内点罚函数(障碍罚函数) min() fx s.t.()0, 1,, gxip,,i 0n,,,,,,,xRgxip()0, 1,,,,i 00x,, (3)分(倒)数罚函数 p1pxfx,,,,(,)() ,gx(),1ii(4)对数罚函数 p pxfxgx(,)()ln[()],,,,, ,i,1i ,nn12,xR,二、证明: 设在点处的Hesse矩阵存在，若,fx()fRR:, ,,2,x，并且正定，则是min ()fx的严格局部最优解。 ,,fx()0,fx()nxR, , ()fxx证明:将在处进行Taylor展开，有 21,,,,,,,TT2fxfxxxfxxxfxxxoxx,，,,，,,,，,()()()()()()()()2由21,,,,,T2,，,,,，,fxxxfxxxoxx ()()()()()2 2,的正定性得: ,fx() 3 1,,,,T2 xxfxxxxx,,,,,,()()()0, 2 2,,xx,而为的高阶无穷小量。 oxx(), ,,,,,xx,必然存在，使得,. ,,0fxfx()(), 因此结论得证，证毕。 三、用两阶段法求解下列线性规划问题: min3zxxx,,，，123 xxx,，,211,123,,，，,423xxx ,123st..,,，,21xx13, ,xj,,01,2,3j, 解:引入辅助问题 minwyy,，12 xxxx,，，,211,1234,,，，,，,423xxxxy 12351,st..,,，，,21xxy132, ,xjyy,,,0(1,,5),,0j12, 利用单纯形法求解辅助问题的过程，见表3。 表3 0 0 0 0 0 1 1 c j b XCxxxxxyyBB1234512 0 1 -2 1 1 0 0 0 11 x4 1 -4 1 2 0 -1 1 0 3 y1 1 -2 0 (1) 0 0 0 1 1 y2 6 -1 -3 0 1 0 0 -4 , j 0 3 -2 0 1 0 0 -1 10 x4 1 0 (1) 0 0 -1 1 -2 1 y1 4 0 -2 0 1 0 0 0 1 -1 x3 0 -1 0 0 1 0 2 1 ,j 0 3 0 0 1 -2 2 -5 12 x4 0 0 1 0 0 -1 1 -2 1 x2 0 -2 0 1 0 0 0 1 1 x3 0 0 0 0 0 1 1 0 ,j 在最优表中，基变量已无人工变量。消去第一阶段最终计算表中人工变量所在列，并将目标函数系数换成LP问题相应系数，进行第二阶段的单纯形法迭代，计算过程列于表4中。 表4 -3 1 1 0 0 c j b XCxxxxxBB12345 0 (3) 0 0 1 -2 12 x4 1 0 1 0 0 -1 1 x2 1 -2 0 1 0 0 1 x3 -1 0 0 0 1 -2 , j 12-3 1 0 0 4 x ,133 1 0 1 0 0 -1 1 x2 241 0 0 1 9 x ,333 110 0 0 2 , j33 T从表4知最优解为:，最优值为:。 X*(4,1,9,0,0),z,,2min 5 四、运用分枝定界方法求解下列整数规划问题: max zxx,，(1) 12 951,xx，, 12(2) ,1414 ,1, ,，,2 xx(3) 12,3 ,(4) xx,0 ,, 12 ,(5) 取整数xx, ,12 解:记整数规划问题为(IP)，它的松弛问题为(LP)。 用单纯形法解(LP),最优解为，而. xx,,32,103max 296z,12 (LP)的最优解不符合整数条件(5).选择较小的进行分枝。x,32(32,103)1由于最接近的整数是1和2，因而可以构造两个约束条件: 32 (6) x,21 (7) x,11 将(6)、(7)分别并入(LP)，形成两个分枝，即子问题(LP)和(LP)，分别由(LP)12及(6)和(LP)及(7)组成。S和S分别是(LP)和(LP)的可行域。 1212 解(LP)，最优解为，，该点不符合整数条件(5)。xx,,2,239max 419z,112 因此，解(LP)，其最优解为，，该点也不符合整xx,,1,73max 103z,212 数条件(5)。因此，继续分枝。 由于，所以优先选择S进行分枝。此时只有不符合整数x,239419103,12条件，故可以构造两个约束条件: (8) x,32 (9) x,22 将(8)和(9)分别并入(LP)，形成两个新分枝，即后继子问题(LP)和(LP)，11112分别由(LP)及(8)和(LP)及(9)组成。S为(LP)的可行域。由于约束条件(8)111212 和(LP)不相容，故(LP)无可行解，也就是说只需考虑子问题(LP)。 11112在S上解(LP)，最优解为，. xx,,3314,2max 6114z,121212 对于原问题来讲，此时还剩下两个分枝:子问题(LP)和(LP)，(LP)最优解2122的目标函数值为，(LP) 最优解的目标函数值为，因此优先考虑103611412 (LP)进行分枝。 12 两个新约束条件为: (10) x,31 (11) x,21 将(10)和(11)分别并入(LP)，又形成两个新的分枝。即后继子问题(LP)和12121(LP)，分别由(LP)及(10)和(LP)及(11)组成。S和S分别为它们的可1221212121122行域。 max 4z,(LP)的最优解是，;(LP)的最优解是，xx,,3,1xx,,2,21211221212max 4z,.这两个解都满足整数条件(5)，且目标函数值相等。至此，对(LP)12 6 的分枝完成。 对于子问题(LP)，由于其最优解的目标函数值为，比界限4小，因此不1032 必再对(LP)进行分枝搜索了。 2 和，综上所述，原整数规划问题的两个最优解为:xx,,3,1xx,,2,21212 . max 4z, 五、试写出用动态规划方法求解下列问题时的基本方程 设有一个外贸公司计划在1月至4月份从事某种商品的经营。已知它的仓库最多可存储1000件这种商品，该公司开业时有存货500件，并根据预测知道，该种商品1月至4 月的进价和售价如表5所示。 表5 月份 1 2 3 4 进价c(百元/10 9 11 15 件) 售价p(百元/12 9 13 17 件) 问如何安排进货量和销售量，使该公司获得最大利润。(假设四月底库存为零。) 解:若将1月至4月份的购销安排作为阶段k (k=1,2,3,4),那么该问题就是一个四阶段决策问题。 选择第k月初公司的存货量作为状态变量，第k月的销售量和进货量sk 分别作为决策变量和。我们不难看出，这一问题的每一阶段都有两个决uvkk 策变量;而且在应用动态规划方法把整个问题分解为若干个子问题后，对每个子问题需应用线性规划解法求解。 状态转移方程是 ssvuk,，,,1,2,3,4kkkk，1 而 001000()1,2,3,4,,,,,,,usvsukkkkkk 由已知，;假想有第五阶段，。 s,500s,015 动态规划基本方程为 7 fspucvfs()max{()()},,，,kkkkkkkk，，11uv,kk, ,,,，，,max{()()}pucvfsvukkkkkkkk，1uv,kk , ,k,4,3,2,1,fs()0,55, 其中，阶段收益函数为 rsuvpucv(;,),,kkkkkkkk 六、已知有6个村子，相互间道路的距离如图1所示。拟合建一所小学，已知A处有小学生50人，B处40人，C处60人，D处20人，E处70人，F处90人，问小学应建在哪一个村子，使学生上学最方便(走的总路程最短)。 B 6 D 6 2 8 F 4 1 A 1 7 3 C 3 E 图1 解:先求出任意两点间的最短路程如表1所示: 表1 从 A B C D E F 到 A 0 2 6 7 8 11 B 2 0 4 5 6 9 C 6 4 0 1 2 5 D 7 5 1 0 1 4 E 8 6 2 1 0 3 F 11 9 5 4 3 0 将表中每行数字分别乘上各村小学生数得表2: 表2 A B C D E F 0 100 300 350 400 550 8 80 0 160 200 240 360 360 240 0 60 120 300 140 100 20 0 20 80 560 420 140 70 0 210 9908104503602700 107010501500213016701040 按列相加，其总和最小的列为D，即小学应建立在D村。 9