Исследование комбинаторной структуры классов деформированноых 3-многогранников и их применение к решению задачи оптимального раскроя тема автореферата и диссертации по математике, 01.01.09 ВАК РФ

МИНИСТЕРСТВО ВЫСШЕГО И СРЕДНЕГО СПЕЦИАЛЬНОГО ОБРАЗОВАНИЯ ‘ РЕСПУБЛИКИ УЗБЕКИСТАН

ИССЛЕДОВАНИЕ КОМБИНАТОРНОЙ СТРУКТУРЫ КЛАССОВ ДЕФОРМИРОВАННЫХ 3-МНОГОГРАННИКОВ И ИХ ПРИМЕНЕНИЕ К РЕШЕНИЮ ЗАДАЧИ ОПТИМАЛЬНОГО РАСКРОЯ

ТАШКЕНТСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ имени В. И. ЛЕНИНА

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

ХУЖАЕВ Туймурад Худдисвич

0I.0l.0J) — математическая кибернетика

АВТОРЕФЕРАТ

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

Ташкент — 1992

Работа -ВЫПОЛНИ в Ташкентском государственном ушг--'. верситете имени В. Й. Ленина. - ' '

кандидат . физико-математич^. ских наук, доцент А. К. Пулі атов. .

доктор физико-математических наук, профессор А. Д. Коршунов,

кандидат физико-математических наук Г. И. Ибрагимов.

УзНПО «Кибернетика» АН РУз.

Защита диссертации состоится « ^

199 2, года в « }Ч » часов на заседании специализиро-валного совета К 067.02,13 в Ташкентском государственном университете им. В. И. Ленина по адресу: 700095, Ташкент', ВУЗгородок, ТашГУ, факультет прикладной математики и механики, ауд. А-205.

С диссертацией можно ознакомиться в научной библиотеке ТашГУ им. В. И, Ленина (ВУЗгородок).

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

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

Автореферат разослан о\._____ *9

Ученый секретарь специализированного совета,

доктор физ.-мат. наук, доцент /^^г^^^^МЙРЗАЕВ И.

:уднше;:зЦ

ОІЛЦАЛ ХАРАКТЕРИСТИКА РАБОТЫ

а.». .існ&агауа лшхггь темы. Исследование комбинаторно-мегрическол струн Сі дел мссёДОЦи*'

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

- многие природные образования и технологические изделия имеют Форму выпуклого многогранника (кристаллы, детали машин, юеелмрнмо наделил и т.д.>;

- множества всех решают системи линейный неравенств является випуклим многогранником;

- оипуклме тола аппроксимируется випуклими многогр^ннками.

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

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

Нель работы. Целью диссертационное работы являются:

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

- изучение в том или ином смисле оптимального раокрол изделии на

тел Оормы випуклого многогранника, ■

- применение разработанного метода оптимального раскрои напелин к

раскрою кристалла бездефектного алмаза под бриллианты круглій: и

фантазийных Форм.

ОДщан методика выполнения иссло дона пип Методика нииледогмпн;!

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

ДПСІфЬ'ЖОН Іі КОМбИНаТОрНОІІ reOMOTpr.iL

Научная попиано диссертации состоит в сладумпом:

- рассмотрена изманамш различная метрически;! параметров многогранника, т.о определит понятия деформации млогогрлнпшеоо;

- сравнительно анализируются различные типы доформаций;

- научается класс веек комбинаторно ноэквипалоипшк многогранников о п вершинами и р гранями как класс деформированная ішогогранникш;

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

- описан некоторый осЭДип подход к решению задачи оптимального раскроя изделии;

теопатичвс1сая и практически ценность. В диссертации изучена комбинаторная структура випуклих многограшшкои н оптчналышй р&скрои издолки <йорми випуклого многогранника. Результаты диссертации могут быть ислользовапи в теоретических работал при иэучотш комйипаторно-мвтричоской структуры одпуклш: многогранников . Результати также имоют прикладное иначенио. Разработан камбииаторпо-гвсмэтрич&ския метод оптимального раскрои кристаллов беадоф&ктпык алмазов под бриллшнги круглій и Йашаэппннк форм.

Роелизацня результатов работа. Результаты диссертации (Зшш примени ни при создании математического осіаспечешія для ПЭВМ, ниодрииного в СІСТВ "КРИСТАЛЛ", и ориентированного іс район и їй задачи отииапыюго раскроя сырья адназа

АпрснЗищш набог». Гопулі.г-дін диссертации доклплмппл«сь и

0спстт4!'!(! КОІГЇ’ЧрчЧШКІ 110 млчвмат И’КИЛТОМУ 'К;<Н'ПЧ'!'’1Г. ршятоипл.ного р^спрон и сиогоман адтоматтирпиоткн

прооіп ироімтш С У Я'*. 1997 5, нп III Рсосошнск сомі кпро "Лиохро'і няя математика и о о іірнліжсшіш’’ <Москнп ЛУЭО). пл V Ікясогоно. нау ’«і ю- ток» »ич « мал шяц-орчншш по сопти ліпи) її піриінчснтаю ргинштии пданэ^'Ф^И. \ тноамчй го нрнэшдотш » ХІІ-ХЛІ cm гнл'П к«я ССиожтск, 13ІШ. a ток-с-.і па с«ікпкг>рах ''Лионратиая математика и оч лршюкокип" СТасіҐУ, К’ПУ-ІЯ'ЛХ

