线性代数模拟试题及答案1

第 1 页 共 8 页 一 判断题 本题共一 判断题 本题共 5 5 小题 每小题 分小题 每小题 分 共共 1515 分分 下列叙述中正确的打下列叙述中正确的打 错误的打 错误的打 1 图解法与单纯形法 虽然求解的形式不同 但从几何上理解 两者是一致的 2 若线性规划的原问题有多重最优解 则其对偶问题也一定具有多重最优解 3 如果运输问题单位运价表的某一行 或某一列 元素分别加上一个常数 k 最优调运方 案将不会发生变化 4 对于极大化问题 max Z ij n i n j ijx c 11 令 ijijij ccbcc max 转化为极小化问题 ij n i n j ijx bW 11 min 则利用匈牙利法求解时 极大化问题的最优解就是极小化问题 的最优解 但目标函数相差 n c 5 影子价格是对偶最优解 其经济意义为约束资源的供应限制 二 填空题二 填空题 本题共本题共 8 8 小题小题 每空每空 3 3 分分 共共 3636 分分 把答案填在题中横线上把答案填在题中横线上 1 在线性规划问题的约束方程中 对于选定的基 B 令非基变量 XN 0 0 m n AXb X 得到的解 X 若 则称此基本解为基本可行解 2 线性规划试题中 如果在约束条件中出现等式约束 我们通常用增加 的方法来产生初始可行基 3 用单纯形法求解线性规划问题的迭代步骤中 根据 确定为进基变 k k x 量 根据最小比值法则 确定为出基变量 r x 4 原问题有可行解且无界时 其对偶问题 反之 当对偶问题无可行 解时 原问题 5 对于 Max 型整数规划问题 若其松弛问题的最优单纯形表中有一行数据为 XBb1 x 2 x 3 x 4 x 第 2 页 共 8 页 x23 4017 4 11 4 则对应的割平面方程为 6 原问题的第 1 个约束方程是 型 则对偶问题相应的变量是 变量 7 用 LINGO 软件求解整数规划时 要说明变量 X 是只可以取 0 或 1 的整数变量 则要用 命令函数 8 用匈牙利法解分配问题时 当 则找到了分配问题的最优解 称此时 独立零元素对应的效益矩阵为 三 解答题三 解答题 本题共本题共 6 6 小题小题 共共 4949 分分 1 已知线性规划问题 利用对偶理论证明其目标函数值无界 8 8 分分 123 123 123 123 max34 236 347 0 zxxx xxx xxx x x x 2 试用大 M 法解下列线性规划问题 8 8 分分 12 1 2 12 12 max35 4 6 3218 0 zxx x x xx x x 3 福安商场是个中型的百货商场 它对售货人员的需求经过统计分析如下表所示 为了 保证售货人员充分休息 售货人员每周工作五天 休息两天 并要求休息的两天是连续的 问该如何安排售货人员的休息 既满足了工作需要 又使配备的售货人员的人数最少 请 列出此问题的数学模型 8 8 分分 时间所需售货人员数时间所需售货人员数 星期一 28 星期五 19 星期二 15 星期六 3l 星期三 24 星期日 28 星期四 25 4 建立模型题 10 10 分分 在高校篮球联赛中 我校男子篮球队要从 名队员中选择平均身高最高的出场阵容 队员 的号码 身高及擅长的位置如下表 第 3 页 共 8 页 队员 身高 m 位置 1 92 中锋 1 90 中锋 1 88 前锋 1 86 前锋 1 85 前锋 6 1 83 后卫 7 1 80 后卫 1 78 后卫 同时 要求出场阵容满足以下条件 中锋最多只能上场一个 至少有一名后卫 如果 号队员和 号队员都上场 则 号队员不能出场 号队员和 号队员必须保留一个不出场 问应当选择哪 5 名队员上场 才能使出场队员平均身高最高 1 建立该问题的数学模型 2 写出用 LINGO 软件求解它时的源程序 5 从甲 乙 丙 丁 戊五人中挑选四人去完成四项工作 已知每人完成各项工作的时 间如下表所示 规定每项工作只能由一个人去单独完成 每个人最多承担一项工作 假定 甲必须保证分配到工作 丁因某种原因不同意承担第四项工作 在满足上述条件下 如何 分配工作 使完成四项工作总的花费时间最少 8 8 分分 人 工作 一二三四 甲 1051520 乙 210515 丙 3151413 丁 15276 戊 94158 6 用割平面法求解下面的纯整数规划问题 7 7 分分 12 12 12 12 max 26 4520 0 zxx xx stxx xx 且全为整数 第 4 页 共 8 页 参考答案参考答案 一 判断题 本题共一 判断题 本题共 5 5 小题 每小题 分小题 每小题 分 共共 1515 分分 下列叙述中正确的打下列叙述中正确的打 错误的打 错误的打 二 填空题二 填空题 本题共本题共 8 8 小题小题 每空每空 3 3 分分 共共 3636 分分 把答案填在题中横线上把答案填在题中横线上 1 2 人工变量 3 1 0 B b 1 0B b max j 00 min 0 ir ij rj bb b bijb 4 无可行解 或有无界解或无可行解 5 6 无非负限制 345 313 444 xxx 7 bin x 8 得到 n 个独立零元素 最优解矩阵 三 解答题三 解答题 本题共本题共 6 6 小题小题 共共 4949 分分 1 证明 原问题的对偶问题是 12 12 12 12 123 min67 33 24 341 0 wyy yy yy yy y yy 由于第一个约束条件不成立 所以对偶问题无可行解 由此可知原问题无最优解 又容易知 是原问题的可行解 所以原问题具有无界解 即目标值无界 100 T X 2 加入人工变量 化原问题为标准形 1234512 13 24 125 12345 max3500 33 52 18 4 212 3218 0 zxxxxMxM xM xM xx xx xxx x x x x x 单纯形表如下 B X b 1 x 2 x 3 x 4 x 5 x 3 x 4101004 4 x 601010 5 x 18320016 第 5 页 共 8 页 Z 18M3 3M5 2M000 迭代一次后 B X b 1 x 2 x 3 x 4 x 5 x 1 x 410100 4 x 6010106 5 x 602 3013 Z 12 6M05 2M 3 3M00 再迭代一次后 B X b 1 x 2 x 3 x 4 x 5 x 1 x 4101004 4 x 3003 21 1 22 2 x 301 5 201 2 Z 27009 20 5 2M 再迭代一次后 B X b 1 x 2 x 3 x 4 x 5 x 1 x 2100 2 31 3 3 x 20012 3 1 3 2 x 601010 Z 36000 3 7 2 2M 所以最优解为 2 6 2 0 0 36Xz 3 解 设为从星期开始休息的人数 则 i x 1 2 7 i i 第 6 页 共 8 页 7 1 5 1 6 2 7 3 45671 56712 67123 71234 min 28 15 24 25 19 31 28 0 1 2 7 i i i i i i i i i zx x x x xxxxx xxxxx xxxxx xxxxx xi 4 解 设 0i 1i i x 第个队员入选 第个队员不入选 12345678 12 678 146 26 8 1 1 max 1 921 901 881 861 851 831 801 78 5 1 1 2 1 5 01 i i i zxxxxxxxx xx xxx xxx xx x x 取或 Modle max 1 92 1 1 90 2 1 88 3 1 86 4 1 85 5 1 83 6 1 80 7 1 78 8 5 121 6781 1462 261 123456785 xxxxxxxx xx xxx xxx xx xxxxxxxx bin X1 bin X2 bin X3 bin X4 bin X5 bin X6 bin X7 bin X8 第 7 页 共 8 页 End 5 解 10 5 15 20 M 8 3 10 12 M 5 0 7 9 M 3 2 10 5 15 0 0 8 0 7 0 0 8 0 7 0 3 15 14 13 0 1 13 9 5 0 1 13 9 5 0 15 2 7 M 0 13 0 2 M 8 0 13 0 2 M 8 0 9 4 15 8 0 7 2 10 0 0 7 2 10 0 0 4 0 6 8 M 3 0 9 0 7 1 0 13 8 4 0 12 0 1 M 9 0 7 3 10 0 1 此时 费用最小 218553 Z 其中 丙 一 甲 二 乙 三 戌 四 6 解 运用单纯形法得松弛问题的最优解为 对应最优单纯形表如下 12 5813 max 333 xxz B X b 1 x 2 x 3 x 4 x 1 x 5 3 100 2 3 2 x 8 3 0012 3 Z 13 3 00 1 6 1 6 由第一个约束条件得 则得到割平面方程为 代入上表得 134 515 663 xxx 345 552 663 xxx B X b 1 x 2 x 3 x 4 x 5 x 1 x 5 3 100 2 31 3 2 x 8 3 0012 3 1 3 5 x 2 3 00