| course |
course_year |
question_number |
tags |
title |
year |
Optimization |
IB |
59 |
|
Paper 4, Section II, H |
2021 |
(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} .]$