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

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

Дорожкина Наталия Николаевна

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

ФОРМАЛИЗУЕМЫХ СИСТЕМАМИ ЛИНЕЙНЫХ ДИЗЪЮНКТНЫХ НЕРАВЕНСТВ

Специальность 05.13.18 - «Математическое моделирование, численные методы и комплексы программ»

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата физико-математических наук

Ставрополь 200Э

Работа выполнена на кафедре информационных технологий автоматизированных систем Белорусского государственного университета информатики и радиоэлектроники

Научный руководитель:

кандидат технических наук, доцент Герман Олег Витольдович

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

профессор

Перепелица Виталий Афанасьевич

кандидат физико-математических наук, доцент Сочнев Владимир Георгиевич

Ведущая организация:

Ростовский государственный университет

Защита состоится 19 сентября 2003 г. в 1400 часов на заседании диссертационного совета Д 212.256.05 по присуждению ученой степени кандидата физико-математических наук в Ставропольском государственном университете по адресу: 355009, г. Ставрополь, ул. Пушкина 1, ауд. 214.

С диссертацией можно ознакомиться в научной библиотеке СГУ по адресу: г. Ставрополь, ул. Пушкина 1.

Автореферат разослан « /~» аЛ'Щ'&уъ2- 2003 г.

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

Л.Б. Копыткова

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

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

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

Можно выделить два основных аспекта данной задачи:

1) создание математического аппарата;

2) создание комплекса программ.

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

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

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

Поставленная цель требует решения следующих задач:

1. Построить математические модели и методы решения задач на основе систем дизъюнктных неравенств.

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

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

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

На защиту выносятся следующие основные положения:

1. Математические модели задач производственного планирования и диспетчеризации, формализуемые ограничениями в форме дизъюнктных неравенств.

2. Алгоритм для решения задач оптимизации с линейным функционалом и линейными ограничениями на основе стратегии устранения невязок.

3. Метод для решения задач с ограничениями в форме линейных дизъюнктных неравенств в вещественных числах на основе стратегии устранения невязок.

4. Метод для решения задач оптимизации с линейным функционалом и ограничениями в форме линейных дизъюнктных неравенств.

5. Градиентный метод для повышения скорости сходимости стратегии устранения невязок для задач с линейными простыми и дизъюнктными ограничениями.

6. Статистически оптимальный алгоритм для решения задач с ограничениями в форме дизъюнктных неравенств на основе предложенных сведений к задаче о минимальном взвешенном покрытии.

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

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

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

шанных вещественно-целочисленных задач математического программирования.

3. Разработан метод для решения задач оптимизации с линейным функционалом и ограничениями в форме линейных дизъюнктных неравенств.

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

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

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

Реализация результатов. Теоретические и практические результаты работы внедрены на заводе крупнопанельного домостроения № 1 (г. Минск); на экспериментально-опытном заводе «Политехник» (г. Минск); в учебный процесс Белорусского государственного университета информатики и радиоэлектроники (БГУИР), Международного гуманитарно-экономического института (г. Минск).

Работа выполнялась в рамках двух научно-исследовательских работ БГУИР: «Разработка теоретических основ исчисления спецификаций сложных систем». Раздел II. № ГР 19982351, ГБЦ Т97-321; «Разработка программно-математического обеспечения для быстрого логического вывода в системах принятия решений реального времени». № ГР 19972927, ГБЦТ97-8011.

Апробация работы. Результаты работы докладывались на 63-й научно-технической конференции Белорусского государственного технологического университета (Минск, 1999г.); на XXXV, XXXVIII научно-

технических конференциях аспирантов и студентов БГУИР (Минск, 1999, 2002гг.); на Шестой межвузовской научно-теоретической конференции «Человек. Цивилизация. Культура» (Международный гуманитарно-экономический институт, Минск, 2001г.); на Международной школе-семинаре по геометрии и анализу памяти Н.В. Ефимова (Абрау-Дюрсо, МГУ, РГУ, 2002г.).

Публикации. Материалы диссертации опубликованы в 8 научных статьях, в 2 тезисах докладов, в отчете о НИР.

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

Краткое содержание работы

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

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

Модель задачи оперативного регулирования производственного процесса имеет следующий вид:

А1, А2, Ап - установленные по плану объемы выпуска к моменту завершения планового периода;

Т13 Т2,..., Тп — директивные времена выполнения работ;

Т — истекшее время с начала планового периода (от нулевого момента);

2Х, 2г,2п - выполненные объемы работ к моменту Т;

V/7 = — - плановые скорости производства продукции /-го наимено-

Тт'

вания (7] Ф 0).

Все приведенные величины известны.

Л,, Д2,Ап - планируемые на ближайшем отрезке АТ объемы выпуска.

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

п

>А, > А?;

Ч '

(1) 5>А<Л;;

(3)

2>, а^А*,;

(2) л,>о, / =

(4)

1=1

где с,- - коэффициент, оценивающий прибыль от единицы продукции /го наименования;

¿/,. - коэффициент, оценивающий затраты на изготовление единицы продукции.

Целевая функция устанавливает, что чем больше отставание от плановой скорости V?, тем больше следует установить оперативный планируемый объем А,. Целевая функция задает критерий качества регулирования производственного процесса. Условия (1), записанные в форме дизъюнктного неравенства, означают, что величина Aj не должна быть меньше (больше) некоторого значения минимального (максимального) размера партии Щ (А^), либо равняется 0. Ограничение (2) учитывает «минимальную приемлемую рентабельность» плана выпуска. Ограничение (3) учитывает «общую пропускную способность» системы.

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

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

Теорема 1. Задача решения системы линейных дизъюнктных неравенств с рациональными коэффициентами ЫР-полна.

Теорема 2. Для произвольной системы линейных дизъюнктных неравенств с п переменными х1)...>хп в общем случае нет полиномиального от размеров матрицы коэффициентов А и п сведения к системе простых линейных неравенств с переменными хх,...,хп на основе тотального гомоморфизма, переводящего множество решений исходной задачи во множество решений системы простых линейных неравенств.

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

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

Рассматривается линейная система неравенств вида

