Содержание к диссертации
Введение
Глава I. Комитетная дискриминация бесконечных множеств 18
I.I. Некоторые свойства комитетных конструкций 18
1.2. Системы неравенств, связанные с задачами диск риминации 27
1.3. Отделение квазиполиэдрального множества 37
Глава II. Синтез обучаемых методов оптимального плани рования с использованием процедур дискриминантного анализа 51
2.1. Смешанные системы неравенств и методы их решения 51
2.2. Комитет несовместной смешанной системы неравенств 71
2.3. Задача математического программирования, содержащая плохо формализуемые ограничения 76
2.4. Модель динамики экономической системы при плохо формализуемых ограничениях 92
2.5. Замечания о вычислительном аспекте предлагаемых алгоритмов 107
Глава III. Идентификация ресурсных ограничений в задаче оптимизации выпуска проката 117
3.1. Постановка задачи 117
3.2. Математическая модель 118
3.3. Метод решения 123
Заключение 129
Литература
- Системы неравенств, связанные с задачами диск риминации
- Комитет несовместной смешанной системы неравенств
- Модель динамики экономической системы при плохо формализуемых ограничениях
- Математическая модель
Введение к работе
Настоящая диссертационная работа посвящена вопросам использования методов распознавания образов для моделирования плохо определенных элементов оптимизационных задач.
Распознавание образов оформилось как самостоятельное научное направление около 20 лет назад. За прошедшие годы были классифицированы задачи распознавания, разработаны математические модели этих задач и методы их решения. В настоящий момент прилагаются усилия к созданию единой теории распознавания образов.
В нашей стране развитие теории распознавания образов связано с именами Э.М.Бравермана, В.Н.Вапника, Ю.И.Журавлева, Н.Г.За-горуйко, М.М.Камилова, Вл.Д.Мазурова, Л.А.Расстригина, В.Н.Фомина, Я.З.Цыпкина и др. Из зарубежных ученых, работающих в этой области, следует отметить Р.Гонсалеса, У.Гренандера, Д.Кэйлора, М.Минского, Н.Нильсона, М.Осборна, Ф.Розенблатта, Р.Такияму, Дж. Ту, С.Эцблоу.
Методы распознавания образов нашли широкое применение для моделирования плохо формализуемых элементов оптимизационных задач: целевой функции, ограничений, предпочтений и т.д. Эти методы позволяют целенаправленно структуризовать информацию, получаемую в результате опытов и экспертиз и использовать ее для моделирования указанных элементов.
На существование плохо формализуемых факторов и важность их учета в моделях прирожных, технологических, экономических и других процессов, указывается в работах Ю.И.Журавлева [17] , Вл.Д. Мазурова [I, 32, 33], Н.Н.Моисеева [28, 39], Ю.М.Свирежева [23] и других авторов. В работах Ю.И.Журавлева [ 12, I7J с точки зрения плохой формализуемости рассматриваются задачи распознавания образов и изучается вопрос построения корректных алгоритмов для
5 таких задач.
В данной диссертационной работе рассматривается учет плохо формализуемых ограничений в моделях экономических систем. Под ними понимаются такие ограничения, точное аналитическое описание которых неизвестно. Информация об этих ограничениях может быть получена при помощи разного рода экспертиз. В частности, эта информация может включать в себя примеры допустимых и недопустимых состояний объекта оптимизации, а также различные экспертные оценки величин, характеризующих плохо формализуемые ограничения. Отсутствие аналитического описания затрудняет учет этих ограничений в процессе оптимизации. Однако решение, полученное без их учета, может оказаться лишенным содержательного смысла или нереализуемым.
Идентификация плохо формализуемых ограничений методами регрессионного типа [2] часто бывает затруднена, поскольку эти методы требуют достаточно достоверного значения значений функций, задающих плохо формализуемые ограничения.
В работах Б.Б.Розина [46, 47] для моделирования плохо обусловленных зависимостей предлагаются методы, включающие процедуры таксономии. Однако в применении к задаче моделирования плохо формализуемых ограничений эти методы в большей мере ориентированы на определение допустимости или недопустимости некоторого плана по плохо формализуемым ограничениям, чем на получение аналитического описания этих ограничений.
В данной работе для учета плохо формализуемых ограничений предлагается включение в процесс оптимизации процедур обучения распознаванию образов. Материалом обучения при этом служат примеры состояний оптимизируемой системы, для которых посредством экспертиз установлена допустимость или недопустимость по плохо формализуемым ограничениям. С помощью методов дискриминантного анализа строится правило, классифицирующее состояния получаемого объекта, входящие в материал обучения, в соответствии с классификацией, проводимой экспертом.
Это правило выбирается в качестве приближенной модели плохо формализуемых ограничений. Оптимальный план задачи, построенной с использованием этой приближенной модели, предъявляется эксперту для анализа. Поскольку построенная модель плохо формализуемых ограничений будет являться в большинстве случаев достаточно грубой, трудно ожидать сразу высокого качества решения. Поэтому полученный план пополняет материал обучения, и процесс построения модели плохо формализуемых ограничений повторяется. Таким образом, организуется итерационная процедура решения оптимизационной задачи, где на каждом шаге пополняется материал обучения и уточняется модель плохо формализуемых ограничений.
Методы, построенные по такой схеме,называются в данной работе обучаемыми. Впервые идея такого подхода, т.е. использования комплексных методов, включающих процедуры математического программирования и распознавания образов, в явном виде была сформулирована ^по-видимому^в работах [29, 30]В.Д.Мазурова. Подробное изложение этого подхода и некоторых реализующих его алгоритмов приведено в [ю].
Таким образом, в связи с построением обучаемых методов оптимизации оказывается необходимым построение процедур дискриминант-ного анализа. В данной работе рассматривается постановка задачи дискриминантного анализа с использованием аппарата линейных неравенств. Систематическое и глубокое изложение теории линейных неравенств приведено в монографии С.НЛерникова [54]. В используемой постановке [зі] задача дискриминантного анализа есть по сути дела задача решения системы линейных неравенств, которая однозначно определяется разделяемыми множествами. Эта система мо- жет быть конечной или бесконечной в зависимости от того, конечны или бесконечны разделяемые множества. Совместность этой системы эквивалентна линейной разделимости множеств. В случае линейной не разделимости понятие комитета система неравенств позволяет говорить о комитетном разделении f28j.
Понятие комитета системы неравенств было введено в [56, 57] Эйблоу и Кэйлором. Дальнейшее развитие комитетных методов в распознавании образов связано s нашей стране с работами Вл.Д.Мазурова [27] и В.Н.Фомина [53], за рубежом - с исследованиями Н.Ниль-сона [4-і], М.Осборна [59J , Р.Такиямы [60, 61] . Вл.Д.Мазуровым были, в частности, получены условия существования комитета конечной системы линейных неравенств и сформулированы условия коми-тетной разделимости конечных множеств. Оказывается, всякие два непересекающиеся конечные множества векторов пространства К разделимы комитетом аффинных функций. Вопросы корректности комитетных алгоритмов подробно изучены в работах Ю.И.Журавлева [13-I6J.
Интерес к комитетной дискриминации бесконечных множеств обусловлен следующими причинами. Во-первых, в большинстве задач, и в частности, в обучаемых методах оптимизации, обучающая последовательность постоянно пополняется и потому может рассматриваться как потенциально бесконечная.
Во-вторых, обычно в задачах дискриминантного анализа конечные разделяемые множества суть некоторые подмножества множества всех возможных ситуаций. Так, например, если вектор. X <= К отража ет состояние некоторой системы, X - К - множество всех возможных состояний, то А , как правило, бесконечно. Если все возможные состояния системы делятся на 2 типа, то есть л'П^ то множества п и D обычно тоже бесконечны. Чаще всего эти множества неизвестны, известны лишь конечные их подмножества
, и комитетная конструкция, разделяющая hi и Df выбирается в качестве некоторого приближения комитетной конструкции, разделяющей множества Н и о . В связи с этим встает вопрос о существовании разделяющей комитетной конструкции для двух произвольных бесконечных множеств, то есть вопрос оценки широты класса комитетно разделимых бесконечных множеств.
В-третьих, по-видимому, мыслимы ситуации, когда материал обучения может включать бесконечные множества точек. Так, например, в описанном выше случае может быть известно, что все векторы, лежащие в некоторой области, относятся к одному и тому же типу. Это диктует необходимость изучения возможности построения алгоритмов установления комитетной разделимости и нахождения разделяющих комитетных конструкций для бесконечных множеств.
Комитетная дискриминация бесконечных множеств рассматривалась А.И.Кривоноговым в f25J. Некоторым новым результатам в этой области посвящена глава I настоящей работы.
Дадим теперь краткий обзор результатов работы по главам.
Системы неравенств, связанные с задачами диск риминации
В данном параграфе задача комитетной дискриминации подмножеств пространства К рассматривается как задача нахождения комитета или Z -решения некоторой системы линейных неравенств под пространством К вида где Л - К . Множество л будем называть индексным множеством системы (I.2.I). Заметим, Н и и - квазиполиэдральные множества, то и множество Л Задача разделения двух подмножеств п и Ъ пространства К при помощи комитетных конструкций, построенных из линейных функций, эквивалентна задаче нахождения -решения системы не равенств вида (I.2.I), где в качестве Л взято множество Л =: л У "О . Аналогично, задача разделения множеств л и О при помощи комитетных конструкций, построенных из аффинных функ ций, эквивалентна задаче нахождения % -решения системы нера венств вида (I.2.I) над К , где в качестве л взято мно жество заметим, что если и множество А являются квазиполиэдральными подмножествами соответственно пространств К и К . Таким образом, изучение возможностей комитетной разделимости квазиполиэдральных множеств оказывается связанным с изучением вопроса существования %. -ре шений систем неравенств вида (I.2.I), где А - квазиполиэдраль ное множество. выпуклое квазиполиэдральное множество. Поставим в соответствие системе (I.2.I) следующую систему неравенств: объединение конечного числа открытых многогранных конусов. В настоящем параграфе мы выделим некоторый класс систем вида (1.2.2), докажем, что системы этого класса всегда обладают комитетом и 2 -решением и установим связь между комитетами систем вида (I.2.I) и систем вида (1.2.2).
Допустим, что система (1.2.2) не обладает решением. Совме стную систему , будем называть совместной подсистемой системы (1.2.2), а множество I индексным множеством этой подсистемы. Пусть 1 Ijifjgft- набор всех индексных множеств совместных подсистем системы (1.2.2).
Определение 1.2.3. Совместная подсистема системы (1.2.2) называется ее максимальной совместной подсистемой или fir -подсистемой, если ее индексное множество является максимальным по включению элементом множества [ Іі] еД
Обозначим через всех индексных множеств несовместных подсистем системы (1.2.2).
Определение 1.2.4-. Несовместная подсистема системы (1.2.2) называется ее минимальной несовместной подсистемой или V -подсистемой, если ее индексное множество является минимальным по включению элементом множества
Определение 1.2.5. Несовместная система неравенств вида (1.2.2) называется конечно противоречивой, если число различных ее Us -подсистем конечно. Следующая теорема дает представление о виде произвольной jt -подсистемы конечно противоречивой системы неравенств. Теорема I.2.I. Система (1.2.2) конечно противоречива тогда и только тогда, когда индексное множество / всякой ее fJL,-подсистемы есть объединение некоторых множеств из (A; Jfeiln.
Доказательство. Достаточность условия очевидна в силу того, что существует лишь конечное число различных наборов множеств из
Докажем необходимость условия. Допустим, что индексное множество I некоторой ft -подсистемы (1.2.2) указанным свойством не обладает. Пусть У - некоторое решение этой JU- -подсистемы, то есть выполнено (,4) 0 (VX/J По нашему допущению, для некоторого / i,/n найдутся такие Х и Хг из Д/ » чт0 Х,е Xjrt?, Х то есть (,,г[) 0, (XL ) 0 - При некотором неотрицательном Л вектор Хс - АХ1 + (і X)Xt удовлетворяет условию (Хо,4} = U , причем в силу выпуклости множества X: вектор Х0 принадлежит
Возьмем последовательность неотрицательных чисел монотонно сходящуюся к нулю. Заметим, что для всех І , поскольку У , так что для всех к вектор Xo k Поскольку ї/ представляет собой индексное множество некоторой совместной подсистемы системы (1.2.2), то каждое из может быть дополнено до индексного множества некоторой ft -подсистемы (1.2.2).
Комитет несовместной смешанной системы неравенств
Непосредственно из рассмотрения смешанной системы неравенств (2.1.18) легко заметить, что при подстановке в нее фиксированных векторов ym=(Umt Z ) , где фиксированный вектор система стано вится системой линейных неравенств относительно переменных
Справедливость доказываемого утвержде ния следует из того, что множество /б есть проекция множества решений этой системы на пространство переменной К
В параграфе 2.3 будут приведены условия, при которых структура множества Ау существенно упрощается. Там же результаты данного параграфа будут применены для построения обучаемых процедур оптимизации.
В предыдущем параграфе были описаны системы неравенств, названные нами смешанными, и приведены условия их совместности. Однако в ряде случаев смешанная система может быть несовместной, т.е. не обладать решением. Эта ситуация может возникнуть, например, вследствие несовместности системы всех неравенств прямого вида, входящих в смешанную систему или несовместности системы всех неравенств сопряженного вида. Может случиться также, что обе упомянутые выше системы совместны, однако никакой набор их решений не удовлетворяет неравенствам смешанного вида.
Исходя из этого, в настоящем параграфе будет дано определение комитета смешанной системы неравенств и указаны условия его существования. Понятие комитета смешанной системы неравенств аналогично понятию комитета системы линейных неравенств [34-j. Представляется естественным, чтобы в случае совместности системы всех неравенств прямого вида, входящих в смешанную систему построение комитета смешанной системы сводилось бы по сути дела к построению комитета системы неравенств сопряженного вида и наоборот, а также чтобы в случае совместности смешанной системы всякое ее решение могло рассматриваться как частный случай комитета. Исходя из этого нами принято следующее определение комитета смешанной системы.
Получим необходимые и достаточные условия существования комитета для смешанных систем, описанных в предыдущем параграфе. Ограничимся как и прежде рассмотрением линейных смешанных систем с фазовым пространством д = R и пространством г/ аффинных функций
Доказательство. Необходимость условия с очевидностью следует из условий существования комитета однородной системы линейных неравенств. Докажем достаточность условия. Пусть условие теоремы выполнено. Тогда, согласно з4], для каждого /71 П существует комитет следующей системы линейных неравенств:
Под задачей математического программирования с плохо формализуемыми ограничениями мы будем понить следующую задачу: найти причем функции {filial известны, а функции отвечают плохо формализуемым ограничениям и их аналитическое описание неизвестно. Такая постановка совпадает с приведенной, например, в [ю] . Хотя конкретный вид функций (Оп Ц неизвестен, но можно считать, что об этих функциях имеется некоторая информация, которая может быть следующей.
Будем также предполагать, что информация, описанная в пунктах 1-3, всегда присутствует, а наличие информации, описанной в пункте 4- не обязательно. На основании информации, описанной в пунктах 1-3, мы заключаем, что каждая из функций о» есть решение системы неравенств сопряженного вида Аналогично на основании информации, описанной в пункте 4, если таковая имеется, заключаем, что каждая из функций О» является решением системы неравенств сопряженного вида
Определение 2.3.1. Всякую функцию , удовлетворяющую при фиксированном м системе неравенств сопряженного вида (2.3.2) и (2.3.3), будем называть моделью функции 0 Определение 2.3.2. Набор {fiA i моделей функций iQ L будем называть допустимым набором моделей этих функций, если- при подстановке Qt - /L задача (2.3.1) обладает непустым допустимым множеством.
Непосредственно из определения видно, что множество всех допустимых наборов моделей функций, задающих плохо формализуемые ограничения в задаче (2.3.1), совпадает с множеством 7ь/ для смешанной системы неравенств (2.3.4-). Множество JY для этой системы есть множество тех векторов фазового пространства, которые являются допустимыми и для какого-либо набора моделей функ Далее везде мы ограничимся рассмотрением случая: JZe класс всех линейных функций, определенных на R (для t bi ), - класс всех аффинных функций, определенных на К (для конечные множества векторов. При этих предположениях каждая из функций й определяется вектором своих коэффициентов Ц К (для t l i) и U — = (( JZJ4\ (для l Lz ). Система (2.3.2) при этом оказывается для каждого 1$ Ь системой линейных неравенств.
Информация, описанная в пункте 4, соответствует сведениям о знаке, величине или отношении коэффициентов функций О , а также об упорядочении векторов из л Uи по величине значения функций. Мы ограничимся рассмотрением случая, когда все б1; аффинные функции, определенные на Ц (для І Ь )инаК (для L і/д ). При этих предположениях для каждого 1& L система (2.3.3) является также системой линейных неравенств.
В случае, если задача (2.3.1) является задачей линейного программирования, система (2.3Л) является линейной смешанной системой неравенств с несколькими сопряженными переменными.
В случае, если \L\ - \) Хл - класс линейных функций, си стема (2.3Л) есть неоднородная смешанная система первого типа. В случае, если Ц / } 5.1 - класс аффинных функций, система (2.3Л) есть неоднородная смешанная система второго типа. Все эти виды смешанных систем рассмотрены в 2.1. Там же описаны множества jtx » -/Lu. » VW Отмечено, что в общем случае множество Уц, имеет достаточно сложную структуру. Следующая теорема дает условия, при которых строение множества существенно упрощается.
Модель динамики экономической системы при плохо формализуемых ограничениях
В данном параграфе рассматривается построение алгоритмов выбора оптимального варианта динамики экономической системы при наличии плохо формализуемых ограничений. Пусть динамика экономической системы состоит в реализации Если задан некоторый функционал or ($,J , оценивающий вариант развития системы, то может быть поставлена задача выбора из всех допустимых траекторий оптимальной, в смысле критерия, задаваемого этим функционалом. Обычно этот функционал является функцией конечного состояния системы, то есть - линейная функция, задача выбора оптимального варианта динамики системы является задачей линейного программирования
Допустим теперь, что включение со б Т плохо формализуемо, то есть множество I аналитически не задано, а известны лишь конечные множества векторов такие, что и класс функционалов X , которому принадлежит функционал, определяющий границу множества I . Будем считать, что ни один из векторов A U 5 не лежит на границе множества I Тогда функционал, описывающий границу множества , ищем среди решений системы неравенств сопряженного вида
Предположим, что і - класс линейных функционалов (это со-ответствует предположению, что множество J должно быть полупространством, граница которого проходит через начало координат), д0 - выпуклое полиэдральное множество, - выпуклые замкнутые многогранные конусы, то есть
Нашей целью в данном параграфе будет получение условий совместности системы (2.4.1), исследование множества ее решений и построение обучаемого алгоритма решения задачи выбора оптимального варианта динамики исследуемого объекта, аналогичного алгоритмам, построенным в 2.3 настоящей работы.
Пусть X - устойчивое решение системы (2Л.2). Тогда X представим в виде кажем возможность разложения вектора X по системе положительными коэффициентами. Обозначим Если искомое разложение найдено. Пусть, например, При малом положительном векторы X = ЭС+ЕХ и являются решениями системы (2Л.2).
В этом разложении . Повторяя описан ную процедуру, получим через некоторое число повторений искомое разложение вектора X по системе векторов Зтим доказано второе утверждение леммы.
Вернемся к рассмотрению системы Пусть Х0 ограниченное замкнутое выпуклое полиэдральное множество, fX cCl совокупность вершин этого множества. Пусть также {XJ}je3 фундаментальная система решений системы фундаментальная система решений системы ylL V фундаментальная система решений системы Но в этом случае множество решений системы неравенств oJ цУ О лежит в гиперплоскости пространства , что противоречит, в силу леммы 2Л.І, линейной строгой разделимости множеств Полученное противоречие доказывает необходимость условий теоремы. Докажем достаточность этих условий. Пусть выполнено условие I. Легко заметить, что при этом условии для некоторого а выполнено неравенство (поскольку Тогда полагаем теперь положить все неравенства (2.4.3) выполнены строго. Это гарантирует их выполнение и при достаточно малых положительных значениях что означает существование нетривиального решения системы (2.4.1).
При V неравенства (2.4.3) выполнены строго, что гарантирует их выполнение при достаточно малых положительных /V /з Это означает существование нетривиального решения системы (2.4.1).
Теорема 2.4.1 дает необходимые и достаточные условия существования нетривиального решения Получим теперь описания проекций множества решений этой системы. Введем, еле дующие обозначения:
Математическая модель
Использование величин с fie з " ; р в качестве коэф фициентов функций 4 4 і 3 позволяет при нахождении в большей мере отклонять от экспертных оценок значе ния менее точно заданных величин. Введение коэффициента Z у\ в функцию (,5 ) позволяет при нахождении 5 в большей мере корректировать значения погрешности экспертных оценок для (Лі , чем для , поскольку, как правило, значения этих п грешностей как и сами значения оценок менее точно заданы для
В силу задача нахождения может решаться как задача минимизации функции где -достаточно большие положительные числа, при ограничениях, задаваемых смешанной системой неравенств (3.2.4).
Согласно результатам 2.1 настоящей работы, допустимое множество этой задачи есть объединение конечного числа выпуклых полиэдральных множеств. Таким образом, в общем случае задача нахо-ждения сводится к решений конечной последовательности задач оптимизации функции на выпуклых полиэдральных множествах. Каждая из этих задач может быть сформулирована в виде задачи линейного программирования.
В нашем случае множества для всех состави ли три плана, реализованные в предплановый период и удовлетворяю щие всем формализованным ограничениям. Поэтому, в силу теоремы 2.3.1 в нашем случае задача выбора (X І , является задачей оптимизации функции X на выпуклом полиэдральном множестве, задаваемом подсистемой всех неравенств сопряженного вида системы (3.2Л). В силу этой же теоремы это полиэдральное множество является прямым произведением выпуклых полиэдральных множеств, каждое из которых есть множество решений t -й группы неравенств сопряженного вида, входящих в смешанную систему (3.2.4).
Анализ этих планов показывает существенное их различие. Так, например, вариант ІУ предусматривает выпуск 57,3 тыс. т осевой заготовки, тогда как согласно варианту У осевая заготовка совсем не выпускается. Вариант У предусматривает вдвое больший выпуск крупносортной стали на РБС, чем вариант ІУ. Еще больше различие плана выпуска конструкционного сорта на РБС согласно варианту У и варианту ІУ. Существенна и разница двойственных оценок. Согласно ІУ варианту плана, в интервалах устойчивости двойственных оценок дополнительное производство рудничных рельсов приведет к росту прибыли на 20,2 руб/т, тогда как согласно варианту У увеличение производства рудничных рельсов сверх запланированного количества нецелесообразно. Более чем в б раз отличаются оценки эффективности изменения объемов выпуска квадратной заготовки. Велика и разница двойственных оценок для ограничений по загрузке оборудования, хотя различие коэффициентов этих ограничений невелико .
Уточнение описания производительности комплекса позволило повысить обоснованность принимаемых плановых решений. Отметим следующие основные результаты данной работы.
В главе I выделен класс бесконечных систем линейных неравенств, обладающих комитетом. На основании этого сформулированы некоторые достаточные условия комитетной разделимости бесконечных множеств пространства К . Эти условия в случае пространства И являются к тому же и необходимыми.
Для задачи отделения квазиполиэдрального множества от дополнения выделены те функции, вхождение которых в любую комитет-ную конструкцию, отделяющую это множество, обязательно. Рассмотрены случаи, когда с использованием только этих функций возможно построение отделяющей комитетной конструкции либо установление комитетной неотделимости исследуемого множества. Приведены примеры комитетно отделимых и комитетно неотделимых множеств.
В главе построены обучаемые алгоритмы оптимизации, включающие процедуры, дискриминантного анализа для идентификации плохо формализуемых ограничений. Развит подход к построению таких алгоритмов с использованием смешанных систем неравенств. В этой связи исследованы различные типы смешанных систем неравенств. Для несовместных смешанных систем неравенств предложено обобщение понятия решения - понятие комитета смешанной системы неравенств. Получены необходимые и достаточные условия существования комитета смешанной системы неравенств. На основании этих результатов построены обучаемые алгоритмы решения задачи математического программирования при плохо формализуемых ограничениях и задачи выбора оптимального варианта динамики экономической системы при плохо формализуемом описании ее технологического множества. Приведены некоторые замечания, касающиеся вычислительного аспекта предлагаемых алгоритмов.
