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

л,

ШВСЬКИЙ УН1ВЁРСИТЕТ 1М. ТАРАСА ШЕВЧЕША

На правах рукопису КУД1Н Володимир 1ваиович

, УДК 619.652:519.676

Р03Р0БКА I ЗАСТОСУВАННЯ ПРОЦЕДУР А11ШЗУ МОДЕЛЕЙ Л1Н1ЙНОГО ПРОГРАМУВАННЯ ВЕЛИКО! Р03М1РН0СТ1

05.13.16. -застосування обчислювально! техники,

математичиого моделювання 1 математичних метод!в у наукових досл1джаннях

АВТОРЕФЕРАТ

на здобуття вченого ступени кандидата техшчних наук

КИ1В 1993

Робота виконана в лабораторп 342 В1дд1лення Систем керу-вання 1нституту кЮернентики ш. В.М. Глушкова АН Укра!ни та на кафедр! теорП автоматизованих систем факультету ккзернети-ки Кшвсъкого ун1верситету 1м. ТАРАСА ШЕВЧЕНКА

Науковий кер}вник -доктор техн1чних наук, професор

Волошин 0лекс1й Федорович-

0ф[ц1йн| опоненги -доктор технтшх наук, професор

Зайченко Юр1й Петрович

-кандидат ф!эико-математичних наук Мащенко Серпй Олегович

Ведуча оргашзащя -Дн1пропетровський ун!верситет

Захист в1дйудеться 1994 року

о годин! на зас1данн! спещал!зовано1 ради К 068.18.10 в Кшвському ун1верситет1 1м. Тараса Шевченка за адресом: 252127, Ки1в 127, проспект Академ1ка Глушкова, 6, факультет кI(Зернетики, ауд. 42.

1з дисертатею можна ознайомитись у науков1й 01блютец1 Шпвського ушверситету 1м. Тараса Шевченка( вул. Володи-мирська, 58)

Автореферат роз 1 слано "_ " ■__ 1994 року

Вчений секрета? спеЦ1ал1зовано1 ради, доктор техн1чних наук

Т.В.Бейко

ЗАГАЛЬНА ХАРАКТЕРИСТИКА РОБОТИ

Актуадьн1сть теми. Потреби дослгдаення моделей Л1Н1Иного програмування велико! розмдаост! поставили ряд проблем, як1, нер!дко, эастосуванням стандартшх метод!в за прийнятний час не розв'язуються без врахування специфмш i'x структури. Розрхд-жен1сть, розташован!сть ненульових елемент!ь матриц особлиьим чином, наявшсть велико i к1лькост! пасивних 1 неактивних обме-жень( CTOBimtB), як1 не Формують область допустимих 1 оптималь-них розв'язк!в, е характерними властивостями 61лыюст1 практично досл1джуваних великорозм1рних задач. Специфша структури матриц! умов використовуеться при розробц! адаптованих схем ix доел i дження, як! можна под1лити на прям! i шкшдовного анал!зу вар1ант!в. Прям! схеми грунтуються на врахуванш ti специф!ки при представленн! обернено* матриц! в методах знаходження оптимального чи набдикеного розв'язку( Л. Марков Ш, М.Форрест та !н.). Схеми поел1довного анал!зу вар!ант!в( B.C. Михалевич I Н.З. Шор) базуються на скороченш розм!рност! модели в!дс!вом пасивних обмежень та стовпц!в( С.Н. Черн1ков, В.Л. Волкович I О.Ф. Волошин та 1н.); релаксуванням( A.M. Джоффрюн), агрегуван-ням( В.Л. Вен, В.Г. Меднщький) i декомпозузанням( B.I. Цурков, Ю.П. Зайченко та 1н.). Анал1з великорозм!рних моделей л!н!йного програмування суттево ускладаюеться необх1дн!стю розв'язання ряду 1нших задач: усунення несумюност!( I.I. Ерьомт та !н.); системно! оптим!зац!i( В.М. Глушков. та В.Л. Волкович); постоп-тим!защйного досл!дження властивостей моделей при л!н!йних ва-Р1ац!ях окремих елемент!в( I.B. Серпенко, В.К. Леонт'ев та 1н.).

0птим!защйн1 пакети,так!, як GAMS, MINOS та !н. включають процедура перетворення початково! 1нформац11 модел1( формат MPS), настройки модел!, знаходження оптимального розв'язку, до-сл!дження задач! л!н!йного програмування при лшйних вар!ащях окремих елемент1в модел1 на основ! прямих схем. Необх!дн!сть поеднання можливостей посл!довного анал!зу вар!ант!в при побу-дов! процедур дооптим!защйного, оптим1зац1йного I постоптим1-защйного досл!дження моделей велико! розм1рност! 1 прямих схем зумовлюе необх1дн!сть подалъшого вдосконалення метод!в 1 алгоритма л!hi Иного програмування 1 розробки в!дпов!дного прог-рамного забезпечення.

М&Х2 роОоти.

1. Обгрунтування та реал!зац1я базових метод1в I алгоритм1в побудови процедур анал!зу моделей.

2. розробка процедур анал1зу моделей л!н!йдаго програмуван-пя велико! роэм!рност1 на стад1ях дооптим1зац!!, оитим1защ!

I постоптишзаш I.

3. Застосування процедур анал!зу моделей лшйного црогра-мувашш для досл1дження практичних задач.

Наукова новизна.

1. Обгрунтовано 1 реэл!зовано базов! метода досл!дження великороэм1рних моделей: построковий симплекс метод 1 дво}стий поотроковий симплекс метод, як! поедпан1 з процедурами !денти-ф!кащ! пасивних 1 неактивних компонент Сезпосередньо на 1тера-щях метод!в, адаптоваш для вивчення властивостей модел! на Р1зних стад1ях досл!дження. Встановлено ознаки оптимальность несум1сност1, необмеженост! щльово! функцИ, пасивност! I не-активност! обмежень, зв'язку елемент1в схеми в сус!дн!х базисах. Досл!джен1 умови виродаевост! задач!.

