Optimizacijos teorijos kursinis darbas

TIESINIO OPTIMIZACIJOS UŽDAVINIO SPRENDIMAS

1 Tiesinis optimizavimo uždavinys ir jo bendrasis matematinis modelis.

Inžineriniai uždaviniai konstrukcijų projektavime dažnai yra susiję sujų elementų skerspjūvių parinkimu ir gali turėti daug sprendinių. Kaip yražinoma konstrukcijai parinkti skerspjūviai turi tenkinti tam tikrassąlygas. Jos gali būti stipruminės, standumo, stabilumo, pusiausvyros irkt. Šios visos sąlygos yra aprašomos matematinėmis lygtimis arbanelygybėmis, bendru atveju: [pic] [pic] [pic] [pic]. Skaičių [pic] rinkinys tenkinantis šią sąlygų sistemą yra vadinamasleistinuoju sprendiniu: [pic]. Konstrukcijų skaičiavimo uždavinyje apribojimų išreikštų lygybėmisskaičius dažniausiai yra mažesnis už nežinomųjų skaičių, todėl leistinųsprendinių yra labai daug. Pasirinkus tam tikrą funkciją [pic] išreikštąper šiuos kintamuosius, galima leistinuosius sprendinius palyginti šiosfunkcijos atžvilgiu ir priklausomai nuo to koks ekstremumas keliamasfunkcijai [pic] galima gauti geriausią sprendinį šios funkcijos atžvilgiu,todėl mūsų uždavinyje ši funkcija bus vadinama uždavinio optimalumokriterijumi. Todėl leistinasis taškas x, kuriam esant optimalumo kriterijus[pic] įgyja ekstreminę reikšmę (max arba min) priklausomai nuo keliamotikslo, optimalus taškas bus laikomas optimaliu sprendiniu. Toks uždavinys,kuriame tarp daugybės sprendinių reikia rasti geriausią ir vadinamasoptimizavimo uždaviniu. Tiesiniame optimizacijos uždavinyje visos funkcijos anksčiau aptartos[pic] ir [pic] yra tiesinės. Todėl toks optimizacijos uždavinys irvadinamas tiesiniu optimizaciniu uždaviniu. Norint nustatyti optimalųsprendinį taikant matematinio programavimo metodus reikia tiesinįoptimizavimo uždavinį aprašyti matematinėmis išraiškomis – matematiniumodeliu. Matematinis modelis – tai sistema matematinių priklausomybiųaprašančių pagrindines modeliuojamo objekto savybes, rodiklius ir ryšiustarp jų. Į optimizacijos uždavinio matematinį modelį turi įeiti tiesinėfunkcija, išreiškianti tiesinį optimalumo sąlygos, apribojimai, kuriuos

turi tenkinti nagrinėjamo uždavinio sprendinys. Visa tai apibendrinanttiesinio optimizacijos uždavinio matematinį modelį galima pateikti taip: [pic]; (1) Čia [pic] – uždavinio nežinomųjų vektorius. [pic]- tikslo funkcijos koeficientų esančių prie nežinomųjų xkomponentai. [pic] – tiesinio uždavinio apribojimų sąlygų, (lygybių irnelygybių) koeficientų esančių prie nežinomųjų matrica. Šioje matricojestulpelių skaičius n, o eilučių skaičius lygus visų apribojimų skaičiui. [pic] – apribojimų sąlygų (lygybių ir nelygybių) laisvųjų nariųvektorius.

2 Konstrukcijos minimalaus tūrio optimizacijos matematinis modelis.

