90
правок
Изменения
→Доказательство корректности алгоритма
То есть имеем, что <tex> p_{i1} < \min(p_{j1}, p_{i2}) </tex>. Так как <tex> p_{i1} < \min(p_{j1}, p_{i2}) \leq p_{i2} </tex>, то работа <tex> i \in L </tex>. Работа <tex> j </tex> либо стоит в <tex> R </tex>, либо она стоит в <tex> L </tex> и при этом <tex> p_{i1} < p_{j1} </tex>. Заметим, что в обоих случаях она расположена позже( в силу нашего построения), чем работа <tex> i </tex>, то лемма доказана.
}}
{{Лемма
|id=lemma2
|about=2
|statement= Пусть имеет случайное расписание, в котором работа <tex> j </tex> идет сразу же после работы <tex> i </tex>. Тогда если <tex> \min(p_{j1}, p_{i2}) \leq \min(p_{i1}, p_{j2}) </tex>, то можем поменять местами эти работы без ухудшение целевой функций.
|proof=
TODO
}}
