Exercise 1.4

Consider the problem

minimize 2x1 + 3|x2 − 10| subject to|x1 + 2| + |x2|≤ 5,

and reformulate it as a linear programming problem.

Answers

Following the procedure described on the p. 18, we express the first absolute value as z1, the second as z2 and the third as z3. We then obtain the following linear problem:

minimize 2x1 + 3z1 subject to z2 + z3 ≤ 5 x2 − 10 ≤ z1 − x2 + 10 ≤ z1 x1 + 2 ≤ z2 − x1 − 2 ≤ z2 x2 ≤ z3 − x2 ≤ z3

Moving variables to the left and constraints to the right, we rewrite the above as:

minimize 2x1 + 3z1 subject to z2 + z3 ≤ 5 x2 − z1 ≤ 10 − x2 − z1 ≤−10 x1 − z2 ≤−2 − x1 − z2 ≤ 2 x2 − z3 ≤ 0 − x2 − z3 ≤ 0.

Alternatively, we can use the matrix notation:

minimize [ 20300 ] [ x1 x2 z1 z2 z3 ] subject to [ 0 0 0−1−1 0 −1 1 0 0 0 1 1 0 0 −1 0 0 1 0 1 0 0 1 0 0 −1 0 0 1 0 1 0 0 1 ] [ x1 x2 z1 z2 z3 ] ≥ [−5 −10 10 2 −2 0 0 ].
User profile picture
2022-02-03 21:50
Comments