MHB No Optimal Explaining Formally

  • Thread starter Thread starter evinda
  • Start date Start date
AI Thread Summary
The discussion centers on a linear programming problem that lacks an optimal solution due to its unbounded solution space. Participants explore the implications of the coefficients and constraints, specifically when they are negative or zero, which can lead to scenarios where the maximum value is not attainable. It is established that an optimal solution may not exist if the solution space is unbounded in the direction of increasing values or if there are no feasible solutions at all. The conversation also raises questions about the angles of boundary conditions that affect feasibility and unboundedness. Understanding these conditions is crucial for formally explaining the absence of an optimal solution.
evinda
Gold Member
MHB
Messages
3,741
Reaction score
0
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)
 

Attachments

  • graph5.png
    graph5.png
    7.8 KB · Views: 84
Physics news on Phys.org
evinda said:
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)
 
I like Serena said:
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$.
 
evinda said:
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)
 
I like Serena said:
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)
 
evinda said:
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)
 
I was reading documentation about the soundness and completeness of logic formal systems. Consider the following $$\vdash_S \phi$$ where ##S## is the proof-system making part the formal system and ##\phi## is a wff (well formed formula) of the formal language. Note the blank on left of the turnstile symbol ##\vdash_S##, as far as I can tell it actually represents the empty set. So what does it mean ? I guess it actually means ##\phi## is a theorem of the formal system, i.e. there is a...
Back
Top