Thereom: (Weak Duality)

For every primal feasible solution $(x_1,...,x_n)$ to the primal problem (P) and every dual feasible solution $(y_1,...,y_n)$ to the dual problem (D), it holds that:

$\sum_{j=1}^n c_jx_j \leq \sum_i^m b_iy_i \tag{1}$

So if I take an arbitrary feasible solution of P and one of D, then (1) holds. So that means, I could check for which feasible dual solution the objective value would be the smallest and thus find an upper bound for the optimal solution for P, right?


Yes, every dual feasible solution provides an upper bound on the primal objective value, and the smallest dual objective value provides the best such bound. The strong duality theorem states that equality is attained.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.