VI + ат2Х2 + - + атпХ„ * «„О 5 ^

ЛССу € Я .

Определение. Любое из неравенств системы, в котором а,0 > 0 называется невязкой.

Определение. Невязка, в которой все а у < 0 называется стоп-невязкой.

Если невязок нет, то имеем тривиальное решение хх = х2 =... = хп = 0. Если имеется стоп-невязка, то констатируется несовместность исходной системы неравенств. Рассматриваемая стратегия отыскивает систему без невязок.

Каждый шаг сводится к проведению подстановок для х^, определяемых из невязок. Например, из неравенства аихх +апх2 + ... + а1лхл > аю в предположении, что а1п > 0, получим:

у -ВВ.-ВН. г _ у . -

Лп ~ Л1 — лп-1

а1п а\ п а\п

где 2, - новая неотрицательная переменная, заменяющая хп.

Замена хп проводится во всех неравенствах системы.

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

Доказаны теоремы о сходимости стратегии устранения невязок.

Теорема 3. Пусть система (5) несовместна. Тогда найдется несовместная подсистема, содержащая ровно (п+1) неравенства (п - количество переменных).

Теорема 4. Всякая подстановка = с1 + спгп +... + с/>_,2;>ч с вновь вводимой переменной г вместо гш в совместную систему неравенств, в которую входят переменные гп, ..., , сохраняет свойство совместности.

Теорема 5. Стратегия устранения невязок финитна.

За п подстановок вместо х} {] = \,п) из общей системы (5) получена рассматриваемая далее система вида:

а'иг, + а'п2г +... + а[пгп > а'0;

ат-п,\21 + ат-л,2г2 + — + ат-п,п2п — ат-п,0 '

2)> О, у =

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

Градиентный метод состоит в следующем. Составим задачу оптимизации, введя дополнительные переменные у1:

апхх +а12х2 + ... + аХпхп +ух >а10;

т — »

х1 >0, у' = 1,«;

у, > 0, / = 1,т;

^= У\ У 2 ••• Ут ^ гпах.

Произведя замену у1 по правилам СУН, получим функцию Ь в виде: Ь = -(я]0 - ах -... - а]пх„ + гх )2 -... - (ат0 - атххх -... - атпхп + гт )2 шах

Определим градиент функции Ь в точке х1 = = 0:

, , дь дЬ Ы дь дЬ

grad Ь = -,--,..., , —,...,— ■ '. дх, дх-у дх„ дг, дгт /

| - п I т в точке о

Теорема 6. Пусть %га<1 Ь в точке (0, 0, ...,0) имеет неположительные координаты. Тогда система неравенств несовместна, если она не выполняется в точке (0, 0,..., 0).

Определим те переменные х , для которых ^ > 0 в точке 0. Для ка-

dxj

ждой такой переменной найдем значение корня уравнения -— = 0 в

dL

дх.

.1

точке 0. Определим из корней х'п, х'/2,..., х']к тот, для которого достигает максимума функция ¿{0,0,...,Х^7,0,...,0), например х'г. Теперь отыскивается невязка апхх + апхг +... + а1гхг +... + атхп > <я,0, где а1Г > 0 и

такая, что — наименьшим образом отклоняется от х'г среди всех таких а1г

невязок.

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

Анализ скорости сходимости стратегии устранения невязок базируется на теореме 7.

Теорема 7. Пусть в текущей системе неравенств невязки соответствуют неравенствам с номерами /,, /2, ..., /,. Тогда, если система выполнима, как минимум один из номеров г,, /2, ..., /г определяет неравенство, которое

1) не зависит от других неравенств системы;

2) принимает вид ^>0 в некоторой результирующей системе без невязок.

Предложение 1. Оценка нижней границы числа итераций к имеет вид:

Г

к = 0

т- log 2 v

, где т - число неравенств, h - среднее значение сво-

бодного члена невязки, v - требуемая погрешность.

На основе СУН разработан алгоритм для решения задач линейного программирования. Рассматривается система неравенств (5) с целевой функцией с0 + CjX, + с2х2 +... + спхп -» max, с/ е R.

Алгоритм реализуется следующим образом:

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

(A) получена стоп-невязка - система неравенств несовместна, конец;

(B) получена система без невязок - переход на шаг 2.

2. Возможны два варианта:

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

(B) фиксируем найденный результат ^ = с'0, переход на шаг 3.

3. Предположим существование переменой щ >0, такой что

Щ = С1Х1 + С2Х2 + - + СХ • (6)

Из (6) выражаем переменную х) с положительным коэффициентом и проводим замену х^ во всех неравенствах текущей системы и целевой функции: со +Щ-* тах ;

а^х[ + а[гх2 + + ...+ >д/0;

^Л' + <2*2 + - + а'щ)™к + - + «К ^ ««'о -

4. Если во все неравенства системы входит с положительным коэффициентом, то целевая функция не ограничена, иначе находим максимальное значение м>к, при котором образуется первая невязка, пусть это неравенство I. Увеличиваем целевую функцию, полагая: м>к = а\0 + м>к+] (где м>к+] > 0 - переменная, заменяющая м>к), проводим замену м>к во всех неравенствах системы и целевой функции, переход на шаг 5.

5. Возможны два варианта:

(A) в неравенстве / все коэффициенты при переменных неположительны - оптимальное решение найдено, конец;

(B) из неравенства / выражаем переменную с положительным коэффициентом по правилам СУН, проводим замену этой переменной в текущей системе неравенств, переход на шаг 4.

Начиная с шага 4 стратегия устранения невязок «работает по принципу» стандартного симплексного алгоритма, не используя понятия базиса и базисных переменных. Доказана теорема о сходимости стратегии устранения невязок для задачи линейного программирования.

Теорема 8. Стратегия устранения невязок финитна при решении оптимизационной задачи линейного программирования.

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

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

Решение задачи на системах линейных дизъюнктных неравенств рассматривается для случая, имеющего следующий общий вид: xjZO; ^

~Xj >-dj (aj >0, У = 1,«);

ft > a¡o v/2' > ajo v... v Д >; (7)

