Математическое обеспечение задач планирования и управления производством тема автореферата и диссертации по математике, 01.01.11 ВАК РФ

АКАДЕМИЯ НАУК СССР ВСЕСОЮЗНЫЙ НАУЧНО-ИССЛЕДОВАТЕЛЬСКИЙ ИНСТИТУТ СИСТЕМНЫХ ИССЛЕДОВАНИЙ Специализированный совет Д 003.63.02

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

БЕРЕЗНЕВ Валентин Александрович

УДК 519.85 519.86

МАТЕМАТИЧЕСКОЕ ОБЕСПЕЧЕНИЕ ЗАДАЧ ПЛАНИРОВАНИЯ И УПРАВЛЕНИЯ ПРОИЗВОДСТВОМ (для предприятий иногоноиенклатурного и крупносерийного производства)

Специальность: 01.01.II - Системный анализ и автоиатическое управление

АВТОРЕФЕРАТ

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

/еХ2

Москва , 1988 г.

Работа выполнена в Институте проблей кибернетики АН СССР.

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

доктор физико-математических наук Вайникко Г.М.

доктор технических наук Ларичев О.И.

Ведущая организация: Казанский государственный университет им. В.И.Ульянова-Ленина

Защита состоится "_"_1988 г. в_

на заседании специализированного совета Д 003.63.02 Всесоюзного научно-исследовательского института системных исследований по адресу: П7312, Москва, Проспект 60-летия Октября, 9.

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

Автореферат разослан " __1988 "г.

час.

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

специализированного совета, к.ф.-м.н. В.С.Левченков

дел. лаций

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

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

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

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

Основной целью работы является разработка комплекса

-А- .

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

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

Научная новизна работы. В диссертации проведено комплексное исследование основных компонент математического обеспечения оптимального планирования и управления производством. Построены математические модели основных этапов планирования и управления. В области численных методов решения экстремальных задач в конечномерном евклидовом пространстве, соответствующих построенным моделям, разработана методика устойчивого решения этого класса задач при приближенном заедании исходной информации. Развита теория экстремальных задач в конечномерном пространстве. В частности, исследовано . понятие Р-регулярности допустимых множеств экстремальных задач, доказана эквивалентность Р-регулярности множества его регулярности по Лагранжу, доказана строгая и- сильная монотонность минимизирующей последовательности градиентного метода для выпуклой функции из класса С1'1(Е„)> доказана эквивалентность 2-мажорируемости при X = 2 множества решений его регулярности по Люстеряику. Доказана локальная сходимость и получена оценка скорости сходимости градиентного метода при безусловной минимизации гладкой невыпуклой функции.

Практическая ценность работы. Полученные в работе результаты могут быть использованы в теории принятия•решений, теории планирования и управления производством, а также обцей теории экстремальных задач и теории устойчивого решения задач с приближенной информацией. Разработанные в диссертации модели, методы и программные комплексы применяются Ь практике планирования и управления на ряде предприятий легкой промышленности, а также в проводимых в этой отрасли проектных и конструкторских работах. Кроне того, полученные в диссертации результаты используются в курсе лекций "Математическое программирование" , читаемом в Московском университете.'

Апробация работы. Основные результаты диссертации докла-

дывались на Лоионосовских чтениях МГУ (1982 г.), на семинарах кафедры вычислительной математики и кафедры исследования операций факультета вычислительной математики и кибернетики МГУ, на семинаре НИВЦ МГУ, Института кибернетики АН ЭССР, на школе-семинаре "Численные методы высокопроизводительных систеы" в г.Таллине (1986 и 1987 г.г.), на Всесоюзной научной конференции "Математическое обеспечение рационального раскрой в системах автоматизированного проектирования" в г. Уфе (1987), на ГО-ом международном симпозиуме "Автоматизация и научное приборостроение - 87" в г. Варне (Болгария, 1987 г.), на семинаре отдела прикладной математики Института проблем кибернетики АН СССР (1986, 1987 г.г.) и ряде других семинаров и конференций.