Yra duota lenkiama konstrukcija – rėmas. Yra žinoma veikianti išorinėapkrova ir žinomi skerspjūvių atlaikomųjų lenkimo momentų- ribinių lenkimomomentų pasiskirstymo dėsnis (bet ne dydžiai). Reikia rasti tokius ribinių momentų dydžius ir konstrukcijos elementųįrąžas, kad būtų atlaikyta išorinė apkrova ir nepažeistos konstrukcijosstiprumo sąlygos jos suirimo metu (plastiškos deformacijos galimos). Ribiniai momentai turi tenkinti iš anksto užduotą jų optimalumokriterijų, kuris šiuo atveju yra tapatingas konstrukcijos energijosdisipacijos (energijos išsklaidymo) minimumui. Tokio tipo uždavinių matematiniai modeliai sudaromi panaudojantekstreminį energinį principą apie energijos disipacijos minimumą, kurispateiktas knygoje ([1]). Šis principas formuluojamas taip: iš visų statiškai leistinų lenkimomomentų vektorių tikrasis yra tas, prie kurio energijos disipacijos greitisyra minimalus. Iš deformuojamo kūno mechanikos žinoma, kad energijos disipacijosminimumas yra ekvivalentiškas konstrukcijos minimalaus tūrio reikalavimui([1]). Ši energija lenkiamam rėmui yra išreiškiama taip:[pic]; (2) Čia [pic] – rėmo optimizuojamų parametrų vektorius turintiskomponentus [pic]. [pic] 1pav. Konstrukcinė schema (n0=3) Čia [pic] – optimizuojamų parametrų skaičius. Šiame uždavinyjeoptimizuojamais parametrais pasirenkame rėmo strypų atlaikomus momentus. [pic] -strypų turinčių tą patį ribinį momentą, suminių ilgiųvektorius. [pic]. Šiame nagrinėjamame uždavinyje: [pic]; Statiškai leistinas momentų vektorius, kaip mes žinome iš konstrukcijų

projektavimo turi tenkinti pusiausvyros sąlygas ir stiprumo sąlygos, kuriosskaičiuojant konstrukcijas įvertinant plastiškumo deformacijos yravadinamos takumo sąlygomis. Pusiausvyros sąlygos yra užrašomos matricine išraiška: [pic] (3) [pic] (4) Čia [pic] – pusiausvyros lygčių koeficientų prie nežinomųjų matrica.

m – pasirinkto konstrukcijos diskrecinio modelio laisvumolaipsnis. [pic] – duotas išorinių jėgų vektorius. [pic] – stiprumo sąlygų koeficientų matrica. t – bendras stiprumo sąlygų skaičius. [pic] – konfigūracijos matrica. [pic] – nežinomų lenkimo momentų vektorius. [pic]. Tokiu būdu konstrukcijos minimalaus tūrio matematinis modelispanaudojant aprašytą energijos principą bus: [pic] (5) Palyginus (1) su (5) matome, kad jos yra ekvivalentiškos. Tuo atveju: [pic]Turėsime 19 nežinomųjų x. Bendras nežinomųjų skaičius [pic]. [pic] Dalis kintamųjų netinka [pic]. Šiuo atveju: [pic], arba [pic]. Taigi [pic]. Įvertinus konstrukcinius apribojimus galutinai uždavinys turės 19nežinomųjų ir 45 apribojimus.

1 Konstrukcijos diskretinis modelis.

[pic] 2pav. Konstrukcijos diskretinis modelis ir galimi mazgų poslinkiai

2 Optimizacijos uždavinio tikslo funkcija.

Pagal sudaryta matematinį modelį šio nagrinėjamo tiesinio optimizacijosuždavinio tikslo funkcija bus: [pic] Tikslo funkciją sudaro: [pic]; [pic].

3 Optimizacijos uždavinio apribojimų sąlygos.

Sudarydami apribojimų sąlygas naudosime mazgų išpjovimo metodą.Išpjautam mazgui surašę statikos pusiausvyros lygtis gausime apribojimųsąlygas. Apribojimų numeris nurodomas skliaustuose.

|Išpjaunu mazgą 2-3-4: |Išpjaunu mazgą 5-6: ||[pic] |[pic] ||[pic] |[pic] ||Išpjaunu mazgą 7-8: |Išpjaunu mazgą 9-10: ||[pic] |[pic] ||[pic] |[pic] ||Išpjaunu mazgą 11-12-13: |Išpjaunu mazgą 15-16: ||[pic] |[pic] ||[pic] |[pic] |

Išpjaunu mazgus 2-3, 12-13: [pic][pic] Išpjaunu mazgus 5,10:[pic][pic]Išpjaunu mazgą 7-8:[pic][pic]Išpjaunu mazgą 7-8:[pic][pic]

Apribojimų sąlygose lygybėse esančių nežinomųjų koeficientai surašomi įapribojimų lygybių koeficientų matricą [pic].[pic] Apribojimų sąlygose lygybėse esantys laisvieji nariai surašomi į

