40
правок
Изменения
м
→Доказательство корректности алгоритма
Докажем теперь второе утверждение. У нас имеется 3 блока работ: <tex> I \setminus \{x\}, \{x\}, J</tex>.
<ol>
<li>Для блока <tex> \{x\}</tex> пересечения отсутствуют это следует из того, что <tex> C_{max} \ge a_{x}+b_{x}</tex>, а этот блок работа <tex> x </tex> выполняется с разных концов станков. Получили, что отрезки выполнения работы <tex> x </tex> на разных станках не пересекаются.</li><li>Для блока Покажем, что любая работа из <tex> I \setminus \{x\}</tex> начинает выполняться на втором станке позже, чем заканчивает выполняться на первом. Для этого рассмотрим сумму:
<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/>
</ol>
Итого мы доказали корректность.<br/>
Оптимальность вытекает, из того, что <tex>C_{max}</tex> не может быть меньше <tex>\sum \limits_{i = 1}^{n} a_i, \sum \limits_{i = 1}^{n} b_i, \max \limits_{i = 1}^{n}\{a_i + b_{i}\}</tex>, а из построения оно равно максимум максимуму из нихэтих значений.
}}