Публикации. По теме диссертации опубликовано 23 научные работы, в число которых входит монография.

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

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

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

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

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

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

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

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

F(i)={fi(ï).....Их)),

где ^ i(x),L=i,...- целевые функции оптовых покупателей, на технологическом множестве Х(А), зависящем от величины уступки А по критерию качества предприятия. Если соглашения не происходит, то участники меняют свои стратегии (предприятие значение А, а потребители функции f t) и вновь решается задача векторной оптимизации. В работе рассматривается несколько вариантов свертки векторного критерия F(l), отвечающих различным формам хозяйственных отношений между предприятием и потребителями его продукции. Если участники торга не хотят менять свои стратегии, а соглашение не достигнуто, то принятие решения возлагается на арбитра (ярмарочный комитет).

Вторая модель отличается от первой более активной позицией арбитра. Поведение арбитра на £рмарке моделируется, так называемыми, функциями рационирования. Пусть 1° - предложение предприятия, а X1 - спрос 1-го потребителя. Функции рационирования Ч*'(х",... ,Х"") определяют ограничения на поставку и приобретение продукции. Предполагается, что Ч> 1 удовлетворяют следующий естественным условиям:

(а) V '(Х°.....Xй) < X4 ; '

(б) если спрос на i-ый продукт не превосходит предложения,

т.е. Х° > 2 xj, то Ч* j = Xj для 1=1,. : ; в t

противном случае Ч* * = Х°;

(в) £ Ч> '(Х*.....Xм) = 4>в(х х");

t

(г), функции Ч* (Xе,... ,Хт), 1=0,1,... непрерывны по всем

аргументам.

При условии, что арбитр, задавая ограничения на сделки между партнерами, руководствуется значениями функций рационирования, вводится понятие равновесия торга. Пусть X *(К) -стратегия Ь-го участника на К-ой итерации торга, а - его технологическое множество. В качестве 11(К+1) рассмотрим так называемый вектор активного спроса, получаемый в результате решения следующих задач:

х Лк+1) = агдашС ¡1з-х'(0) II : ч е XIЛ,

где Хи = а23га1п{? !(1) : i е X,л Ф Ф , Х„ = {1 е : х5 < ч* 5> л Ф Л» - л-ая компонента вектора X.

Определение. Назовем равновесием торга такой набор стратегий 1°(к),... ,хт(к), при котором x '(к+1) = х*(к) для всех 1=0,1,...,Ш.

Справедлива следующая теорема существования.

Теорема 1.6. Если функции ^»(Х), 1=0,1,... выпуклы и непрерывны, технологические множества участников компактны, функции рационирования удовлетворяют условиям (а)-(г), то равновесие торга существует.

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

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

- s-

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

Пусть Z Ж - календарный план поставок продукции предприятия, t=i,...,T, Xt - план производства продукции, Ut - план производства полуфабрикатов, узлов и деталей, X-t и U* технологические множества выпускающего и подготовительного цехов соответственно. Тогда календарный план производства (Xt»Ut)»t=i,• • • »T определяется из решения задачи

(xS.u*) е Агашах Шхл : adO-Sdu) < О, Xt<zi, xteXt, UtGUt }, t=i,...,T, (i)

