运筹学 试卷A2006.1.doc

运筹学 试卷（A） 2006年1月 时间120分钟一、（10分)已知如下线性规划问题(1) 用大M法求最优解；(2) 最优解是否唯一。若是，说明理由；若不是，求出另一最优解。二 、(10分)下表为用单纯形法计算时某一步的表格。已知该线性规划的目标函数为，约束形式为，为松弛变量，表中解代入目标函数后得z=16，求表中字母ah。 x1 x2 x3 x4 x5x3x2x12a2b 0 1 1/3 -1/3c e 0 1/2 0d 0 0 -1/3 hf 0 0 g -1三、(10分)已知下述线性规划问题 其最优解为。写出对偶问题，并根据对偶理论求出k的值和对偶问题的最优解。四、(10分) 用表上作业法求解下表所示运输问题的最优调运方案和最小总运费，并讨论最优调运方案是否唯一，若不唯一，找出不同的最优调运方案。 销地产地B1B2B3产量A1A26357421525销量201015五、(10分) 设有M1、M2、M3三台机器可以安装在A、B、C和D四个不同位置，各种不同安装的费用见下表。M2不能安装在位置C。试求使安装费用最小的方案。 位置机器ABCDM1M2M3161181012171213151816六、(10分) 用动态规划解以下极大值问题：运筹学 试卷（A） 2006年4月 时间120分钟学院 班级 序号 姓名 一、（20分)已知如下线性规划问题(1) 化成标准型，并求一个基可行解；(2) 用单纯型法求最优解。二 、(20分)下表为用单纯形法求极大值计算时某一步的表格。当为何值时（1）现有解为唯一最优解；（2）现有解为最优解并有无穷多最优解；（3）存在可行解，但目标函数值无界。 0 0 0bx1 x2 x3 x4 x5x3x4x5d234 1 0 0-1 -5 0 1 0 -3 0 0 1三、(20分)已知下述线性规划问题 （1）写出对偶问题；（2）证明原问题目标函数值。四、(20分) 用表上作业法求解下表所示运输问题的最优调运方案和最小总运费。 销地产地B1B2B3B4产量A1A2A31637235442708065销量40307060运筹学 试卷（B） 2005年 时间120分钟一、 (20分)考虑如下线性规划问题(1) 化成标准型；(2) 找出一初始基可行解及相应的基变量与非基变量；(3) 将线性规划转化成典式，并列出相应单纯型表；(4) 以上初始基可行解是否为最优解，为什么？二 、(20分)用两阶段法求解下述线性规划三、(20分)已知下述线性规划问题 其最优解为。写出对偶问题，并根据对偶理论求出k的值和对偶问题的最优解。四、(20分)下表是用单纯形法计算时某一步的表格，已知该线性规划的目标函数是，约束形式为，为松弛变量，x1x2x3x4x3x12cd0e101/51-10b-1fg求ag的值；表中给出的解是否为最优解五、(20分)已知两个产地A1、A2和三个销地B1、B2、B3的产销量和单位运价表如下所示 销地产地B1B2B3产量A1A23754981525销量201015求最总运费最少的调拨方案，并说明最优调运方案是否唯一.运筹学 试卷（B） 2006年1月 时间120分钟一、（10分）已知如下线性规划问题(1) 用两阶段法求最优解；(2) 最优解是否唯一。若是，说明理由；若不是，求出另一最优解。二 、(10分)下表为用单纯形法计算时某一步的表格。已知该线性规划的目标函数为，约束形式为，为松弛变量，表中解代入目标函数后得z=14，求表中字母ag。 x1 x2 x3 x4 x5 x5X6x2x4a503 0 -14/3 0 1 16 d 2 0 5/2 00 e f 1 0 0b c 0 0 -1 g三、(10分)已知下述线性规划问题 其对偶问题的最优解为。写出对偶问题，并根据对偶理论求出原问题的最优解。四、(10分) 用表上作业法求解下表所示运输问题的最优调运方案和最小总运费。 销地产地B1B2B3B4产量A1A2A3351637235442708065销量40307060五、(10分) 欲指派张、王、李、赵分别加工A、B、C和D四种不同零件，每人所需时间见下表。试求使总时间最小的指派方案。 零件人ABCD张王李赵467961083571188894六、(10分) 用动态规划解以下极大值问题：运筹学 试卷（B） 2006年4月 时间120分钟一、（10分）已知如下线性规划问题 用单纯型法求最优解。二 、(20分)下表为用单纯形法计算时某一步的表格。已知该线性规划的目标函数为，约束形式为，为松弛变量，表中解代入目标函数后得z=14，求表中字母ag。 x1 x2 x3 x4 x5 x5X6x2x4a503 0 -14/3 0 1 16 d 2 0 5/2 00 e f 1 0 0b c 0 0 -1 g三、(20分)已知线性规划问题 其对偶问题的最优解为，试根据对偶理论求出原问题的最优解。四、(20分) 用表上作业法求解下表所示运输问题的最优调运方案和最小总运费。 销地产地B1B2B3B4产量A1A2A3379547985452300500600销量150100400450中国矿业大学20062007学年第 一 学期 运筹学 试卷（A）卷考试时间：120 分钟 考试方式：闭卷一、 简答题：（共15分）1、 （8分）线性规划的标准型有哪些限制？如何把一般的线性规划化成标 准型？2、（7分）单纯形法中选择换出变量的法则是什么？违背这一法则会出现什么问题？二、（10分）用大M法或两阶段法求解下述线性规划： 三、（10分）已知某线性规划的初始单纯形表和最终表，请把表中空白处的数字填上。要求指出最优基B及B-1，写出最终表中非基变量的检验数的计算过程。2 -1 1 0 0 0bx1 x2 x3 x4 x5 x6x4x5x63 1 1 1 0 01 -1 2 0 1 01 1 -1 0 0 12 -1 1 0 0 0x4x1x210155 -1 -2 1/2 1/2 -1/2 1/2四、（15分）已知线性规划问题：的最优解是。a) 写出其对偶问题。b) 用互补松弛定理求其对偶问题的最优解，若有无穷多最优解，求出一个即可。五、（20分）设有A1，A2 ，A3三个产地生产某种物资，其产量分别是7，5，7；B1，B2 ，B3 ，B4四个销地需要该种物资，销量分别是2，3，4，6。又知各产销地之间的单位运价表如下。试决定总费用最少的调运方案。并说明最优调运方案是否唯一，若不唯一，求出另一最优方案。 B1 B2 B3 B4A1A2A32 11 3 410 3 5 97 8 1 2757 2 3 4 6六、（20分）用动态规划求解以下极大值问题： 七、（10分）已知分配问题的效率矩阵如下： （1） 写出对应分配问题的数学模型（目标是最小）。（2） 用匈牙利法求解。中国矿业大学20062007学年第 一 学期 运筹学 试卷（B）卷考试时间：120 分钟 考试方式：闭卷一、 简答题：（10分）图解法的主要步骤是什么？从中可以看出线性规划的最优解有哪些特点？二、（10分）用大M法或两阶段法求解下述线性规划： 三、（10分）已知某线性规划的最终表如下，初始基变量是 x1， x4，x5 。（1）求最优基B。（2）求初始表。 0 1 -2 0 0 bx1 x2 x3 x4 x5 x1x2x313/25/21/2 1 0 0 -1/2 5/20 1 0 -1/2 3/20 0 1 -1/2 1/2 0 0 0 -1/2 -1/2四、（20分）已知线性规划问题：的最优解是。（1） 写出其对偶问题。（2） 用互补松弛定理求其对偶问题的最优解。五、（20分）某工厂有B1，B2 ，B3三个分厂，在生产中需要用的热水分别由A1，A2 两个锅炉房供应。每月各分厂的需求量、锅炉房的供应量及输送热水的单位费用见下表。由于需求量大