临沂师范学院数学本科期未试题 《运筹学》(1) 题号 三四五六七八九十|总分 得分 阅卷人 填空题(15) 1.在求极小值的线性规划问题中,松弛变量在目标函数中的价值系数为 人工变量 在目标函数中的价值系数为 2.某极小化线性规划问题(P)一个“≤”型的约束所对应的(P)对偶问题的决策变量 (P)中的一个取值“≤0”的决策变量对应了(P)对偶问题的一个 型约束。 3.中国邮递员问题的最优解判别定理是 4.若整数规划|4xz= 在x=02时均取得最优解,则其最优解x= x,x2≥0且x,x2为整数 f(x)= 5.图G有支撑树的充要条件是 求图G的最小支撑树常应用的方法是 证明题(15) 1.凸规划问题的一个局部最优解一定是它的全局最优解 2.在任何一个图中,奇点的个数为偶数 3.证明产销平衡的运输问题必有最优解 三、判断对错(10) 1.若X为LP的可行解,则x亦为LP的基本解。() 2.设LP的可行域为D,D非凸集,则LP的最优点必在D的顶点上。()
1 ………………………………装………………………………订……………………………线………………………… 临沂师范学院数学本科期末试题 《运筹学》（１） 一、 填空题（15） 1．在求极小值的线性规划问题中，松弛变量在目标函数中的价值系数为 ，人工变量 在目标函数中的价值系数为 。 2. 某极小化线性规划问题（P）一个“≤”型的约束所对应的（P）对偶问题的决策变量 0， （P）中的一个取值“≤0”的决策变量对应了（P）对偶问题的一个 型约束。 3.中国邮递员问题的最优解判别定理是——————————————————————。 4. 若整数规划 + + = + 1 2 且 1， 2为整数 1 2 1 2 1 2 , 0 4 5 20 2 6 x x x x x x x x MaxZ x x , 在 x1 = 0，2 时均取得最优解，则其最优解 = * x ， ( ) = * f x 。 5. 图 G 有支撑树的充要条件是——————，求图 G 的最小支撑树常应用的方法是——————和 ——————————。 二、 证明题（15） 1． 凸规划问题的一个局部最优解一定是它的全局最优解． 2． 在任何一个图中，奇点的个数为偶数。 3. 证明产销平衡的运输问题必有最优解。 三、判断对错 （10） 1. 若 x ~ 为 LP 的可行解，则 x ~ 亦为 LP 的基本解。（ ） 2. 设 LP 的可行域为 D，D 非凸集，则 LP 的最优点必在 D 的顶点上。（ ） 题号 一 二 三 四 五 六 七 八 九 十 总分 得分 阅卷人 专业： 科类： 科 班级： 级 班 姓名： 学号： 专业： 科类： 科 班级： 级 班 姓名： 学号：
3.若图G是一个树,p(G)≥2,则G中至少有两个悬挂点。() 4.如果线性规划的原问题和对偶问题都具有可行解,则该线性规划问题一定具有有限最优解。() 5.一旦一个人工变量在迭代中变为非基变量后,该变量及相应列的数字可以从单纯形表中删除,而 不影响计算结果。() 四、计算题(45) 1.用对偶单纯形法求解下面的线性规划 max==x+ x2 x1+7x2 ≥0 2.用单纯形法求解如下目标规划的满意解 min : Pd, +Pd2+ pdi x+2x2+d-d=10 10x1+12x2+d-d=624 2 x1,x2,d,d+≥0,i=1,2 3.出逆序解法求解下列动态规划问题的求解模型 五、建模题(15) 在土质不同的两种水田里,相同的水、肥、技术等条件下,种植三种水稻。土地面积、所准备种子可 以供种植的面积以及每公顷产量见下表 稻种可供量(公顷 B C 土地实有量 (公顷) 70900012000|9750 13013500112501050 问如何种植,使总产量最大。试建立这个问题的线性规划的数学模型(不求解) 2
2 3. 若图 G 是一个树，p（G）≥2，则 G 中至少有两个悬挂点。（ ） 4． 如果线性规划的原问题和对偶问题都具有可行解，则该线性规划问题一定具有有限最优解。（ ） 5．一旦一个人工变量在迭代中变为非基变量后，该变量及相应列的数字可以从单纯形表中删除，而 不影响计算结果。（ ） 四、计算题 （45） 1. 用对偶单纯形法求解下面的线性规划 , 0 7 7 2 4 max 1 2 1 2 1 2 1 2 + + = + x x x x x x z x x 2. 用单纯形法求解如下目标规划的满意解： = + + + − = + + − = = + + − + − + − + + − − , , , 0, 1,2 2 8 10 12 62.4 2 10 min 1 2 1 2 1 2 2 2 1 2 1 1 1 2 1 2 2 1 x x d d i x x x x d d x x d d z Pd Pd P d i i 3． 出逆序解法求解下列动态规划问题的求解模型： = = = = 0 ,( 0) ( ) 1 1 i n i i n i i i x x c c Maxz g x 五、 建模题（15） 在土质不同的两种水田里，相同的水、肥、技术等条件下，种植三种水稻。土地面积、所准备种子可 以供种植的面积以及每公顷产量见下表。 土地实有量 （公顷） 稻种可供量（公顷） A B C 50 80 90 甲 70 9000 12000 9750 乙 130 13500 11250 10500 问如何种植，使总产量最大。试建立这个问题的线性规划的数学模型（不求解）