автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.18, диссертация на тему:Синтез методов оптимизации и дискриминантного анализа в математических моделях экономики

На правах рукописи

С

СОКОЛИНСКАЯ Ирина Михайловна ^^

УДК 519.6

СИНТЕЗ МЕТОДОВ ОПТИМИЗАЦИИ И ДИСКРИМИНАНТНОГО АНАЛИЗА В МАТЕМАТИЧЕСКИХ МОДЕЛЯХ ЭКОНОМИКИ

05.13.18 - математическое моделирование, численные методы и комплексы программ

Автореферат диссертации на соискание ученой степени кандидата физико-математических наук

Челябинск - 2006

Работа выполнена на кафедре вычислительной математики Челябинского государственного университета.

Научный руководитель: доктор физико-математических наук, профессор

МАЗУРОВ Владимир Данилович.

Официальные оппоненты: академик РАН, доктор физико-математических

наук, профессор ЕРЕМИН Иван Иванович;

Ведущая организация: Вычислительный центр им. А.А. Дородницына РАН

Защита состоится 19 октября 2006 г. в 13 часов

на заседании диссертационного совета Д 212.296.02 при Челябинском государственном университете по адресу: 454021, Челябинск, ул. Бр. Кашириных, 129.

С диссертацией можно ознакомиться в библиотеке Челябинского государственного университета

кандидат физико-математических наук, доцент ЗЫКИНА Анна Владимировна.

Автореферат разослан 29 августа 2006 г.

Ученый секретарь диссертационного совета, доктор физ.-мат. наук, профессор

Общая характеристика работы

Актуальность темы. В практике экономико-математического моделирования часто встречаются задачи, при решении которых приходится учитывать большое число взаимосвязанных факторов, включая плохо формализуемые1. Процесс решения плохо формализуемой задачи включает в себя преобразование ее формулировки путем уточнений и упрощений. В результате этого процесса мы получаем формализованную задачу, имеющую некоторое отношение к исходной постановке задачи. Во многих случаях удается построить формализованную задачу в виде задачи линейного программирования. Однако решение формализованной задачи может сколь угодно сильно отличаться от решения исходной задачи в силу наличия неформализованных ограничений.

Помимо формальных методов и моделей для решения плохо формализуемой задачи используются средства неформального анализа, включающие в себя суждения экспертов для учета так называемых «внемодельных» факторов. При этом человеческий компонент в процессе экспертизы может постепенно, с помощью обучения, заменяться машинным компонентом путем использования экспертных систем или нейросетевых программ. Однако при решении задач линейного программирования большой размерности эти подходы могут оказаться неэффективными, если их применять для решения всей задачи в целом. Это объясняется тем, что трудно адекватно настроить (обучить) экспертную систему или нейронную сеть в случае, когда система ограничений содержит тысячи линейных неравенств и десятки тысяч переменных. В таких ситуациях перспективным является подход, основанный на сочетании методов линейной оптимизации с процедурами экспертного оценивания. Алгоритм решения задачи в этом случае строится как итерационный процесс, в ходе которого шаг за шагом происходит уточнение ограничений, относящихся к неформализованной части задачи. Приближенные решения исходной задачи, получаемые в ходе итерационного процесса, формируют множество образцов, квалифицируемых экспертом. Применяя к этому множеству образцов процедуру дискриминантного анализа, мы получаем разделяющую поверхность, аппроксимирующую неформализованные ограничения. В соответствии с этим актуальной является задача разработки, анализа и реализации на ЭВМ алгоритмов решения задач линейного программирования с неформализованными ограничениями путем синтеза методов дискриминантного анализа и линейной оптимизации.

Цель и задачи исследования. Цель данной работы состояла'в разработке и исследовании методов и алгоритмов решения задач линейного программирования с неформализованными ограничениями и их реализации в виде программного комплекса. Для достижения этой цели необходимо было решить следующие задачи:

1. Построить математическую модель задачи линейного программирования с неформализованными ограничениями (ЛПНО) и описать общий

подход к ее решению.

1 Еремин ИИ., Мазуров Вп. Д. Вопросы оптимизации и распознавания образов. -Свердловск: Сред.-Урал. кн. изд-во, 1979.

2. На базе данного подхода разработать метод решения задачи ЛПНО, допускающий реализацию в виде алгоритма для ЭВМ, и исследовать сходимость этого метода.

3. На основе описанного метода разработать и исследовать алгоритм ЛП-ДА (Линейное Программирование — Дискриминантный Анализ), соединяющий алгоритмы линейного программирования с алгоритмами дискриминантного анализа.

4. Спроектировать и реализовать программный комплекс для решения задач ЛПНО, использующий предложенные методы и алгоритмы.

5. Провести вычислительные эксперименты для анализа эффективности предложенного подхода.

6. Разработать и реализовать параллельную версию алгоритма ЛП-ДА. Провести вычислительные эксперименты на кластерной системе для исследования ускорения и расширяемости параллельного алгоритма.

Методы исследования. В исследованиях, проводимых в диссертационной работе, используется аппарат теории математического программирования и распознавания образов, применяются методы дискриминантного анализа и линейной оптимизации.

Научная новизна работы заключается в следующем:

1) предложен метод решения задачи линейного программирования с неформализованными ограничениями, базирующийся на синтезе методов дискриминантного анализа и методов линейной оптимизации, и доказана сходимость генерируемой им итерационной последовательности к точному решению задачи ЛПНО;

2) предложен оригинальный метод осцилляций, позволяющий существенно ускорить сходимость последовательности приближений к точному решению задачи ЛПНО;

3) разработан новый алгоритм, соединяющий симплекс-метод и метод линейной коррекции, и предложена его параллельная версия;

4) выполнена реализация алгоритма решения задач ЛПНО в виде программного комплекса для персональных компьютеров и многопроцессорных систем на основе стандарта МР1-2.

Теоретическая ценность работы состоит в том, что в ней представлены доказательства теоремы об устойчивости задачи линейного программирования по неформализованным ограничениям и теоремы о сходимости метода, соединяющего дискриминантный анализ и рандомизацию с линейной оптимизацией. Практическая ценность работы заключается в том, что предложенный программный комплекс в сочетании с системами экспертного оценивания может быть использован для решения плохо формализуемых задач, возникающих в экономико-математическом моделировании.

Апробация работы. Основные положения диссертационной работы, разработанные модели, методы, алгоритмы и результаты вычислительных экспериментов докладывались автором на следующих международных и всероссийских научных конференциях:

- на Всероссийской научной конференции "Алгоритмический анализ неустойчивых задач" (2-6 февраля 2004 г., Екатеринбург);

- на Международной научной конференции "Системный Анализ и Информационные Технологии" САИТ-2005 (12-16 сентября 2005 г., Переел авль-Залесский);

- на III Всероссийской научной конференции "Проблемы оптимизации и экономические приложения" (Омск, 11-15 июля 2006 г.).

Публикации. Основные научные результаты диссертации опубликованы в 5 печатных работах, приведенных в конце автореферата. Статья [2] опубликована в научном журнале «Pattern Recognition and Image Analysis», включенном ВАК в перечень журналов, в которых должны быть опубликованы основные результаты диссертаций на соискание ученой степени доктора наук. В статье [2] Вл.Д. Мазурову принадлежит общая постановка задачи; И.М. Соколинской принадлежат формальное описание алгоритма £ порождения образцов, формулировки и доказательства всех теорем и лемм.