где f(Xt) - целевая функция выпускающего цеха, 9(Х) - функция потребления материалов, узлов и деталей в выпускающем цехе, £(U = Uв + U 1, £(Ut) = ß(Ut-i) - 9(l*-i) + Ut, U, предполагается заданным.

Модель календарного планирования (I) опирается на априорное задание технологических множеств X* и Ut в каждый t-ый период планирования. В практических ситуациях Xt и Ut зависят от множества факторов (в том числе - от факторов случайного характера), поэтому их априорное задание с требуемой точностью крайне затруднительно. В этом случае естественно ставить задачу об оптимальном управлении производством, т.е. определять (Xt,Ut) в начале очередного t-ro периода планирования, опираясь текущее состояние множеств Xt и Ut, а также на известные результаты работы за предыдущие (t-1) периодов.

Рассмотрим сначала модель оперативнрго управления при полном информационном обеспечении, когда.к началу каждого t-'го периода имеется возможность передавать в центр информацию об Xt и Ut ■ В этом случае вычислим вектор t-i

z' t = zt + 22 С» rz") , t> 2, z' i=z*, t»i

где ä» - реальный выпуск готовой продукции за L-ый период, 1=1,...,t-1, а затем решим, задачу

(x*,u«) e Агдтах Cid<) : s(xt) - 8(u,) < 0, Xt < z\, it e Xt, u« e Ut), (2)

i-t

где 8(Ut)4lt ♦ S (g(U,)-3(äi)).t> l,g(Ui)4li, а И, -

lal

реальный выпуск материалов, узлов и деталей за L-ый период. Таким образом, в соответствии с моделью (2) делается попытка уже в t-ом периоде ликвидировать отклонение от календарного графика поставок.

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

Будем предполагать, что центральный орган к началу очередного t-ro календарного этапа вычисляет Z' t и передает этот вектор.в выпускающий цех.

1-ый шаг. Выпускающий цех, получив Н'решает задачу

i' * е АгзтгШх») : itext, it < Z' J (3)

