1

I'm reading some notes Linear Programming on linear programming. I'm considering the standard minimum problem. Why is it so obvious that, if $-\textbf{c}\geq \textbf{0}$ and $\textbf{b}\geq \textbf{0}$, then minimum occurs at $\textbf{y}=\textbf{0}$ and $\textbf{s}=-\textbf{c}$ ? I see that, when $\textbf{s}=-\textbf{c}$ then $\textbf{y}=\textbf{0}$ must be true. I'm confused why $\textbf{b}\geq \textbf{0}$ is neccecary. Thank you in advance.

$\begin{array}{c|cccc|c} & s_1 & s_2 & \cdots & s_n & \\ \hline y_1 & a_{11} & a_{12} & \cdots & a_{1n} & b_1 \\ y_2 & a_{21} & a_{22} & \cdots & a_{2n} & b_2 \\ \vdots & \vdots & \vdots & & \vdots & \vdots \\ y_m & a_{m1} & a_{m2} & \cdots & a_{mn} & b_m \\ \hline 1 & -c_1 & -c_2 & \cdots & -c_n & 0 \\ \end{array}$

Don't math.exchange support tabulars? Or what am I doing wrong ? It's se same table as the one on page 20 in the hyperlink.

New_to_this
  • 442

1 Answers1

1

If any term of $\mathbf{b}$ is negative, we might make the corresponding term of $\mathbf{y}$ grow without bound -- hence there is no minimum to $\mathbf{y}^T\mathbf{b}$.

vadim123
  • 82,796
  • And if, $-\textbf{c}\geq \textbf{0}$ then $\textbf{c}\leq \textbf{0}$. This ensures that when $\textbf{y}=\textbf{0}$ the constraint $\textbf{y}^{T}A\geq \textbf{c}^{T}$ are preserved. Right ? – New_to_this Sep 06 '13 at 16:19