Твердження
Для будь-яких двох перестановок їх матриці мають властивість:
де “ ” - операція множення двох перестановок.
Терема 2.
Матриця перестановок n-го порядку може бути представлена у вигляді множення (n - 1) елементарних матриць перестановок.
Терема 3. Квадрат елементарної матриці перестановок є одинична матриця.
Твердження: Для будь-якої матриці перестановок існує зворотна матриця, що дорівнює вихідній транспонованій
де - транспонована матриця Р.
Твердження: Для будь-якої матриці перестановок Р справедливо:
де Е - одинична матриця.
Деякі властивості блочних матриць (БМ),
що необхідно знати для виконання операцій над ними.
Блокові матриці однакового розміру і однакового розбиття на блоки називаються Конформними
Додавання БМ.
Нехай А(q*p) та В(q*p) конформнi матрицi:
Тоді їх сума:
формується так же, як у випадку додавання звичайних матриць
Множення блочних матриць
Для операції множення блочних матриць необхідно виконати умову їх узгодження.
Воно передбачає, що якщо: то
Припустимо, що всі блоки та такі, що число стовпців блока співпадає з числом строк блоку . Тоді множенням матриць А та В називається матриця
, де
Вставка** К
9.4. Існування базисних допустимих рішень (БДР).
Звичайно нам зручно записувати стандартну ЛП задачу у вигляді
(1) чи -тут: m – кількість обмежень та n кількість початкових змінних, А - матриця відомих параметрів.
Однак, якщо нам далі необхідно перетворити стандартну постановку в канонічну (через обмеження типу "="), то зручніше користуватись трохи штучними позначеннями (проте запис задачі буде еквівалентний тієму запису, що вище) з тим що-б отримана канонічна задача виглядала найбільш просто. Для цього стандартну ЛП запишемо так:
или (*)
Відмінності у запису:
1.Тут "n" вже не кількість змінних початкової задачі, а сума: = кількість початкових змінних (колишнє n) + кількість обмежень m. Для початкових змінних в цьому запису зарезервовані номери індексів від m + 1 до n: xm + 1, xm + 2, ..., xn - див (*). Інших х-ів в цьому записі поки немає (вони зарезервовані для переходу у канонічну форму)
2. Матрицю параметрів позначили тут через А *, щоб зарезервувати позначення матриці параметрам А для канонічного виду.
Приведемо далі систему (*) до канонічного вигляду ввівши додаткові змінні
x1,x2,...,x m : Ax = b (**)
де система (**) в розгорнутому вигляді має вигляд чи точніше
(**)
Звертаю увагу, тепер у канонічному вигляді будемо завжди мати !! mобм>(m-n)змінних
Прийнято називати початкові змінні xm+1,xm+2,...,xn - сильними, а додаткові
x1,x2,...,xm - слабими.
Існують різні визначення базисного рішення. Найбільш просте:
Достарыңызбен бөлісу: |
