对偶和Benders分解算法

对偶和Benders分解算法"/>

对偶和Benders分解算法

对偶定理

max      cx                                       
s.t.     Ax ≤ b                                       x ≥ 0                                        (uA - c)x ≥ 0                                       

 min       ubs.t.     uA ≥ c u ≥ 0u(Ax - b) ≤ 0

原式是max：x与对偶不等式（uA - c）同号，对偶变量u与原不等式（Ax - b）异号；
原式是min：x与对偶不等式（uA - c）异号，对偶变量u与原不等式（Ax - b）同号；
疑问：当原式中x范围是特定有限区间，u的范围是多少？

benders 分解

对于一个线性规划问题，将之分解成两个问题，一个子问题，一个主问题，主问题包含复杂变量，子问题中将复杂变量看做是常数，那么就剩下简单的线性变量，子问题就是一个可以求解的纯线性规划问题。给一个初始值求解主问题，求得的解带入子问题中验证，如果主问题的解不符合子问题的条件，加一些约束给主问题，如果符合标准，就是最优值，具体例子如下：

示例