Optimization with absolute values: Difference between revisions
No edit summary |
No edit summary |
||
| Line 2: | Line 2: | ||
Steward: Fengqi You | Steward: Fengqi You | ||
==Numerical Example== | |||
<math>\ Min |x_1| + 2|x_2| + |x_3| </math><br> | |||
<math>\ s.t. x_1 + x_2 - x_3 \le 10</math> | |||
<math> x_1 - 3x_2 + 2x_3= 12</math> | |||
We replace the absolute value quantities with a single variable: | |||
<math>|x_1| = U_1 </math> | |||
<math>|x_2| = U_2</math> | |||
<math>|x_3| = U_3</math> | |||
We must introduce additional constraints to ensure we do not lose any information by doing this substitution: | |||
<math> -U_1 \le x_1 \le U_1 </math> | |||
<math> -U_2 \le x_2 \le U_2 </math> | |||
<math> -U_3 \le x_3 \le U_3 </math> | |||
The problem has now been reformulated as a linear programming problem that can be solved normally: | |||
<math>\ Min U_1 + 2U_2 + U_3 </math><br> | |||
<math>\ s.t. x_1 + x_2 - x_3 \le 10</math> | |||
<math> x_1 - 3x_2 + 2x_3 = 12</math> | |||
<math> -U_1 \le x_1 \le U_1 </math> | |||
<math> -U_2 \le x_2 \le U_2 </math> | |||
<math> -U_3 \le x_3 \le U_3 </math> | |||
The optimum value for the objective function is <math>6</math>, which occurs when <math>x_1 = 0 </math> and <math>x_2 = 0 </math> and <math>x_3 = 6 </math>. | |||
Revision as of 16:29, 20 November 2020
Authors: Matthew Chan (mdc297), Yilian Yin (), Brian Amado (ba392), Peter (pmw99), Dewei Xiao (dx58) - SYSEN 5800 Fall 2020
Steward: Fengqi You
Numerical Example
Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ Min |x_1| + 2|x_2| + |x_3| }
Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ s.t. x_1 + x_2 - x_3 \le 10}
Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle x_1 - 3x_2 + 2x_3= 12}
We replace the absolute value quantities with a single variable:
Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle |x_1| = U_1 }
Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle |x_2| = U_2}
Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle |x_3| = U_3}
We must introduce additional constraints to ensure we do not lose any information by doing this substitution:
Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle -U_1 \le x_1 \le U_1 }
Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle -U_2 \le x_2 \le U_2 }
Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle -U_3 \le x_3 \le U_3 }
The problem has now been reformulated as a linear programming problem that can be solved normally:
Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ Min U_1 + 2U_2 + U_3 }
Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ s.t. x_1 + x_2 - x_3 \le 10}
Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle x_1 - 3x_2 + 2x_3 = 12}
Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle -U_1 \le x_1 \le U_1 }
Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle -U_2 \le x_2 \le U_2 }
Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle -U_3 \le x_3 \le U_3 }
The optimum value for the objective function is Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 6} , which occurs when Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle x_1 = 0 } and Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle x_2 = 0 } and Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle x_3 = 6 } .