fx ^ afo v f" > a2Q v ...v /* > акщ0.

Каждое /-oe дизъюнктное неравенство состоит из простых неравенств f¡ > a't0, где f¡ = а'пхх + а'(2х2 +... + а'тх„.

Определение. Невязкой называется такое дизъюнктное неравенство, в котором каждое простое неравенство представляет невязку.

Определение. Дизъюнктное неравенство является стоп-невязкой, если каждое простое неравенство в его составе представляет стоп-невязку. Определение. Пусть дано некоторое дизъюнктное неравенство: апхг +... + а]пхп > Ъх V ед +... + а2пх„ >b2v... v апхх +... + ашхп > Ьп. Резольвентой этого дизъюнктного неравенства (в предположении, что х; > 0, j = 1, п) является простое неравенство вида:

тах(я,,;а2Х;...;ап)хх +... + тах(я,„\а2п\,..\ат)хп >min(6,;b2..;bn).

Выполнение дизъюнктного неравенства соответствует выполнению хотя бы одного входящего в его состав простого неравенства. Алгоритм реализуется следующим образом:

1. / = 1 (/ - номер блочной итерации). На каждой блочной итерации выполняем стратегию устранения невязок на системе резольвент, построенной по текущей системе линейных дизъюнктных неравенств и дополненной неравенствами вида > 0, j =1, п до тех пор пока:

(A) не будут удалены все невязки - переход на шаг 2;

(B) не будет получена стоп-невязка - система невыполнима.

При этом подстановки проводим одновременно как в систему резольвент, так и в основную систему.

2. Если в основной системе невязок нет, решение найдено, иначе переход на шаг 1.

Доказана теорема о сходимости стратегии устранения невязок для решения задачи с ограничениями в форме линейных дизъюнктных неравенств.

Теорема 9. Стратегия устранения невязок финитна при решении задачи с дизъюнктными ограничениями.

На основе экспериментальных данных построена и статистически обоснована регрессионная модель времени счета дизъюнктных задач с т неравенствами и п переменными:

tM = 16,2 -1,86 -п + 0,00012 • т + 0,014 • т -п, из которой следует полилинейная в среднем вычислительная сложность алгоритма (число переменных п варьировалось от 10 до 50, число неравенств т - от 100 до 200).

8-приближенный метод для решения задач оптимизации на системах линейных дизъюнктных неравенств состоит в следующем.

Пусть i - номер итерации я S'- система линейных дизъюнктных неравенств вида (7) на итерации /, причем,

F' - ахх[ + а2х2 +... + а„х'п -> шах - функционал для S'. (8)

Для S' строится система резольвент с функционалом (8), после чего решается задача линейного программирования на основе «симплексного» варианта стратегии устранения невязок. Возможны следующие исходы:

(A) F' = Ъ < оо и х - допустимая точка - решение найдено;

(B) F' = Ъ < оо и х - недопустимая точка;

(C) нет допустимых точек - исходная система S' несовместна.

В случае (В) процесс поиска продолжается на системе, полученной из S' следующим образом: делаем замену переменных:

хх = х* + щ -v,; *

uJt Vj >0,; = Ъп.

Функционал (8) переписываем в виде

Ь-ах (х* +щ -v,)-аг (х*2 +и2- v2) -... - а„(х* +un-vn) ~> min. Замена исключает «старое» решение, а функционал «означает» наименьшее ухудшение рекорда Ь. Конечность процесса можно гарантировать, добавляя в систему неравенство

ах(хх + щ - v,) + ... + а„(х* +u„-v„)<b-s, (9)

где е > 0 - достаточно малая величина.

Если при таком добавлении система резольвент, станет несовместной, то вместо ограничения (9) добавляется ограничение

ax{x\+ux-vx) + ... + an(x*n+un-vn)>b-s. (Ю)

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

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

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

1. Введением булевых переменных приводим систему дизъюнктных неравенств к системе неравенств с булево-вещенственными переменны-

,ми.

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

Таким образом, мы получаем задачу псевдобулева программирования.

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

1. Избавляемся от отрицательных переменных заменой: х] = 1 - х] .

2. Для каждой переменной вводим контрарную переменную с малым коэффициентом.

3. Для каждого ограничения формируем матрицу покрытия ограничения.

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

Предложение 2. Оценка существования покрытия с числом строк к имеет вид:

1 1

12л \2к +1

х (И)

\2(п-к) + \ V U

где п - число строк объединенной матрицы покрытия ограничений; к = п/2 - размер искомого минимального покрытия; т - число различных столбцов объединенной матрицы покрытия ограничений;

^-fX'-ä-f^}

да D-

где & =0, если п-рп<к; p = YJ-L,

ыт

где р, - плотность единичных элементов в столбце /.

Выполнение соотношения (11) устанавливает завершение итераций с ответом «нет решения», если оно не было еще найдено.

Среднее число присоединенных столбцов-резольвент оценивается как:

тр «(« + 2,41).т^/Л/ГГР (12)

Соотношение (12) указывает на полиномиальную сложность алгоритма в среднем.

Для оценки вероятности существования покрытия с меньшим весом также используется соотношение (11), но пересчитанное для взвешенной матрицы покрытия.

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