ІІубді-mam;і). Иа rorw дпссорпишп опуОлпхспапо у работы. Структури и обгон резолі. Диссорто ні іонная рпботп состоит то поядонип , трох г.пйп и списка яит-зратурн из 50 ппимписткіііии. Сбднп абгам раОотн -09 мпиинописпих стрсмінн.

СО/ЭРИНИЕ ДИССЕРТАЦИИ Во пкздонин пр’.іииди re/і оо'зор результата, имогаих прякоо или косім нни-з отіюяоішо к диссертации, обоснсшоавтся актуальность поотдплошшк зодпч, и излагавтсп краткое содорзашіе диссертации.

D пчріюп глаио определены понятна деформации многогранника М, пороздог -чо многогранника. Исслодувтсл взаимосвязи между

различными тинами деформация многогранников из класса (П'л>р)

комбинаторно ноэкоиналвптинх многогранников с п ворщинамн и \; граилки.

В параграфа 1.1 вводятся необходимые определения и dl„?u: ymt.t Пршзодои определения основних типов дд^ормацип. Пусть гвопстшнныэ многогранник’!! М с п вершинами и М с р воршинами агдлнн ^?итпот-стгюнно utcroHcn линопных наргігюнсто, по имоицоП изОнточнпі; нпр:лг>ііісі н и координатами єоррин в подг.рноп сисюгм хсзрдинат.

Нэм'шпиио лишь линяпных параметров гранен многогранника М , при котором оигггома, соотр-зтствуг'ктл измененному многограннику лпля^тсл сопмоптноп и ннкпкоч нврпронстро этоп спотами не око.еот-пп шуточным, н- л’пится линопно ограниченной деформацией <Л0Д>. '<1->м'Ч1>я!ио линопнчк и угловнх параметров гранчи К, при котором порогдасісп попуст о?? ограничониоо множество и никакое неравенства

ІГ-МИЮтіОП ОИОГМНН, ПО ЛПЛЛ'ПСЯ НЭ0НТОЧНЦМ, НПЭ«РЕ>ОТСП

лі ■ огно-углоооп ограниченное деформацией ОІУОД). її ім^тю-у глотан ограниченная деформация многогранника И, при •чгороп сохраняются смокнооги Гранин по робру , называется • рщтминной лп^ормацисп <0Д>. Кзмононио лишь полярных радиусої? ірг.нпі многогранника м" , при котором суиостпуот р-вершиииая ннуклал (^улочка поро>?донішх ворами и начало систем» координат •пялится гщутр'ншон точкой, иоэыоаогсл полярно ограниченной Л0С,);’ч.\щ-!>-1П <ГЩ>.

И'м-ьч-чнмч полнрннх ролиусо» и угловых порог чггроо вершин ин^г’-'гранни.ка м" , при которой существует р-воркинная випуклая олопочко порохдонннк яоршин . называется полярно-угловоп огранич-ніноп лоії-ормміиоп СПУОД). Поллриа-угловап ограниченная Г/’^рьапил многогранника М* . при котором сохраняются сменности ікірлип по ройру , называется сї-вримчскн ограниченной деформацией ССОД).

