Operacijų tyrimas

1, Operacijų tyrimo esmė Operacijų tyrimo esmę sudaro šie pagrindiniai bruožai: Pirma, uždaviniuose visada nagrinėjamos oragnizacinės sistemos, kurias sudaro tikslingai veikiantys žmonės, naudojantys įvairias technines priemones, konkrečiam tikslui pasiekti. Paprastai tyrinėjami “mikro”, o ne “makro” lygio organizacinių sistemų problemos. Antra, uždaviniai visada orientuoti į sprendimo priėmimo procesą. Tikslas – ne tik smulkiai ištirti nagrinėjamą organizacinę sistemą, bet ir paruošti mokslines rekomendacijas racionaliam sprendimui priimti. Operacijų tyrimo metodais nustatoma geriausiai atitinkanti įmonės tikslus jos padalinių, įrengimų bei jų kompleksų funkcionavimo tvarka, reguliuojamos gamybos proporcijos, produkcijos asortimento keitimo kryptys ir pan. “Operacija” veiksmų visuma, kuri būtina pasiūlytam sprendimui įgyvendinti. Trečia, o.t. uždavinių sprendimas remiasi nagrinėjamos sistemos modelių, dažniausiai matematinių, sudarymu ir sprendimu. O.t. tik paruošia rekomendacijas, bet galutinį sprendimą priima ir už jį atsako žmonės. O.t. uždavinio sprendimas visada remiasi simetriškumo principu. O.t. dėmesio centre – konkretus praktinių problemų sprendimas. 2. Operacijų tyrimo uždavinių klasės ir sprendimo etapai. Uždavinių klasės: 1.Paskirstymo uždavinai. Tikslas – racionaliai paskirstyti ribotus išteklius įvairiems darbams atlikti. Jei žinomi ištekliai, sprendžiama, kuriuos darbus atlikti naudingiausia; jei žinomi darbai, sprendžiama, kaip juos geriausia aprūpinti ištekliais; jei žinomi ir darbai, ir ištekliai, spredžiama, kaip geriausia paskirstyti išteklius darbams. Šie uždaviniai gali būti naudojami optimaliam gamybos planui sudaryti, spręsti aprūpinimo uždavinius, optimizuoti transporto priemononių, įrengimų paskirstymą darbams. 2.Masinio aptarnavimo uždaviniai. Jais modeliuojamos situacijos, kuriose tam tikri pastoviai atsirandantys darbai turi būti apdorojami keliais aptarnavimo kanalais. Sprendžiama, kaip organizuoti aptarnavimą, kad nuostoliai dėl eilių susidarymo ir kanalų pratovų būtų minimalūs. 3.Pakeitimo ir remonto uždaviniai. Nagrinėjami įrengimai, kurių funkcionavimas laikui bėgant blogėja arba patikimumas mažėja. Sprendžiama, koks optimalus šių įrengimų pakeitimo arba profilaktinių remontų laikas, kad išlaidos pakeitimams ar remontams ir nuostoliai dėl avarinių prastovų būtų minimalūs. 4.Atsargų valdymo uždaviniai. Nagrinėjamas optimalios atsargų apimties nustatymas įvairiuose ūkinės veiklos baruose. Naudojant įvairius modelius sprendžiama, kiek turėti atsargų, kada jas užsakyti ir pan. 5.Sutvarkymo ir tvarkaraščių teorijos uždaviniai. Tikslas – nustatyti optimalią tam tikrų darbų atlikimo tvarką, kad visi darbai būtų atlikti kuo greičiau (pigiau, kokybiškiau). 6.Maršruto sudarymo ir tinklinio planavimo uždaviniai. Tikslas – susieti kelis punktus trumpiausia arba pigiausia ryšių linija, suplanuoti transporto srautus, nutiesti komunikacijas. Gali būti sprendžiami trumpiausio kelio tarp kurių nors punktų suradimo, maksimalaus produktų srauto, kurį galima perduoti iš vieno punkto į kitą nustatymo, naujų įmonių išdėstymo vietos nustatymo uždaviniai. 7.Paieškos uždaviniai. Tikslas – taip organizuoti paiešką, kad tikimybė surasti ieškomą objektą būtų didžiausią, turint ribotus lauko, darbo, įrengimų išteklius. 8.Konfliktinių situacijų uždaviniai. Jie sprendžiami, kai reikia priimti sprendimą interesų nesutapimo sąlygomis. Nagrinėjami kooperavimo, koalicijų sudarymo ir pan. uždaviniai. Sprendimo etapai: 1.Problemos formulavimas. Pirmiausia reikia išsiaiškinti materialinius, finansinius, juridinius, psicholognius ir visus kitus nagrinėjamos situacijos aspektus. Išsiaiškinus situaciją sprendžiama problema padalinama į dalinius uždavinius. Atsižvelgiama, ar yra visi reikalingi duomenys. Nusprendžiama, kaip detaliai nagrinėsime problemą, kiek ir kokių valdomų ir nevaldomų kintamųjų, technologinių parametrų reikia turėti. Gerai išnagrinėjamas tyrimo tikslas, jis konkretinamas. 2.Modelio sudarymas. Remiantis problemos formulvimo etapo rezultatais nusprendžiama, koks bus modelio tipas. Statiniai modeliai tinka modeliuojant vienąkart, dinaminiai – daug kartų priimamus sprendimus; determinuoti modeliai pretenduoja į tikslią nežinomųjų ryšių išraišką, stochastiniai – atsižvelgia į atsitiktinumus; optimizaciniai skirsti surasti geriausią sprendimą, imitaciniai – leidžia nagrinėti įvairius sprendimo variantus ir t.t. Parinkus modelio tipą, formalizuojami modelio nežinomieji. Jei problema buvo suskaidyta į kelias, gali būti sudaromi keli modeliai. Modelio nežinomųjų priklausomybės gali išreikšti iš apibrėžimų išplaukiančius ryšius ir technologinius bei kitus situacijos parametrus. Sudarant modelį, reali ekonominė situacija supaprastinama, daromos prielaidos, kurios padeda lengviau nagrinėti problemą. 3.Sprendimas. Pirmiausia išsiaiškinami sprendimo metodai. Suradus juos reikia pateikti aiškių algoritmų pavidalu ir sudaryti atitinkamą ESM programą. Šiame etape turi būti surinkti visi reikalingi duomenys, statistikos metodais įvertintos priklausomybės ir pan. 4.Modelio tyrimas. Tiriama, ar modelis gerai atvaizduoja nagrinėjamą situaciją. Tikrinama modelio reakcija į įvairių parametrų, duomenų pakeitimus, “kraštutines” parametrų reikšmes. Tikrinama, ar modelis pakankamai gerai imituoja jau žinomus, praktikoje stebimus reiškinius, ar modelio elgesys neprieštarauja žinomiems faktams. Tikrinamas modelio jautrumas parametrų pakeitimui. 5.Įdiegimas. Rekomendacijos pateikiamos įmonės vadovams ir, jiems pritarus, pradedamos įgyvendinti. Kadangi klaidos ir nesklandumai neišvengiami, projektą paruošusi grupė turi stebėti, kaip jis įgyvendinamas ir funkcionuoja. 3. Gamybos planavimo uždavinys ir jo taikymai. Nagrinėsime įmonę, kuri gali gaminti n skirtingų produktų tipų, naudodama m išteklių rūšių. m išteklių apimtys nagrinėjamam periodui – b1,b2,...bm. reikšmė parodo, kiek i-tojo ištekliaus vienetų reikia j-tojo produkto vienetui pagaminti. Sąnaudos kiekvieno produkto gamybai tiesiog proporcingos jo gamybos apimčiai. cj parodo, kiek j-tojo produkto vienetas atneša pelno. xn – kiek n-tojo produkto vienetų planuojama gaminti. Sudarome leistiną planą: be to, 4. Dietos arba mišinių uždavinys Sakykim galime pirkti n maisto prod. rūšių, o jose yra m maistingųjų medžiagų. Organizmui per para reikia b1, b2, …, bm vienetų. Žymėsime aji i-tosios maistingosios medžiagos kiekį j-tojo maisto produkto vienetu; j-tojo prdukto vienetas kainuoja cj. Reikia kuo pigiau nupirkti tokį maisto produktų rinkinį, kad būtų ptenkintas poreikis maisto medžiagom. Taigi (x1, x2, …, xn) – maisto produktų pirkimo planas. Pirmame produkte jos turime a11x1 vienetų, antrajame a21x2. Taigi iš viso turime a11x1+a21x2+…+an1xn vienetų. Ši suma negali būti mažesnė už pirmos maisto medžiagos poreikį b1.Tai: a11x1+a21x2+…+an1xn b1 a12x1+a22x2+…+an2xn b2 …………………………. a1mx1+a2mx2+…+anmxn bm x10; x20; …; xn0; Pirkimo planas leistinas jei patenkinti apribojimai. Reikia rasti mažiausią: c1x1+c2x2+…+cnxn (min). Visas šis uždavinys vadinamas dietos arba kartais mišinių uždaviniu. 5. Geometrinis tiesinio programavimo uždavinių interpretavimas ir sprendimas. Geometriškai interpretuojame tiesinio programavimo uždavinius su dviem kintamaisiais. c1x1 + c1x2 (max) (i = 1,2, … , m) Plokštumoje atvaizduosim taškus, kurių koordinatės x1 ir x2 tenkina uždavinio apribojimus. Brėžiame tiesę Aibė taškų (x1, x2), kurių koordinatės tenkina nelygybę priklausys vienaj plokštumos, perkirstos šia tiese pusei. Patikrinam, ar taškas (0,0) yra ieškomoje plokštumos pusėje. , vadinasi šioje tiesės pusėje yra šį apribojimą tenkinanti taškų aibė. Atžymime brūkšniukais šią pusplokštumę ir kitus apribojimus atitinkančias pusplokštumes (įtraukiam ir apribojimus). Kadangi ieškomi taškai turi tenkinti visus apribojimus, jie priklauso pusplokštumių sankirtai ir sudaro daugiakampį. Kiekvienas jo taškas yra leistinas kandidatas į optimalius. Tikslo f-jos c1x1 + c1x2 = φ grafikas yra plokštuma trimatėje koordinačių sistemoje (x1, x2, φ), todėl brėžinyje vaizduojame tik jos lygio linijas, t.y. linijas, kurios jungia tuos plokštumos taškus, kuriuose f-jos reikšmė ta pati. (0cfj (f-fityvaus tiekėjo nr.), tai j-asis gavėjas patiria mažesnius nuostolius dėl negauto produkto vnt., negu i-asis. Vadinasi, pastarojo poreikiai bus patenkinti geriau. Uždaviniai su privalomais vežimais: jei norime kažkuriam gavėjui nuvežti daugiau nei tam tikras kiekis produkcijos, t.y. . Tada iš k-ojo tiekėjo atsargų atimame d ir laikome jo atsargas lygiomis ak-d vienetų; l-ojo gavėjo poreikį sumažiname iki bl-d, prie gautos optimalios reikšmės po sprendimo reikia pridėti dydį d. Uždaviniai su ribotais pervežimais: jei , tada vietoj vieno l-ojo gavėjo nagrinėjame du: l1 ir l2. Gavėjo l1 poreikį nustatome d vnt., o l2 poreikį – bl-d vnt. Pervežimų kainos cil1 ir cil2 sutampa su cil išskyrus ckl2, kuri priskiriama labai didelė, taigi srautas xkl apribojamas. Išsprendus uždavinį reikia sudėti xil1+xil2. 18. Išdėstymo uždavinys ir jo ryšys su transporto uždaviniu. Yra m miestų (punktų), kuriuose galime išdėstyti gamyklas, gaminančias produktą. a1, a2, ... am – gaminame produkto; b1, b2, ... bm –miestų poreikiai tam produktui; cij – produkto gabenimo iš i miesto į j miestą išlaidos. Gali būti, kad pajėgumai mažesni negu miesto poreikiai arba gerokai didesni už poreikius. Kokiuose miestuose, kokio pajėgummo gamyklas statyti, kad būtų patenkinti visų miestų poreikiai ir produkto gabenimo išlaidos būtų minimalios? xij – produkto pervežimo iš i-ojo miesto į j-ąjį miestą apimtis. Išdėstymo uždavinio modelis: (1) ; (2) - iš i-tojo miesto išvežti galima ne daugiau nei jame pagaminam.; (3) - į j-tojo miestą reikia atvežti ne mažiau nei to miesto poreikis; (4). - optimalūs pervežimo srautai; - i-ajam mieste statom įmonę tokio galingumo, kad užtektų išvežti į visus miestus. Jeigu , t.y. potencialios gamybos galimybės mažesnės už poreikį, uždavinio išspręsti negalima. Laikykim, kad , t.y. potencialios galimybės didesnės už poreikį. Jeigu , spręstumėme paprastą transporto uždavinį. , įsivedam fiktyvų miestą m+1. m+1 poreikis ; Visi pervežimai iš i į m+1 nekainuoja, nes nieko nepervežame: . Tada uždavinys tampa subalansuotu, (2) ir (3) iš nelygybių tampa lygybėmis ir gauname paprastą transporto uždavinį. 19. Atsargų valdymo uždavinys kaip transporto uždavinys Įmonė planuoja darb m dienų į priekį. Per šias dienas ji gali pagaminti a1, a2,...,an tam tikro produkto vienetų. Vartotojams pateikti per šias dienas būtina b1, b2,...,bm šio produkto vienetų. Visas vartotojų poreikis gali būti patenkintas: . Tačiau kai kurios dienos poilsio, be to, yra dienų, kada produkto reikia labai daug, ir įmonei geriau turėti jo atsargas. Reikia sudaryti optimalų gamybos planą. gi – produkto vieneto gamybos i-tąją dieną kaina, s – produkto sandėliavimo vienos dienos kaina. m+1 – fiktyvi diena, t.y. kai gamybinių pajėgumų perviršis. xij –„ transportuojamas“ kiekis iš gamybos į vartojimą. si*(j-i) (;) - sandėliavimo nuo i-tosios iki j-tosios dienos išlaidos. Laikysime, kad , nes galima gaminti tik atsargas. - gamybos pajėgumų perteklius. Uždavinį galime užrašyti taip: ; ; ; ; ; - tikslo funkcija. Toliau sprendžiame kaip transporto uždavinį. 20. Tiesiniai sveikaskaitiniai ir diskretūs uždaviniai. Karpymo uždavinys. Matematinio programavimo uždavinys, kurio visi arba dalis nežinomųjų įgyja reikšmes tik iš baigtinės ar suskaičiuojamos reikšmių aibės, vadinamas diskrečiojo programavimo uždaviniu. Sveikaskaitinio programavimo uždavinyje nežinomasis gali įgyti tik sveikas reikšmes. Diskrečiojo programavimo uždaviniai skirstomi: 1. Transporto tipo. Šiuose uždaviniuose tarp optimalių planų visada yra ir sveikaskaitinių, kurie gali būti surasti įprastais tiesionio programavimo metodais. 2. Uždaviniai, kuriuose planuojami nedalūs objetai. Optimalus ir optimalus sveikaskaitinis planai šiuose uždaviniuose dažnai nesutampa. 3. Kombinatoriniai. Juose su kiekvienu tam tikros grupės objektų pertvarkiu siejama apibrėžta nauda ar nuostoliai. Reikia rasti geriausią iš pertvarkių. 4. Uždaviniai su neiškiliomis arba nesusijusiomis leistinų planų aibėmis ir uždaviniai su netolydžiomis tikslo funkcijomis. Šių uždavinių pradiniame formulavime sveikaskaitinių nežinomųjų gali ir nebūti, bet jie atsiranda performuluojant uždavinius ir juos sprendžiant. „Karpymo uždavinys“ – uždavinio su komplektų skaičiaus planavimu pavyzdys. Turime b lapų medžaiagos. Kiekvieną lapą galime karpyti vienu iš n būdų. Karpydami lapus gauname skirtingas detales, kurių iš viso yra m skirtingų tipų. Iš detalių sudaromi komplektai. Į komplektą įeina ki i-ojo tipo detalių, tad vieno komplekto sudėtį nurodo vektorius . Kaip sukarpyti lapus, kad gautume kuo daugiau komplektų? xj – j-uoju būdu karpomų lapų skaičius, z – planuojamas komplektų skaičius. , - kiek i-ųjų detalių sukarpoma j-uoju būdu. Pirmuoju būdu karpomi lapai duos i-ojo tipo detalių, antruoju - ir t.t. i-ojo tipo detalių turėsime . Karpymo uždavinį galime užrašyti: (max)z; ; x1+x2+….+xn ≤ b; . Gavome tiesinio programavimo uždavinį, bet su papildoma sąlyga – visi nežinomieji gali įgyti tik sveikaskaitines reikšmes. 21. Kuprinės(vienmatis ir daugiamatis), paskyrimų, komivojažieriaus uždaviniai. Kuprinės uždavinys. Kuprinės uždavinys. Turime b kvadratinių metrų talpos kurpinę, į kurią galime sudėti kai kuriuos iš n daiktų. Kiekvienas idėtas daiktas užima kuprinėje tam tikrą tūrį aj (j=1,n) m3 ir duoda naudą cj (j=1,n). Kuriuos daiktus dėti į kuprinę, kad nauda būtų maksimali? xj (j=1,n) – parodo, ar j-tasis daiktas dedamas į kuprinę (xj=0), ar ne (xj=1). Tada j-tojo daikto užimamas tūris bus ajxj. Visų daiktų užimamas tūris: . Uždavinio pavidalas: Galim turėti apribojimus pagl tūrį ir svorį. d – kuprinės svoris dj - j-ojo daikto svoris. Uždavinio pavidalas: Kuprinės uždavinys gali būti papildomas įvairiomis sąlygomis, pvz. kad įdėjus i-tąjį daiktą būtina įdėti ir j-tąjį, arba keliami ir svorio, įkrovimo trukmės ir kiti apribojimai. Tada vietoj apribojimo atsiranda visa apribojimų matrica . Paskyrimų uždavinys. Turime n įrengimų ir n darbų. Kiekvieną įrengimą galima skirti tik vienam darbui atlikti. Jei i-tasis įrengimas skiriamas j-tajam darbui atlikti, jo eksploatavimo išlaidos sudaro cij. Bendros eksploatavimo išlaidos turi būti minimalios. xij nežinomasis parodo, ar i-tasis įrengimas paskirtas j-tajam darbui atlikti ar ne; jei xij=1 – paskirtas, jei xij=0 – nepaskirtas. Uždavinio pavidalas: , (j=1,n) - kiekvienam darbui skirtas tik vienas įrenginys. ,(i=1,n)-kiekvienas įrenginys gali būti skirtas tik vienam darbui. , (i=1,n ; j=1,n) Užrašytas uždavinys – transporto, kurio sprendinys apribota , xij reikšmės – nuliai arba vienetai. Kitas uždavinio variantas gaunamas, kai n kandidantų turime paskirti į n vietų, kai i-tojo kandidato teikiama nauda sudaro cij: Komivojažieriaus uždavinys. Keliaujantis prekiautojas turi aplankyti n miestų, nė į vieną neužsukdamas 2 kartus, ir grįžti į miestą, iš kurio išvyko. Jei žinome kelionės tarp bet kurių dviejų miestų trukmę, reikia sudaryti optimalų komivojažieriaus maršruta. - kelionės iš i-tojo miesto į j-tąjį trukmė/išlaidos. Kelionės trukmė/išlaidos turi būti minimalūs. - iš i-ojo miesto į j-ąjį komivojažierius nuvyksta (1) arba nenuvyksta (0). 22. Sveikaskaitinio tiesinio programavimo uždavinio sprendimas Turime kanoninį sveikaskaitinį tiesinio programavimo uždavinį: . Jam spręsti naudojame šakų ir rėžių metodą. Simpleksiniu metodu rasime šio uždavinio sprendinį . Jei visos koordinatės sveiki skaičiai, uždavinys išspręstas. Priešingu atveju pasirinkime kuria nors koordinatę, kurios reikšmė ne sveikaskaitinė, sakykim ir sudarykime du leistinų planų aibės poaibius: Čia [x] – sveikoji skaičiaus x dalis. Sąlygos ir leidžia, toliau dirbant su aibėmis ir bei jų nesveikaskaitiniais variantais, nebegrįžti prie plano, kuris netenkina xt sveikaskaitiškumo sąlygos. Nesunku įsitkinti, kad ir yra uždavinio leistinų planų aibės šakos. Pasirinkime pvz. ir įvertinkime viršutinį tikslo f-jos rėžį šioje aibėje. Tam reikia išspręsti tiesinio programavimo uždavinį aibėje be sveikatiškumo sąlygos. Jei gautas sprendinys bus sveikaskaitinis, tai turėsime pirmąjį sprendimo variantą, o reikšmę laikysime rekordu. Jei paaiškės, kad uždavinys neišsprendžiamas, darbą su šaka nutrauksime. Abiem atvejais pereisime prie šakos tyrimo. Pagaliau trečiuoju atveju bus nevisiškai sveikaskaitinis. Tada fiksuosime kaip viršutinį reikšmių rėžį aibėje , o pačią aibę šakosime į dalis pagal kurį nors nežinomąjį su nesveikaskaitine reikšme, sakykim xr.

Daugiau informacijos...

★ Klientai rekomenduoja

Šį rašto darbą rekomenduoja mūsų klientai. Ką tai reiškia?

Mūsų svetainėje pateikiama dešimtys tūkstančių skirtingų rašto darbų, kuriuos įkėlė daugybė moksleivių ir studentų su skirtingais gabumais. Būtent šis rašto darbas yra patikrintas specialistų ir rekomenduojamas kitų klientų, kurie po atsisiuntimo įvertino šį mokslo darbą teigiamai. Todėl galite būti tikri, kad šis pasirinkimas geriausias!