Характер зависимости А, от величины [v" определяется фор-

мулой

^ = -A,(oj или iM) =С, - CAW, (13)

где С, = С |Д(0) = 0

ГА.

-ф-T-Zj |, Сг = С, причем С определяется из условий:

A (T) = Am-Z{T)' (14)

Решение дифференциального уравнения (13) дает

(1(С2Щ)-СХ) сг' (с2д(0-с,)

= -сИ,

С + е~С2'+С1 откуда Д(/) = —-

Из (14) и (15) определяем планируемые объемы А,,..., А„ для t = AТ. С учетом этого задача принимает следующий вид оптимизационной задачи булевого программирования:

V-Ъ

ГГ

Г , _-С2ДГ+С3 N

Ед1 с"

/=1

дf

С» У и

А?

шах

С,

/=1 \ ^

2/

-С2ДГ+С3

>а;

<а;

^ = 1,.,»', Д е {0,1} причем л' ограничивает пересчет только теми индексами для которых Д,->Д?.

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

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

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

Рассмотрены модели задач практической реализации.

В приложениях приведены примеры реализации методов; результаты сравнения программной реализации СУН для задач с ограничениями в форме линейных простых и дизъюнктных неравенств с коммерческими программами Microsoft Excel, MathCad, DiscoGrad, с программной реализацией алгоритма Харрис; документы, подтверждающие внедрение результатов диссертационной работы.

Заключение

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

1. Разработан метод и алгоритм для решения задач с ограничениями в форме линейных дизъюнктных неравенств в вещественных числах [4].

2. Разработан метод и алгоритм для решения задач оптимизации с линейным функционалом и ограничениями в форме линейных простых и дизъюнктных неравенств [4].

3. Разработан градиентный метод для повышения скорости сходимости стратегии устранения невязок при решении задач на системах линейных простых и дизъюнктных неравенств в вещественных числах [3].

4. Разработан статистически оптимальный алгоритм для решения задач с ограничениями в форме линейных дизъюнктных неравенствах на основе предложенных способов сведения к задаче о минимальном взвешенном покрытии [2, 7-10].

5. Проведены экспериментальные и теоретические оценки сложности алгоритмов [3, 4].

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

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

1. Герман О.В., Кузьмина Н.В., Дорожкина H.H. Логические аспекты проблемы распознавания доказательств // Гуманитарно-экономический вестник. - Мн.: ЗАО «Веды». - 1998. - № 4. - С. 121-127.

2. Герман О.В., Дорожкина H.H. Об одной общей задаче производственного планирования //Труды Белорусского государственного технологического университета. Выпуск VII. - 1999. - С. 29-33.

3.Герман О.В., Дорожкина H.H. Различные приложения стратегии устранения невязок // Вестник Ставропольского государственного университета. - 1999. -№ 18. - С. 73-85.

4. Герман О.В., Дорожкина H.H. Стратегия устранения невязок для задач с дизъюнктными неравенствами // Вестник Ставропольского государственного университета. - 1999. - № 20. - С. 85-99.

5. Дорожкина H.H. Объектно-ориентированные технологии в автоматизации производства // Труды Белорусского государственного технологического университета. Выпуск VIII. - 2000. - С. 145-154.

6. Разработка теоретических основ исчисления спецификаций сложных систем. Отчет о НИР (заключит.) / БГУИР; Рук. темы Герман О.В. -№ГР 19982351, ГБЦ Т97-321. - Мн., 2000. -120 с.

7. Герман О.В., Дорожкина H.H. Статистически оптимальный алгоритм для задач линейных дизъюнктных неравенств //Гуманитарно-экономический вестник. -2002. -№ 1. - С. 93-98.

8. Герман О.В., Дорожкина H.H. Метод решения задач, формализуемых на основе систем линейных дизъюнктных неравенств /БГУИР. - Минск, 2002, - 9 с. - Деп. в БелИСА 04.07.02, № Д200261 // Реф. сб. непубл. раб. - 2002. - № 1 (24). - С. 88.

9. Герман О.В., Гончарова E.H., Дорожкина H.H. Статистически оптимальный подход к решению NP-полных задач большой размерности //Вестник Ставропольского государственного университета. - 2002. -№31.-С. 12-16.

10. Герман О.В., Дорожкина H.H. Метод решения дизъюнктных задач большой размерности // Труды участников Международной школы-семинара по геометрии и анализу памяти Н.В. Ефимова, Абрау-Дюрсо, 5-11 сент. 2002г. /МГУ, РГУ. - Ростов-на-Дону, 2002. - С. 239-241.

Изд. лиц.серия ИД № 05975 от 03.10.2001 Подписано в печать 23.06.2003 Формат 60x84 1/16 Усл.печ.л. 1,1 Уч.-изд.л. 0,85

Бумага офсетная Тираж 100 экз. Заказ 91

Отпечатано в Издательско-полиграфическом комплексе Ставропольского государственного университета. 355009, Ставрополь, ул.Пушкина, 1.

~~ ( ^GfÇ

Р 126 9 5

ВВЕДЕНИЕ.

ГЛАВА 1. МОДЕЛИ ЗАДАЧ ПЛАНИРОВАНИЯ И

ДИСПЕТЧЕРИЗАЦИИ. ИХ ФОРМАЛИЗАЦИЯ И АНАЛИЗ МЕТОДОВ РЕШЕНИЯ.

1.1. Модель задачи оперативного регулирования производственного процесса.

1.2. Модели задач теории расписаний и планирования.

1.3. Модель задачи распределительного типа.

1.4. Принадлежность задачи линейных дизъюнктных неравенств к классу NP.

1.5. Возможные варианты сведения системы линейных дизъюнктных неравенств к системе простых неравенств.

1.6. Выводы.

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

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

2.1.1. Существо стратегии устранения невязок.

2.1.2. Доказательство финитности стратегии устранения невязок.

2.1.3. Градиентный метод для повышения скорости сходимости стратегии устранения невязок.

2.1.4. Анализ скорости сходимости градиентного метода.

2.1.5. Вариант реализации стратегии устранения невязок без неравенствО-блока.

2.2. Задача линейного программирования.

2.3. Выводы.

ГЛАВА 3. МАТЕМАТИЧЕСКИЕ МЕТОДЫ НА ОСНОВЕ СТРАТЕГИИ УСТРАНЕНИЯ НЕВЯЗОК ДЛЯ РЕШЕНИЯ ЗАДАЧ НА СИСТЕМАХ ЛИНЕЙНЫХ ДИЗЪЮНКТНЫХ НЕРАВЕНСТВ.

3.1. Стратегия устранения невязок для решения задач на системах линейных дизъюнктных неравенств в вещественных числах.

3.2. Построение модели времени счета задач на линейных дизъюнктных неравенствах.

3.3. Задача оптимизации на системах линейных дизъюнктных неравенств, е- приближенный подход.

3.4. Статистически оптимальный алгоритм для задач линейных дизъюнктных неравенств.

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

3.6. Выводы.

ГЛАВА 4. РАЗРАБОТКА КОМПЛЕКСА ПРОГРАММ ДЛЯ

АВТОМАТИЗАЦИИ ИССЛЕДОВАНИЯ И РЕШЕНИЯ ЗАДАЧ, ФОРМАЛИЗУЕМЫХ СИСТЕМАМИ ЛИНЕЙНЫХ ДИЗЪЮНКТНЫХ НЕРАВЕНСТВ.

4.1. Объектно-ориентированные технологии в автоматизации прикладных задач.

4.1.1. Иерархия классов.

4.1.2. Диаграмма классов.

4.2. Синтаксис спецификаций в форме Бэкуса-Наура.

4.3. Реализация.

4.4. Примеры моделей задач практической реализации.

4.4.1. Технологический процесс изготовления изделий на заводе крупно-панельного домостроения №1.

4.4.2. Технологический процесс изготовления плат.

4.4.3. Задача раскроя материала.

4.5. Выводы.

Современные системы автоматизации решения задач характеризуются широким спектром используемых моделей. К числу важнейших относятся модели задач диспетчеризации (оперативного регулирования) и планирования. Задачи планирования отличаются от задач диспетчеризации большей неопределенностью и большей длительностью временного интервала. Оперативное регулирование призвано обеспечить требуемую динамику производственного процесса с целью выхода на установленные директивные сроки и плановые показатели. Эти задачи имеют сложный математический характер, особенно для многономенклатурных дискретных производств (электронное машиностроение и оборудование, вычислительная техника и радиотехника, приборостроение и т.п.). Для решения этих задач применяются разнообразные методы теории оптимизации, как дискретной, так и вещественной, теории расписаний, теории очередей, массового обслуживания и другие, включая также эвристические и приближенные методы. Это разнообразие подходов и принципов не позволяет решать задачи планирования и управления современным производством на основе единой достаточно универсальной платформы. Наличие множества методик, подходов и алгоритмов, реализованных, как правило, на разных теоретических платформах не позволяет выбрать и единую программную платформу, и уже незначительное изменение условий производства при переходе от одних систем к другим связано зачастую с выбором новых пакетов и новых математических методов. Таким образом, создание универсальных программно-математических платформ является одним из важнейших направлений в автоматизации решения задач планирования, диспетчеризации и управления.

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

Отметим наиболее значимые работы в развитии численных методов решения задач математического программирования.

Юдин Д.Б., Гольштейн Е.Г., Немировский А.С., Шор Н.Э. [81, 82] разработали методы типа эллипсоидов для решения задач выпуклого программирования, а также указали случаи их эффективного решения.

Хачиян Л.Г. [76] разработал вариант метода эллипсоидов для задач линейного программирования. Метод совершенно отличается от большинства предыдущих подходов к линейному программированию тем, что в нем почти полностью игнорируется комбинаторная природа задачи, имеет полиномиальную оценку сложности. Несмотря на большое теоретическое значение алгоритма, он оказался на практике менее эффективным в своей реализации по сравнению с симплекс-методом, характеризующимся с точки зрения теории сложности экспоненциальной временной сложностью. Наиболее очевидным среди большого числа препятствий является требование большой точности вычислений. С другой стороны нет убедительных свидетельств в пользу того, что алгоритм эллипсоидов заведомо не может использоваться на практике.

Н. Кармаркар [41] создал метод проективных преобразований, как основу полиномиальных алгоритмов в линейном программировании. Его сложность, однако, лишь незначительно меньше сложности метода эллипсоидов.

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

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

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

1) последовательного анализа вариантов (разработанного Михалевичем B.C. и Шором Н.З. [50, 51]);

2) методов ветвей и границ (предложенного Лэндом и Дойгом и развитого Литтлом, Мурти, Суини и Кэрелом);