и вычисляет U1 t=[j(l't)-5 t-i]+> где a+^nai{0,a), <§ t_4 -запасы полуфабрикатов, узлов и деталей, имеющиеся на склад», выпускного цеха к началу t-ro этапа. Значение U't передается подготовительному цеху как заявка на детали.

2-ой шаг. Подготовительный цех, получив U t» решмот задачу

üt = azsalnf ||ut - u' t ii : ut e ut) (4)

и передает значение U* выпускающему цеху.

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

Xt е АгдяшШх») : 3(Xt) < Ut + s t-1,

it < z't, I« 6 XO. (5)

Таким образом, процесс (3) - (5) позволяет вычислить управление (Хг,1Ц) на местах. Выпускающий цех, решая задачи (3) и (5), используем только информацию об Хъ а подготовительный цех при решении задачи (4) опирается только на известную ему информацию об и«. Из цеха в цех передаются только векторы и'* и Ц^.

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

{х\и") е Агзшх Шх) : 3(х) < и,

х < г", х е X., и е IIЛ, (6)

Н* - суммарный план поставок по календарным периодам,

^(х) = < р,х >, з *(х) = < В Р 1 С ип» X. = {хеЕп : Ах < в}, и. = {иеЕ: : Йи < сО,

А и Б - технологические матрицы для выпускающего и подготовительного цехов соответственно.

Определение. Назовеи Ч ' е Е К! вектором условных

оптовых цен внутризаводского хозрасчета, если-< > > < >

для всех и Е ив. ®

Обозначив через В матрицу, составленную из вектор-строк

Вь I = 1.....В.

Теореиа 1.7. Если Ч Л (р), где Л(Р) - множество оптимальных двойственных оценок ограничений Вх < . и в задаче (б), то Ч* - условные оптовые цены.

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

Модааь формулируется в форме задачи о нахождении обхода связного графа Г(1),У) > т.е. построении так называемого эйлерова цикла на графе. Поскольку существование эйлерова цикла не гарантируется в общем случае , формулируется задача о приведении графа к виду, в.котором эйлеров цикл существует! Эта задача относится к классу линейных задач с

-и-

булевыии переменными.

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

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

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

Пусть |(СС)ЕС "'(Ер) выпукла. Рассмотрим задачу безусловной минимизации

min { <f(x) : х е Е„ }.

Пусть Y = AzsmLnÜd) : xeEj t- Ф . Для решения задачи безусловной минимизации |{Х) воспользуемся итерационной схемой градиентного метода

хк+1 = хк - (X. i (х„), х.еЕг.» (7)

где величина (Хк выбирается из условия

idJ-Kxx-aJ'ixJ) > sa, ||?'(xK) II2,

0.5 < s < 1. (8)

Будем предполагать, что для К = 0,1,... . После-

довательность {?{ХК)3 является релаксационной, т.е. /

l(xK+i) < I(X«), К=0,1..... 11 Г (X.) II 0

при .

Теорема 2.1. Пусть |(Х) выпукла, минимизирующая последовательность строится по схеме (7), (8). Тогда для любого фиксированного ^gY и всех к = 0,1,... выполняется неравенство 111,,+i-ii II < Их*-» II и fun X« = ¡f'eY,

ч' = а'(х„).

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

Рассмотрим следующую задачу:

|(х) ir,Ln, хеХ={хеЕ„ : з»(х) < 0, L=1.....m).

Функции f(X) и 9i(X), 1=1,...,И предполагаются непрерывно дифференцируемыми. Пусть 1(У)=[ L : = 0 ,

ч е X }.

Ccneia',(a),lgl(a)} =

={неЕ„: z»S a t9\(3),A t>0, Lel(a)]. t

Принцип Лагранжа. В любой точке H=tocmLn (1(Х) : X Е X) выполняется соотношение

-л .Пз)еСопв{У ,(»),1е1(а)}, а . > 0. (9)

Условие регулярности по Лагранжу множества X. Для любой функции |(Х) и любого

ä=-focmLri{|(x) : хеХ)

найдутся такие числа A i = Л i(y-), что выполняются соотношения

-|'(»)=ел a' tin), а.) о, Lelm. do

-

Условие Я-регулярности в точке. Существует такая Б-окрестность II е (У) точки 3 £ X и такое число ОС = ОС(З) > 0, что

3(1) = ВИХ 31(1) > аР(Х,Х), (11)

isl.ll

для веек хеие (з) \ X, где Р(Х,Х) = ||х-рх || -

расстояние от точки X до множества X, Рх - проекция точки X на X.

В дальнейшем будем предполагать, что функции 1(1) и З^(ЭС), 1=1,выпуклы и непрерывно дифференцируемы.

Теорема 2.3. (об эквивалентности). Условие регулярности по Лагранжу множества X выполняется тогда и только тогда, когда выполняется условие Р-регулярности в каждой точке множества X.

Понятие Р-регулярности множества X определяется существованием равномерной по 3 £ X константы (X > 0.

Определение. Множество Х={х : 3 < 0, 1=1,...,ш} называет Р-регулярным, если существует такое число СИ > 0, что для веек X , не принадлежащих X, справедливо неравенство 3(Х) > (ХЯ(Х,Х).

Теорема 2Л. Если множество X ограничено, то условие регулярности по Лагранжу множества X эквивалентно условию Р-регулярности этого множества.

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

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

-ИР = azgmlnC Ii» - x„ II2 : з e Y},

где'У = Azmn{|(xj : X E X}, X = {x E En : 3 4(x) < 0,

L=i,...,m} Ф ф , X0 - заранее выбранная точка из Е„. Предполагается, что о функциях f(X) и 3t(X), 1=1,... ,m известны лишь приближенные данные, т.е. функции f « (X) и 9 « t(X), L=l,...,ffi, с известной степенью точности отличающиеся от |(Х) . и 9 i(X) соответственно.

Основу методики составляет сведение приближенной задачи к задаче безусловной минимизации функции

Ф(Х) = Ф(?*(Х),3* i(X).....3*т(Х)) ,

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

||р - хв II ,где хв е Агзш1п{Ф(х) : х е EJ.

В' § '2,3 обсуждается применение метода штрафов для устой- . чивого решения системы неравенств

34(х) < 0 , L=i,...,m .

в которой информация о функциях 3t(X) задана приближенно. Предполагается, что l3i(X)-3« i(X) | < <5 (1 + ||х II)

для всех 1=1.....Ш и для любого I Е Е„ , где <3 > 0 -

параметр точности задания информации. В этом случае

ФСХ) Ibc-x. г ♦ nh [»; .(х)]-, i<i

где М > 0, Ч > 1.

Теореиа 2.9. Пусть 3t(X). 1=1,...»И выпуклы на Е„ и выполнено условие Р-регулярности множества X. Тогда существуют такие M« > 0 и <3 ' > О, что для всех 5 Е (О, S'] справедливы оценки

