Problem Statement
From (page 10 Chapter 1) [1].
Problem 1.7
Prove or disprove: If Problem 1.7 above is unbounded, then there is a subscript \(k\) such that the Problem 1.5 below is unbounded.
Problem 1.5
Proof
Assume without loss of generality that the objective function coefficients \(c_{j}\) of all decision variables, \(x_{j}\), in Problem 1.7 are non-zero.
We see that Problem 1.5 defines \(n\) sub-problems, one for each decision variable \(x_k\) in Problem 1.7. Now, suppose there is no subscript \(k\) for which the sub-problems are unbounded. This means we can identify constants \(M_{1},\ldots,M_{n}\) which are the maximum objective function values for each sub-problem in Problem 1.5. So, for example, \(M_1\) is the largest value \(x_{1}\) can take while still staying feasible.
Next, let \(I_{c_{j} \gt 0}\) be an indicator function that tells us with a one or a zero whether the coefficient of decision variable \(x_{j}\) in the objective function of Problem 1.7 is strictly positive.
Now we claim that \(M=\sum_{j=1}^{n}c_{j}I_{c_{j} \gt 0}M_{j}\) is the greatest upper bound on the objective function of Problem 1.7.
It is possible that if some objective function coefficient \(c_{l}\) is negative that a more accurate upper bound can be obtained by solving a minimization version of Problem 1.5. Solving this minimization would give us the smallest \(x_{l}\) for which the problem remains feasible. But since \(c_{l} \lt 0\) having \(x_{l} >0\) will only serve to reduce \(\sum_{j=1}^{n}c_{j}x_{j}\).
What this means is that \(M\) is the greatest upper bound on the objective function of Problem 1.7.
However, the existence of a finite upper bound contradicts the unboundedness of Problem 1.7 since for an unbounded problem we can always find a feasible solution such that \(\sum_{j=1}^{n}c_{j}x_{j} \gt M\) for any value of \(M\).