计算题

某项任务的各项工序与所需时间以及它们之间的相互关系如下表所示。请根据此表画网络图，并确定关键线路。

问答题某医院6名检验师担当4项检验项目需用的时间矩阵如下，问应如何指派4名检验师去担当这4项检验任务，使总检验时间最少？

问答题学生小强、小明、小林组成了一个课程竞赛代表队，他们各门课的成绩如下。竞赛同时进行，每人只能参加一项。问如何参赛才能使他们的总分最高？

问答题用匈牙利法求解下列指派问题：

问答题某城市急救中心考虑为6个区设点配置救护车，6个区中均可设点。从成本和服务社会两方面着想，急救中心希望设置的点尽量少，但必须满足在任何地区有呼救，救护车都能在15分钟内赶到。各区之间救护车的行驶时间见下表（单位：分钟）。请帮助急救中心制定一个设点最少的计划。

问答题一个旅行者要在其背包里装一些最有用的旅行物品。背包容积为a，携带物品的总重量最多为b。现有物品m种，第i件物品的体积为ai、重量为bi（i=1，2，…，m）。为了比较物品的有用程度，假设第i件物品的价值为ci（i=1，2，…，m）。问旅行者应携带哪几件物品，才能使携带物品的总价值最大（给出数学模型）？

问答题用隐枚举法求解下列0-1规划：

问答题用分枝定界法求解下列整数规划问题：

判断题指派问题成本矩阵的每个元素乘上同一常数k，将不影响最优指派方案。

判断题用分枝定界法求解一个极大化的整数规划问题，当得到多于一个可行解时，通常可任取其中一个作为下界值，经比较后确定是否再进行分枝。

判断题用分枝定界法求解一个极大化的整数规划问题时，任何一个可行解的目标函数值是该问题目标函数值的一个下界。

判断题整数规划问题解的目标函数值一般优于其相应的松弛问题解的目标函数值。

问答题南方飞机制造公司在制造过程的最后一步是生产喷气发动机并把它们安装到已经完成的飞机框架之中去。公司根据订单为未来4个月喷气发动机的生产制定计划。根据订单要求，1至4月要安装的发动机数量分别是10台、15台、25台和20台。而在此期间，根据其他产品制造、保养以及维修工作安排的不同，这种发动机的生产能力及生产成本也有所不同（见表）。此外，如果当月生产的发动机不在当月安装，其储存成本为每台30万元 月。 生产管理人员需要制订出一个每月生产多少发动机的计划，使制造和存储的总成本达到最小。

问答题大洋发动机厂按合同规定需于每个季度末分别完成10、15、25、20台同一规格发动机。已知该厂各季度生产能力及生产每台发动机成本如下表所示。如果生产出来的发动机当季不交货，每台每积压一个季度需储存、维护费用0.15万元。要求在完成合同的条件下，制订使该厂全年生产、存贮和维护费用为最小的决策方案。

问答题格林公司有甲、乙、丙3个分厂生产同一种产品，产量分别为200吨、400吨和300吨，供应Ⅰ、Ⅱ、Ⅲ、Ⅳ4个地区的需要，各地区的需要量分别为300吨、250吨、350吨和200吨。由于原料、工艺、技术的差别，各厂每千克产品的成本分别为1.3元、1.4元、1.5元。又由于行情不同，各地区销售价分别为每千克2.0、2.2、1.9、2.1元。已知从各分厂运往各销售地区的运价如下表所示： 由于产品供不应求，因此各地的需求不可能完全充分满足，因此要求第Ⅰ和第Ⅱ销地至少供应150吨；第Ⅳ销地必须全部满足；请确定一个运输方案使该公司获利最多。

问答题某药品公司在3个不同的地区分别设有药厂，生产同一种药品，其产量分别为300箱、400箱和500箱。该药厂需要在4个地区供应该种药品，这4个地区该种药品的需求量均为300箱。3个药厂到4个销地的单位运价如下表所示： a.应如何安排运输方案，使得总运费最小？ b.如果药厂2的产量从400箱提高到了600箱，那么应如何安排运输方案，使得总运费为最小？ c.如果销地甲的需求从300箱提高到450箱，而其他情况与a相同，那么该如何安排运输方案，使得运费为最小？