3) методов отсечений (идея которого предложена Данцигом [34] и развита в работах Гомори)

4) локальной оптимизации (предлагаемого Сергиенко И.В.[65]).

Разработанная методология последовательного анализа вариантов оказала влияние на развитие вычислительных методов оптимального управления (например, метода локальных вариаций, предложенного Н.Н. Моисеевым и его учениками [53]), с успехом использована для решения широкого класса дискретных задач оптимизации в работах В.А. Емеличева и его учеников [37].

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

Определенный интерес представляют исследования, связанные с решением широкого класса задач комбинаторного типа. Для решения такого рода задач к настоящему времени разработан ряд алгоритмов, сочетающих процедуры симплекс-метода и ветвей и границ, базирующихся на алгоритме В.А. Трубина для решения целочисленных задач специального вида [71]. Близким к методам ветвей и границ является алгоритм Балаша [5], предназначенный для решения целочисленных задач с булевыми переменными, и его модификации.

К настоящему времени накопился значительный опыт в разработке и использовании алгоритмов, вкладывающихся в общую схему метода ветвей и границ. Эти алгоритмы отличаются между собой способами ветвления, вычислением оценок (границ) [43, 51, 74]. В [67, 78] предлагается комбинировать метод ветвей и границ с другими методами. Однако решение многих практических задач большой размерности с помощью алгоритмов ветвей и границ проблематично, при точном решении задач дискретной оптимизации обнаруживаются патологические задачи, для которых объем вычислений близок к полному перебору.

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

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

В работах Габасова Р. и его учеников [1, 2, 3, 13, 14] развивается адаптивный метод, который возник в результате анализа классического симплекс-метода. Основная цель обобщения - избавиться от некоторых недостатков симплекс-метода и создать метод, который можно использовать для решения динамических задач линейного программирования. Идеи адаптивного метода получили развитие в алгоритмах решения различных задач математического программирования и оптимального управления. Они легли в основу разработанного Габасовым Р., Кирилловой Ф.М., Костюковой О.И. метода опорных задач, который также был обобщен на различные типы экстремальных задач.

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

