0

I'm having problems with the following task:

Let $A = \begin{pmatrix}1 & 1\\\ 1/2 & 1\\\ -1 & 1 \end{pmatrix}$ , $b = \begin{pmatrix}4 \\\ 2\\\ -1\end{pmatrix}$ .

Find all possible $ c \in \mathbb{R}^2$ sucht that $(2,1)^T$ is a solution for the following problem: $$\min_{ x \in \mathbb{R}^2} c^Tx \text{ with } Ax \le b, x \ge 0.$$ Justify your answer with a graphic.

I don't know how to get started with this problem , we've thus far only learned how to graphically solve linear optimization problems.

I'd be thankful for any help.

Community
  • 1
3nondatur
  • 4,178
  • Start by drawing the feasible region. Suppose you know $c$ -- how would you solve it? Can you "doctor" the $c$ so the solution comes out to $(2,1)^T$? – gt6989b Mar 08 '18 at 23:43

1 Answers1

1

The constraint $Ax \leqslant b$ specifies a convex area in $\mathbb{R}^2$, i.e.$$ \{(x_1, x_2) \in \mathbb{R}^2 \mid x_1 + x_2 \leqslant 4,\ \frac{1}{2}x_1 + x_2 \leqslant 2,\ -x_1 + x_2 \leqslant -1\}, $$ and $(2, 1)$ is a vertex of this area. Suppose $c = (c_1, c_2)$, then minimizing $c^T x$ is equivalent to minimizing the intercept of line $c_1x_1 + c_2x_2 = m$ on the $x_2$-axis if $c_2 > 0$, or maximizing the intercept if $c_2 < 0$. This can be done graphically.

Ѕᴀᴀᴅ
  • 34,263