Доведення.
Нагадаємо визначення опуклості множини:
Точкова множина S називається опуклою множиною (ОМ), якщо для його довільних точок p,q: точки відрізка належать S, тобто
w = , (*)
- на прикладі відрізка:
множина визначається співвідношенням (9.3.1)
Нехай тепер x, y - довільна пара точек з X.
Тоді з (9.3.1) справедливо
Ax = b, ; Ay =b,
Відрізок, що з’єднує ці точки, позначимо, як множину точок w,
Із визначення (*) - (див рис) ці точки можно представити як ,
(тобто, аналогично як ми записували ), і , ,
Звідси маємо тобто
Aw = b,
Дивимся на 9.3.1. и бачимо, що твердження доведено.
Доведення інших властивостей можна подивитися в «И.В.Семушин. Практикум по методам оптимізації», необхідні відомості, потрібні для зрозуміння доведень наведені в вставці нижче.
Вставка** П
Перестановки, матриця перестановок
Перестановки транспозиції парні і непарні перестановки
Розглянемо множину S натуральних чисел від 1 до n, розташованих в порядку зростання (в природному порядку):
Під перестановкою множини S розуміється множина цих же чисел, впорядкована деяким іншим чином:
Перестановка називається транспозицією, якщо переставляються місцями тільки два елементи множини, тоді як інші елементи залишаються на своїх місцях.
Приклад перестановки: Приклад транспозиції:
Будь-яку перестановку множини S можна здійснити за допомогою декількох транспозицій.
Наприклад, перестановка {2,4,1,3} є результатом трьох транспозиція множини :
1234 3214 2314 2413
Кажуть, що перестановка множини S містить інверсію елементів ij та ik ,, якщо є порушеним їх природний порядок розташування, тобто більший елемент розташований лівіше меншого ij > ik ( j < k ).
Наприклад, перестановка {2, 4, 1, 3} містить три інверсії елементів:
2 і 1,
4 і 1,
4 і 3.
Число інверсій визначає парність перестановки. Перестановка називається парною, якщо вона містить парне число інверсій елементів. Непарна перестановка містить непарне число інверсій. Зауважимо, що парна перестановка може бути перетворена до природного порядку за допомогою тільки парного числа транспозицій, для перетворення непарної перестановки до природного порядку потрібно непарне число транспозицій. (Це твердження є наслідком Теореми 1, см розділ "Теореми про транспозиція і перестановках".)
Достарыңызбен бөлісу: |