Структура и объем работы. Диссертация состоит из введения, четырех глав, заключения, библиографии и приложения, в кагором приводятся основные обозначения, используемые в диссертационной работе. Объем диссертации составляет 92 страницы, объем библиографии — 77 наименований.

Содержание работы

Во введении приводится обоснование актуальности темы, формулируются цели работы и кратко излагается содержание диссертации.

Первая глава, «Синтез дискриминантного анализа и линейной оптимизации», посвящена описанию и исследованию общего метода решения задач ЛПНО, сочетающего дискриминантный анализ, линейную оптимизацию и рандомизацию. Сначала рассматривается случай одного неформализованного ограничения, а затем показывается, как полученные результаты могут быть обобщены на случай произвольного количества ограничений.

Предположим сначала, что только одно ограничение не может быть формализовано. Данную ситуацию можно записать в виде следующей задачи линейного программирования с неформализованным ограничением (ЛПНО) в пространстве R":

тах{(с,х) | Ах < Ъ, ¡р(х) <0} (1)

Здесь неравенство ip(z) < 0 играет роль неформализованного ограничения в том смысле, что нам не известен вид функции v?. Будем предполагать, что <р принадлежит к классу аффинных функций. Предположим также, что задача (1) имеет единственное решение:

х = arg max {(с, ж) | Ах <Ь, <р{х) < 0}. Неформализованное ограничение <р(х) < 0 представляется двумя информационными ресурсами: экспертам и набором образцов. В качестве абстрактной модели эксперта введем функцию е(х) = sgn(y5(x)). С помощью

функции эксперта е мы можем для любого х е К" определить, удовлетворяет х неформализованному ограничению или нет, используя следующую систему правил:

е(х) = 1 ф(х) > О;

е(х) = О ф(х) = 0; (2)

е(х) = — 1 ф(х) < 0.

Набор образцов = {А, В} определяется путем задания пары конечных непересекающихся множеств А и В из пространства Ж", удовлетворяющих условиям

Ге(г) =1, \/х е А;

е(а) = -1, Ух е В. (3)

Применяя методы дискриминантного анализа, мы можем найти для множеств А и В разделяющую функцию ф 6 Ф (Ф - класс всех аффинных функций), удовлетворяющую условиям

ф{х) >0, геА;

' ф{х) <0, х е В

(существование ф следует из (2), (3) и предположения, что ф € Ф). В качестве приближенного решения задачи ЛПНО мы можем теперь взять решение (если оно существует) следующей задачи линейного программирования, называемой аплроксимационной (ЛПА):

х = а^шах{(с,х) | Ах < Ь, ф{х) < 0}.

Далее формулируется и доказывается теорема об устойчивости задачи линейного программирования по неформализованному ограничению:

Теорема 1. Задача ЛПНО (1) является устойчивой по ф.

Эта теорема играет важную роль при решении проблемы сходимости.

Далее описывается алгоритм получения новых образцов, служащий основой итерационного процесса. При этом используются следующие обозначения. О = {х | Ах < 6} — многогранник, определяемый формализованной частью задачи ЛПНО. Предполагается, что И — телесное множество (то есть £> содержит внутренние точки), и что £> ограничен. Перепишем задачу ЛПНО в виде

шах{(с,х) | х € Д ф(х) < 0}. (4)

Будем рассматривать случай, когда задача (4) имеет единственное решение: х ' а^тах{(с,х) | х € 2?; ф(х) < 0}.

Обозначим как ЛПФ задачу линейного программирования с формализованной частью:

тах{(с,х) | х е В}. (5)

Предполагаем, что задача (5) также имеет единственное решение:

х = arg max {(с, x) | x £ £>},

причем

X * X.

Пусть P = {x | <p(x) < 0} — множество значений, удовлетворяющих неформализованному ограничению ¡р{х) < 0. Так как ¡р является аффинной функцией, то Р представляет собой замкнутое полупространство. Допустимое множество значений задачи (4) будет иметь вид ДПР. Будем предполагать, что D С\ Р содержит внутренние точки. Определим: Н = {а; | ip(x) = 0} — гиперплоскость, определяемая неформализованным ограничением.

Алгоритм £. Пусть заданы конечные множества А0 и В0, такие, что А0 С D \ Р, С D П (Р \ П). Множества А0 и В0 задают начальный набор образцов . Будем предполагать, что А° 0 и1° #0. Алгоритм £ состоит из следующих шагов: Шаг 0.к 0.

Шаг 1 (дискриминантный анализ). Найдем аффинную функцию <рк, удовлетворяющую условиям

Vx 6 А* : фк(х) > 0, Vx е В* : фк{х) < 0. и условию нормализации: вектор нормали к гиперплоскости Йк — {i j фк(х) = 0} должен быть коллинеарен вектору нормали к гиперплоскости Н.

Шаг 2 (порождение образцов). Получим новый образец как решение следующей задачи ЛПА*:

хк = arg max {(с, ж) | х € D, фк{х) < 0). Шаг 3 (экспертиза и пополнение ф).

Если

(с,хк) £ {(с,х) ¡хеАкиВкиЛ}, (6)

то положим

[А*, е(хк) = - 1

| А* U {ifc}, е(хк) — 1

S* U {х*}, е(хк) = - 1

Bfc, е(хк) = 1

Шаг 4 (рандомизация).Если условие (6) не выполняется, то выполним процедуру рандомизации. Пусть

W(C) = {х + r?(x) 1 Vx е С; г = 1,...,тп},

Ак+1 = В*+1 =

где rf(x) — случайный вектор в ^-окрестности точки х. Будем называть р радиусом рандомизации, т — мощностью рандомизации (т > 1). Выберем рк такое, что

О < рк < min(dist(At,W),dist(Bfc,Я)) (здесь dist{X,Y) = inf{||a; ~vV- * e X, у e Г}). Положим:

A*+1 = A* U 9tÄ(A*), B*+I = В4 U ÍHA(B*).

Шаг 5. к := к + 1.

Шаг 6. Перейти на шаг 1.

Применение алгоритма £ для нахождения решения задачи ЛПНО (4) заключается в последовательном вычислении точек хк, являющихся решением задач ЛП А*:

max{(с,х) I х € D, фк{х) < 0} .

Процесс завершается при выполнении некоторого критерия, указывающего на то, что очередной хк оказался в достаточной близости от точного решения х.

Центральной частью первой главы является доказательство сходимости полученной последовательности приближенных решений к точному решению исходной задачи.

Теорема 2. Для последовательности зг0,®1,...,®4, определяемой алгоритмом £, имеем:

{х*}Г=0 ш.

Для доказательства теоремы 2 используются леммы 1-3.

Лемма 1. Пусть для всех достаточно больших к задача ЛПАк ßk = max-^c.x) I х е D, <pk(x) < 0], порождаемая алгоритмом £, имеет бесконечное множество решений Xk = {х I х € D Л Р*;(с,х) = ßk}. Тогда

lim dist(Нк,Н) = 0 х — х.

A—too

Лемма 2. В контексте алгоритма ¡и справедливо следующее утверждение:

lim dist (Я*, Я) = 0 {хН^о -> х.

h—*oo

Лемма 3. Применительно к алгоритму £ хотя бы одно из следующих условий истинно:

{х*}Г=0 - äf;

lim dist(co А^соВ*) = 0

k—foо

(со —выпуклая оболочка).

Реализация алгоритма £ непосредственно в том виде, как он был описан выше, на практике не всегда возможна. Прежде всего это относится к условию нормализации. Во многих случаях эксперт не в состоянии определить нормаль к гиперплоскости, задаваемой неформализованным ограничением. Следующая теорема показывает, что при определенных обстоятельствах неформализованным ограничением можно пренебречь.

Теорема 3. Пусть И — плоский слой толщины е > 0, серединой которого является гиперплоскость Н, задаваемая неформализованным ограничением. Обозначим через алгоритм, получающийся из алгоритма £ путем снятия ограничения на фк, связанного с выполнением условия норма-лгаации. Тогда, если для алгоритма выполняется условие Чк' : ЭЬ > к' :хк 6 А* и В* и Н,

то

Че > 0 : Зк' : Ук > к' : (Нк П X») С (Iе Г) £>).

Теорема 3 показывает, что, если при поиске приближенного решения с помощью алгоритма регулярно выполняется рандомизация, то при к, стремящемся к бесконечности, Йк «стремится стать параллельной» к Н, а это означает, что в данном случае мы можем пренебречь на практике условием нормализации.

Далее рассматривается случай нескольких неформализованных ограничений. Пусть имеется задача линейного программирования с несколькими неформализованными ограничениями (ЛПНО ) в пространстве К":

х е А^тах{(с,аг) | Ах < Ь, ^(х) < 0, ... , фч(х) < О}. (7) Здесь неравенства <р1(х) < 0, ... , <рч(х) < 0 играют роль неформализованных ограничений в том смысле, что нам не известен вид функций (г = 1,...,д). Будем предполагать, что функции щ принадлежат к классу аффинных функций, и что задача (7) имеет единственное решение. Пусть Pi = {х | <р,(х) < 0} — множество значений, удовлетворяющих неформализованному ограничению < 0. Так как ^ является аффинной функцией, то 1\ представляет собой замкнутое полупространство. Пусть ч _

Р = . Тогда допустимое множество задачи ЛПНО* будет иметь вид

¿=1

£> Г) Р . Будем предполагать, что ДПР* содержит внутренние точки.

Имеет место следующее обобщение теоремы 1 для случая нескольких неформализованных ограничений.

Теорема 4. Задача ЛПНО* (7) является устойчивой по ¡р1,...,(рй.

Решение задачи ЛПНО* может быть сведено к решению нескольких задач ЛПНО с одним неформализованным ограничением следующим образом. Рассмотрим следующую последовательность независимых задач ЛПНО, каждая из которых имеет только одно неформализованное ограничение ЛПНО1 : xi = argmax{(c,x) | Ах < Ь, <pi(x) < 0};

ЛПНО, : xq = arg max {(с, х) \ Ах < Ь, <pq(x) < 0} (предполагается, что каждая из этих задач имеет единственное решение). Используя алгоритм £, мы можем построить для каждой задачи ЛПНО,-(г = 1,...,д) последовательность аффшшыхразделяющих функций ф},...,фк. Сконструируем следующую задачу линейного программирования: ЛП* : хк е Arg max {(с, я) | Ах < Ь, ф${х) < 0, ... , фк(х) < 0). (8)

Теорема 5. Пусть задача ЛПНО* (7) имеет единственное решение х. Пусть каждая задача ЛПНО{ (1 < i < q) также имеет единственное решение xit причем Xi ^ х, где х = arg max {(с,г) | Ах < 6} — единственное решение задачи ЛПФ. Пусть хк — решение задачи ЛТ1к. Тогда

{**}й.0 -> я.

то есть при достаточно большом к в качестве приближенного решения задачи ЛПНО* (7) можно взять решение задачи ЛП* (8).

Формулировка теоремы 5 опирается на предположение, что все задачи ЛПНО/ имеют решение xt, не совпадающее с решением х задачи ЛПФ. На практике это требование мы можем выполнить следующим образом. На первом этапе находим приближенные значения коэффициентов и свободных членов для всех неформализованных ограничений ф^х) < 0, удовлетворяющих условию xi ^ х (каждое ограничение вычисляется независимо от других). Заметим, что если ни одно неформализованное ограничение не удовлетворяет условию Xi ^ х , то решением задачи ЛПНО будет х. На втором этапе добавляем к системе ограничений задачи ЛПФ найденные на первом этапе приближения неформализованных ограничений и полагаем х равным решению расширенной задачи ЛПФ. Из оставшихся неформализованных ограничений снова выбираем все, удовлетворяющие условию я х, и находим их приближенный вид. Процесс заканчивается, когда либо все неформализованные ограничения будут найдены, либо останутся несколько ограничений, для которых х, — х (эти ограничения можно отбросить). Последняя расширенная задача ЛПФ даст приближенное решение исходной задачи ЛПНО*.

Во второй главе, «Алгоритм ЛП-ДА», предлагается вариант реализации метода, описанного в первой главе, в виде алгоритма, основанного на синтезе алгоритмов линейного программирования и дискриминантного анализа. Такую комбинацию мы обозначаем как алгоритм ЛП-ДА. На первом шаге формируется начальный набор образцов ф = {А, В} путем задания пары конечных непересекающихся множеств А и В из пространства R™, удовлетворяющих условиям

[е(х) = 1, Ух е А; е(х) — -1, Ух € В.

На следующем шаге с помощью какого-либо метода дискриминантного анализа строится аффинная функция ф, разделяющая множества А и В:

ф(х) >0, Ухе А; ' ф(х) < 0, Ух е В.

В качестве метода дискриминантного анализа могут фигурировать, например, метод линейной коррекции, метод комитетов или фейеровские методы.

Далее с использованием полученной разделяющей функции строится аппроксимационная задача линейного программирования (ЛПА):

х е Arg max {(с, х) | Ах < Ь,ф(х) < 0}. Аппроксимационная задача решается в блоке оптимизации одним из методов линейного программирования. Здесь может использоваться, например, симплекс-метод или методы фейеровского типа.

С помощью критерия завершения проверяется, является ли полученное решение £ допустимым приближением к точному решению х. Если точка х не удовлетворяет критерию завершения, то она направляется в блок экспертизы, где к ней применяется функция эксперта t. Если t(x) = 1, то точка х добавляется в множество А, если е(5) = — 1, то точка х добавляется в множество В. После этого описанный процесс повторяется применительно к расширенному набору образцов.

При проведении экспертизы и пополнении набора образцов могут возникать коллизии следующих трех типов:

1. e(i) = 0;

2. с(х) = 1 и х € А (образец уже присутствует в множестве А);

3. e(i) = — 1 и х е В (образец уже присутствует в множестве В).

В этом случае к х применяется процедура рандомизации. Точки, полученные в результате процедуры рандомизации, вновь подвергаются экспертизе и используются для пополнения набора образцов.

Эффективную работу алгоритма ЛП-ДА обеспечивает набор образцов = {А, В}, удовлетворяющий следующим условиям:

A <ZD\P, 1С0П(?\Й),

А ^ 0, В 0.

При этом мы предполагаем, что множества Б\Р и Вп(Р\ II) имеют внутренние точки. В этом случае аппроксимационная задача всегда будет иметь решение. В соответствии с этим можно использовать следующий алгоритм для формирования начального набора образцов. Мы находим все вершины многогранника Д применяем к ним функцию эксперта е и формируем множества Л и В по следующему правилу:

А = {* | е(х) = 1}, В = {х \ ф) = -1}. Точки, для которых е(ж) = 0, отбрасываются.

Для реализации алгоритма ЛП-ДА в виде программы нам необходим некоторый критерий близости решения аппроксимационной задачи к точному решению задачи ЛПНО. Этот критерий необходим для завершения итерационного процесса. Пусть ,...,хк — последовательность решений ап-проксимационных задач, полученных при работе алгоритма ЛП-ДА. Тогда в качестве искомого критерия может выступать условие вида

