WWW.DISSERS.RU

БЕСПЛАТНАЯ ЭЛЕКТРОННАЯ БИБЛИОТЕКА

   Добро пожаловать!

Pages:     | 1 |   ...   | 53 | 54 || 56 | 57 |   ...   | 82 |

Conclusion Now we have definition of AI and at least one program (TD5) which satisfies it (with assumption 1). The first question is: Does this definition satisfy our intuitive idea that AI is a program which is more intelligent than a human being. Yes, but for some values of the parameters educational time and level of intelligence. In this paper the educational time was fixed on 100 games each of them no longer than 1000 steps (educational time is equal to the life length because we learn all our life). The level of intelligence here was fixed on 20. Which means that XII-th International Conference "Knowledge - Dialogue - Solution" we assume that we can find a model of the world which is TM_W with size not bigger than 20. We cannot say what is the exact level of intelligence of the human being.

The second question is: Is TD5 which satisfies the definition the program which we are looking for. The answer is definitely no. We are looking for a program which can work in real time.

TD5 is like the perfect chess playing program. All other chess playing programs play worse than the prefect one.

Anyway, the perfect chess program is useless because it cannot play in real time. In the same way TD5 is perfect but useless. We need AI which is not perfect but which can play in real time.

Bibliography [1] Dobrev D. D. A Definition of Artificial Intelligence. In: Mathematica Balkanica, New Series, Vol. 19, 2005, Fasc. 1-2, pp.67-74.

[2] Dobrev D. D. AI - What is this. In: PC Magazine - Bulgaria, November'2000, pp.12-13 (in Bulgarian, also in [4] in English).

[3] Dobrev D. D. AI - How does it cope in an arbitrary world. In: PC Magazine - Bulgaria, February'2001, pp.12-13 (in Bulgarian, also in [4] in English).

[4] Dobrev D. D. AI Project, http://www.dobrev.com/AI [5] Kolmogorov A. N. and Uspensky V. A. Algorithms and randomness. - SIAM J. Theory of Probability and Its Applications, vol. 32 (1987), pp.389-412.

[6] Turing, A. M. On Computable Numbers, with an Application to the Entscheidungsproblem. Proceedings of the London Mathematical Society, Series 2, 42, 1936-37, pp.230-265.

Author’s Information Dimiter Dobrev - Institute of Mathematics and Informatics, BAS, Acad.G.Bonthev St., bl.8, Sofia-1113, Bulgaria;

P.O.Box: 1274, Sofia-1000, Bulgaria; e-mail: d@dobrev.com СИСТЕМНЫЙ АНАЛИЗ МОДЕЛИ ЛЕОНТЬЕВА ПРИ НЕЧЁТКО ЗАДАННЫХ ПАРАМЕТРАХ МЕТОДОМ БАЗИСНЫХ МАТРИЦ Владимир Кудин, Григорий Кудин Аннотация. Предложено применение метода базисных матриц для анализа модели Леонтьева (МЛ).

МЛ можно интерпретировать как задачу прогноза затрат-выпуска продукции на основе известной статистической информации о значениях элементов технологической матрицы при нечётко заданном векторе ограничений и границах переменных. Вектор правых частей ограничений МЛ может испытывать изменения и в таком случае получается динамический аналог задачи. Существенным осложнением МЛ является включение ограничений на переменные и вектор целевой функции.

Ключевые слова: модель Леонтьева, количественный и качественный анализ, нечёткое множество, базисная матрица, функция принадлежности.

Введение Модель Леонтьева (МЛ) была сформулирована, как задача прогноза затрат-выпуска продукции на основе известной статистической информации о значениях элементов технологической матрицы при нечётко заданном векторе ограничений и границах переменных [Леонтьев, 1972 ]. Нечёткость значений параметров модели предопределяет наличие в контуре принятия решения экспертов (ЛПР), которые призваны качественно определить структуру модели, указать механизм устранения неопределённостей и разногласий при ее формировании [Гасс., 1961].

