I have to write the linear program which minimizes this function :
$$y = \max_j \sum_{i=1}^{n}c_{ij}x_{ij}$$
My book says that this is not a linear function but it can be trasformed into one using the minimizing program $\min y$ with the conditions :
$$ \sum_{i=1}^{n}c_{ij}x_{ij} \leq y \:\:, \:\:j = 1,...,m$$
(+ other conditions not related with $y$)
I really don't get why when these conditions are met then I should consider it a linear program, $y$ isn't neither a linear function nor a constant as far as I understand. Besides, I don't get neither how to calculate the maximum, can $y$ be traslated as :
$$\max (\sum_{i=1}^{n}c_{ij}x_{ij} \:\:, \:\:j = 1,...,m) $$
But, then I have a function with different variables, so how can I find a maximum, maybe considering the other restrictions ?
Maybe, I'm misunderstanding everything , I'm new to linear programming
2 Answers
The $y$ in the linear program is being treated as a totally new variable that doesn't (directly) keep its old meaning as $\max_j \sum_i c_{ij} x_{ij}$. I suspect the reason for your confusion is that you're continuing to try to expand $y$ out to its old definition inside the linear program.
The point is that by adding a constraint that $\sum c_{ij} x_{ij} \leq y$ for each $j$, the linear program requires that the value assigned to the variable $y$ is at least $\max_j \sum_i c_{ij} x_{ij}$, so any optimal solution of the linear program, having made the variable $y$ as small as possible, must in fact make $y$ equal to $\max_j \sum_i c_{ij}x_{ij}$. (The constraints only force that $y$ is at least this max, but clearly there's no reason to have $y$ any larger than the max if there are no other constraints involving $y$, so an optimal solution makes it equal.)
An important fact on this.
Given $k_1,\dots,k_n$ :
$$\max(k_1,\dots,k_n) \iff \min(\{M :k_1\leq M,\dots ,k_n \leq M\})$$