Многогранник ,пор?ял<)мш;п от С-уголькой пиромили М* некоторой о:'типа ЛОЛ или ОД ^ПОЛ или СОД), називаотся с-босЗконныи кли;г.'.: < -омонол пирамидон >.

Пусть 'і1! і’-нокотор;гп из ояр?додонник пкпо ті лов деформации и и"’-’ г:.о/. ко;юиилгерио кзгжиио&лонткнх многогранник-

с к •••■ --г пк.гогрт-чг.н-п М„ п-хрч/спрм деформации тепа

<)еГ. Если для каждого многогранника И (е (П' н кллссо .

VI

гПШ ,(1еГг> существует двопг.Ганнин ому многогранник и , наоборот, для каждого многогранника М*б<л^Ны ЛеГ^) а классе гпСИ.> оущ^тпуйт двопитевшнж ому многогранник, то многогранники И и И** иаанвзатоя дгюпстпаниимн относительно деформаций <ЗеГ 1 и <1еГг. иначо - нодвопствэиными относительно деформация !1 ген

<1е?^ и -мвкоториз типи деформации.

Рассмотрения таких деформация 1-11.1 а от как таорвтпчэскоо так и практическое гзнкчвнпо. Например, кристалл алмаза идеально» Я-орни имоот &орму гжтлэлрл и в реальных условиях растят подчиняясь сзакопу постоянства углов . Следовательно, кристалл аллаза подо лиру етол ниигпгранником по класса гп'Ий*ЯОД> , гхь !.!д-пктазлр. Известно, что в природе кристаллы алмаза встрэчаптся в 1? разновидностях по Ферма.

Понятия обоСщшишя клин и ломаная пирамида играют важнуи роль при ИЭУЧОВИН ВЗЗПМОСВЯЗеН Нв'ЯЛУ различии?»! типами дз$арна«ил. Псслздовгнив двсПотеэнности мпогограш.тисов относитольно деформация показнвзот, чю при изучении ол.-юг^, и;» них мезко будет сулить. о комбинаторной структура класса мюгограннмгсо» . порсэдгакних другим. Понятия поронсдаедих многогранников вводятся в параграфа 1.2. Приседам их корогк.-;а определения. Сначала дадим вопомогатэлышо определения.

Если существует тжоторнп многогранник И <~Г1~£М.Л0Д> и нним»сл некое чем по три элемента из шгоаеств Жк> и !К1) . (VI. что грыпа иноп;грш:ии:са М0 соотсдтстоуьщнз эгим элокантам инцидентна кокотороя рарвнна В <многогранника М0>. то воршинц В!( и многогранника М маэивакгтся линейно зависимыми, иначе - линейно независимыми* ГД9 IКк}-множество номеров граней инцидантних

ь-оршшш В(., 1 -'к .

Eonu сукаотву&т иекоторпи ыюгогргшиис П*єнУГ:’ >І10Д> іі наііпагсу,

чю »!apiiiviH:i і.п«оп)і'і)аііі«-ік&. Ц* соотвйтотьувдіїх этим ^лзиоіггаи г.шіидеитнц некоторой грана Г »то грани Г‘!( і і і‘3 мііУ.сграпипка Ц* назішактоп ловдрио зависимыми» иначэ - полярно нонашс;;

по шфію-аао! і; ш . То к jo ішк&іш>м АОД ы.огогромшкл h н^аозна^оо

ііаоив&л-тся ішрохід&шщіціі и:іОГО.ізеИіНк-а::.і для ЛОд a І'ООТГ; а ТОТВй ііНО.

0'іііСТї;„г, >!іо iid выклик м:іогсгран<іііК кмміт с-^кигі, із і:-.

Г(0рі-^ла>:г;агс >іїтГ0Г';;Цї;:;іь<а . П<аПр:и<..:р, !.‘q о 5

і.зрпшь'«-;і не і,ойат ся’/шіті. а клчзита-з пораі.'дзwj гч.

і.ііт;т,граімлкс- , t::n\i:.iy чи» иосридстиои ПОЛ мсі.к.і ііОЛУііічі, йуго-г;:ип,.л:. іі, <[-.нс.І,о> о б взрашії-'мі и 5 гр^ияим. Ij cuo.j «ічурсль, і!іі;сакяпл ПОД гп <ьаг< уяопші.гь чизло гр&кзй шсглгр&ышка Н, , пз»гему k..v-гс» доіиш -Ц і.йііііітсп пар^і:'іЮіи;и иис!гаграш.п:чы Лін!

по Кі’.а.'іПііі! нз{)£і по три ь;>з<мнг& пз иноьасть ?J (О і: І! Сі). !г»'1.

VJUC IlM<K>-UHOi.aCiuO UQlSvpQQ BOpWUI иііцидсатних Г pul ill Г,. J^k.l^n.

Пусть нвкотсріш tie pate iu кшгогргнникг. К ыэхду одіоп мичИ’то-вовнсиь.'.а и иокотераз гр«нк н.-.'зпй'рьнпша Н ' ичхду ссбоа

VMiilibKSSVb ЧИСЛА его DtipfiiW И НЛКОКЛГЫ ІРД иного,груПШіК-і !Г' K5b;rsaov!-:o уио-нь.шть чюло его гр&нап. (и;згогр£шиц-’м И a U

В шірої раФо 1.3 иссладуэтсн взаимосвязи иакду ргкшпикчч типами дпформацип многогранника. Докапано, что для каждого ипсго-граішиїсп класса г/^М.ЛУОД) Я класса сг^и”.І1У0Д) супосчпуот дпсП'лпанинИ ому многогранник и, наоборот, для лкйого многогранника из класса [('[СП**. ЛУОД) в к лассо (Г^П.ЛУОД) суцоствуот двспст-роцііип ому многогранник, т.о. диопатввннна иногогрвнннки Н и М‘* дсспствэнкн относительно ЛУОД и 11У0Л. Такжо доказано, что класс (ГГН.ЛУОД) содоргиг псо многогранники с р гранями. Лямка ІЛ гтортгдоот, что 1-уголмтл пирамида яплттсн иороядпктдпм г:!!ог(!гряши!ко;! и отиоситолыга ЛОЛ, и огизситолыга ПОД.

Окаоивпотся , что лмЗоп многогранник класса .Л0Д> припаллэ-янт < в комбинаторном синсло ) классу гП^И,. .ОД) и, наоборот, явйеп пггагогранипк класса і("£М,.-0Л) принадлежит классу -ЛОЛ), котл

опралолонип ЛОД и ОД -различии, гда Нь -и-уголытя нирсшила. То?'о самса относится м к классам (Г^И^ПОД) и іП'М,. -СОД). Однако это кп означает, что лтаЗоп многогранник Ид относительно ЛОД <П0Д) и ОД (СОД) псроіЕдеіот один и тот жо класс. Іізпримор, колію у (Золится , что сктоэлр но поропдаот многогранника (рисЛ.) посролст’гом ЛОД, но тшогсграпиик М0 посредством ОД порождается от октаэдра.

, рис.2.

Возникает следуголип вопрос. Порождается ли посредством деформации два поршини <грани> произвольноп смежности при

а

C'jxpoiHJHiiii имаьнииги ослажнчх перини Сгр-знвп) от лкбоп бзішшін

- И

<i point) многогранннк-л М(Ч > ?. Прокдо чей отвотип. на этст вогір'-с д-плчм "прэп'золи'.он сио тост доух ворпчн при

го,‘ртисним <:*->«• остальных в«р«нп".

!!yi;ri, и -ШК1Є6СТОО номорои ві'вк оирізнь- <граней) смягивк г еоршниоп S.'j (и і р-лик» Г > піп; ограіінпга ИШ*) Для опродалаїшзсг;;;

<>улоп г: !птспь ,чго и мн'-^остпз М, здоичіпн упорядочен» так^ і|»в

л.і:)і ін»і>яшн Dj, и Dj <грани ГА и Г ) омшаник с Uj і! инцид'їтіик Оаіі'.-'П гріли <шршиіш) мно!-о!-ргч::іміс? Н<Н”) (іояярл і п J І>=лсиолjs-’jiw друг зэ другом Чзрчз Ilt її !<j о(Зоаііач!і;-с

