Linear programming with min of max function

An important fact on this.

Given $k_1,dots,k_n$ :

$$max(k_1,dots,k_n) iff min({M :k_1leq M,dots ,k_n leq M})$$

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.)