LP Duality
Estimating LP bounds Given an optimization problem $$ \begin{aligned} \max_{f, s} &\quad 12f + 9s \\ \st &\quad 4f + 2s \leq 4800 \\ &\quad f + s \leq 1750 \\ &\quad 0 \leq f \leq 1000 \\ &\quad 0 \leq s \leq 1500 \\ \end{aligned} $$ Suppose the maximum profit is $p^\star$. How can we bound $p^\star$? The lower bound of $p^\star$ can be found by picking any feasible point (since maximization). For example, $\{f=0, s=0\}$ is feasible. Therefore, $p^\star \geq 12f + 9s = 0$. Since any feasible point yields a lower bound of $p^\star$ and $p^\star$ itself is yielded by an feasible point, then finding the largest lower bound of $p^\star$ is equivalent to solving the LP.
Read note →