2. Розроблено процедури скорочення розм1рност! моделей л!-шйного програмування застосуванням схем агрегування, релаксу-вання, 1дентиФ1кац11 пасивних 1 неактивних обмежень( стовпщв), локал!зац!1 облает! оптимума, знаходження наближених розв'яз-к!в на стад1ях дооштаизащ! I оптимгзацг! .

3. Умови 1дентиф1кацп пасивних 1 неактивних обмежень, стовпщв застосовуван! для ряду симплекс метод!в, як! грун-туються на 1де! опорного базису.

4. Для стад!г постоптим1зац!йного досл1даення модел1 за-пропоновано процедури анал1зу ст!йкост! розв'язку при л1н!йн!й вар1ац1!, таких елемент!в модел!, як вектор1в обмеження, стовпщв, щльово? функцП, дравих частин обмежень. Отримано ощнки "меж несум1сност! 1 пасивносп" обмежень. Досл1даено оптималь-ний розв'язок при л!н!йн1й вар1ац11 параметру у векторах щльово! функцП 1 право! частини обмежень в заданому 1нтервал1.

Практична ц!нн1сть дисвртаЩйно! тоботи. Робота виконува-лась, як розд!ли тем CT.340.0i "Научно-методические основы создания, функционирования и развития РАСУ УССР " 1 СГ.330.01 "Создание и внедрение в эксплуатацию 11-го этапа 11-ой очереди РАСУ УССР" Державного Комиету по Науц! 1 ТехнЩ! 1нститу-

том к1бернетики 1м. В.М. Глушкова АН Укра!ни в 1985-1990рр. Процедури скорочення розм!рност! були застосован1 при розв'я-занн1 задач! "Разработка модели программного обеспечения задачи вариантного планирования производства сельскохозяйственной продукции и рекомендаций по организации агропромышленних АСУ ТП для агрокомбината "Кубань" на стад! i доооптимизацл' в ход! виконання угоди N 175 В1д 25 грудня 1989 року м1ж Все-союзним науково-досл1дним 1 проектно-технолопчним шститутом, м. Москва та 1нститутом к!бернетики, м. Кшв.

