148
правок
Изменения
→Доказательство корректности алгоритма
<ul><tex>\sum \limits_{i = 1}^k a_{i} \le \sum \limits_{i = 1}^k b_{i} \le \sum \limits_{i = 1}^{k - 1} b_{i} + b_{x}</tex></ul>
Это неравенство следует из выбора <tex>I</tex> и из того, что <tex>b_{x} \ge a_{x} \ge a_{i}, \forall i \in I</tex>.<br/>
Получили, что каждая работа из этого блока начинает выполняться на втором станке позже, чем она заканчивается на первом.</li><li>Для блока Покажем, что любая работа из <tex>J</tex> начинает выполняться на втором станке позже, чем заканчивает выполняться на первом. Для этого рассмотрим сумму:
<ul><tex>\sum \limits_{i = 1}^k b_{i} \le \sum \limits_{i = 1}^k a_{i} \le \sum \limits_{i = 1}^{k - 1} a_{i} + a_{x}</tex></ul>
Это неравенство следует из выбора <tex>J</tex> и из того, что <tex>a_{x} \ge a_{i}, \forall i \in I</tex>.<br/>
Получили, что этот блок тоже не пересекаетсякаждая работа из этого блока начинает выполняться на втором станке позже, чем она заканчивается на первом.</li>
</ol>
Итого мы доказали корректность.<br/>
