Maximize system of linear equations

Question

Suppose you have the system

$$ \begin{bmatrix} 4 & 3\\ 1 & 7\\ 5 & 9\\ 2 & 4\\ \end{bmatrix} \begin{bmatrix} x\\y\end{bmatrix}=\begin{bmatrix}b_1\\b_2\\b_3\\b_4\end{bmatrix} $$

How could one find scalars $x$ and $y$ such that $b_1+b_2+b_3+b_4$ is maximized? I can see the math behind it as I just took Theory of Linear Algebra, but am stuck on the question.

EDIT: it must be that $0\leq x\leq 1$, $0\leq y\leq 1$, and $x+y=1$.

Answer 1

\begin{align} 4x+3y&=b_1\\ x+7y&=b_2\\ 5x+9y&=b_3\\ 2x+4y&=b_4 \end{align}

Since the coefficients of these systems are all positive and there are no restriction on $b_i$, we can set $x$ and $y$ to be as large or small as we want and $b_1+b_2+b_3+b_4\in (-\infty,\infty)$

This would of course be another question if there were positive and negative coefficients in both $x$ and $y$

Answer 2

$4x+3y=b_1$
$x+7y=b_2$
$5x+9y=b_3$
$2x+4y=b_4$
Add them up we can get $12x+23y=b_1+b_2+b_3+b_4=12(x+y)+11y$
Since $x+y=1$, $b_1+b_2+b_3+b_4=12+11y$
In order to maximize the sum, y has to be as large as it can be, thus $y=1,x=0$

Answer 3

First note $$ b_1 + b_2 + b_3 + b_4 = (4 + 1 + 5 + 2) x + (3 + 7 + 9 + 4) = 12 x + 23 y $$ then we can formulate it as linear program $$ \begin{array}{rr} \max & c^\top u \\ \text{w.r.t.} & A u = b \\ & B u \le d \\ & u \ge 0 \end{array} $$ for cost vector $c = (12, 23)^\top$, vector of unknowns $u = (x, y)^\top$ and constraints $$ A = \begin{pmatrix} 1 & 1 \end{pmatrix} \quad b = \begin{pmatrix} 1 \end{pmatrix} \\ B = \begin{pmatrix} 1 & 0 \\ 0 & 1 \end{pmatrix} \quad d = \begin{pmatrix} 1 \\ 1 \end{pmatrix} $$ As a problem with only $2$ unknowns, it can be solved graphically:

(Large version)

The blue lines and half spaces show the constraints $u \ge 0$ and $B u \le d$. The red line is the constraint $A u = b$. The yellow lines show the cost isolines, the lowest one is $c = 0$, in the middle $c = 10$ and above $c = 20$.

The set of feasible solutions $u$ consists of the red line clamped to the box $[0,1]^2$.

The maximum is determined by the highest possible cost isoline, thus $12 x + 23 y = c$ which intersects the point $(0, 1)^\top$, thus $12 \cdot 0 + 23 \cdot 1 = 23 = c$.

This gives the maximal solution $u = (0, 1)^\top$ with $c^\top u = 23$.