Агпюбац1я роботи. Результата робота Допов!дались 1 обго-ворювались на Ц-республ1канськ1й конферент i по проблемам об-числювально1 техшки I автоматизаш I досл1джень, ( м. Алмати, 26 жовтня 1988р), республ1канськ1Й науково-практичнШ конферен-цП "Моделювання планових розрахунк!в 1 д!алогова оптим1зац!ян, ( м. Севастополь, серпень 1990р), Ш-й 1 IV-й конферентi мо-лодих учених I спещал1ст1в Гнституту кгбернетики АН УКра1НИ (вересень 1986р 1 травень 1988р'), сем1нарах 1нституту к!берне-тики АН Укра1ни та кафедр! теорП автоматизованих систем факультету к1бернетики Юпвського ун!верситету.

Публ1квц11. Основн! результата дисертац!i опубл!кован! в роботах [1-9].

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

SMICT РОБОТИ

У вступ! наводиться огляд основних роб1т з досл!джувано1 теми, обгрунтовуеться актуалыпсть та структура роботи, даеть-ся скорочений зм!ст дисертацП.

g петому роздШ приведен! основн! структурн! особли-bocti моделей лшйного програмування. Розглянут1 основн! процедури анал1зу властивостей моделей. .Формально досл!джувану модель можна представйти тр1йною M=<D, Z, А>, де ■

D - включае однокритер!альну щльову Функщю, систему об-межень вигляду

opt BuT, (1.1)

ATuT0CT. • (1.2)

UjjSU^Ug, (1.3)

де opt =(rain, im), 0= < =. * ), A=(aJ-1);j=s^, i=I7m =

= ааг.....ajm>j=T^ e матриця обмекень,

ш, n - розм1рнють моде л! по стовгщям i стр!чкам( для визначе-ност! п»т), В = (blt b2, ... ,bm)- вектор щльовог 'функцИ, С =(с5, с2. ... ,сп)- вектор обмежень, и, 1%, ив е m - вишрн! вакгори шуканих змшних, нижние I верхн!х меж на змити Ранг системи обмекень дор]внюе т. Т- знак транспонування. Влементи модел! належать множит дхйсних чисел. Z -множина процедур анал!зу модели

-В1ДС1ВУ пасивних ) неактивных обмежень( стовпщв); -локал!зац1i облает! оптимуму;

-знаходження оптимального або наближеного допустимого розв'язкгв;

-скорочення розм1рност1 модели -дослютення статусу елемент!в модель таких, як стовпц1 1 обмекення: оптимально активн!, що формують оптимально розв'язок; активн 1, як! утворюють множину до-пустимих розв'язк!в; пасивнК надлишков! чи несуттевО, що не Формують мнокину розв'язк!в: невласн!, як! утворюють несум!сн!сть модели

-визначенняv "меж несушсност!, неактивност! чи па-сивност!" елеменпв модели ст1йкост1 оптимального роз-в'язку при ЛШ1ЙН1Й Bapiami елемешчв модели моделей задано! розм!рност! з властивютю оптимальност! розв'яз-ку при лшШпй Bapiami вектор!в обмежень, стопц!в, правих частин чи окремих елемент!в; динам!ки зм!ни оптимального розв'язку при ШСЛ1ДОВН1Й Л1н1йн1й Bapiami параметру щльово! функц! i чи правих частин в заданому 1Н-тервал!.

А -множила базових алгоритм!в дослхдження. Наряду 1з стандартами процедурами анал!зу, такими, як модиф!кований симплекс метод, будуть застосовуватись при доапдженнях построковий симплекс, метод х дво!стий построковий симплекс метод. Еле-менти аеА мають структуру, ¡до встановлюе в!дношення мик величинами предметноi облает! 1 способом розв'яэаняя задач: а=<Ра, Са, Ра, Qa>, де множили Ра -процедур, що утворюють алгоритм; Са -вар!ант]в схеми анал!зу;

Ра -лрограмних модул!в, як! реалхзують фуннш! Ра;

<За -критерив застосування алгоритму.

Реал!защя дослдаення модел! досягаеться гидключенням процедур алгоритму, що. утворюють мнозшну Ра. В залежност! в!д струк-турних особливостей множили Б, вар!ант1в схеми анал1зу Са 1 критерПв застосування 0а шдключаеться та чи пша процедура 13 множини а .програмно це оэначае актив! зашю в!дпов1дшх програмних модул!в множини Ра.

