Question

运筹学答题

Answer 1

问：运筹学答题

答：请把题目打字发出来我来给你解答

问：有4个工人，要指派他们分别完成4种工作，每人做各种工作所消耗的时间如表1所示，问指派哪个人去完成哪种工作，可使总的消耗时间为最小？表1工人工种ABCD甲15 18 21 24乙19 23 22 18丙26 17 16 19丁19 21 23 17

问：那5.3 的

答：请把题目打字发出来我来给你解答

问：用分枝定界法求解下列问题：max z=x1+x2S.t[x1+9/14.x2≤51/14{-2x+x2≤1/3x1,x2≥0，x1,x2为整数

答：首先，我们要将目标函数和约束条件转化为标准形式：max z = x1 + x2s.t. x1 + 9/14*x2 ≤ 51/14 -2x1 + x2 ≤ 1/3 x1, x2 ≥ 0, x1, x2 为整数然后，我们可以通过分枝定界法来求解该问题。1. 首先，我们将目标函数的最大值设为 M = 正无穷。2. 然后，我们从约束条件中选择一组不等式，将其转化为等式，然后将未知数分为两个部分，即 xj = l 和 xj = u。 在本问题中，我们选择 x1 = l。 当 x1 = l 时，我们可以将约束条件和目标函数分别转化为： x2 ≤ (51/14 - l) / (9/14) x2 ≤ (1/3 + 2l) max z = l + x23. 接下来，我们需要对每个 xj = l 和 xj = u 的情况进行分枝。 在本问题中，我们首先选择 x1 = 0，即 l = 0。 当 l = 0 时，我们可以得到以下两个子问题： 子问题 1：

答：max z = 0 + x2 s.t. x2 ≤ 51/14 子问题 2： max z = 1 + x2 s.t. x2 ≤ 1/34. 对于每个子问题，我们使用线性规划求解器求解，得到子问题的最优解。 对于子问题 1，最优解为 z = 51/14，x1 = 0，x2 = 51/14。 对于子问题 2，最优解为 z = 4/3，x1 = 1，x2 = 1/3。5. 接下来，我们需要对最优解进行限界。 对于子问题 1，由于 z = 51/14 大于当前的 M，因此我们将 M 更新为 z = 51/14。 对于子问题 2，由于 z = 4/3 小于当前的 M，因此我们不需要更新 M。6. 然后，我们再次选择一个 xj = l 或 xj = u 的情况进行分枝，并重复上述步骤，直到不能再分枝为止。 在本问题中，我们选择 x2 = 1，即 u = 1。 当 u = 1 时，我们可以得到以下两个子问题： 子问题 3： max z = 0 + 1 s.t. x1 ≤ 6/7

答：子问题 4： max z = 1 + 1 s.t. -2x1 + 1 ≤ 1/37. 对于子问题 3，最优解为 z = 1，x1 = 6/7，x2 = 1。 对于子问题 4，最优解为 z = 4/3，x1 = 1/3，x2 = 1。8. 通过限界，我们得到 z 的最大值为 51/14。因此，该问题的最优解为 z = 51/14，x1 = 3，x2 = 3/14。