apribojimų lygybių laisvųjų narių vektorių [pic][pic]. Nagrinėjamame optimizacijos uždavinyje sekančią grupę apribojimų,išreikštų nelygybėmis, sąlygas sudarys konstrukcijos stiprumo sąlygos. Bet kuriame konstrukcijos pjūvyje stiprumo sąlygos: [pic] ; [pic]. Užrašome stiprumo sąlygas kiekvienam konstrukcijos pjūviui: M01+M1≥0, (11) M03+M9≥0, (27) M01-M1≥0, (12) M03-M9≥0, (28) M01+M2≥0, (13) M01+M10≥0, (29) M01-M2≥0, (14) M01-M10≥0, (30) M01+M3≥0, (15) M02+M11≥0, (31) M01-M3≥0, (16) M02-M11≥0, (32) M02+M4≥0, (17) M01+M12≥0, (33) M02-M4≥0, (18) M01-M12≥0, (34) M01+M5≥0, (19) M01+M13≥0, (35) M01-M5≥0, (20) M01-M13≥0, (36) M03+M6≥0, (21) M01+M14≥0, (37) M03-M6≥0, (22) M01-M14≥0, (38) M03+M7≥0, (23) M02+M15≥0, (39) M03-M7≥0, (24) M02-M15≥0, (40) M03+M8≥0, (25) M02+M16≥0, (41) M03-M8≥0, (26) M02-M16≥0, (42)Koeficientus, esančius prie nežinomųjų apribojimuose nelygybėse surašome įapribojimų nelygybių koeficientų matricas[pic] ir [pic].Kaip papildomus apribojimus užrašome sąlygas, ieškomi ribiniai momentaituri būti neneigiami: [pic]

3 Optimizacijos uždavinio Simpleksų lentelės sudarymas.

Nagrinėjamam uždaviniui iš viso turėsime 10 apribojimus išreikštustiesinėmis lygtimis ir 35 apribojimus išreikštus nelygybėmis. Nežinomųjųturėsime 19. Šio uždavinio sprendimui naudosime SIMPLEKSO algoritmą. Tamtikslui sudaroma uždavinio simpleksų lentelė (1 lentelė). Simpleksųlentelėje, stulpelių yra tiek kiek nežinomųjų plius laisvasis narys, oeilučių tiek kiek apribojimų plius tikslo funkcija.Optimizacijos uždavinio Simpleksų lentelė (1lent.):

Norint patikrinti ar gauti rezultatai tenkina visas uždavinio sąlygas,t.y. visas lygybes ir nelygybes, sudarome nagrinėjamos konstrukcijoslenkimo momentų diagramą. [pic] 3pav. Konstrukciją veikiančių lenkimo momentų ir ribinių momentų diagrama

4 DUALUS OPTIMIZACIJOS UŽDAVINYS

1 Dualus optimizacijos uždavinio sudarymo taisyklės

Tiesinio matematinio programavimo teorijoje pasakyta, kad kiekvienamtiesinio optimizavimo uždaviniui galima sudaryti jam dualų uždavinį. Jeigu turime pradinį optimizacijos uždavinį: [pic] Visada egzistuoja jam dualus uždavinys, kuriame tikslo funkcijoje

