True or false questions for LP and the simplex method

Question

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!!

What are the reasonings that lead you to those conclusions? – Siong Thye Goh Jul 14 '19 at 14:38 — Siong Thye Goh, Jul 14 '19 at 14:38
This should explain it. – cookiemonster Jul 14 '19 at 14:44 — cookiemonster, Jul 14 '19 at 14:44

score 1 · Accepted Answer · answered Jul 14 '19 at 14:48

1

$(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?

answered Jul 14 '19 at 14:48

Siong Thye Goh

149,520
20
88
149

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

True or false questions for LP and the simplex method

1 Answers1