1=1

где е > 0 — заданное вещественное число, определяющее точность вычислений. Здесь I — фиксированное целое положительное число, являющееся параметром алгоритма ЛП-ДА.

Для разрешения коллизий, возникающих при проведении экспертизы, мы используем следующую процедуру рандомизации. Определим случайное отображение хр : К" —> К", обладающее свойством: Цг^х) — х|| < р. Отображение Vй(х) порождает случайные точки внутри сферы радиуса р с центром в х. Вещественное число р > 0 является параметром алгоритма ЛП-ДА, задающим радиус рандомизации. Процедура рандомизации заключается в построении с помощью отображения хр{х) множества точек

= {х1,...,!"1}, удовлетворяющих условию

2' ^ А и В и Я, ||24-2|)<,з (г = 1,...,т). Целое положительное число т является параметром алгоритма ЛП-ДА, задающим мощность рандомизации. Все точки множества подвергаются экспертизе и используются для пополнения набора образцов на текущей итерации.

Описывается оригинальный метод осцилляций, позволяющий во многих случаях значительно повысить эффективность алгоритма ЛП-ДА. Суть метода осцилляций состоит в том, что на каждой итерации алгоритма ЛП-ДА кроме аппроксимационной задачи решается следующая дополнительная задача линейного программирования (ЛПД):

х € Агешт{(с,ж) | Ах < Ь,ф(х) > 0} Решение х дополнительной задачи подвергается процедуре экспертизы и, в случае отсутствия коллизий, добавляется к набору образцов ф = {А,В}.

При возникновении коллизии к точке х применяется процедура рандомизации.

В заключительном разделе главы предлагается система допусков, обеспечивающая корректную работу алгоритма при возникновении погрешностей вычислений, связанных с неточным представлением вещественных чисел в ячейках памяти ЭВМ.

В третьей главе, «Программный комплекс ЛП-ДА», рассматривается архитектура программного комплекса для решения задач линейного программирования с неформализованными ограничениями на базе использования алгоритма ЛП-ДА. Предлагается модульная структура программного комплекса, использующая технологию картриджей, которая позволяет расширять программный комплекс путем добавления новых методов линейной оптимизации и дискриминантного анализа. Описывается оригинальный формат входных данных LPNC для представления задач ЛПНО, базирующийся на стандарте MPS. Рассматривается параллельная реализация комплекса для многопроцессорных систем. Схема параллельного алгоритма решения задачи ЛПНО приведена на Рис. 1. На первом шаге задача ЛПНО , имеющая г неформализованных ограничений, разбивается на г задач ЛПНО.....,ЛПНО,. Каждая из этих задач независимо

решается методом ЛП-ДА. Из вычисленных приближений неформализованных ограничений и формализованной части задачи ЛПНО строится полная система ограничений. На втором шаге полученная таким образом задача решается одним из методов линейного программирования. В результате с некоторым приближением мы получаем х —решение исходной задачи ЛПНО*. При реализации параллельной версии алгоритма ЛП-ДА нахождение каждого неформализованного ограничения оформлялось в виде независимого процесса Р/ (t = 1.....г). Вычисленные ограничения передавались некоторому

выделенному процессору-координатору PIt который формировал полную задачу линейного программирования и решал ее каким-либо методом линейной оптимизации. При реализации параллельной версии алгоритма ЛП-ДА мы использовали передачу сообщений на основе односторонних коммуникаций MPI-2. Проектирование программы выполнялось в соответствии в моделью SIMD.

В рамках диссертационного исследования была выполнена реализация прототипа программного комплекса ЛП-ДА на языке Си. В качестве блока оптимизации был реализован симплекс-метод, в качестве блока дискриминантного анализа был реализован метод линейной коррекции. Работа эксперта моделировалась явным заданием неформализованных ограничений. Общий объем кода на языке Си составил около 3000 строк.

Рнс. 1. Схема параллельного алгоритма.

О -1-•-1-1-1-:-1-

0.0001 0.0002 0.001 0.002 0.01 0.02 0.1 0.2 Радиус ранломиэаиии

о

0.0001 0.0002 O.OOI 0.002 0.01 O.D2 0.1 0.2 Радиуо рвндомнзацнк

Рис. 2. Зависимость времени решения задачи от радиуса рандомизации р.

Рис. 3. Зависимость числа итераций от радиуса рандомизации /?.

В четвертой главе, «Компьютерный анализ алгоритма ЛП-ДА»,

приводится описание реальных и искусственных задач, использованных для проверки эффективности предложенных подходов, методов и алгоритмов. Описываются и обсуждаются результаты экспериментов, проведенных на персональном компьютере и на высокопроизводительном вычислительном кластере.

Для проведения экспериментов была сконструирована масштабируемая модельная задача Мой-п, содержащая п переменных 2(п~1) формализованных ограничений и одно неформализованное. В первой серии экспериментов была исследована зависимость количества итераций и времени решения задачи Мос1-п от радиуса рандомизации р. Эксперименты проводились для значений и, равных 40, 60 и 80. Результаты представлены на Рис. 2 и Рис. 3. Графики на Рис. 2 показывают, что время решения задачи слабо зависит от радиуса рандомизации, достигая минимума приблизительно при значении р — 0.01. Графики на Рис. 3 показывают, что количество итераций для задач небольшой размерности (п = 40) может значительно уменьшаться с увеличением радиуса рандомизации, принимая горизонтально-асимптотический характер для значений р > 0.01. Для задач большой размерности (п = 80) влияние радиуса рандомизации на количество итераций становится незначительным. Проведенные эксперименты показывают, что в большинстве случаев хорошим выбором является значение р = 0.01.

Во второй серии экспериментов исследовалась зависимость количества итераций и времени решения задачи Мос1-п от мощности рандомизации тп. Эксперименты проводились для значений п, также равных 40, 60 и 80. Графики на Рис. 4 показывают, что время решения задачи также слабо зависит от мощности рандомизации, достигая минимума приблизительно при значении 77г = 30. Графики на Рис. 5 показывают, что количество итераций для всех трех размерностей уменьшается с ростом тп, принимая горизонтально-асимптотический характер для значений тп > 20. При этом для задач большой размерности (п = 80) влияние мощности рандомизации на количество итераций также становится незначительным. Проведенные эксперименты показывают, что в большинстве случаев хорошим выбором является значение 771 = 30.

Мощное» рандомизации

Рис. 4. Зависимость времени решения задачи от мощности рандомизации т.

Мощность рандомизации

Рис. 5. Зависимость числа итераций от мощности рандомизации т<

1 . «О

Я

* овс-он — О— -озс-огг

Рнс. б. Зависимость времени решения задачи от размерности п.

30 ЭО 40 50 50 70 во 90 100 110 Размерность мпчя

Гнс. 7. Зависимость числа итераций от размерности л.

В следующей серии экспериментов исследовалась эффективность примененгм метода осцилляции при решении задач различной размерности. Были проведены вычислительные эксперименты с задачей Мос1-п, в ходе которых размерность задачи п варьировалась в диапазоне от 20 до 110. В первом эксперименте метод осцилляций был включен (ОБСНЭЫ), а ¡во втором — выключен (ОЗС=ОРР). Результаты этих экспериментов показывают (см. Рис. 6 и Рис. 7), что в обоих вариантах при увеличении размерности время решения задачи растет, а количество итераций уменьшается. Однако, если задача имеет размерность п < 50, вариант алгоритма, использующий метод осцилляций, позволяет получить решение при значительно меньшем количестве итераций, что дает возможность существенно сократить число обращений к эксперту.

Эффективность алгоритма ЛП-ДА была также проверена на реальной задаче управления металлургическим предприятиемЭта задача моделирует управление прокатным комплексом, включающим рельсобалочный стан, участок отделки фасонных профилей и термоямы. Была проведена серия вычислительных экспериментов, в которых исследовались зависимость времени решения задачи и количества итераций от значения е, используемого в

Фролов В.Н. Оптимизация плановых программ при слабо согласованных ограничениях. -М.: Наука, 1986.

0.5 0.1 0.05 0.01 0.D05 0.00t О.ОООв 0.0001 Величина <

Рис. 8. Зависимость времени решения задачи от величины в.

0.5 0.1 0.05 0.01 0.005 0.001 0.0005 0.0001 Величина«

Рис. 9. Зависимость числа итераций от величины £.

- " —

—О—П=100 —о— П»В0 —йг—л=60

12 10 20 24 2i 32 Эв 40 Количество процессоров р

Рнс. 10. Ускорение для Mod-пц.

О 4 8 12 10 20 24 2а 32 Эв 40 44 Калпеспо процессоров Р

Рис. 11. Расширяемость для Kíod-nr

критерии завершения. Проведенные эксперименты показали (см. Рис. 8 и Рис. 9), что метод осцилляции во всех случаях обеспечивает примерно двукратное превосходство по скорости сходимости.

В заключительном разделе главы исследуется масштабируемость параллельной версии алгоритма ЛП-ДА для варианта, использующего симплекс-метод и метод линейной коррекции. Для проведения экспериментов был использован вычислительный кластер с 52 процессорами Intel Хеопб4 3,2 GHz. Результаты по исследованию ускорения представлены на Рис. 10. Эксперименты проводились для трех размерностей: п — 60, п = 80 и п = 100. Ускорение вычислялось по формуле а = а0 + tp/ta , где fs — время, затраченное на решение модельной задачи размерности п с 48 неформализованными ограничениями на 8 процессорах, tp — время, затраченное на решение этой же задачи на р процессорах, а0 = (п — 60)^60. Для каждой

размерности варьировалось количество процессоров, используемых для решения задачи. Во всех трех случаях было получено ускорение, близкое к линейному. Результаты по исследованию расширяемости для параллельного алгоритма ЛП-ДА приведены на Рис. 11. Здесь tpr обозначает время, затраченное на решение модельной задачи размерности пег неформализованными ограничениями на р процессорах. При проведении эксперимента для каждой размерности варьировалось количество процессоров, используемых

для решения задачи. При этом количество неформализованных ограничений всегда равнялось количеству процессоров. Проведенные эксперименты показали, что во всех случаях параллельный алгоритм ЛП-ДА демонстрировал расширяемость, близкую к линейной.

В заключении суммируются основные результаты диссертационной работы, выносимые на защиту, приводятся данные о публикациях и апробациях автора по теме диссертации, и рассматриваются направления дальнейших исследований в данной области.

В приложении приводятся основные сокращения и обозначения, используемые в диссертационной работе.

Основные результаты диссертационной работы

На защиту выносятся следующие новые научные результаты.

1. Предложен и исследован итерационный метод для решения задач линейного программирования с неформализованными ограничениями, базирующийся на синтезе дискриминантного анализа и линейной оптимизации.

2. Предложен метод осцилляции, позволяющий существенно ускорить сходимость последовательности приближений к точному решению.

3. Разработан и исследован алгоритм ЛП-ДА, соединяющий методы линейного программирования и дискриминантного анализа.

4. Спроектирован и реализован прототип программного комплекса для решения задач линейного программирования с неформализованными ограничениями. Общий объем кода на языке Си составил около 3000 строк. Исходные тексты прототипа свободно доступны в Интернет по адресу: http://life.susu.ru/lpno/.

5. Спроектирована и реализована параллельная версия алгоритма ЛП-ДА с использованием пакета МР1-2. Исходные тексты параллельной версии свободно доступны в Интернет по адресу: http://life.susu.ru/lpnoMPI/.

6. Проведены вычислительные эксперименты на модельных и реальных задачах экономико-математического моделирования, подтверждающие эффективность предложенных алгоритмов, методов и подходов.

Публикации по теме диссертации

Основные результаты диссертации полностью опубликованы автором в следующих работах:

1. Сокалинская И.М. Синтез симплекс-метода и метода линейной

коррекции в задачах линейной оптимизации с неформализованными ограничениями // Вычислительные методы и программирование. —2005. -Том 6, №2. -С. 103-115.

2. Mazurov Vl.D., Sokolinskaya I.M. Discrimination analysis and randomization in linear optimization problems with not formalized restrictions // Pattern Recognition and Image Analysis. -2006. -Vol. 16, No. 2. -P. 170-178.

3. Соколинская И.М. Метод осцилляции в задачах линейного программирования с неформализованным ограничением // Алгоритмический анализ неустойчивых задач: Тез. докл. Всерос. науч. конф. (2-6 февраля 2004 г., Екатеринбург). -Екатеринбург: Изд.-во Урал, ун-та. -2004. -С. 302-303.

4. Соколинская И. М., Соколинский Л, Б. Программный комплекс для решения задач линейного программирования с неформализованными ограничениями //.Первая Международная Конференция «Системный Анализ и Информационные Технологии» САИТ-2005 (12-16 сентября 2005 г., Переславль-Залесский, Россия): Труды конференции. В 2 т. Т. 2. -М.: КомКнига. -2005. -С. 286-292.

5. Соколинская И.М., Соколинский Л.Б. Параллельный алгоритм решения задачи линейного программирования с неформализованными ограничениями // Проблемы оптимизации и экономические приложения: Тезисы докладов международной конференции. -Омск: Омск. гос. ун-т. -2006.-С. 1.

Работа выполнялась при поддержке Российского фонда фундаментальных исследований (проекты 03-01-00565, 06-01-00380).

Подписано в печать 04.07.2006 Формат 60x84 1/16. Бумага офсетная. Печать офсетная. Усл. печ. л. 1,0. Уч.-изд. л. 1,2. Тираж 100 экз. Заказ № 76. Бесплатно

Челябинский государственный университет 454021 Челябинск, ул. Братьев Кашириных, 129

Полиграфический участок Издательского центра ЧелГУ 454021 Челябинск, ул. Молодогвардейцев, 576

Введение.

Глава 1. Синтез дискриминантного анализа и линейной оптимизации.

1.1. Математическая модель задачи ЛПНО.

1.2. Общий метод решения задачи ЛПНО.

1.3. Устойчивость задачи ЛПНО.

1.4. Алгоритм £ порождения образцов.

1.5. Теорема сходимости для алгоритма £.

1.6. Реализационные аспекты алгоритма £

1.7. Случай нескольких неформализованных ограничений.

Глава 2. Алгоритм ЛП-ДА.

2.1. Общая схема алгоритма ЛП-ДА.

2.2. Формирование начального набора образцов.

2.3. Критерий завершения итерационного процесса.

2.4. Рандомизация.

2.5. Метод осцилляций.

2.6. Проблема погрешности вычислений.

Глава 3. Программный комплекс ЛП-ДА.

3.1. Модульная структура комплекса.

3.2. Формат входных данных ЬР>1С.

3.3. Параллельная реализация.

3.3.1. Классификация параллельных методов решения задачи ЛПНО

3.3.2. Параллельная версия алгоритма ЛП-ДА.

3.4. Реализация прототипа.

Глава 4. Компьютерный анализ алгоритма ЛП-ДА.

4.1. Эксперименты на искусственных задачах.

4.1.1. Модельная задача Мос1-п.

4.1.2. Влияние радиуса рандомизации на эффективность.

4.1.3. Влияние мощности рандомизации на эффективность.

4.1.4. Эффективность метода осцилляций.

4.1.5. Эксперименты с неполными наборами образцов.

4.2. Эксперименты на реальной задаче.

4.3. Масштабируемость параллельного алгоритма.

АКТУАЛЬНОСТЬ ТЕМЫ

В практике экономико-математического моделирования часто встречаются задачи, при решении которых приходится учитывать большое число взаимосвязанных факторов, включая плохо формализуемые [16, 21, 22, 25]. Процесс решения плохо формализуемой задачи включает в себя преобразование ее формулировки путем уточнений и упрощений. В результате этого процесса мы получаем формализованную задачу, имеющую некоторое отношение к исходной постановке задачи. Во многих случаях удается построить формализованную задачу в виде задачи линейного программирования [7, 12, 14, 18, 52]. Однако решение формализованной задачи может сколь угодно сильно отличаться от решения исходной задачи в силу наличия неформализованных ограничений.

Помимо формальных методов и моделей для решения плохо формализуемой задачи используются средства неформального анализа, включающие в себя суждения экспертов для учета так называемых «внемодель-ных» факторов [26, 51]. При этом человеческий компонент в процессе экспертизы может постепенно, с помощью обучения, заменяться машинным компонентом путем использования экспертных систем [8, 36, 54] или ней-росетевых программ [28, 29, 30, 63, 64]. Однако при решении задач линейного программирования большой размерности эти подходы могут оказаться неэффективными, если их применять для решения всей задачи в целом. Это объясняется тем, что трудно адекватно настроить (обучить) экспертную систему или нейронную сеть в случае, когда система ограничений содержит тысячи линейных неравенств и десятки тысяч переменных. В таких ситуациях перспективным является подход, основанный на сочетании методов линейной оптимизации с процедурами экспертного оценивания. Алгоритм решения задачи в этом случае строится как итерационный процесс, в ходе которого шаг за шагом происходит уточнение ограничений, относящихся к неформализованной части задачи. Приближенные решения исходной задачи, получаемые в ходе итерационного процесса, формируют множество образцов, квалифицируемых экспертом. Применяя к этому множеству образцов процедуру дискриминантного анализа [23, 32, 37, 66, 71], мы получаем разделяющую поверхность, аппроксимирующую неформализованные ограничения.

В соответствии с этим актуальной является задача разработки, анализа и реализации на ЭВМ алгоритмов решения задач линейного программирования с неформализованными ограничениями путем синтеза методов дискриминантного анализа и линейной оптимизации.

ЦЕЛЬ И ЗАДАЧИ ИССЛЕДОВАНИЯ

Цель данной работы состояла в разработке и исследовании методов и алгоритмов решения задач линейного программирования с неформализованными ограничениями и их реализации в виде программного комплекса. Для достижения этой цели необходимо было решить следующие задачи:

1. Построить математическую модель задачи линейного программирования с неформализованными ограничениями (ЛПНО) и описать общий подход к ее решению.

2. На базе данного подхода разработать метод решения задачи ЛПНО, допускающий реализацию в виде алгоритма для ЭВМ, и исследовать сходимость этого метода.

3. На основе описанного метода разработать и исследовать алгоритм ЛП-ДА (Линейное Программирование - Дискриминантный Анализ), соединяющий алгоритмы линейного программирования с алгоритмами дискриминантного анализа.

4. Спроектировать и реализовать программный комплекс для решения задач ЛПНО, использующий предложенные методы и алгоритмы.

5. Провести вычислительные эксперименты для анализа эффективности предложенного подхода.

6. Разработать и реализовать параллельную версию алгоритма ЛП-ДА. Провести вычислительные эксперименты на кластерной системе для исследования ускорения и расширяемости параллельного алгоритма.

МЕТОДЫ ИССЛЕДОВАНИЯ

В исследованиях, проводимых в диссертационной работе, используется аппарат теории математического программирования и распознавания образов, применяются методы дискриминантного анализа и линейной оптимизации.

НАУЧНАЯ НОВИЗНА

Научная новизна работы заключается в следующем:

1. предложен метод решения задачи линейного программирования с неформализованными ограничениями, базирующийся на синтезе методов дискриминантного анализа и методов линейной оптимизации, и доказана сходимость генерируемой им итерационной последовательности к точному решению задачи ЛПНО;

2. предложен оригинальный метод осцилляций, позволяющий существенно ускорить сходимость последовательности приближений к точному решению задачи ЛПНО;

3. разработан новый алгоритм, соединяющий симплекс-метод и метод линейной коррекции, и предложена его параллельная версия;

4. выполнена реализация алгоритма решения задач ЛПНО в виде программного комплекса для персональных компьютеров и многопроцессорных систем на основе стандарта МР1-2.

ТЕОРЕТИЧЕСКАЯ И ПРАКТИЧЕСКАЯ ЦЕННОСТЬ

Теоретическая ценность работы состоит в том, что в ней представлены доказательства теоремы об устойчивости задачи линейного программирования по неформализованному ограничению и теоремы о сходимости метода, соединяющего дискриминантный анализ и рандомизацию с линейной оптимизацией. Практическая ценность работы заключается в том, что предложенный программный комплекс в сочетании с системами экспертного оценивания может быть использован для решения плохо формализуемых задач, возникающих в экономико-математическом моделировании.

СТРУКТУРА И ОБЪЕМ РАБОТЫ

Диссертация состоит из введения, четырех глав, заключения, библиографии и приложения, в котором приводятся основные обозначения, используемые в диссертационной работе. Объем диссертации составляет 92 страницы, объем библиографии - 77 наименований.

Основные результаты диссертации полностью опубликованы в следующих печатных работах.

1. Соколинская И.М. Синтез симплекс-метода и метода линейной коррекции в задачах линейной оптимизации с неформализованными ограничениями // Вычислительные методы и программирование. -2005. -Том 6, №2.-С. 103-115.

2. Mazurov Vl.D., Sokolinskaya I.M. Discrimination analysis and randomization in linear optimization problems with not formalized restrictions // Pattern Récognition and Image Analysis. -2006. -Vol. 16, No. 2. -P. 170-178.

3. Соколинская И.М. Метод осцилляций в задачах линейного программирования с неформализованным ограничением // Алгоритмический анализ неустойчивых задач: Тез. докл. Всерос. науч. конф. (2-6 февраля 2004 г., Екатеринбург). -Екатеринбург: Изд.-во Урал, ун-та. -2004.-С. 302-303.

4. Соколинская И.М., Соколинский Л.Б. Программный комплекс для решения задач линейного программирования с неформализованными ограничениями // Первая Международная Конференция «Системный Анализ и Информационные Технологии» САИТ-2005 (12-16 сентября 2005 г., Переславль-Залесский, Россия): Труды конференции. В 2 т. Т. 2. -М.: КомКнига. -2005. -С. 286-292.

5. Соколинская И.М., Соколинский Л.Б. Параллельный алгоритм решения задачи линейного программирования с неформализованными ограничениями // Проблемы оптимизации и экономические приложения: Тезисы докладов международной конференции. -Омск: Омск. гос. ун-т. -2006. -С. 1.

АПРОБАЦИЯ РАБОТЫ

Основные положения диссертационной работы, разработанные модели, методы, алгоритмы и результаты вычислительных экспериментов докладывались автором на следующих международных и всероссийских научных конференциях: на Всероссийской научной конференции "Алгоритмический анализ неустойчивых задач" (2-6 февраля 2004 г., Екатеринбург); на Международной научной конференции "Системный Анализ и Информационные Технологии" САИТ-2005 (12-16 сентября 2005 г., Пе-реславль-Залесский); на III Всероссийской научной конференции "Проблемы оптимизации и экономические приложения" (Омск, 11-15 июля 2006 г.).

НАПРАВЛЕНИЯ ДАЛЬНЕЙШИХ ИССЛЕДОВАНИЙ

Теоретические исследования и практические разработки, выполненные в рамках этой диссертационной работы, предполагается продолжить по следующим направлениям.

1. Доказательство сходимости представленного в данной диссертации алгоритма £ при более слабых ограничениях. В частности, может быть сформулирована гипотеза о том, что теорема сходимости для алгоритма £ остается справедливой и в случае устранения условия нормализации. В пользу этой гипотезы свидетельствуют теорема 3 (см. раздел 1.6 диссертации) и проведенные в ходе диссертационного исследования эксперименты на реальных и искусственных задачах (см. главу 4 диссертации), так как во всех экспериментах был использован вариант алгоритма без условия нормализации.

2. Создание версии программного комплекса для 64-разрядных процессоров. Здесь основной проблемой является подбор оптимальных значений допусков, связанных с преодолением ошибок округления.

3. Создание в рамках программного комплекса альтернативных блоков для решения задач линейного программирования и дискриминантно-го анализа (в дополнение к симплекс-методу и методу линейной коррекции предполагается реализовать методы фейеровского типа [2, 3, 9, 10] и метод комитетов [20, 26, 27, 46]).

ЗАКЛЮЧЕНИЕ

В диссертационной работе были рассмотрены вопросы, связанные с решением задач линейного программирования при наличии неформализованных ограничений. Было показано, что задачу с несколькими неформализованными ограничениями можно свести к задаче с одним неформализованным ограничением. Предложен общий метод для решения задач с одним неформализованным ограничением, базирующийся на дискриминантном анализе и экспертизе новых образцов, получаемых в результате решения задачи линейного программирования. Каждый новый образец получается как решение аппроксимационной задачи линейного программирования, где вместо неформализованного ограничения фигурирует неравенство на основе разделяющей функции. В случае, когда решение аппроксимационной задачи уже присутствует в наборе образцов, применяется процедура рандомизации. Для описанного метода была доказана теорема сходимости и рассмотрены вопросы его практической реализации. В качестве реализации общего метода предложен итерационный алгоритм ЛП-ДА для решения задач линейного программирования при наличии нескольких неформализованных ограничений. Этот алгоритм базируется на сочетании симплекс-метода и метода линейной коррекции. Рассмотрены различные аспекты реализации алгоритма ЛП-ДА в виде программы для ЭВМ. Предложена параллельная версия алгоритма. Выполнены проектирование и реализация программного комплекса на языке Си и проведено большое количество вычислительных экспериментов на реальных и искусственных задачах, подтверждающих эффективность предложенных подходов.

Работа выполнялась при поддержке Российского фонда фундаментальных исследований (проекты 03-01-00565, 06-01-00380).

В заключение перечислим основные полученные результаты диссертационной работы, приведем данные о публикациях и апробациях, и рассмотрим направления дальнейших исследований в данной области.

1. Бердникова Е.А., Ерёмин И.И., Попов Л Д. Распределенные фейеровские процессы для систем линейных неравенств и задач линейного программирования // Автоматика и телемеханика. -N0. 2. -2004. -С. 16-32.

2. Васин В.В., Еремин И. И. Операторы и итерационные процессы фейеров-ского типа. Теория и приложения. -Екатеринбург: УрО РАН, 2005. -210 с.

3. Воеводин Вл.В., Капитонова А.П. Методы описания и классификации архитектур вычислительных систем. —М: Изд-во МГУ, 1994. -103 с.

4. Воеводин В.В., Воеводин Вл.В. Параллельные вычисления. -СПб.: БХВ-Петербург, 2002. -600 с.

5. Горелик А.Л., Гуревич И. Б., Скрипкин В. А. Современное состояние проблемы распознавания: Некоторые аспекты. -М.: Радио и связь, 1985. -161 с.

6. Данциг Дж. Линейное программирование, его применение и обобщения. -М.: Прогресс, 1966. -600 с.

7. Джексон П. Введение в экспертные системы. -М: Издательский дом "Вильяме", 2001.-624 с.

8. Еремин И.И. Методы фейеровских приближений в выпуклом программировании //Мат. заметки. -1968. -Т. 3, вып. 2. -С. 217-234.

9. Еремин И.И. Применение метода фейеровских приближений к решению задач выпуклого программирования с негладкими ограничениями // Журн. вычисл. мат. и мат. физики. -1969. -Т. 9, № 5. -С. 1153-1160.

10. Еремин И.И. Общая теория устойчивости в линейном программировании // Известия ВУЗов. Математика. -1999. -N 12. -С. 43-52.

11. Еремин И.И. Теория линейной оптимизации. -Екатеринбург: Изд-во "Екатеринбург", 1999. -312 с.

12. Еремин И.И. Фейеровские методы сильной отделимости выпуклых полиэдральных множеств // Известия вузов. Сер. математика. -2006. (в печати).

13. Еремин ИИ., Астафьев H.H. Введение в теорию линейного и выпуклого программирования. -М.: Наука, 1976. -192 с.

14. Еремин И.И, Мазуров Вл.Д. Нестационарные процессы математического программирования. -М.: Наука, 1979. -291 с.

15. Еремин И. И., Мазуров Вл. Д. Вопросы оптимизации и распознавания образов. -Свердловск: Сред.-Урал. кн. изд-во, 1979. -63 с.

16. Еремин И.И, Мазуров Вл.Д., Скарин В Д., Хачай М.Ю. Математические методы в экономике. -Екатеринбург: У-Фактория, 2000. -280 с.

17. Канторович Л.В. Математические методы организации и планирования производства. -Л.: Изд-во ЛГУ, 1939. -68 с.

18. Корнеев В.В. Параллельные вычислительные системы. -М.: "Нолидж", 1999. -320 с.

19. Мазуров Вл. Д. Комитеты систем неравенств и задача распознавания // Кибернетика. -1971. -№ 3. -С. 140-146.

20. Мазуров Вл. Д. Об одном итерационном методе планирования, использующем распознавание образов для учета плохо формализуемых факторов // Изв. АН СССР. Техн. кибернетика. -1973. № з. -С. 205-207.

21. Мазуров Вл.Д. Распознавание образов как метод формирования плохо формализуемых ограничений в моделях планирования // Оптимизация. Вып. 10 (27). -Новосибирск: СО АН СССР, 1973. -С. 144-158.

22. Мазуров Вл.Д. Дискриминантный анализ при математическом моделировании плохо формализуемых ситуаций // Нелинейная оптимизация и приложения в планировании. -Свердловск: УНЦ АН СССР, 1973.-С. 26-35.

23. Мазуров Вл.Д. Комитеты в нечетких задачах // Методы оптимизации и распознавания образов в задачах планирования. -Свердловск: УНЦ АН СССР, 1980. -С. 44-65.

24. Мазуров Вл.Д. О задаче оптимизации с плохо формализуемой целью // Параметрическая оптимизация. -Свердловск: УНЦ АН ССР, 1985. -С. 51-53

25. Мазуров Вл.Д. Метод комитетов в задачах оптимизации и классификации. -М.: Наука, 1990. -248 с.

26. Мазуров Вл.Д., Кривоногое А.И., Казанцев B.C., Сачков И.О., Белецкий КГ. Комитеты в принятии решений // Кибернетика. -1984. -№ 1. -С. 90-95.

27. Мазуров Вл.Д., Мазуров П.В. Оптимизация, распознавание и нейронные сети в экономике. -Екатеринбург: УрГУ, 1999. -58 с.

28. Мак-Каллок У.С., Питтс В. Логическое исчисление идей, относящихся к нервной деятельности // Нейрокомпьютер. -1992. -№ 3-4. -С. 29-34.

29. Меламед И. И. Нейронные сети и комбинаторная оптимизация // Автоматика и телемеханика. 1994. - № 11. - С. 3-40.

30. Муртаф Б. Современное линейное программирование: Теория и практика. -М.: Мир, 1984. -224 с.

31. Немчинов B.C. Экономико-математические методы и модели. -Т. 3. -М.: Наука, 1967.

32. Нильсон Н. Обучающиеся машины. -М.: Мир, 1967. -180 с.

33. Оленев Н.Н. Основы параллельного программирования в системе MPI. -M.: изд-во ВЦ РАН, 2005. 90 с.

34. Портал вычислительного кластера «Infinity» http://cluster.susu.ru/.

35. Поспелов Д. А. Логико-лингвистические модели в системах управления. -М.: Энергоиздат, 1981. -232 с.

36. Розин Б.Б. Теория распознавания образов в экономических исследованиях. -М.: Статистика, 1973.

37. Соколинская КМ. Синтез симплекс-метода и метода линейной коррекции в задачах линейной оптимизации с неформализованными ограничениями // Вычислительные методы и программирование. -2005. -Том 6, №2.-С. 103-115.

38. Соколинский Л.Б., Цымблер Н.Ю. Параллельный алгоритм решения задач линейного программирования на основе фейеровских отображений. Технический отчет РФФИ#06-01-00380/УШ1. -Челябинск: ЮУрГУ, 2006.

39. Таненбаум Э. Современные операционные системы. -Издательство: Питер, 2002.-1040 с.

40. Фролов В.Н. Оптимизация плановых программ при слабо согласованных ограничениях. -М.: Наука, 1986. -164 с.

41. Четверушкин Б.Н. Высокопроизводительные многопроцессорные вычислительные системы // Вестник российской академии наук. -2002. -Том 72, №9. с. 786-794.

42. Ablow С.М., Kaylor D.J. A committee solution of the pattern recognition problem // IEEE Trans. -1965. -V. 71, No. 5.

43. Bartels R.H., Golub G.H. The simplex method of linear programming using LU decomposition // Communications of the ACM. -1969. Vol. 12, No. 5. -P. 266-268.

44. Bishop CM. Neural Networks for Pattern Recognition. -Oxford University Press, 1996. -504.

45. Dantzig G.B., Wolfe P. Decomposition principle for linear programs // Oper Res.-1960.-Vol. 8, No. l.-P. 101-111.

46. Dongarra J. J., Otto S. W., Snir M., Walker D. A message passing standard for MPP and workstations // Communications of the ACM. -1996. -Vol. 39, No. 7. -P. 84-90.

47. Gass S.I. Linear Programming. New York: McGraw-Hill. -1969.

48. Ghosh J., Hwang K. Critical issues in mapping neural networks on message-passing multicomputers // Proceedings of the 15th Annual International Symposium on Computer architecture. Honolulu, Hawaii, United States. -1988.-P. 3-11.

49. Giarratano J.C., Riley G.D. Expert Systems: Principles and Programming. -Course Technology. -1998. -624 p.

50. Gose T., Johnsonbaugh R., JostS. Pattern Recognition and Image Analysis. -Prentice Hall, 1996. -483 p.

51. Gropp W., Huss-Lederman S., Lumsdaine A., LuskE., NitzbergB., Saphir W., Snir M. MPI The Complete Reference: Volume 2, The MPI Extensions. -MIT Press, 1998.

52. Gunther N.J. The Practical Performance Analyst. -Authors Choice Press, 2000. -468 p.

53. FausettL. V. Fundamentals of Neural Networks. -Prentice Hall, 1994. -461 p.

54. Flynn M.J., Rudd K. W. Parallel architectures // ACM Computing Surveys. -1996.-Vol. 28, No. l.-P. 67-70.

55. Forrest J. J.H., Tomlin J.A. Implementing the simplex method for the optimization subroutine library // IBM Systems Journal. -1992. -Vol. 31, No. l.-P. 11-25.

56. Hadley G. Linear Programming. Mass.: Addison-Wesley, Reading. -1962.

57. Hopfield J.J., TankD. W. Neural computation of decision in optimization problems // Biol. Cybernet. -1985. -V. 52. -P. 141-152.

58. Jordan M.I., Bishop C.M. Neural networks // ACM Computing Surveys. -1996. -Vol. 28, No. l.-P. 73-75.

59. Kennedy J. V., Austin J., Pack R., Cass B. CNNAP A Parallel Processing Architecture for Binary Neural Networks I I Proceedings of the IEEE International Conference on Neural Networks (ICNN'95), Perth, Western Australia. -1995.

60. Lachenbruch P.A. Discriminant Analysis. -New York: Hafner Press, 1975.

61. Lyu J.J., Luh H., Lee M.-C. Solving Linear Programming Problems on the Parallel Virtual Machine Environment // American Journal of Applied Sciences. -2004. -Vol. 1, No. 2. -P. 90-94.

62. Martinson R.K., Tind J. An interior point method in Dantzig-Wolfe decomposition// Computers & Operations Research. -1999. -Vol. 26, No. 12. -P. 1195-1216.

63. Mazurov Vl.D., Sokolinskaya I.M. Discrimination analysis and randomization in linear optimization problems with not formalized restrictions // Pattern Recognition and Image Analysis. -2006. -Vol. 16, No. 2. -P. 170-178.

64. Molina F. W. A Survey of Resource Directive Decomposition in Mathematical Programming // ACM Computing Surveys. -1979. -Vol. 11, No. 2. -P. 95-104.

65. McLachlan G.J. Discriminant Analysis and Statistical Pattern Recognition. -New York: John Wiley and Sons, 1992. -526 p.

66. Nazareth J.L. Computer Solution of Linear Programs. -Oxford University Press, 1988.

67. Orchard-Hays W. Advanced Linear Programming Computing Techniques. -New York: McGraw-Hill, 1968.

68. Quinn M.J. Parallel Computing: Theory and Practice. -McGraw-Hill Companies, 1993. -446 p.

69. Snir M., Otto S., Huss-Lederman S., Walker D., Dongarra J. MPI The Complete Reference. Volume 1, The MPI Core. 2nd Ed. -MIT Press, 1999.

70. Stunke C.B.I, Reed D.A. Hypercube implementation of the simplex algorithm // Proceedings of the third conference on Hypercube concurrent computers and applications Volume 2. -New York, NY, USA: ACM Press. -1989. -P. 1473-1482.

71. White W. W. A Status Report on Computing Algorithms for Mathematical Programming // ACM Computing Surveys. -1973. -Vol. 5, No. 3. -P. 135-166.