Изменения

Докажем то, что описанный выше алгоритм корректен. Для этого достаточно показать, что если имеются 3 вектора a, b, c, расположенные как на рис. 5, т.е. точка b не лежит на выпуклой оболочке векторовч векторов <tex>0, a, b, c </tex> : <tex> \Leftrightarrow |[a-b, b-c]| < 0 </tex>, то либо <tex>(a, u[i])</tex> оптимальнее, чем <tex>(b, u[i])</tex>, либо <tex>(с, u[i])</tex> оптимальнее, чем <tex>(b, u[i])</tex>

|statement=Если есть <tex>3 </tex> вектора <tex>a, b, c</tex>, таких что <tex>|[a-b, b-c]| < 0</tex> то либо <math>(a, u[i]) < (b, u[i])</math>, либо <math>(c, u[i]) < (b, u[i])</math>, где вектор <math>u = (1; k)</math>.|proof=<tex>|[a-b, b-c]| < 0 \Leftrightarrow (a_{x} - b_{x})\cdot(b_{y} - c_{y}) < (a_{y} - b_{y}) \cdot (b_{x} - c_{x})</tex> (*). Предположим (от противного), что <tex>(b, u[i]) < (a, u[i]) \Leftrightarrow b_{x} + a[i] k \cdot b_{y} < c_{x} + a[i] k \cdot c_{y} \Leftrightarrow (b_{x} - c_{x}) < a[i] k \cdot (c_{y} - b_{y})</tex> и <tex>(b, u[i]) < (c, u[i]) \Leftrightarrow b_{x} + a[i] k \cdot b_{y} < a_{x} + a[i] k \cdot a_{y} \Leftrightarrow (a_{x} - b_{x}) > a[i] k \cdot (b_{y} - a_{y})</tex>.

Подставим эти неравенства в (*). Получим цепочку неравенств : <tex>a[i] k \cdot (a_{y} - b_{y})</tex><tex> \cdot (c_{y} - b_{y}) = a[i]k</tex><tex> \cdot (b_{y} - a_{y}) \cdot </tex><tex>(b_{y} - c_{y})</tex> <tex> < (a_{x} - b_{x})</tex><tex> \cdot (b_{y} - c_{y})</tex><tex> < (a_{y} - b_{y}) \cdot </tex><tex>(b_{x} - c_{x})</tex> <tex>< a[i] k \cdot (a_{y} - b_{y})</tex><tex> \cdot (c_{y} - b_{y})</tex>. Получили противоречие : <tex>a[i] k \cdot (a_{y} - b_{y}) \cdot (c_{y} - b_{y}) < a[i] k \cdot (a_{y} - b_{y}) \cdot (c_{y} - b_{y})</tex>. Значит предположение неверно, чтд.