0
$\begingroup$

True or false?

(a) Deleting a constraint leaves the feasible region larger.

(b) Adding a constraint leaves the feasible region either unchanged or smaller.

(c) An LP cannot have an unbounded objective function value.

Here are my answers:

(a) True because when I graphed a random problem, it looked like the feasible region got bigger.

(b) True -Same as (a) but saw it get smaller.

(c) True because it can have an optimal objective function value but probably not an unbounded objective function value.

But I don't understand how all three are true. Help is very much appreciated!!

$\endgroup$
  • $\begingroup$ What are the reasonings that lead you to those conclusions? $\endgroup$ – Siong Thye Goh Jul 14 '19 at 14:38
  • $\begingroup$ This should explain it. $\endgroup$ – cookiemonster Jul 14 '19 at 14:44
1
$\begingroup$

$(A)$: It can also remains the same. For example for a $2$-dimensional problem, if $0 \le x\le 1$ and $0 \le y \le 1$ and $x+y \le 2$. Removing the last constraints doesn't change the feasible set.

$(B)$: Let $D$ be the initial feasible set and $D'$ be the new feasible set with more constraitns, then we have $D' \subseteq D$ since any element of $D'$ would satisfy the conditions to be in $D$.

$(C)$: Consider $\max x$, subject to $y = 0$. Is it bounded?

$\endgroup$
  • $\begingroup$ So (A) is false, (b) is True and (C) is false? just want to confirm $\endgroup$ – cookiemonster Jul 14 '19 at 14:53
  • $\begingroup$ seems to be from the reasoning. $\endgroup$ – Siong Thye Goh Jul 14 '19 at 14:55
  • $\begingroup$ Thank you very much. I understand now. $\endgroup$ – cookiemonster Jul 14 '19 at 15:34

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.