填空题（____）装配线；（____）灭火器

正确答案：这是一道考查动态规划算法求解最优汽车装配线的分析题。当问题具有两个特性即最优子结构和重叠子问题时可以考虑用动态规划算法求解问题。用动态规划算法求解具体应用问题具有以下4个步骤。 ①刻画问题的最优子结构描述问题的最优解包含子问题的最优解。对于本试题最短装配时间等于经过装配线0的第n个工位的最短装配时间加上x[0]或者等于经过装配线1的第n个工位的最短装配时间加上x[1]取哪条装配线取决于哪个值更小。而经过某条装配线0/1的第i个工位的最短装配时间又等于经过本条装配线第i-1个工位的最短装配时间或者等于经过另一条装配线第i-1个工位的最短装配时间加上从这个工位到装配线0/1的迁移时间取决于哪个值更小。 ②建立最优子结构的递归关系这是关键的一步。对于本试题可建立如下的递归关系。 由此可得初始化数据时(1)空缺处所填写的内容是f[0][0]=e[0]+a[0][0]和f[1][0]=e[1]+a[1][0]。 (2)空缺处所填写的内容可由该空缺处所在的条件判断框的“真”执行语句框中的内容——“f[0][j-1]+a[0][j]得到启发。而(3)空缺处所在条件判断框的填写内容可由(2)空缺处所在的条件判断框内容得到启发即f[1][j-1]+a[1]刚=f[O][j-1]+t[0][j-1]+a[1][j]或其他等价形式。 ③根据递归关系求最优解的值。由图4-17流程图最后一个条件判断框中信息“f[0][n-1]+x[0]= f[1][n-1]+x[1]?”可知最优解记录在fi中fi=min(f(0n-1)+xOf(1n-1)+x1)即(4)空缺处所填写的内容是最短的装配时间fi=f[O][n-1]+x[0]和获得最短装配时间的下线装配线号li=0(5)空缺处所填写的内容是fi=f[1][n-1]+x[1]和li=1。 ④构造最优解。对于本试题来说只是求出最优解是从哪条装配线装配出来并没有记录最优解。
这是一道考查动态规划算法求解最优汽车装配线的分析题。当问题具有两个特性，即最优子结构和重叠子问题时，可以考虑用动态规划算法求解问题。用动态规划算法求解具体应用问题具有以下4个步骤。 ①刻画问题的最优子结构，描述问题的最优解包含子问题的最优解。对于本试题，最短装配时间等于经过装配线0的第n个工位的最短装配时间加上x[0]，或者等于经过装配线1的第n个工位的最短装配时间加上x[1]，取哪条装配线取决于哪个值更小。而经过某条装配线0/1的第i个工位的最短装配时间又等于经过本条装配线第i-1个工位的最短装配时间，或者等于经过另一条装配线第i-1个工位的最短装配时间加上从这个工位到装配线0/1的迁移时间，取决于哪个值更小。 ②建立最优子结构的递归关系，这是关键的一步。对于本试题，可建立如下的递归关系。 由此可得，初始化数据时，(1)空缺处所填写的内容是f[0][0]=e[0]+a[0][0]和f[1][0]=e[1]+a[1][0]。 (2)空缺处所填写的内容可由该空缺处所在的条件判断框的“真”执行语句框中的内容——“f[0][j-1]+a[0][j]得到启发。而(3)空缺处所在条件判断框的填写内容可由(2)空缺处所在的条件判断框内容得到启发，即f[1][j-1]+a[1]刚=f[O][j-1]+t[0][j-1]+a[1][j]或其他等价形式。 ③根据递归关系求最优解的值。由图4-17流程图最后一个条件判断框中信息“f[0][n-1]+x[0]= f[1][n-1]+x[1]?”可知，最优解记录在fi中，fi=min(f(0,n-1)+xO，f(1,n-1)+x1)，即(4)空缺处所填写的内容是最短的装配时间fi=f[O][n-1]+x[0]和获得最短装配时间的下线装配线号li=0，(5)空缺处所填写的内容是fi=f[1][n-1]+x[1]和li=1。 ④构造最优解。对于本试题来说，只是求出最优解是从哪条装配线装配出来，并没有记录最优解。

答案：C

解析：

正确答案：B
要点解析：由题干关键信息“这两种设备均需要逐次按序经过两条装配线进行装配”和“第一装配线和第二装配线同时接通电源，且连续工作”可知，甲(或乙)设备需要先经过多；一装配线进行装配之后，再进入第二装配线进行装配。为了缩短总工时，应适当安排甲、乙两种设备的装配顺序，以缩短第二装配线最后的加工时间(第一装配线完工后还需要用第二装配线的装配时间)，并缩短第一装配线最先的加工时问(第二装配线启动前需要等待的时间)。因此应采取如：原则来安排各设备的装配顺序：在给定的工时表中找出最小值，如果它是第二装配线时问，则该设备应最后加工；如果它是第一装配线时间，则该设备应最先加工。除去该设备后，再按此原则继续进行安排。在表7．2中，最小台时为1小时，这是乙设备所用的第二装配线装配时间，因此有一台乙设备应放在最后加工；表7．2中除去1小时之后，最小台时为2小时，这是甲设备所需的第一装配线装配时间，因此有一台甲设备应最先3wn-。设x，、x，分别表示每周甲、乙两种主要设备的产量，则可得到表7-9所示的求解过程。