IIp - I, II < CS 1/2 . n > Mo при q=l, ||p - a, ¡I < Cá 1/4 , Í1 > S'1 при

причем константа С > 0 не зависит от <3 .

Несколько выше точность приближенного решения получается в случае применения гладкой штрафной функции к решению приближенных систем линейных неравенств < üj,X > - < О,

1=1.....m , НА - А* || < 5 , ||g - ё. || < <3 . здесь

уже не требуется предположения о Р-регулярности допустимого множества исходной системы, так как оно в соответствии с результатами В.В.Федорова выполняется. Однако, и это важно отметить, свойством Р-регулярности обладает и непустое допустимое множество заданной приближенной системы, если к задаче применить гак называемую стратегию <3-расширения, .т.е. рассмотреть функционал Ф(Х) в виде

m

Ф(х)= ||х-хо II2 + НЕ [(< аЛ ЬХ »-С<3)Т .

1 а 1

Определим непустое множество Х'={хеЕ п '• 9 в i(x) <cá,

га

L=l,... ,m}, функцию Ф i (X) = И Ьв j(X)-C<3]*, где С > 0 -

i = i

некоторая константа, и рассмотрим задачу безусловной минимизации функции Ф ff (Х,11) = !|х-хо ||2+МФ а (X). Пусть SR(P)={xeEn : ||х-р || < R, R > 0}. Следующая теорема устанавливает Р-регулярность множества X' равномерную по <3 при достаточно малых (3 >0.

Теорема 2.10. Для любого R > 0 существуют такие числа С" > 0, S с > 0 и а 0 > 0, что при всех <3 Е (0,3 „] и С > С*

шах 1э <» »(х) — с«S | > а.„р(х,Х') 1:1«

для любого X Е SR \ X' .

В этом случае ||р-Хг II < С<5 1УЗ, М > М„ , причем доказательство оценки опирается главным образом на свойство сильной выпуклости функции Ф(Х) .

В четвертом параграфе главы рассматривается задача математического программирования

mlnü(x) : X Е X}, X = {х Е Е„ : 9i(x) <0,1=1,.. .,ш}

с приближенной информацией, подчиняющейся условиям

lid) - f.(i)l < <3(1+ Их ||) ,

1зi(x) - i(x)I < <3(1+ ||х II) , Ui,...,m .

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

Определение. Множество Х={хеЕ„ : 3 t(x) < 0 1=1,..., ii)}

называется X-мажорируемым, если существуют такие числа £ >0,

X > 0, ОС > 0, что для любого xeUE (X) \ X выполняется

неравенство пюх 3 t(l) > OCP*(l,X). i. i ,«i

Функция штрафа строится в виде

i»

Ф(х) = ||х-х„ ||2 + N[f.(x) + MS зв ,(i)], N > 0.

i=i

В предположении Р-регулярности множества X и X-мажорируемости множества Y доказывается оценка при М > М0 :

||р - х* || < C(N<5)1/2 , N > N„ при Ь1, ||р - х* II < С<3 1/4 , N > 8-1/г при Я =2.

Здесь же рассматривается задача линейного программирования

гаш{< 1,х > : хеХ } , X = {хеЕл : Ах - Í < 0}

с приближенной информацией

||А-А. || < 8, IM. || < <3, И-1. II < 8 .

