(a) Consider the linear program

$$\begin{aligned} P: \quad \text { maximise over } x \geqslant 0, & c^{T} x \\ \text { subject to } & A x=b \end{aligned}$$

where $A \in \mathbb{R}^{m \times n}, c \in \mathbb{R}^{n}$ and $b \in \mathbb{R}^{m}$. What is meant by a basic feasible solution?

(b) Prove that if $P$ has a finite maximum, then there exists a solution that is a basic feasible solution.

(c) Now consider the optimization problem

$$Q: \quad \text { maximise over } x \geqslant 0, \quad \frac{c^{T} x}{d^{T} x}$$

subject to $A x=b$,

$$d^{T} x>0,$$

where matrix $A$ and vectors $c, b$ are as in the problem $P$, and $d \in \mathbb{R}^{n}$. Suppose there exists a solution $x^{*}$ to $Q$. Further consider the linear program

$$\begin{aligned} R: \quad \text { maximise over } y \geqslant 0, t \geqslant 0, & c^{T} y \\ & A y=b t \\ & d^{T} y=1 \end{aligned}$$

(i) Suppose $d_{i}>0$ for all $i=1, \ldots, n$. Show that the maximum of $R$ is finite and at least as large as that of $Q$.

(ii) Suppose, in addition to the condition in part (i), that the entries of $A$ are strictly positive. Show that the maximum of $R$ is equal to that of $Q$.

(iii) Let $\mathcal{B}$ be the set of basic feasible solutions of the linear program $P$. Assuming the conditions in parts (i) and (ii) above, show that

$$\frac{c^{T} x^{*}}{d^{T} x^{*}}=\max _{x \in \mathcal{B}} \frac{c^{T} x}{d^{T} x}$$

[Hint: Argue that if $(y, t)$ is in the set $\mathcal{A}$ of basic feasible solutions to $R$, then $y / t \in \mathcal{B} .]$