列生成算法在广义指派问题中的应用示例

题目描述：
考虑一个广义指派问题，某公司有5项任务（T1~T5）需要分配给3台机器（M1~M3）。每台机器的可用工时不同（M1:10小时，M2:12小时，M3:15小时），每项任务在不同机器上的处理时间和成本均不同。目标是在满足机器工时限制的前提下，最小化总成本。具体数据如下：

处理时间矩阵（小时）：

     M1  M2  M3
T1   4   6   5
T2   3   5   4
T3   2   3   2
T4   5   4   3
T5   4   5   6

成本矩阵（元）：

     M1  M2  M3
T1   90  80  85
T2   70  60  65
T3   50  40  45
T4   80  70  75
T5   100 90  95

解题过程：

步骤1：建立主问题模型
定义决策变量 \(x_{ij}\) 表示任务i是否分配给机器j（1-分配，0-不分配）。主问题模型为：

最小化总成本：90x11+80x12+...+95x53
约束条件：
  每项任务必须分配：x11+x12+x13=1（对T1）... x51+x52+x53=1（对T5）
  机器工时限制：4x11+3x21+2x31+5x41+4x51 ≤ 10（M1）
                6x12+5x22+3x32+4x42+5x52 ≤ 12（M2）
                5x13+4x23+2x33+3x43+6x53 ≤ 15（M3）
  xij ∈ {0,1}

步骤2：构造限制主问题（RMP）
初始RMP只包含部分变量（例如每台机器只分配一个任务）。设初始解为：

• M1分配T1和T2（x11=1, x21=1）
• M2分配T3（x32=1）
• M3分配T4（x43=1）
  此时T5未被分配，需要生成新列。

步骤3：求解子问题（定价问题）
对每台机器j，求解以下子问题以寻找检验数为负的列（即可能改进解的变量）：

最小化 reduced_cost = cij - π_i - μ_j*t_ij
其中π_i是任务约束的对偶变量，μ_j是机器约束的对偶变量

假设当前对偶解为π=[30,25,15,20,35]，μ=[-2,-1,-3]（通过求解RMP的线性松弛获得）。

以M1为例计算T5的检验数：
reduced_cost = 100 - 35 - (-2)×4 = 100-35+8=73 >0
说明当前变量不是改进方向，需继续检查其他组合。

步骤4：列生成迭代
通过求解子问题发现，将T5分配给M3（检验数=95-35-(-3)×6=95-35+18=78>0）不是最优。进一步检查发现T2分配给M3的检验数：65-25-(-3)×4=65-25+12=52>0。此时所有检验数非负，当前解已是最优。

步骤5：整数解处理
将RMP的线性松弛解取整，得到最终分配方案：

• M1处理T1和T2（工时4+3=7≤10，成本90+70=160）
• M2处理T3和T4（工时3+4=7≤12，成本40+70=110）
• M3处理T5（工时6≤15，成本95）
  总成本=160+110+95=365元，所有任务均被分配且满足工时约束。

通过5个步骤的列生成过程，我们高效解决了这个广义指派问题，避免了枚举所有5×3=15个变量的计算复杂度。