Для разработки достаточно универсальной математической платформы необходимо выделить класс задач, для которого можно сформулировать общий и эффективный подход к решению. Можно перечислить разнообразные, известные из литературы, задачи планирования, диспетчеризации и управления, модели которых формально сводятся к системам линейных дизъюнктных неравенств. Анализ литературы показывает, что методов решения дизъюнктных задач, учитывающих их специфику, нет, а число работ, посвященных их решению незначительно. В [7, 43, 57] решение таких задач сводится к решению частично целочисленной задачи. Задача целочисленного линейного программирования (ЦЛП) (а тем более частично целочисленная) является NP-полной (при ограничении на размер величин переменных), такие задачи, по общему мнению, не разрешимы за полиномиальное время [30, 33, 47, 66]. Т.е. сведением дизъюнктных задач к задачам дискретной оптимизации, мы, возможно, получаем более сложную задачу. В [38] решение дизъюнктной задачи предлагается сводить к решению некоторой совокупности задач линейного программирования.

Таким образом, актуальность разработки «собственных» методов решения дизъюнктных задач очевидна.

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

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

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

Поставленная цель требует решения следующих задач:

1. Построить математические модели и методы решения задач на основе систем дизъюнктных неравенств.

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

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

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

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

3. Разработан метод для решения задач оптимизации с линейным функционалом и ограничениями в форме линейных дизъюнктных неравенств.

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

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

На защиту выносятся следующие основные положения:

1. Математические модели задач производственного планирования и диспетчеризации, формализуемые ограничениями в форме дизъюнктных неравенств.

2. Алгоритм для решения задач оптимизации с линейным функционалом и линейными ограничениями на основе стратегии устранения невязок.

3. Метод для решения задач с ограничениями в форме линейных дизъюнктных неравенств в вещественных числах на основе стратегии устранения невязок.

4. Метод для решения задач оптимизации с линейным функционалом и ограничениями в форме линейных дизъюнктных неравенств.

5. Градиентный метод для повышения скорости сходимости стратегии устранения невязок для задач с линейными простыми и дизъюнктными ограничениями.

6. Статистически оптимальный алгоритм для решения задач с ограничениями в форме дизъюнктных неравенств на основе предложенных сведений к задаче о минимальном взвешенном покрытии.

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

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

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

3. Разработано программное средство для решения одного варианта задачи оптимального раскроя и упаковки материала, позволяющее повысить точность раскроя на 5-10 фигур в сравнении с эвристическими методами за практически приемлемое время.

Результаты работы внедрены:

1. На заводе крупнопанельного домостроения №1 (г. Минск).

2. На экспериментально-опытном заводе «Политехник» (г. Минск).

3. В учебный процесс Белорусского государственного университета информатики и радиоэлектроники (БГУИР), Международного гуманитарно-экономического института (г. Минск).

Связь работы с крупными научными программами. Работа выполнялась в рамках двух научно-исследовательских работ БГУИР:

1. «Разработка теоретических основ исчисления спецификаций сложных систем». Раздел II. № Гос. регистрации 19982351, ГБЦ Т97-321.

2. «Разработка программно-математического обеспечения для быстрого логического вывода в системах принятия решений реального времени». № Гос. регистрации 19972927, ГБЦ Т97-8011.

Апробация работы. Результаты работы докладывались на 63-Й научно-технической конференции Белорусского государственного технологического университета (Минск, 1999г.); на XXXV, XXXVIII научно-технических конференциях аспирантов и студентов БГУИР (Минск, 1999, 2002гг.); на Шестой межвузовской научно-теоретической конференции «Человек. Цивилизация. Культура» (Международный гуманитарно-экономический институт, Минск, 2001г.); на Международной школе-семинаре по геометрии и анализу памяти Н.В. Ефимова (Абрау-Дюрсо, МГУ, РГУ, 2002г.).

Результаты изложены в 8 научных статьях, в 2 тезисах докладов конференций, в отчете о НИР.

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

4.5. Выводы

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

Предложенная платформа характеризуется двумя основными чертами:

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

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

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

Для задачи резки предложена математическая модель, задача резки материала на прямоугольные формы решена практически и подтверждена актом внедрения. Исходя из прилагаемой оценки сложности математической модели, разработанные методы могут быть рекомендованы при резке листа на 5-10 форм.

ЗАКЛЮЧЕНИЕ

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

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

2. Разработан метод и алгоритм для решения задач оптимизации с линейным функционалом и ограничениями в форме линейных простых и дизъюнктных неравенств.

3. Разработан градиентный метод для повышения скорости сходимости стратегии устранения невязок при решении задач на системах линейных простых и дизъюнктных неравенств в вещественных числах.

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

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

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

1. Альсевич В.В. Математическая экономика. Конструктивная теория: Учебное пособие. Мн.: ДизайнПро, 1998. - 238 с.

2. Альсевич В.В., Габасов Р., Глушенков B.C. Оптимизация линейных экономических моделей: Статические задачи: Учебное пособие. Мн.: БГУ, 2000.-210 е.: ил.

3. Балашевич В.А., Основы математического программирования. Мн.: Вышэшая школа, 1985. - 173 с.

4. Балашевич В.А., Андронов A.M. Экономико-математическое моделирование производственных систем. Мн.: Ушверсггэцкае, 1995. -240 е., ил.

5. Банк Б., Белоусов Е.Г. и др. Математическая оптимизация: Вопросы разрешимости и устойчивости. М.: МГУ, 1986. - 216 с.

6. Барский А.Б. Планирование параллельных вычислительных процессов в многопроцессорных системах. М.: Машиностроение, 1983. - 400 с.

7. Буч. Г. Объектно-ориентированное проектирование с примерами применения: Пер. с англ. М.: Конкорд, 1992. - 519 е., ил.

8. Буч. Г. Объектно-ориентированный анализ и проектирование с примерами приложений на С++. 2-е изд. /Пер. с англ. М.: Издательство Бином, 1998. - 560 е., ил.

9. Волокитин Е.П. О представлении непрерывных кусочно-линейных функций //Управляемые системы. Новосибирск: Наука. - 1979. - № 19. -С. 14-21.

10. Габасов Р., Кирилова Ф.М. Методы линейного программирования: В 3 ч. -Мн.:БГУ. 1977-1980.