В другому розд1л! роаглянуп базовГ метода 1 алгоритм1ч-Н1 схеми досл1даення моделей лш1йного програмування вигля-ду (1.1)- (1.3), як! основан1 на твердаеннях, що приводяться нижче.

Введемо необх!дн! позначення. Нехай Р;^-}, = Г7й - еле-менти базисшн матриц! В1, елементи матрищ В^1, оберне-но! до В!; Цэ= (\хо1, и^, ... базисний розв'язок, що

визначаеться 13 системи р!внянь. Вгц^ =с°; аГ=(аГ1. аГ2> • • • • а^)- вектор розкладу коефЩ1ент!в а^. за векторами базису Вг, тобто аг =«131: % =(а01. ао2* •аощ)~ вектор розвинення Шльово! функщI В, тобто В^В,; Аг= а^ -сг- нев'язка г-го обмеження (1.2) у базис! и0; ЛЙ, множит, в1дпов!дно ба-зисних I небазисних обмежень.

В £2.1 викладений построковий симплекс метод, який е ба-зовим при побудов! процедур анал!зу моделК задач 2) на опти-

мальнЮть, скорочення розм!рност1 И в ход1 1терац!йного проце-цесу. Основн! характеристики методу: базис построковий; на 1те-ращях вводяться I виводяться 13 нього стр!чки обмеження задачи безпосередаьо на гтеращях в!дс!ваються пасивн! I неактив-Н1 обмеження модел!; зб1жн1сть до оптимального розв'язку проводиться по допустимим базисним вершинам, при цьому значения Шльово $ функцП зростае^ Приведен! нижче твердаення охоплюють вс! моклив! вар!анти для орган1зац1! построкового симплекс методу.

Визначення 2.1. П1дматрицю Вг матриц! А, утворену ш лШй-но незалежними стр1чками (1.2),(1.3) будемо називати базисной.

Твердаення 2.1. М1ж элементами базисного розв'язку в даох сус!дн!х базисах мають мюце так! сп!вв!дношення :

агк "гк _ _

агк= а^ • а^ «ц. 1=1 .ш; 1*к,

__ ег\. _ ®гк _ ——

егк= а^ • егГегГ а^ а11. 1=1

^"оз ' Л1 • й.

\ =" • =Лг " г=1'т:

В^Ви- - ^ АХ .

Нехай и0- допустимий базисний розв'язок задач!. тобто Iс-нуе базисна матриця В1 така, що В1и^=с° 1 Лг£0, г=ТТп.

т —

Твердження 2.2. Для того, щоб Ви0>Вид 1 розв'язок и0 за-

лишався допустим™ базисним розв'язком задач! (1.1)- (1.3),

необх!дно I достатньо.^щоб юнували так1 номери г I 1, для аок<°. а1к<0 1 > о2 • ^Ьп.

Визначення 2.2. Допустимий базисний розв'язок ип оптималь-

т ф V

ний , якщо Ви05Ви для всIX и, що задовольняють (1.2).

Твердження 2.3. Якщо аокХ) для вс1х к, то и0 -оптимальний базисний розв'язок задач1 (1.1)-(1.3).

Твердження 2.4. Якщо 1снуе 1ндекс к такий, що аок<0, агк-0 для вс1х небазисних г, то щльова функтя задач! необмежена на множит допустимих роз'язк!в.

А-. Ш1П Дг _т т

Твердкення 2.5. Якщо аок<0 1 ^— = г д— , то Ви0>Ви^,

1к

йо-допустимий базисний розв'язок.

Нехай и={и/ а1ит^с1, 1е«П, иг=(и/ а1ит^с1, ).

Визначення 2.3. Обмеження ■ агиТ£сг е пасивним( надлишко-вим), якщо 11=иг.

Нехай и°={ип/ Ви„ =шахВит, адт- множила оптимальних роз-

г

в'язк1в задач! (1.1)- (1.3) 1 и£={ц/ Ви^=тахВит, u£Ur).

Назначения 2.4. Обмеження aji^c-p е неактивним, якщо

m

Твердження 2.6. Для того, щоб обмеження аги ^сг було па-сивним, необх1дно i достатньо юнування базисно! матриц! Bt, В1ДНОСНО ■ ЯКОI ctrk>0 ДЛЯ ВСIX к.

Через в£ позначимо матриц», яка отримуеться !з базисно1 матриц! Bj, що в1дпов!дае базисному розв'язку г^, задач! (1:1)-(1.3), зам!ною стр!чки, що займае к-у позищю вектором щльо-во! функцП, взятии 13 протилежним знаком.

Визначення 2.5. Матрицю В^ будемо називати оптимально базисного, якщо !снуе обернена до не! i B^u^cIq, де üq = (ct, ... . -вц,,, ck+1, ... ,cm)

Твердження 2.7. Для того, щоб обмеження aru -сГ було неактивним, необх!дао i достатньо, щоб 1снувала оптимально базисна матриця в£ , k=l7m, вгдаосно яко! «г1-0 для bcix 1.

Досл!джено питания виродженост!. Побудовано алгоритм!чн! схеми процедур анал1зу на ochobi методу.

В 52-2 викладений дво!стий построковий симплекс метод, який е основним при побудов! процедур анал!зу властивостей мо-дел! 13 множили Z. В цьому метод1: базис построковий; на кож-н!й !теращ! псевдобазиса! розв'язки и0 не задоьольняють об-меженням (1.2); зб!жн!сть до максимуму щльово! функцИ (1.1)' проводиться зверху. На !терац!ях методу шнтифшуються пасив-н! обмеження, шдключаються процедури агрегування, релаксуван-ня, поел!довного анал!зу вар!ант!в.

Визначення 2.7. Допустимий псевдобазисний розв'язок u0 е оптимальним , якщо Bu^BuT для bcix и, що задовольняють (1.2).

Твердження 2.8. Якщо аок>0, к=1,т, то псевдобазисний розв'язок uD е оптимальним, якщо А^О, reJ.

Твердження 2.9. Для того, щоб обмеження агит-сг було па-сивним, необхщю i достатньо ютуванння Bt, в якому k=T7m , l a^Cj,, де uQ -псевдовершина, що в!дпов1дае псевдобазису Вг. •

Твердження 2.10. Якщо АрО, юнуе t 1ндекс к такий,

що ^ок _ min то для вибраних к i 1 нова матриця Б,

aik ~ 11 aii ' аи>о Х1

буде псевдобазисною.

Твердження 2.11. Для несумюност! (1.2) необхшо 1 до-

статньо, щоб у даному псевдобазис! Д1>0, а^О, i=I7m.

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

В §2.3 побудовано процедури анал!зу моделей лШ1йного про-грамування спеЩально! структури. Приведено вар1анти застосу-вання агрегування, декомпозищi, релаксування для досл1дження блочних моделей ai зв'язуючимм обмеженнями I стовпцями на ста-д1i дооптим1зац!1.

В §2.4 розглянуто схеми скорочення розм1рност1 модел1 эа-стосуванням процедур адроксимац!i на стад!i доопмаизацП 1 релаксування на стад!ях дооптим!зашi 1 оптютацП для обмеже-них задач.

Бизначенкя 2.6. Множина Зи апроксимуюча для U, ято Ü£SW. В параграф! Оудуть розглядатися апроксимуюч! множит двох

вид!в: S„, Бц , де Su- апроксимуюча множина для багатогранника

о

1), Su -апроксимуюча множина для оптимальних розв'язк!в на U эа о •

щльо: эю функщею (1.1).

Процедура V^ уточнения меж апроксшуючоi множили, як! отриман1 процедурою- Чт посл!довного анал!зу вар.1онт!в:

U= Ш AViCT. -BuT^ -К^ ), де

, f^ --ш1п( Bu^1^ max BuT. P=Bi£ ).

uen .

=maxi Bu^^mln bJ. Buf )t. i-TTFT. Bu£ }-- uen(p-I)

верхня i нижн! ошнки оптимального розв'язку задач! за

ц!льовою функц!ею, и^?"1и^-1'- вершили, в яких досягаеться мтшальне i максимальне значения щльово! функцП на парале-лешпед! змхнних (р-1) -го кроку

)_ {а/ й(р-1) ¿и^^». 1е1(р-1,£1).

Нехай И^'1» -в!дстань В1д и^"} >=(11^4*(1р)> — «>,>. да + <*&) V2- вершини П^; а

)_ найкоротша в!дстань В1д точки ^ до 1-го обмеження.

Твврдження 2.12. Якщо й{р_1\ то 1-е обмеження неак-•гивне.

Твврдження 2.13. Якщо И, то для неактивност! обме-

т

ження аги необх!дно 1 достатньо, щоб коефЩ1енти розкладу обмеження агит^сг в базис!, що в!дпов!дае дан!й вершин!, були додатн!ми.

Твврдження 2.14. Якщо И, то для неактивност! обмеження агит^сг необх!дно I достатньо, щоб коефипенти розкладу обмеження агат«сг в базис!, що в!дпов!дае данхй вершин! були до-датн!ми, а нев'язка в!д'емною.

Якщо в ход! !терац!й дво!стого построкового симплекс метот ду при доел!дженн! модел! на стадН оптимзацП отримали два недопустим! розв'язки и*, псевдобазиси А^, А§), що е верх-н!ми оц!нками оптимального розв'язку (1.1), (1.2) I допусти- ' мий розв'язок ий, що е нижньою допустимою оЩнкою оптимального

розв'язку( Ви" =р*. Ви|т = Р^, Ви^ =К0, 1'1> то тод! .

симплекс = { и/ Ади^с^, -Вит^-К0), 1 . симплекс

3<г) = ( и/ А^Й Сд, Вти^р|, -Втит5 -К0)

будуть апроксимуючнми множинами для допуст'имих розв'язк!в в ттервал! значень Щльово1 функщI 1К0, Р^] I Р^].

Приведен! процедури уточнения нижньо! допустимо! меж! оптимального розв'язку за щльовою функщею, анал1зу моделей л!-н1йного програмування на оптимальшеть застосувакням релаксу-

вання. тобто тимчасового вшидання певно! частшш обмежень в ход! обчислень 1 побудови початкового базису.

В трвтьом.у тозд1л1 розглянуто алгоритм» процедур аналгзу мбделей Л1н1йного програмування на стад!! постоптим!зац!1.

В S3.1 приведено задач1 постоптим!зац!йного дослшення модел!: ст1йк!стш, звуження, розширення, параметричн1 та 1нш1.

