15.053期中考试 2001年3月12日，星期二 (闭卷考试) 1.回答试卷中的所有问题。 2.计划好你的时间。若一个问题（或者问题的部分）花费时间太长，你可能会做下一题目。 3.若你认为问题有些不明确，请指出你做的假设。（要使你的假设有道理） 4.本试卷总分105分
15.053 .期中考试 2001 年 3 月 12 日，星期二 （闭卷考试） 1. 回答试卷中的所有问题。 2. 计划好你的时间。若一个问题（或者问题的部分）花费时间太长，你可能会做下一题目。 3. 若你认为问题有些不明确，请指出你做的假设。（要使你的假设有道理） 4. 本试卷总分 105 分
1.(60分，每部分5分) Z XI X2 X3 X4 X5 X6 右端项(RHS) -1 0 W 0 0 W2 3 (0) 0 0 W 1 0 1 (1) 0 0 W4 0 1 4 (2) 0 Ws 0 W (3) 上面的问题是最大化问题。对于a到g部分，我们要求你在下面答案中给出w1,w2,w6的条 件。忽略所有标记为*的值，即使这些值都未知。若不相关，没有必要给出未知量的解。例 如，对于a部分，没有必要给出w3的值。 a.当未知量的值满足什么条件时，当前基本解是可行解？ b.当未知量的值满足什么条件时，当前基本解是退化可行解？ ℃.假定当前基是可行基，基本解是什么？给出所有变量以及目标函数的值。如果需要，用 w6表示解以及目标函数值。 d.当未知系数满足什么条件时，当前解是最优解？（假定解可行） ©.假设解是可行的，变量x2将下一个迭代入基。在什么条件下出现无界解？ ￡假定解不是最优，变量2将下一个迭代入基。当未知系数集合满足什么条件时，X3将会 迭代出基。 g。假定当前基本可行解是最优解且非退化。当满足什么条件时存在多个最优解？
１．（60 分，每部分 5 分） z x1 x2 x3 x4 x5 x6 右端项（RHS） -1 0 w1 0 0 w2 * 3 (0) 0 0 w3 1 0 * * 7 (1) 0 0 w4 0 1 * * 4 (2) 0 1 w5 0 0 * * w6 (3) 上面的问题是最大化问题。对于 a 到 g 部分，我们要求你在下面答案中给出 w1,w2,…w6 的条 件。忽略所有标记为*的值，即使这些值都未知。若不相关，没有必要给出未知量的解。例 如，对于 a 部分，没有必要给出 w3 的值。 a. 当未知量的值满足什么条件时，当前基本解是可行解？ b. 当未知量的值满足什么条件时，当前基本解是退化可行解？ c. 假定当前基是可行基，基本解是什么？给出所有变量以及目标函数的值。如果需要，用 w6 表示解以及目标函数值。 d. 当未知系数满足什么条件时，当前解是最优解？（假定解可行） e. 假设解是可行的，变量 x2 将下一个迭代入基。在什么条件下出现无界解？ f. 假定解不是最优，变量 x2 将下一个迭代入基。当未知系数集合满足什么条件时，x3将会 迭代出基。 g. 假定当前基本可行解是最优解且非退化。当满足什么条件时存在多个最优解？
对于h,,j,k,I部分，假定上面给出的初始表不是最优的。经过几轮迭代，得到最优表： XI X2 七 X4 X5 专 右端项(RHS) 1 0 0 3 0 0 -18 (0) 0 0 1 1/4 -1/2 -1 0 1 (1) 0 a 1/4 2 0 1 2 0 0 0 0 0 7 (3) h.约束(2)的影子价格多大？ 1.假定约束(2)的右端变成4+△，使影子价格有效的△的上界与下界是什么？ j.能够从表中得到w=-w2的结论么？（注意最优表中第2列与第5列紧密相关）若是这样， 请给出解释：否则，也请给出解释。 k.假定w1变为w+△，若要该基依然最优，△应满足什么条件？ I.2的检验数为0。用这个事实写一个含有w1、w3、w4和w5的线性方程。 2.(20分，每部分5分) 考虑作业中的邮局工作人员问题，只是目标是使工作总人数最少，并且周1的需求为16。 邮局工作人员安排问题。当地邮局中，工作人员要连续工作5天，接下来2天放假。 重复执行安排。这样每人每周只能在固定的连续两天休假（例如周日、周一）。工作人员的 需求如下表。工作人员数量必须满足或者超出每天的需求。数字表示每天工作人员的总数量。 目标是使工作总人数最少。 Day Mon Tues. Wed. Thurs. F11 Sat. Sun. Demand 16 13 15 19 14 16 11
对于 h, i, j, k, l 部分，假定上面给出的初始表不是最优的。经过几轮迭代，得到最优表： z x1 x2 x3 x4 x5 x6 右端项（RHS） -1 0 0 -2 -3 0 0 -18 (0) 0 0 1 1/4 -1/2 -1 0 1 (1) 0 0 0 1/4 2 0 1 3 (2) 0 1 0 0 1 0 0 7 (3) h. 约束（2）的影子价格多大？ i. 假定约束（2）的右端变成 4+Δ，使影子价格有效的Δ的上界与下界是什么？ j. 能够从表中得到 w1= -w2的结论么?（注意最优表中第 2 列与第 5 列紧密相关）若是这样， 请给出解释；否则，也请给出解释。 k. 假定 w1 变为 w1+Δ，若要该基依然最优，Δ应满足什么条件？ l. x2 的检验数为 0。用这个事实写一个含有 w1、w3 、w4 和 w5的线性方程。 ２．（20 分，每部分 5 分） 考虑作业中的邮局工作人员问题，只是目标是使工作总人数最少，并且周 1 的需求为 16。 邮局工作人员安排问题。当地邮局中，工作人员要连续工作 5 天，接下来 2 天放假。 重复执行安排。这样每人每周只能在固定的连续两天休假（例如周日、周一）。工作人员的 需求如下表。工作人员数量必须满足或者超出每天的需求。数字表示每天工作人员的总数量。 目标是使工作总人数最少
这是Excl的部分输出结果，因此，从上周一班（即周一到周五工作）的人数是1。最优解 中工人总数是22。 班次 最后值 检验数 目标函数系数 允许增量 允许减量 周一 0 1 1/2 0 周二 6 0 1 0 0 周三 0 0 1 1E+30 0 周四 7 W 1 1/2 0 周五 0 1/3 1 1E+30 1/3 周六 3 0 1 0 1 周日 0 1 0 1/3 需求 最后值 影子价格 约束右端项 允许增量 允许减量 周一 16 1/3 16 9 3 周二 15 0 13 2 1E+30 周三 15 1/3 15 101/2 2 周四 19 1/3 19 11/2 5 周五 14 0 14 4 1 周六 16 W2 16 11/2 6 周日 15 0 11 4 1E+30 a. 假定管理层有意将周五的服务需求从14变为17。需要多少员工？（若表中的信息不够， 请说明。) b.假定管理层有意将周五的服务需求从14变为20。需要多少员工？（若表中的信息不够， 请说明。) ℃.周三班次的检验数，即当前列为w1的应为多大？（若表中的信息不够，请说明。） d.假定周五班次至少要雇佣1个员工。（应该写为F$>=1)假定允许员工数量为小数，而 且当右端项至少增加1时，约束S>=0的影子价格依然有效，员工总人数应该多少？
这是 Excel 的部分输出结果，因此，从上周一班（即周一到周五工作）的人数是１。最优解 中工人总数是 22。 班次 最后值 检验数 目标函数系数 允许增量 允许减量 周一 １ ０ 1 1/2 0 周二 ６ ０ 1 0 0 周三 ０ ０ 1 1E+30 0 周四 ７ w1 1 1/2 0 周五 ０ 1/3 1 1E+30 1/3 周六 ３ 0 1 0 1 周日 ５ 0 1 0 1/3 需求 最后值 影子价格 约束右端项 允许增量 允许减量 周一 １６ 1/3 １６ ９ 3 周二 １５ 0 １３ ２ 1E+30 周三 １５ 1/3 １５ 10 1/2 2 周四 １９ 1/3 １９ 1 1/2 5 周五 １４ 0 １４ 4 1 周六 １６ w2 １６ 1 1/2 6 周日 １５ 0 １１ 4 1E+30 a. 假定管理层有意将周五的服务需求从 14 变为 17。需要多少员工？（若表中的信息不够， 请说明。） b. 假定管理层有意将周五的服务需求从 14 变为 20。需要多少员工？（若表中的信息不够， 请说明。） c. 周三班次的检验数，即当前列为 w1 的应为多大？（若表中的信息不够，请说明。） d. 假定周五班次至少要雇佣１个员工。（应该写为 FS>=1）假定允许员工数量为小数，而 且当右端项至少增加１时，约束 FS>=０的影子价格依然有效，员工总人数应该多少？
对于问题3,4,5可以回答“对”或者“错”。简单证明问题4和5的答案，问题3不需 要证明。每个判断对错题为5分。 3.当从一个基本可行解开始执行单纯形算法时，右端项可能会是负数。如果这样，那么这 表明问题无可行解。 对于判断问题4和5的对错，考虑下面的二维线性规划问题。 Min cX1+c2X2 S.t.ax1+a122=0,X2>=0. 4.若线性规划问题有可行解，那么该线性规划问题有最优解。 5.若线性规划问题只有一个最优解，那么最优解一定在可行域的拐点。 简答问题。每题5分。 6.当没有退化基时，单纯形算法有什么性质？ 7,设用第一阶段方法建立了一个线性规划问题，并且原线性规划问题有可行解。那么第一 阶段线性规划问题的最优值是多少？（如果回答该问题的信息不够充分，请说出来。）
对于问题３，４，５可以回答“对”或者“错”。简单证明问题４和５的答案，问题３不需 要证明。每个判断对错题为５分。 ３．当从一个基本可行解开始执行单纯形算法时，右端项可能会是负数。如果这样，那么这 表明问题无可行解。 对于判断问题４和５的对错，考虑下面的二维线性规划问题。 Min c1x1+c2x2 S.t. a11x1+a12x2=0，x2>=0。 ４．若线性规划问题有可行解，那么该线性规划问题有最优解。 ５．若线性规划问题只有一个最优解，那么最优解一定在可行域的拐点。 简答问题。每题５分。 ６．当没有退化基时，单纯形算法有什么性质？ ７．设用第一阶段方法建立了一个线性规划问题，并且原线性规划问题有可行解。那么第一 阶段线性规划问题的最优值是多少？（如果回答该问题的信息不够充分，请说出来。）