当前位置：问答库＞考研试题

一、计算题

1． 某公司初步选定6个人去完成4项任务，由于个人和技术专长的不同，他们完成4项任务所获得的收益 如表所示，且规定每个人只能完成一项任务，一项任务只能由一个人来完成，具体完成任务的收益如表 所示，求使总收益最大的指派方案

表

【答案】先将该问题的最大利益改为最小化指派问题，找出最大元素13减去每一个元素，得到最小化指派问题， 但还是一个非标准形式的指派问题，再添加两个虚拟人物，则改为的指派问题矩阵为:

对C’加圈，得到，

对C 进行打钩，能覆盖得到6个独立元素，得到，

得到最优方案:第一个人和第二个人都不做任务，第三个人做第二项任务; 第四个人做第三项任务; 第五个人做第一项任务; 第六个人做第四项任务，能获得最大利益，为43.

2． 出从1节点到U 节点的最短路径

图

【答案】Dijkstra 算法，即标号法求解

（l ）对节点l 进行P 标号，即P （1）=0，其余点进行T 标号，即T （j ）=+∞ 因为

而

（2）修改节点3、5的T 标号

因为

（3）修改节点6，8的标号

因为

（4）修改节点9的标号

因为

（5）修改节点7的标号

故将节点2进行P 标号，

故将点5进行P 标号，

故将点6进行P 标号，

故将点4进行P 标号，

因为

（6）修改节点9、11的标号

因为

（7）修改节点12的标号

故将点8进行P 标号，

故将点9进行P 标号，

因为

顶节点12已经进行了P 标号，且

故将点12进行P 标号，

于是得到节点1到节点12的最短路程为18，最

短路线为1→2→5→8→11→12

3． 某企业用甲、乙、丙三种原料生产A 、B 、C 、D 四种产品，每种产品消耗原料定额以及三种原料的数量 如表所示.

表

求使总利润最大的生产计划。现求得最优单纯形表为:

表

请解答下列问题:

（1）写出此问题的线性规划模型及其对偶问题，并写出此问题的最优解、最优基、最优基的逆和对偶问题的解;

（2）解释最优生产计划中有的产品不安排生产的原因; （3）对产品B 的利润进行灵敏度分析;

（4）若原料甲增加420吨，影子价格是否变化，求原料甲增加后的最优解和各原料的影子价格。

【答案】（l ）设产品A 、B 、C 、D 分别生产x l ，x 2，x 3，x 4万件，则可建立如下线性规划模型: