1、管理运筹学作业 1第 1 题 1939 年前苏联数学家 在生产组织与计划中的数学方法一书中，首次提出了线性规划问题，成为最早研究这方面的问题学者。 您的答案：康托洛维奇 题目分数： 2 此题得分： 2 2第 2 题 根据凸集的定义判断下列图形中是凸集的图形为（ ）。 您的答案： D,E 题目分数： 4 此题得分： 4 3第 3 题 判断下列线性规划问题解的情况（ ）： 您的答案：多重解 题目分数： 4 此题得分： 4 4第 10 题 1947 年，美国学者 （ G.B.Dantzig）提出了线性规划问题的一般解法： ，为线性规划的理论发展奠定了基础。 您的答案：丹捷格，单纯形算法 题目分数：
2、6 此题得分： 6 5第 13 题 线性规划问题由 、 、 三部分组成。 您的答案：目标函数 、 约束条件 、 变量非负 题目分数： 2 此题得分： 2 6第 15 题 判断下列线性规划问题解的情况（ ）： 您的答案：无界解 题目分数： 4 此题得分： 4 7第 7 题 求解 0-1整数规划： Max Z 3x1+7x2-x3 您的答案： 解：先考虑可能的解的组合，共 23 8个，列于表 5.3 中。 先分析第一个解（ 0， 0， 0），经检查为可行解，而其目标函数值为 0，则考察其它的解，只有其目标函数值满足 （ 5.6）时，才检查其是否可行，否则不予检查。我们把条件 (5.6)称为过滤条件
3、。 再分析解（ 0， 0， 1），由于其目标函数值为 -1，不满足过滤条件（ 5.6），故不予检查。 分析解（ 0， 1， 0），其目标函数值为 7，故要检查，经检查不满足约束条件，故过滤条件不予修改。 类似于上述分析，直到将所有的解均检查完毕，最后得到结论，最优解为（ 1， 1， 1），最优目标函数值为 9。 我们将上述求解方法称为隐枚举法。 ？ ？ 题目分数： 8 此题得分： 8 8第 12 题 表 1 给出了一个运输问题的产销平衡表和单位运价表，试用“伏格尔法（ Vogel法）”直接给出近似最优解。 您的答案： 解：第一步：分别计算表中各行、各列的最小运费和次最小运费的差额，并填写该表的
4、最右列和最下行，见表 3。？ ？第二步：从行或列差额中选出最大者，选择它所在行或列中的最小元素。在表 3中，第 3列是最大差额所在列，第三列中的最小元素为 1，可确定产地 2 的产品先供应给销地 3，得表 4。同时将运价表中第 3 列数字划去，如表 5所示。第三步，对表 5 中为划去的元素再分别计算出各行、各列的最小运费和次最小运费的差额，并填入该表的最右列和最下列，重复第一、二步，直到给出初始解为止。用此法给出表的初始解如表 6所示。题目分数： 10 此题得分： 10 9第 14 题 某公司下设生产同类产品的加工厂 A1、 A2、 A3，生产的产品由 4 个销售点 B1、B2、 B3、 B4
5、 出售，各工厂的生产量、各销售点的销量以及各工厂到各销售点的单位运价示于下表中。试用“西北角法”确定其初始基可行解（初始调运方案）。 您的答案： 解：西北角法（又称左上角法）是优先从运价表的西北角（或左上角）的变量赋值。当行或列分配完毕后，再在表中余下部分的西北角（或左上角）赋值，依此类推，直到右下角元素分配完毕。当出现同时分配完一行和一列时，在相应的行或列上选一个变量作为基变量，以保证最后的基变量等于 m+n-1。至此，令空格处的非零变量为零，得到了该运输问题的一个初始调运方案： X11=8、 X12=8、 X22=6、 X23=4、X33=8、 X34=14，其余 Xjy=0。即由 A1运
6、 8个单位物品至 B1，运 8个单位物品至 B2；由 A2 运 6 个单位物品至 B2， 4个单位物品至 B3；由 A3 运 8 个单位物品至 B3， 14个单位物品至 B4。总运输费用Z=8*4+8*12+6*10+4*3+8*11+14*6=372 题目分数： 10 此题得分： 10 10第 8题 证明标准形的线性规划问题 您的答案： 解：题目分数： 10 此题得分： 10 11第 11题 证明线性规划问题的可行解集 S（若非空）是凸集。 您的答案： 证明：按凸集定义，要证明可行解集 S中任意两点 x(1)和 x(2)连线上的一切点 ？ X=ax(1)+（ 1-a） x(2)？ (0 a
7、1)？ ？ 仍属于 S，亦即要证 x仍为可行解。 ？ 一方面，因为 x(1) 0， x(2) 0，且 0 a 1，所以，显然有 x 0，即 x 满足非负条件。 ？ 另一方面，由于 Ax(1)=b， Ax(2)=b，故有 ？ Ax=A【 ax(1)+（ 1-a） x(2)】 =aAx(1)+（ 1-a） Ax(2)=ab+（ 1-a） b=b，则 x 满足约束方程。 ？ 综上， x 仍为可行解，证明完毕。 题目分数： 10 此题得分： 10 12第 4题 运输问题的典型数学语言表述为： 您的答案： 解：题目分数： 6 此题得分： 6 批注： 13第 5题 一个由多个产地供应多个销地的单品种物品运
8、输问题。可列出该问题的运输表，如下表所示。表中变量 xij（ i 1， 2， m； j 1， 2， n）为由产地 Ai运往销地 Bj 的物品数量， Cij 为 Ai 到 Bj 的单位运价。试根据下表写出产销平衡运输问题的数学模型： 您的答案： 解：题目分数： 6 此题得分： 6 批注： 14第 6题 简述指派问题的标准形式及其数学模型。 您的答案： 解：指派问题的标准形式（以人和事为例） n个人做 n 件事，并且要求每人必须而且只做一件事。设第 i人做第 j件事的费用为 Cij（ i,j 1， 2?， n)，使总费用最少。因此，我们可得指派问题的系数矩阵： 为了建立标准指派问题的数学模型，我们引入 n2 个 0 1 变量。并且得到该问题的数学模型。
