0

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.

user312479
  • 473
  • 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. – Michael Oct 05 '16 at 00:21
  • Oh, didnt notice. Yea, $b$ is a vector. – user312479 Oct 05 '16 at 03:55
  • 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..." – Michael Oct 05 '16 at 16:00
  • Hmm, no. But, I can understand this now (used dual theory and gradient of $b$). – user312479 Oct 06 '16 at 19:13
  • 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'$. – Michael Oct 08 '16 at 22:12

1 Answers1

1

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.

Siong Thye Goh
  • 149,520
  • 20
  • 88
  • 149