В §3:2 досл1джбн1 умови стхйкост! оптимального розв'язку при лш1йн1й варзацП базисних I небазисних обмежень вигляду (a-j )uT^Cj +Cj. Умовою ст1йкост! оптимального розв'язку и0 при "збуреюп" коефЩ1ент1в право! частини (1.2) вигляду JeJ, j«Jö, е справедлив 1сть нергвност! ¿j -Cj<0. При "збу-ренн!" коеф1ц!ент1в обмеження JeJ, J«JÖ, у вигляд1 (a-,-+apuTiCj умовою ст1йкост1 оптимального розв'язку u0 е справедливють нер!вност1 +ajUo <0. Умовою спйкост! оптимального роз-

в'язку и0 при "збуренн!" вс1х коеф!Ц1ент!в обмеження (1.2) jeJ, 3«JÖ е справедлив:сть нер!вност1 Д^ -c!j <0. За умо-

ви "збурення" базисних обмежень JeJ6 оптимальшсть збер!-гаеться при виконанн!

aoi

~ '1 + а^(Аб )k"0, <ai+ =0-

Задача в!дшукання меж допустимих "збурень" обмежень, як! збер!гають оптимальшсть, може посл!довно розглядатись для кожного обмеження.

В §3,3 досл!джено задач! ст!йкост! оптимального розв'язку при лшйних вар!ац1ях векторхв обмеження, стовптв 1 ц!льо-Boi функт i. Описано в клас1 моделей задано! розм1рност! лшй-н! щльов! функц!i, що мають оптимальним даний розв'язок.

Для . опорно* вершини uQ в базис! Ад1 розв'язок системи не-р!вностей Ьа^^О описуе щльов1 функц! i з властивютю опти-мальност! в u0. Bapiami шльово* функц!! Ь у вигляд! Ъ+Ь', що збер!гають сИйкють оптимального розв'язку и0, визначаються я?с розв'язок системи нер!вностей b' 1-йт .

Розглянуто параметричну задачу л!н!йного програмування у : припущенн! i i невироджешост! i обмекеност!.

В четвертому роздШ описано програмний комплекс, який' синтезуе 13 набору базових иодулдв конкретну схему анал!зу мо-

делей Л1ШЙН0Г0 програмування I ггоеднаний з рядом стандартних пакет1в програм( МРБ-формат). Приведено результата машинного експерименту по використанню процедур анал1зу оптим!защйних моделей на стад!I дооптим!зац1йного досл!дження. Роэглянуто застосування процедур скорочення розм1рност! практично! задач! на стадП дооптим1зац!1.

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

У до да тку представлено матер! али використання результата дасертац!!.

0СН0ВН1 РЕЗУЛЬТАТИ РОБОТИ

1. Розроблено процедури анал!зу моделей л1н!йного програ-мування велико! розм1рност! на р!зних стад!ях досл!дження:

-скорочення розм!рност! моделей, локал1зац!! облает! оптимума, знаходження точних 1 наближених розв'язк!в на стад!ях дооптим!зац!1 1 оптим!зацП;

-СТ1ЙКОСТ! оптимального розв'язку при л!н1йн1й вар!а-ц!I таких елемент!в модел1, як вектори обмеження, стовпц!, Щльова. функшя I окрем! елементи:

-опису в клас! моделей задано* розм!рност! л!н!йних вар1ащй базисних 1 небазисних обмежень, як! збер!гають оптимальн!сть даного розв'язку;

-зм!ни оптимального розв'язку при Л1н!йн1й вар!ац!I параметру в заданих межах.

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

3. Установлен! умови пасивност! 1 неактивност1 обмежень (стовпц!в) можна поширити на ряд "класичних" симплекс метод!в.

4. На баз! алгоритм!чного забезпечення I ■процедур анал!зу моделей л!н1йного програмування велико! розм1рн®ст! розробле-ний програмний комплекс,' який Еикористовувався при досл1дженн! практичних задач.

ПУБЛ1КАЦИ ПО TEMI ДИСЕРТАЦИ

1. Волкович В.Л., Войналович В.М., Кудин В.И. Релаксационная схема строчного симплекс метода // Автоматика.-198?. -N4.- С. 79-86.

2. Кудин В.И. Алгоритм решения задачи линейного программирования на основе релаксации ограничений // СО. тру-трудов II республиканской конференции по проблемам вычислительной математики и автоматизации исследований, ( г.Алмати, 26 октября, 1988г).

3. Волкович В.Л., Войналович В.М., Кудин В.И. Релаксационная схема двойственного • строчного симплекс метода // Автоматика,- 1988> N1.- С. 39-46.

4. Кудин В.И. Релаксационная схема решения задачи линейного программирования с использованием метода последовательного анализа // Автоматика.- 1989.- JíQ. —

С. 42-47.

Б. Войналович В.М., Кудин В.И. Последовательный анализ в методе улучшения плана // Сб. "Моделирование процедур решений в автоматизируемых системах". -1989.- С. 35-39.

6. Кудин В.И. Релаксационная схема решения задачи линейного программирования с использованием метода последовательного анализа // Сб. "Моделирование и оптимизация сложних систем", КГУ, вып. 9, 1990г • 7. Кудин В.И., Шишова Е.А. Решение задачи линейного программирования на основе схем агрегирования и релаксации// Сб. трудов конф. "Моделирование плановых расчетов и диалоговая оптимизация"( г. Севастополь, 1990).-С.28.

8. Волошин О.Ф., Куд1н B.I. Дооптим1защйне досл!дження Л1Н1ЙН01 модел! велико! розм1рност! методами агрегу-вання i поел!довного анал!зу// Вюник Кшвського ун1-верситету, ф1зико-математичн1 науки ( у друЩ). . 9. Волошин А.Ф., Войналович В.М., Кудин В.И. Предоптимиза1-ционные и оптимизационные схемы сокращения размерности задачи линейного программировния //'Автоматика. -1993.-N4.- С. 60-64.