u(i«і гчз?льныв иодмног/зо та киовоства <Г"адоо сос*. опт 6о;і»*5 чом ні’ їл-іного ?лэмунта), элак'.мпн которых упорядочены кеіс эяеизн'Ш І!

и lQ-1 Н"-ІІД . lijn и'^ . .

Ііусії, для лкігік подмяотсств І1Д >; П. м»ср>;ства 1^ посрсдотвгм

іюроєдайтся две ps-рпіши Ох и Вг (гропи Г( и Г, > or еергсисг И < грини Г, > мішгогроияч.сл М (И > при сохранении c,:0'.s;'!0GTi' осгаяышя ичрпим (гроноft j так , что П омежил о юргаин-іми Dx ,iell , В, скоаиа с Dt , itU С снзада г Г},

і€51* .ґ" СК-.’ХИД С rf, IgIIj >, is ISr. Тогдн о/до.м говорить, что от ьорв'ннк Dj, <гр.лни Г > порождаются лов вершили <грани) пржгаволышк;; спа знает/, ми при иохран'знг.и смежности ссталыш;'. □ориип чграноя).

Подоаитолысш отпет на ггастаЕлонкыл вопрос длл ОД и СОД даіог леммы І.С и 1.7, кагоры© е -чючактсл D олодукщом: '

І) осли егзпень Еораліки многогранника Только трок , то от ноя посредством ид порождаются доз вэрыины произзольнами с;-!огнсетями

при ‘’-'.'ф-ЭН<;НИИ СМЕЖНОСТИ ОСТАЛЬНЫХ ВврВИИ)

Г/ і граиг» многогранника tWTpwo^Han , Toot н«о неервлетшк

второго ТИПД. Оипегтннп ПОДХОД С1аЗИрУ*ЛСЯ !га рПССМОТр'ЖМИ классоп деформированный многогранников.

В параграфа 3 2 кристаллы боэдодьэктного алиаоя моде лиру тел многогранниками из класса г(УМ-Д0Л>, гдо Н-октаэдр. Бриллиант Ид Iгл сами разпнг 'Хоря бриллиантов , имзвялх специалънно {■ормн и тшускстегшх в пр;>пзБодстр|Э олг.азао^рааотки, мпдолнрутгел многогранником иэ класса (ПНЬОД), где) многогранник И соотгкггот-иу от эталону бриллианта №д

О параграфе 3.3 оиыснваетал комбинпторпо-гоомотричасжип метод оптимального роскрая кристалла (Эоэлвфоктного алмаза иод Сриллигдтн круглых и •ТпнгазиПимк -Тюрм кок ряешпанил общого подхода , описанного п параграфа 3.1.

Слодуот огмэтить , что прчдложоппип ивтод раскроя алмазов гэнодрон п практику.

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

РаОчт», опубликованные по таке диссертации.

I. Пулатоз Л.К. , Хуппоо Т.Х. О комбииаторноп структуре и моаностм классов линопно деформируемых многсгрмямксю//. Вероятностные методы и КисЗа риз тика -Казань С.42-Б5. •

2:. іг.'.;гз ІГ'.;; Л.ІС. ,Xy'C..?,VB Т./.. 00 ОКНОМ ПОДХОД" г решении ЗЗУ.ЭЧН о(і пц.!,5лмюго ропкроя. Pvk лчп п УЗНИ1ППИ - Т;.;іг^нг.

:і лг. -ю с.

j}. ІІЛ л . - л*.!' Т л М-п од раи-кроя и ирогнизирокеишя

■; і йрилли.:«нгл'.« и-? гнгі! я э ”,•■!=’?') нг ЭГ<М // Тозп?!) докли-ї:. \. V V’-<',\/j\4}WA\ 11Э У ’ І НО - ’1 >? ХМ! ІЧЧ СКР Й конференції!) по постоя-"і:;. її П'ф!,П‘Л<ті№ам р-лзмгшя ?злмкэдоОраОатHcwjwr'и произвол-і.і : і: УП-/.11І і!ятііл9тк-зх. См0Л‘Ліск.І959.-С.5«1-55.

У,і r--h .К., Косі”.'!' ОД.. Хлкидои КН.. Ху'мео IX- Об оп-

т!!г-! і 'її н< і.: р-’СКі-'С-'.' м!г>р'Гр;и!ііика сп^шплыкто ьид-л /V Теыисн /.мь/: Гіі -j j.c№no;i і'снгГ'';:''шлп; гл мл іг-мзтич^oi.omv о^чсііочонмі) •(ЯЧ'.т-'.'-.'Т'.но!'і> jja'-кроя ы систолах иитомоти .піиогашгсго про-ч-:-tiі; or,:!ili!ji. У-;--?. І[;07.-'ІЛ.-С.<;е