I have a very simple linear problem: <mtable columnalign="right left" rowspacing="3pt" column

Brenden Tran

Brenden Tran

Answered question

2022-06-23

I have a very simple linear problem:
min x   x 2 s.t.    a 1 x 1 + a 2 x 2 = b
Suppose I want to write this problem equivalently as in Find the equivalent linear program. Unlike the problem in the link, I have equality. Can I write it equivalently as:
min x , α , β   x 2 s.t.    a 1 x 1 = α b ,   a 2 x 2 = β b ,   α + β = 1.
The converse is intuitive: Given { x , α , β } feasible for the second problem, adding the first and second constraints gives the constraint of the first problem. But the forward part is not clear, especially because I have never seen an equality constraint written like this. Any help would be highly appreciated.

Answer & Explanation

EreneDreaceaw

EreneDreaceaw

Beginner2022-06-24Added 20 answers

You are correct. Suppose x is feasible. Then a 1 x 1 + a 2 x 2 = b ( a 1 x 1 + a 2 x 2 = ( α + β ) b  and  α + β = 1 ) . Therefore any solution satisfying the latter conditions is also feasible.

A simple example to explain what I think is the part you are unclear about is the following. Look at the following two problems:
1.
min x   x s.t.    x 2 x R
2.
min x   x s.t.    x 2 x 1 x R
They obviously generate the same feasible solution; the constraint added is weaker than the existing constraint. Similarly the following problem also generates the same feasible solution:
min x , a   x s.t.    x a a = 2 x R

Do you have a similar question?

Recalculate according to your conditions!

New Questions in Multivariable calculus

Ask your question.
Get an expert answer.

Let our experts help you. Answer in as fast as 15 minutes.

Didn't find what you were looking for?