= Solution
With the new right sides, the dual function is
$$
\theta_{\mathrm{new}}(\lambda,\mu)=\max\{10-\lambda,\ 8-\mu\},\qquad\lambda,\mu\geq0.
$$
Take $\lambda=\mu=t\to\infty$. Then $\theta_{\mathrm{new}}(t,t)=10-t\to-\infty$, so the minimization dual is \b[unbounded below]:
$$
\boxed{\inf\theta_{\mathrm{new}}=-\infty.}
$$
By <weak duality>, any feasible <integer> point with finite objective would have to have objective at most every dual value, which is impossible. Thus \b[the modified <integer> program is infeasible and has no optimal solution]. This is an <infeasibility certificate from an unbounded Lagrangian dual>.
There is also a direct certificate: the assignment equalities force $(a+b)\cdot x=9$, while the new bounds force it to be at most $3+5=8$. Even the modified linear relaxation is infeasible. The earlier $3.5,5.5$ problem also had no <integer> solution, but there its fractional <feasible point> kept the dual value finite.
Back to article page
