| course |
course_year |
question_number |
tags |
title |
year |
Optimization |
IB |
66 |
|
Paper 3, Section II, H |
2019 |
(a) Suppose that $A \in \mathbb{R}^{m \times n}$ and $b \in \mathbb{R}^{m}$, with $n \geqslant m$. What does it mean for $x \in \mathbb{R}^{n}$ to be a basic feasible solution of the equation $A x=b ?$
Assume that the $m$ rows of $A$ are linearly independent, every set of $m$ columns is linearly independent, and every basic solution has exactly $m$ non-zero entries. Prove that the extreme points of $\mathcal{X}(b)={x \geqslant 0: A x=b}$ are the basic feasible solutions of $A x=b$. [Here, $x \geqslant 0$ means that each of the coordinates of $x$ are at least 0 .]
(b) Use the simplex method to solve the linear program
$$\begin{array}{cl}
\max & 4 x_{1}+3 x_{2}+7 x_{3} \\
\text { s.t. } & x_{1}+3 x_{2}+x_{3} \leqslant 14 \\
& 4 x_{1}+3 x_{2}+2 x_{3} \leqslant 5 \\
& -x_{1}+x_{2}-x_{3} \geqslant-2 \\
& x_{1}, x_{2}, x_{3} \geqslant 0
\end{array}$$