Для этой задачи

Ф(х) = ||х -хо II2 + М< «,х > + ♦ Пг£ [< а. „х > - 6. ,Г •

tal

- -(Т-

Доказано, что ||р-Х в II < С<3 1/2 при М > М„ .

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

Г(х)=й 1(х).....|5(х)3, *Лх)=< ^.х >,} = 1,....,т и

множеством X = {х Е Е„ : Ах-ё < 0}. Предполагается, что

||А-А, И < <3, ||6-ев И < <3, iuvi.il! < 3,

} = . Для этой задачи строится штрафная функция вида

5

Ф(х) = ||х - х„ И2

л= 1

т

+ М5+1£ [< а« „х > - ё4 ,Г 1= 1

и доказывается, что ||р-Х в II < С<3 при М > М0.

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

Нелинейные задачи с приближенно заданной информацией сводятся к задаче безусловной минимизации функции Ф(Х) , которая в общем случае не является выпуклой, поэтому последний параграф главы посвящен применению градиентного метода для решения задач такого класса. В предположении, что множество минимумов У функции Ф(Х) является ¡$-мажорируемым при X = 2, доказывается сходимость метода по аргументу со скоростью геометрической прогрессии. Здесь же показывается . эквивалентность X-мажорируемости при X = 2 множества У его регулярности по Люстернику.

Рассмотрим задачу безусловной минимизации функции *(х) е С1,'(ЕЛ . пусть

У = Агзш1п{ |(х) : х е Еп] Ф Ф , (12)

ие(У) = { х е Еп : р(х,У) < е ) , (13)

• где Я(х,У) = т'т{ Их - ч || : ч е У } .

Предположение. Будем предполагать, что существуют-такие

числа S > 0 и ОО > 0, что для любого XEUe (Y) \ Y выполняется неравенство

J(x) - Г > otP2(x,Y) , (14)

где Г = шш{ |(Х) : X е X }.

Минимизирующую последовательность {хЛ будем строить по схеме градиентного метода

хк+1 = Хк - чРкГ(хк), к=0,1..........(15)

Пусть Зк = Пу(Хк) - проекция точки Хк на множество Y. Выбор величины шага ||х„-и - Хк II по направлению антиградиента подчиним условию

К т и , 2U(xK) - |(Хк-и)] .... l|l-1"lJI ' - |||'(Хк) II • (i6)

Теорема 2.17. Если выполняются условия (12) и (14), последовательность {хЛ строится по схеме (15), (16) , то

fun хк = 3 е Y ,

•к К -> ее

. „ 1ух уг Bxp(-Ctxm)

||1в" * 11 < а 1/2[1-иф(-Са)] *

где и . = |(i.) - Шо). I. е U. (Y) \ Y .

Определение. Множество Т(Х) векторов Z из Еп называется касательным конусом к множеству Y в точке X Е Y , если существует такое. 8 > 0, что X + tz + П (t)EY при tE[0, е] и ||П (t) || = 0(t) . .

Определение. Множество Y называется Т-регулярным (регулярным по Люстернику) в точке 5»е Y. если существует такое S > 0, что для всех X Е Ue {%) П Y выполняются равенства

Т(х) = КегГ(х), dün КвгПх) = dim КегП») .

Теорема 2118. Пусть f(X) дважды непрерывно дифференцируема на Е„-, Y = AzgaiLnCftx) : хеЕ„} Ф Ф. Тогда для

Т-регулярности множества У в точке 3 £ V необходимо и достаточно, чтобы существовали такие Д > 0 и СХ, > 0, что для всех х е им (а) \ У выполнялось неравенство

*(х) - Г > ар2[хЛ) .

Третья глава посвящена описанию прикладного программного комплекса для оптимального планирования и управления производством.

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

Во втором параграфе описывается библиотека программ минимизации, являющаяся базовой библиотекой пакета минимизации МтьРаск Института проблем кибернетики АН СССР.

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

