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

< О Ь '-)

РОССИЙСКАЯ АКАДЕМИЯ НАУК ВЫЧИСЛИТЕЛЬНЫЙ ЦЕНТР

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

Миронова Ирина Васильевна

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

05.13.11 - математическое и программное обеспечение вычислительных машин, комплексов, систем и сетей

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

Москва 1992

Работа выполнена в Вычислительном центре РАН.

Научный руководитель: член-корреспондент РАН,

доктор физ.-математ. наук, профессор Ю.Г.Евтушенко

Официальные оппоненты: доктор физ.-математ. наук Б.А.Флеров

кандидат физ.-математ. наук У.Х.Малк Ведущая организация: Институт проблем кибернетики РАН

Защита состоится -/Г- еЛ-'^!'- 199 ¿¿го

в /3 часов на заседании специализированного совета К002.32. при Вычислительном центре РАН по адресу: 117967, Москва, ул. Вавилова, 40.

г

С диссертацией можно ознакомиться в библиотеке Математ ческого института им. В.А.Стеклова.

Автореферат разослан

„А- 1992 года

Ученый секретарь

специализированного совета КОСЕ.32.01 _ доктор £из.-математ. наук /угмЬг—* К-В-РУД8*

библиотека

РОССЙ^СГДЯ

: зтлсл I

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

Актуальность темы исследований. Модели линейного программирования (ЛП) широко используются при решении задач из различен. прикладных областей. При исследовании этого класса моделей основные трудности, как правило, возникают на этапах постановки задачи и анализа результатов оптимизации. С одной стороны, это изъясняется тем, что оптимизация обычно выполняется с помощью :тандартных пакетов и требует специального представления модели j формате этого пакета. В то же время постановку задачи и шализ результатов оптимизации гораздо удобнее и естественнее юсти в терминах прикладной области, так как эти процессы тесно ¡вязаны с имеющейся информационной базой. С другой стороны, [з-за большого объема и сложной структуры исходных данных, :оторые типичны для прикладных моделей ЛП, может оказаться 'рудным этап создания представления модели, ориентированного на меющиеся исходные данные. Поэтому необходимо создавать спэци-1льные языковые и программные средства, которые автоматизируют ice этапы работы с моделью: описание и построение модели, юздание представления модели, ориентированного на имеющиеся [сходные данные, получение задачи в формате пакета оптимизации [ преобразование результатов оптимизации к их представлению в 'ерминах прикладной области.

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

Научная новизна исследований состоит в том, что

- предложен подход к созданию языковых и программных редств постановки задач в системах ЛП;

- разработан язык MDL для представления моделей ЛП;

-предложены понятия С(1,1 )-грамматики с независимыми

имволами и непротиворечивой С(1,1)-грамматики; показано, что ласс непротиворечивых С(1,1)-языков совпадает с классом детер-инированных языков.

Практическая ценность работы состоит в том, что на основа-

нии предложенного подхода была создана система ЬРМОБ, котора применялась для решения ряда прикладных задач, в частност использовалась автором совместно с НПО НАТИ при обосновали перспективного типажа сельскохозяйственных тракторов на перио до 2000 года.

Апробация работы. Основные положения настоящей работ докладывались и обсувдались на Шестом Всесоюзном симпозиум "Системы программного обеспечения решения задач оптимальног планирования" (Пущино, 1980), Десятом Всесоюзном симпозиум "Системы программного обеспечения решения задач оптимальног планирования" (Нарва-Иыэсуу, 1988), научных семинарах ВЦ РАН.

Публикации. По результатам выполненных исследований опуб ликовано 5 печатных работ и подготовлено б научных отчето общим объемом 8 печатных листов.

Структура и объем диссертации. Работа состоит из введения трех глав, заключения, списка литературы и четырех приложений Общий объем работы - 142 страницы, в том числе 7 таблиц Библиография включает 77 наименований.

СОДЕРНАНИЕ РАБОТЫ

Во введении описана поставленная задача и содержали работы по главам.

В главе I рассматриваются различные подходы к создани языковых и программных средств постановки задач в системах Л (СПЗ ЛП), формулируются требования, которым должны удовлет ворять современные СПЗ ЛП, описывается язык моделирования Ш)Ь предложенный автором.

В разделе 1.1 СПЗ ЛП определяются как специальные Языковы и программные средства, которые обеспечивают:

- возможность описания модели ЛП в терминах структур информационной среды прикладной области;

- автоматическую генерацию программ, выполняющих перехо от этого описания к представлению задачи в формате пакет оптимизации;