238 Mathematical Foundations of AI Существенным осложнением МЛ есть включение ограничений границ на переменные [Орловский, 1981].

При исследованиях, наряду с классической МЛ типа системы линейных алгебраических уравнений с квадратной невыродженной матрицей ограничений (СЛАР), рассматривается и более обобщённая модель, которая математически интерпретируется как система линейных алгебраических неравенств с соответствующей матрицей ограничений (СЛАН), а также и как задача линейного программирования (ЗЛП) [Волошин, 1993], [Войналович, 1987], [Войналович, 1988], [Кудин, 2002]. При построении МЛ, после проведения качественного наполнения и анализа модели [Орловский, 1981] ), нужно провести количественный анализ непротиворечивости структурных элементов [Волошин,1993], [Войналович, 1987], [Войналович, 1988], [Кудин, 2002], что математически включает следующие стадии:

• проверки невырожденности матрицы ограничений и установление ранга матрицы системы;

• направленной коррекции ранга матрицы ограничений изменением отдельных её элементов;

• установление совместных зависимостей МЛ и ограничений на переменные – разрешимость (неразрешимость);

• анализ статуса ограничений МЛ для многогранного множества ограничений на переменные, проведения, при необходимости, направленных изменений;

• нахождение решений при разрешимости за совместностью;

• установление свойства единственности или неединственности решений.

