Метод штучних базисних матриць

Метод штучних базисних матриць

A method of artificial basis matrices for the analysis and solution of the systems of linear algebraic equations and inequalities is proposed.

Збережено в:
Бібліографічні деталі
Дата:2007
Автори: Кудін, В.І., Ляшко, С.І., Хрітоненко, Н.М., Яценко, Ю.П.
Формат: Стаття
Мова:Ukrainian
Опубліковано: Видавничий дім "Академперіодика" НАН України 2007
Теми:
Інформатика та кібернетика
Онлайн доступ:https://nasplib.isofts.kiev.ua/handle/123456789/3127
Теги: Додати тег
Немає тегів, Будьте першим, хто поставить тег для цього запису!
Назва журналу:Digital Library of Periodicals of National Academy of Sciences of Ukraine
Цитувати:Метод штучних базисних матриць / В.І. Кудін, С.І. Ляшко, Н.М. Хрітоненко, Ю.П. Яценко // Доп. НАН України. — 2007. — № 9. — С. 30-34. — Бібліогр.: 2 назв. — укp.

Репозитарії

Digital Library of Periodicals of National Academy of Sciences of Ukraine
id nasplib_isofts_kiev_ua-123456789-3127
record_format dspace
spelling Кудін, В.І.
Ляшко, С.І.
Хрітоненко, Н.М.
Яценко, Ю.П.
2009-06-30T12:46:55Z
2009-06-30T12:46:55Z
2007
Метод штучних базисних матриць / В.І. Кудін, С.І. Ляшко, Н.М. Хрітоненко, Ю.П. Яценко // Доп. НАН України. — 2007. — № 9. — С. 30-34. — Бібліогр.: 2 назв. — укp.
1025-6415
https://nasplib.isofts.kiev.ua/handle/123456789/3127
519.852:519.876
A method of artificial basis matrices for the analysis and solution of the systems of linear algebraic equations and inequalities is proposed.
uk
Видавничий дім "Академперіодика" НАН України
Інформатика та кібернетика
Метод штучних базисних матриць
Article
published earlier
institution Digital Library of Periodicals of National Academy of Sciences of Ukraine
collection DSpace DC
title Метод штучних базисних матриць
spellingShingle Метод штучних базисних матриць
Кудін, В.І.
Ляшко, С.І.
Хрітоненко, Н.М.
Яценко, Ю.П.
Інформатика та кібернетика
title_short Метод штучних базисних матриць
title_full Метод штучних базисних матриць
title_fullStr Метод штучних базисних матриць
title_full_unstemmed Метод штучних базисних матриць
title_sort метод штучних базисних матриць
author Кудін, В.І.
Ляшко, С.І.
Хрітоненко, Н.М.
Яценко, Ю.П.
author_facet Кудін, В.І.
Ляшко, С.І.
Хрітоненко, Н.М.
Яценко, Ю.П.
topic Інформатика та кібернетика
topic_facet Інформатика та кібернетика
publishDate 2007
language Ukrainian
publisher Видавничий дім "Академперіодика" НАН України
format Article
description A method of artificial basis matrices for the analysis and solution of the systems of linear algebraic equations and inequalities is proposed.
issn 1025-6415
url https://nasplib.isofts.kiev.ua/handle/123456789/3127
citation_txt Метод штучних базисних матриць / В.І. Кудін, С.І. Ляшко, Н.М. Хрітоненко, Ю.П. Яценко // Доп. НАН України. — 2007. — № 9. — С. 30-34. — Бібліогр.: 2 назв. — укp.
work_keys_str_mv AT kudínví metodštučnihbazisnihmatricʹ
AT lâškosí metodštučnihbazisnihmatricʹ
AT hrítonenkonm metodštučnihbazisnihmatricʹ
AT âcenkoûp metodštučnihbazisnihmatricʹ
first_indexed 2025-11-26T14:55:57Z
last_indexed 2025-11-26T14:55:57Z
_version_ 1850625260793102336
fulltext оповiдi НАЦIОНАЛЬНОЇ АКАДЕМIЇ НАУК УКРАЇНИ 9 • 2007 IНФОРМАТИКА ТА КIБЕРНЕТИКА УДК 519.852:519.876 © 2007 В. I. Кудiн, член-кореспондент НАН України С. I. Ляшко, Н.М. Хрiтоненко, Ю. П. Яценко Метод штучних базисних матриць A method of artificial basis matrices for the analysis and solution of the systems of linear algebraic equations and inequalities is proposed. Для аналiзу властивостей лiнiйних систем рiвнянь (СЛАР) та нерiвностей (СЛАН) з квад- ратною матрицею обмежень розроблено метод штучних базисних матриць (МШБМ). На основi формул зв’язку елементiв методу в cуciднiх штучних розв’язках запропоновано iте- рацiйну процедуру знаходження рангу матрицi обмежень та розв’язку СЛАР. Встановлено умову єдиностi розв’язкiв СЛАР та формулу аналiтичного зображення загальних розв’язкiв СЛАН з рiзним типом обмежень у випадку невиродженостi матрицi обмежень. Постановка задачi аналiзу СЛАР та СЛАH. Введемо в розгляд СЛАР вигляду AuT = C, (1) де A — квадратна матриця розмiрностi (m × m), та допомiжну СЛАР вигляду IuT = K, (2) в якiй I — одинична матриця розмiрностi (m×m) з вiдомим ров’язком та оберненою матри- цею. Вектори обмежень C = (c1, c2, . . . , cm)T та K = (1, 1, . . . , 1) ︸ ︷︷ ︸ m T — розмiрностi m. Введемо вiдповiдно системi (1) змiною знаку “=” на “6” СЛАН AuT 6 C. (3) При наявностi цiльової функцiї вигляду maxBuT (4) модель набуде вигляду задачi лiнiйного програмування (3), (4), де C = (c1, c2, . . . , cm)T , u = (u1, u2, . . . , um), aj = (aj1, aj2, . . . , ajm), j = 1,m, — рядки матрицi A; T — знак транс- понування. Основою МШБМ є iдея порядкової базисної матрицi. 30 ISSN 1025-6415 Reports of the National Academy of Sciences of Ukraine, 2007, №9 Означення 1. Матрицю Aб, складену iз m лiнiйно незалежних рядкiв (i1, i2, . . . , im) обмежень (1), будемо називати штучною базисною, а розв’язок uo вiдповiдної їй системи рiвнянь Aбu T = C0, де C0 = (ci1 , ci2 , . . . , cim)T , — штучним базисним. Двi базиснi матрицi з вiдмiнним одним рядком називатимемо сумiжними. Базиснi матрицi в ходi iтерацiй послiдовно змiнюються вводом — виводом iз неї ряд- кiв-нормалей обмежень задачi. Нехай eij та βij — елементи матрицi A−1 б , оберненої до Aб та Aб; u0 = (u01, u02, . . . , uom) — базисний розв’язок; αr = (αr1, αr2, . . . , αrm) — вектор розвинення нормалi обмеження aru T 6 6 cr за рядками базисної матрицi Aб, α0 = (α01, α02, . . . , α0m) — вектор розвинення векто- ра-нормалi цiльової функцiї (4) за рядками базисної матрицi Aб; △r = aru T 0 − cr — нев’язка r-го обмеження (1). Всi введенi елементи в сумiжнiй базиснiй матрицi Aб (вiдмiннiй одним рядком вiд Aб) будемо позначати рискою зверху. Введемо в розгляд ai1, ai2, . . . , aim — нормалi обмежень, aju T 6 cj , j ∈ Jб, де Jб = = {i1, i2, . . . , im} — iндекси обмежень, нормалi яких утворюють базисну матрицю Aб; al — вектор-нормалi обмеження alu T 6 cl, αl = (αl1, αl2, . . . , αlm) — вектор розвинення вектора al за рядками базисної матрицi Aб. Вiдомо [1, 2], що необхiдною i достатньою умовою лiнiйної незалежностi cистеми векторiв ai1 , ai2, . . . , aik−1 , al, aik+1 , . . ., aim при замiнi вектора aik , що утворює k-й рядок в базиснiй матрицi Aб вектором al, є виконання умови αlk 6= 0. Теорема 1. Мiж коефiцiєнтами розвинення нормалей обмежень (3), цiльової функ- цiї (4) за рядками штучної базисної матрицi, елементами обернених матриць, базисними розв’язками, нев’язками обмежень (3) та значеннями цiльової функцiї в двох сумiжних базисних матрицях мають мiсце такi спiввiдношення: αrk = αrk αlk , αri = αri − αrk αlk αli, r = 0, n, i = 1,m, i 6= k, (5) erk = erk αlk , eri = eri − erk αlk αli, r = 1,m, i = 1,m, i 6= k, (6) u0j = u0j − ejk αlk ∆l, j = 1,m, (7) ∆k = − ∆l αlk , ∆r = ∆r − αrk αlk ∆l, r = 1, n, r 6= k, (8) BuT 0 = BuT 0 − α0k αlk ∆l, (9) причому умовою невиродженостi базисної матрицi при замiнi вектором нормаллю al обме- ження alu T 6 cl k-го рядка базисної матрицi Aб є виконання αlk 6= 0. Доведення. Виконання (5) випливає з таких тотожних перетворень: arj = m∑ i=1 αriβij = m∑ i=1 i6=k αriβij + αrkalj . Оскiльки alj = m∑ i=1 αliβij , то пiсля пiдстановки цього спiввiдношення отримаємо: ISSN 1025-6415 Доповiдi Нацiональної академiї наук України, 2007, №9 31 m∑ i=1 i6=k αriβij + αrkαij = m∑ i=1 i6=k αriβij + αrk m∑ i=1 αliβij = m∑ i=1 αriβij . Порiвнявши коефiцiєнти злiва i справа для кожного i, де i = 1,m, встановлюємо, що αri + αrkαli = αri, i 6= k; αrkαlk = αrk, i = k, тобто справедливiсть (5), оскiльки αrk = αrk αlk , αri = αri − αrk αlk αli, r = 0, n, i = 1,m, i 6= k. Аналогiчно одержуємо формули (6), враховуючи, що для транспонованих та прямих квадратних матриць справедливо A−1 б · Aб = A−1 б · Aб, тобто m∑ i=1 eriβij = m∑ i=1,i6=k eriβij + erkalj = m∑ i=1 i6=k eriβij + erk m∑ i=1 αliβij = m∑ i=1 eriβij , erk = erk αlk , eri = eri − erk αlk αli, r = 1,m, i = 1,m, i 6= k. Iз формули (6) та наступних перетворень випливає спiввiдношення (7), що зв’язує ба- зиснi розв’язки в двох сумiжних базисних матрицях: u0j = m∑ i=1 ejic 0 i = m∑ i=1 i6=k eijc 0 i + ejkc 0 k = m∑ i=1 i6=k ( eji − ejk αlk αli ) c0 i + ejk αlk cl = = m∑ i=1 ejic 0 i − ejkc 0 k − ejk αlk m∑ i=1 i6=k αlic 0 i + ejk αlk cl = = u0j − ejk αlk αlk c0 k − ejk αlk ( m∑ i=1,i6=k αlic 0 i − cl ) = u0j − ejk αlk ( m∑ i=1 αlic 0 i − cl ) = = u0j − ejk αlk ( m∑ j=1 alj m∑ i=1 ejic 0 i − cl ) = u0j − ejk αlk ( m∑ j=1 alju0j − cl ) = u0j − ejk αlk ∆l, тобто u0j = u0j − ejk αlk ∆l, j = 1,m. При доведеннi (8) використаємо (7). Отримаємо, враховуючи, що ∆k = 0 i αkk = 1 при k /∈ Jб, ∆k = −∆l/αlk, а для решти нев’язок ∆r = m∑ i=1 ariu0i − cr = m∑ i=1 ari ( u0i − eik αlk ∆l ) − cr = ∆r − ∆l αlk m∑ i=1 αrieik = = ∆r − ∆l αlk m∑ i=1 αrieik = ∆r − αrk αlk ∆l, ∆r = ∆r − αrk αlk ∆l, r = 1, n, r 6= k. 32 ISSN 1025-6415 Reports of the National Academy of Sciences of Ukraine, 2007, №9 Аналогiчно можна отримати спiввiдношення BuT 0 = BuT 0 − α0k αlk ∆l, що завершує доведення теореми. Наслiдок 1. Для iснування єдиного розв’язку (1) необхiдно i достатньо, щоб α (i) lk 6= 0, i = 1,m, де α (i) lk — ведучi елементи симплексної iтерацiї МШБМ по замiщенню рядкiв базисної матрицi (2) нормалями обмежень (1). На основi (5)–(9) формується схема визначення рангу системи (1) та розв’язання систе- ми рiвнянь послiдовними змiнами базисних матриць та вiдповiдних штучних розв’язкiв iз збереженням умови невиродженостi сумiжних базисних матриць. Початковi розв’язок u0 та всi елементи методу будуються на основi вiдомих властивостей системи (2). Нижче наведено основнi стадiї алгоритмiчної схеми знаходження величини рангу, обер- неної базисної матрицi та розв’язку системи (1). Алгоритм. Крок 1. Проводимо симплекснi iтерацiї по замiщенню рядкiв базисної матрицi систе- ми (2) нормалями обмежень системи (1), згiдно з спiвiдношеннями (5)–(9) та виконанням умов невиродженостi αl(r)k(r) 6= 0, r — номер iтерацiї. Знаходимо вiдповiднi елементи методу: розвинення за рядками базисних матриць обме- жень (2), обернену базисну матрицю, штучнi базиснi розв’язки u (k) 0 , де k — номер iтерацiї. Крок 2. Перевiряємо кiлькiсть iтерацiй r замiщення рядкiв допомiжної системи рядками основної системи, для яких виконується умова невиродженостi, тобто αlk 6= 0. Число таких iтерацiй визначає ранг основної системи. Крок 3. Якщо кiлькiсть iтерацiй, для яких α (i) lk 6= 0, дорiвнює m, то переходимо на наступний крок. У противному разi — на передостаннiй крок. Крок 4. Знаходимо єдиний розв’язок, згiдно з спiввiдношенням A−1 б c0 = u0 (або згiдно з формулою (7)). Крок 5. Виконання умови r < m означає, що для СЛАР (1) не виконується умова єдиностi розв’язку. Модель потребує подальшого аналiзу розв’язностi задачi. Останнiй крок. Формування вихiдної iнформацiї за результатами аналiзу (1). Виявляється, що побудова загального розв’язку СЛАН (3) грунтується на властивостях розв’язкiв СЛАР (1). Наслiдок 2. Загальний розв’язок СЛАН (3) рангу m є конус K з вiстрям u0 — розв’я- зок СЛАР (1) та твiрними ei = (A−1 б )i, i = 1,m, що наводиться спiввiдношенням K = { u/u = u0 − m∑ i=1 λiei } , де λi > 0. Особливостi дослiдження СЛАР на основi МШБМ. МШБМ є релаксацiйним, оскiльки на кожному кроцi в обчислення включається одне обмеження; обернена матриця та розв’язок (2) є початковими i заданими; максимальна кiлькiсть iтерацiй по знаходженню ISSN 1025-6415 Доповiдi Нацiональної академiї наук України, 2007, №9 33 рангу системи (при невиродженостi) обмежена числом m; iдеологiя симплексних перетво- рень (5)–(9) може бути застосована для аналiзу виродженостi матрицi обмежень, рангу та розв’язку СЛАР (1) при збуреннi елементiв. Таким чином, застосування симплексної iдеологiї на основi МШБМ дає змогу: дослiджу- вати властивостi розв’язкiв СЛАР та СЛАН зi змiнними та функцiональними елементами; проводити построзрахунковий аналiз властивостей системи при змiнi значень окремих еле- ментiв та її компонент; використовувати розв’язок початкової системи при аналiзi збуреної системи; моделювати механiзм постадiйного перетворення виродженої матрицi обмежень в невироджену направленою корекцiєю елементiв; знаходити розв’язок квадратної системи рiвнянь та нерiвностей за фiксовану кiлькiсть крокiв; застосувати схему аналiзу для задач, що передбачають багатокроковiсть або багаторазовiсть розрахункiв на моделях з незначни- ми змiнами в компонентах моделi. Для органiзацiї ефективної роботи алгоритмiчних схем, розроблених на основi МШБМ, необхiдно: включити контроль в ходi обчислень верхнiх значень числа обумовленостi для сумiжних базисних матриць, розробити варiанти алгорит- мiчних схем з направленим вибором ведучого елемента для досягнення числової стiйкостi методу; проводити нормування елементiв моделi в межах [−0,5, 0,5], що перешкоджатиме росту значень елементiв методу. Структурнi властивостi МШБМ дають можливiсть врахувати наведенi вище пункти як доповнення до алгоритмiчного та програмного забезпечення. Робота пiдтримана програмою ICS NATO вiд 18.04.2006 в рамках проекту “Оптимальна за- мiна iнформацiйних технологiй i стiйкий розвиток (в Казахстанi, Українi та США)”, грант НАТО CLG 982209. 1. Волкович В.Л., Войналович В.М., Кудин В.И. Релаксационная схема строчного симплекс-метода // Автоматика. – 1987. – № 4. – С. 79–86. 2. Кудiн В. I. Про побудову загальних розв’язкiв одного класу систем лiнiйних нерiвностей // Вiсн. Київ. ун-ту. Сер. фiз.-мат. науки. Вип. 2. – 2005. – С. 309–313. Надiйшло до редакцiї 14.02.2007Київський нацiональний унiверситет iм. Тараса Шевченка 34 ISSN 1025-6415 Reports of the National Academy of Sciences of Ukraine, 2007, №9

Схожі ресурси