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ę su

jų elementų skerspjūvių parinkimu ir gali turėti daug sprendinių. Kaip yra

žinoma konstrukcijai parinkti skerspjūviai turi tenkinti tam tikras

sąlygas. Jos gali būti stipruminės, standumo, stabilumo, pusiausvyros ir

kt. Šios visos sąlygos yra aprašomos matematinėmis lygtimis arba

nelygybėmis, bendru atveju: [pic] [pic]

[pic] [pic].

Skaičių [pic] rinkinys tenkinantis šią sąlygų sistemą yra vadinamas

leistinuoju sprendiniu: [pic].

Konstrukcijų skaičiavimo uždavinyje apribojimų išreikštų lygybėmis

skaič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 šios

funkcijos atžvilgiu ir priklausomai nuo to koks ekstremumas keliamas

funkcijai [pic] galima gauti geriausią sprendinį šios funkcijos atžvilgiu,

todėl mūsų uždavinyje ši funkcija bus vadinama uždavinio optimalumo

kriterijumi. Todėl leistinasis taškas x, kuriam esant optimalumo kriterijus

[pic] įgyja ekstreminę reikšmę (max arba min) priklausomai nuo keliamo

tikslo, optimalus taškas bus laikomas optimaliu sprendiniu. Toks uždavinys,

kuriame tarp daugybės sprendinių reikia rasti geriausią ir vadinamas

optimizavimo uždaviniu.

Tiesiniame optimizacijos uuždavinyje visos funkcijos anksčiau aptartos

[pic] ir [pic] yra tiesinės. Todėl toks optimizacijos uždavinys ir

vadinamas tiesiniu optimizaciniu uždaviniu. Norint nustatyti optimalų

sprendinį taikant matematinio programavimo metodus reikia tiesinį

optimizavimo uždavinį aprašyti matematinėmis išraiškomis – matematiniu

modeliu. Matematinis modelis – tai sistema matematinių priklausomybių

aprašančių pagrindines mmodeliuojamo objekto savybes, rodiklius ir ryšius

tarp 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 apibendrinant

tiesinio 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ų x

komponentai.

[pic] – tiesinio uždavinio apribojimų sąlygų, (lygybių ir

nelygybių) koeficientų esančių prie nežinomųjų matrica. Šioje matricoje

stulpelių 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ų lenkimo

momentų 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 konstrukcijos

stiprumo sąlygos jos suirimo metu (plastiškos deformacijos galimos).

Ribiniai momentai turi tenkinti iš anksto užduotą jų optimalumo

kriterijų, kuris šiuo atveju yra tapatingas konstrukcijos energijos

disipacijos (energijos išsklaidymo) minimumui.

Tokio tipo uždavinių matematiniai modeliai sudaromi panaudojant

ekstreminį energinį principą apie energijos disipacijos minimumą, kuris

pateiktas knygoje ([1]).

Šis principas formuluojamas taip: iš visų statiškai leistinų lenkimo

momentų vektorių tikrasis yra tas, prie kurio energijos disipacijos greitis

yra minimalus.

Iš deformuojamo kūno mechanikos žinoma, kad energijos disipacijos

minimumas yra eekvivalentiš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 turintis

komponentus [pic].

[pic]

1pav. Konstrukcinė schema (n0=3)

Čia [pic] – optimizuojamų parametrų skaičius. Šiame uždavinyje

optimizuojamais 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, kurios

skaičiuojant konstrukcijas įvertinant plastiškumo deformacijos yra

vadinamos 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 laisvumo

laipsnis.

[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 modelis

panaudojant 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 19

nežinomųjų ir 45 apribojimus.

1 Konstrukcijos diskretinis modelis.

[pic]

2pav. Konstrukcijos diskretinis modelis ir galimi mazgų poslinkiai

2 OOptimizacijos uždavinio tikslo funkcija.

Pagal sudaryta matematinį modelį šio nagrinėjamo tiesinio optimizacijos

už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] |

|Išpjaunu mazgą 7-8: |Išpjaunu mazgą 9-10: |