11. Габасов Р. Кирилова Ф.М., Тятюшкин А.И. Конструктивные методы оптимизации. Ч. 1. Линейные задачи. Мн.: БГУ. 1983. - 214 с.

12. Герман О.В. Вариант исчисления противоречивых множеств для экспертных систем //Материалы 1-й Украинской конференции УКРПРО-98. Киев: НАН Украины. - 1998. -С. 519-523.

13. Герман О.В. Обобщенный статистически оптимальный метод решения задачи о минимальном взвешенном покрытии 0, 1 матрицы // Экономика и математические методы. - 1994. Т. 30. - Вып. 4. - С. 139150.

14. Герман О.В. Принцип групповых резолюций в логике предикатов //Человек и экономика. 1995. - №3. - Деп. в Белинформпрогноз 04.01.95. - № Д19952. - С. 35.

15. Герман О.В., Гончарова Е.Н., Дорожкина Н.Н. Статистически оптимальный подход к решению NP-полных задач большой размерности // Вестник Ставропольского государственного университета. 2002. -№31.-С. 12-16.

16. Герман О.В., Дорожкина Н.Н. Метод решения дизъюнктных задач большой размерности // Труды участников Международной школы-семинара по геометрии и анализу памяти Н.В. Ефимова, Абрау-Дюрсо, 5-11 сент. 2002 г. /МГУ, РГУ. Ростов-на-Дону, 2002. - С. 239-241.

17. Герман О.В., Дорожкина Н.Н. Метод решения задач, формализуемых на основе систем линейных дизъюнктных неравенств / БГУ ИР. Минск, 2002, - 9 с. - Деп. в БелИСА 04.07.02, № Д200261 // Реф. сб. непубл. раб. -2002. -№ 1 (24).-С. 88.

18. Герман О.В., Дорожкина Н.Н. Об одной общей задаче производственного планирования // Труды Белорусского государственного технологического университета. Вып. VII. — 1999. -С. 29-33.

19. Герман О.В., Дорожкина Н.Н. Различные приложения стратегии устранения невязок // Вестник Ставропольского государственного университета. 1999. -№ 18. - С. 73-85.

20. Герман О.В., Дорожкина Н.Н. Статистически оптимальный алгоритм для задач линейных дизъюнктных неравенств // Гуманитарно-экономический вестник. 2002. - № 1. -С. 93-98.

21. Герман О.В., Дорожкина Н.Н. Стратегия устранения невязок для задач с дизъюнктными неравенствами // Вестник Ставропольского государственного университета. 1999. - № 20. - С. 85-99.

22. Герман О.В., Кузьмина Н.В., Дорожкина Н.Н. Логические аспекты проблемы распознавания доказательств // Гуманитарно-экономический вестник. -Мн.: ЗАО «Веды». 1998. - № 4. - С. 121-127.

23. Герман О.В., Найденко В.Г. Статистически оптимальный алгоритм для задачи о минимальном покрытии // Экономика и математические методы. 1993. Т. 29. - Вып. 4. - С. 662-668.

24. Гимади Э.Х., Глебов Н.И., Перепелица В.А. Исследования по теории расписаний. В сб. Управляемые системы. Новосибирск: Ин-т математики СО АН СССР, 1974. - Вып. 12. - С. 3-12.

25. Гимади Э.Х., Глебов Н.И., Перепелица В.А. Алгоритм с оценками для задач дискретной оптимизации //Проблемы кибернетики. 1975. -Вып. 31.-С. 35-42

26. Глебов Н.И. Об одном классе выпуклого целочисленного программирования // Докл. АН БССР. 1983. Т. 27. - № 7. - С. 581-583.

27. Гольштейн Е.Г., Эльстер К.-Х., Мовшович С.М. и др. Методы оптимизации в экономико-математическом моделировании. М.: Наука, 1991.-448 с.

28. Гончаров В.Н. Оперативное управление производством: (Опыт разработки и совершенствование систем).- М.: Экономика, 1987. 120 с.

29. Горох О.В. Сильно полиномиальные алгоритмы решения некоторых классов задач математического программирования: Дис. канд. физ.-мат. наук. Мн., 1992. - 137 с.

30. Гэри М.Р., Джонсон Д.С. Вычислительные машины и труднорешаемые задачи. Пер. с англ. М.: Мир, 1982. - 416 с.

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

32. Дорожкина Н.Н. Объектно-ориентированные технологии в автоматизации производства //Труды Белорусского государственного технологического университета. Вып. VIII. - 2000. - С. 145-154.

33. Дорожкина Н.Н. Практическая апробация стратегии устранения невязок для задач линейного программирования //Человек. Цивилизация. Культура: 6-я межвуз. научн.-теорет. конф.: Тезисы докл., Минск, 20 апр. 2001г. /МГЭИ. Минск, 2002. - С. 286-288.

34. Емеличев В.А. Дискретная оптимизация. Последовательные схемы решения // Кибернетика. 1972. - № 2. - С. 102-121.

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

36. Закревский А.Д. Алгоритмы синтеза дискретных автоматов. М.: Наука, 1971.-512с.

37. Закревский А.Д. Логические уравнения. Мн.: Наука и техника, 1975. -96 с.

38. Кармаркар Н. Новый алгоритм полиномиальной трудности для задач линейного программирования // Кибернетический сборник. Нов. серия. -1989. -№29.-С. 84-112.

39. Конвей Р.В. и др. Теория расписаний. М.: Наука, 1975. - 359 с.

40. Корбут А.А., Финкелынтейн Ю.Ю. Дискретное программирование. Под ред. Д.Б. Юдина. М.: Наука, 1969. - 368 с.

41. Кофман А. Методы и модели исследования операций. М.: Мир, 1966. -432с.

42. Кофман А. Методы и модели исследования операций: Целочисленное программирования. М.: Мир, 1977. - 432 с.

43. Ларичев О.И. Объективные модели и субъективные решения. М.: Наука, 1987.-142 с.

44. Лесин В.В., Лисовец Ю.П. Основы методов оптимизации. -М.: МАЦ, 1995.-340 с.

45. Математический аппарат экономического моделирования. Под ред. Е.Г. Гольштейна. М.: Наука, 1983. - 367 с.

