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]
 

Related to 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
3
Views
862
  • Linear and Abstract Algebra
Replies
9
Views
2K
  • Introductory Physics Homework Help
Replies
4
Views
800
  • Calculus and Beyond Homework Help
Replies
5
Views
3K
  • Calculus and Beyond Homework Help
Replies
2
Views
4K
  • Calculus and Beyond Homework Help
Replies
20
Views
2K
Replies
3
Views
1K
Replies
24
Views
2K
  • Precalculus Mathematics Homework Help
Replies
19
Views
2K
  • Calculus and Beyond Homework Help
Replies
24
Views
2K
Back
Top