Первая подсистема включена в состав разрабатываемой автоматизированной системы управления производством на Московском комбинате "Трехгорная мануфактура". Вторая подсистема в течение длительного времени (с 1979 г.) эксплуатируется в составе АСУП на Московском производственном трикотажном объединении "Красная Заря", а также внедрена в практику планирования на Ивантеевском трикотажном объединении и Брестской фабрике верхнего трикотажа. Третья подсистема включена в состав математического обеспечения автоматизированного раскройного комплекса с лазерным режущим инструментом, разрабатывав-

мого совместно с рядом других организаций в ПКБ АСУтекстиль-про-м. РСФСР.

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

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

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

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

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

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

5. Развита теория экстремальных задач. В чаотности, исследовано понятие Р-регулярности допустимых множеств экстремальных задач, доказана эквивалентность Р -регулярности множества его регулярности по Лагранжу, доказана строгая и сильная монотонность минимизирующей последовательности градиентного метода для выпуклой функции из класса С1'1(ЕП), доказана эквивалентность X-мажорируемости при & = 2 множества решений его регулярности по Люстернику. Доказана локальная сходимость и получена оценка скорости сходимости градиентного метода при безусловной минимизации гладкой невыпуклой функции.

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

-2<1

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

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

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

I

1. Белобродский А.В., Березнев В.А. Математические модели' оперативного управления производством для предприятий одного класса //Вестн. моек, ун-та, сер.15, 1979, № 3, 61 - 68. '

2. Березнев В.А. Математические модели годового производственного планирования в условиях повышенного спроса на продукцию //Вопросы оптимизации и управления, изд-во МГУ, 1978, 23-32.

3. Березнев В.А. Система автоиатизированного планирования раскроя и производства трикотажного полотна с использованием ЕС ЭВМ //Вопросы оптимизации и управления, изд-во МГУ, 1979, 21 - 36.

4. Березнев В.А. Некоторые вопросы численного решения задачи оптимального производственного планирования //Вопросы оптимизации и управления, изд-во МГУ, 1980, 3-11.

5. Березнев В.А. Математические методы планирования производственной программы предприятий легкой промышленности. М.: Легкая индустрия, 1980.

6. Березнев В.А. О математическом обеспечении системы автоматического раскроя //Математические вопросы задач.оптимизации и управления, изд-во МГУ, 1981, 55 - 61.,

7. Березнева Т.Д., Березнев В.А. Модель согласования интересов участников торга на оптовой ярмарке //Оптимизация и управление, изд-во МГУ, 1983, 55-63.

8. Березнева Т.Д., Березнев В.А. О некоторых аспектах модели-

рования внутризаводского хозрасчета //Оптимизация и управление, изд-гво МГУ, 1985, 16 - 21.

9. Березнев В.А., Пальмова И.Е., Третьяков A.A. Об одной задаче оптимизации раскроя материалов //Численный анализ: методы, алгоритмы, программы, изд-во МГУ, 1983, 'iI - 50.

10. Березнев В.А., Карманов В.Г., Третьяков A.A. О стабилизирующих свойствах градиентного метода //Ж. вычисл. мате«, и матем. физ. 1986, т.26, te I, 134 - 137.

11. Березнев В.А., Карманов В.Г., Третьяков A.A. О безусловной минимизации невыпуклых функций //Ж. вычисл. матем. и матем.' физ. 1987, т..27, )* II, 1757 - 1761.

12. Березнев В.А., Карманов В.Г., Третьяков A.A. О выборе параметра в методе штрафных функций //Ж. вычисл. матем. и матем. физ. 1987, т.27, te 10, 1451 - 1461.

13. Березнев В.А., Карманов В.Г., Третьяков A.A. Устойчивые методы, решения экстремальных задач с приближенной информацией //Препринт научного совета по комплексной проблеме "Кибернетика" АН СССР, 1987.