0

I was given the following linear program

$ \begin{align} \alpha x_1 + \beta x_2 &\rightarrow \max \\ -3x_2 &\le -9 \\ -x_1-2x_2 &\le -12 \\ -x_1-x_2 &\le -8 \end{align} $

where $\alpha$ and $\beta$ are real parameters.

The question states the following: "There exist exactly three different vectors $(\alpha, \beta)^T$ with $||(\alpha, \beta)^T|| = 1$ (i.e. the Euclidean norm of the vector is equal to one) for which this linear program has infinitely many optimal solutions. Determine these three vectors."

To my understanding there are infinitely many possibilities to define $\alpha$ and $\beta$ because the solution space is unbounded in the "upper right". What am I missing here? Why are there only three valid combinations for $\alpha$ and $\beta$?

Edit: Here's a drawing of the constraints and the solution space.

enter image description here

Sebastiano
  • 7,649
user1195883
  • 113

2 Answers2

0

Partial answer: The LP can have infinetely many solution if the objective function lies on one the active constraints. First we have the condition $\sqrt{\alpha^2+\beta^2}=1$.

See here for an explanation for multiple (infinitely) solutions. If I take the second constraint, the fraction of the two coefficients is $\frac{-1}{-2}=\frac12$. This has to be equal to $\frac{\alpha}{\beta}$. This leads to an equation system with two equations and two unknowns. From the two possible solutions choose the one which makes sense.

callculus42
  • 30,550
  • I don't understand. The condition $\sqrt{\alpha^2+\beta^2} = 1$ is clear but why does the second constraint lead to the condition $\frac{\alpha}{\beta} = \frac{1}{2}$? And what would then be the third solution? Note: I've added a drawing to the original question for clarity. – user1195883 Jan 26 '24 at 20:22
  • @user1195883 The second constraint is $\color{red}{-1}x_1-\color{red}{2}x_2 \le -12$. The corresponding coefficients of the objective function are $\alpha$ and $\beta$. The fractions (slopes) has to be equal $\frac{-1}{-2}=\frac{1}{2}=\frac{\alpha}{\beta}$. Then at the optimum the objective function lies on the second constraint ($\color{blue}{blue}$). – callculus42 Jan 26 '24 at 20:29
  • But why does the optimum remain on the second constraint (blue line) when the objective is to maximize? Is this maybe the issue here, should it be a minimize problem? Then the three vectors for the three infinitely many solutions would make sense to me. – user1195883 Jan 27 '24 at 08:23
  • @user1195883 You maximize the objective function by holding the (positive) values of the solution as small as possible. From the graph you see that the values must be positive. At the objective function you can see that the greater they are the smaller is the objective funtion. Therefore, the smallest possible values ​​are used in order to maximize the objective function. That the problem is a maximizing problem corresponds with the graph. – callculus42 Jan 27 '24 at 17:40
0

With the valuable input from calculus42 I think I got it now. Since this is a maximization problem we need to find three vectors that are pointing away from the solution space orthogonal to each one of the constraints to answer the question.

For the first constraint (red line) it's trivial to see in the picture: $(0, -1)$. Formally the equations would be:

$$ \begin{align} \sqrt{\alpha^2+\beta^2} &= 1 \\ \frac{\alpha}{\beta} &= 0 \end{align} $$

The result is $\{(0, -1), (0, 1)\}$ from which we take $(0, -1)$.

For the second constraint (blue line) we get:

$$ \begin{align} \sqrt{\alpha^2+\beta^2} &= 1 \\ \frac{\alpha}{\beta} &= \frac{1}{2} \end{align} $$

The result is $\{(-0.447, -0.894), (0.447, 0.894)\}$ from which we take $(-0.447, -0.894)$.

For the third constraint (green line) we get:

$$ \begin{align} \sqrt{\alpha^2+\beta^2} &= 1 \\ \frac{\alpha}{\beta} &= 1 \end{align} $$

The result is $\{(-0.707, -0.707), (0.707, 0.707)\}$ from which we take $(-0.707, -0.707)$.

user1195883
  • 113