Let $$f(x) = \left\{ \begin{array}{l} {a_1}x + {b_1} & if\,0 \le {x_1} \le x \le {x_2}\\ {a_2}x + {b_2} & if\,{x_2} < x \le {x_3}\\ \vdots \\ {a_n}x + {b_n} & if\,{x_{n - 1}} < x \le {x_n} \end{array} \right.$$ be a piecewise continuous function and $0\leq a_1\leq a_2\leq \cdots \leq a_n$.

Formulate the problem of miniimizing $f(x)$ in terms of linear programming

  • 3
    $\begingroup$ Is this problem a homework problem? $\endgroup$ – Geoff Oxberry Sep 30 '13 at 17:30

Note that $f(x)=\max_{i} a_{i}x+b_{i}$. You can then reformulate the problem as

$\min_{t,x} t $

subject to

$ t \geq a_{i}x + b_{i}$, $i=1, 2, \ldots, n$.

| cite | improve this answer | |
  • $\begingroup$ but optimal point may not lying in the intervals. can you give an example (for n=2) $\endgroup$ – SKMohammadi Sep 30 '13 at 15:44
  • 1
    $\begingroup$ Your comment doesn't make sense as a sentence in English, so I'm not sure what you're asking. If you're concerned that the minimum of the LP might be outside of the interval $[x_{1},x_{n}]$, you can simply add the constraints $x \geq x_{1}$ and $x \leq x_{n}$. Pick any numbers that you want for $a_{1}$, $b_{1}$, $a_{2}$, and $b_{2}$ and try it. $\endgroup$ – Brian Borchers Sep 30 '13 at 16:14
  • $\begingroup$ Maybe a feasible point do not satisfy all restrictions! Please give an simple example. $\endgroup$ – SKMohammadi Oct 2 '13 at 5:46

Not the answer you're looking for? Browse other questions tagged or ask your own question.