1

I was given two linear systems {$2x=1$, $x=1$} and I was told to write the min-max model. Which I hope I did correctly and got

$|| Ax-b||$ = max {$||2x-1||, ||x-1||$} -> min.

now it is asking me to write the min-max model in the standard LP form as defined on-page $152$ of [Forst]

enter image description here

So I am assuming that the form is (P).

I have found these lecture notes online which helped me understand how to change LP into SF. However, I am still unsure of how I can do that with my question. Any help would be really appreciated.

Hidaw
  • 971
  • This linear system is empty $x=1$ do not satisfy $2x=1$. You can use the $||.||_{\infty}$ to minimize the error but, there is no solution. – Alexandre Frias Sep 29 '19 at 03:38

1 Answers1

1

Probably, you want to minimize the error of $||Ax-b||_{\infty}$. Let $t=\max\{|2x-1|, |x-1|\}$ the error of the linear system solution.

$$ \begin{align} \min ~ t & \\ &|2x-1|\leq t\\ &|x-1|\leq t\\ & t\geq 0 , ~ x\in \mathbb{R} \end{align} $$

Removing the module

$$ \begin{align} \min ~ t & \\ & 2x-1\leq t\\ & 2x-1\geq t\\ & x-1\leq t\\ & x-1\geq t\\ & t\geq 0 , ~ x\in \mathbb{R} \end{align} $$

Putting in standard form using $x=x_1 - x_2$ and adding $s_1, ...s_4$

$$ \begin{align} \min ~ t & \\ & 2x_1 - 2x_2 -t +s_1 = 1\\ & 2x_1 - 2x_2 -t -s_2 = 1\\ & x_1 - x_2 -t +s_3 = 1\\ & x_1 - x_2-t - s_4 = 1\\ & t\geq 0 , x_i\geq 0, s_j\geq 0 \end{align} $$

Alexandre Frias
  • 462