- автоматическую генерацию программ, преобразующих резуль-■аты оптимизации из формата пакета к их представлению в терми-[ах структуры информационной среда прикладной области.

На основании анализа различных подходов к созданию СГО ЛП I работе делается вывод, что современные СПЗ Ж должны удовлет-юрять следующим требованиям:

- модель формулируется в естественных для пользователя ерминах, при этом может быть несколько представлений одной и ой же модели с разным уровнем детализации;

- обеспечена интеграция по выполняемым функциям и способам редставления данных с пакетом оптимизации и средствами работы

данными прикладной области (СРД);

- имеется возможность работы с большим объемом исходных анных предметной области и моделями Ш больших размеров.

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

Программное обеспечение, предназначенное для исследования рикладных моделей ЛП, обычно состоит из пакета оптимизации, РД и СПЗ ЛП. Для того, чтобы пользователь мог сосредоточиться а содержательном исследовании модели и не уделял много времени ехническим вопросам стыковки отдельных пакетов, необходима нтеграция СПЗ ЛП с пакетом оптимизации и СРД. Интеграция по аполняемым функциям подразумевает, что эти пакеты объединены в циную интегрированную систему оптимизации (ИСО), и доступ к им производится с помощью одних и тех же средств. Интеграция э способам представления данных означает, что все пакеты, ходящие в ИСО, могут работать с одними и теми же данными, не ребуя от пользователя их предварительного преобразования и перекачки".

При создании или анализе достаточно сложной модели, также ак и при работе с любыми сложными программами или алгоритмами,

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

Дальнейшее развитие СПЗ ЛП будет идти в направлении создания многоуровневых систем, в которых уровни отличаются друг oi друга степенью детализации модели. На более высоких уровнях объекты модели могут - рассматриваться без их конкретизации и привязки к исходным данным. На этом уровне удобно создавать или исследовать модель в целом. Объекты нижнего уровня наследую! свойства объектов более высокого уровня.

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

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

дальнейшем, по-видимому, будут создаваться системы с элементами искусственного интеллекта.

Чтобы помочь пользователю описать модель на ЯОМ в тех слу-1аях, когда это описание не порождается автоматически, целесообразно иметь в рамках СТО ЛП синтаксически управляемый редактор, ориентированный на этот язык. Однако использование такого редактора может оказаться очень утомительным при создании новой гадели. Наиболее приемлемым является, видимо, использование редактора для описания отдельных объектов модели, а для анализа структуры модели в целом и при создании новой модели целесообразно использовать методы ограниченного синтаксического анализа.

Среди ЯОМ наибольшее распространение получили языки, которые были названы языками моделирования. Идеальный язык моделирования должен позволять описывать модель в виде, по возмок-гости приближенном к алгебраической записи. Данные и переменные федставляются в нем символически. Связь с реальными данными »существляется другими частями системы моделирования и машинным »кружением.

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

Представление модели на ЯОМ используется для полного и ;етального описания модели. Хотя в многоуровневых системах этот ровень не является верхним, выбору ЯОМ и там следует уделять олыпое внимание. Несомненные преимущества имеют в данном слу-ае языки моделирования. Это объясняется следующими причинами:

1. Если модель строится автоматически (например, по описа-ию объектов, входящих в эту модель, и связей между ними), то ромежуточное описание модели на языке моделирования может

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

2. Часто при описании модели возникает необходимое^ выполнить некоторые вычисления над объектами, уже имеющимися i системе, или каким-либо нестандартным образом записать групщ ограничений (обычно в целях повышения эффективности). Поэтому i любой системе должна оставаться возможность явно задать такие нестандартные действия. Использование универсального языке программирования в данном случае нерационально, так как потребует от пользователя весьма высокой квалификации и знанш некоторых особенностей реализации системы, в то же врем> средств языка моделирования для этих целей вполне достаточно.

3. В СТО ЛП целесообразно выделять две части. Первая част! ориентирована на пользователя. Результатом ее работы является описание модели на некотором промежуточном языке. Вторая часть, обрабатывая полученное описание модели, формирует представление модели в виде, необходимом для пакета оптимизации. Меня! интерфейс с пользователем, можно значительно быстрее создавай новые системы различного назначения. В качестве промежуточной языка удобно использовать язык моделирования, так как это языз высокого уровня, в котором имеются необходимые типы данных.

4. Описание модели на языке моделирования может представлять и самостоятельный интерес. Его легко изменять, дополнять Действительно, если остаются нужными большинство ранее определенных объектов, и необходимо ввести новый объект (используй имеющиеся), то изменению будет подлежать небольшая часть исходного текста. Если изменения модели редки и незначительны, т< надобность в специальном интерфейсе отпадет после того, ка] получено описание модели на языке моделирования.

