I am completely stuck on the following question:
Consider the LP program $Extr\{c^T x|Ax≤pb+d\}$,where $Extr$ is either $min$ or $max$, and $p$ is a real parameter. It is known that the optimal values for $p= 1,2,3$ are, respectively, $0,2,5$. What is $Extr$?
I tried solving it geometrically, but that was to no avail. I am clueless on any other possible ways to solve this.
Do you mean for the objective $c^Tx$ ? Because if we assume $Extr\{c^T x|Ax\leq pb + d\}$ we can see the following:
Assume $x_1$ is the optimum for $p=1$ with $c^Tx_1=0$, $x_2$ the optimum for $p=2$ with $c^Tx_2=2$ and $x_3$ the optimum for $p=3$ with $c^Tx_3=5$. Note that $x_1$ and $x_3$ satisfy the constraints $Ax_1\leq b +d$ and $Ax_3 \leq 3b +d$. The sum of both inequalities gives you $A(x_1+x_3)\leq 4b + 2d$, which implies $A(\frac{x_1+x_3}{2})\leq 2b + d$. By that we see that $\frac{x_1+x_3}{2}$ is a feasible solution for the case $p=2$ with objective value $c^T(\frac{x_1+x_3}{2})=\frac{1}{2}(c^Tx_1 + c^Tx_3)=\frac{1}{2}(0 + 5)=2.5$. Assume now $Extr=max$, then $c^Tx_2\geq c^T x \ \forall x\in \{x|Ax\leq 2b + d\}$ by the optimality of $x_2$. But since $\frac{x_1+x_3}{2}\in \{x|Ax\leq 2b + d\}$ this is a contradiction because $2=c^Tx_2 \geq c^T(\frac{x_1+x_3}{2})=2.5$. Therefore we must have $Extr=min$.