turime taip pat tam tikrą tiesinę funkciją. Tik tokios funkcijos busieškomas maksimumas, o apribojimų sąlygos bus lygybės. Duotajam tiesioginiam uždaviniui dualus uždavinys atrodys taip: [pic] Čia [pic]- dualaus uždavinio nežinomieji. Jame yra tiek nežinomųjų,kiek yra apribojimų tiesioginiame uždavinyje. Dualaus uždavinio sudarymo taisyklės: 1. Tiesioginio uždavinio tikslo funkcijos minimumas dualiameuždavinyje keičiamas į naujos funkcijos maksimumą. Ir atvirkščiai. 2. Dualaus uždavinio tikslo funkcija [pic] – Lagranžo funkcija. Šiosfunkcijos kintamieji yra tiesioginio uždavinio kintamieji [pic]ir naujikintamieji [pic], kurių skaičius yra lygūs tiesioginio uždavinio apribojimųlygybių ir apribojimų nelygybių sumai. Šie nauji kintamieji yra vadinamiLagranžo daugikliais ir atstovauja atitinkamam apribojimui tiesioginiameuždavinyje. Lagranžo daugikliai, kurie atstovauja apribojimams lygybėms yražymimi – [pic], o kurie atstovauja apribojimams nelygybėms – [pic]. 3. Lagranžo funkcija yra lygi tiesioginio uždavinio tikslo funkcijai ,prie kurios pridedamos sandaugos sudarytos iš Lagranžo daugiklio [pic] irapribojimų lygybių, bei Lagranžo daugiklio [pic] ir apribojimų nelygybių. 4. Lagranžo daugikliai, kurie atstovauja apribojimams lygybėms yralaisvi, t.y. gali būti bet kokios skaitinės reikšmės. Lagranžo daugikliai,kurie atstovauja apribojimams nelygybėms yra nelaisvi, t.y. gali būti tik[pic]. 5. Apribojimai sudaromi atliekant Lagranžo funkcijos variacijas bendruatveju, t.y. skaičiuojamos pirmosios išvestinės pagal tiesioginio uždaviniovisus kintamuosius [pic]. Jei kintamasis yra nelaisvas, tai Lagranžofunkcijos variacija taip pat bus apribota pagal ženklą atitinkantįsuvaržyto kintamojo ženklą ir jei kintamasis yra laisvas, tai Lagranžofunkcijos variacija pagal šį kintamąjį bus lygybė. Mūsų nagrinėjamu atveju tiesioginiame uždavinyje turime 45 apribojimus,taigi dualiame uždavinyje bus 45 nežinomieji. [pic]

2 Nagrinėjamo dualaus uždavinio matematinis modelis

Sudaromas tiesinio, dualaus uždavinio matematinis modelis:

RASTI:[pic] kai: [pic] (1) [pic] (2) [pic] (3) [pic] (4) [pic] (5) [pic] (6) [pic] (7) [pic] (8) [pic] (9) [pic] (10) [pic] (11) [pic] (12) [pic] (13) [pic] (14) [pic] (15) [pic] (16) [pic] (17) [pic] (18) [pic] (19) [pic](20) [pic](38) [pic](21) [pic](39) [pic](22) [pic](40) [pic](23) [pic](41) [pic](24) [pic](42) [pic](25) [pic] (43) [pic](26) [pic] (44) [pic](27) [pic] (45) [pic](28) [pic] (46) [pic](29) [pic] (47) [pic](30) [pic] (48) [pic](31) [pic] (49) [pic](32) [pic] (50) [pic](33) [pic] (51) [pic](34) [pic](52) [pic](35) [pic](53) [pic](36) [pic](54) [pic](37)

3 Dualaus optimizacijos uždavinio Simpleksų lentelė

Gauta tiesinė funkcija ir apribojimų sąlygos surašomos į Simpleksųlentelę (2 lentelė).

5 Uždavinių sprendimo analizė

Turėdami tiesinio ir dualaus uždavinių rezultatus, atlikus sprendiniųanalizę, galime padaryti išvadą apie vienintelio sprendinio egzistavimą,jei: 1. Dualaus uždavinio daugikliai ([pic]) atstovaujami tiesioginiouždavinio apribojimams nelygybėms yra didesni už nulį ir neneigiami. 2. Gautas sprendinys bus tikrasis, jeigu uždavinio apribojimų lygybių ME skaičius + y>0=[pic]: [pic] 16+3=10+9; čia [pic]- momentų skaičius; [pic]- analizuojami parametrai. Matome, kad lygybė yra tenkinama, tai toliau pagal gautus momentusgalime projektuoti konstrukciją. 2 lentele:[pic] Duomenų failo paruošimas ir dualaus uždavinio sprendimo rezultataipateikiami 2 priede.

6 Strypų skerspjūvių parinkimas panaudojant gautas ribines įrąžų reikšmes, ir konstrukcijos minimalaus tūrio radimas.

Mūsų nagrinėjama konstrukcija yra plieninė, tai [pic] yra žinomasdydis, o [pic] randamas su „Simplex“ programa. Taigi [pic] optimaliskaitinė vertė yra: [pic]Parenku plina C255 ,[pic]Pagal gautą [pic] reikšmę iš sortimento parenku dvitėjus profilius: 1) M0,1 = 10.5 kNm, [pic]Parenku pagal euronormas dvitėjinę siją IPEA120, kurios Wpl = 49.87 cm3,skerspjūvio plotas A1 = 5.41 cm2; 2) M0,2 = 21.0 kNm. [pic]Parenku pagal euronormas dvitėjinę siją IPE140, kurios Wpl = 88.34 cm3,skerspjūvio plotas A2= 7.64 cm2; 3) M0,3 = 33.3 kNm. [pic]Parenku pagal euronormas dvitėjinę siją IPE180, kurios Wpl = 166.4 cm3,skerspjūvio plotas A2= 11.25 cm2.Parinktų konstrukcijų minimalūs tūriai (skerspjūvio plotą A dauginu iškonstrukcijos ilgio l):[pic];[pic][pic]

