I'm aware that for any given maximize/minimize LP problem, if its dual is unbounded then the primary is infeasible and vice versa. But what if there is no maximize/minimize objective function? For instance, if the problem were simply as follows:

$$x_1+x_2+x_3+x_4\geq 12 \\ 2x_1-6x_2-3x_3+2x_4\geq 4 \\ -x_1+x_2-x_3-x_4 \geq 1 \\ x_{1,2,3,4} \geq 0$$

And we were supposed to either provide A feasible solution, OR show that that it is infeasible?

I suspect one might have to first turn the above into equality constraints by introducing surplus variables, but then what? I think intuitively that there is probably no feasible solution here, but how might one prove it?

  • $\begingroup$ Add a 'dummy' objective function max 0x1 + 0x2 + 0x3 + 0x4 $\endgroup$ – Auberon Apr 6 '16 at 19:55

Your Answer

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

Browse other questions tagged or ask your own question.