How do i prove that this LP is equivalent to a piecewise linear function?

53 Views Asked by At

Let be $$z(e)=min \sum_{k=1}^Rp_k\sum_{j=1}^M q_j(\sum_{i=1}^M c_ig_{ijk}+c_\delta\delta_{jk})\\ s.a \sum_{i=1}^M g_{ijk}+h_{jk}+\delta_{jk}=d_j\\ 0\leq g_{ijk}\leq\overline{g}_{ik}\\0\leq h_{jk}\leq\overline{h}_j\\ \sum_{k=1}^Rp_k\sum_{j=1}^M q_j h_j=e$$.I want to show that $ z (e) $ is a piecewise linear function with respect to the independent term $e$.

I tried to see first what happens with $\dfrac{\partial z(e)}{\partial e}$, if I can see that they are of the form $a_i$ then it could have support hyperplanes like this $$a_ie+b_i$$ Another approach I could give it is to take the dual, to form a maximum, but I still can't get to the piecewise linear function form.