В разделе 1.2 рассматривается язык MDL, предложенный автором для описания линейных моделей, неформально описываются синтаксис и семантика языка MDL, рассматривается пример использования языка MDL для описания простой модели.

По своему назначению и возможностям MDL является языко) моделирования. При записи модели на этом языке используютс:

тривычные математические понятия: множество, переменна«, ограничение на переменные. Форма записи модели приближена к общепринятой алгебраической.

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

Другой отличительной чертой языка MDL является описание множеств. Оно максимально приближено к общепринятому алгебраическому. Подмножество ранее определенного множества задается просто указанием дополнительных условий для элементов исходного множества.

Глава II посвящена описанию системы LFM0D, созданной автором.

В разделе 2.1 рассматриваются назначение и возможности системы, язык системы, а также некоторые детали реализации.

Система LFM0D входит в состав интегрированной системы Ш/БЭСМ-6, разработанной в ВЦ РАН для решения задач линейного программирования. Система позволяет описывать модель ЛП на ззыке моделирования MDL, рассмотренном в главе I. По этому описанию автоматически генерируется программа, формирующая представление той же модели во внутреннем формате системы ЛП/БЭСМ-б (MG-программа). При этом обеспечена интеграция как по данным, так и по выполняемым функциям с другими подсистемами системы ЛП/БЭСМ-6.

Для обеспечения возможности работы MG-программы с большим количеством исходных данных и моделями ЛП больших размеров в системе LPMOD использовались два приема: сегментация MG-программы и моделирование виртуальной памяти при работе с данными.

Сегментация MG-программы выполняется системой при порождении этой программы автоматически (без участия человека).

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

Для представления моделей ЛП в системе LPMOD используется язык MDL.Полный формальный синтаксис этой версии языка приведен в приложении 1. Изменения касаются типов данных и наличия выполняемых операторов (присваивания, цикла, условного оператора)

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

MG-программа порождается на автокоде БЭСМ-б. Транслятор с языка MDL, генерирующий эту программу, также написан на автокоде БЭСМ-б. Транслятор реализован по однопроходной схеме.

При реализации синтаксического анализа использовалась непротиворечивая С(1,1)-грамматика языка MDL. Этот тип грамматик и алгоритм разбора описаны в главе Ш данной работы.

Элементарные операции языка MDL, не имеющие близкого аналога в машинном языке, моделируются с помощью подпрограмм. Во время выполнения MG-программы библиотека этих подпрограмм постоянно находится в оперативной памяти, занимая около 24 Кбт.

В разделе 2.2 обсуждается опыт применения системы LPM0D для решения практических задач, в частности для решения задачи технико-экономического обоснования перспективных типоразмерных рядов сельскохозяйственных тракторов и самоходных машин (TP СТСМ).

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

Применявшиеся модели характеризуется большим объемом исходных данных, сложными расчетами коэффициентов матрицы и сложной структурой данных. Модели насчитывают до 2000 ограничений и 7000 переменных. Математическая формулировка блочной подзадачи приводится в приложении 2. В приложении 3 дается описание этой же модели на языке MDL.

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

Глава Ш посвящена описанию теоретических основ реализации синтаксического анализа в системе LPM0D. Эти результаты были получены при попытке практического использования С(1,1)-грамматик для реализации языка MDL.

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

Реализация языка MDL в системе LPM0D и последующее его использование при решении прикладных задач ЛП подтвердили практическую работоспособность рассмотренного в главе метода.

В разделе 3.1 приводятся основные определения для С( 1,1 )-грамматик, а также формулируются некоторые необходимые в дальнейшем утверждения.

Определение. Пусть

V-конечное множество символов;

ZcV - множество терминальных символов;

AUA=V\E - множество нетерминальных символов, АПЛ=0;

i/£V - символ, используемый только как признак левого и право ;епочки над алфавитом V;

Р=К11Т - конечное множество правил;

Т содержит правила переобозначения, имеющие вид Ха->ХЬ, где

XeV', аеД, beSUA;

К/fi содержит правила вида XAY-»XwY, где АеЛ, ojçV* ,

XeV'Ujej, YeS'll|e|- и, если о>=е, то Х^е, и Y/e;

