一种求解阶梯状结构线性规划问题的原始-对偶分解算法

摘要

阶段状线性规划作为一种具有特殊结构的线性规划问题，有着重要的应用背景，我们首先对分解算法的发展过程及其主要算法进行了简单的回顾，然后给出一种求解阶梯状线性规划问题的原始-对偶分解算法，它将多阶段线性规划问题分解为一系列单阶段问题，并通过向前以及向后传递的原始和对偶信息进行协调，用原始极点和对偶极点的凸组合表示其相应的变量，同时从原始和对偶两个方向上逼近原问题，以尽快达到最优。通过www.netlib.org这个网址找到三个算例并根据需要做了修改。虽然问题不是很大，但数值实验仍然可以帮助我们对这个方法有更深的理解。