Opis prezentacije na pojedinačnim slajdovima:
1 slajd
Opis slajda:
Teorija odlučivanja PetrSU, A.P. Moshchevikin, 2004. Linearno programiranje Ovoj klasi linearno programiranje(75% problema koje rješavaju Amerikanci) uključuju probleme u kojima je ciljna funkcija Wm(x), m=1,2,...,M, ograničenja u obliku jednakosti hk(x)=0, k=1, 2... K, a nejednačine gj(x)>0, j=1,2,...J, su linearne i matematičko rješenje. Moguće teme zadataka LP: racionalna upotreba sirovina i materijala; zadaci optimizacije rezanja; optimizacija proizvodnog programa preduzeća; optimalan plasman i koncentracija proizvodnje; izraditi optimalan plan transporta, transporta; upravljanje zalihama; i mnoge druge koje pripadaju oblasti optimalnog planiranja. Postavljanje LP problema (definiranje indikatora učinka, varijabli zadatka, postavljanje linearne ciljne funkcije W(x) da bude minimizirana ili maksimizirana, funkcionalni hk(x), gj(x) i regionalni xli 2 slajd
Opis slajda:
Teorija odlučivanja PetrSU, A.P. Moshchevikin, 2004. Primjer LP problema Primjer - Optimizacija lokacije sporedne proizvodnje šumarije Šumarija ima 24 hektara slobodnog zemljišta pod ugarom i zainteresirana je za izvlačenje prihoda od toga. Može uzgajati sadnice brzorastuće hibridne jelke, koje sazrijevaju za godinu dana, ili gobice, preusmjeravajući dio zemljišta za ispašu. Drveće se uzgaja i prodaje u serijama od 1.000 komada. Potrebno je 1,5 ha za uzgoj jedne serije stabala i 4 ha za hranjenje jednog bika. Šumski okrug može potrošiti samo 200 sati godišnje na svoju proizvodnju. Praksa pokazuje da je za kultivaciju, sječu, sječu i skupljanje jedne serije stabala potrebno 20 sati. Za njegu jednog bika potrebno je i 20 sati, a šumarija za ovu svrhu ima mogućnost izdvojiti 6 hiljada rubalja. Godišnji troškovi za jednu seriju stabala iznose 150 rubalja. i 1,2 hiljade rubalja. za jednog bika. Već je potpisan ugovor za nabavku 2 bika. Po trenutnim cijenama, jedno božićno drvce će donijeti profit od 2,5 rubalja, jedan bik - 5 hiljada rubalja. 3 slajd
Opis slajda:
Teorija odlučivanja PetrSU, A.P. Moshchevikin, 2004. Izjava o problemu 1. Kao pokazatelj efikasnosti, preporučljivo je uzeti profit po operaciji (godišnji profit od zemljišta u rubljama). 2. Kao kontrolisane varijable problema treba uzeti sljedeće: x1 - broj utovljenih bikova godišnje; x2 - broj uzgojenih serija brzorastućih jelki, 1000 kom. svaki godišnje. 3. Ciljna funkcija: 5000 x1 + 2500 x2 max, gdje je 5000 neto prihod od jednog bika, rub.; 2500 - neto prihod od jedne serije stabala (1000 komada za 2,5 rubalja). 4. Ograničenja: 4.1. Po namjeni zemljišta, ha: 4 x1 + 1,5 x2 24 4.2. Prema budžetu, rubalja: 1200 x1 + 150 x2 6000 4.3. Po radnim resursima, h: 20 x1 + 20 x2 200 4.4. Obaveze po ugovoru, kom.: x1 2 4.5. Granice područja: x1 0, x2 0 4 slajd
Opis slajda:
Teorija odlučivanja PetrSU, A.P. Moshchevikin, 2004. Grafičko rješenje LP problema Prikazivanje na grafikonu linija koje odgovaraju sljedećim jednačinama, 4 x1 + 1,5 x2 = 24 1200 x1 + 150 x2 = 6000 20 x1 + 20 x 20 2 x2 = 0 zasjenimo područje u čijim su točkama zadovoljena sva ograničenja. Svaka takva tačka naziva se dopušteno rješenje, a skup svih dopuštenih rješenja naziva se dopušteno područje. Očigledno, rješenje LP problema se sastoji u pronalaženju najboljeg rješenja u dopuštenom području, koje se, pak, naziva optimalnim. U ovom primjeru, optimalno rješenje je izvodljivo rješenje koje maksimizira funkciju W=5000 x1 + 2500 x2. Vrijednost ciljne funkcije koja odgovara optimalnom rješenju naziva se optimalna vrijednost LP problema. 5 slajd
Opis slajda:
Teorija odlučivanja PetrSU, A.P.Moshchevikin, 2004 Grafičko rješenje LP problema 6 slajd
Opis slajda:
Teorija odlučivanja PetrSU, A.P. Moshchevikin, 2004. Grafičko rješenje LP problema Nabrajanje svih kutnih tačaka područja izvodljivih rješenja dovodi do pronalaženja maksimalnog prihoda u iznosu od 34 hiljade rubalja. (Š=5000x1+2500x2) koje šumarija može izvući uzgojem 3,6 junadi i 6,4 serije jelki. Cjelobrojne metode (na primjer, nabrajanje) daju x1=3 i x2=6, što dovodi do prihoda od 30 hiljada rubalja, x1=4 i x2=5 dovode do optimalnijeg rezultata od 32,5 hiljada rubalja, tačka x1 =3 i x2=7 dovodi do sličnog rezultata. Zbog velike dimenzije stvarnih praktičnih LP problema, grafička metoda se rijetko koristi, ali omogućava jasno razumijevanje jednog od glavnih svojstava LP - ako postoji optimalno rješenje u LP problemu, onda barem jedno od vrhova dozvoljenog regiona je optimalno rešenje. Unatoč činjenici da se dopušteno područje LP problema sastoji od beskonačnog broja tačaka, optimalno rješenje se uvijek može pronaći namjernim nabrajanjem konačnog broja njegovih vrhova. Simpleks metoda za rješavanje LP problema koji se razmatra u nastavku temelji se na ovoj fundamentalnoj osobini. 7 slajd
Opis slajda:
Teorija odlučivanja PetrSU, A.P.Moshchevikin, 2004. Rješavanje LP problema u MS Excel-u Jedna od ugrađenih funkcija MS Excel uređivača proračunskih tablica (potrebno je označiti kućicu prilikom instalacije MS Office-a) je "Traži rješenje" . Ovaj paket vam omogućava da brzo riješite probleme linearnog i nelinearnog programiranja. 8 slajd
Opis slajda:
Teorija odlučivanja PetrSU, A.P. Moshchevikin, 2004. LP problem u standardnom obliku LP problem u standardnom obliku sa m ograničenja i n varijabli ima sljedeći oblik: W = c1x1 + c2x2 + ... + cnxn min (max) pod ograničenja a11x1 + a12x2 + ... + a1nxn = b1; a21x1 + a22x2 + ... + a2nxn = b2; ... am1x1 + am2x2 + ... + amnxn = bm; x10; x20;...; xn0 b10; b20;...; bm0 U matričnom obliku W = cx min (max) pod ograničenjima Ax = b; x0; b0, gdje je A matrica dimenzije m*n, x je vektor stupca varijabli dimenzije n*1, b je vektor stupca resursa dimenzije m*1, s je vektor reda procjena LP problem 1*n. 9 slajd
Opis slajda:
Teorija odlučivanja PetrSU, A.P.Moshchevikin, 2004. Transformacija nejednakosti Ograničenja nejednakosti mogu se transformisati u jednakosti uvođenjem takozvanih rezidualnih ili redundantnih varijabli. Jednadžba iz prethodnog primjera 4x1 + 1,5x2 24 može se pretvoriti u jednakost koristeći nenegativnu rezidualnu varijablu 4x1 + 1,5x2 + x3 = 24. Varijabla x3 je nenegativna i odgovara razlici desne i lijeve strane strane nejednakosti. Slično, x1 2 se može transformisati uvođenjem redundantne varijable x4: x1 - x4 = 2. 10 slajd
Opis slajda:
Teorija odlučivanja PetrSU, A.P. Moshchevikin, 2004 predznakom varijabli Transformacija varijabli neograničenih predznakom Varijable koje uzimaju i pozitivne i negativne vrijednosti treba zamijeniti razlikom dvije nenegativne: x = x+ - x-; x+0; x- 0. Primjer. 3x1+4x2+5x3+4x4 max 2x1+x2+3x3+5x4 5 5x1+3x2+x3+2x4 20 4x1+2x2+3x3+x4 = 15 x10; x20; x3 0; x4 = znak -3x1-4x2+5x3-4x4 min 2x1+x2-3x3+5x4-x5 = 5 5x1+3x2-x3+2x4+x6 = 20 4x1+2x2-3x3+x4 = 15 x10; x20; x30; x4 = znak; x4 =x8-x7 -3x1-4x2+5x3-4x8+4x7 min 2x1+x2-3x3+5x8-5x7-x5 = 5 5x1+3x2-x3+2x8-2x7+x6 = 20 4x1+2x2-3x3+x8 -x7= 15 x1,x2,x3,x5,x6,x7,x80; x4=x8 -3x1-4x2+5x3-4x4+4x7 min 2x1+x2-3x3+5x4-5x7-x5 = 5 5x1+3x2-x3+2x4-2x7+x6 = 20 4x1+2x2-3x3+x4-x = 15 x1,x2,x3,x4,x5,x6,x70; x8 zamijenjen sa x4 11 slajd
Opis slajda:
Teorija odlučivanja PetrSU, A.P. Moshchevikin, 2004 Simpleksna LP metoda Simpleksna metoda je iterativni postupak za rješavanje LP problema napisan u standardnom obliku, sistem jednačina u kojem i uz pomoć elementarnih operacija na matricama sveden je na kanonski oblik: x1 + a1,m+1xm+1 + ... + a1sxs+...+ a1nxn = b1; x2 + a2,m+1xm+1 + ... + a2sxs+...+ a2nxn = b2; ... xm + am,m+1xm+1 + ... + amsxs+...+ amnxn = bm. Varijable x1, x2,...,xm, koje ulaze sa jediničnim koeficijentima samo u jednu jednačinu sistema, a sa nultim koeficijentima u ostatku, nazivaju se osnovnim. U kanonskom sistemu, svaka jednačina odgovara tačno jednoj osnovnoj promenljivoj. Preostalih n-m varijabli (xm+1, ...,xn) nazivaju se nebazične varijable. Da bi se sistem doveo u kanonski oblik, mogu se koristiti dvije vrste elementarnih operacija nad nizovima: Množenje bilo koje jednačine sistema pozitivnim ili negativnim brojem. Dodavanje bilo kojoj jednačini druge jednačine sistema, pomnožene pozitivnim ili negativnim brojem. 12 slajd
Opis slajda:
Teorija odlučivanja PetrSU, A.P. Moshchevikin, 2004 Simpleksna metoda LP Zapisivanje problema u obliku jednačina x1 + a1,m+1xm+1 + ... + a1sxs+...+ a1nxn = b1; x2 + a2,m+1xm+1 + ... + a2sxs+...+ a2nxn = b2; ... xm + am,m+1xm+1 + ... + amsxs+...+ amnxn = bm. identično je zapisano u obliku matrica 1 0 .. 0 a1,m+1 .. a1s .. a1n x1 b1 0 1 .. 0 a2,m+1 .. a2s .. a2n x2 = b2 . . .. . . .. . .. . .. .. 0 0 .. 1 am,m+1 .. ams .. amn xn bm 13 slajd
Opis slajda:
Teorija odlučivanja PetrSU, A.P. Moshchevikin, 2004 Algoritam Simpleks metode 1. Odaberite početno dopušteno osnovno rješenje. Osnovno rješenje je rješenje dobijeno sa nultim vrijednostima nebazičnih varijabli, tj. xi=0, i=m+1,...,n. Osnovno rješenje se naziva dopuštenim osnovnim rješenjem ako su vrijednosti osnovnih varijabli koje su uključene u njega nenegativne, tj. xj = bj 0, j=1,2,...,m. U ovom slučaju, funkcija cilja će imati sljedeći oblik: W=cbxb=c1b1+c2b2+...+cmbm. Popunjavamo početnu tabelu simpleks metode: 14 slajd
Opis slajda:
Teorija odlučivanja PetrSU, A.P.Moshchevikin, 2004 Algoritam Simpleksne metode 2. Izračunajte vektor relativnih procjena c koristeći pravilo produkta cj = cj - cbSj, gdje je cb vektor procjena osnovnih varijabli; Sj je j-ti stupac koeficijenata aij u kanonskom sistemu koji odgovara razmatranoj bazi. Dopunjavamo početnu tabelu sa c - linijom. 15 slajd
Opis slajda:
Teorija odlučivanja PetrSU, A.P. Moshchevikin, 2004 Simpleks metodski algoritam). Rješenje pronađeno. 4. U suprotnom je potrebno umjesto jedne od osnovnih varijabli u bazu uvesti nebazičnu varijablu xr sa najvećom vrijednošću cj (vidi tabelu). 16 slajd
Opis slajda:
Teorija odlučivanja PetrSU, A.P. Moshchevikin, 2004 Simpleks metod algoritam 5. Koristeći pravilo minimalnog omjera min(bi/air) određujemo varijablu xp, izvedenu iz baze. Ako je koeficijent zraka negativan, tada bi/air=. Kao rezultat toga, presjek stupca koji sadrži ulaznu ne-osnovnu varijablu xr i reda koji sadrži izlaznu osnovnu varijablu xp odredit će poziciju vodećeg elementa tablice. 6. Primjenjujemo elementarne transformacije kako bismo dobili novo prihvatljivo osnovno rješenje i novu tablicu. Kao rezultat toga, stožerni element bi trebao biti jednak 1, a preostali elementi pivot kolone bi trebali biti postavljeni na nulu. 7. Izračunajte nove relativne rezultate koristeći pravilo skalarne transformacije i nastavite na korak 4. 17 slajd
Opis slajda:
Teorija odlučivanja PetrSU, A.P.Moshchevikin, 2004 Primjer rješenja simpleks metode Primjer - Optimizacija lokacije bočne proizvodnje šumarstva 3. Ciljna funkcija: 5000 x1 + 2500 x2 max, 4. Ograničenja: 4.1. Po namjeni zemljišta, ha: 4 x1 + 1,5 x2 24 4.2. Prema budžetu, rubalja: 1200 x1 + 150 x2 6000 4.3. Po radnim resursima, h: 20 x1 + 20 x2 200 4.4. Obaveze po ugovoru, kom.: x1 2 4.5. Regionalna ograničenja: x1 0, x2 0 Svodimo problem na standardni oblik: 4 x1 + 1,5 x2 +x3= 24 1200 x1 + 150 x2 +x4= 6000 20 x1 + 20 x2 +x5= 200 x1 – x6 2 x1 ... x6 0 Prve tri jednačine imaju, odnosno, x3, x4, x5 u osnovnoj varijabli, au četvrtoj ga nema zbog činjenice da varijabla x6 ima negativan jedinični koeficijent. Da bismo sistem sveli na kanonski oblik, koristimo metodu veštačkih varijabli. x1 – x6+x7= 2, uveo je vještačku varijablu x7. slajd 2 Metode linearnog programiranja koriste se u prediktivnim proračunima, planiranju i organizaciji proizvodnih procesa. Linearno programiranje je grana matematike koja proučava metode za istraživanje i pronalaženje ekstremnih vrijednosti neke linearne funkcije čiji su argumenti podložni linearnim ograničenjima. slajd 3 Takva linearna funkcija naziva se ciljna funkcija, a skup kvantitativnih odnosa između varijabli koji izražavaju određene zahtjeve ekonomskog problema u obliku jednačina ili nejednakosti naziva se sistem ograničenja. Riječ programiranje je uvedena jer nepoznate varijable obično određuju program ili plan rada nekog predmeta. slajd 4 Skup relacija koji sadrži ciljnu funkciju i ograničenja na njene argumente naziva se matematički model optimizacijskog problema. ZLP je napisan u opštem obliku na sledeći način: pod ograničenjima slajd 5 Ovdje - nepoznato, - date konstante Ograničenja se mogu dati jednadžbama. Najčešći zadaci su u obliku: postoje resursi pod ograničenjima. Potrebno je odrediti količine ovih resursa pri kojima će funkcija cilja dostići maksimum (minimum), odnosno pronaći optimalnu raspodjelu ograničenih resursa. U ovom slučaju postoje prirodna ograničenja >0. slajd 6 U ovom slučaju, ekstremum ciljne funkcije se traži na dozvoljenom skupu rješenja određenom sistemom ograničenja, a sve ili neke od nejednakosti u sistemu ograničenja mogu se zapisati u obliku jednačina. Slajd 7 Ukratko, LLP ima oblik: pod ograničenjima Slajd 8 Za sastavljanje matematičkog modela ZLP-a potrebno je: 1) označiti varijable; 2) sastavi funkciju cilja; 3) zapisuje sistem ograničenja u skladu sa svrhom zadatka; 4) zapisati sistem ograničenja, uzimajući u obzir indikatore dostupne u stanju problema. Ako su sva ograničenja problema data jednadžbama, tada se model ovog tipa naziva kanonskim. Ako je barem jedno od ograničenja zadano nejednakošću, tada je model nekanonski. Slajd 9 problem optimalne raspodele resursa u planiranju proizvodnje u preduzeću (problem asortimana); zadatak maksimiziranja proizvodnje za dati asortiman; problem mešavina (obroci, dijeta, itd.); transportni zadatak; zadatak racionalnog korišćenja raspoloživih kapaciteta; zadatak zakazivanja. Slajd 10 Pretpostavimo da preduzeće proizvodi različite proizvode. Njihova proizvodnja zahtijeva različite vrste resursa (sirovine, radno i mašinsko vrijeme, pomoćni materijali). Ova sredstva su ograničena i iznose konvencionalne jedinice u planskom periodu. Poznati su i tehnološki koeficijenti koji pokazuju koliko je jedinica i-tog resursa potrebno za proizvodnju proizvoda j-te vrste. Neka je dobit koju preduzeće primi pri prodaji jedinice proizvoda j-te vrste jednaka. U planskom periodu pretpostavlja se da su svi indikatori konstantni. slajd 11 Potrebno je izraditi takav plan proizvodnje proizvoda, u čijoj implementaciji bi profit preduzeća bio najveći. Ekonomsko-matematički model problema slajd 12 Ciljna funkcija je ukupna dobit od prodaje svih vrsta proizvedenih proizvoda. U ovom modelu problema optimizacija je moguća odabirom najprofitabilnijih vrsta proizvoda. Ograničenja znače da za bilo koji od resursa njegova ukupna potrošnja za proizvodnju svih vrsta proizvoda ne prelazi njegove rezerve. slajd 13 Slajd 14 Pretpostavimo da će se proizvoditi proizvodi tipa A, - proizvodi tipa B i - proizvodi tipa C. Tada će za proizvodnju takvog broja proizvoda biti potrebno utrošiti mašinsko-sate opreme za glodanje. Budući da ukupan fond radnog vremena mašina ovog tipa ne može biti veći od 120, mora biti zadovoljena nejednakost slajd 15 Raspravljajući na sličan način, možemo sastaviti sistem ograničenja slajd 16 Sada kreirajmo ciljnu funkciju. Dobit od prodaje proizvoda vrste A iznosiće 10, od prodaje proizvoda tipa B -14 i od prodaje proizvoda tipa C-12 Ukupna dobit od prodaje svih proizvoda iznosiće Slajd 17 Tako dolazimo do sljedećeg LLP: Među svim nenegativnim rješenjima sistema nejednačina potrebno je pronaći jedno za koje ciljna funkcija ima maksimalnu vrijednost. Slajd 18 Proizvodi mljekare su mlijeko, kefir i pavlaka pakovana u kontejnere. Za proizvodnju 1 tone mlijeka, kefira i pavlake potrebno je 1010,1010, odnosno 9450 kg mlijeka. Istovremeno, trošak radnog vremena prilikom izlivanja 1 tone mlijeka i kefira iznosi 0,18 i 0,19 mašinskih sati. Na pakovanju od 1 tone pavlake specijalne mašine rade 3,25 sati. Slajd 19 Ukupno, fabrika može da iskoristi 136.000 kg mleka za proizvodnju punomasnih mlečnih proizvoda. Glavna oprema može biti zauzeta 21,4 mašinskih sati, a mašine za pakovanje pavlake 16,25 sati. Dobit od prodaje 1 tone mlijeka, kefira i pavlake je 30, 22 i 136 rubalja. Postrojenje mora proizvoditi najmanje 100 tona flaširanog mlijeka dnevno. Nema ograničenja u proizvodnji drugih proizvoda. Slajd 20 Potrebno je odrediti koje proizvode iu kojoj količini biljka treba dnevno proizvoditi kako bi profit od njegove prodaje bio maksimiziran. Napravite matematički model problema. slajd 21 Neka fabrika proizvodi tone mlijeka, tone kefira i tone pavlake. Tada mu treba kg mlijeka. S obzirom da postrojenje ne može potrošiti više od 136.000 kg mlijeka dnevno, nejednakost mora biti zadovoljena slajd 22 Vremenski rokovi za pakovanje mleka i kefira i pavlake. Pošto se dnevno mora proizvoditi najmanje 100 tona mlijeka. U ekonomskom smislu slajd 23 Ukupna dobit od prodaje svih proizvoda jednaka je rubljama. Dakle, dolazimo do sljedećeg problema: pod ograničenjima Pošto je ciljna funkcija linearna i ograničenja su data sistemom nejednakosti, ovaj problem je LLP. slajd 24 Postoje dvije vrste proizvoda koji sadrže hranjive tvari (masti, proteini, itd.) Slajd 25 slajd 26 Ukupni trošak prehrane pod ograničenjima, uzimajući u obzir potrebni minimum nutrijenata Slajd 27 Matematička formulacija problema: napraviti dnevnu ishranu koja zadovoljava sistem ograničenja i minimizira ciljnu funkciju. Uopšteno govoreći, grupa zadataka o mješavinama uključuje probleme pronalaženja najjeftinijeg skupa određenih polaznih materijala koji mješavini daju željena svojstva. Dobijene smjese moraju sadržavati n različitih komponenti u određenim količinama, a same komponente su sastojci m polaznih materijala. Slajd 28 Uvedemo oznaku: -količina j-tog materijala uključenog u smjesu; -cijena materijala tipa j; je minimalni potrebni sadržaj i-te komponente u smjesi. Koeficijenti pokazuju specifičnu težinu i-te komponente u jedinici j-tog materijala Slajd 29 Ciljna funkcija je ukupni trošak mješavine, a funkcionalna ograničenja su ograničenja sadržaja komponenti u mješavini: mješavina mora sadržavati komponente u količinama ne manjim od specificiranih. slajd 30 U fabrici konfekcije, tkanina se može rezati na nekoliko načina kako bi se proizveli željeni komadi odevnih predmeta. Neka se i-ti tip dijelova proizvodi sa j-tom varijantom rezanja, a količina otpada u ovoj varijanti rezanja je otpad. Napravite matematički model problema. Slajd 31 Rješenje. Pretpostavimo da je prema j-toj varijanti izrezano na stotine tkanina. Budući da se pri rezanju tkanine po j-toj opciji dobijaju dijelovi i-te vrste, za sve opcije krojenja od upotrijebljenih tkanina ukupna količina otpada za sve opcije krojenja će biti Slajd 35 Def.4. Glavni, ili kanonski, LLP je zadatak koji se sastoji u određivanju vrijednosti ciljne funkcije, pod uslovom da je sistem ograničenja predstavljen kao sistem jednačina: slajd 36 Ako je zbog praktičnosti ili smisla zadatka potrebno prelazak s jednog oblika snimanja na drugi, postupite na sljedeći način. Ako trebate pronaći minimum funkcije, onda možete prijeći na pronalaženje maksimuma množenjem ciljne funkcije sa (-1). Ograničenje tipa nejednakosti može se pretvoriti u jednakost dodavanjem nenegativne dodatne varijable na njegovu lijevu stranu, a ograničenje tipa nejednakosti može se pretvoriti u ograničenje jednakosti oduzimanjem dodatne nenegativne varijable sa njegove lijeve strane. Slajd 41 Dizajn podrške se naziva nedegenerisanim ako sadrži m pozitivnih komponenti. Inače se naziva degenerisanim. Plan, u kojem funkcija cilja LLP-a uzima svoju maksimalnu (minimalnu) vrijednost, naziva se optimalnim.
Pogledajte sve slajdove Uvod Linearno programiranje kao grana operativnog istraživanja ima skoro četrdesetogodišnju istoriju. Uvođenje kompjuterske tehnologije dalo je značajan podsticaj istraživanjima u ovoj oblasti matematike. Razvijen je niz algoritama za rješavanje problema linearnog programiranja, au narednim godinama kreirani su programi i softverski paketi, uglavnom za velike računare. Najveći dio literature o Linearni program u našoj zemlji izlazio je 60-ih - 70-ih godina. Istraživanja u ovoj oblasti (teorijska i primijenjena) nastavljaju se iu današnje vrijeme. Metode linearnog programiranja su se pokazale kao veoma efikasne za rešavanje nekih problema iz oblasti istraživanja operacija. Riječ "programiranje" razumijemo kao planiranje, a to određuje prirodu aplikacija koje se razmatraju. Glavne ideje linearnog programiranja nastale su tokom Drugog svetskog rata u vezi sa traženjem optimalnih strategija u vođenju vojnih operacija. Od tada su našli široku primenu u industriji, trgovini i administraciji - kako na lokalnom tako i na nacionalnom nivou. Ove metode mogu riješiti mnoge (iako ne sve) probleme vezane za efikasno korištenje ograničenih resursa. Matematičke metode i modeli su dobro poznati, rasprostranjeni i korišćeni pod raznim nazivima - matematičke metode u odlučivanju; metode istraživanja operacija; ekonomske i matematičke metode; metode ekonomske kibernetike; metode optimalnog upravljanja, primijenjena matematika u ekonomiji i organizaciji proizvodnje itd. U mnogim publikacijama na ovu temu (manje ili više opsežnim) razmatraju se u raznim kombinacijama. Operativno istraživanje je naučna disciplina koja se bavi razvojem i praktičnom primjenom metoda za najefikasnije upravljanje različitim organizacionim sistemima. Upravljanje bilo kojim sistemom implementira se kao proces koji poštuje određene zakone. Njihovo znanje pomaže da se odrede uslovi neophodni i dovoljni za sprovođenje ovog procesa. Da bi se to postiglo, svi parametri koji karakterišu proces i vanjske uslove moraju biti kvantificirani i izmjereni. Stoga je svrha operativnog istraživanja kvantitativno opravdanje odluka koje se donose o organizaciji menadžmenta. Svrha svakog modeliranja je proučavanje objekta najprije kvalitativno, a zatim, kako se informacije akumuliraju i model se razvija, na sve preciznijim kvantitativnim razinama. Ova razmatranja mogu se ilustrirati jednostavnim primjerom. Postojala je (i još uvijek postoji) metoda "teorije vjerovatnoće" kao široke klase matematičkih modela koji rade s konceptima "vjerovatnosti", "slučajnog događaja", "slučajne varijable", "matematičkog očekivanja (srednja vrijednost) slučajne varijable ", "disperzija (raspršenje)" i dr. Na granici XIX i XX vijeka. pojavljuje se novi objekt - komutirani telefonski komunikacioni sistem, sa kojim se vezuju pojmovi "zahtjev za povezivanje", "odbijanje", "vrijeme čekanja veze", "prebacivanje" i druge karakteristike sistema. U 20-im godinama. A. K. Erlang je povezao ovu metodu i objekat; kao rezultat, kreiran je matematički probabilistički model procesa u komutiranim telefonskim mrežama, koji operiše konceptima "tok narudžbi", "prosječno vrijeme čekanja", "prosječna dužina čekanja za uslugu", "varijansa vremena čekanja", "neuspjeh". vjerovatnoća“ itd. Dalji razvoj ovog naučnog pravca pokazao je plodnost idejne osnove ovog modela, njegove široke dizajnerske mogućnosti. Model se razvio u metodu za proučavanje složenih sistema - "teoriju čekanja", čija su terminologija i konceptualna osnova apstrahovani od asocijacija na telefonske mreže i dobili opšti teorijski karakter. A sada se novi modeli mogu graditi primjenom teorije čekanja na druge objekte (proizvodni procesi, operativni sistemi računara, prometni tokovi, itd.). Dakle, s jedne strane, metoda se definira ako se razvije homogeni skup modela, odnosno načini sagledavanja različitih objekata u jednom aspektu, a s druge strane, predmet je poznat što je dublje, što se više objektnih modela razvija. . Istovremeno, dualna priroda modela dovodi do dualizma konceptualne osnove modeliranja, koja uključuje opće (iz „metode”) i specifične (od „objekta”) koncepte. Operativno istraživanje je skup primijenjenih matematičkih metoda koji se koriste za rješavanje praktičnih organizacionih (uključujući ekonomske) problema. To je složena naučna disciplina. Opseg problema koje proučava nije dovoljno definisan. Ponekad se operativno istraživanje shvata veoma široko, uključujući niz čisto matematičkih metoda, ponekad, naprotiv, vrlo usko - kao praktična tehnika za rešavanje strogo definisane liste problema korišćenjem ekonomskih i matematičkih modela. Glavni metod operativnog istraživanja je sistematska analiza svrsishodnih radnji (operacija) i objektivna (posebno kvantitativna) komparativna procjena mogućih rezultata ovih akcija. Među najvažnijim klasama problema u istraživanju operacija su problemi upravljanja zalihama, alokacije i dodjele resursa (problemi distribucije), problemi čekanja, problemi zamjene opreme, naručivanja i koordinacije (uključujući teoriju rasporeda), suparnički (na primjer, igre), problemi pretraživanja, itd. Među korištenim metodama su matematičko programiranje (linearno, nelinearno, itd.), diferencijalne i diferencijalne jednadžbe, teorija grafova, Markovljevi procesi, teorija igara, teorija (statističkih) rješenja, teorija prepoznavanja obrazaca i broj drugih. Smatra se da je istraživanje operacija nastalo uoči Drugog svjetskog rata, kada je u Engleskoj stvorena grupa stručnjaka na radarskoj stanici za rješavanje tehničkih problema uz pomoć matematike. Fokusirali su se na poređenje efektivnosti načina rješavanja problema, pronalaženje optimalnog rješenja. Učešće u ovoj grupi predstavnika različitih specijalnosti predodredilo je sveobuhvatan, ili kako se sada kaže, sistematski pristup. Trenutno stotine istraživačkih institucija i grupa u desetinama zemalja rade u ovom pravcu. Društva za operativna istraživanja organizira Međunarodna federacija (IFORS). Ruski naučnici L.V. Kantorovich, N.P. Buslenko, E.S. Wentzel, N.N. Vorobyov, N.N. Moiseev, D.B. Yudin i mnogi drugi. Značajan doprinos formiranju i razvoju operativnih istraživanja dali su strani naučnici R. Akof, R. Bellman, G. Danzig, G. Kuhn, J. Neumann, T. Saaty, R. Churchman, A. Kofman i drugi. Metode istraživanja operacija, kao i sve matematičke metode, uvijek pojednostavljuju, donekle, grublje problem, odražavajući nelinearne procese sa linearnim modelima, stohastičke sisteme sa determinističkim itd. Stoga ne treba ni preuveličavati vrijednost kvantitativnih metoda istraživanja operacija, niti ga potcijeniti., pozivajući se na primjere neuspješnih odluka. Poznata je paradoksalna definicija koju je dao veliki američki specijalista u ovoj oblasti T. A. Saaty: “Istraživanje operacija je umjetnost davanja loših odgovora na praktična pitanja na koja se još gore odgovara na druge načine.” CENTRALNA MEĐREGIONALNA KOLEŽA ZA INDUSTRIJSKE TEHNOLOGIJE I PREDUZETNIŠTVO Ja odobravam zamjenik Direktor obrazovanja « » 200 G . VJEŽBA za dizajn kursa iz predmeta "Matematičke metode" Student: Sergejev Evgenij Anatoljevič. Tema projekta: "Linearno programiranje, rješavanje problema simpleks metodom". OBJAŠNJENJE Zadaci i njihovo rješavanje: Prvi zadatak: Riješite simpleks problem na sljedeći način: F = 2X1 +3X2 → max 3.1.2 Zadatak dva: Kompanija proizvodi dvije vrste proizvoda. Vrste sirovina, njihove rezerve, stope potrošnje sirovina po god. e. za svaku vrstu proizvoda, proizvodna dobit od prodaje proizvoda dati su u tabeli: 3.1.3. Zadatak tri: Preduzeće proizvodi 3 vrste proizvoda, koristeći 3 vrste sirovina. Zalihe sirovina, njihove stope potrošnje i dobit od prodaje svakog proizvoda prikazane su u tabeli: Kako planirati proizvodnju da bi se maksimizirao profit? 3.1.4. Četvrti zadatak: Za proizvodnju 4 vrste proizvoda koriste se 3 vrste sirovina. Zalihe sirovina, njihove stope potrošnje i dobit od prodaje svakog proizvoda prikazane su u tabeli: Kako planirati proizvodnju da bi se maksimizirao profit? 3.
Zaključak 4.
Bibliografija Predsjednik komisije za ciklus/ Baranov V.A. Menadžer projekta kursa/ Karpuškin A.G. Datum izdavanja zadatka: Datum završetka: « » 2007 « » 2007 SIMPLEX METHOD Simpleks metodu je prvi predložio američki naučnik J. Danzig 1949. godine, međutim, davne 1939. godine ideje metode je razvio ruski naučnik L V. Kantorovich. Simpleks metoda, koja omogućava rješavanje bilo kojeg problema linearnog programiranja, je univerzalna. Trenutno se koristi za kompjuterske proračune, ali jednostavni primjeri korištenjem simpleks metode mogu se rješavati i ručno. Za implementaciju simpleks metode - sekvencijalno poboljšanje rješenja - potrebno je savladati tri glavna element: Način da se odredi bilo koje početno dozvoljeno osnovno rješenje problema; Pravilo prelaska na najbolje (tačnije, ne na najgore) rješenje; Kriterij za provjeru optimalnosti pronađenog rješenja. Da bi se koristila simpleks metoda, problem linearnog programiranja se mora svesti na kanonski oblik, tj. sistem ograničenja mora biti predstavljen u obliku jednačina. Obični Jordanski izuzeci Razmotrimo sistem od m linearnih jednačina sa n nepoznatih a11 x1 + a12 x2 + … + a1n xn = b1, am1 x1 + am2 x2 + … + amn xn = bm. Ovaj sistem zapisujemo u obliku tabele a11 … a1j … a1n ……………….. ai1 … aij … ain ……………….. am1 … amj … amn Korak obične Jordanove eliminacije (OJI) koji se izvodi na datoj tablici s elementom za razrješenje aij ≠ 0 s I razrješujućim redom i j razrješujućim stupcem je operacija rješavanja jednadžbe bi = ai1 x1 + ai2 x2 + … + aij xj + … + ain xn u odnosu na xj, zamjenom ovog rješenja u originalni sistem, i zapisivanjem novodobijenog sistema u obliku nove tabele. Lako je provjeriti da li će nova tabela izgledati b11 b12 … a1j … b1n b21 b22 … a2j … b2n ……………….. Ai1 –ai2 … 1… -ain ……………….. bm1 bm2 … amj … bmn gdje je brs = ars aij - arj ais (i ≠ r, j ≠ s), i svi elementi tabele moraju biti podeljeni sa aij . Dakle, jedan korak Jordan Elimination (JJI) transformiše originalnu tabelu u novu tabelu prema šemi koja se sastoji od sledećih 5 pravila: 1) omogućavajući element je zamijenjen jednim 2) preostali elementi kolone za razrješenje j ostaju nepromijenjeni. 3) preostali elementi niza za razrješenje i mijenjaju samo svoje predznake. 4) preostali elementi brs se izračunavaju po formuli brs = ars aij - arj ais 5) svi elementi nove tabele su podeljeni sa rezolucionim elementom aij. Primjer 1. Za sto Jordanski izuzeci omogućavaju prelazak sa nasumično uzetog kartezijanskog sistema koordinatnih ravnina na novi sistem u kojem su koordinate tačaka njihova odstupanja od zanimljivijeg sistema ravnina za određeni problem. Modifikovani Jordanski izuzeci Ako je originalni sistem jednačina ai1 x1 + ai2 x2 + … + ain xn = bi, gdje je i = 1,m, zapisati kao -ai1 (-x1) - ai2 (-x2) - ... - ain (-xn) = bi i napravi sto koji se dobija prema pravilima 1 - 5 GOG sa jedinom promjenom da pravila 2 i 3 mijenjaju uloge: 1) preostali elementi dozvoljenog niza ostaju nepromijenjeni 2) preostali elementi kolone za razrješenje mijenjaju samo svoje predznake Razmotrite sistem 2X1 + 3X2 - 5X3 = 16 = b1, 3X1 - 2X2 + 4X3 = 36 = b2, 5X1 + 7X2 - 11X3 = 44 = b3. Zapišimo to u obliku tabele Ekstremi linearne funkcije Neka se razmotri opšti problem linearnog programiranja. Računske metode LP zasnovane su na sljedećoj fundamentalnoj teoremi. Teorema. Ako problem linearnog programiranja ima optimalno rješenje (uvijek u ograničenom području, a u neograničenom području ovisno o ograničenosti funkcije Z), onda se poklapa s barem jednim od potpornih rješenja sistema restriktivnih jednačina. Prema ovoj teoremi, umjesto proučavanja beskonačnog skupa izvodljivih rješenja da bi se među njima pronašlo željeno optimalno rješenje, potrebno je proučavati samo konačan broj potpornih rješenja. Ova teorema kaže da postoji barem jedno optimalno rješenje za podršku, međutim, u problemima može postojati nekoliko optimalnih rješenja za podršku (alternativni optimum). Dakle, shematski dijagram za rješavanje problema linearnog programiranja je sljedeći: 1. Uz pomoć ZhI-a pronaći ćemo sva rješenja za podršku sistema. a11 x1 + a12 x2 + … + a1n xn = b1 , ……................... ak1 x1 + ak2 x2 + … + akn xn = bk , ak+1,1 x1 + ak+1,2 x2 + … + ak+1n xn ≤ bk+1 , ……................... am1 x1 + am2 x2 + … + amn xn ≤ bm . 2. Izračunajte za svaku od njih vrijednost funkcije Z, određene omjerom. Z = c1 x1 + c2 x2 + … + cn xn. 3. Od njih biramo ekstremno Z. Treba napomenuti da može postojati vrlo veliki broj referentnih rješenja, pa je potrebno izvršiti redosledno nabrajanje referentnih rješenja, postižući na svaki korak monotone promjene funkcije Z. Takva ideja o sukcesivnom poboljšanju rješenja ugrađena je u glavnu računsku metodu za rješavanje problema linearnog programiranja, nazvanu simpleks metoda. Simpleks metoda zasnovana na punim tabelama Postavljanje problema određivanja optimalnog asortimana proizvoda Preduzeće može da proizvodi dve vrste proizvoda A i B, sa ograničenim resursima materijala od gvožđa i čelika za njihovu proizvodnju, u količinama od 350, odnosno 392 kg i opreme u količini od 408 mašinskih sati. Podaci prikazani u obliku tabele karakterišu troškove svake od tri vrste resursa navedene za proizvodnju jednog proizvoda A i B. Potrebno je odrediti koliko proizvoda A i B treba da proizvede preduzeće da bi ostvarilo najveći profit. Uvodimo tražene nepoznanice X1 i X2, koje označavaju broj proizvoda A i B koje preduzeće treba da proizvede. Tada se matematički problem može formulirati na sljedeći način. Među skupom nenegativnih rješenja sistema nejednačina 14X1 + 5X2 ≤ 350, (1.1) 14X1 + 8X2 ≤ 392, 6X1 + 12X2 ≤ 408, pronaći rješenje za koje je funkcija Z = 10 X1 + 5 X2 dostiže svoju najveću vrijednost. Geometrijsko rješenje zadatka Prije svega, konstruirajmo oblast izvodljivih rješenja koja odgovaraju sistemu nejednačina. Da biste to učinili, zamijenite svaku od nejednakosti jednakošću 14X1 + 5X2 = 350, (1. ravna linija), 14X1 + 8X2 = 392, (2. red), 6X1 + 12X2 = 408, (3. prava linija), izgradnja granične linije. Uzimajući u obzir da je X1 ≥ 0 i X2 ≥ 0, dobijamo zasjenjeni dio ravni, koji čini poligon OABCD rješenja (Sl. 1). Zatim gradimo liniju nivoa 10X1 + 5X2 = 0 i vektor (10; 5), koji su međusobno okomiti. Lako je pokazati da vektor daje smjer najvećeg porasta linearne funkcije. Zaista Z0 \u003d 10X10 + 5X20 \u003d 10 * 0 + 5 * 0 = 0, ZA \u003d 10X1A + 5X2A \u003d 10 * 0 + 5 * 34 = 170, ZD = 10X1D + 5X2D = 10 * 25 + 5 * 0 = 250 itd. Od svih linija nivoa biramo dvije, od kojih jedna prolazi kroz tačku 0 i daje minimalnu vrijednost funkcije Z, a druga prolazi kroz tačku C i funkcija Z za nju poprima maksimalnu vrijednost. Ove linije nivoa nazivaju se referentnim linijama. Rice. 1 Tačku C formiraju prva i druga linija. Dakle, rješavanje sistema jednačina 14Xl + 5X2 = 350, 14X1 + 8X2 = 392, pronađite koordinate tačke C X1 = 20, X2 = 14, dok Zmax \u003d 10 * 20 + 5 * 14 = 270 rubalja. Dakle, maksimalni profit od 270 rubalja. biće primljeno ako preduzeće proizvede 20 proizvoda tipa A i 14 proizvoda tipa B. Pronalaženje maksimuma linearne funkcije Simpleks metoda za rješavanje problema linearnog programiranja zasniva se, uz neke dopune, na prethodno analiziranoj metodi uzastopnih eliminacija, koja predstavlja skup pogodnih računskih algoritama zasnovanih na sekvencijalnoj primjeni identičnih (simpleksnih) transformacija sistema jednačina. Dodavanje na lijevu stranu nejednakosti 14X1 + 5X2 ≤ 350, 14X1 + 8X2 ≤ 392, 6X1 + 12X2 ≤ 408, neka nenegativna vrijednost Yj ≥ 0 (i = 1, 2, 3), (1.2) nazivamo izjednačujuća ili osnovna varijabla, pretvaramo ih u jednadžbe: X1 + 5X2 + Y1 Štaviše, može se pokazati da svakom rješenju sistema nejednačina (1.1) odgovara jedinstveno rješenje sistema jednačina (1.3) i nejednačina (1.2) i obrnuto. Svaka od varijabli Y1, Y2, Y3 uključena je u samo jednu jednačinu i zavisi od varijabli X1 i X2, koje nazivamo slobodnim. Sistem (1.3) odgovara početnom dozvoljenom osnovnom rješenju X1 = X2 = 0; Y1 = 350; Y2 = 392; Y3 = 408 i Z = 0. Izvodimo prvu identičnu transformaciju sistema jednačina (1.3). Biramo rezolucionu kolonu koja odgovara najmanjem negativnom elementu u Z redu, jer je teoretski utvrđeno da se, pod inače jednakim uslovima, može očekivati veći porast Z funkcije. Na presjeku odabrane kolone i reda nalazi se broj rezolucije. Prvu jednačinu podijelimo brojem rezolucije i zapišemo rezultirajuću jednačinu. Množenjem ove jednačine sa 14, 6 i -10 i oduzimanjem od 2., 3. i 4. jednačine sistema (1.3), dolazimo do sledećeg sistema (1.4): X2 + 1/4 Y1 = 25, X2 - 6/14 Y1 + Y3 Takva identična transformacija, u kojoj se odabir razlučivog broja vrši prema naznačenom pravilu, nazvat će se simpleks transformacija. Dakle, simpleks transformacija se izvodi prema sljedećem pravilu: 1. Odaberite kolonu za omogućavanje koja odgovara najmanjem negativnom elementu u Z - redu. 2. Odabire se red za razrješenje koji odgovara najmanjem pozitivnom omjeru elemenata desne strane jednadžbe prema odgovarajućim elementima kolone za razrješenje. Na presjeku kolone za rješavanje i reda za razrješenje nalazi se broj za razrješenje. 3. Elementi dopuštenog niza podijeljeni su brojem dopuštenja. 4. Elementi svih ostalih redova izračunavaju se prema formuli: Iz sistema (1.4) nalazimo drugo dopustivo osnovno rješenje H2 = Yl = 0; X1 = 25; Y2 = 42; Y3 = 258, što odgovara novoj povećanoj vrijednosti funkcije Z = 250. Dakle, proces uzastopnih simpleks transformacija je proces sukcesivnog poboljšanja rješenja. pri čemu: 1. Ako postoji barem jedan negativan element u Z - liniji i a) postoji barem jedan pozitivan element u koloni za razrješenje, tada se rješenje može poboljšati; b) ako kolona za razrješenje ne sadrži pozitivne elemente, tada funkcija Z raste beskonačno. 2. Ako su svi elementi u Z - redu nenegativni, tada je postignuto optimalno rješenje. Ovo su dovoljni uslovi za postojanje plana optimalnog rešenja. U sistemu (1.4), koeficijent na X2 u Z - redu je negativan, tako da će druga kolona biti razrješava. Smatramo da će druga linija biti dopuštena. Zatim izvodimo simpleks transformaciju sistema (1.4) prema naznačenom pravilu: X1 + 8/42 Y1 - 5/42 Y2 = 20, X2 - 1/3 Y1 + 1/3 Y2 = 14, 20/7 Y1 - 23/7 Y2 + Y3 = 120, 10/42 Y1 + 20/42 Y2 + Z = 270, (1,5) Pošto su svi elementi u Z-redu nenegativni, ovaj plan je optimalan. U ovom slučaju, Yl = Y2 = 0; X1 = 20; X2 = 14 i Zmax = 270. Izvođenje simpleks transformacija povezano je s mukotrpnim i često prilično glomaznim proračunima. Ovi proračuni se mogu uvelike pojednostaviti korištenjem takozvanih simpleks tablica za rješavanje problema. Svaka simpleksna transformacija sistema se svodi na prijelaz iz jednog simpleksnog prikaza u drugi. Prema originalnom sistemu jednačina (1.3) sačinjavamo prvu simpleks tablicu (tabela 1.1). Tabela 1.1 Prvi stupac je stupac osnovnih varijabli, drugi stupac sadrži slobodne koeficijente desne strane jednadžbi (1.3), prvi red sadrži sve varijable, posljednji stupac je kontrolni stupac i koeficijenti u njemu su jednaki zbir svih koeficijenata u redu. Iz tabele. 1.1 imamo prvo dopušteno rješenje sistema (1.3) X1 = X2 = 0, Y1 = 350, Y2 = 392, Y3 = 408, Z = 0, što odgovara vrhu O (0,0) poligona izvodljivih rješenja OABCD (slika 1). Prelazak na drugu simpleks tabelu (tabela 1.2) vrši se prema pravilu navedenom u ovom paragrafu za simpleks transformacije sistema jednačina, dok rezoluciona varijabla X1 ide u bazu umjesto razlučujuće varijable Y1. 1.2. Tabela 1.2 Nakon popunjavanja tabele 1.2 potrebno je provjeriti ispravnost njegovog popunjavanja, za šta koeficijent sumiramo po redovima i taj zbir mora biti jednak koeficijentima u odgovarajućim ćelijama kontrolne kolone. Iz tabele. 1.2 drugo važeće rješenje bi bilo X1 = 25, X2 = 0, Y1 = 0, Y2 = 42, Y3 = 258 i Z = 250. Lako je vidjeti da ova tabela odgovara sistemu (1.4) i referentnom rješenju X1 = 25, X2 = 0 odgovara vrhu D(25,0) poligona rješenja. Budući da u Z-redu postoji negativan element, poboljšavamo rješenje, za što sastavljamo simpleks tablicu. 1.3. Tabela 1. 3
* Bilješka. Radi jednostavnosti proračuna, treba imati na umu da se u novoj tabeli, umjesto elemenata kolone koja dozvoljava (osim elementa koji dozvoljava), nalaze nule. Ako postoje nule u redu za rješavanje, tada se odgovarajuće kolone prenose u novu tablicu bez promjene: Budući da u Z - liniji nema negativnih elemenata, ovo rješenje će biti optimalno. Tab. 1.3 odgovara sistemu jednadžbi (1.5) i optimalnom rješenju H1 = 20, X2 = 14 i Zmax = 270 i vrh C (20,14) poligona dopuštenih rješenja OABCD. Ovakve izdužene tabele koje sadrže sve varijable u prvom redu, zahvaljujući prisustvu kontrolne kolone, omogućavaju vam da kontrolišete ispravnost popunjavanja tabela i izbegnete aritmetičke greške. Simpleksna metoda zasnovana na skraćenim tabelama Razmotrimo sistem jednačina (1.3) i zapišemo ga u obliku tabele 1.4 Tabela 1.4 U prvu kolonu upisujemo osnovne varijable (BP), a u prvi red slobodne varijable (SP). Zatim se vrši prelazak na novu tabelu 1.5 prema pravilu: 1) zamijeniti SP i BP 2) umjesto elementa za razrješenje postoji vrijednost recipročna njemu 3) elemente razlučivačke linije dijelimo rezolutivnim brojem 4) podijelimo elemente razrješivača kolonom za razrješenje i promijenimo predznak 5) preostali elementi se nalaze kao u poglavlju „Pronalaženje maksimuma linearne funkcije“, pravilo 4 (pravilo pravougaonika za OGI). Dobijamo tabelu 1.5. Tabela 1.6 Dobili smo optimalni plan Zmax = 270 sa X1 =20, X2 = 14, a ispostavilo se da su sredstva opreme viška u iznosu od 120 mašinskih sati. Rješavanje problema linearnog programiranja Pronađite maksimalnu funkciju cilja pod ograničenjima 14x + 5y ≤ 350 Rješavanje problema pomoću programa Microsoft Excel. Dodijelimo A3 i B3 vrijednostima varijabli x i y. U ćeliju C4 unesite funkciju cilja U ćelije A7:A9 uvodimo lijevi dio ograničenja a u ćelijama B7:B9 - desni dijelovi ograničenja. Nakon toga odaberite naredbu Servis, Pronalaženje rješenja(Alati, Solver) i popunite dijaloški okvir koji se otvara Pronalaženje rješenja ( Solver) kao što je prikazano na sl. 2. Nakon pritiska na dugme Trči Otvara se prozor (Reši). Rezultati pretrage rješenja(Solver Results), koji javlja da je rješenje pronađeno (slika 3). Rice. 2. Pronalaženje rješenja Rice. 3. Rezultati potrage za rješenjem Geometrijsko rješenje zadatka korištenjem programa MATHCAD 2000. 14x + 5y = 350 (-14/5)x + 70 y1(x):= (-14/5)x + 70 7x + 4y = 196 (-7/4)x + 49 y2(x):= (-7/4)x + 49 x + 2y = 68 (-1/2)x + 34 y3(x):= (-1/2)x + 34 10x + 5y = C -2x + (1/5)C y4(x):= -2x + (1/5)C Rice. 4. Nađi (x, y) → (20, 14) f(x, y): = 10x + 5y fmin := f(20, 14) Analitičko rješenje problema pomoću programa MATHCAD 2000. Analitičko rješenje problema u MathCAD-u je mnogo jednostavnije. Z(x, y): = 10x + 5y 14x + 5x ≤ 360 M:=Maksimiraj(z,x,y) M=(20,14)Z(M0,M1)=270 Problem maksimiziranja linearne funkcije u prisustvu negativnih slobodnih koeficijenata Pronađite maksimum linearne funkcije pod ograničenjima X1 – X2 ≤ 3, 2X1 – 3X2 ≤ 6, X1 ≥ 0, X2 ≥ 0. Sistem zapisujemo u formu Y1 = -X1 + X2 + 3 ≥ 0 Y2 = X1 + X2 - 5 ≥ 0 Y3 = -2X1 + 3X2 + 6 ≥ 0 Y4 = -X2 + 6 ≥ 0 Hajde da napravimo sto. Nastavljamo raditi s 2. redom, jer negativni element nije nestao. Izrađujemo SHMZhI sa elementom za razrješenje -2. Dobijamo sto. Problem minimizacije linearne funkcije Svođenje problema minimizacije na problem maksimizacije linearne funkcije Razmatrali smo rješenje problema pronalaženja maksimuma linearne funkcije simpleks metodom W = c1 x1 + c2 x2 + … + cn xn. Međutim, u mnogim ekonomskim problemima potrebno je pronaći minimum linearne funkcije. Za ovo je dovoljno staviti W = -Z = -c1 x1 - c2 x2 - ... - cn xn i riješiti problem maksimiziranja rezultujuće funkcije W pod odgovarajućim ograničenjima. Pošto je to jasno Minimizirajte linearnu funkciju uz ispunjavanje ograničenja 7X1 + 2X2 ≥ 14, 5X1 + 6X2 ≤ 30, 3X1 + 8X2 ≥ 24, X1 ≥ 0, X2 ≥ 0. Geometrijsko rješenje zadatka na (sl. 5) i odgovara optimalnom rješenju u tački C (48/11, 15/11) i istovremeno Zmin = -21/11. Slika 5. Geometrijsko rješenje problema Uvodeći varijable nivelmana Yi ≥ 0 i funkciju W = -Z = 2X1 - 5X2 → max, zapisujemo problem u obliku. Y1 = 7X1 + 2X2 - 14, Y2 = -5X1 - 6X2 + 30, Y3 = 3X1 + 8X2 - 24, Ovaj sistem zapisujemo u obliku tabele. Riješimo se negativnog slobodnog člana u Y1 - liniji, čineći SHMZhI sa elementom za razrješenje “-50/8”, dobivamo tablicu. Kako nema negativnih elemenata u W - redu i u 1 - koloni, dobili smo optimalno rješenje X1 = 48/11, X2 = 15/11, Wmax - 21/11 ili Zmin = -Wmax = -21/11 , Praktični dio 1.
Riješite problem korištenjem simpleks metode. X1 + 3X2 ≤ 300 F = 2X1 + 3X2 → max Rješenje X1 + 3X2 + X3 = 300 F - 2X1 - 3X2 = 0 X1 + X2 + X4 = 150 Odgovor: X1 = 75; X2 = 75; X3 = 0; X4 = 0. Zadatak broj 1. Kompanija proizvodi dvije vrste proizvoda. Vrste sirovina, njihove rezerve, stope potrošnje sirovina po k.u. za svaku vrstu proizvoda, proizvodni dobitak od prodaje proizvoda dati su u tabeli. Rješenje 2X1 + 2X2 ≤ 17 X1 + 3X2 + X3 = 20 F - 2X1 - X2 = 0 2X1 + X2 + X4 = 10 2X1 + 2X2 + X5 =17 Odgovor: X1 = 5; X2 = 0; X3 = 15; X4 = 0; X5 = 7. Zadatak broj 2. Kompanija proizvodi tri vrste proizvoda, koristeći tri vrste sirovina. Zalihe sirovina, njihove stope potrošnje i dobit od prodaje svakog proizvoda prikazane su u tabeli. Kako planirati proizvodnju da bi profit preduzeća bio najveći? Rješenje 2X1 + 3X2 + 7X3 ≤ 1250 F = 41X1 + 35X2 + 96X3 → max 5X1 + 3X2 ≤ 900 2X1 + 3X2 + 7X3 + X4 = 1250 F - 41X1 - 35X2 - 96X3 = 0 X1 + X2 + X5 = 250 5X1 +3X2 + X6 = 900 X1 + 3X2 ≤ 20 F = 2X1 + X2 → max 2X1 + 2X2 ≤ 17 (-1/3)(-1/3)(2/3) Odgovor: X1 = 0; X2 = 29/5; X3 = 0; X4 = 13/5; X5 = 0; X6 = 0; X7 = 54/5. Zaključak Zaustavimo se na najjednostavnijim interpretacijama simpleks metode. Algebarsko značenje simpleks metode je da, izvodeći identične algebarske transformacije, prelazimo sa jednog izvodljivog rješenja na sistem algebarskih jednačina na drugo poboljšano, postižući optimalno rješenje problema. Sa geometrijske tačke gledišta, identične transformacije prema simpleks metodi su uzastopna kretanja od jednog vrha konveksnog poligona rješenja do susjednog, od njega do sljedećeg, i tako dalje do optimalnog vrha duž stranica ovog poligona . Ekonomska suština simpleks metode leži u činjenici da je riječ o metodi sukcesivnog poboljšanja rješenja. Ova metoda omogućava, nakon odabira polazne tačke – osnovnog plana akcije, da se postepeno ide naprijed i na kraju postigne optimalan plan, ako, naravno, postoji. Simpleks je konveksan poligon u n-dimenzionalnom prostoru sa n + 1 vrhova koji ne leže na istoj hiperravni. Simpleksi su odvojeni u posebnu klasu jer je simpleks najjednostavniji poligon koji sadrži neki volumen n-dimenzionalnog prostora. Dokazano je da ako postoji optimalno rješenje, onda će se ono nužno naći nakon konačnog broja koraka (s izuzetkom tzv. „degeneriranog problema”, u kojem se pojavljuje fenomen „cikliranja”, tj. višestrukog povratka na istu poziciju, moguće). Linearno programiranje je oblast matematičkog programiranja posvećena teoriji i metodama za rešavanje ekstremnih problema koje karakteriše linearni odnos između varijabli. Matematičko programiranje (optimalno programiranje) je grana matematike koja kombinuje različite matematičke metode i discipline: linearno programiranje, dinamičko programiranje, konveksno programiranje itd. Opšti zadatak matematičkog programiranja je pronalaženje optimalne (maksimalne ili minimalne) vrednosti cilja. funkciju, a vrijednosti varijabli moraju pripadati nekom rasponu prihvatljivih vrijednosti. Spisak korišćene literature 1) A. S. Shapkin, N. P. Mazaeva; Matematičke metode i modeli istraživanja operacije, 2005. 2) N.Sh. Kremer, B.A. Putko, I.M. Trišin, M.N. Friedman; Istraživanje operacija u ekonomija. - UNITI, 2002. Za korištenje pregleda prezentacija, kreirajte Google račun (nalog) i prijavite se: https://accounts.google.com Rješavanje najjednostavnijih zadataka linearnog programiranja grafičkom metodom 17.04.2012. Ako se sistem ograničenja problema linearnog programiranja predstavi kao sistem linearnih nejednačina sa dvije varijable, onda se takav problem može riješiti geometrijski. Zadatak. Postoji 14 radio relejnih kanala (RRC) i 9 troposferskih kanala. Na njih je potrebno prenijeti informacije 3 vrste: A, B, C. Štaviše, informacija A je jednaka 600 USD, B - 3000 USD, C - 5500 USD. (Informacija se može shvatiti kao broj telefonskih razgovora, prijenos podataka itd.). Mogućnosti kanala i troškovi održavanja za svaki kanal dati su u tabeli. Potrebno je pronaći uključeni broj kanala oba tipa, neophodnih za prenos traženih informacija, kako bi troškovi rada bili minimalni. Vrste informacija Komunikacijski kanali Potrebna količina informacija, k.u. Tropospheric RRS A 80 40 600 V - 1000 3000 C 300 800 5500 Troškovi održavanja jednog kanala, rub. 3000 2000 Faze rješavanja LLP-a: Izgradite ODR. Izgradite vektor gradijenta ciljne funkcije u nekoj tački X 0 koja pripada ODR - (c 1 ;c 2) . Konstruirajte pravu c 1 x 1 + c 2 x 2 = h, gdje je h bilo koji pozitivan broj, poželjno takav da nacrtana linija prolazi kroz poligon rješenja. Pomičite pronađenu liniju paralelno sa sobom u smjeru vektora gradijenta sve dok linija ne napusti ODR (kada tražite maksimum) ili u suprotnom smjeru (kada tražite minimum). U graničnoj tački ciljna funkcija dostiže maksimum (minimum) ili se uspostavlja neograničenost funkcije na skupu rješenja. Odredite koordinate maksimalne (minimalne) tačke funkcije i izračunajte vrijednost funkcije u ovoj tački. Ovaj razvoj se može koristiti kao generalizujući čas na temu "Sistemi nejednakosti sa dve varijable" u 9. razredu (algebra 9, priredio Telyakovsky) i kao čas ponavljanja na ovu temu u 10. razredu. ... Materijal je namijenjen naprednim studentima. program razmatra algoritam za sastavljanje osnovnih i referentnih dijagrama različitim metodama i pronalaženje optimalnog rješenja... Radnu svesku za čas matematike na temu "Problemi linearnog programiranja" izradio sam za istoimeni čas matematike (napredni nivo). može se koristiti i u učionici, seminaru... Donošenje odluka pod neizvjesnošću Ako prvi subjekt ima m strategija, a drugi ima n strategija, onda kažemo da imamo posla sa m x n igrom. Razmotrimo igru m x n. Neka je zadan skup strategija: za prvog igrača (Ai), za drugog igrača (Bj), matrica isplate, gdje je aij dobitak prvog igrača ili gubitak drugog igrača kada odaberu strategije Ai i Bj, respektivno. Svaki od igrača jedinstveno bira sa vjerovatnoćom I neku strategiju, tj. koristi čistu strategiju pri odabiru rješenja. U ovom slučaju, rješenje igre će biti u čistim strategijama. Pošto su interesi igrača suprotni, prvi igrač nastoji da maksimizira svoj dobitak, a drugi igrač, naprotiv, da minimizira svoj gubitak. Odluka igre je odrediti najbolju strategiju za svakog igrača. Izbor najbolje strategije od strane jednog igrača vrši se u potpunom odsustvu informacija o odluci drugog igrača.
Linearno programiranje
Primjeri zadataka koji se svode na PAP.
1. Zadatak optimalne alokacije resursa.
Primjeri
Primjer 2
Rješenje
Problem sa mešavinom.
Table
Rješenje
Ekonomsko-matematički model problema.
Zadatak rezanja
Glavni zadatak LP-a
Naslovi slajdova:
Na temu: metodološke izrade, prezentacije i bilješke
Učitavanje...