KVADRATINIO PROGRAMAVIMO OPTIMIZACIJOS UŽDAVINYS

1 Bendrasis kvadratinio optimizacijos uždavinio matematinis modelis

Tai toks optimizacijos uždavinys, kuriame tikslo funkcija yra išreikštakvadratine forma, o apribojimus sudaro tiesinės lygybės ir nelygybės. Tokiotipo uždavinį skaičiuosim su programa “KVADPR”. Rasti: [pic] [pic] – kvadratinė forma; [pic] – tiesinė forma. Esant apribojimams: [pic] [pic] čia: [pic] – nežinomųjų vektorius; [pic] – Hesės matrica, [pic] [pic] [pic] – tiesinės formos koeficientų vektorius; [pic] – apribojimų-lygybių koeficientų matrica, [pic] – apribojimų- lygybių skaičius, [pic] – nežinomųjų skaičius; [pic] – apribojimų-lygybių laisvųjų narių vektorius; [pic] – apribojimų-nelygybių koeficientų matrica, [pic] – apribojimų-nelygybių skaičius, [pic] – nežinomųjų skaičius; [pic] – apribojimų-nelygybių laisvųjų narių vektorius.

2 Kvadratinio programavimo optimizacijos uždavinio sudarymas

Rasti[pic] [pic] [pic] [pic]

3 Optimizacijos uždavinio tikslo funkcijos tyrimas

Sudarykime nelygybių koeficientų matricą [pic]: [pic] [pic]

Suveskime likusiąją lygybių koeficientų matricą [pic]:[pic][pic]

Sudarykime tikslo funkcijos hesės matricą:

[pic]

[pic]

4 Programos “KVADPR” skaičiavimo duomenys ir rezultatai

Duomenų failo ruošimas :KP12 Sergej Sokolov 9 7 2001050106020102020207030303080408 1. 1. 1. 1. 1. 1. 1. 2.9404090501050205030602060307040705 3.94 -.323 .286 .286 -.286 -.286 -.323 -.32307060707 .278 .27801010201030204020503060307040804 1. -1. 1. -1. 1. -1. 1. -1.09080909100810091105120513061406 2.94 2.94 -2.94 -2.94 1. -1. 1. -1.150716071708180819092009 1. -1. 1. -1. 1. -1.01010202020303020303040404050504 24.8 35. -17.5 -17.5 35. 12.4 -6.2 -6.205050606060707060707080808090908 12.4 14.4 -7.2 -7.2 14.4 269.72 254.42 254.420909 269.72 . .65 . -32.5 .325 .65 5.2 5. 5. 4. 4. 4. 4. 10. 10. -25.5 39.5 10. 10. 10. 10. 10. 10. 7. 7. 7. 7. -74.9 -121.2 81.4 -17.3 -26.4 5.8 69.8 -2161.45 -2266.35 Kvadratinio optimizacijos uždaviniorezultatai pateikiami 3 priede.

5 Gautų skaičiavimo rezultatų analizė

Uždavinio apribojimų- lygybių sąlygos:[pic]Sąlygos tenkinamos.

Uždavinio apribojimų- nelygybių sąlygos: [pic] [pic] Su šiais, kvadratinio programavimo optimizacijos uždavinionežinomaisiais, funkcijos reikšmė:[pic]Kvadratinės formos funkcijos reikšmė:[pic]

Naudota literatūra:

1. R. Karkauskas. „Statybinės mechanikos uždavinių sprendimas kompiuteriais“.  Vilnius : Mokslo ir enciklopedijų leidykla, 1995.

2. St. Kalanta. „Taikomosios optimizacijos pagrindai. Tiesinių uždavinių formulavimas ir sprendimo metodai“.  Vilnius : Technika, 2003.———————–

2 pav. Matria A