46. Мирзоян Н.А. Луч-метод и опыт решения задач ЦЛП // Математическое моделирование и дискретная оптимизация. Сб. статей. Вычислительный центр АН СССР. 1988. С. 20-29.

47. Михалевич B.C. Последовательные алгоритмы оптимизации и их применение // Кибернетика. 1968. - № 2. - С. 85-89.

48. Михалевич B.C. Кукса А.И. Методы последовательной оптимизации в дискретных сетевых задачах оптимального распределения ресурсов. -М.: Наука, 1983.-208 с.

49. Михалевич B.C. Шор Н.З. Численные методы многовариантных задач по методу последовательного анализа вариантов. В. кн.: Научно-методические материалы экономико-математического семинара. - М.: 1962. - Вып. 1. - С. 15-42. - (Ротапринт/АН СССР ЛЭМИ).

50. Моисеев Н.Н. Численные методы в теории оптимальных систем. М.: Наука, 1971.-424 с.

51. Муртаф Д. Современное линейное программирование. М.: Мир, 1984. - 224 с.

52. Немировский А.С., Юдин Д.Б. Сложность задач и эффективность методов оптимизации. М.: Наука, 1974. - 383 с.

53. Основы современных компьютерных технологий. Учебное пособие. Под ред. проф. А.Д. Хомоненко. СПб.: КОРОНА принт. 1998. - 448 с.

54. Пападимитриу X., Стайтлиц К. Комбинаторная оптимизация: Алгоритмы и сложность. М: Мир, 1985. 510 с.

55. Первозванский А.А. Математические модели в управлении производством. М.: Наука, 1975. - 615 с.

56. Перепелица В.А. Об одной задаче теории расписаний // Кибернетика. -1966.-№ 5.-С. 75-78.

57. Пшеничный Б.Н., Данилин Ю.М. Численные методы в экстремальных задачах. М.: Наука, 1975. - 319 с.

58. Разработка теоретических основ исчисления спецификаций сложных систем. Отчет о НИР (заключит.) / БГУИР; Рук. темы Герман О.В. № ГР 19982351, ГБЦ Т97-321. - Мн., 2000.

59. Романовский И.В. Алгоритмы решения экстремальных задач. М.: Наука, 1977.-352 с.

60. Саати Т. Целочисленные методы оптимизации и связанными с ними экстремальные проблемы. М.: Мир. 1979. - 302 с.

61. Сергиенко И.В. Математические модели и методы решения задач дискретной оптимизации. Киев: Наук, думка, 1985. - 384 с.

62. Сергиенко И.В., Лебедева Т.Т., Рощин В.А. Приближенные методы решения дискретных задач оптимизации. Киев: Наук, думка, 1980. -276 с.

63. Соломенцев Ю.М. Управление гибкими производственными системами. М.: Машиностроение, 1988. - 351 с.

64. Схрейвер А. Теория линейного и целочисленного программирования: В 2 т. М.: Мир, 1991. Т. 1- 2. - 702 с.

65. Танаев B.C., Шкурба В.В. Введение в теорию расписаний. М.: Наука, 1975.-256 с.

66. Тамм Б.Г., Пуусепп М.Э., Таваст P.P. Анализ и моделирование производственных систем. -М.: Финансы и статистика. 1987. 191 с.

67. Таха Хэмди А. Введение в исследование операций: В 2 т. М.: Мир, 1985. Т. 1-2.-975 с.

68. Трубин В.А. О методе решения задач целочисленного линейного программирования специального вида // Докл. АН СССР. 1969. - № 5. - С. 952-954.

69. Уздемир А.П. Динамические целочисленные задачи оптимизации в экономике. М.: Физматлит. 1995. - 288 с.

70. Фаулер М., Скотт К. UML в кратком изложении. Применение стандартного языка объектного моделирования. Пер. с англ. М.: Мир, 1999.- 191 е., ил.

71. Финкелынтейн Ю.Ю. Приближенные методы и прикладные задачи дискретного программирования. М.: Наука, 1976. 264 с.

72. Хачиян Л.Г. Выпуклость и алгоритмическая сложность задач полиномиального программирования // Изв. АН СССР, Техническая кибернетика. 1982. - № 6. - С. 46-56.

73. Хачиян Л.Г. Полиномиальные алгоритмы в линейном программировании //ВМ и МФ, 1980. Т. 20. - № 1. - С. 51 -69.

74. Хачиян Л.Г. Сложность задач линейного программирования. М.: Знание, 1987.-31 с.

75. Черников С.Н. Линейные неравенства. М.: Наука, 1968. - 488 с.

76. Шор Н.З. Методы минимизации недифференцируемых функций и их приложения. Киев: Наук, думка, 1979, - 200 с.

77. Шор Н.З. Метод отсечения с растяжением пространства для решения задач выпуклого программирования //Кибернетика, 1977. - № 1. - С. 94-95.

78. Юдин Д.Б., Немировский А.С. Информационная сложность и эффективные методы решения выпуклых экстремальных задач //Экономика и математические методы, 1976. Т. 12. - №2. - С. 357-369.

79. Benchekroun В. A nonconvex piecewise linear optimization problem // Computers Math. Applic., 1991. -V. 21. - № 6/7. - P. 77-85.

80. Gorokhovik V.V., Zorko O.I. Piecewise affine functions and polyhedral sets // Optimization, 1994. V. 33. - P. 209-221.

81. Gunluk Oktay, Pochet Yves. Mixing mixed-integer inequalities //Math Programm, 2001. - № 3. - C. 429-457.

82. Kripfganz A., Schulze R. Piecewise affine functions as a difference of two convex functions // Optimization, 1987. V. 18, - № 1. - P. 23-29.

83. Lesaja Goran. Interior-point methods and modern optimization codes // Zb. rad. Sveuc. Zagrebu. Fak. organ. I inf., Varazdin, 1999. № 2. - C. 167-196.

84. Peng J., Roos C., Terlaky Т. Новый и эффективный метод внутренних точек с большим шагом для линейной оптимизации // Вычисл. технолог., -2001.-№4.-С. 61-80.