SçA - начальный символ. Тогда грамматика G=(V',P,S) называется С(1,1)-грамматикой.

Определение. Пусть G=(V' ,2' ,P,S) - C(1,1 )-грам-матика, ZeV'. Тогда пару символов, принадлежащую множеству C(Z,G)=f(X,Y)€V'*V' |iSi=»*aZp, a,pç(V')t а=а'Х, P=YP'J,

назовем G-контекстом символа Z, символ из множества CL(Z,G)=jx€V' |iSi=>*ap, a,p<E(V')t а=а'Х, p=zp'j,

назовем левым G-контекстом символа Z, а символ из CR(Z,G)=|y€V' |iSi=»*ap, a,pe(V')Î а=а' Z, p=Yp'j

назовем правыгл G-контекстом символа Z.

Вместо "G-контекст" будем писать "контекст", если G подразумевается.

В случае правостороннего вывода рассматриваются множества C^Z.G^X.YKV'xV |iSi-*raZp, a,pe(V' )t a=a'X, p=Yp'},

CLr(Z,G)=|xeV' liSi^ap, a,p€(V')t a=a'X, p=zp'|,

CR^CZ.GÎ^YeV' |iSi^rap, atpe(V')î a=a'Z, P=YP'|.

Определение. Пусть AçA. Обозначим П(А)={ coeV*| 3 YeV'llje}, beS'u|e|: YAb->Ya)bçK }.

Символ A называется независимым (от контекста), если для любой пары (X,a)eOT"(A,G), такой, что , и любой цепочки шеП(А) в К существует хотя бы одно из правил ХАснХша, ХА-»Хш, Аа-члз, А-»ш. В противном случае будем говорить, что А зависит от контекста.

Пусть а^Д. Тогда обозначим Q(a)=| beSUA| 3 YçV': Ya-»Yt>eT j.

Символ aeA называется независимым, если для любых символов XeCLr(a,G) и befi(a) существует правило ХснХЬеТ. В противном случае будем говорить, что a зависит от контекста.

С(1,1)-грамматика называется грамматикой с независимыми символами, если все ее нетерминальные символы независимы.

В теореме 1 показывается, что 0(1,1)-грамматики с независимыми символами эквивалентны контекстно-свободным грамматикам.

В следствии 1 теоремы 1 сформулированы необходимые и достаточные условия для того, чтобы 0(1,1)-грамматика была грамматикой с независимыми символами.

Понятие приведенной С(1,1)-грамматики является обобщением понятия приведенной КС-грамматики.

В теореме 2 сформулированы необходимые и достаточные условия приведенности С(1,1)-грамматики с независимыми символами.

Для символов С(1,1)-грамматики вводятся приоритетные (<•, = , •>) и контекстные (А.с, рс, е, 6) отношения. Отношения <•, =, •> строятся по КС-Грамматикам, которые порождаются по исходной С(1,1)-грамматике.

Определение. С(1,1 )-грамматика называется приоритетной, если она обратима, и множества Хс, рс, в, е, о\А,с, =, '>\ро попарно не пересекаются.

Пусть АеЛ, (X,Y)eCr(A,G). Обозначим n(A,X,Y)={ueV+| 3 XAY-XtoYeK, xejx.jj, Yçjy.ej }. Очевидно, что

П(А)= U n(A,X,Y) U (е\ 3XeV', YeS': XAY-XYeK }.

(x,y)€cr(a,g) ^ j

