<s>[INST] Maximize system of linear equations 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$.
 [/INST] 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$.
</s>