Постановка задачи Пусть имеем МЛ вида u = AT uT + yT, (1) где AT = aij i=1,m невырожденная квадратная матрица размерности (m m), { } j =1,m u = (u1,u2,...,um ) - вектор переменных, для которого выполняется: u U, U = U, 0,[ ] m m (i) (-) ( U = / =,U+) ], 1 x (u), u [Ui(-),Ui(+) ] (-,+), u U [U i i=1 i=YT = (y1, y2,..., ym ) - вектор ограничений со свойством Y Y, Y = Y, 0,[ ] m m (i) (-) Y = y / =,Y(+) ], 1 x (y), y [Yi(-),Yi(+) ] (-,+), Y [Y i i=1 i=x (u), y (y), i I - заданные кусочно-линейные функции принадлежности [Орловский, 1981] с i i областью значений 0,1, областью определения (-, +), i I = (1, 2,.......m) - индексы строк и [ ] столбцов матрицы ограничений, Т - знак транспонирования. Модель (1) исследуется в эвклидовом пространстве Em. При наличии в контуре принятия решения экспертов (ЛПР) фаза качественного анализа (1) определяет следующую задачу количественного анализа при указанных уровнях ( p), p = 1, 2,....p { } последовательности задач (1) при дополнительных ограничениях вида mm m m (i) (-) ( (i) (-) U { =,Ui(+) ], p P}, Y =,Yi(+) ], p P (2) Uз [Ui( p) ( p) Yз [Yi( p) p) i=1 i- i=1 i-Предложена схема применения методологии последовательного анализа [Волошин, 1987] и метода базисных матриц (МБМ) [Кудин, 2002] для проведения количественного анализа разрешимости за совместимостью и свойств ограничений (активности - пассивности) задачи (1)-(2) в зависимости от уточнения значений параметров на стадии качественного анализа модели.

XII-th International Conference "Knowledge - Dialogue - Solution" Основные положения метода базисных матриц (МБМ) T T T Модель вида (1) можно преобразовать к эквивалентной СЛАР вида A u = C.

Введем соответственно системе (1), изменением знака (= на ), СЛАН ATuT CT. (3) Модели СЛАН (3) и СЛАР типа (1) могут исследоваться при наличии целевой функций вида max Bu, (4) uRm как задача анализа модели линейного программирования, где в (1) - (3) B = (b1,b2,...,bm ), CT = (c1,c2,..,cn ), uT = (u1,u2,..,um ), aj = (aj1, aj 2,..., ajm ), j = (1, 2,.., n) - строки матрицы АТ.

Предметом исследования будет:

• установление ранга системы (1) и разрешимости задачи (1), (2);

• анализ статуса ограничений (1) для многогранного множества (2);

• нахождение решения (1 ), (2) при разрешимости за совместимостью;

• установление условий разрешимости (неразрешимости) за совместимостью системы (1)-(2), • (2) - (3);

• установление условий существования, единственности и неединственности решения СЛАН (3);

• исследование свойств, построенных на основании (1), (2), оптимизацонных задач (3),(4).

В предлагаемом МБМ используются строчные базисные матрицы [Войналович, 1987], [Войналович, 1988], [Кудін, 2002]. Базисные матрицы в ходе итераций решения задачи последовательно изменяются вводомвыводом из нее строк-нормалей ограничений.

В общем случае количество ограничений превышает количество переменных вида (4) при ограничениях:

u Rm. (5) ATuT CT, u Rm, Определение 1. Подматрицу Aб матрицы AT, составленную из m линейно независимых нормалей ограничений (5), будем называть базисной, а решение соответствующей ей системы уравнений A uT = Cб базисным. Две базисные матрицы отличающимися одной строкой будем называть сопредельными.

-Пусть элементы базисной подматрицы Aб, erі - элементы матрицы Аб,, i, j =1,2,...,m, іj -обратной к Аб ; ek = (Aб )k.- столбец обратной матрицы. Решение u0 = (u01,u02,...,u0m ) системы уравнений, где c0 - подвектор С, компоненты которого состоят из правых частей ограничений A uT = cб (5), нормали которых образуют базисную матрицу Аб ; r = (r1,r 2,...,rm ) - вектор разложения нормали ограничения aru1 cr за строками базисной матрицы Aб, 0 = (01,02,...,0m ) вектор T разложения нормали целевой функции (4) за строками базисной матрицы Aб, r = aru0 - cr - невязка r-го ограничения (5) в вершине u0 ;

Jб, JН, J = Jб JН - множества индексов базисных и небазисных ограничений (5). Установим формулы связи базисного решения, коэффициентов разложения нормалей ограничений и целевой функции (4), коэффициентов обратной матрицы, невязок ограничений и значений целевой функции при переходе к базисной матрице A, которая образуется из матрицы А заменой ее б б строки ak на al, которая не входит в базисную матрицу Aб. В новой базисной матрице А введённые б величины будем называть элементами или компонентами метода базисных матриц и будем обозначать черточкой сверху, т.е., r k ri,, e,. Вершины (0-грани), ребра ( 1-грани ), к-грани, іj нормали, гиперплоскости и полупространства, многообразия будем называть структурными элементами модели.

При нахождении формул и основных соотношений между элементами метода при переходе от одной базисной матрицы к следующей считаем, что ai1, ai 2,..., aim - нормали ограничений, 240 Mathematical Foundations of AI ajuT cj, j Jб, Jб = {i1,i2,...,im} - индексы ограничений, нормали которых образовывают строки где базисной матрицы Aб, аl - нормаль ограничения au cl, l = (l1,l 2,...,lm ) - коэффициенты l разложения вектора al за строками базисной матрицы Aб,.

Лемма 1. (Критерий линейной независимости системы векторов). Необходимым и достаточным условием ai, ai,..., ai, al, ai,..., ai линейной независимости cистемы векторов, образованной заменой вектора 1 2 k-1 k+1 m ai, который занимает k -ю строку в базисной матрице Aб, вектором а, есть выполнение условия l k lk 0.

Теорема 1. (О cвязи между смежными базисными матрицами). Между коэффициентами разложения нормалей ограничений (5) и целевой функции (4) за строками базисной матрицы, элементами обратных матриц, базисными решениями, невязками ограничений (5) и значениями целевой функции для двух смежных базисных матриц имеют место соотношения rk rk = rk =, ri rі - lі, r = 0, n; i = 1, m; і k;

(6) lk lk erk erk і k;

e =, e = erі - lі, r = 1, m; i = 1, m;

rk ri (7) lk lk ejk u = u0 j - l, j = 1, m, (8) 0 j 1k l rk = -, = r - l, r = 1, n; r k ;

k r (9) lk lk T 0k T Bu = Bu0 - l, (10) lk причем условием того, что матрица остаётся базисной при замещении вектором нормали al k -ой строки базисной матрицы Aб, есть выполнение условия lk 0, условием допустимости опорного базисного решения есть lk < 0, роста значений целевой функции 0k <.

Доказательство леммы 1 и теоремы 1 основывается на теоретических положениях, изложенных в [Войналович, 1987], [Войналович, 1988], [Кудин, 2002].

С учётом соотношений (6)-(10) будет строиться схема типа метода поиска не только оптимального решения последовательными переходами согласно допустимым базисным вершинами, а и проведение анализа свойств линейных моделей - метод базисных матриц.

T Определение 2. Допустимое базисное решение u0 оптимальное, если Bu0 BuT для всех u, которые удовлетворяют (5).

Теорема 2. (Критерий оптимальности решения). Для оптимальности базисного решения u0 необходимо и достаточно неотрицательности коэффициентов разложения вектора нормали целевой функции (4) по строкам базисной матрицы, т.е. ok 0 для всех k = 1, m.

A б Справедливость критерия оптимальности вытекает из формулы (10) теоремы 1.

Теорема 3. (О неограниченности значений целевой функции). Если существует индекс k такой, что 0k < 0 и rk 0 для всех небазисных r, то целевая функция задачи приобретает неограниченные значения на множестве допустимых решений.

Полное доказательство теоремы приведено в [Войналович, 1987].

Теорема 4. Для существования единственного решения (1) необходимо и достаточно, чтобы ( ( lki) 0, i = 1, m, где lki) ведущие элементы симплексной итерации МБМ по замещению строк базисной матрицы (2) нормалями ограничений (1).

XII-th International Conference "Knowledge - Dialogue - Solution" ---( Следствие 1. Матрица А основной системы (1) невырожденная, если lki) 0, i = 1, m.

Следствие 2. Ранг системы (1) определяется количеством корректных замещений строк матрицы ограничений вспомогательной системы векторами нормалями (1), согласно формулам (6)-(10).

Справедливость теоремы 2 и следствий 1,2 является непосредственным следствием леммы 1.

Теорема 5. Оптимизационная задача (3),(4) с квадратной невырожденной матрицей ограничений имеет ---единственное решение тогда и только тогда, если 0i > 0, i = 1, m.

Теорема 6. Необходимым и достаточным условием неединственности решения задачи (3),(4) есть i таких, что 0i = 0, причём множество решений имеет ребра неограниченности.

Пусть для a ограничения auT cl относительно, выполняется lk = 0, а для возмущения l A l б - '' -(al + al' )uT cl + cl', = l + l l l = (l +l' ) = (al + al' )Aб.

Теорема 7. Необходимым условием невирожденности новой Аб, образованной замещением нормали al, которая занимает k - ю строку в базисной матрице нормалью (€l + €l ) является выполнения условия i eik 0, где eik элемент А-1 такой, что ' 0. Решение будет определяться соотношением ‡ li - ejk - u = uoj -, причем если = 0, то u = uoj, j = 1, m.

oj l l oj lk Теорема 7 дает условия направленного восстановления свойства невырожденности базисной матрицы (1).

Следствие 3. Если ведущий элемент симплексной итерации lk 0, то при возмущении, сохраняющего ' невырожденность, должно выполняться lk +lk.

T Пусть U = u / a c, jJ, U = {u / a uT c, jJ, J r } } { ju j r j j Определение 3. Ограничение aruT cr пассивное, если U = Ur.

Определение 4. Ограничение aruT cr порождующее неразрешимость за несовместностью, если U =, Ur.

Pages:     | 1 |   ...   | 53 | 54 || 56 | 57 |   ...   | 82 |



© 2011 www.dissers.ru - «Бесплатная электронная библиотека»

Материалы этого сайта размещены для ознакомления, все права принадлежат их авторам.
Если Вы не согласны с тем, что Ваш материал размещён на этом сайте, пожалуйста, напишите нам, мы в течении 1-2 рабочих дней удалим его.