Определение. 0(1,1 )-грамматика G=(V' ,P=KUT,S) называется полной, если для любых АеЛ, (ХД)еСг(А,С), YeS', o>=Uu=uWen(A,X,Y) выполняются следущие условия: при (Х,и)€\с, (W,Y)epc правило XAY-XuYeK, ■ при (X,U)eA.c, (ff,Y)€• > правило ХА-ХшеК, при (X,U)€<-, (W,Y)çpc правило AY-hoYçK, при (X,U)€<•, (W,Y)e> правило A-koîK.

Определение. Приведенная приоритетная полная С(1,1)-грамматика называется непротиворечивой С(1,1)-грамматикой

В теореме 3 доказывается, что класс непротиворечивых С(1,1)-языков совпадает с классом детерминированных языков.

В разделе 3.2 рассматривается С(1,1)-грамматика языка MDL, приводятся некоторые числовые характеристики грамматики, описываются приемы, которые применялись при получении непротиворечивой С(1,1)-грамматики с независимыми символами по КС-грамматике языка MDL.

В разделе 3.3 рассматривается алгоритм разбора с нейтрализацией синтаксических ошибок для С(1,1)-грамматик.

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

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

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

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

Для С(1,1)-грамматики G=(V',2',P=KUT,S) обозначим

Г=| Ьелил I 3 XçV', аеА: Ха-ХЬеТ |

В теореме 5 доказывается, что, если G - непротиворечивая С(1,1)-грамматика, удовлетворяющая условиям:

для любого правила ХАа-ХшаеК цепочка Хше(У\Г)+,

для любого правила Ха->ХЬеТ символ X€V\T, то для любой цепочки шеЕ* предлагаемый алгоритм выдает разбор этой цепочки тогда и только тогда, когда 0J€Lr(G), и результатом работы алгоритма является пустая цепочка правил тогда и только тогда, когда шД,т'(С).

В разделе 3.4 приводится способ автоматического вычисления контекстов символов КС-грамматик (теоремы 6,7). Ввиду эквивалентности С(1,1)- грамматик с независимыми символами и КС-грамматик указанные теоремы позволяют вычислять множества контекстов для С(1,1)-грамматик с независимыми символами.

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

В приложении 1 приводится формальный синтаксис версии языка MDL, реализованной в системе LPMOD.

В приложении 2 описана математическая модель функционирования машинно-тракторного парка за годовой цикл в отдельном модельном хозяйстве.

В приложении 3 приводится описание модели функционирования машинно-тракторного парка модельного хозяйства на языке MDL.

Приложение 4 содержит доказательства лемм и теорем из главы Ш. .

ОСНОВНЫЕ РЕЗУЛЬТАТЫ ДИССЕРТАЦИИ

1. На основе анализа языковых и программных средств постам новки задач в системах линейного программирования (СПЗ Ж) сформулированы требования к СПЗ Ж. Разработан язык MDL, позволяющий описывать модели Ж в форме близкой к алгебраической.

2. Создана система LPMOD для постановки задач Ж, предусматривающая возможность работы с большими объемами данных и моделями Ж больших размеров. Осуществлена интеграция системы LPMOD с системой ЛП/БЭСМ-б.

3. Предложены понятия непротиворечивой С(1,1)-грамматики и С(1,1)-грамматики с независимыми символами. Показано, что класс непротиворечивых С(1,1)-языков совпадает с классом детерминированных языков. Разработан алгоритм разбора с нейтрализацией синтаксических ошибок, управляемый С(1,1)-грамматикой. Полученные результаты использованы при реализации языка MDL в системе LPMOD.

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

ПО ТЕМЕ ДИССЕРТАЦИИ ОПУБЛИКОВАНЫ СЛЕДУЮЩИЕ РАБОТЫ:

1. Миронова И.В., Станевичене Л.И., Станевичюс А.-И. А. О входном языке генератора матриц // Системы программного обеспечения решения задач оптимального планирования: Крат, тезисы докл. Шестого Всесоюз. симпоз. (Пущино, 1980) М.: ЦЭМИ АН СССР, 1980. С. 118-119.

2. Миронова И.В., Станевичене Л.И. Применение приоритетных С(1,1)-грамматик для описания детерминированных языков // Ж. вычисл. матем. и матем. физ. 1982. Т. 22, * 5. С. 1227-1236.

3. ИзимОетов Е.Т., Миронова И.В., Станевичюс А.-И. А. Пакет прикладных программ МСБ для генерирования входных данных пакетов линейного программирования в МРБ-формате. М.: ВЦ АН СССР, 1984. - Реф. в: Алгоритмы и программы: Информ. бш. 1986. № 1. С. 39. Регистр. Л ГОСФАП 50850000505.

4. Миронова И.В. Система генерирования входных данных для пакетов линейного программирования // Пакеты прикладных программ. Программное обеспечение оптимизационных задач. М.: Наука, 1987. С. 70-89. (Алгоритмы и алгоритмические языки)

5. Миронова И.В. Средства генерации линейных моделей в системе ЛП/БЭСМ-б // Системы программного обеспечения решения задач оптимального планирования: Крат, тезисы докл. Десятого Всесоюз. симпоз. (Нарва-Иыэсуу, 1988) М.: ЦЭМИ АН СССР, 1988. С. 96.

Миронова Ирина Васильевна

Языковые и программные средства постановки задач в системах линейного программирования

Подписано в печать 19/У1 1992 Формат бумаги 60*84 1/1б Тираж 100 екз. Заказ 72. Бесплатно

Отпечатано на ротапринтах в ВЦ РАН 117967, Москва, ГСП-1, ул. Вавилова, 40