|[pic] |[pic] |

|Išpjaunu mazgą 11-12-13: |Išpjaunu mazgą 15-16: |

|[pic] |[pic] |

Išpjaunu mazgus 2-3, 12-13:

[pic]

Išpjaunu mazgus 5,10:

[pic][pic]

Išpjaunu mazgą 7-8:

[pic]

Išpjaunu mazgą 7-8:

[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 momentai

turi būti neneigiami:

[pic]

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

Nagrinėjamam uždaviniui iš viso turėsime 10 apribojimus išreikštus

tiesinėmis lygtimis ir 35 apribojimus išreikštus nelygybėmis. Nežinomųjų

turėsime 19. Šio uždavinio sprendimui naudosime SIMPLEKSO algoritmą. Tam

tikslui sudaroma uždavinio simpleksų lentelė (1 lentelė). Simpleksų

lentelėje, stulpelių yra tiek kiek nežinomųjų plius laisvasis narys, o

eiluč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 konstrukcijos

lenkimo 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 kiekvienam

tiesinio 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 bus

ieš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 dualiame

uždavinyje keičiamas į naujos funkcijos maksimumą. Ir atvirkščiai.

2. Dualaus uždavinio tikslo

funkcija [pic] – Lagranžo funkcija. Šios

funkcijos kintamieji yra tiesioginio uždavinio kintamieji [pic]ir nauji

kintamieji [pic], kurių skaičius yra lygūs tiesioginio uždavinio apribojimų

lygybių ir apribojimų nelygybių sumai. Šie nauji kintamieji yra vadinami

Lagranžo daugikliais ir atstovauja atitinkamam apribojimui tiesioginiame

už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] ir

apribojimų lygybių, bei Lagranžo daugiklio [pic] ir apribojimų nelygybių.

4. LLagranžo daugikliai, kurie atstovauja apribojimams lygybėms yra

laisvi, 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 bendru

atveju, t.y. skaičiuojamos pirmosios išvestinės pagal tiesioginio uždavinio

visus kintamuosius [pic]. Jei kintamasis yra nelaisvas, tai Lagranžo

funkcijos variacija taip pat bus apribota pagal ženklą atitinkantį

suvaržyto kintamojo ženklą ir jei kintamasis yra laisvas, tai Lagranžo

funkcijos variacija pagal šį kintamąjį bus lygybė.

Mūsų nagrinėjamu atveju tiesioginiame uždavinyje turime 45 apribojimus,

taigi dualiame uuž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 tiesioginio

už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 momentus

galime projektuoti konstrukciją.

2 lentele:

[pic] Duomenų failo paruošimas ir dualaus uždavinio sprendimo rezultatai

pateikiami 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 žinomas

dydis, o [pic] randamas su „Simplex“ programa. Taigi [pic] optimali

skaitinė 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]

KVADRATINIO PROGRAMAVIMO OPTIMIZACIJOS UŽDAVINYS

1 Bendrasis kvadratinio optimizacijos uždavinio matematinis modelis

Tai toks optimizacijos uždavinys, kuriame tikslo funkcija yra išreikšta

kvadratine forma, o apribojimus sudaro tiesinės lygybės ir nelygybės. Tokio

tipo uždavinį skaičiuosim su programa “KVADPR”.

Rasti: [pic]

[pic] – kvadratinė forma;

[pic] – tiesinė forma.

Esant apribojimams:

[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]

4 Programos “KVADPR” skaičiavimo duomenys ir rezultatai

Duomenų failo ruošimas :

KP12 Sergej Sokolov

9 7 20

01050106020102020207030303080408

1. 1. 1. 1. 1. 1. 1. 2.94

04090501050205030602060307040705

3.94 -.323 .286 .286 -.286 -.286 -.323 -.323

07060707

.278 .278

01010201030204020503060307040804

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.2

05050606060707060707080808090908

12.4 14.4 -7.2 -7.2 14.4 269.72 254.42 254.42

0909

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ždavinio

rezultatai 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ždavinio

než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