Формально-логическое моделирование

Формально­логическое моделирование  (фр. modèle, от лат. modulus — «мера, аналог, образец») — это система,  Мод льее исследование которой служит средством для получения информации о другой системе[1],  это упрощённое представление реального устройства и/или протекающих в нём процессов,  явлений. Построение и исследование моделей, то есть моделирование, облегчает изучение  имеющихся в реальном устройстве (процессе, …) свойств и закономерностей. Применяют  для нужд познания (созерцания, анализа и синтеза). Моделирование является обязательной частью исследований и разработок, неотъемлемой  частью нашей жизни, поскольку сложность любого материального объекта и окружающего  его мира бесконечна вследствие неисчерпаемости материи и форм её взаимодействия, —  как внутри себя, так и с внешней средой. Одни и те же устройства, процессы, явления и т. д. (далее — «системы») могут иметь  много разных видов моделей. Как следствие, существует много названий моделей,  большинство из которых отражает решение некоторой конкретной задачи. Ниже приведена  классификация и дана характеристика наиболее общих видов моделей. Требования к моделям[править | править вики­текст] Моделирование всегда предполагает принятие допущений той или иной степени важности.  При этом должны удовлетворяться следующие требования к моделям:  адекватность, то есть соответствие модели исходной реальной системе и учет,  прежде всего, наиболее важных качеств, связей и характеристик. Оценить  адекватность выбранной модели, особенно, например, на начальной  стадии проектирования, когда вид создаваемой системы ещё неизвестен, очень  сложно. В такой ситуации часто полагаются на опыт предшествующих разработок  или применяют определённые методы, например, метод последовательных  приближений;  точность, то есть степень совпадения полученных в процессе моделирования  результатов с заранее установленными, желаемыми. Здесь важной задачей является  оценка потребной точности результатов и имеющейся точности исходных данных,  согласование их как между собой, так и с точностью используемой модели; универсальность, то есть применимость модели к анализу ряда однотипных систем в одном или нескольких режимах функционирования. Это позволяет расширить  область применимости модели для решения большего круга задач;  целесообразная экономичность, то есть точность получаемых результатов и  общность решения задачи должны увязываться с затратами на моделирование. И  удачный выбор модели, как показывает практика, — результат компромисса между  отпущенными ресурсами и особенностями используемой модели;  и др. Выбор модели и обеспечение точности моделирования считается одной из самых важных  задач моделирования. Точность моделей[править | править вики­текст] Погрешности моделирования вызываются как объективными причинами, связанными с  упрощением реальных систем, так и субъективными, обусловленными недостатком знаний  и навыков, особенностями характера того или иного человека. Погрешности можно  предотвратить, компенсировать или учесть. И всегда обязательна оценка правильности  получаемых результатов. В технике быструю оценку точности модели часто проводят  следующими способами:  проверяют соответствие результатов физическому (здравому) смыслу. Удобно это  делать для частного случая модели, когда решение очевидно. Иногда даже говорят,  что ещё перед решением задачи инженер уже должен представлять характер и  порядок ожидаемого результата. Но точность такого представления зависит от  развитости физического воображения и опыта работы с подобными системами;  проверяют выполнение частных очевидных условий задачи, что также позволяет  отсечь неприемлемые решения;  проверяют соблюдение тенденции изменения величин и знаков результатов  (монотонность, цикличность, плавность и т. п.);  проверяют правильность размерности полученного результата (если работа ведется с  аналитическими зависимостями). Известно, что посредством грубых измерений, использования контрольно­измерительных  приборов с низкой точностью или приближенных исходных данных невозможно получить  точные результаты. С другой стороны, бессмысленно вести, например, расчет с точностью  до грамма, если результат потом нужно округлять (скажем, указывать в формуляре) сточностью до ста грамм, или же определять среднюю величину точнее составляющих её  значений, и т. д. Поэтому важно помнить о следующем:  точность результатов расчетов и экспериментальных исследований модели не может  превысить точности исходных данных, используемых приборов, измерительных  инструментов и т. п.;  вид выбираемой модели должен согласовываться с точностью исходных данных и  потребной точностью результатов;  желаемая точность результатов должна соответствовать нуждам и реалиям практики. Основные виды моделей[править | править вики­текст] По способу отображения действительности различают три основных вида моделей —  эвристические, натурные и математические. Эвристические модели[править | править вики­текст] Эвристические модели, как правило, представляют собой образы, рисуемые в  воображении человека. Их описание ведется словами естественного языка  (например,вербальная информационная модель) и, обычно, неоднозначно и субъективно.  Эти модели неформализуемы, то есть не описываются формально­логическими и  математическими выражениями, хотя и рождаются на основе представления реальных  процессов и явлений. Эвристическое моделирование — основное средство вырваться за рамки обыденного и  устоявшегося. Но способность к такому моделированию зависит, прежде всего, от  богатства фантазии человека, его опыта и эрудиции. Эвристические модели используют на  начальных этапах проектирования или других видов деятельности, когда сведения о  разрабатываемой системе ещё скудны. На последующих этапах проектирования эти модели заменяют на более конкретные и точные. Натурные модели[править | править вики­текст] Отличительной чертой этих моделей является их подобие реальным системам (они  материальны), а отличие состоит в размерах, числе и материале элементов и т. п. По  принадлежности к предметной области модели подразделяют на следующие:  Физические модели. Ими являются реальные изделия, образцы, экспериментальные и натурные модели, когда между параметрами системы и модели одинаковой  физической природы существует однозначное соответствие. Выбор размеров такихмоделей ведётся с соблюдением теории подобия. Физические модели  подразделяются на объёмные (модели и макеты) и плоские (тремплеты):  в данном случае под (физической) моделью понимают изделие или устройство, являющееся упрощённым подобием исследуемого объекта или позволяющее  воссоздать исследуемый процесс или явление. Например, предметные модели,  как уменьшенные копии оригинала (глобус как модель Земли, игрушечный  самолёт с учётом его аэродинамики);  под тремплетом[2] понимают изделие, являющееся плоским масштабным  отображением объекта в виде упрощённой ортогональной проекции или его  контурным очертанием. Тремплетеотанарные вырезают из плёнки, картона  и т. п., и применяют при исследовании и проектировании зданий, установок,  сооружений;  под макетом понимают изделие, собранное из моделей и/или тремплетов. Физическое моделирование — основа наших знаний и средство проверки наших гипотез и  результатов расчётов. Физическая модель позволяет охватить явление или процесс во всём  их многообразии, наиболее адекватна и точна, но достаточно дорога, трудоёмка и менее  универсальна. В том или ином виде с физическими моделями работают на всех этапах  проектирования;  Технические модели;  Социальные модели;  Экономические модели, например, Бизнес­модель;  и т. д. Математические модели[править | править вики­текст] Основная статья: Математическая модель Математические модели — формализуемые, то есть представляют собой совокупность  взаимосвязанных математических и формально­логических выражений, как правило,  отображающих реальные процессы и явления (физические, психические, социальные  и т. д.). По форме представления бывают:  аналитические модели. Их решения ищутся в замкнутом виде, в виде  функциональных зависимостей. Удобны при анализе сущности описываемогоявления или процесса и использовании в других математических моделях, но  отыскание их решений бывает весьма затруднено;  численные модели. Их решения — дискретный ряд чисел (таблицы). Модели  универсальны, удобны для решения сложных задач, но не наглядны и трудоемки при  анализе и установлении взаимосвязей между параметрами. В настоящее время такие  модели реализуют в виде программных комплексов — пакетов программ для расчета на компьютере. Программные комплексы бывают прикладные, привязанные к  предметной области и конкретному объекту, явлению, процессу, и общие,  реализующие универсальные математические соотношения (например, расчет  системы алгебраических уравнений);  формально­логические информационные модели — это модели, созданные на  формальном языке. Например:  модель формальной системы в математике и логике как  любая совокупность объектов, свойства которых и отношения между которыми  удовлетворяют аксиомам и правилам вывода формальной системы, служащей тем  самым совместным (неявным) определением такой совокупности;  модель в теории алгебраических систем как совокупность некоторого множества и  заданных на его элементах свойств и отношений;  эталонная модель. Построение математических моделей возможно следующими способами (более  подробно — см. Математическая модель):  аналитическим путём, то есть выводом из физических законов, математических  аксиом или теорем;  экспериментальным путём, то есть посредством обработки  результатов эксперимента и подбора аппроксимирующих (приближённо  совпадающих) зависимостей. Математические модели более универсальны и дешевы, позволяют поставить «чистый»  эксперимент (то есть в пределах точности модели исследовать влияние какого­то  отдельного параметра при постоянстве других), прогнозировать развитие явления или  процесса, отыскать способы управления ими. Математические модели — основа  построения компьютерных моделей и применения вычислительной техники.Результаты математического моделирования нуждаются в обязательном сопоставлении с  данными физического моделирования — с целью проверки получаемых данных и для  уточнения самой модели. С другой стороны, любая формула — это разновидность модели  и, следовательно, не является абсолютной истиной, а всего лишь этап на пути её познания. Промежуточные виды моделей[править | править вики­текст] К промежуточным видам моделей можно отнести: Трёхмерная компьютерная модель  графические модели. Занимают промежуточное место между эвристическими и  математическими моделями. Представляют собой различные изображения:  графы;  схемы;  эскизы. Этому упрощенному изображению некоторого устройства в  значительной степени присущи эвристические черты;  чертежи. Здесь уже конкретизированы внутренние и внешние связи  моделируемого (проектируемого) устройства, его размеры;  графики;  полигональная модель в компьютерной графике как образ объекта, «сшитый»  из множества многоугольников.  аналоговые модели. Позволяют исследовать одни физические явления или  математические выражения посредством изучения других физических явлений,  имеющих аналогичные математические модели. В качестве примера можно привести  метод динамических аналогий, широко применяемый  в акустике (электроакустические аналогии), а также в механике;  и др.Существует и другие виды «пограничных» моделей, например, экономико­ математическая и т. д. Выбор типа модели зависит от объема и характера исходной информации о  рассматриваемом устройстве и возможностей инженера, исследователя. По возрастанию  степени соответствия реальности модели можно расположить в следующий ряд:  эвристические (образные) — математические — натурные (экспериментальные). Уровни моделей[править | править вики­текст] Количество параметров, характеризующих поведение не только реальной системы, но и её  модели, очень велико. Для упрощения процесса изучения реальных систем выделяют  четыре уровня их моделей, различающиеся количеством и степенью важности учитываемых свойств и параметров. Это — функциональная, принципиальная, структурная и  параметрическая модели. Функциональная модель[править | править вики­текст] Функциональная модель предназначена для изучения особенностей работы  (функционирования) системы и её назначения во взаимосвязи с внутренними и внешними  элементами. Функция — самая существенная характеристика любой системы, отражает её  предназначение, то, ради чего она была создана. Подобные модели оперируют, прежде  всего, с функциональными параметрами. Графическим представлением этих моделей  служат блок­схемы. Они отображают порядок действий, направленных на достижение  заданных целей (т. н. 'функциональная схема'). Функциональной моделью  является абстрактная модель. Модель принципа действия[править | править вики­текст] Модель принципа действия (принципиальная модель, концептуальная модель)  характеризует самые существенные (принципиальные) связи и свойства реальной системы.  Это — основополагающие физические, биологические, химические, социальные и т. п.  явления, обеспечивающие функционирование системы, или любые другие принципиальные  положения, на которых базируется планируемая деятельность или исследуемый процесс.  Стремятся к тому, чтобы количество учитываемых свойств и характеризующих их  параметров было небольшим (оставляют наиболее важные), а обозримость модели —  максимальной, так чтобы трудоемкость работы с моделью не отвлекала внимание от  сущности исследуемых явлений. Как правило, описывающие подобные модели  параметры — функциональные, а также физические характеристики процессов и явлений.Принципиальные исходные положения (методы, способы, направления и т. д.) лежат в  основе любой деятельности или работы. Так, принцип действия технической системы — это последовательность выполнения  определённых действий, базирующихся на определённых физических  явлениях (эффектах), которые обеспечивают требуемое функционирование этой системы. Примеры моделей принципа действия: фундаментальные и прикладные науки (например,  принцип построения модели, исходные принципы решения задачи), общественная жизнь  (например, принципы отбора кандидатов, оказания помощи), экономика (например,  принципы налогообложения, исчисления прибыли), культура (например, художественные  принципы). Работа с моделями принципа действия позволяет определить перспективные направления  разработки (например, механика или электротехника) и требования к возможным  материалам (твердые или жидкие, металлические или неметаллические, магнитные или  немагнитные и т. д.). Правильный выбор принципиальных основ функционирования предопределяет  жизнеспособность и эффективность разрабатываемого решения. Так, сколько бы ни  совершенствовали конструкцию самолета с винтомоторным двигателем, он никогда не  разовьет сверхзвуковую скорость, не говоря уже о полетах на больших высотах. Только  использование другого физического принципа, например, реактивного движения и  созданного на его основе реактивного двигателя, позволит преодолеть звуковой барьер. Графическим представлением моделей принципа действия служат блок­ схема, функциональная схема, принципиальная схема. Например, для технических моделей эти схемы отражают процесс преобразования  вещества, как материальной основы устройства, посредством определённых  энергетических воздействий с целью реализации потребных функций (функционально­ физическая схема). На схеме виды и направления воздействия, например, изображаются  стрелками, а объекты воздействия — прямоугольниками. Структурная модель[править | править вики­текст] Четкого определения структурной модели не существует. Так, под структурной  моделью устройства могут подразумевать: структурную схему, которая представляет собой упрощенное графическое  изображение устройства, дающее общее представление о форме, расположении и  числе наиболее важных его частей и их взаимных связях;  топологическую модель, которая отражает взаимные связи между объектами, не  зависящие от их геометрических свойств. Под структурной моделью процесса обычно подразумевают характеризующую его  последовательность и состав стадий и этапов работы, совокупность процедур и  привлекаемых технических средств, взаимодействие участников процесса. Например, — это могут быть упрощенное изображение звеньев механизма в виде стержней, плоских фигур (механика), прямоугольники с линиями со стрелками (теория  автоматического управления, блок­схемы алгоритмов), план литературного произведения  или законопроекта и т. д. Степень упрощения зависит от полноты исходных данных об  исследуемом устройстве и потребной точности результатов. На практике виды  структурных схем могут варьироваться от несложных небольших схем (минимальное число частей, простота форм их поверхностей) до близких к чертежу изображений (высокая  степень подробности описания, сложность используемых форм поверхностей). Возможно изображение структурной схемы в масштабе. Такую модель относят  к структурно­параметрической. Её примером служит кинематическая схема механизма,  на которой размеры упрощенно изображенных звеньев (длины линий­стержней, радиусы  колес­окружностей и т. д.) нанесены в масштабе, что позволяет дать численную оценку  некоторым исследуемым характеристикам. Для повышения полноты восприятия на структурных схемах в символьном (буквенном,  условными знаками) виде могут указывать параметры, характеризующие свойства  отображаемых систем. Исследование таких схем позволяет установить соотношения  (функциональные, геометрические и т. п.) между этими параметрами, то есть представить  их взаимосвязь в виде равенств f (x1, х2, …) = 0, неравенств f (x1, х2, …) > 0 и в иных  выражениях. Параметрическая модель[править | править вики­текст] Под параметрической моделью понимается математическая модель, позволяющая  установить количественную связь между функциональными и вспомогательными  параметрами системы. Графической интерпретацией такой модели в технике служит  чертеж устройства или его частей с указанием численных значений параметров. Классификация моделей[править | править вики­текст]По целям исследований[править | править вики­текст] В зависимости от целей исследования выделяют следующие модели:  функциональные. Предназначены для изучения особенностей работы  (функционирования) системы, её назначения во взаимосвязи с внутренними и  внешними элементами;  функционально­физические. Предназначены для изучения физических (реальных)  явлений, используемых для реализации заложенных в систему функций;  модели процессов и явлений, такие как кинематические, прочностные, динамические и другие. Предназначены для исследования тех или иных свойств и характеристик  системы, обеспечивающих её эффективное функционирование. По особенностям представления[править | править вики­текст] С целью подчеркнуть отличительную особенность модели их подразделяют на простые и  сложные, однородные и неоднородные, открытые и закрытые, статические и динамические,  вероятностные и детерминированные и т. д. Стоит отметить, что когда говорят, например,  о техническом устройстве как простом или сложном, закрытом или открытом и т. п., в  действительности подразумевают не само устройство, а возможный вид его модели, таким  образом подчеркивая особенность состава или условий работы.  Четкого правила разделения моделей на сложные и простые не существует.  Обычно признаком сложных моделей служит многообразие выполняемых функций,  большое число составных частей, разветвленный характер связей, тесная взаимосвязь с внешней средой, наличие элементов случайности, изменчивость во времени и  другие. Понятие сложности системы — субъективно и определяется необходимыми  для его исследования затратами времени и средств, потребным уровнем  квалификации, то есть зависит от конкретного случая и конкретного специалиста.  Разделение систем на однородные и неоднородные проводится в соответствии с  заранее выбранным признаком: используемые физические явления, материалы,  формы и т. д. При этом одна и та же модель при разных подходах может быть и  однородной, и неоднородной. Так, велосипед — однородное механическое  устройство, поскольку использует механические способы передачи движения, но  неоднородное по типам материалов, из которых изготовлены отдельные части  (резиновая шина, стальная рама, пластиковое седло). Все устройства взаимодействуют с внешней средой, обмениваются с нею сигналами,  энергией, веществом. Модели относят к открытым, если их влиянием на  окружающую среду или воздействием внешних условий на их состояние и качество  функционирования пренебречь нельзя. В противном случае системы рассматривают  как закрытые, изолированные.  Динамические модели, в отличие от статических, находятся в постоянном  развитии, их состояние и характеристики изменяются в процессе работы и с  течением времени.  Характеристики вероятностных (иными словами, стохастических) моделей  случайным образом распределяются в пространстве или меняются во времени. Это  является следствием как случайного распределения свойств материалов,  геометрических размеров и форм объекта, так и случайного характера воздействия  внешних нагрузок и условий. Характеристики детерминированных моделей заранее  известны и точно предсказуемы. Знание этих особенностей облегчает процесс моделирования, так как позволяет выбрать  вид модели, наилучшим образом соответствующей заданным условиям. Этот выбор  основывается на выделении в системе существенных и отбрасывании второстепенных  факторов и должен подтверждаться исследованиями или предшествующим опытом.  Наиболее часто в процессе моделирования ориентируются на создание простой модели,  что позволяет сэкономить время и средства на её разработку. Однако повышение точности  модели, как правило, связано с ростом её сложности, так как необходимо учитывать  большое число факторов и связей. Разумное сочетание простоты и потребной точности и  указывает на предпочтительный вид модели. ЛОГИЧЕСКОЕ МОДЕЛИРОВАНИЕ СИСТЕМ С ПОСЛЕДОВАТЕЛЬНО­ ПАРАЛЛЕЛЬНОЙ СТРУКТУРОЙ 05.13.18 ­ Математическое моделирование, численные методы и комплексы программ Автореферат диссертации на соискание ученой степени кандидата технических наук Саратов 2004 Работа выполнена в Саратовском государственном техническом университетеНаучный руководитель: кандидат технических наук, доцент Большаков Александр Афанасьевич Официальные оппоненты: доктор технических наук, профессор Кушников Вадим Алексеевич доктор физико­математических наук, профессор Ушаков Николай Михайлович Ведущая организация: Институт проблем точной механики и управления РАН, г. Саратов Защита состоится 13 апреля 2004 г. в 15 часов 00 минут на заседании диссертационного  совета Д 212.242.08 при Саратовском государственном техническом университете (410054, г. Саратов, ул. Политехническая, 77, корп. 2, ауд. 322). С диссертацией можно ознакомиться в научно­технической библиотеке Саратовского  государственного технического университета. Автореферат разослан «12» марта 2004 г. Ученый секретарь диссертационного совета ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ Актуальность темы. Задачи выбора оптимального варианта из конечного набора  альтернатив являются важными как в теоретическом,, так и в прикладном значении. К их  числу относятся так называемые многоиндексные, в том числе трехиндексные задачи о  назначениях, которые до сих пор недостаточно глубоко исследованы. Они принадлежат к  классу наиболее трудных с вычислительной точки зрения задач дискретной оптимизации,  имеющих экспоненциальную (NP) вычислительную сложность (Емеличев В.А., Ковалев  М.М., Кравцов М . М , (1981)). NP­полнота данных задач обусловливает необходимость  поиска и разработки приближенных алгоритмов их решения. Для исследования задач о назначениях и разработки приближенных схем их решения  наиболее часто используемым является метод исследования на графах. Характерными  являются работы Э.Х. Гимади, A.И. Сердюкова (1999), Н.М. Кайрана (2000), Н.М. Коркишко (2003) и др., в которых  алгоритмы решения разработаны для задач малой размерности.В связи с этим актуальной является разработка альтернативных методов решения  трехиндексной задачи о назначениях. Для этого предлагается использовать новый подход с  последующим применением методов теории расписаний. Одним из способов решения проблемы оптимального расписания (плана) и связанной с ней  большой размерности является применение структурно­логического метода исследования  систем. Этот подход заключается в использовании математического аппарата непрерывной  логики (НЛ) и логических определителей (ЛО), которые представляют собой своеобразные экстремальные числовые характеристики прямоугольных матриц. Это позволяет  разработать эффективные алгоритмы, вычислительная сложность которых растет как  полиномы невысокой степени от размера задачи. При этом полный перебор всех вариантов  заменяется частичным меньшего объема, что позволяет проводить оптимизационные  исследования системы, т.е. осуществлять качественный анализ получаемых решений. Общие положения и теоретические основы этого метода разработаны B.И. Левиным (1979) и получили развитие в работах А.Ф. Буланова (1981), C.А. Лысаха (1983), И.Ю. Мирецкого (1987) и других ученых. Особенность данного метода заключается в необходимости развития и доработки математического аппарата  непрерывной логики и логических определителей для конкретного класса задач  дискретной оптимизации. Применение структурно­логического метода исследования  систем для разработки алгоритмов решения рассматриваемого в данной диссертационной  работе класса задач выражает большую благодарность за плодотворное сотрудничество и научные  консультации проф. Левину В.И. Все это обусловливает актуальность диссертационной темы, выбор подхода к  исследованию, а также определяет его цели и задачи. Предметом исследования является проблема оптимизации работы последовательно­ параллельной системы обслуживания. В терминах и представлениях трехиндексной задачи  о назначениях подобная система описывается следующим образом. Последовательно­ параллельная система обслуживания представляет собой N параллельно соединенных  ветвей, характеризующихся быстродействием, и способных выполнять одновременно N  однотипных работ. Каждая ветвь предназначена для последовательного выполнения двух  работ и представляет собой цепочку из последовательно соединенных блоков, которые  осуществляют операции, составляющие работу. Имеется 2N работ, характеризующихся  издержками на их выполнение в ветвях системы. Необходимо выбрать оптимальный  порядок подачи работ в ветви системы, минимизирующий общее время выполнениякомплекса работ. При этом применяются следующие допущения: 1) абсолютная  надежность всех блоков системы обслуживания; 2) для каждой работы задается множество составляющих ее операций, порядок выполнения которых предписывается некоторым  заданным отношением порядка; 3) в любой момент времени, каждый блок может  выполнять не более одной операции; 4) первые N работ подаются в систему одновременно. Целью работы является создание адекватных математических моделей функционирования  последовательно­параллельной системы обслуживания, сформулированной в виде  трехиндексной задачи о назначениях как при детерминированных, так и при  недетерминированных (интервальных) параметрах функционирования системы,  исследование с помощью этих моделей задачи синтеза оптимальных и приближенно­ оптимальных расписаний (планов), разработка эффективных приближенных алгоритмов  решения задачи. Для достижения этой цели необходимо решить следующие задачи. • Развить математический аппарат непрерывной логики и логических определителей с  учетом специфики рассматриваемого класса задач теории расписаний. • Разработать приближенный метод оптимизации формальнологических моделей системы и применить его к построению эффективных приближенно­оптимальных алгоритмов  решения задачи произвольной размерности. Методы исследования. В работе использовались методы алгебры непрерывной логики и  логических определителей, теории множеств, теории г алгоритмов, исследования  операций, в том числе теории расписаний, теории графов, статистического моделирования, математического  программирования и комбинаторного анализа. Достоверность и обоснованность научных положений и результатов исследований  подтверждаются корректностью применения апробированного математического аппарата  непрерывной логики и логических определителей, а также аппарата теории вероятностей,  математической статистики, и согласованностью результатов теоретических расчетов с  данными, полученными экспериментальным путем автором и другими исследователями. На защиту выносятся: 1. Формально­логические модели, которые представляют собой матричные структуры и  позволяют адекватно описать функционирование последовательно­параллельных систем  для трехиндексной задачи о назначениях.2. Метод, основанный на непрерывной логике и логических определителях, который  позволяет эффективно проводить оптимизационные исследования задачи как при  детерминированных, так и при недетерминированных (интервальных) параметрах  функционирования системы на основе единого подхода. 3. Условия существования решения недетерминированной трехиндексной задачи о  назначениях, связанные с недетерминированностью параметров системы, а также структура множества всех решений рассматриваемой задачи с интервальной матрицей  коэффициентов. 4. Методика оптимизационных исследований рассматриваемых систем как при  детерминированных, так и при недетерминированных (интервальных) параметрах ее  функционирования, основанная на анализе разработанных формально­логических моделей  систем. 5. Эффективные алгоритмы получения приближенно оптимальных решений задачи  произвольной размерности. Научная новизна. В ходе выполнения работы получены следующие новые результаты: 1. Разработаны формально­логические модели функционирования последовательно­ параллельной системы в терминах и представлениях трехиндексной задачи о назначениях  как при детерминированных, так и при недетерминированных (интервальных) параметрах  ее функционирования, позволяющие адекватно представлять заданную о системе  информацию в компактной, обозримой форме, что важно для решения проблемы большой  размерности при исследовании системы и разработки оптимизационных алгоритмов. 2. Сформулированы и исследованы связанные с недетерминированностью условия  существования задачи при интервальной неопределенности параметров функционирования  системы. 3. Разработаны оригинальные аппарат и метод оптимизационных исследований  рассматриваемой системы, основанные на анализе полученных формально­логических  моделей, позволяющие осуществлять качественный анализ решений при варьировании  исходных данных. 4. Созданы эффективные алгоритмы синтеза приближенно оптимальных расписаний для  задач произвольной размерности. Практическая ценность. Использование предлагаемых методик и теоретических разработок расширяет круг решаемых оптимизационных задач. Полученные аналитические результаты  позволяют строить легко реализуемые на ЭВМ эффективные алгоритмы полученияприближенно­оптимальных решений трехиндексной задачи о назначениях как при  детерминированных, так и при недетерминированных (интервальных) параметрах, которые  могут использоваться, в частности, при создании оптимизационных модулей экспертных  систем. Реализующая данные алгоритмы экспертная система моделирования экологии  транспортно­экспедиторской компании используется в Пешенском областном управлении  инкассации, внедрена в учебный процесс Пензенской государственной  сельскохозяйственной академии. Апробация работы. Основные результаты диссертационной работы были доложены и  обсуждены на Всероссийских, международных научно­технических, научно­практических  конференциях и совещаниях «Непрерывная логика и ее применение в технике, экономике и социологии» (Пенза, 1994); «Экологическая безопасность и социально­экономическое  развитие регионов России» (Саранск, 1994); «New Information Technologies and Systems»  (Penza, Russia, 1994); «Непрерывно­логические и нейронные сети и модели» (Ульяновск,  1995); «Непрерывно­логические методы и модели в науке, технике и экономике» (Пенза,  1995); «Информационные технологии и системы» (Воронеж, 1995); «Экологическая  безопасность регионов России» (Пенза, 1996); «Применение баз данных» (Пенза, 1997);  «Непрерывная и смежная логики в информатике, экономике и социологии» (Пенза, 1997);  «Математические методы и информационные технологии в экономике, социологии и  образовании» (Пенза, 2001); «Математические ­методы в технике и технологиях» (Ростов­ на­Дону, 2003); «Компьютерное моделирование и информационные технологии в науке,  инженерии, образовании» (Пенза, 2003). Публикации. По теме диссертации опубликованы 13 печатных работ, перечисленных в  конце автореферата. Структура работы. Диссертация общим объемом 141 страница состоит из введения,  четырех глав, заключения, списка использованной литературы из 119 наименований и  приложений, содержит 8 рисунков, 12 таблиц. Приложения содержат акты о внедрении и  доказательства теорем. СОДЕРЖАНИЕ РАБОТЫ Во введении показаны актуальность работы, научная новизна и практическая значимость.  Здесь же сформулированы цель и задачи диссертационной работы, выделены новые  результаты, приводятся основные положения, выносимые на защиту. В первой главе рассмотрено современное состояние вопросов, связанных с  оптимизационными исследованиями функционирования последовательно­параллельныхсистем, приводящих к задачам распределения во времени ограниченных ресурсов,  предназначенных для выполнения различных видов работ. Дается аналитический обзор решения задач, существующих моделей и методов их решения, таких как метод исследования на графах, метод ветвей и границ, статистическое  моделирование, методы математического программирования. Анализ литературы показал, что существующие формулировки трехиндексной задачи о  назначениях имеют формальный характер, в то время как ряд содержательных постановок,  в частности логистических задач, не имеют оптимизационных формулировок и  математических моделей. Также в рассмотренных работах отмечается, что большинство математических задач  распределения, составления плана, сопоставления и трехиндексная задача о назначениях, в  частности, относятся к наиболее трудным с вычислительной точки зрения задачам  дискретной оптимизации, так называемым ^ ­сложным задачам. Задачи дискретной  оптимизации считают эффективно решаемыми, если для них имеется алгоритм с  полиномиальными оценками времени и памяти. Это означает, что время работы и память  этих алгоритмов растут не быстрее, чем степенные функции при увеличении размерности  задачи. ^ ­ полнота рассматриваемой задачи обусловливает необходимость поиска и  разработки приближенных алгоритмов решения. Отличительной особенностью существующих методов решения трехиндексной задачи о  назначениях является ориентированность алгоритмов на небольшую размерность задачи (в  основном до 3­х), ограничения на нечетность размерности задачи, а также акцент на  эвристические подходы. Анализ литературных данных позволил сформулировать цель и задачи исследования. Вторая глава посвящена структурно­логическому подходу к анализу последовательно­ параллельной системы обслуживания, описываемой в терминах и представлениях  трехиндексной задачи о назначениях. Рассматривается система обслуживания, состоящая из N параллельно соединенных ветвей,  характеризующихся быстродействием и способных выполнять одновременно N  однотипных работ. Каждая ветвь предназначена для последовательного выполнения двух  работ и представляет собой цепочку из последовательно соединенных блоков,  предназначенных для выполнения операций, составляющих работу. Необходимо выбрать  оптимальный порядок подачи 2N работ, характеризующихся издержками на их  выполнение, в ветви системы, минимизирующий общее время выполнения комплекса работ. При этом применяются следующие допущения: 1) абсолютная надежность всех блоковсистемы обслуживания; 2) для каждой работы задается множество составляющих ее  операций, порядок выполнения которых предписывается некоторым заданным отношением порядка; 3) в любой момент времени каждый блок может выполнять не более одной  операции; 4) первые N работ подаются в систему одновременно. Для создания адекватных математических моделей функционирования вышеуказанной  системы необходимо развить и доработать математический аппарат непрерывной логики и  логических определителей, базирующийся на алгебре непрерывной логики НЛ с несущим  множеством и элементарными операциями над переменными : Ьх V Ь2 V... V Ь„ — \/ Ъ( ­ тах(6,,Ь2Ь„) ­ дизъюнкция НЛ; ¿>! л Ь2 л... л Ьп = д ¿>, = тт{Ь{,Ь2,—,Ьп) ­ конъюнкция НЛ. Расширением алгебры НЛ является аппарат логических определителей ЛО ­ некоторых  экстремальных числовых характеристик прямоугольных матриц, которые выражаются с  помощью элементов матриц и операции непрерывной логики. Для произвольной трехиндексной м а т р г С = | э д я т с я следующие понятия. Определение 1. Распределяющей суммой ^'с^ называется сумма элементов матрицы С, удовлетворяющих ограничению: любые три слагаемых имеют  различные первые индексы различные вторые индексы у и различные третьи индексы к. Определение 2. л ­определителем трехиндексной матрицы С называется выражение вида Предлагается следующая формально­логическая модель последовательно­параллельной  системы в терминах трехиндексной задачи о назначениях. Имеется п исполнителей и две группы из п работ. Каждый исполнитель может выполнять  любую пару работ по одной из каждой группы. Требуется распределить пары работ между исполнителями таким образом, чтобы  суммарные затраты на реализацию всех работ были минимальными. Принимаются  следующие допущения: любая работа выполняется не более чем одним исполнителем, а  любой исполнитель выполняет ровно одну пару работ из каждой группы. Обозначим Сцк издержки на выполнение у­м исполнителем ьй и к­и работ из 1­й и 2­й  группы соответственно, тогдаили £? = СЛ=Л =|с&а|Л. В такой постановке поиск оптимального распределения сводится к нахождению  минимальной распределяющей суммы, т е. к вычислению л­определителя трехиндексной  матрицы С. Сложность вычисления данного JЮ с помощью непосредственного перебора сумм имеет  экспоненциальную оценку: (т­п)\(р­п)\ В случае недетерминированности (интервальной неопределенности) функционирования  последовательно­параллельной системы в терминах недетерминированной (интервальной)  трехиндексной задачи о назначениях предлагается следующая формально­логическая  модель. Дана трехиндексная матрица издержек С = [С],С2], где С^Цс)^! ­ минимальная, а ­ максимальная детерми парованная матрицы издержек, составленные из нижних и вер) РИХ границ замкнутых интервалов С^ = [р!^/^ > с2,уЛ: ]' в которых за лючены фактические значения издержек. Необходимо на  множестве всех булевых матриц назначений , удовлетворяющих ограничениям найти такую матрицу X, которая минимизирует значение интервальной распределяющей  суммы матрицы С: X •' Вх ­ с№ = "ИП сук или й = СЛ В = лХ^, что сводится к вычислению интервального логического определителя. Однако в связи с ограничениями на сравнимость интервальных величин, находящихся в  отношении неравенства, т.е. требованием согласованности (Левин В.Щ1992)), решение  данной задачи существует не всегда. Далее рассматриваются основные определения и вспомогательные сведения, с помощью  которых исследуются условия существования решения недетерминированной  трехиндексной задачи о назначениях с интервальной матрицей коэффициентов, а также  определяется структура множества всех ее решений, сформулированных в следующих  теоремах: рассматриваемой \ ¿д | ­ трехиндексная матрицаназначений, являющаяся 1­м частным решением задачи í = 1,..., Р; МСх и МСг ­ множества всех решений детерминированных задач с постоянными  коэффициентами с матрицами издержек Затем формулируются и доказываются три теоремы о существовании, необходимых и  достаточных условиях решения недетерминированной задачи о назначениях с  трехиндексной интервальной матрицей издержек Третья глава посвящена вопросу синтеза оптимальных и приближенно оптимальных планов работы последовательно­параллельной системы в терминах, трехиндексной задачи о  назначениях при детерминированных и интервальных параметрах ее функционирования на  основе ее формально­логических моделей. Для проведения численного исследования  созданных моделей предлагается метод ветвей, границ и отсечений. На его основе  разработаны методы вычислений трехиндексных логических определителей. Предлагается  методика вычисления трехиндексного логического определителя задачи путем разложения  его по элементам аксиального сечения и фиксированному набору аксиальных сечений. Оптимизационные исследования базируются на следующих теоремах: множество всех решений с=[с„с2]. Определение 3. Логическим дополнением Сдо элемента С/„ называется трехиндексный логический определитель задачи, матрица которого получается  из матрицы задачи удалением аксиальных сечений на пересечении которых находится  элемент Теорема 4. л ­ определитель трехиндексной задачи о назначениях может быть  разложен по элементам плоского сечения j = const в виде Вычисление ЛО с использованием теоремы 4 требует т!р!(и­1) ТУд/ =­—­­­­­1­ тр — 1 операций сравнения, что сокращает их (т­п)\(р­п)\ число по сравнению с полным перебором в п1е раз. Определение 4. Минором г­го порядка назовем логический определитель , матрица  которого получена из матрицы задачи выделением наборов аксиальных сечений 1Т,3Г, Кг (1 < г < л)Пусть означает логический определитель, имеющий матрицу, полученную из матрицы С = ||с^ | удалением наборов аксиальных сечений /г,Уг,/Гг. Имеет  место следующая теорема. Теорема 5. Логический определитель СА можно разложить по заданному фиксированному  набору аксиальных сечений в.виде Вычисление ЛО с использованием теоремы 5 обеспечивает обозримость процедуры поиска, однако имеет также экспоненциальную оценку сложности. Вследствие того, что понятие вычисления логического определителя включает не только  вычисление минимальной распределяющей, суммы (нахождения длины кратчайшего пути  из корня в вершину в дереве последовательного разложения ЛО), а также отыскание ее  поэлементного состава, то есть идентификацию этого пути по составу входящих в него  вершин­элементов. Использование данного метода позволяет проводить оптимизационные  исследования системы, т.е осуществлять качественный анализ решений при варьировании  исходных данных. Оптимизация в условиях интервальной неопределенности строится на базе  детерминистского подхода при постоянных параметрах с использованием выясненных  условий существования решения интервальной трехиндексной задачи о назначениях и  теорем 4,5. Предлагается следующая методика использования структурно­логического подхода для  получения алгоритмов с полиномиальными оценками сложности. Алгоритм А приближенного решения трехиндексной задачи о назначениях, основанный на  теореме 4, описывается формулой СЛ +С.Г(2),2,*(2)Ч1)*С1) +С'И)А*тЧ|)1(2)¥(2) + ",+ где, например, ­ минимальный элемент 2­го аксиального сечения (у = 2) определителя, полученного удалением из аксиальных сечений / = 5()) и / =  кщ При оценке временной сложности отыскания приближенного решения по этому алгоритму  использовались количественные оценки зависимости «сложность задачи ­ размеры  системы», согласно которым она равнаВероятностный анализ точности решения проводился для решений задачи для случайных  входов, определяемых множеством Мп матриц С = Цсдо| размера пхпх П, где элементы С­  независимые случайные величины, выбираемые из отрезка , с одинаковой функцией распределения. Проанализировано поведение оценок е^ оценки относительной  погрешности получаемого алгоритмом А решения и 8д ­ вероятности несрабатывания  алгоритма А, т.е. доли случаев, когда алгоритм не гарантирует погрешность, не  превосходящую при увеличении размерности задачи. Предполагаемая сложность отыскания оптимального решения модифицированного алгоритма NА. (л) = (и­1)л(л+1)/3 Проведенный анализ эффективности алгоритма подтверждает целесообразность  предложенного метода оптимизации и обусловливает его ценность для практического  применения. Четвертая глава посвящена аспектам компьютерного моделирования некоторых  последовательно­параллельных систем обслуживания. Проблема понижения сложности  является центральной не только в теории оптимизации, но и в теории искусственного  интеллекта. Как показывают результаты, полученные в предыдущей главе, структурно­ логический подход, основанный на сведении исходной оптимизационной задачи к совокупности более простых, а также разработанные алгоритмы, значительно сокращающие поиск решения, позволяют решать ее эффективно. Это демонстрируется на примере  экспертной системы моделирования экологии транспортно­экспедиторской компании (ЭС  МЭТЭК). В главе рассматриваются процессы управления в транспортно­экспедиторской компании,  формулируются требования, предъявляемые к системе, предлагается реализация  программного комплекса ЭС МЭТЭК. Кроме традиционного набора компонентов системы: модулей ввода и редактирования данных (экспертных оценок и т.д.), оптимизационного  процессора, осуществляющего поиск решения, модуля формирования выходных  документов, в систему вводится модуль проверки согласованности экспертных оценок,  заданных в интервальном виде. Детально исследован режим решения задач предлагаемой  экспертной системы.Одной из практических задач составления расписания движения транспортных средств на  маршрутах является назначение заданных транспортных средств на определенные  маршруты в соответствии с уже выбранными для них расписаниями. Компьютерная оптимизация экосистемы автотранспортного предприятия должна быть  направлена не просто на уменьшение выбросов всех загрязняющих веществ, а на  минимизацию степени ущерба, наносимого природной среде, что подразумевает  оптимизацию структуры выбросов вредных веществ. В связи с этим предлагается следующая модель работы автотранспортного предприятия. Даны N единиц автотранспортных средств, N заказов на перевозки. Даны С1]к = £ с'ук ­ суммарные выбросы т загрязняющих веществ при осуществлении одним автомобилем предполагаемой пары перевозок. Требуется распределить пары заказов на перевозки между единицами автомобильного  парка так, чтобы минимизировать, суммарный экологический ущерб от работы  автотранспортного предприятия: (\й1йт\й ] <,п\<,кй р) Знания об удельных выбросах загрязняющих веществ основаны на результатах  исследований и наблюдений, проводимых различными научно­исследовательскими и  проектными организациями. Метод расчета основан на результатах натурных наблюдений и измерений в различных климатических условиях. Один из вариантов расчета выброса 1­го загрязняющего вещества при осуществлении одним автомобилем предполагаемой пары перевозок с'ук: "" с'«/* = тпрогр] X Кр + т^ч X Ц] + Пщк + X , где ^„рогр/ ­ удельный выброс /­го загрязняющего вещества при прогреве двигателя  автомобиля, г/мин; ­ время прогрева двигателя, мин; пробеговый выброс /­го  загрязняющего вещества автомобиля с относительно постоянной скоростью, г/км; ­  предполагаемый пробег при выполнении автомобилем заказов, км; Ю^д ­ удельный выброс загрязняющего вещества при работе двигателя на холостом ходу, г/мин; ­  предполагаемое время работы на холостом ходу.Оптимизационная задача формулируется как рассмотренная выше трехиндексная задача о  назначениях. В заключении сформулированы основные результаты и выводы диссертационной работы.. ОСНОВНЫЕ РЕЗУЛЬТАТЫ РАБОТЫ 1. Для класса задач оптимизации систем обслуживания с последовательно­параллельной  структурой в терминах трехиндексной задачи о назначениях как при детерминированных/  так и при недетерминированных (интервальных) параметрах функционирования системы  развит и доработан математический аппарат, основанный на непрерывной логике и  логических определителях. 2. Предложены формально­логические модели, представляющие собой матричные  структуры, позволяющие адекватно в компактной форме описывать функционирование  вышеуказанных систем и решать на них задачи синтеза оптимальных и приближенно­ оптимальных решений. 3. Сформулированы и исследованы условия существования решения недетерминированной  трехиндексной задачи о назначениях, а также определена структура множества решений  задачи с интервальной матрицей коэффициентов. 4. Для нахождения оптимальных решений задачи предложен метод ветвей, границ и  отсечений. На его основе разработаны методы вычислений трехиндексных логических  определителей с помощью разложения их по элементам аксиального сечения и  фиксированному набору аксиальных сечений. 5. Разработанные методы оптимизации применены к построению алгоритмов решения  задачи с полиномиальными оценками сложности для задачи произвольной размерности.  Проведен анализ работы алгоритмов, указываются условия их асимптотической точности для решения задачи на  случайных входах. 6. Предлагаемый структурно­логический подход, основанный на сведении исходной  оптимизационной задачи к совокупности более простых, а также разработанные алгоритмы, значительно сокращающие поиск решения могут успешно находить применение в  прикладном плане при разработке экспертных систем. ОСНОВНЫЕ ПУБЛИКАЦИИ ПО ТЕМЕ РАБОТЫ 1. Близнова О.В. Условия существования задачи интервальной оптимизации решения  трехиндексной аксиальной задачи о назначениях// Компьютерное моделирование иинформационные технологии в науке, инженерии и образовании: Сборник материалов  Междунар. науч. конф. ­ Пенза, 2003. ­ С. 18­21. 2. Близнова О.В. Структурный алгоритм решения трехиндексной аксиальной задачи о  назначениях// Компьютерное моделирование и информационные технологии в науке,  инженерии и образованииг Сборник материалов Междунар. науч. конф.­ Пенза, 2003. ­ С.  16­18. 3. Близнова О.В. Логическая модель принятия решений, в условиях интервальной  неопределенности// Непрерывная и смежные логики в технике, экономике и социологии:  Сборник материалов Междунар. науч.­техн. конф­Пенза, 1996. ­ С. 144. 4. Близнова О.В., Большаков А.А., Глазков В.П. Структурный подход к задаче  моделирования работы транспортно­экспедиторской компании// Математические методы в технике и технологиях: Сборник трудов 16 Междунар. науч. конф. ­ Ростов­на­Дону, 2003.  ­ Т.7 ­ С. 84­86. 5. Близнова О.В., Лягин И.А. Анкетирование пользователей­прикладников экспертных  систем оценки результатов измерений. ­ М., 1995. ­ 1 1с. Деп. в ВИНИТИ ЮЛ 1.95, № 2992­ В95. 6. Левин В.И., Близнова О.В. Объединение детерминированных экспертных оценок на  основе априорной информации. ­ М., 1994. ­ 7 с. Деп. в ВИНИТИ 22.06.94, № 1547 ­ В94. 7. Левин В.И., Близнова О.В. Интервальный подход к оптимизации работы  автотранспортного предприятия // Непрерывная и смежные логики в информатике,  экономике и социологии: Сборник материалов Всерос. науч.­техн. конф. ­ Пенза, 1997. ­ С.  ­ 85­86. 8. Левин В.И., Близнова О.В. Система управления планированием перевозок АТП в  условиях экологического кризиса// Математические методы и информационные  технологии в экономике, социологии и образовании: Сборник материалов Междунар.  науч.­техн. конф. ­Пенза,2001.­С. 141­142. 9. Лягин И.А., Близнова О.В. Модель предметной области экспертной системы оценки  результатов измерений. ­ М., 1995. ­ 8 с. Деп. в ВИНИТИ 10.11.95, №2993­В95. 10.Лягин И.А., Близнова О.В. Формализация описания алгоритмов обработки данных ­ М.,  1995. ­ 5 с. Деп. в ВИНИТИ 14.02.95, №425­В95.11. Свидетельство об официальной регистрации программы для ЭВМ №2004610418  (Россия). Экспертная система моделирования экологии транспортно­экспедиторской  компании / Большаков А.А., Близнова О.В., Левин В.И. Дата реп: 10 февраля 2004г. 12.Bliznova О., Levin V. Application of Priory Information in Knowledge Bases of Expert  Systems// New Information Technologies and Systems (NITS' 94): Proceedings of Intern. Conf.  of Science and Technology. ­Penza, Russia, 1994. ­ P. 48. 13.Bliznova O., Tuzilov I. On Expert Systems for Simulation of Industrial Ecology// New  Information Technologies and Systems (NITS' 94): Proceedings of Intern. Conf. of Science and  Technology. ­ Penza, Russia, 1994. ­ P. 21­22. Лицензия ИД № 06268 от 14.11.01 Подписано в печать 09.03.04 Формат 60x84 1/16 Бум.тип. Усл.­печ.л. 0,93(1,0) Уч.­изд. л. 0,9 Тираж 100 экз. Заказ 113 Бесплатно Саратовский государственный технический университет 410054, г. Саратов, ул.  Политехническая, 77 Копипринтер СГТУ, 410054, г. Саратов, ул. Политехническая, 77 Оглавлениеавтор диссертации — кандидат технических наук Близнова, Ольга  Владимировна ВВЕДЕНИЕ. 1. ОБЗОР РАБОТ ПО МОДЕЛИРОВАНИЮ И ОПТИМИЗАЦИИ ДИСКРЕТНЫХ  СИСТЕМ. 1.1. Классификация моделей и методов решения задач дискретной оптимизации. 1.2. Характеристика методов математического программирования^ . 1.3. Описание метода  исследования на графах. 1.4. Описание метода ветвей и границ. 1.5 Характеристика статистического моделирования. 1.6 Выводы и постановка задачи. 2. СТРУКТУРНО­ЛОГИЧЕСКИЙ ПОДХОД К АНАЛИЗУ ПОСЛЕДОВАТЕЛЬНО­ ПАРАЛЛЕЛЬНОЙ СИСТЕМЫ.2.1. Краткая характеристика математического аппарата непрерывной логики и логических  определителей. 2.2. Описание интервального анализа. 2.2.1. Краткое описание принципов сравнения и оптимизации интервальных величин. 2.2.2. Характеристика интервальных логических определителей. 2.3 Разработка формально­логической модели последовательно­параллельной системы  обслуживания в задачах о назначениях. 2.4 Анализ условий существования решения недетерминированной трехиндексной задачи о  назначениях. 2.5. Выводы. 3. СИНТЕЗ ПЛАНА РАБОТЫ ПОСЛЕДОВАТЕЛЬНО ­ПАРАЛЛЕЛЬНОЙ СИСТЕМЫ. 3.1 Синтез последовательно­параллельной системы методом ветвей и границ. 3.2. Разработка метода оптимизации, основанного на вычислении логических  определителей. 3.3. Создание метода решения задачи в условиях интервальной неопределенности. 3.4. Конструктивный подход к построению приближенно­оптимального решения. 3.5. Анализ алгоритма приближенной оптимизации. 3.6. Выводы. 4. КОМПЬЮТЕРНОЕ МОДЕЛИРОВАНИЕ ПОСЛЕДОВАТЕЛЬНО­ПАРАЛЛЕЛЬНЫХ  СИСТЕМ. 4.1. Процессы управления в транспортно­экспедиторской компании 4.2. Описание требований к системе моделирования. 4.3. Реализация программного комплекса моделирования экологии транспортно­ экспедиторской компании. 4.4. Характеристика режимов решения задач с помощью экспертной системы. 4.5. Организация диалога с пользователем на ограниченном естественном языке.Введение2004 год, диссертация по информатике, вычислительной технике и управлению,  Близнова, Ольга Владимировна Актуальность темы. Задачи выбора некоторого оптимального варианта из конечного набора альтернатив являются важными как в теоретическом, так и прикладном значении. К их  числу относятся так называемые многоиндексные, в том числе трехиндексные задачи о  назначениях, которые до сих пор недостаточно глубоко исследованы. Они относятся к  классу наиболее трудных с вычислительной точки зрения задач дискретной оптимизации,  имеющих экспоненциальную (ИР) вычислительную сложность (Емеличев В.А., Ковалев  М.М., Кравцов М.М, (1981)). ЫР­полнота данных задач обусловливает поиск и разработку  приближенных алгоритмов их решения. Наиболее часто используемым для исследования этих задач о назначениях и разработки  приближенных схем их решения является метод исследования на графах. Характерными  являются работы Гимади Э.Х., Сердюкова А.И. (1999), Кайрана Н.М. (2000), Коркишко  Н.М. (2003) и др., в которых алгоритмы решения разработаны для задач малой  размерности. В связи с этим актуальной является разработка новых методов решения трехиндексной  задачи о назначениях. Для этого предлагается использовать подход, с последующим  применением методов теории расписаний. Теория расписаний представляет собой специальное направление прикладной математики,  изучающее модели и методы организации комбинаторных вычислений для составления  расписаний, т.е. распределения во времени ограниченных ресурсов, предназначенных для  выполнения различных видов работ (операций, заданий, процессов, и т. д.) и построения  оптимального расписания (плана) выполнения их заданной совокупности. Объектом  изучения этой теории являются системы обслуживания, представляющие собой  определенное множество блоков, объединенных некоторым множеством связей,  предназначенные для выполнения заданной совокупности работ. Одним из способов решения проблемы. оптимального расписания (плана), и связанной с  ней большой размерности является применение структурно­логического метода  исследования систем. Этот подход заключается в использовании математического  аппарата непрерывной логики (HJI) и логических определителей (ЛО) (своеобразных  экстремальных числовых характеристик прямоугольных матриц). Это позволяет  разработать эффективные полиномиальные алгоритмы невысокой степени, позволяющие  заменять полный перебор всех вариантов частичными переборами меньших объемов и  проводить оптимизационные исследования системы, т.е. осуществлять качественный  анализ получаемых решений.Общие положения и теоретические основы этого метода разработаны В.И. Левиным (1979)  и получили развитие в работах А.Ф. Буланова (1981), С.А. Лысака (1983), И.Ю. Мирецкого (1987) и др. ученых. Особенность данного метода заключается в необходимости развития и  доработки математического аппарата непрерывной логики и логических определителей  для конкретного класса задач дискретной оптимизации. Применение структурно­ логического метода исследования систем для разработки алгоритмов решения  рассматриваемого в данной диссертационной работе класса задач осуществляется впервые. Все это обусловливает актуальность диссертационной темы, выбор подхода к  исследованию, а также определяет его цели и задачи. Предметом исследования является проблема оптимизации работы последовательно­ параллельной системы обслуживания. В терминах и представлениях трехиндексной задачи  о назначениях подобная система описывается следующим образом. Последовательно­ параллельная система обслуживания представляет собой N параллельно соединенных  ветвей, , характеризующихся быстродействием, и способных выполнять одновременно N  однотипных работ. Каждая ветвь предназначена для последовательного выполнения двух  работ и представляет собой цепочку из последовательно соединенных блоков,  предназначенных для выполнения операций, составляющих работу. Имеется 2 ТУ работ,  характеризующихся издержками на их выполнение в ветвях системы. Необходимо выбрать  оптимальный порядок подачи работ в ветви системы, минимизирующий общее время  выполнения комплекса работ. При этом применяются следующие допущения: 1)  абсолютная надежность всех блоков системы обслуживания; 2) для каждой работы  задается множество составляющих ее операций, порядок выполнения которых  предписывается некоторым заданным отношением порядка; 3) в любой момент времени  каждый блок может выполнять не более одной операции; 4) первые N работ подаются в  систему одновременно. Целью работы создание адекватных математических моделей функционирования  последовательно­параллельной системы обслуживания, сформулированной в виде  трехиндексной задачи о назначениях как при детерминированных, так и при  недетерминированных (интервальных) параметрах функционирования системы,  исследование с помощью этих моделей задачи синтеза оптимальных и приближенно­ оптимальных расписаний (планов), разработка эффективных приближенных алгоритмов  решения задачи. Для достижения этой цели необходимо решить следующие задачи: • Развить математический аппарат непрерывной логики и логических определителей с  учетом специфики рассматриваемого класса задач теории расписаний.• Разработать приближенный метод оптимизации формальнологических моделей системы и применить его к построению эффективных приближенно оптимальных алгоритмов решения задачи произвольной размерности. Методы исследования. В работе использовались методы алгебры непрерывной логики и  логических определителей, теории множеств, теории алгоритмов, исследования операций,  в том числе теории расписаний, теории графов, статистического моделирования,  математического программирования и комбинаторного анализа. Достоверность и обоснованность научных положений и результатов исследований  подтверждаются корректностью применения апробированного математического аппарата  непрерывной логики и логических определителей, а также аппарата теории вероятностей,  математической статистики и согласованностью результатов теоретических расчетов с  данным, полученными экспериментальным путем автором и другими исследователями. На защиту выносятся: 1. Формально­логические модели, которые представляют собой матричные структуры и  позволяют адекватно описать функционирование последовательно­параллельных систем в  терминах и представлениях трехиндексной задачи о назначениях. 2. Метод, основанный на непрерывной логике и логических определителях, который  позволяет эффективно проводить оптимизационные исследования задачи как при  детерминированных, так и при недетерминированных (интервальных) параметрах  функционирования системы на основе единого подхода. 3. Условия существования решения недетерминированной трехиндексной задачи о  назначениях, связанные с недетерминированностью параметров системы, а также структура множества всех решений рассматриваемой задачи с интервальной матрицей  коэффициентов. 4. Методика оптимизационных исследований рассматриваемых систем как при  детерминированных, так и при недетерминированных интервальных) параметрах ее  функционирования, основанная на анализе разработанных формально­логических моделей  систем. 5. Эффективные алгоритмы получения приближенно оптимальных решений задачи  произвольной размерности. Научная новизна. В ходе выполнения работы получены следующие новые результаты:1. Разработаны формально­логические модели функционирования последовательно­ параллельной системы в терминах и представлениях трехиндексной задачи о назначениях  как при детерминированных, так и при недетерминированных (интервальных) параметрах  ее функционирования, позволяющие адекватно представлять заданную о системе  информацию в компактной, обозримой форме, что важно для решения проблемы большой  размерности при исследовании системы и разработки оптимизационных алгоритмов. 2. Сформулированы и исследованы связанные с недетерминированностью условия  существования задачи при интервальной неопределенности параметров функционирования  системы. 3. Разработаны оригинальные аппарат и метод оптимизационных исследований  рассматриваемой системы, основанные на анализе разработанных формально­логических  моделей, позволяющие осуществлять качественный анализ решений при варьировании  исходных данных. 4. Созданы эффективные алгоритмы синтеза приближенно оптимальных расписаний для  задач произвольной размерности. Практическая ценность. Использование предлагаемых методик и теоретических разработок расширяет круг решаемых оптимизационных задач. Полученные аналитические результаты  позволяют строить легко реализуемые на ЭВМ эффективные алгоритмы получения  приближенно­оптимальных решений трехиндексной задачи о назначениях как при  детерминированных, так и при недетерминированных (интервальных) параметрах, которые  могут использоваться, в частности, при создании оптимизационных модулей экспертных  систем. Реализующая данные алгоритмы экспертная система моделирования экологии  транспортно­экспедиторской компании используется в Пензенском областном управлении  инкассации, внедрена в учебный процесс Пензенской государственной  сельскохозяйственной академии. Апробация работы. Основные результаты диссертационной работы были доложены и  обсуждены на 1­й Всероссийской конференции «Непрерывная логика и ее применение в  технике, экономике и социологии» (Пенза, 22­23 сентября 1994); научно­практической  конференции «Экологическая безопасность и социально­экономическое развитие регионов  России» (Саранск, 14­16 декабря 1994); International Conference of S cience and Technology  «New Information Technologies and Systems» (Penza, Russia, 21­29 Dec. 19.94);  Международной научно­технической конференции «Непрерывно­логические и нейронные  сети и модели» (Ульяновск, 23­25 мая 1995); Международной научно­технической  конференции «Непрерывно­логические методы и модели в науке, технике и экономике»  (Пенза, 19­20 октября 1995); Всероссийской конференции «Информационные технологии исистемы» (Воронеж, 16­19 октября 1995); научно­практическом семинаре «Экологическая  безопасность регионов России» (Пенза, 25­26 апреля 1996); научно­практическом семинаре «Применение баз данных» (Пенза, 26­27 ноября 1997); Всероссийской научно­технической  конференции «Непрерывная и смежная логики в информатике, экономике и социологии»  (Пенза, 30­31 октября 1997); Международной научно­технической конференции  «Математические методы и информационные технологии в экономике, социологии и  образовании» (Пенза, 22­23 ноября 2001); 16­й Международной научной конференции  «Математические методы в технике и технологиях» (Ростов­на­Дону, 27­29 мая 2003);  Международной конференции «Компьютерное моделирование и информационные  технологии в науке, инженерии, образовании» (Пенза, 2003). Публикации. По теме диссертации опубликованы 13 печатных работ, перечисленных в  конце автореферата. Структура работы. Диссертация общим объемом 141 страница состоит из введения,  четырех глав, заключения и приложений, содержит 8 рисунков, 12 таблиц, список  литературы из 119 наименований. Приложения содержат акты о внедрении и  доказательства теорем. Заключениедиссертация на тему "Логическое моделирование систем с последовательно­ параллельной структурой" Основные результаты, полученные в диссертационной работы сводятся к следующему: 1. Для класса задач оптимизации систем обслуживания с последовательно­параллельной  структурой в терминах трехиндексной задачи о назначениях как при детерминированных,  так и при недетерминированных (интервальных) параметрах функционирования системы  развит и доработан математический аппарат, основанный на непрерывной логике и  логических определителях. 2. Предложены формально­логические модели, представляющие собой матричные  структуры, позволяющие адекватно в компактной форме описывать функционирование  вышеуказанных систем и решать на них задачи синтеза оптимальных и приближенно­ оптимальных решений. 3. Сформулированы и исследованы условия существования решения недетерминированной  трехиндексной задачи о назначениях, а также определена структура множества решений  задачи с интервальной матрицей коэффициентов. 4. Для нахождения оптимальных решений задачи предложен метод ветвей, границ и  отсечений. На его основе разработаны методы вычислений трехиндексных логическихопределителей с помощью разложения их по элементам аксиального сечения и  фиксированному набору аксиальных сечений. 5. Разработанные . методы оптимизации применены к построению алгоритмов решения  задачи с полиномиальными оценками сложности для задачи произвольной размерности.  Проведен анализ работы алгоритмов, указываются условия их ассимптотической точности  для решения задачи на случайных входах. 6. Предлагаемый структурно­логический подход, основанный на сведении исходной оптимизационной задачи к совокупности более простых,  а также разработанные алгоритмы, значительно сокращающие поиск решения могут  успешно находить применение в прикладном плане при разработке экспертных систем. ЗАКЛЮЧЕНИЕ В диссертации разработаны теоретические и практические вопросы оптимизации работы  последовательно­параллельной системы { обслуживания терминах и представлениях  трехиндексной задачи о ч назначениях. БиблиографияБлизнова, Ольга Владимировна, диссертация по теме "Математическое  моделирование, численные методы и комплексы программ" 1. Авен О.И., Ловецкий С.Е., Моисеенко Г.Е. Оптимизация транспортных потоков. М.:  Наука, 1985. ­ 268 с. 2. Алексеев О.Г. Комплексное применение методов дискретнойf „оптимизации. М.: Наука,  1987. ­ 248 с. 3. Алефельд Г. Хальцбергер Ю. Введение в интервальные вычисления. М.: Мир, 1987. ­ 365  с. 4. Ахо А., Хопкорфт Дж. Ульман Дж. Построение и анализ вычислительных алгоритмов.  М.: Мир, 1979. ­ 536 с. 5. Ахо А., Хопкорфт Дж. Ульман Дж. Структуры данных и алгоритмы. М.: Вильяме, 2000. ­ 468 с. 6. Беленький A.C., Левнер Е.В. Применение моделей и методов теории расписаний в  задачах оптимального планирования на грузовом транспорте // Автоматика и  телемеханика, 1989. №1. С.3­77. 7. Беллман Р., Дрейфус С. Прикладные задачи динамического программирования. М.:  Наука, 1965. ­ 458 с.8. Близнова О.В. Логическая модель принятия решений в условиях интервальной  неопределенности // Непрерывная и смежные логики в технике, экономике и социологии:  Материалы Межд. НТК. Пенза: ПДЗ, 1996.­С.144. 9. Близнова О.В. Структурный алгоритм решения трехиндексной задачи о назначениях //  Компьютерное моделирование и информационные технологии в науке, инженерии и  образовании: Сборник матер. Межд. научн. конф. Пенза, 2003. ­ С. 16­18. 10. Близнова О.В., Тужилов И.В. Проблема разработки экспертных систем моделирования  экологии предприятий. М., 1994. ­ 4 с. Деп. в ВИНИТИ 22.06.94 № 1546 ­ В 94. 11. Близнова О.В., Лягин И. А. Анкетирование пользователей­прикладников экспертных  систем оценки результатов измерений. М:., 1995. 5 с. Деп. в ВИНИТИ 10.11.95 № 2992­ В95. 12. Бондаренко В.А. Полиэдральные графы и сложность в комбинаторной оптимизации.  Ярославль, 1995. 230 с. 13. Венгерова И.И., Финкельштейн Ю.Ю. К вопросу об эффективности метода ветвей и  границ //Экономика и математические методы. 1975. Т. XI, №1. С.186­193. 14. Вилкас Э.Й., Майминас Е.З. Решения: теория, информация, моделирование. ­М.: Радио  и связь, 1981. 328 с. 15. Гимади Э.Х., Коркишко Н.М. Об одном алгоритме решения трехиндексной аксиальной  задачи о назначениях на одноциклических подстановках // Дискретный анализ и  исследование операций, 2003. ­Серия 1. Том 10, №2. С. 56­65. 16. Гимади Э.Х., Сердюков А.И. Аксиальные трехиндексные задачи о назначении и  коммивояжера: быстрые приближенные алгоритиы и их вероятностный анализ // Изв. вузов. Математика, 1999. № 12. С.19­25. 17. Гончаров E.H. Математическая модель и метод решения двухуровневой задачи  стандартизации // Модели и методы оптимизации Новосибирск: Институт математики СО  РАН, 1994. ­ Т.28 ­ С. 77­90. 18. Гэри М., Джонсон Д. Вычислительные машины и труднорешаемые задачи.­М.: Мир,  1982.­416 с. 19. Жаке­Лагрез Э. Применение размытых отношений при оценке предпочтительности  распределенных величин // Статистические модели и многокритериальные задачи принятия решений. М.: Статистика, 1979.­ С. 168­183.20. Иванов Б.Н. Дискретная математика. Алгоритмы и программы. — М.: Лаборатория  Базовых Знаний, 2002. 288 с. 21. Информационные технологии в транспортной логистике. Составитель А.К. Труханов.  М.: КИА центр, 2000. 86 с. 22. Крисевич B.C., Кузьмин Л.А., Шиф A.M. и др. Экспертные системы для персональных  компьютеров: методы, средства, реализации: Справ, пособие. Мн.: Выш. Шк., 1990. ­ 197 с. 23. Конвей Р.В., Маквелл В.Л., Миллер Л.В. Теория расписаний. М.: Наука, 1975.­360 с. 24. Коркишко Н.М. Трехиндексная аксиальная задача о назначениях на одноциклических  подстановках на максимум. Новосибирск, 2003. 18 с. 25. Кочетов Ю.А. Задачи оптимального выбора состава систем технических средств при  многоэтапном процессе выполнения работ. Новосибирск, 1987. С.48­58. (Препринт/АН  СССР. Сиб. Отд­ние. Ин­т математики; №12) 26. Ларин P.M., Пяткин A.B. Двухуровневая задача о назначениях // Дискретный анализ и  исследование операций, 2001. Серия 2, Т.8, №2, ­С. 42­51. 27. Левин В.И. Структурно­логический метод комбинаторной оптимизации // Автоматика и вычислительная техника, 1979. №1. ­С.45­52. 28. Левин В.И. Структурно­логический метод приближенной комбинаторной оптимизации  в задачах распределения вычислительных мощностей // Автоматика и вычислительная  техника, 1981. №6. ­С.46­53. 29. Левин В.И. Логический метод оптимизации решения задач в вычислительных  системах // Автоматика и вычислительная техника, 1982.­№3.­С.55­61. 30. Левин В.И. К планированию работы вычислительных систем. Математический  аппарат // Автоматика и вычислительная техника, 1982.­ №5. — С.52­58. 31. Левин В.И. Бесконечнозначная логика в задачах кибернетики. — М.: Радио и связь,  1982. 175 с. 32. Левин В.И. К планированию работы вычислительных систем. Анализ плана //  Автоматика и вычислительная техника, 1983. №2. ­С.64­72. 33. Левин В.И. К планированию работы вычислительных систем. Синтез плана //  Автоматика и вычислительная техника, 1983. №3. ­ С.64 — 70.34. Левин В.И. Структурно­логические методы исследования сложных систем с  применением ЭВМ. М.: Наука, 1987. ­ 304 с. 35. Левин В.И. Непрерывная логика. Ее обобщения и применения. 1, 2 //автоматика и  телемеханика, 1990. №8. ­ С.3­22 ­ и ­ №9. ­ С. 3­26. 36. Левин В.И. Дискретная оптимизация в условиях интервальной неопределенности //  Автоматика и телемеханика, 1992. №7. ­ с.97­106. 37. Левин В.И. Антагонистические игры с интервальными параметрами // Кибернетика и  системный анализ. 1999. №7. С. 100­121. 38. Левин В.И. Оптимизация расписаний в М стадийной системе с неопределенными  временами обработки. 1, 2. // Автоматика и телемеханика, 2002. ­ №1. ­ с.116­124 ­ и ­ №2.  ­ С. 129­136. 39. Левин В.И., Близнова О.В. Объединение детерминированных экспертных оценок на  основе априорной информации. М: 1994. . — 7 е.­ Деп. в ВИНИТИ 22.06.94, № 1547 ­ В94 40. Левин В.И., Близнова О.В. Управление процессом планирования перевозок АТП в  условиях экологического кризиса // Применение баз данных: Сборник материалов НПС. —  Пенза: ПДЗ, 1997. — С. 12­13. 41. Левин В.И., Близнова О.В. Интервальный подход к оптимизации работы  автотранспортного предприятия // Непрерывная и смежные логики в информатике,  экономике и социологии: Сборник материалов Всеросс. НТК. Пенза, ПДЗ, 1997. ­ С. ­ 85­ 86. 42. Левин В.И., Буланов А.Ф. Логический синтез алгоритма вычислений в  пространственной задаче о назначениях. // Применение вычислительных методов в научно­ технических исследованиях. ­Пенза, 1981.­С. 67­74. 43. Левин В.И., Лысак С.А. Оптимизация порядка следования работ в системе с  параллельно­последовательной обработкой // Вычислительная техника в  автоматизированных системах контроля и управления. Пенза, 1984. ­ Вып. 14. ­ С. 34­37. 44. Левин В.И., Мирецкий И.Ю. Организация процесса обработки заданий в конвейерной  вычислительной системе // Вопросы радиоэлектроники. Сер. ЭВТ., 1986. Вып. 8. ­ С.3­7. 45. Левин В.И., Мирецкий И.Ю. Моделирование и оптимизация работы производственной  системы // Механизация и автоматизация производства, 1987. №10. ­ С. 35­36.46. Левин Р., Дранг Д., Эделсон Б. Практическое введение в технологию искусственного  интеллекта и экспертных систем. М. Финансы и статистика, 1991. ­ 239 с. 47. Луканин В.Н., Трофименко Ю.В. Промышленно­транспортная экология. М.: Высш.  Шк., 2001.­273 с. 48. Луканин В.Н., Буслаев А.П., Яшина М.В. Автотранспортные потоки и окружающая  среда 2. ­ М.: ИНФРАМ, 2001. ­ 646 с. 49. Лягин И.А., Близнова О.В. Модель предметной области экспертной системы оценки  результатов измерений. М:., 1995. — 6 с. Деп. в ВИНИТИ 10.11.95 № 2993­В95. 50. Лягин И.А., Близнова О.В. Формализация описания алгоритмов обработки данных. М:.,  1995.­ 5 с. Деп. В ВИНИТИ 14.02.95 №425­В95. 51. Максимей И.В. Математическое моделирование больших систем. ­Минск: Вышэйшая  школа, 1985. 120 с. 52. Марселус Д. Программирование экспертных систем на Турбо­Прологе: Пер. с англ. /  М.: Финансы и статистика, 1994. 256 с. 53. Методика определения массы выбросов загрязняющих веществ автотранспортными  средствами в атмосферный воздух. М.: НИИАТ, НИИКТП, МАДИ, НИЦИАМТ, 1993. 54. Методика проведения инвентаризации выбросов загрязняющих веществ в атмосферу  для автотранспортных предприятий (расчетным методом). М. НИИАТ, 1991. 55. Мирецкий И.Ю. Оценивание возможностей повышения производительности  конвейерной вычислительной системы // Вопросы радиоэлектроники. Сер. ЭВТ, 1990. Вып.  9. ­ С.34­39. 56. Михалевич B.C., Трубин В.А., Шор Н.З. Оптимизационные задачи производственно­ транспортного планирования. М.: Наука, 1986. —240 с. 57. Нечеткие множества и теория возможностей. Последние достижения: Пер. с англ. / Под ред. Р.Р.Ягера. М.: Радио и связь, 1986. ­408 с. 58. Павлова Е.И. Экология транспорта. М.: Транспорт, 2000. ­ 248 с. 59. Пападимитриу X., Стайглиц К. Комбинаторная оптимизация. Алгоритмы и сложность.  М.: Мир, 1985. ­ 510 с. 60. Подчасова Т.П., Португал В.М., Татаров В.А., Шкурба В.В. Эвристические методы  календарного планирования. Киев: Техника, 1980.­ 140 с.61. Португал В.М., Писаренко В.М. Экспериментальное исследование алгоритмов  случайного поиска для задач календарного планирования // Вопросы разработки  территориальных автоматизированных систем управления: Сб. научн. трудов . Кемерово,  1984. ­ С. 8­12. 62. Романовский И.В. Алгоритмы решения экстремальных задач. М.: Наука, 1977.­352 с. 63. Саати Т. Целочисленные методы оптимизации и связанные с ними экстремальные  проблемы. М.: Мир, 1973. — 304 с. 64. Сергиенко И.В. Математическое модели и методы решения задач дискретной  оптимизации. Киев: Наукова думка, 1985. ­ 384 с. 65. Стаханов В.Н., Украинцев В.Б. Теоретические основы логистики. Ростов н/Д:  «Феникс», 2001. 160 с. 66. Танаев B.C., Шкурба В.В. Введение в теорию расписаний. М.: Наука, 1975.­280 с. 67. Трубин В.А., Шарифов Ф.А. Простейшая многоэтапная задача размещения на  древовидной сети // Кибернетика и системный анализ, 1992. №6. С.128­135. 68. Финкельштейн Ю.Ю. Приближенные методы и прикладные задачи дискретного  программирования. М.: Наука, 1976. ­ 234 с. 69. Хелд М., Карп P.M. Применение динамического программирования к задачам  упорядочения // Кибернетический сборник. — М.: Мир, Вып. 9.­С. 202­218. 70. Хохлюк В.И. Задачи целочисленной оптимизации. Новосибирск: Новосибирск, ун­т,  1979. ­ 92 с. 71. Свидетельство об официальной регистрации программы для ЭВМ № 2004610418  (Россия). Экспертная система моделирования экологии транспортно­экспедиторской  компании / Большаков А.А., Близнова О.В., Левин В.И. // дата per: 10 февраля 2004г. 72. Adams W.P., and Johnson Т. Improved Linear Programming­based Lower Bounds for the  Generalized Assignment Problem. DIMACS Series in Discrete Mathematics and Theoretical  Сотр. Science, vol. 16, 1994. Pp. 43­76. 73. Adams W.P. and Sherali H.D. A Tight Linearization and an Algorithm for Zero­One  Quadratic Programming Problems // Management Science, Vol.32, № 10, 1986.­ Pp. 1274­1290. 74. Assard A.A. and Xu W. On Lower Bounds for Class of Quadratic 0,1 Programs // Operation  Research Letters, vol.4. 1985. Pp.175­180.75. Azar Y., Naor J. and Rom R. The Competitiveness of On­line Assignment. In Proc. 3rd  ACM­SIAM Symposium on Discrete Algorithms, 1995. Pp.203­210. 76. Bazaraa M.S. and Kirca, O. A Branch­and­Bound­Based Heuristics for Solving the  Generalized Assignment Problem // Naval Research Logistics Quaterly/ vol. 30, № 1, 1983. Pp  287­304. 77. Bellman R. Dynamic Programming. Princeton: Princeton University Press, 1957. ­ 348 p. 78. Bliznova O., Levin V. Application of Priory Information in Knowledge Bases of Expert  Systems // New Information Technologies and Systems (NITS' 94). Proceedings of Intern. Conf.  of Science and Technology: Penza, Russia, 1994. P. 48. 79. Bliznova O., Tuzilov I. On Expert Systems for Simulation of Industrial Ecology // New  Information Technologies and Systems (NITS' 94). Proceedings of Intern. Conf. of Science and  Technology: Penza, Russia, 1994. ­P. 21­22. 80. Borodin A. and El­Yanin R. Online Computation and Competitive Analysis/ Cambridge  University Press, 1998. 134 p. 81. Borodin A., Nielsen M.N. and Rackoff D. Priority Algorithms. In Proc. 13th ACM­SIAM  Symp. on Discrete Algorithms, 2002. Pp. 752­761. 82. Broder A.Z., Frieze A., Lund C. Phillips S. and Reingold N. Balanced Allocations for Tree­ like Inputs //Information Processing Letters, №55 (6) 1995.­ P. 329­332. 83. Burkard R.E. Locations with Spatial Interactions: The Generalized Assignment Problem //  Discrete Location Theory, 1991. P. 387­437. 84. Burkard R.E., and Bonniger T. A Heuristic for Quadratic Boolean Programs with  Applications to Quadratic Assignment Problems // European Journal of Operation research,  Vol.13, 1983. P. 374­386. 85. Burkard R.E. and Stratmann K.H. Numerical Investigations on Generalized Assignment  Problems // Naval Research Logistical Quarterly, vol. 25, № 16 1978. P. 129­148. 86. Carraresi P. and Malucelli F. A New Lower Bound for the Quadratic Assignment Problem //  Operation Research, Vol. 40, 1992. P.22­27. 87. Clausen J., and Perregaard M., Solving large Quadratic Assignment Problems in Parallel.  DIKU, Dept. of Computer Science, University of Copenhagen, June 30, 1995. P. 134­147.88. Edmonds J. Matching and a Polyhedron with 0­1 Vertices // J. Res. NBS, 69B, 1965.­ P. 125­ 130. 89. Frieze A.M., and Yadegar J. On the Generalized Assignment Problem // Discrete Applied  Mathematics, vol. 5, № 1,1983. P. 89­98. 90. Frumkin M.A., Gens G.V., Hemelevskii J.I., Levner E.V. On Computational Complexity of  Optimization Combinatorial Problems. IV Workshop on Combinatorial Optimization // Report  №80159. Bonn. University of Bonn, 1980. ­ 32 p. 91. Gomory R.E. Outline of an Algorithm for Integer Solution to Linear Programs // Bui. Amer.  Math. Soc. V.64, № 5, 1958. P. 275­278. 92. Grant T.L. An Evaluation and Analysis of the Resolvent Eequence Method for Solving the  Generalized Assignment Problem. Master's Thesis, University of Pennsylvania, 1989.­ P. 489­ 501. 93. Gutin G., Punnen A.P. (Eds.) The Traveling Salesman Problem and its j,. Variations.  Dordrecht; Boston; London: Kluwer Acad. Publ., 2002. — 218 p/ 94. Hadley S., Rendl F., and Wolkowicz H. Bounds for the Quadratic Assignment Problem  Using Continuous Optimization Techniques // Integer Programming and Combinatorial  Optimization, University of Waterloo Press, 1990.­ P. 237­248. 95. House R.W., Nelson L.D. and Rado T. Computer studies of a certain Class of linear Integer  Programs // recent advances in Optimization Techniques, ed. by A. Lavi and T.P. Vogl, New  York: John Wiley and Sons, 1965.­340 p. 96. Johnson T.A. New Linear Programming­Based solution Procedures for the Generalized  assignment problem. Ph. D. Dissertation, Clemson University, Clemson, SC. 1992. 97. Itaraki I. Integer Programming Formulation of Combinatorial Optimization Problems.  Discrete Math., 1976, V.16, №1. P.39­52. 98. Kaku, B.K., Thompson, G.L. An Exact Algorithm for the General Assignment Problem //  European Journal of Operation Research, vol. 23, №3, 1986. P. 382­390. 99. Karisch S.E. and Rendl F. Lower Bounds for the Generalized assignment Problem via  Triangle Decomposition // Mathematical Programming, Vol 71, №2, 1995. P. 137­152. 100. Kohler W.H., Stieglitz K. Characterization and Theoretical Comparison of1. V101. Branch­and­Bound Algorithms for Permutation Problems // J. of the ACM. ­1974. V.21,  №1. ­ P. 140­156. 102. Koopmans T.C. and Beckmann M.J. Assignment Problems and the Location of Economic  Activities // Econometrica, vol. 25, 1957. P. 53­76. 103. Kuhn H.W. The Hungarian Method for the Assignment Problem // Naval Research  Logistics Quarterly, №2, 1955. P. 83­97. 104. Lawler E.L. The Cubic Assignment Problem // Management Science, vol. 9, 1963. P. 586­ 599. 105. Lawler E.L. Combinatorial Optimization: Networks and Matroids. New York: Holt,  Rinehart & Winston, 1976. 260 p. 106. Lenstra J.K., Shimoys D.B. and Tardos E. Approximation Algorithms for Scheduling  unrelated P arallel M achines. M ath. Prog., 46, 1 990. P . 2 59271. 107. Li Y., Pardalos P. and Resende M. A Greedy Randomized Adaptive Search Procedure for  the cubic assignment Problem, DIMACS Series in Discrete Mathematics and Theoretical comp.  Science, vol. 16, 1994. P. 237263. 108. Li Y., Pardalos P., Ramakrishnan K.G., Resende M.G. Lower Bounds for the Quadratic  Assignment Problem // Annals of Operation Research, vol. 50, 1994. P. 387­410. 109. Little J.D., M urty K .G. S weeney D.W., Karel C. A n A lgorithm for t he Traveling  Salesman problem // Oper. Res. V.l 1,№6, 1963/ P. 972­989. 110. Munkeres M. Algorithms for the Assignment and Transportation Problems // Journal of the  Society for Industrial and Applied Mathematics, vol. 5,№ i, 1957. p. 32­38. 111. Nugent C.E., Vollman T.E. and Ruml J. An Experimental Comparison of Techniques for  the Assignment of Facilities to Locations // Operations Research, vol. 16, 1968.­ P.150­173. 112. Papadimitriou C.H., Yannakakis M. The Complexity of Restricted Spanning Tree  Problems // Automata, Languages and Programming, ed. H.A. Maurer. Berlin: Springer­Verlag,  1979. 98 p. 113. Resende M.G.C., Ramakrishnan K.G. and Drezner Z. Computing Lower Bounds for the  Generalized assignment Problem with an Interior Point 114. Algirithm for Linear Programming // Operation research, vol.43. Pp. 781791.