0
$\begingroup$

Let a linear programming (LP) in the form:

$\max \ cx$

$s.t. \ Ax\leq b,$

$\ \ \ \ \ \ \ \ x\geq0$

If this program has an optimal finite solution, then if I exchange $b$ to $\bar{b}$, show that the new LP either has an finite optimal solution or is infeasible.

Finally, how can I argue that, regardless of the value of $\bar{b}$ I choose, I will not have an unbounded LP problem?

obs: I dont need a rigorous formal proof, just arguments with a mathematical basis it's ok.

$\endgroup$
5
  • $\begingroup$ Is $b$ a vector or a scalar? If it is a vector, it does not make sense to break into cases $\overline{b} \geq b$ and $\overline{b} < b$, since those are not the only cases. $\endgroup$
    – Michael
    Commented Oct 5, 2016 at 0:21
  • $\begingroup$ Oh, didnt notice. Yea, $b$ is a vector. $\endgroup$
    – user312479
    Commented Oct 5, 2016 at 3:55
  • $\begingroup$ Have you learned about "directions of recession" or "recession cones" for closed convex sets? Or, perhaps you have a theorem about "If a linear program has an infinite solution then there is a direction of recession such that..." $\endgroup$
    – Michael
    Commented Oct 5, 2016 at 16:00
  • $\begingroup$ Hmm, no. But, I can understand this now (used dual theory and gradient of $b$). $\endgroup$
    – user312479
    Commented Oct 6, 2016 at 19:13
  • $\begingroup$ I didn't think of that. Another way is if a linear program MAX: $cx$ ST: $Ax \leq b$, $x \geq 0$ has an infinite optimal solution, there must be vectors $d, v$ such that for all $t \geq 0$ the vector $d + tv$ satisfies all constraints, and $\lim_{t\rightarrow\infty} c(d + tv) =\infty$. [In other words, starting from a feasible point $d$, there must be some "direction of recession" $v$ that we can travel in to improve the solution]. You can reason out basic properties of $v$ and show it is also a direction of recession for a modified problem with constraints $Ax \leq b'$. $\endgroup$
    – Michael
    Commented Oct 8, 2016 at 22:12

1 Answer 1

1
$\begingroup$

Let's write down the dual of the original problem:

$$\min p'b$$

$$p'A \geq c'$$ $$p \geq 0$$

We know that the original problem has a finite solution, hence we can conclude that the feasible region for the dual is non-empty.

Now, suppose we replace $b$ by $\bar{b}$.

Suppose on the contrary that the problem is unbounded, then the dual is infeasible. However, the new dual is

$$\min p'\bar{b}$$

$$p'A \geq c'$$ $$p \geq 0$$

We have earlier found out that the feasible region is instead non-empty, which is a contradiction.

Hence, it cannot be unbounded. The primal either has finite solution or it is not feasible.

$\endgroup$
1
  • $\begingroup$ wow, I see 'the man who has all the answers'. $\endgroup$
    – user312479
    Commented Oct 10, 2016 at 12:09

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .