Linear Optimization Conversion (nested free variable)

In summary, the LP formulation for this problem involves maximizing a linear function while satisfying a set of linear constraints, and can be solved using standard LP techniques.
  • #1
Passanger
1
0

Homework Statement


(This is a mock-up)
Given
maximize(x,y) Ax + | x - y |

s.t.
x + By - C >= 0
y >= 0

A, B, and C are some coefficients.

Homework Equations


Linearizing absolute expressions:
z = | x |; where z >= x, z >= -x

Linearizing free variables:
let x = x+ - x-; where x+, x- >= 0 ---- (1)

The Attempt at a Solution


-------------------------------------------------------------------------------------------------------
(I think?) x is not constrained like y (as in y >= 0),
Let x = x+ - x-; where x+, x- >= 0

To linearize the expression | x - y |
Let z = | x - y |; such that z >= ( x - y ) and z >= -( x - y )

So... From (1):
Let z = | x+ - x- - y |; such that z >= ( x+ - x- - y ) and z >= -( x+ - x- - y )
-------------------------------------------------------------------------------------------------------
Therefore, the LP for this problem is
maximize(x,y) A(x+ - x-) + z

s.t.
x+ - x- + By - C >= 0
y >= 0
z >= ( x+ - x- - y )
z >= -( x+ - x- - y )
x+, x- >= 0

... ?
 
Physics news on Phys.org
  • #2


Your attempt at a solution is correct. The linear programming (LP) formulation for this problem is:

maximize(x,y,x+,x-,z) A(x+ - x-) + z

s.t.
x+ - x- + By - C >= 0
y >= 0
z >= ( x+ - x- - y )
z >= -( x+ - x- - y )
x+, x- >= 0

This formulation can be solved using standard LP techniques, such as the simplex method. The objective function can be maximized by adjusting the values of x+, x-, and z, while ensuring that the constraints are satisfied.
 

1. What is linear optimization conversion?

Linear optimization conversion is a mathematical technique used to find the optimal value of a linear objective function while satisfying a set of linear constraints. It is also known as linear programming and is used in various fields such as economics, engineering, and operations research.

2. What are nested free variables in linear optimization conversion?

Nested free variables refer to variables that are not explicitly mentioned in the objective function or the constraints, but are instead defined in terms of other variables. These variables can take on any value and are not restricted by any constraints. They are often used to simplify the problem and make it easier to solve.

3. How are nested free variables handled in linear optimization conversion?

Nested free variables are handled by using additional constraints to define their relationship with the other variables. These constraints are then included in the optimization problem, allowing the nested free variables to be optimized along with the other variables. In some cases, the nested free variables may be eliminated through variable substitution, depending on the specific problem.

4. What are some applications of linear optimization conversion?

Linear optimization conversion has many applications in real-world problems, such as resource allocation, production planning, and transportation logistics. It is also used in portfolio optimization, where it helps to determine the optimal mix of investments to maximize returns while considering risk. It is also used in diet planning and scheduling problems.

5. What are the benefits of using linear optimization conversion?

Linear optimization conversion allows for the efficient allocation of resources, leading to cost savings and increased productivity. It also provides a systematic and structured approach to decision-making, allowing for better-informed decisions. Additionally, it can handle complex problems with multiple variables and constraints, making it a valuable tool in a wide range of industries and fields.

Similar threads

  • Engineering and Comp Sci Homework Help
Replies
1
Views
1K
  • Precalculus Mathematics Homework Help
Replies
17
Views
907
  • Calculus and Beyond Homework Help
Replies
8
Views
344
  • Engineering and Comp Sci Homework Help
Replies
1
Views
1K
  • Set Theory, Logic, Probability, Statistics
Replies
30
Views
2K
  • Calculus and Beyond Homework Help
Replies
1
Views
465
  • Linear and Abstract Algebra
Replies
11
Views
1K
Replies
5
Views
833
  • Calculus and Beyond Homework Help
Replies
3
Views
870
  • Quantum Physics
Replies
13
Views
710
Back
Top