Upper Bound for Optimal Value in Max Problem

In summary, the problem involves finding an upper bound for the optimal value in a maximization problem with four variables and three constraints. The upper bound is defined as the smallest value that is greater than or equal to all values in a given set.
  • #1
pinki82
9
0
Obtain an upper bound for the optimal value in the following problem;
Max (4x_1 + x_2 + 2x_3 + 3x_4 )
2x_1 - x_2 + x_3 - 2x_4 <= 2
7x_1 + x_2 + 5x_3 + 10x_4 <= 4
2x_1 + 3x_2 - x_3 - x_4 <= 2
x_i >= 0 , i= 1,2,3,4

any hint.help. please.
thanks

note: >= means > or equal to
<= means < or equal to

WORK DONE :

I understnad how to find the optimal value...but how do i find the
upper bound?
i don't really understand what is meant by the Upper Bound??

thanks.
 
Physics news on Phys.org
  • #2
Definition of upper bound:

Given an ordered set [tex] X and A \subset X , s \in X is its "upper bound" ( sup\{A\}) \leftrightharpoons \forall x \in A, x \preceq s et \forall y \prec s \exists a \in A : a \prec y[/tex]
 

FAQ: Upper Bound for Optimal Value in Max Problem

1. What is an upper bound for optimal value in a max problem?

An upper bound for optimal value in a max problem refers to the maximum possible value that can be achieved in the problem. It is often used as a benchmark for evaluating the performance of different algorithms or solutions in finding the optimal value.

2. How is an upper bound determined in a max problem?

An upper bound is determined by analyzing the problem and its constraints. It involves finding the maximum possible value that can be obtained without violating any of the constraints. This can be done through mathematical calculations or by using heuristics and approximation techniques.

3. Why is it important to know the upper bound for optimal value in a max problem?

Knowing the upper bound for optimal value is important because it provides a reference point for evaluating the quality of solutions. If a solution is close to the upper bound, it can be considered a good solution. Additionally, the upper bound can help in identifying any gaps or room for improvement in the problem formulation.

4. Can the upper bound be used to find the optimal solution in a max problem?

No, the upper bound itself does not provide the optimal solution. It only serves as a benchmark for evaluating the performance of solutions. However, it can be used to guide the search for the optimal solution by providing a target to aim for.

5. How can the upper bound be improved in a max problem?

The upper bound can be improved by refining the problem formulation or by using more advanced algorithms and techniques. Additionally, incorporating additional information or constraints into the problem can also help in improving the upper bound.

Similar threads

Replies
9
Views
2K
Replies
20
Views
2K
Replies
5
Views
3K
Replies
3
Views
1K
Replies
29
Views
6K
Replies
24
Views
2K
Back
Top