No Optimal Explaining Formally

[evinda]

Hello! (Wave)

There is given the following example of a linear programming problem that has no optimal solution.

View attachment 4813

$$\begin{Bmatrix}
a_{11}x_1+a_{12}x_2 \geq b_1 & \\
a_{21}x_1+a_{22}x_2 \geq b_2 &
\end{Bmatrix} \Leftrightarrow (x_1,x_2) \in D \\ \\ \\ \\ \ \ \max_{(x_1, x_2) \in D} (x_1+x_2)$$

How could we explain formally that there is no optimal solution? (Thinking)

 

[I like Serena]

Hello! (Wave)

There is given the following example of a linear programming problem that has no optimal solution.

$$\begin{Bmatrix}
a_{11}x_1+a_{12}x_2 \geq b_1 & \\
a_{21}x_1+a_{22}x_2 \geq b_2 &
\end{Bmatrix} \Leftrightarrow (x_1,x_2) \in D \\ \\ \\ \\ \ \ \max_{(x_1, x_2) \in D} (x_1+x_2)$$

How could we explain formally that there is no optimal solution? (Thinking)

Hey evinda! (Smile)

Before we can do that, we need to know more about the $a_{ij}$.
Can we for instance assume that they are non-negative? (Wondering)

 

[evinda]

Hey evinda! (Smile)

Before we can do that, we need to know more about the $a_{ij}$.
Can we for instance assume that they are non-negative? (Wondering)

It holds that $a_{ij} \in \mathbb{R}, x_i \geq 0, i=1, \dots, n, b_j \geq 0, j=1, \dots, m$.

 

[I like Serena]

It holds that $a_{ij} \in \mathbb{R}, x_i \geq 0, i=1, \dots, n, b_j \geq 0, j=1, \dots, m$.

Let's pick $a_{ij} = -1, b_j = 0$ for every $i,j$.
Can you find an optimal solution for it? (Wondering)

 

[evinda]

Let's pick $a_{ij} = -1, b_j = 0$ for every $i,j$.
Can you find an optimal solution for it? (Wondering)

Then it has to hold that $x_1=x_2=0$ so the maximum is equal to $0$, right?

So under which conditions isn't there an optimal solution, given that we have an unbounded space? (Thinking)

 

[I like Serena]

Then it has to hold that $x_1=x_2=0$ so the maximum is equal to $0$, right?

So under which conditions isn't there an optimal solution, given that we have an unbounded space? (Thinking)

Yes. (Nod)

Either when there is no solution at all, or when the solution space is unbounded in the direction of increasing value. (Thinking)

Suppose we start with 1 boundary condition.
For which angles of the line of the boundary condition will there be no feasible solution?
And for which angles will the maximum be unbounded? (Wondering)