90
правок
Изменения
→Доказательство корректности алгоритма
Пусть <tex> w_{ij} </tex> {{---}} время, прошедшее с начала выполнения работы <tex> i </tex> на первом станке до окончания работы <tex> j </tex> на втором станке.
...
Таким образом, <tex> w_{ij} = \max (p_{i1} + p_{j1} + p_{j2}, p_{i1} + p_{i2} + p_{j2}, delta + p_{i2} + p_{j2}) </tex>. Иначе говоря <tex> w_{ij} = \max (p_{i1} + \max(p_{j1}, p_{i2}) + p_{j2}, delta + p_{i2} + p_{j2}) </tex>.
Аналогично имеем, что <tex> w_{ji} = \max (p_{j1} + \max(p_{i1}, p_{j2}) + p_{i2}, delta + p_{i2} + p_{j2}) </tex>
Так как <tex> \min(a, b) = - \max(-a, -b)</tex>, то из условию леммы имеем <tex> \max(-p_{i1}, -p_{j2}) \leq \max(-p_{j1}, -p_{i2}) </tex>, то добавим <tex> p_{i1} + p_{i2} + p_{j1} + p_{j2} </tex> к обеим частям. То получим, что <tex> p_{j1} + \max(p_{i1}, p_{j2}) + p_{i2} \leq p_{i1} + \max(p_{j1}, p_{i2}) + p_{j2} </tex>, то есть <tex> w_{ji} \leq w_{ij} </tex>, то при смене местами работ <tex> i </tex> и <tex> j </tex> ответ не ухудшается.
}}
