Paper 2, Section I, H

Optimization
Part IB, 2015

Define what it means to say that a set SRnS \subseteq \mathbb{R}^{n} is convex. What is meant by an extreme point of a convex set SS ?

Consider the set SR2S \subseteq \mathbb{R}^{2} given by

S={(x1,x2):x1+4x230,3x1+7x260,x10,x20}S=\left\{\left(x_{1}, x_{2}\right): x_{1}+4 x_{2} \leqslant 30,3 x_{1}+7 x_{2} \leqslant 60, x_{1} \geqslant 0, x_{2} \geqslant 0\right\}

Show that SS is convex, and give the coordinates of all extreme points of SS.

For all possible choices of c1>0c_{1}>0 and c2>0c_{2}>0, find the maximum value of c1x1+c2x2c_{1} x_{1}+c_{2} x_{2} subject to (x1,x2)S\left(x_{1}, x_{2}\right) \in S.