两阶段法是求解线性规划问题常用的方法之一,步骤如下:
1. 标准化原始问题:将原始问题转化为标准型,即使得所有的约束和目标函数都是≤或≥或=的形式,并且变量系数都是非负的。
2. 设置人工变量:在标准化的问题中增加人工变量(artificial variables)使目标函数等于0,并在原始问题中增加人工变量的系数为1的约束条件。这样,将原来的目标函数转化为了一个最小化人工变量的问题。
3. 第一阶段求解:解决这个最小化人工变量的问题,即让所有的人工变量的值为0,得到初始解。
4. 检验初始解是否可行:如果初始解中所有变量的取值均满足所有约束条件,则说明初始解是可行的,可直接进入第二阶段求解;否则,需要进行人工变量法的迭代过程。
5. 第二阶段求解:将人工变量移出问题,不再考虑人工变量,直接求解标准问题,即消去第二阶段增加的目标函数和约束条件,得到原始问题的最优解。
6. 检验解的可行性:将所得解代入原始问题的所有约束条件中,检查是否满足所有约束条件。如果满足,则所得解为原始问题的最优解;否则,需要进行对偶检验,确定原始问题的对偶问题,再对对偶问题进行求解。
需要注意的是,两阶段法求解线性规划问题的难点在于受到线性规划基本定理的限制,即没有解或者存在无数个解。在实际应用中,需要根据实际情况进行个性化的调整,以便得出可行的、最优的解决方案。