运筹学模拟题及答案5套.pdf

西南交通大学 2士研究生入学考试试卷 1 008 年硕西南交通大学 2士研究生入学考试试卷 1 008 年硕 试题代码：试题代码：453 试题名称：运筹学试题名称：运筹学 考生注意 考生注意 本试题共 七 本试题共 七 题，共 3 题，共 3 页，请考生认真检查； 请务必将答案写在 页，请考生认真检查； 请务必将答案写在答卷纸答卷纸上，写在试卷上的答案无效。上，写在试卷上的答案无效。 题号 一 二 三 四 五 六 七 总分 得分 签字 一某炼油厂生产三种牌号的汽油，70#，80#和 85#汽油。每种汽油有不同的辛 烷值和含硫量的质量要求并由三种原料油调和而成。 每种原料也有不同的质量指 标。每种原料每日可用数量、质量指标和生产成本见表 1，每种汽油的质量要求 和销售价格见表 2。问该炼油厂如何安排生产才能使其利润最大？假定在调和中 辛烷值和含硫量指标都符合线性相加关系。试建立数学模型。 （25 分) 表 1 序号 i 原料 辛烷值 含硫量（） 成本（元/吨） 可用量（吨/日） 1 直馏汽油62 1.5 600 2000 2 催化汽油78 0.8 900 1000 3 重整汽油90 0.2 1400 500 表 2 序号 j 产品 辛烷值 含硫量（）销售价（元/吨） 1 70汽油 70 1 900 2 80汽油 80 1 1200 3 85汽油 85 0.6 1500 二用对偶单纯形法求解下列线性规划问题： （25 分） 0, 964 52 5 2max 321 32 32 321 21 xxx xx xx xxx xxz 三已知某运输问题的产销平衡表与单位运价表如下表所示，B2地区需要的 115 单位必须满足，试确定最优调拨方案。 （20 分） Ai Bj B1 B2 B3 B4 B5 产量 A1 10 15 20 20 40 50 A2 20 40 15 30 30 100 A3 30 35 40 55 25 130 销量 25 115 60 30 70 四从甲, 乙, 丙, 丁, 戊五人中挑选四人去完成四项工作，已知每人完成各项工 作的时间如下表所示。规定每项工作只能由一个人去单独完成，每个人最多承担 一项工作，假定甲必须保证分配到工作，丁因某种原因不同意承担第四项工作。 在满足上述条件下， 如何分配工作， 使完成四项工作总的花费时间最少。 （20 分） 人 工作 一 二 三 四 甲 10 5 15 20 乙 2 10 5 15 丙 3 15 14 13 丁 15 2 7 6 戊 9 4 15 8 五求 V1到各点的最短路及最短路径。 （20 分） 六某公司有资金 4 百万元向 A，B，C 三个项目追加投资，各个项目可以有不 同的投资额（以百万元为单位） ，相应的效益值如下表。问怎样分派资金，使总 效益值最大，试用动态规划方法求解。 （25 分） 项目 投资额 0 1 2 3 4 A 38 41 48 60 66 B 40 42 50 60 66 C 38 64 68 78 76 七用单纯形法解线性规划问题，如何判断下列问题： （15 分） 1. 无可行解； 2. 有多重解； 3. 有无界解。 西南交通大学 2士研究生入学考试试卷 2 008 年硕西南交通大学 2士研究生入学考试试卷 2 008 年硕 试题代码：试题代码：453 试题名称：运筹学试题名称：运筹学 考生注意 考生注意 本试题共 七 本试题共 七 题，共 3 题，共 3 页，请考生认真检查； 请务必将答案写在 页，请考生认真检查； 请务必将答案写在答卷纸答卷纸上，写在试卷上的答案无效。上，写在试卷上的答案无效。 题号 一 二 三 四 五 六 七 总分 得分 签字 一华津机器制造厂专为拖拉机厂配套生产柴油机，今年头四个月收到的订单数 量分别为 3000，4500，3500，5000 台柴油机。该厂正常生产每月可生产柴油机 3000 台，利用加班还可生产 1500 台。正常生产成本为每台 5000 元，加班生产 还要追加 1500 元成本，库存成本为每台每月 200 元。华津厂如何组织生产才能 使生产成本最低，建立其线性规划模型。 （20 分） 二考虑线性规划问题： （25 分） 0, 232 52 4125max 321 321 321 321 xxx xxx xxx xxxz 用单纯形法求解，得其终表如下： cj 5 12 4 0 -M CB XB x1 x2 x3 x4 x5 B-1b 12 x2 0 1 -1/5 2/5 -1/5 8/5 5 x1 1 0 7/5 1/5 2/5 9/5 cz jj 0 0 -3/5 -29/5-M+2/5 X4为松弛变量，X5为人工变量， 1上述模型的对偶模型为： ； 2对偶模型的最优解为： ； 3当两种资源分别单独增加一个单位时，目标函数值分别增加 和 ； 4最优基的逆矩阵 B -1 = 5如果原问题增加一个变量，则对偶问题的可行域将可能变大还是变小？ . 三求解下列各题（解题方法自选）（20 分） ) 3 , 2 , 1; 3 , 2 , 1( 01 1 1 1 1 1 1 544 121081065min 332313 322212 312111 333231 232221 131211 333231 232221131211 jix xxx xxx xxx xxx xxx xxx xxx xxxxxxz ij 或 四用隐枚举法求解下列 0-1 规划问题（20 分） max , zxxxxx xxxxx xxxxx xxxx xj j 57103 354 263220 22 0115 1234 12345 12345 2345 2 1 5 五用动态规划方法求解下列问题（25 分） 3 , 2 , 10 1 )1 (max 321 321 jx xxx xxxz j 六 今有三个仓库运送某种产品到四个市场上去， 仓库的供应量是 20， 20 和 100， 市场需求量是 20，20，60 和 20，仓库与市场之间的路线上的容量如下表（容量 零表示两点间无直接的路线可通） 。用图论方法确定现有路线容量能否满足市场 的需求，若不能，应修改哪条线路的容量。 （20 分） 市场 仓库 1 2 3 4 供应量 1 30 10 0 40 20 2 0 0 10 50 20 3 20 10 40 5 100 需求量 20 20 60 20 七下列叙述中正确的是 （ ） （20 分） 4 图解法与单纯形法，虽然求解的形式不同，但从几何上理解，两者是一致的； 5 若线性规划的原问题有多重最优解，则其对偶问题也一定具有多重最优解； 6 如果运输问题单位运价表的某一行（或某一列）元素分别加上一个常数 k， 最优调运方案将不会发生变化； 7 对于极大化问题 max Z =令 ij n i n j ijx c 11 ijijij ccbcc,max 转化为极小化 问题，则利用匈牙利法求解时，极大化问题的最优解就是 极小化问题的最优解，但目标函数相差： n+c； ij n i n j ijx bW 11 min 8 如果图中从 i v 至各点均有惟一的最短路，则连接至其他各点的最短路在去掉 重复部分后，恰好构成该图的最小支撑树。 西南交通大学 2士研究生入学考试试卷 3 008 年硕西南交通大学 2士研究生入学考试试卷 3 008 年硕 试题代码：试题代码：453 试题名称：运筹学试题名称：运筹学 考生注意 考生注意 本试题共 七 本试题共 七 题，共 3 题，共 3 页，请考生认真检查； 请务必将答案写在 页，请考生认真检查； 请务必将答案写在答卷纸答卷纸上，写在试卷上的答案无效。上，写在试卷上的答案无效。 题号 一 二 三 四 五 六 七 总分 得分 签字 一用单纯形法求解下述线性规划问题（20 分） 0, 82 44 2 4max 21 21 21 21 21 xx xx xx xx xxz 二设一线性规划问题为（25 分） max , zxxx xxx xx xj j 27 6 24 013 12 12 12 3 3 其最优单纯形表为 cj 2 -7 1 0 0 CB XB x1 x2 x3 x4 x5 B-1b 2 x1 1 1 1 1 0 6 0 x5 0 3 1 1 1 10 cz jj 0 -9 -1 -2 0 在下述每一种情况下，进行灵敏度分析并求出最优解。 2 目标函数变为maxz xxx23 123； 3 约束条件右端项由(6,4) T变为(3,5)T； 4 增加一个约束条件 xx 13 22 三某种产品今后四周的需求量分别为 300，700，900，600 件，必须得到满足。 已知每件产品的成本在起初两周是 10 元，以后两周是 15 元。工厂每周能生产这 种产品 700 件，且在第二、三周能加班生产。加班后，每周可增产 200 件产品， 但成本每件增加 5 元。产品如不能在本周交货，则每件每周存贮费是 3 元。问如 何安排生产计划，使总成本最小，要求建立运输问题数学模型求解。 （25 分） 四某校蓝球队准备从以下 6 名预备队员中选拔 3 名为正式队员，并使平均身高 尽可能高，这 6 名预备队员情况如下表所示，试建立数学模型。 （20 分） 队员的挑选要满足下列条件： 2 少补充一名后卫队员； 3 大李或小田中间只能入选一名； 4 最多补充一名中锋； 5 如果大李或小赵入选，小周就不能入选。 预备队员 号码 身高（厘米） 位置 大张 大李 小王 小赵 小田 小周 4 5 6 7 8 9 193 191 187 186 180 185 中锋 中锋 前锋 前锋 后卫 后卫 五某高校拟开设文学、艺术、音乐、美术四个学术讲座。每个讲座每周下午举 行一次。 经调查知， 每周星期一至星期五不能出席某一讲座的学生数如下表： （20 分） 星期 讲座 一 二 三 四 五 文学 50 40 60 30 10 艺术 40 30 20 30 20 音乐 40 30 30 20 10 美术 20 30 20 30 30 问：应如何安排一周的讲座日程，使不能出席讲座的学生总数最少，并计算不能 出席讲座的学生总数。 六某飞行队有 5 名正驾驶员和 5 名副驾驶员。由于种种原因，某些正、副驾驶 员不能同机飞行，某些则可以，如下表所示。每架飞机出航时需正，副驾驶员各 一人。问最多能有几架飞机同时出航？应如何安排正，副驾驶员?用图论方法求 解。 （20 分） 正 副 B1 B2 B3 B4 B5 A1 * * A2 * * A3 * * A4 * * A5 * 七填空： （20 分） 1某工程公司拟从四个项目中选择若干项目，若令 i x = 4 , 3 , 2 , 1 0 1 i i i 个项目未被选中；，第 个项目被选中；，第 用的线性表达式表示下列要求： i x （1）从 1，2，3 项目中至少选 2 个： ； （2）只有项目 2 被选中，项目 4 才能被选中： ； 2用表上作业法求解某运输问题，若已计算出某空格的检验数为-2，则其经 济意义是 ，若从 该空格出发进行调整，设调整量为 2，则调后可使总运费下降 ； 10 动态规划中的 Bellman 最优性原理是 。 西南交通大学 20士研究生入学考试试卷 4 08 年硕 西南交通大学 20士研究生入学考试试卷 4 08 年硕 试题代码：试题代码：453 试题名称：运筹学试题名称：运筹学 考生注意 考生注意 本试题共 七 本试题共 七 题，共 3 题，共 3 页，请考生认真检查； 请务必将答案写在 页，请考生认真检查； 请务必将答案写在答卷纸答卷纸上，写在试卷上的答案无效。上，写在试卷上的答案无效。 题号 一 二 三 四 五 六 七 总分 得分 签字 一对约束条件（20分） xxxxx xxxx xxxx xj j 12356 3467 1247 481 223 4102 017, 7 2 9 1 说明解 X=（1,2,1,0,0,0,0）T是不是基可行解，假定不是，试找出一个基可 行解。 二已知线性规划问题（20分） 0, 0 6 4 22m 21 321 321 321 xx kxxx xxx xxxinz 其最优解为x xx 12 50 , 3 1求k的值； 2求出对偶问题的最优解 三已知某运输问题的产销平衡表与单位运价表如下表所示（25分） Ai Bj B1 B2 B3 B4 B5 产量 A1 10 15 20 20 40 50 A2 20 40 15 30 30 100 A3 30 35 40 55 25 150 销量 25 115 60 30 70 1求最优调拨方案； 2如产地 A3的产量变为 130，又 B2地区需要的 115 单位必须满足，试重新确 定最优调拨方案 四.塞尔默公司的营销经理将要主持召开一年一度的由营销区域经理以及销售人 员参加的销售协商会议。为了更好地安排这次会议，他雇佣了四个临时工（安、 伊恩、琼、肖恩） ，每一个人负责完成下面的一项任务：1.书面陈述的文字处理； 2.制作口头和书面陈述的电脑图；3.会议材料的准备，包括书面材料的抄写和组 织；4.处理与会者的提前和当场注册报名。虽然这四个临时工都有完成这四项任 务所需的基本能力， 但是在他们完成每一项任务时所表现出来的有效程度是有很 大差异的。表 1 显示了每一个人完成每一项任务所用的时间（单位：小时） 。试 问营销经理应该将哪一项任务指派给哪一个人，才能使总时间最小？（20分） 表 1 塞尔默公司问题中的有关数据 文字处理 制作电脑图材料准备记录 安 35 41 27 40 伊恩 47 45 32 51 琼 39 56 36 43 肖恩 32 51 25 46 五用动态规划方法求解下列问题（25分） max , , zxxx x x x xj j 34 9 012 3 1 2 2 2 3 2 1 2 3 六求解下图的中国邮路问题（20分） 6 2 3 4 2 5 1 2 2 1 6 七选择（20分） 1标准形式的线性规划问题，其可行解（ ）是基可行解，最优解（ ）是可 行解，最优解（ ）在可行域的某一顶点。 （a）一定 （b）不一定 （c）一定不 2影子价格是（ ） ，其经济意义为（ ） （a）对偶最优解 （b） （c）约束资源的供应限制 bB 1 （d）约束条件所付的代价 3运用表上作业法求解运输问题时，计算检验数可用（ ） （a）闭回路法 （b）西北角法 (c) 位势法 (d) 最小元素法 4动态规划的研究对象是（ ） ，其求解的一般方法是（ ） （a）最优化原理 （b）静态决策 （c）逆序求解 （d）函数迭代法 （e）多阶段决策过程 西南交通大学 20士研究生入学考试试卷 5 08 年硕西南交通大学 20士研究生入学考试试卷 5 08 年硕 试题代码：试题代码：453 试题名称：运筹学试题名称：运筹学 考生注意 考生注意 本试题共 七 本试题共 七 题，共 3 题，共 3 页，请考生认真检查； 请务必将答案写在 页，请考生认真检查； 请务必将答案写在答卷纸答卷纸上，写在试卷上的答案无效。上，写在试卷上的答案无效。 题号 一 二 三 四 五 六 七 总分 得分 签字 一对约束条件（20分） xxxxx xxxx xxxx xxx xj j 12456 3467 1247 346 38 2234 4102 336 017 13 19 , 说明解 X=（1,2,1,1,0,0,0）T是不是基可行解，假定不是，试找出一个基可行解。 二某极小化线性规划的最优单纯形表为（25分） XB x1 x2 x3 x4 x5 b x3 0 1/2 1 1/2 0 5/2 x1 1 -1/2 0 -1/6 1/3 5/2 cz jj 0 -4 0 -4 -2 其中，为松驰变量，问题的约束为形式 x4x5 1写出原线性规划问题； 2写出原问题的对偶问题； 3直接由最优表写出对偶问题的最优解。 三考虑四种不同类型的机器和五项任务的分配问题，可利用的四种类型机器的 台数是 25，30，20 和 30，五项任务的工作量是 20，20，30，10 和 25，不能把 第 4 类机器分配到第 4 项工作上，单位成本如下表所示，求各类机器分到各项任 务上的最优分配。 （20分） 任务类型 1 2 3 4 5 机 1 10 2 3 15 9 器 2 5 10 15 2 4 类 3 15 5 14 7 15 型 4 20 15 13 8 四有 A、B、C 三种资源可用来生产甲、乙、丙三种产品。资源量、单位产品 利润和单位产品资源消耗量、各种产品生产的固定费用如下表所示。现在要求制 定一个生产计划，使总收益最大，试建立数学模型。 （20分） 单位产品 产品 资源消耗量 甲 乙 丙 资源限量 资源 A 2 4 8 500 B 2 3 4 300 C 1 2 3 100 单件利润 4 5 6 固定费用 100 150 200 五动态规划方法是解决 ，它是在明确 条件的基础 上，建立 ，最终应求出 。 （20分） A、动态问题 B、多阶段决策过程的问题 C、阶段和阶段数 D、无后效性 E、最优性原理 F、基本方程（递推关系式） G、决策变量与允许决策集合 H、阶段指标与指标函数 I、状态转移方程 J、逆序解法和顺序解法 K、最优决策序列和最优目标值 L、状态与状态变量 六有 3 个电站 t1，t2，t3，每月每个电站各需 60kt 煤，有 2 个煤矿 S1，S2，每 月每个煤矿可提供 100kt 煤。煤矿向电站每月的最大运输能力： （25分） 运输量/ kt t1 t2 t3 S1 40 40 30 S2 40 20 50 各线路的千吨运费为 运价 / 千元 t1 t2 t3 S1 4 5 8 S2 5 5 6 试用网络分析方法给出供煤方案，使总运费最小。 七什么是线性规划问题的灵敏度分析？（20分） 第一套第一套 一、解：设代表第 i 种原料混入第 j 种产品中的数量，其中 i=1，2，3；j=1，2，3；则 3 , 2 , 1, 3 , 2 , 1, 0 2 . 08 . 05 . 1 2 . 08 . 05 . 1 2 . 08 . 05 . 1 85907862 80907862 70907862 500 1000 2000 140090060015001200900max 3 1 3332313 3 1 2322212 3 1 1312111 3 1 3332313 3 1 2322212 3 1 1312111 3 1 3 3 1 2 3 1 1 3 1 3 3 1 2 3 1 3 1 13 3 1 2 3 1 1 jix xxxx xxxx xxxx xxxx xxxx xxxx x x x xxxxxxZ ij i i i i i i i i i i i i j j j j j j j j j j ij ji i i i i 二、解：原问题可化为： 52 , 1, 0 94 52 5 2max 532 432 321 21 ix xxx xxx xxx xxZ i 2 1 0 0 0 124 1 x x 3 x x 5 x b 2 1 x 0 4 x 0 5 x 1 1 1 0 0 0 2 1 1 0 0 -4 -6 0 1 5 5 -9 j r 0 -1 -2 0 0 ijj ar / - 1/4 1/3 - - 2 1 x 0 4 x 0 5 x 1 0 1/2 0 1/4 0 0 -2 1 1/2 0 1 3/2 0 -1/4 j r 0 0 -1/2 0 -1/4 -31/4 4 31 ) 4 9 , 4 11 (),( * 21 * Z xxX TT 三、解：将原问题改成产销平衡问题，并用沃格尔法给出初始解得： 124 B B 3 B B 5 B 产 j v 销 产 1 A 10 5 15 50 20 20 20 5 40 35 50 -15 2 A 20 10 40 10 15 60 30 30 30 10 100 0 3 A 30 5 35 65 40 20 55 20 25 65 130 5 A 0 15 M M-10 0 5 0 -10 0 5 20 -20 销 25 115 60 30 70 300 i u 20 30 15 30 20 此方案还不是最优，需要调整 销 产 124 B B 3 B B 5 B 产 j v 1 A 10 15 15 50 20 30 20 15 40 35 50 -25 2 A 20 25 40 0 15 60 30 15 30 0 100 0 3 A 30 15 35 65 40 30 55 30 25 65 130 -5 A 0 10 M M-10 0 15 0 15 0 5 20 -30 销 25 115 60 30 70 300 i u 20 40 15 30 30 此时检验数均大于或等于 0，为最优解 650025*6515*3015*6035*6550*1520*25 * Z 四、解： 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 其中，丙 一， 甲 二， 乙 三， 戌 四 五、解： 1 v 2 v 3 v 4 v 5 v 6 v 7 v 0* 11 9* 10 11 10* 20 11* 21 20 21 21* 21* 28 25* 21 vv 11 ： 21 vv 9 ： 31 vv 31 vv 10 ： 41 vv 41 vv 21 ： 51 vv 541 vvv 20 ： 61 vv 631 vvv 25 ： 71 vv 7541 vvvv 六、解： 阶段：以向某一项目投资作为一个阶段，如此可划分为三个阶段。 状态变量：以可以提供的投资额作为状态变量 ，其范围为 0，1，2，3，4 百 万 i s 决策变量：以给某项目投资的金额作为决策变量，则 i x ii sx 状态转移方程： iii dss 1 40 , 3 3 sk 3 s 3 x 0 1 2 3 4 )( 33 sf 3 x * 0 1 2 3 4 38 41 48 60 66 38 41 48 60 66 0 1 2 3 4 40 , 2 2 sk 2 s 2 x 0 1 2 3 4 )(sf 22 2 x * 0 1 2 3 4 40+38 40+41 42+38 40+48 42+41 50+38 40+60 42+48 50+41 60+38 40+66 42+60 50+48 60+41 66+38 78 81 88 100 106 0 0 0，2 0 0 4, 1 1 sk 1 s 1 x 0 1 2 3 4 )( 11 sf 1 x * 4 38+106 64+100 68+88 78+81 76+78 164 1 总效益最大值为 164，其中 3, 0, 1 321 xxx 。 七、解： 1、无可行解：最终表人工变量不为零；或右侧常数 0 i b ，对应的； 0 ij a 2、有多重解：（非基变量）且至少有一个为零。 0 j r 3、有无界解：非基变量的检验数 ，且对应的系数列向量a。 0 j r0 ij 第二套第二套 一、解：设代表第 i 月正常生产的柴油机数量， i x 代表第 i 月加班生产的柴油机数量， i y 代表第 i 月末的库存量，则=4 i z i z 4 , 3 , 2 , 1, 0, 5000 3500 4500 3000 20065005000min 443 332 221 11 4 1 4 1 4 1 izyx yxz yxz yxz yx zyxZ iii i i i i i i 二、解： 1、 对偶模型 无约束 21 21 21 21 21 , 0 43 122 52 25min yy yy yy yy yyW 2、 由单纯形表可看出， 5 29 5 29 1 )(*y 由于 0, 0 0, 0, 0; 0 21 212211 ss ss yy xxxyxy而 则对偶问题的第一、二个约束是紧的，可解出 5 2 2 y 将代入第三个约束，满足约束条件，则21, y y 5 141 5 2 5 29 21 *),(),(*wyyy T 3、5 和 2 4、 1 B 5/25/1 5/15/2 5、如果原问题增加一个变量，则对偶问题就增加一个约束条件，它的可行域要么减少， 要么不变，绝对不会变大。 三、解：此题可看作指派问题求解： 5 6 10 1 2 5 0 1 4 0 0 3 8 10 12 4 6 7 0 2 3 0 1 2 4 4 5 0 0 0 0 0 0 1 0 0 19*0, 1, 1, 1 331221 Zxxx，其余为最优解 四、解：将最大化问题化为极小化问题，并将系数转为正，即令，整理得 1 ii xx )5, 2 , 1( 10 322 122362 2453 2631075min 5 4 3 2 5 4 3 2 1 5 4 3 2 1 5 4 3 2 1 jx xxxx xxxxx xxxxx xxxxxZ j 或 综上，该 0-1 规划无可行解 五、解：按三个变量划分为三个阶段，状态转移方程 第三阶段： 233333 *,max)(sxsxsf 33 0sx 第二阶段： 2 24 1 22 23 222 )(max)(max)(sxsxsxsf 2 2 0sx 2 2 0sx 其中 22 1 2* sx )1( 2 2 xx 第一阶段： 27 8 2 2 14 1 1 2 24 1 111 )2(maxmax)(xxsxsf 2 200 1 x 1 x 其中 3 2 1* x 27 8 3 2 33 1 3 2 223 2 1 * *,1*1*,* Z xxxx最优解 六、解：依题意，首先给出一个可行流 在初始流上增流到不能再增，得到如下结果： 此时已不能再增流，流量 105f ，不能满足市场的需求量。应修改仓库 3 到市场 3 和 4 的容量，分别增流 10 和 5 即能满足需求。 七、解：3、5 正确。 第三套第三套 一、解：将原问题化为标准形得 5, 2 , 1, 0 82 44 2 4max 521 421 321 21 ix xxx xxx xxx xxZ i 4 1 0 0 0 i b iki ab / 1 x 2 x 3 x 4 x 5 x 0 3 x -1 1 1 0 0 2 - 0 1 -4 0 1 0 4 4 4 x 0 1 -2 0 0 1 8 8 5 x j r 4 1 0 0 0 0 3 x 0 -3 1 1 0 6 - 4 1 -4 0 1 0 4 - 1 x 0 0 2 0 -1 1 4 2 5 x j r 0 17 0 -4 0 0 0 0 1 -1/2 3/2 12 3 x 4 1 0 0 -1 2 12 1 x 1 0 1 0 -1/2 1/2 2 2 x j r 0 0 0 9/2 -17/2 由于而对应的 04 r0 4 i a 此线性规划问题无界 二、解 （1）X2的价值系数由-7 变为 3。 01 3 1 023 2 r 最优解发生变化，继续迭代。 2 3 1 0 0 i b iki ab / 1 x 2 x 3 x 4 x 5 x 2 1 1x 1 1 1 0 6 10 6 10/3 0 5 x0 3 1 1 1 j r 0 1 -1 -2 0 2 1 x 3 2 x 1 0 2/3 2/3 -1/3 0 1 1/3 1/3 1/3 8/3 10/3 j r 0 0 -4/3 -2 -1/3-46/3 此时最优解为 3 46 ) 3 10 , 3 8 (),( * 21 * Z xxX TT （2） 11 01 1 B 0 8 3 5 3 11 01 1 bBb 此时不影响解的最优性，只改变解的值及目标函数值 6* )8 , 3(),(* 51 Z xxX TT （3） 最优解不满足新增加的约束条件 22 31 xx 最优解要发生改变 将约束条件改写为 22 631 xxx 加入最优表中继续迭代。 2 -7 1 0 0 0 i b 1 x 2 x 3 x 4 x 5 x 6 x 2 1 x1 1 1 1 0 0 0 3 1 1 1 0 0 -1 -3 -1 0 1 6 10 0 5 x 0 6 x-8 j r 0 -9 -1 -2 0 0 ikj ar / - 9 1/3 2 - - 2 1 x 0 5 x 1 3 x 10/3 22/3 1 2/3 0 2/3 0 1/3 0 8/3 0 2/3 1 4/3 0 1/3 1 1/3 0 -1/3 8/3 j r 0 -26/3 0 -5/3 0 -1/3 -28/3 新的最优解为3 28 * ),()3, 1(* 3 8 3 10 Z xxX TT 三、解：建立运输问题模型并给出初始方案得： 销 产 1 2 4 5 产 3 i u 10 300 13 17 16 200 19 200 0 4 700 1 0 1 15 1 18 18 21 1 24 1 0 200 200 4 2 M 10 700 13 -7 16 -7 0 0 700 4 2 M 15 17 18 0 21 200 0 2 200 2 3 M M 15 700 18 0 0 5 -1 700 3 M M 20 0 23 200 0 0 200 4 4 M M M 15 -8 0 700 700 4 4 M M M 20 -3 0 200 200 4 销 300 700 900 600 1100 3600 j v 10 -4 16 19 -4 检验数有负，重复调整，得如下解： 销 产 1 2 3 4 5 产 i u 10 300 13 0 16 200 19 4 0 200 1 700 0 1 15 5 18 5 21 5 24 9 0 200 200 0 2 M 10 700 13 0 16 4 0 3 700 -3 2 M 15 2 18 2 21 6 0 200 200 0 3 M M 15 700 18 4 0 1 700 -1 3 M M 20 4 23 8 0 200 200 0 4 M M M 15 600 0 100 700 0 4 M M M 20 5 0 200 200 0 销 300 700 900 600 1100 3600 j v 10 13 16 15 0 此时检验数全，为最优解 0 ji r )(327001560015700162001070010300*元Z 分配计划如下：第一个月正常生产 500 件，分别给 1 月 300 件，3 月 200 件。 第二个月正常生产 700 件，供给第二个月 第三个月正常生产 700 件，供给第三个月 第四个月正常生产 600 件，供给第六个月 四、解：设 号码的人入选，第 号码的人不入选，第 i i yi 1 0 10 1 1 1 1 1 3 )185180186187191193(max 98 97 95 54 85 987554 9876543 1 或 i y yy yy yy yy yy yyyyyy yyyyyyZ 五、解：利用匈牙利法求解，增加一行元素 00000 3030203020 1020303040 2030203040 1030604050 0000 1010010 10202030 0101020 020503040 0 0 0 0 0 0 0 0 1001010 10000 0201030 00020 10502040 0 0 0 0 0 0 0 0 0 0 此时方案最优，最少人数 人7010202020*Z 方案为周一上美术课，周三上艺术课，周四上音乐课，周五上文学课。 六、解 七、解： 1、 （1） 2 321 xxx （2） 02 4242 xxxx或 2、运费还可以减少，此方案不是最优方案 3、在多阶段决策过程中，最优决策序列具有这种性质，即不管该序列上某状态以前的 状态和决策如何，余下的决策序列必构成该状态的最优决策序列。 第四套第四套 一、解： （1） 首先将解代入约束条件，满足，说明是可行解 041 200 841 A 0A 线性相关，此解不是基可行解 （2） 选取 作为基变量， 431 ,xxx 1001 220 081 A 036 A 线性无关。 令 0 7652 xxxx ，解出 0, 01, 09 431 xxx 得出一个基可行解 即。 )0 , 0 , 0 , 0 , 1 , 0 , 9(X 二、解：写出原问题的对偶问题得 0 2 1 2 64max 21 21 21 21 21 yy kyy yy yy yyZ 无约束， 由互补松弛定理： 0 11 s yx 得 2, 0 211 yyys 0 33 s yx 得 2, 0 213 kyyys 联立得 k y k k y 1 4 *, 1 26 * 21 而 *,*,12* 21 yyZZ将 代入 12*6*4 21 yy 则 2*, 6*, 3 21 yyk 综上，对偶问题最优解为 3k TT yyY)2 , 6(),(* 21 三、解： （1）表上作业法求解得： 销 产 124 B B 3 B B 5 B 产 i u 10 0 15 50 20 15 20 0 40 35 1 A 50 -10 2 A 20 10 40 15 15 60 30 30 30 15 100 0 3 A 30 15 35 65 40 25 55 15 25 70 150 10 销 25 115 60 30 70 300 j v 20 25 15 30 15 检验数，此方案最优 0 ji r 722517509009002275750450200*Z （2）增加虚拟产地 4 A 销 产 124 B B 3 B B 5 B 产 i u 10 15 15 50 20 30 20 15 40 35 1 A 50 -25 2 A 20 25 40 0 15 60 30 15 30 0 100 0 3 A 30 15 35 65 40 30 55 30 25 65 130 -5 4 A 0 10 M 0 15 0 15 0 5 20 -20 销 25 115 60 30 70 300 j v 20 40 15 30 30 检验数，此方案最优 0 ji r 650016254509002275750500*Z 四、解：用匈牙利法求解 46255132 43365639 51324547 40274135 60100 311157 117415 0203 6010 8124 7311 203 0 0 0 0 0 0 0 0 80120 06122 7109 0001 最优方案为：肖恩 文字处理，伊恩