UVOD
UVOD U METODE OPTIMIZACIJE
2. TEMELJI TEORIJE OPTIMIZACIJE
2.1 Mogućnosti plana
2.2 Ciljna funkcija (plan)
3. FUNKCIJA JEDNE VARIJABLE
3.1 Definicija funkcije jedne varijable i njezina svojstva
3.2 Funkcija istraživanja u gospodarstvu. Pronalaženje maksimalnog profita
3.3 Definicija globalnog ekstremuma
3.4 Konveksnost, konkavnost funkcije
3.5 Kriterij optimalnosti
3.6 Identifikacija optimuma
4. JEDNODIMENZIONALNA OPTIMIZACIJA
4.1 Metode eliminacije razmaka
4.1.1 Metoda skeniranja
4.1.2 Metoda bisekcije
4.1.3 Metoda zlatnog reza
4.1.4. Usporedne karakteristike metoda za uklanjanje intervala
4.2 Metode polinomske aproksimacije i točkaste estimacije
4.2.1 Metoda parabolične aproksimacije
4.2.2 Puell metoda
4.3 Usporedba metoda jednodimenzionalnog pretraživanja
5. FUNKCIJE VIŠE VARIJABLI
5.1 Funkcije više varijabli, njihova oznaka i opseg
5.2 Neke multivarijatne funkcije koje se koriste u ekonomiji
5.3 Parcijalne derivacije funkcija više varijabli
5.4 Ekonomsko značenje parcijalnih derivacija
5.5 Više parcijalne derivacije
5.6 Svojstva funkcije više varijabli
5.7 Derivacija s obzirom na smjer. Gradijent. Linije razine značajki
5.8 Ekstrem funkcije više varijabli
6. MULTIDIMENZIONALNA OPTIMIZACIJA BEZ UVJETA GRADIJENTA
6.1 Pojam metoda
6.2 Metoda gradijentnog spuštanja
6.3 Metoda najvećeg spuštanja
7. KRITERIJI OPTIMALNOSTI U PROBLEMIMA S OGRANIČENJIMA
7.1 Problemi s ograničenjima u obliku jednakosti
7.2 Lagrangeovi multiplikatori
7.3 Ekonomska interpretacija Lagrangeovih multiplikatora
7.4 Kuhn-Tuckerovi uvjeti
7.4.1 Kuhn-Tuckerovi uvjeti i Kuhn-Tuckerov problem
7.5 Kuhn-Tuckerovi teoremi
7.6 Uvjeti za postojanje sedlaste točke
8. MODELI DINAMIČKOG PROGRAMIRANJA
8.1 Predmet dinamičkog programiranja
8.2 Izjava problema dinamičkog programiranja
8.3 Načelo optimalnosti i matematički opis procesa dinamičkog upravljanja
8.4 Opća shema primjene metode dinamičkog programiranja
8.5 Dvodimenzionalni model raspodjele resursa
8.6. Diskretni dinamički model optimalne alokacije resursa
8.7 Odabir optimalne strategije nadogradnje hardvera
8.8 izbor optimalne rute za prijevoz robe
8.9 Konstrukcija optimalnog slijeda operacija u komercijalne djelatnosti
PRAVILA ZA PROVEDBU I UPIS RAČUNSKOG I GRAFIČKOG ZADATKA
RAČUNSKI I GRAFIČKI ZADATAK 1
RAČUNSKI I GRAFIČKI ZADATAK 2
RAČUNSKI I GRAFIČKI ZADATAK 3
KNJIŽEVNOST
UVOD
Matematizacija raznih područja znanja trenutno nije novost. Rašireno uvođenje matematičkih metoda u najrazličitija područja djelovanja danas više nikoga ne iznenađuje. Nije samo tehnički i ekonomske znanosti, gdje te metode već odavno donose plodove, ali i razne primijenjene znanosti o upravljanju koje se sada razvijaju: menadžment, upravljačko odlučivanje, socio-ekonomsko predviđanje itd.
Primijenjene znanosti razvijaju se na svoj način, koristeći postojeći matematički aparat za rješavanje novonastalih problema, pa čak i vlastitim potrebama potiču razvoj pojedinih grana matematike.
Ovaj priručnik namijenjen je studentima ekonomskih specijalnosti koji studiraju optimizacijske metode. Budući da je za uspješnu asimilaciju gradiva u ovom kolegiju potrebno određeno minimalno poznavanje problematike viša matematika, priručnik ističe ove točke. Materijal je popraćen relevantnim ekonomskim primjenama. Tamo gdje su primjene u ekonomiji od samostalnog interesa, izdvojene su u posebne dijelove.
Udžbenik ne zamjenjuje postojeće akademske udžbenike koji su posvećeni matematičkim aspektima računalnih metoda. Glavni zadatak je upoznati se s računalnim metodama kao alatom za rješavanje problema, dobiti jasnu predodžbu o logičkoj strukturi prikazanih metoda, kao i njihovim komparativnim prednostima i nedostacima.
Pri radu s priručnikom student se najprije upoznaje s teoretskim gradivom, zatim proučava praktični dio koji se nalazi odmah iza teorijskog dijela u svakom dijelu. Svako poglavlje sadrži kontrolna pitanja na kojima učenik može vježbati samokontrolu. Nakon toga student pristupa izradi kontrolnog zadatka predviđenog programom. Zatim test poslan na pregled. Ako recenzent otkrije pogreške, otkrije nedostatke u znanju, preporuča se ponovno vratiti na relevantne odjeljke i ponovno proći kroz materijal dok se u potpunosti ne usvoji.
Edukativno-praktični vodič za sustav obrazovanja na daljinu iz discipline "Optimizacijske metode i teorija upravljanja" namijenjen je samostalan rad student u nestacionarnom obliku kontrole znanja.
U okviru discipline studenti tijekom petogodišnjeg studija rade tri računsko-grafička zadatka, studenti koji studiraju 3,5 godine rade dva računsko-grafička zadatka - drugi i treći. Rješavanje sličnih problema razmatra se u teoretskom i praktičnom dijelu priručnika.
Nakon odslušanog kolegija studenti polažu test. Pitanja za testiranje sastavljena su na temelju kontrolnih pitanja navedenih na kraju svakog dijela priručnika.
Poglavlje 1. UVOD U METODE OPTIMIZACIJE
Pojam "optimizacija" ima vrlo široku upotrebu i stoga može ovisiti o kontekstu. Optimalno (od lat. optimum - najbolji) - skup najpovoljnijih uvjeta; najbolja opcija za rješavanje problema ili način postizanja cilja u danim uvjetima i resursima. Ekonomski optimum u širem smislu - najučinkovitije funkcioniranje proizvodnje, u užem smislu - najbolje korištenje materijalnih sredstava, čime se postiže najveći mogući proizvodni učinak ili mogući minimalni trošak.
Optimizacija- to je proces izbora najbolje opcije ili proces dovođenja sustava u najbolje (optimalno) stanje, koji se sastoji u pronalaženju svih maksimizirajućih ili minimizirajućih elemenata ili sedlišnih točaka. Optimizacija je u srži ekonomske analize. U pasivnim ekonomskim modelima (poput onih koji proučavaju opću ravnotežu), zanima nas optimalno ponašanje donositelja odluka. U aktivnim modelima (kao što su modeli učinkovitog rasta) sami smo zainteresirani za postizanje optimuma. Posljednjih godina postoji trend prelaska s input-output modela na modele analize. proizvodni procesi, od najjednostavnijih modela rasta do modela koji proučavaju putanje optimalnog i učinkovitog rasta.
Metode optimizacije– metode za pronalaženje ekstrema funkcije (u praktičnim problemima, kriteriji optimalnosti) sa ili bez ograničenja vrlo su široko korištene u praksi. To je, prije svega, optimalno projektiranje (odabir najboljih nominalnih tehnoloških načina, strukturnih elemenata, strukture tehnoloških lanaca, uvjeta gospodarske aktivnosti, povećanje profitabilnosti itd.), optimalna kontrola izgradnje nematematičkih modela objekata upravljanja. (minimiziranje reziduala raznih struktura modela i stvarnog objekta) i mnoge druge aspekte rješavanja ekonomskih i socijalni problemi(na primjer, upravljanje zalihama, radnim resursima, prometnim tokovima itd.).
Optimizacijske metode su grana matematičkog modeliranja.
Ove teme pokrivaju širok raspon različitih problema matematičkog modeliranja koji se javljaju u proučavanju stvarnih objekata. industrijska proizvodnja, ekonomskih, financijskih i drugih problema.
Model- to je takav materijalni ili misaono prikazan predmet koji u procesu istraživanja zamjenjuje izvorni predmet tako da se njegovim neposrednim proučavanjem dobiva nova spoznaja o izvornom objektu.
Da bi se matematički rezultati i numeričke metode optimizacijske teorije mogli koristiti za rješavanje specifičnih problema, potrebno je:
postaviti granice sustava koji se optimizira;
odrediti kvantitativni kriterij na temelju kojeg je moguće analizirati opcije kako bi se identificirala "najbolja";
· napraviti izbor unutarsustavnih varijabli koje se koriste za određivanje karakteristika i identificiranje opcija;
· izgraditi model koji odražava odnos između varijabli.
Ovaj slijed radnji čini sadržaj proces postavljanja optimizacijskog problema .
Pogledajmo neke od praktične aktivnosti probleme matematičkog modeliranja u smislenoj, a ne u formalnoj matematičkoj interpretaciji.
Problemi optimalne raspodjele resursa. Općenito, ti se zadaci mogu opisati na sljedeći način. Postoji niz resursa, koji se mogu shvatiti kao unovčiti, materijalna sredstva(primjerice sirovine, poluproizvodi, radna snaga, razne vrste opreme itd.). Ti resursi moraju biti raspodijeljeni između različitih objekata njihovog korištenja za odvojena vremenska razdoblja ili za različite objekte kako bi se dobila maksimalna ukupna učinkovitost odabranog načina raspodjele. Indikator učinkovitosti može biti, na primjer, profit, tržišni output, kapitalna produktivnost (problemi maksimiziranja kriterija optimalnosti) ili ukupni troškovi, trošak, vrijeme za dovršetak zadane količine posla itd. (problemi minimiziranja kriterija optimalnosti).
Postoji početni iznos sredstava P 0, koji se mora raspodijeliti na P godine između S poduzeća. Fondovi i ki (k = 1,...,n; i = 1,...,S) istaknuto u k-ti godina i-ti poduzeću generirati prihod u iznosu f ki (u ki) a do kraja godine vratiti količinski j ki (u ki). U naknadnoj raspodjeli dohodak može sudjelovati (djelomično ili potpuno) ili ne sudjelovati.
Potrebno je utvrditi takav način raspodjele sredstava (količina sredstava koja se izdvajaju za svako poduzeće u svakoj planskoj godini) da ukupni prihod od S poduzeća za P godine bio maksimum. Stoga, kao pokazatelj učinkovitosti procesa raspodjele resursa za P godina, ukupan prihod ostvaren od S poduzeća:
Broj resursa na početku k-ti godine karakterizirat će vrijednost P n 1(parametar stanja). Upravljanje uključeno k-volumen korak se sastoji u odabiru varijabli u k 1 , u k 2 , …, u ks označava resurse alocirane u k-volumen godina i-ti poduzeće.
Ako pretpostavimo da dohodak ne sudjeluje u daljnjoj raspodjeli, tada jednadžba stanja procesa ima oblik
Ako, pak, određeni dio dohotka sudjeluje u daljnjoj raspodjeli u nekoj godini, tada se odgovarajuća vrijednost dodaje desnoj strani posljednje jednakosti.
Obavezno definirati n s nenegativne varijable i ki, zadovoljava uvjete (2) i maksimizirajuću funkciju (1).
Optimalno upravljanje zalihama. Klasa problema u kojoj se razmatra optimalna kontrola zaliha jedna je od najtežih. To je zbog činjenice da se u problemima upravljanja zalihama proces prirodno odvija u vremenu, a kontrola leži u činjenici da se odluka u određenom vremenskom intervalu donosi uzimajući u obzir stanje koje je sustav postigao u prethodnom razdoblju. razdoblja. Osim toga, ti su problemi u pravilu povezani s diskretnom prirodom varijabli i stoga ih je prilično teško riješiti.
Problem upravljanja zalihama jedno je od najvažnijih područja praktične primjene ekonomsko-matematičkih metoda, uključujući i metode matematičkog programiranja.
Pri formuliranju zadataka upravljanja zalihama koriste se sljedeći koncepti.
Dionice - to su sve novčane ili materijalne vrijednosti koje se povremeno nadopunjuju (proizvode, isporučuju i sl.) i pohranjuju neko vrijeme kako bi se potrošile u narednim vremenskim razdobljima. Razina zaliha u bilo kojem trenutku vremena određena je početnom razinom zaliha plus nadopuna i minus potrošnja tijekom vremenskog razdoblja od početnog trenutka do trenutnog.
Upravljanje zalihama općenito se sastoji od utjecaja na odnos između dva glavna čimbenika – nadopune i potrošnje. Cilj upravljanja je optimizirati neki kriterij, ovisno o troškovima držanja zaliha, troškovima zaliha, troškovima povezanim s nadopunjavanjem, kaznama itd.
U takvoj općoj formulaciji, takvi problemi mogu biti najrazličitiji praktičnu upotrebu. Na primjer, zalihe se mogu shvatiti kao proizvodi poduzeća koji se kontinuirano proizvode (nadopuna) i isporučuju potrošačima u određenim odvojenim serijama (trošak). U ovom slučaju, pretpostavlja se da je potražnja za proizvodima unaprijed određena (deterministička potražnja) ili podložna nasumičnim fluktuacijama (stohastički problem). Upravljanje zalihama je odrediti veličinu potrebnog outputa kako bi se zadovoljila određena potražnja. Cilj je minimizirati ukupne troškove skladištenja i obnavljanja zaliha.
Zalihe se mogu shvatiti kao zalihe sirovina ili drugog materijala isporučene u diskretnim serijama (nadopuna), koje moraju osigurati kontinuiranu potrošnju u procesu proizvodnje (potrošnja). Kriterij optimalnosti mogu biti ukupni troškovi skladištenja zaliha, zamrzavanja obrtnih sredstava i nabave zaliha.
Zalihe mogu biti robe koje se u trgovinu isporučuju u određenim serijama i namijenjene su kontinuiranim, ali podložnim nasumičnim fluktuacijama potražnje kupaca. Kriterij optimalnosti su ukupni troškovi zaliha, skladištenje zaliha i promjene u ritmu proizvodnje; vezano uz fluktuacije potražnje.
Zalihe mogu biti i sezonski artikli pohranjeni u skladištu ograničenog kapaciteta. Roba se može kupiti i prodati u različitim količinama po cijenama koje se mijenjaju tijekom vremena. Izazov je definirati politiku kupnje i prodaje koja maksimizira ukupni profit, i primjer je problema sa skladištenjem.
zamjenski zadaci. Jedan od važnih ekonomskih problema s kojim se susreće u praksi je određivanje optimalne strategije zamjene starih strojeva, industrijskih objekata, agregata, strojeva i sl., odnosno stare opreme novom.
Starenje opreme uključuje njezino fizičko i moralno trošenje, što za posljedicu ima povećanje proizvodnih troškova za proizvodnju proizvoda na staroj opremi, povećanje troškova njezina popravka i održavanja, a ujedno i produktivnost i dr. -nazvan pad vrijednosti likvidnosti.
Dođe vrijeme kada je isplativije prodati staru opremu, zamijeniti je novom, nego je eksploatirati po cijeni visoki troškovi. U tom slučaju oprema se može zamijeniti ili novom opremom iste vrste ili novom, naprednijom u tehničkom smislu, uzimajući u obzir tehnički napredak.
Optimalna strategija zamjene opreme je određivanje optimalnog vremena zamjene. Kriterij optimalnosti pri određivanju vremena zamjene može biti ili dobit od rada opreme, koju treba maksimizirati, ili ukupni troškovi rada tijekom razmatranog vremenskog razdoblja, koje treba minimizirati.
Problemi optimalnog upravljanja. Obično ova vrsta zadataka uključuje zadatke koji se odnose na pronalaženje kontinuiranog upravljačkog djelovanja raspoređenog tijekom vremena. U ekonomiji su to prije svega zadaće predviđanja kretanja razvoja, dugoročnih ulaganja itd. potrošnje i dr.
Sve navedene klase problema (a njihova je kompozicija daleko od potpune) za svoje rješavanje zahtijevaju korištenje posebnih matematičkih metoda linearnog i nelinearnog programiranja, dinamičkog programiranja, principa maksimuma i nekih drugih. Sastavni dio računskog rada u rješavanju razmatranih problema mogu biti problemi rješavanja nelinearnih jednadžbi i njihovih sustava, izračunavanja integrala, rješavanja diferencijalnih jednadžbi i sl.
Postoji prilično velik broj numeričkih metoda optimizacije. Glavni mogu klasificirati na sljedeći način:
po dimenziji problema koji se rješava: jednodimenzionalni i višedimenzionalni;
Prema metodi formiranja koraka, višedimenzionalne metode se dijele na sljedeće vrste:
q gradijent:
o prema načinu izračuna gradijenta: s parnim uzorkom i sa središnjim uzorkom;
o prema algoritmu korekcije koraka;
o prema algoritmu za izračunavanje nove točke: jednokorak i višekorak;
q negradijentna: s naizmjeničnom izmjenom varijabli i s istovremenom izmjenom varijabli;
q slučajno pretraživanje: s čisto slučajnom strategijom i s mješovitom strategijom;
Prisutnošću aktivnih ograničenja;
· bez ograničenja (bezuvjetno);
s ograničenjima (uvjetno);
· s ograničenjima tipa jednakosti;
s ograničenjima tipa nejednakosti;
mješoviti.
Jednodimenzionalne metode optimizacije su osnova za neke "višedimenzionalne" metode. U multivarijatnoj gradijentnoj optimizaciji, slijed poboljšanja se gradi ovisno o brzini promjene kriterija u različitim smjerovima. U ovom slučaju, slijed poboljšanja se razumije kao takav slijed x 0, x 1, ..., x i, ..., u svakoj točki od kojih je vrijednost kriterija optimalnosti bolja nego u prethodnoj. U metodama bez gradijenta, veličina i smjer koraka prema optimumu pri konstruiranju slijeda za poboljšanje jedinstveno se oblikuje određenim determinističkim funkcijama ovisno o svojstvima kriterija optimalnosti u blizini trenutne točke bez korištenja derivacija (tj. gradijenta) . Slučajne metode se koriste u visokodimenzionalnim problemima. Multivarijatna uvjetna optimizacija uzima u obzir aktivna ograničenja izražena kao jednakosti i nejednakosti. U svakom od razmatranih pravaca postoji veliki broj metoda koje imaju svoje prednosti i nedostatke, a koji ovise prvenstveno o svojstvima funkcija čiji se ekstremum traži. Jedan od usporedni pokazatelji Kvaliteta metode je broj vrijednosti funkcije koje je potrebno izračunati da bi se riješio problem sa zadanom greškom. Što je taj broj manji, to je metoda učinkovitija, pod ostalim uvjetima.
U teorijskim i matematičkim problemima, uobičajeno je probleme optimizacije smatrati problemima pronalaženja minimuma funkcije. Čak i metode imaju zajedničko ime - metode spuštanja. Međutim, pri rješavanju stvarnih praktičnih problema vrlo često postoje zadaci maksimuma (na primjer, maksimiziranje prihoda, outputa itd.). Naravno, lako je prijeći iz jedne vrste ekstremuma u drugu promjenom predznaka kriterija optimalnosti, ali to se ne radi uvijek u primijenjenim nematematičkim problemima, kako se ne bi izgubila smislena nit problema.
Pitanja za 1. poglavlje
1. Zašto je potrebno koristiti matematiku u ekonomiji?
2. Što je matematički model?
3. Kako se gradi matematički model ekonomske pojave i objekta? Navedite primjer izrade modela.
4. Što je optimizacija?
5. Koje su metode optimizacije?
6. Koji se ekonomski problemi rješavaju optimizacijskim metodama?
Poglavlje 2. TEMELJI TEORIJE OPTIMIZACIJE
termin "optimizacija" označavaju proces koji vodi do rafiniranog rješenja. Iako je krajnji cilj optimizacije pronaći najbolje ili "optimalno" rješenje, obično se moramo zadovoljiti poboljšanjem poznatih rješenja, a ne njihovim usavršavanjem. Stoga je vjerojatnije da će se optimizacija shvatiti kao težnja ka savršenstvu, koje možda neće biti postignuto.
Uzimajući u obzir neki proizvoljni sustav opisan od m jednadžbe sa n nepoznato, postoje tri glavne vrste problema:
· ako m = n, onda h Problem se naziva algebarski. Takav zadatak obično jedina odluka;
· ako m > n, onda se problem redefinira, u pravilu, nema rješenja;
· ako m< n , onda je problem nedovoljno definiran, ima beskonačno mnogo rješenja.
U praksi najčešće imamo posla sa zadacima treće vrste.
Uvedimo nekoliko definicija.
2.1. Mogućnosti plana
Definicija. Mogućnosti plana su neovisno varijabilni parametri koji potpuno i nedvosmisleno definiraju problem koji se rješava.
To su nepoznate veličine čije se vrijednosti izračunavaju tijekom procesa optimizacije. Kao projektni parametri mogu poslužiti bilo koje osnovne ili izvedene veličine koje služe za kvantitativni opis sustava.
Na primjer, vrijednosti duljine, mase, vremena, temperature mogu se smatrati parametrima.
Broj projektnih parametara karakterizira stupanj složenosti danog projektnog problema.
Notacija. Obično se broj parametara dizajna označava s n, x- sami parametri dizajna s odgovarajućim indeksima
x 1, x 2, ..., x n - n projektni parametri zadatka.
2.2. Ciljna funkcija (plan)
Definicija. ciljna funkcija- izraz čiju vrijednost nastojimo učiniti maksimalnom ili minimalnom.
Funkcija cilja omogućuje vam kvantitativnu usporedbu dva alternativna rješenja. S matematičkog gledišta, funkcija cilja opisuje neke (n+1)-dimenzionalna površina.
1) Ako postoji samo jedan parametar dizajna, tada se funkcija cilja može prikazati krivuljom na ravnini (slika 1).
2) Ako postoje dva projektna parametra, tada će funkcija cilja biti predstavljena plohom u trodimenzionalnom prostoru (slika 2).
Definicija. S tri ili više projektnih parametara pozivaju se površine određene funkcijom cilja hiperpovršine i nisu podložni prikazivanju konvencionalnim sredstvima.
Funkcija cilja se u nekim slučajevima može prikazati kao:
komadno-glatka funkcija;
stol
Samo cjelobrojne vrijednosti
dvije vrijednosti - da ili ne (diskretna funkcija).
U kojem god obliku je ciljna funkcija predstavljena, ona mora biti jednovrijedna funkcija projektnih parametara.
U nizu optimizacijskih problema potrebno je uvođenje više od jedne funkcije cilja. Ponekad jedno od njih može biti nekompatibilno s drugim. Primjer je projektiranje zrakoplova, kada se zahtijeva maksimalna snaga, minimalna težina i minimalni trošak u isto vrijeme. U takvim slučajevima projektant mora uvesti sustav prioriteta. Kao rezultat, dobiva se "kompromisna funkcija", koja omogućuje korištenje jedne složene funkcije cilja u procesu optimizacije.
Pitanja za 2. poglavlje
1. Što su opcije plana?
2. Navedite primjere parametara plana.
3. Definirajte funkciju cilja.
4. Kako je prikazana funkcija cilja?
Parametri za zadanu strukturu objekta, tada se ona poziva parametarska optimizacija. Izborni zadatak optimalna struktura je strukturna optimizacija.
Standard matematički problem optimizacija je formulirana na ovaj način. Među elementima χ koji čine skupove X nađite takav element χ * koji daje minimalnu vrijednost f(χ *) zadane funkcije f(χ). Za pravilno postavljanje problema optimizacije potrebno je postaviti:
Zatim riješiti problem znači jedno od:
Ako funkcija koja se minimizira nije konveksna, tada se često ograničavaju na pronalaženje lokalnih minimuma i maksimuma: točaka koje su posvuda u nekim njihovim susjedstvima za minimum i za maksimum.
Ako je skup dopustiv, tada se takav problem naziva problem neograničene optimizacije, inače - problem uvjetne optimizacije.
Klasifikacija metoda optimizacije
Opća notacija optimizacijskih problema definira širok raspon njihovih klasa. Izbor metode (učinkovitost njezina rješenja) ovisi o klasi problema. Klasifikaciju problema određuju: funkcija cilja i dopustivo područje (zadano sustavom nejednakosti i jednakosti ili složenijim algoritmom).
Metode optimizacije klasificiraju se prema zadacima optimizacije:
- Lokalne metode: konvergiraju nekom lokalnom ekstremumu funkcije cilja. U slučaju unimodalne funkcije cilja, ovaj ekstrem je jedinstven i bit će globalni maksimum/minimum.
- Globalne metode: bave se višeekstremnim funkcijama cilja. U globalnom pretraživanju glavni zadatak je identificirati trendove u globalnom ponašanju funkcije cilja.
Trenutno postojeće metode pretraživanja mogu se podijeliti u tri velike skupine:
- deterministički;
- slučajni (stohastički);
- kombinirani.
Prema kriteriju dimenzije dopustivog skupa optimizacijske metode dijelimo na metode jednodimenzionalna optimizacija i metode multivarijatna optimizacija.
Prema obliku funkcije cilja i dopustivog skupa, optimizacijski problemi i metode za njihovo rješavanje mogu se podijeliti u sljedeće klase:
Prema zahtjevima za glatkoćom i prisutnosti parcijalnih derivacija u funkciji cilja, mogu se također podijeliti na:
- izravne metode koje zahtijevaju samo izračun funkcije cilja u točkama aproksimacije;
- metode prvog reda: zahtijevaju izračun prvih parcijalnih izvoda funkcije;
- metode drugog reda: zahtijevaju izračun druge parcijalne derivacije, odnosno Hessian funkcije cilja.
Osim toga, metode optimizacije podijeljene su u sljedeće skupine:
- analitičke metode (na primjer, Lagrangeova metoda multiplikatora i Karush-Kuhn-Tuckerovi uvjeti);
- grafičke metode.
Ovisno o prirodi skupa x Problemi matematičkog programiranja klasificirani su kao:
- problemi diskretnog programiranja (ili kombinatorne optimizacije) – ako x konačan ili prebrojiv;
- problemi cjelobrojnog programiranja – if x je podskup skupa cijelih brojeva;
- problem nelinearnog programiranja ako ograničenja ili funkcija cilja sadrže nelinearne funkcije i x je podskup konačnodimenzionalnog vektorskog prostora.
- Ako sva ograničenja i funkcija cilja sadrže samo linearne funkcije, onda je to problem linearnog programiranja.
Osim toga, grane matematičkog programiranja su parametarsko programiranje, dinamičko programiranje i stohastičko programiranje.
Matematičko programiranje koristi se u rješavanju optimizacijskih problema u operacijskim istraživanjima.
Metoda pronalaženja ekstremuma u potpunosti je određena klasom problema. Ali prije nego što dobijete matematički model, morate izvršiti 4 faze modeliranja:
- Određivanje granica optimizacijskog sustava
- Odbacujemo te veze objekta optimizacije s vanjski svijet, koji ne mogu značajno utjecati na rezultat optimizacije, točnije oni bez kojih je rješenje pojednostavljeno
- Izbor kontroliranih varijabli
- “Zamrzavamo” vrijednosti nekih varijabli (neupravljane varijable). Ostalima ostaje da uzimaju bilo koje vrijednosti iz područja dopuštenih odluka (kontrolirane varijable)
- Definiranje ograničenja na kontrolirane varijable
- … (jednakosti i/ili nejednakosti)
- Odabir numeričkog kriterija optimizacije (na primjer, pokazatelj izvedbe)
- Napravite funkciju cilja
Priča
Kantorovich je zajedno s MK Gavurinom 1949. godine razvio metodu potencijala koja se koristi u rješavanju prometnih problema. U kasnijim radovima Kantorovicha, Nemchinova, V. V. Novozhilova, A. L. Lur'ea, A. Brudna, Aganbegyana, D. B. Yudina, E. G. programiranje i primjena njegovih metoda na proučavanje raznih ekonomskih problema.
Mnogi radovi stranih znanstvenika posvećeni su metodama linearnog programiranja. Godine 1941. F. L. Hitchcock postavio je transportni izazov. Osnovnu metodu za rješavanje problema linearnog programiranja, simpleks metodu, objavio je Dantzig 1949. godine. Metode linearnog i nelinearnog programiranja dalje su razvijene u radovima Kuhna ( Engleski), A. Tucker ( Engleski), Gass (Saul. I. Gass), Charnes (Charnes A.), Beale (Beale E. M.) itd.
Istodobno s razvojem linearnog programiranja, velika se pozornost pridavala problemima nelinearnog programiranja u kojima su ili funkcija cilja, ili ograničenja, ili oboje nelinearni. Godine 1951. Kuhn i Tucker objavili su potrebne i dovoljne uvjete optimalnosti za rješavanje problema nelinearnog programiranja. Ovaj je rad bio temelj za kasnija istraživanja u ovom području.
Od 1955. objavljeni su mnogi radovi o kvadratnom programiranju (radovi Beala, Barankina i Dorfmana (Dorfman R.), Franka (Frank M.) i Wolfea (Wolfe P.), Markowitza i dr.). Dennis J. B., Rosen J. B. i Zontendijk G. razvili su gradijentne metode za rješavanje problema nelinearnog programiranja.
Trenutno su za učinkovitu primjenu metoda matematičkog programiranja i rješavanje problema na računalima razvijeni jezici za algebarsko modeliranje, čiji su predstavnici AMPL i LINGO.
vidi također
Bilješke
Književnost
- Abakarov A. Sh., Sushkov Yu. A. Statistička studija jednog algoritma globalne optimizacije. - Zbornik radova FORA, 2004.
- Akulich I. L. Matematičko programiranje u primjerima i zadacima: Zbornik radova. dodatak za studente ekonom. kućni ljubimci. sveučilišta. - M .: Viša škola, 1986.
- Gill F., Murray W., Wright M. Praktična optimizacija. Po. s engleskog. - M .: Mir, 1985.
- Girsanov I.V. Predavanja na matematička teorija ekstremni zadaci. - M.; Iževsk: Istraživački centar "Regularna i kaotična dinamika", 2003. - 118 str. - ISBN 5-93972-272-5
- Zhiglyavsky A. A., Zhilinkas A. G. Metode za pronalaženje globalnog ekstremuma. - M .: Nauka, Fizmatlit, 1991.
- Karmanov V. G. Matematičko programiranje. - Izdavačka kuća fiz.-mat. Književnost, 2004. (monografija).
- Korn G., Korn T. Matematički priručnik za znanstvenici i inženjeri. - M .: Nauka, 1970. - S. 575-576.
- Koršunov Ju. M., Koršunov Ju. M. Matematičke osnove kibernetike. - M .: Energoatomizdat, 1972.
- Maksimov Yu.A., Filippovskaya E.A. Algoritmi za rješavanje problema nelinearnog programiranja. - M .: MEPHI, 1982.
- Maksimov Yu. A. Algoritmi za linearno i diskretno programiranje. - M .: MEPHI, 1980.
- Plotnikov A.D. Matematičko programiranje = ekspresni tečaj. - 2006. - S. 171. - ISBN 985-475-186-4
- Rastrigin L. A. Metode statističkog pretraživanja. - M., 1968.
- Hemdy A. Taha. Uvod u operacijska istraživanja = Operations Research: An Introduction. - 8. izd. - M .: Williams, 2007. - S. 912. - ISBN 0-13-032374-8
- Keaney R. L., Raifa H. Odlučivanje prema više kriterija: preferencijama i zamjenama. - M .: Radio i komunikacije, 1981. - 560 str.
- S.I. Zukhovitsky, L.I. Avdeeva. Linearno i konveksno programiranje. - 2. izdanje, revidirano. i dodatni .. - M .: Izdavačka kuća "Nauka", 1967.
Linkovi
- B.P. Pol. Povijest matematičkog programiranja u SSSR-u: analiza fenomena // Zbornik radova 14. Bajkalske škole-seminara "Metode optimizacije i njihova primjena". - 2008. - T. 1. - S. 2-20.
| Metode optimizacija | |
|---|---|
| Jednodimenzionalni | Metoda zlatnog reza Metoda dihotomije Parabole Pretraživanje mreže Fibonaccijeva metoda Ternarno pretraživanje |
| Izravne metode | Gaussova metoda Nelder-Meadova metoda Hook-Jeevesova metoda Metoda konfiguracije Rosenbrockova metoda |
| Prva narudžba | Gradijentni spust Zeutendijkova metoda Koordinatni spust Metoda konjugiranog gradijenta Kvazi-Newtonove metode Levenberg-Marquardtov algoritam |
| druga narudžba | Newtonova metoda Newton-Raphsonova metoda |
| Stohastički | Monte Carlo metoda Simulirano žarenje Evolucijski algoritmi Diferencijalna evolucija Algoritam kolonije mrava Metoda roja čestica |
| Linearne metode programiranje |
Simpleksna metoda Gomoryjev algoritam Metoda elipsoida Metoda potencijala |
| Metode nelinearne programiranje |
Sekvencijalno kvadratno programiranje |
Zaklada Wikimedia. 2010. godine.
UDK 711.4 Mazaev A. G
Optimizacijske metode i kriteriji u modernoj teoriji naseljavanja
Članak se bavi konceptom optimizacije u urbanističkom planiranju. Prikazano je podrijetlo pojma "optimizacija", njegova povezanost s glavnim pojmovima iz područja metodologije znanosti, a posebno ekonomije. Prikazane su mogućnosti daljnjeg razvoja koncepta optimizacije u urbanističkom planiranju. Kao zaključak, predlaže se skup kriterija optimizacije u primjeni na urbanističko planiranje.
Ključne riječi: optimizacija u urbanom planiranju, teorija optimizacije, kriteriji i metode optimizacije, Pareto kriterij.
METODE I KRITERIJI OPTIMIZACIJE U SUVREMENOJ TEORIJI NASELJAVANJA
U članku se razmatra koncept urbanističke optimizacije. Prikazuje se podrijetlo pojma optimizacija, njegova povezanost s temeljnim pojmovima iz područja metodologije znanosti, gospodarstva. Razmatraju se mogućnosti razvoja koncepta optimizacije u suvremenom urbanističkom planiranju. Ponuđen je skup kriterija optimizacije koji je moguć u suvremenoj urbanističkoj djelatnosti.
Ključne riječi: optimizacija u urbanističkom planiranju, teorija optimizacije, oriterij i metode optimizacije, Paretov kriterij.
Mazaev Anton
Grigorijevič
Kandidat arhitekture, savjetnik RAASN-a, voditelj. laboratorij Podružnice Savezne državne proračunske ustanove "TsNIIP Ministarstva graditeljstva Rusije" UralNIIproekt
e-mail: [e-mail zaštićen]
Svrha ovog članka je prikazati teoretsko razmatranje pojma "optimizacija" u odnosu na urbane objekte - gradove i sustave naselja. Optimizacija naseljavanja velike regije Rusije na primjeru Urala federalni okrug predmet je znanstvenog istraživanja autora. Relevantnost ove teme povezana je s hitnim pitanjem racionalizacije razvoja regionalnih sustava naselja Nacionalnog sustava Rusije, čiji je razvoj poprimio nekontroliran i neravnotežan karakter. Metodologija obrade teme temelji se na trenutno formiranoj teoriji geopolitičkog razvoja naselja.
Pojam optimizacije u suvremenoj znanosti
Potrebno je razjasniti pojam optimizacije u teoriji znanosti, a zatim ga definirati u odnosu na teoriju naseljavanja. U početku je pojam "optimizacija" nastao u matematici: "Optimizacija - u matematici, informatici i operacijskim istraživanjima, problem pronalaska ekstrema (minimuma ili maksimuma) objektivne funkcije u određenom području konačnodimenzionalnog vektorskog prostora, ograničen skupom linearnih i/ili nelinearnih jednakosti i/ili nejednakosti. Proučavaju se teorija i metode rješavanja optimizacijskog problema
matematičko programiranje ... (It) se bavi matematičkim metodama za rješavanje problema pronalaženja najbolje opcije od svih mogućih ” . Velika sovjetska enciklopedija pojašnjava: “Optimizacija je proces pronalaženja ekstremuma (globalnog maksimuma ili minimuma) određene funkcije ili odabira najbolje (optimalne) opcije iz niza mogućih. Najpouzdaniji način pronalaska najbolje opcije je usporedna procjena svih mogućih opcija (alternativa). Drugim riječima, može postojati mnogo kriterija optimizacije za isti fenomen, sustav. Možete optimizirati bilo što i prema značajnom broju kriterija optimizacije. Štoviše, ti kriteriji mogu biti u međusobnom sukobu, a za optimizaciju ih je potrebno odrediti, inače će se rješenje optimizacijskog problema pokazati netočnim, odnosno lažnim, opasnim i neučinkovitim. Izvori različito tumače sadržaj optimizacije, na temelju ciljeva i zadataka pojedine znanstvene discipline. Primjerice, ekonomski rječnik tumači ovaj pojam na sljedeći način: „Optimizacija je definiranje vrijednosti ekonomskih pokazatelja pri kojima se postiže optimum, odnosno optimalno, najbolje stanje sustava. Najčešće, optimum odgovara postizanju najvećeg rezultata uz dani utrošak resursa.
ili postizanje zadanog rezultata uz minimalne troškove resursa. Drugim riječima, optimizacija je povezana s troškovima resursa i učinkovitošću njihovog korištenja.
Pojam optimizacije u ekonomskoj teoriji
Upravo se u ekonomiji pitanja optimizacije najčešće postavljaju kao hitan znanstveni i praktični problem. U okviru ekonomskih teorija razvila se razvijena teorija optimizacije, a ekonomija i teorija naseljavanja imaju sličan predmet proučavanja - društvo u cjelini, njegove ekonomske potrebe, s tom razlikom što se teorija naseljavanja bavi prostorni aspekt ljudskog života.
Ekonomisti daju veliki broj definicija optimizacija, koje se mogu proširiti na pitanja teorije poravnanja. „Optimizacija – maksimiziranje ekonomske dobrobiti društva u odnosu na makroekonomske ciljeve“. Iz ovoga možemo izvesti shvaćanje optimizacije kao povećanja određenog resursa, koji se poistovjećuje s dobrom. NA ovaj slučaj govorimo o ekonomskom blagostanju kao ključnom dobru, a optimizacija nije povezana s postizanjem optimalne vrijednosti ili skupa vrijednosti, već neograničenim povećanjem tog dobra.
Najopširniju i najdublju definiciju optimizacije dao je svojedobno V. Pareto: “... Svaka promjena koja nikome ne nanosi štetu i koja nekima ide u korist (prema njihovoj vlastitoj procjeni) je poboljšanje.” Ovaj kriterij ima vrlo široko značenje: koristi se u rješavanju takvih problema kada optimizacija znači poboljšanje nekih pokazatelja, pod uvjetom da se drugi ne pogoršavaju, kao i onih kada se primjenjuje kompozicijski pristup za izradu plana razvoja gospodarskog sustava. koja vodi računa o interesima svojih sastavnih podsustava (grupa gospodarskih subjekata). Gornja se definicija može formalizirati sljedećom tvrdnjom: stanje gospodarstva S* smatra se boljim, prema V. Paretu, od drugog stanja B1, ako barem jedan gospodarski subjekt preferira S*, a svi ostali, barem , ne razlikuju ova stanja, ali u isto vrijeme nema nikoga tko preferira 81; prema V. Paretu, stanje 8* je ravnodušno prema stanju B1, ako ih svi gospodarski subjekti ne razlikuju; konačno, optimalno je ako ne postoji moguće stanje gospodarstva koje je bolje od ovoga. V. Paretov kriterij optimalnosti od velike je metodološke važnosti jer daje razumijevanje koje se promjene u gospodarskom sustavu mogu nazvati pozitivnima, tj. usmjerene na njegovo opće poboljšanje, a koje ne. Rast ekonomskog blagostanja jednih subjekata na račun drugih ne može se smatrati pozitivnim prema ovom kriteriju. Ilustracija 1 prikazuje učinak V. Pareto kriterija u obliku grafikona, koji prikazuje područje "prihvatljivih vrijednosti" koje osiguravaju poboljšanje barem jednog pokazatelja, a da ne dovode do pogoršanja ostalih.
Smatramo da je nemoguće dati jedinstvenu detaljnu definiciju optimizacije za sve vrste ljudskih aktivnosti zbog njihove bitno različite prirode. Istraživanje optimizacijskih problema dobilo je značajan razvoj u SSSR-u u vezi s planskom prirodom njegove ekonomije. Pitanja optimizacije gospodarstva okupirala su sovjetske znanstvenike sve do prijelaza na Ekonomija tržišta. Štoviše, ozbiljnost problema
Slika 1. Optimalnost prema V. Paretu
optimizacija u gospodarstvu nije se smanjila zbog brzog rasta asortimana proizvoda, lokacije značajnog broja industrija na velikom području, kao rezultat toga, velikog volumena prijevoza tereta. Zapadni znanstvenici suočili su se sa sličnim pitanjima, posebno je pitanje optimizacije postalo akutno tijekom Drugog svjetskog rata, kada se pojavila potreba za sličnom centraliziranom kontrolom velikih količina trupa, opreme i opreme. Tijekom proteklih desetljeća razvijene su mnoge teorijske i primijenjene tehnike optimizacije koje su sustavno prikazane na slici 2.
Koncept optimizacije u urbanoj znanosti
Ovaj koncept u urbanističkom planiranju korišten je u sovjetskom razdoblju u nekoliko značenja. Prije svega, to je bilo povezano s konceptom ekonomske optimizacije, služeći ekonomskim interesima. Urbanističko planiranje shvaćeno je kao jedan od alata optimizacije, čija je zadaća pomiriti interese industrijskog kompleksa s interesima stanovništva. Pojavili su se različiti optimizacijski koncepti, a među najvažnijima treba izdvojiti koncept GSNM - grupnih sustava naseljenih mjesta. Bio je to pokušaj optimizacije naselja kroz multifaktorijalnu redukciju njegovih nedostataka - izolacije ruralnog stanovništva od mjesta primjene rada i kulturnih centara, pretjeranog urbanog rasta, koji stvara ogromno opterećenje za biosferu.
Provedba koncepta GSNM-a poduzeta je u okviru Opće sheme naseljavanja SSSR-a, razvijene 1970-ih. Stvaranje GSNM-a trebalo je optimizirati proces aglomeracije velikih i srednjih gradova koji su do tada stekli. Umjesto proizvoljnog "lijepljenja" naselja trebalo je stvoriti njihovu hijerarhijsku organizaciju. Još jedna posljedica optimizacije u urbanističkom planiranju
Slika 2. Osnovne metode rješavanja optimizacijskih problema. Sustavni sažetak nje razne tehnike
bilo je razjašnjenje pitanja o tzv. "optimalnoj veličini" gradova. Podrazumijevalo se da budući da postoji prevelika prenaseljenost pojedinih gradova, odnosno njezina optimalna vrijednost koju urbanistička znanost može izračunati. “... Koncept "optimalnog" grada ostao je jedan od najbitnijih elemenata sovjetske urbane politike. .Nije bilo sumnje da takav optimum postoji. Nesuglasice su počele kada se pokušavalo odrediti kakvu populaciju treba smatrati optimalnom. Dvadesetih godina prošlog stoljeća 50.000 stanovnika činilo se optimalnim. Dovoljno je bilo pokazati dobrobiti ekonomije razmjera i urbane infrastrukture, a pritom ne toliko velike da unište osjećaj zajedništva i socijalističku komunalnu etiku. Sredinom 1950-ih. Optimalne procjene kretale su se između 150.000 i 200.000, da bi do 1960. godine skočile na 250-300.000 ljudi, a sama legitimnost ovog koncepta. je ispitan." Spor se pokazao školskim, jer optimalna veličina grada ne ovisi o apsolutnoj vrijednosti
maske o broju njezina stanovništva, već o gospodarskom i geografskom položaju u sustavu naseljavanja. Drugim riječima, nije bitna apsolutna, već relativna veličina grada, koja je različita u svakom pojedinom slučaju.
Pitanje te optimalne veličine grada postavilo se na novi akutni način 1960-ih i 1970-ih godina, kada je u SSSR-u počeo rasti broj velikih i najvećih gradova, a njihovi nedostaci postali su uočljivi. U članku karakterističnog naslova " Maksimalne dimenzije gradovi” (1970.) izjavio je: “S gledišta urbane ekonomije, najekonomičniji gradovi su oni koji imaju najmanji iznos kapitalnih ulaganja i operativnih troškova po stanovniku. I premali gradovi i divovski gradovi pokazuju se neekonomičnima. U urbanoj gradnji očituje se načelo zajedničko svim područjima gospodarstva prema kojem je velika gospodarska jedinica učinkovitija od male. U malim mjestima do 20.000 stanovnika potrebno je stvarati mala, neučinkovita komunalna i kućanska poduzeća. Kako gradovi rastu, postaju ekonomičniji.<.>Kako populacija nastavlja rasti, situacija se pogoršava.<.>nemoguće
osigurati normalno funkcioniranje grada bez većih inženjerskih i tehničkih izgradnja i takvih oblika prijevoza koji do sada nisu bili potrebni.
Autori članka vjeruju da su uspjeli pronaći odgovor na problem optimizacije: „Vagajući sve prednosti i nedostatke, u mnogim zemljama, uključujući SSSR, urbanisti i ekonomisti došli su do zaključka da je trenutno potrebno ograničiti rast gradova s milijunskim stanovništvom, poticati urbani razvoj Srednja veličina(naš kurziv. - A. M.) ".
Vidimo da je grad srednje veličine s populacijom od 50 tisuća do 100 tisuća stanovnika prepoznat kao optimalan. V. I. Perevedencev se ne slaže s tim zaključkom; Pokazuje nelinearnu prirodu ovisnosti ekonomska učinkovitost o veličini grada: „Grad nisu samo kuće u kojima ljudi žive, već i tvornice u kojima rade. Utječe li veličina grada na produktivnost rada? Da, ima. Veliki grad je isplativ u smislu proizvodnje. Ovo su dobrobiti dijeljenja
energetski, prometni, vodovodni i kanalizacijski objekti. Ovo je opskrba kvalificiranih radna snaga... Teritorijalna koncentracija industrije povećava produktivnost rada. Dakle, sam veliki grad stvara preduvjete za daljnju koncentraciju proizvodnje. Nadalje, autor napominje da je “održavanje” osobe u vrlo velikom gradu skuplje od prosjeka, ali je povrat od osobe u takvom gradu, po njegovom mišljenju, veći. Ističe: “Trenutno prihvaćeno shvaćanje optimalne veličine grada, po mom mišljenju, pogrešno je načelno, metodološki. Ako imamo u vidu ne samo potrošnju, nego i proizvodnju, tada optimalan grad neće biti onaj u kojem je uzdržavanje čovjeka jeftinije, nego onaj u kojem je razlika između onoga što čovjek daje i onoga što se na njega troši. bit će najveći.Ibid.]. To rezultira modelom "trošak-trošak" koji se primjenjuje na stanovnika određenog grada, što pokazuje da rast ekonomske učinkovitosti može biti vrlo dugoročan kako veličina grada raste, budući da produktivnost rada može rasti u širokom rasponu raspona zbog kooperativnog učinka. Drugim riječima, optimalna veličina grada može biti proizvoljno velika, ako se nastavi tendencija povećanja ekonomskog povrata od svakog pojedinca.
Istovremeno, autor stvara koncept optimalne veličine grada. S njegove točke gledišta, optimalna veličina grada općenito se određuje prema kriteriju usklađenosti veličine grada s njegovim unaprijed planiranim vrijednostima. „... Većina neugodnosti veliki grad ne zbog same veličine, već zbog grešaka u urbanističkom planiranju. Riječ je o pogreškama u predviđanju rasta grada, neskladu između “opremljenosti” grada i njegove veličine, čisto planerskim pogreškama i, konačno, uskom ekonomskom pristupu sektoru usluga. Često se planira gradnja za pola milijuna stanovnika, a grad naraste na milijun. Istovremeno, sve komunikacije, svi komunalni sustavi, struktura grada i njegov raspored ostaju u osnovi isti kao što je bilo predviđeno početnim projektom. Zapravo, ova izjava zatvara raspravu o optimalnoj veličini grada – kao optimalan se prepoznaje grad čiji razvoj odgovara vlastitom master planu.
Mora se reći da je vrlo teško pronaći optimalne gradove prema ovom kriteriju, jer, kako pokazuju brojne studije, ključne točke glavni planovi gotovo nikad nisu izvedeni. Ispada da su ruski gradovi kronično u "neoptimiziranom" stanju.
Kao zaključak ove rasprave, vrijedi navesti simptomatičnu pritužbu samog V. I. Perevedenceva da se gradovi u svom razvoju udaljavaju od stanja optimalnosti, a ne dolaze do njega: „... Najveće stope rasta stanovništva bile su u gradovima u kojoj je 1959. bilo od 400 do 600 tisuća ljudi – preko 35 posto. Prema stajalištima koja prevladavaju u našem urbanističkom planiranju, gradovi s populacijom od 50 do 200 tisuća ljudi smatraju se optimalnima, a do 400 tisuća su prihvatljivi. To znači da su najbrže rasli gradovi koji su išli preko "dopuštenog". "Optimalni" gradovi također su brzo rasli, postajući neoptimalni (naš kurziv. - A. M.) ” .
S naše točke gledišta, ova rasprava je vrlo plodna u znanstvenom smislu, iako su se njeni praktični rezultati pokazali negativnim, budući da optimalna veličina grada nikada nije pronađena. Međutim, može se izolirati teorijski rezultat:
1 Koncept optimizacije grada prema jednom ključnom parametru - broju stanovnika - nije dobio pravu teorijsku i praktičnu potvrdu. Takvu vrijednost nije bilo moguće jasno formulirati i opravdati. Nije izrađena metodologija koja bi učinkovito usmjeravala razvoj gradova prema optimalnim vrijednostima.
2 Ostaje otvoreno i neriješeno pitanje postoji li takva optimalna vrijednost u načelu. Za njegovo rješavanje potrebni su novi metodološki pristupi, koji se formiraju u sklopu tekućih istraživanja optimizacije sustava naselja Uralskog saveznog okruga.
3 Pojavilo se novo shvaćanje koncepta optimalne veličine grada, neke vrste ne apsolutne, već relativne optimalne vrijednosti, koja nije povezana s apsolutnim, već s relativnim pokazateljima. Štoviše, predlaže se razmatranje podudarnosti veličine grada s njegovim parametrima postavljenim u glavnom planu kao najjasniji takav pokazatelj.
4 Autori koncepta optimizacije grada jednostavno su svom pitanju pristupili na razini koja nije adekvatna problemu. Čini nam se da je najvjerojatnije rješenje ne optimizirati pojedini grad, nego sustav naseljavanja - regionalni i nacionalni. To je zbog činjenice da svaki grad postoji samo kao element sustava više razine, odnosno sustava naselja, i čini se da je težak zadatak optimizirati ga izolirano od tog sustava. Pravo mjerilo na kojem je moguća postavka i rješenje optimizacijskog problema je mjerilo sustava poravnanja. Određivanje veličine i razine ovog sustava dodatni je teorijski problem.
Vrste optimizacijskih problema u urbanističkom planiranju
Postalo je moguće identificirati nekoliko ključni kriteriji, prema kojem je potrebno evaluirati problem optimizacije naselja. Ukupnost ovih kriterija svojevrsna je matrica, koja bi trebala otkriti bit problema optimizacije sustava naselja.
1 Prema prisutnosti ili odsutnosti granice rasta resursa koji se optimizira. Za neke probleme optimizacije moguć je teoretski neograničen rast indikatora koji treba optimizirati. Ili, naprotiv, postoji određena konačna razina, nakon koje rast pokazatelja postaje nemoguć. U našem slučaju, preliminarno smatramo da problem optimizacije naselja pripada prvoj opciji, budući da je povećanje indeksa optimizacije povezano s veličinom stanovništva, a taj indeks teoretski može neograničeno rasti.
2 Prisutnošću jednog optimuma ili više optimuma (optimalni skup). Ovisno o vrsti problema, može imati jedan optimum ili određeni skup optimuma. U našem slučaju problem možemo preliminarno opisati kao problem s nekoliko optimuma zbog činjenice da je moguće nekoliko opcija za optimizaciju distribucije na ograničenoj ravnoj površini.
3 Ispunjavanjem Pareto kriterija (povećanje parametra optimizacije za neke elemente ne dolazi nauštrb njegovog smanjenja za druge elemente). U ovoj situaciji morate odgovoriti na pitanje - je li moguće povećati razinu opti-
mizacija nekih elemenata sustava naselja, nikad njegova redukcija u drugima. Praksa urbanističkog planiranja pokazuje da se razvoj velikog sustava naselja uz ispunjenje Paretovog kriterija čini nemogućim. Razvoj elemenata sustava naselja događa se, između ostalog, i zbog protoka stanovništva po hijerarhiji naselja (u pravilu od nižih prema višim razinama).
4 Prema kojem broju kriterija treba provesti optimizaciju - jednom ili nekoliko. Treba li optimizacija biti višeciljna ili monociljna najveći je teorijski problem. Da bi se to riješilo, potrebno je uključiti već razvijeni metodološki aparat: prije svega, potrebno je ukazati da se na makrorazini život društva formira kao rezultat interakcije njegova tri glavna podsustava. Mogu se navesti redoslijedom kojim se pojavljuju:
1) Prirodni i ekološki podsustav.
2) Sociodemografski podsustav.
3) Ekonomski podsustav.
Ti su se podsustavi tijekom povijesnog razvoja dosljedno međusobno generirali. Prirodno-ekološki podsustav, koji je izvorno postojao nemjerljivo duže od samog čovjeka, iznjedrio ga je u tijeku njegova evolucijskog razvoja. Glavni smjer djelovanja čovjeka kao razumnog bića postala je želja da osigura svoj opstanak i razvoj kroz što učinkovitije korištenje prirodnih resursa uz istovremeno nastojanje da svoju ovisnost o prirodnim katastrofama svede na najmanju moguću mjeru. Zbog te želje sociodemografski podsustav koji je stvorio čovjek stekao je značajnu autonomiju u odnosu na prirodno-ekološki podsustav. Između njih su se počele stvarati ravne linije. Povratne informacije i razvijati kontradikcije. Da bi ih prevladao, osoba je stvorila ekonomski podsustav koji osobi omogućuje naglo povećanje količine proizvedenih i potrošenih dobara i time učvršćuje svoju odvojenost od prirodno-ekološkog podsustava. Treba napomenuti da je subjekt u ovom sustavu, naravno, društveno
mografski podsustav, koji je skup ljudskih jedinki ujedinjenih u različite zajednice po etničkoj, rasnoj, vjerskoj i drugim osnovama. Čovječanstvo kroz svoju povijest živi i razvija se u ovom trokutu sila: priroda – društvo – gospodarstvo.
Kao što je vidljivo, tri su kriterija po kojima se sustav naselja može optimizirati, ovisno o tome za koji razvojni prioritet društvo izabere. Istodobno, u okviru ranijeg istraživanja, iznijeta je sljedeća tvrdnja: teritorijalni sustav naseljavanja, po našem mišljenju, element je koji na okupu drži tri podsustava razvoja ljudskog društva. To se događa iz nekoliko razloga.
Prvo, zato što čovječanstvo općenito i svaka ljudska zajednica posebno nastaje i razvija se na evolucijski oblikovanom teritoriju (prvenstveno na kopnu), koji je prije svega biosferni prostor - zona pogodna za postojanje bioloških vrsta. Dakle, stvaranje bilo kakvih ljudskih naselja uvijek se događa, prije svega, zbog odbacivanja i korištenja teritorija koji pripada biosferi. Prirodno-ekološki podsustav također obavlja vrlo važnu funkciju ograničavanja razvoja drugih podsustava i postavlja specifičnosti njihovog razvoja u određenim uvjetima.
Drugo, razvoj teritorijalnog sustava naseljavanja izravan je odraz aktivnosti sociodemografskog podsustava. Teritorijalni sustav naseljavanja u koncentriranom obliku odražava specifičnosti društva, njegovu povijest i sadašnjost, dostignuti stupanj razvoja i demografsku strukturu. Ta se obilježja prostorno očituju kroz pokazatelje kao što su broj i gustoća stanovništva, omjer i raspored ruralnog i urbanog stanovništva, smjer i intenzitet migracijskih tokova.
Treće, ekonomski podsustav, kao derivat sociodemografskog podsustava, njegov je izravni prostorni nastavak, obavljajući nekoliko osnovnih funkcija u prostornom smislu. Ovo je odredba potrebnog
vodeni procesi, organizacija prometnih veza između naselja, crpljenje potrebnih prirodnih resursa. Gospodarski podsustav, kao i sociodemografski podsustav koji ga je iznjedrio, može postojati i razvijati se samo u okviru prirodno-ekološkog podsustava. Njegov razvoj u još većoj mjeri smanjuje prostor prirodno-ekološkog sustava, kako neposredno svojim materijalnim objektima smještenim u prostoru, tako i posljedicama svojih aktivnosti. Teritorijalni sustav naseljavanja povezujući je element svih podsustava ljudskog društva i kao takav njihova je sinteza. Izvan i bez teritorijalnog sustava naseljavanja ti podsustavi jednostavno ne mogu postojati.
Dakle, imamo posla s dvosmislenom situacijom. S jedne strane, postoje tri kriterija za optimizaciju naselja: ekološki, socijalni i ekonomski. Studija pritom kao ključni uvodi potpuno novi kriterij optimalnosti - geopolitički. Dana je primarna koncepcija ovog kriterija optimizacije, a njegov sadržaj se otkriva na sljedeći način: najadekvatnija razina razmatranja razvoja teritorijalnih sustava naselja je nacionalna razina. A prava jedinica teritorijalnog sustava naseljavanja je nacionalni sustav naseljavanja. Upravo su državne granice jasne i opravdane granice sustava naselja.
S tim u vezi postavlja se pitanje kakvu ulogu ima nacionalni sustav naseljavanja u funkcioniranju države, a ne općenito neke apstraktne ljudske zajednice. Po našem mišljenju, glavni cilj postojanja i funkcioniranja nacionalnog teritorijalnog sustava naseljavanja je osigurati što učinkovitiju i dugoročniju kontrolu nad nacionalnim teritorijem postojeće države i naroda koji ga nastanjuje. Teritorijalni sustav naseljavanja svojevrsna je "dominantna struktura" koja osigurava najučinkovitiji razvoj teritorija i raspoloživih resursa na njemu, osiguravajući najučinkovitiji
razvoj ovog nacionalnog društva u cjelini i njegovih pojedinačnih članova. A uz to - osiguranje najveće stabilnosti nacije od mogućih nepovoljnih vanjskih utjecaja. Usklađenost ili nepoštivanje ovog glavnog kriterija za učinkovitu prostornu kontrolu ključ je za ocjenu kvalitete teritorijalnog sustava naselja.
Zaključak
Dakle, teoretski imamo čak četiri mogućnosti odgovora na pitanje kakva bi trebala biti priroda optimizacije u urbanističkom planiranju:
1 Optimizacija je moguća prema bilo kojem od tri odvojena parametra: ekološkom, socijalnom ili ekonomskom, što se zapravo pokušavalo učiniti u sovjetskom razdoblju u okviru sustava prostornog planiranja, kada je trebalo postići optimizaciju sustava naselja prema ekonomskom parametru, u njegovom socijalističkom shvaćanju.
2 Optimizacija je moguća (barem teoretski) za sva tri odvojena parametra istovremeno, izglađujući proturječja koja postoje među njima. U svojoj srži, takva optimizacija je bliska konceptu održivi razvoj, koji se temelji na želji da se uravnoteže socioekonomske potrebe društva i ekološke mogućnosti za njihovo osiguranje.
3 Optimizacija po geopolitičkom parametru, pri čemu kamen temeljac postaje osiguranje najučinkovitije i dugoročnije kontrole nad nacionalnim teritorijem postojeće države i nacije koja je nastanjuje. Ova vrsta optimizacije je u skladu s metodologijom ove studije i čini se da najviše obećava.
4 Optimizacija za sva četiri parametra odjednom, kada se postiže istovremena optimizacija ekoloških, društvenih, ekonomskih i geopolitičkih parametara. Ovu vrstu optimizacije možemo nazvati superoptimizacijom, kada se svi parametri optimiziraju istovremeno. Postizanje takvog stanja čini se vrlo upitnim, ali to se mora imati na umu.
kao idealan krajnji rezultat.
Popis korištene literature
1 Shuper V. A. Samoorganizacija urbanog naselja / Ros. otvoriti un-t. M., 1995.
2 Pokšiševski V. V. Naseljavanje Sibira. Povijesni i geografski ogledi. M., 1951.
3 Brazovskaya N. V. Metode optimizacije: udžbenik. dodatak / država Altai. tehn. un-t im. I. I. Polzunova [Centar udaljenosti. učenje]. Barnaul, 2000.
4 Velika sovjetska enciklopedija. 3. izd. M., 1975. T. 19.
5 Raizberg B. A., Lozovsky L. Sh., Starodubtseva E. B. Moderni ekonomski rječnik. 2. izdanje, rev. M., 1999. (monografija).
6 Ekonomija: rječnik. M., 2000. (monografija).
7 Perevedentsev V.I. Metode proučavanja migracije stanovništva, M., 1975.
8 Dubrovsky P. N. Maksimalna veličina grada // Znanost i tehnologija. 1970. br. 6.
9 Mazaev A. G. Nacionalni teritorijalni sustav naselja kao čimbenik kontrole: geopolitički pristup // Akademski bilten UralNIIproekt RAASN. 2008. br. 1. S. 32-37.
10 Mazaev A.G. Formiranje i razvoj sustava naselja Urala (XVII-XIX stoljeća): faze i geopolitičke značajke // Akademski bilten UralNIIproekt RAASN. 2014. br. 1. str. 10.
11 Mazaev A.G. Analiza razvoja strukture sustava naselja Urala (kasno XIV - XX stoljeće) metodom pokretnih prosjeka // Akademski bilten UralNIIproekt RAASN. 2014. br. 3. str. 34.
3.2.1. Linearno programiranje
Među problemima optimizacije u teoriji odlučivanja najpoznatiji su problemi linearnog programiranja u kojima funkcija koju treba maksimizirati F(x) je linearan, a ograničenja ALI zadane su linearnim nejednadžbama. Počnimo s primjerom.
proizvodni zadatak. Radionica može proizvoditi stolice i stolove. Potrebno je 5 jedinica materijala za proizvodnju stolice i 20 jedinica (stopa od mahagonija) za proizvodnju stola. Za stolicu je potrebno 10 radnih sati, za stol 15. Radi se o 400 komada materijala i 450 radnih sati. Dobit u proizvodnji stolice - 45 USD, u proizvodnji stola - 80 USD. Koliko stolica i stolova trebate napraviti da biste ostvarili maksimalan profit?
Označiti: x 1 - broj izrađenih stolica, x 2 - broj izrađenih stolova. Optimizacijski problem ima oblik:
45 x 1 + 80 x 2 → max ,
5 x 1 + 20 x 2 ≤ 400 ,
10 x 1 + 15 x 2 ≤ 450 ,
x 1 ≥ 0 ,
x 2 ≥ 0 .
Prvi redak sadrži ciljnu funkciju - dobit nakon izdavanja x 1 stolica i x 2 stola. Potrebno ga je maksimizirati odabirom optimalnih vrijednosti varijabli X 1 i x 2. U ovom slučaju moraju se poštovati ograničenja materijala (drugi red) - nije potrošeno više od 400 stopa mahagonija. Kao i radna ograničenja (treća linija) - ne više od 450 utrošenih sati. Osim toga, ne smijemo zaboraviti da su broj stolova i broj stolica nenegativni. Ako a x 1 = 0, to znači da se stolice ne proizvode. Ako se napravi barem jedna stolica, onda x 1 je pozitivan. Ali nemoguće je zamisliti negativno izdanje - x 1 ne može biti negativan s ekonomske točke gledišta, iako se s matematičke točke gledišta takvo ograničenje ne može vidjeti. U četvrtom i petom retku zadatka i navedeno je da su varijable nenegativne.
Uvjeti proizvodnog zadatka mogu se prikazati na koordinatnoj ravnini. Vrijednosti ćemo iscrtati duž horizontalne apscise x 1 , a po okomitoj ordinati - vrijednosti x 2. Zatim ograničenja na materijal i zadnja dva retka optimizacijskog problema ističu moguće vrijednosti ( x 1 , x 2) izlazni volumeni u obliku trokuta (slika 1).
Stoga su materijalna ograničenja prikazana kao konveksni poligon, točnije trokut. Ovaj trokut se dobiva odsijecanjem zone koja se nalazi uz ishodište iz prvog kvadranta. Rezanje se provodi ravnom linijom koja odgovara drugoj liniji izvornog problema, pri čemu je nejednakost zamijenjena jednakošću. Pravac prelazi os x 1 koji odgovara stolicama na (80,0). To znači da ako se sav materijal iskoristi za izradu stolica, tada će biti napravljeno 80 stolica. Ista linija siječe os x 2 , što odgovara tablicama, u točki (0,20). To znači da ako se stavi sav materijal
izrade stolova, tada će se izraditi 20 stolova. Za sve točke unutar trokuta zadovoljena je nejednakost, a ne jednakost – materijal će ostati.
Ograničenja rada mogu se prikazati na sličan način (slika 2).
|
|
Dakle, radna ograničenja, kao i materijalna ograničenja, prikazana su kao trokut. Ovaj se trokut također dobiva odsijecanjem zone koja je susjedna ishodištu iz prvog kvadranta. Rezanje se provodi ravnom linijom koja odgovara trećoj liniji izvornog problema, pri čemu je nejednakost zamijenjena jednakošću. Pravac prelazi os x 1 koji odgovara stolicama na (45,0). To znači da ako se za izradu stolica utroše svi radni resursi, tada će biti izrađeno 45 stolica. Ista linija siječe os x 2 , što odgovara tablicama, u točki (0,30). To znači da ako se svi radnici zaduže za izradu stolova, tada će biti izrađeno 30 stolova. Za sve točke unutar trokuta nejednakost je zadovoljena, a ne jednakost – neki od radnika će biti besposleni.
Vidimo da nema očitog rješenja - za proizvodnju 80 stolica ima materijala, ali nema dovoljno radnika, a za proizvodnju 30 stolova ima radne snage, ali nema materijala. Dakle, trebamo napraviti oboje. Ali u kojem omjeru?
Da bismo odgovorili na ovo pitanje, potrebno je "kombinirati" sl. 1 i sl. 2, dobivajući područje mogućih rješenja, a zatim pratiti koje vrijednosti poprima funkcija cilja na ovom skupu (sl. 3).
Dakle, skup mogućih vrijednosti za proizvodne količine stolica i stolova ( x 1 , x 2), ili, drugim riječima, skup ALI, koji specificira ograničenja na kontrolni parametar u problemu opće optimizacije, je presjek dvaju trokuta, tj. konveksni četverokut prikazan na sl.3. Njegova tri vrha su očita - to su (0.0), (45.0) i (0.20). Četvrti je sjecište dviju ravnih linija - granica trokuta na sl. 1 i sl. 2, t.j. rješenje sustava jednadžbi
5 x 1 + 20 x 2 = 400 ,
10 x 1 + 15 x 2 = 450 .
Iz prve jednadžbe: 5 x 1 = 400 - 20 x 2 , x 1 = 80 - 4 x 2. Zamijenite u drugu jednadžbu:
10 (80 - 4 x 2) + 15 x 2 = 800 - 40x 2 + 15 x 2 = 800 - 25 x 2 = 450,
dakle 25 x 2 = 350, x 2 = 14, odakle x 1 \u003d 80 - 4 x 14 \u003d 80 -56 \u003d 24.
Dakle, četvrti vrh četverokuta je (24, 14).
Moramo pronaći maksimum linearne funkcije na konveksnom poligonu. (U općem slučaju linearnog programiranja, maksimum linearne funkcije na konveksnom poliedru koji leži u konačnodimenzionalnom linearnom prostoru.) Osnovna ideja linearnog programiranja je da se maksimum postiže na vrhovima poligona. U općem slučaju - na jednom vrhu, a to je jedina maksimalna točka. Privatno - u dva, a zatim se segment koji ih povezuje također sastoji od maksimalnih točaka.
Funkcija cilja 45 x 1 + 80 x 2 poprima minimalnu vrijednost 0 u vrhu (0,0). Kako se argumenti povećavaju, ova funkcija raste. Na vrhu (24,14) poprima vrijednost 2200. U ovom slučaju, pravac 45 x 1 + 80 x 2 = 2200 prolazi između ravnih linija 5 x 1 + 20 x 2 = 400 i 10 x 1 + 15 x 2 = 450 koji se sijeku u istoj točki. Odavde, kao i izravnom provjerom preostala dva vrha, proizlazi da je maksimum funkcije cilja, jednak 2200, postignut na vrhu (24,14).
Dakle, optimalni učinak je sljedeći: 24 stolice i 14 stolova. Pri tome se koriste svi materijalni i svi radni resursi, a dobit iznosi 2200 američkih dolara.
Dvostruki problem. Svakom problemu linearnog programiranja odgovara tzv. dualni problem. U njemu se, u usporedbi s izvornim problemom, redovi pretvaraju u stupce, nejednakosti mijenjaju predznak, traži se minimum umjesto maksimuma (ili obrnuto, umjesto minimuma traži se maksimum). Zadatak dualan dualnom je sam izvorni zadatak. Usporedimo izvorni problem (lijevo) i njegov dvostruki problem (desno):
45 x 1 + 80 x 2 → maksimalno, 400 W 1 + 450 W 2 → min ,
5 x 1 + 20 x 2 ≤ 400 , 5 W 1 + 10 W 2 ≥ 45,
10 x 1 + 15 x 2 ≤ 450 , 20 W 1 + 15 W 2 ≥ 80,
x 1 ≥ 0 , W 1 ≥ 0,
x 2 ≥ 0 . W 2 ≥ 0.
Zašto je dvojni zadatak tako važan? Može se dokazati da su optimalne vrijednosti funkcija cilja u izvornom i dualnom problemu iste (tj. maksimum u izvornom problemu podudara se s minimumom u dualnom problemu). U ovom slučaju, optimalne vrijednosti W 1 i W 2 prikazuju troškove materijala, odnosno rada, ako su procijenjeni svojim doprinosom funkciji cilja. Ne smije se brkati s tržišne cijene ovi faktori proizvodnje W 1 i W 2 nazivaju se "objektivnim vrednovanjem" sirovina i rada.
Linearno programiranje kao znanstvena i praktična disciplina. Od svih problema optimizacije, problemi linearnog programiranja razlikuju se po tome što su njihova ograničenja sustavi linearnih nejednadžbi ili jednakosti. Ograničenja definiraju konveksne linearne poliedre u konačnom linearnom prostoru. Ciljne funkcije su također linearne.
Po prvi put takve probleme riješio je sovjetski matematičar L.V. Kantorovich (1912-1986) 1930-ih godina kao zadaće upravljanja proizvodnjom u cilju optimizacije organizacije proizvodnje i proizvodnih procesa, na primjer, procesa utovara strojeva i rezanja listova materijala. Nakon Drugog svjetskog rata slične su zadaće preuzele i Sjedinjene Države. Godine 1975. T. Koopmans (1910.-1985., rođen u Nizozemskoj, radio uglavnom u SAD-u) i akademik Akademije znanosti SSSR-a L.V. Kantorovich je dobio Nobelovu nagradu za ekonomiju.
Razmotrite nekoliko tipični zadaci linearno programiranje (vidi također).
Problem prehrane (pojednostavljena verzija). Pretpostavimo za sigurnost da je potrebno formulirati najjeftiniju hranu za piliće koja sadrži potrebnu količinu određenih hranjivih tvari (jednostavnije radi, tiamin T i niacin H).
Stol 1.
Početni podaci u problemu optimizacije smjese.
Nutritivna vrijednost dijete (u kalorijama) mora biti barem onoliko koliko je navedeno. Neka, jednostavnosti radi, smjesa za piliće bude napravljena od dva proizvoda - Do i IZ. Poznat je i sadržaj tiamina i niacina u ovim proizvodima. također nutritivnu vrijednost Do i IZ(u kalorijama). Kako Do i IZ treba uzeti za jednu porciju hrane za piliće tako da pilići dobiju potrebnu dozu H i T tvari i kalorija (ili više), a trošak porcije je minimalan? Početni podaci za izračun dati su u tablici 1.
3,8 Do + 4,2 IZ→ min ,
0,10 Do + 0,25 IZ ≥ 1,00 ,
1,00 Do + 0,25 IZ ≥ 5,00 ,
110,00Do + 120,00 IZ ≥ 400,00 ,
Do ≥ 0 ,
IZ ≥ 0 .
Njegovo grafičko rješenje prikazano je na sl.4.
sl.4. Grafičko rješenje problema optimizacije smjese.
Na slici 4, radi lakšeg uočavanja, četiri ravne linije označene su brojevima (1) - (4). Pravac (1) je pravac 1.00 Do + 0,25 IZ= 5,00 (granica tvari H). Prolazi, kao što je prikazano na slici, kroz točke (5.0) na x-osi i (0.20) na y-osi. Imajte na umu da su dopuštene vrijednosti parametara (K, IZ) leže iznad linije (1) ili na njoj, za razliku od prethodno razmatranih slučajeva u prethodnom proizvodni zadatak linearno programiranje.
Ravna linija (2) je ravna linija 110.00 Do + 120,00 IZ= 400,00 (ograničenje kalorija). Imajte na umu da u području nenegativnih IZ nalazi se posvuda ispod crte (1). Doista, ovo vrijedi za Do=0, pravac (1) prolazi kroz točku (0.20), a pravac (2) prolazi kroz točku (0, 400/120) koja se nalazi ispod. Sjecište dviju pravaca nalazi se pri rješavanju sustava jednadžbi
1,00 Do + 0,25 IZ = 5,00 ,
110,00 Do + 120,00 IZ = 400,00 .
Iz prve jednadžbe Do = 5 - 0,25 IZ. Zamjena u drugom: 110 (5-0,25 IZ) + 120 IZ= 400, odakle 550 - 27,5 IZ + 120 IZ= 400. Prema tome, 150 = - 92,5 IZ, tj. do rješenja dolazi negativnim IZ. To znači da za sve pozitivne IZ linija (2) nalazi se ispod linije (1). Dakle, ako je ograničenje na H ispunjeno, onda je nužno ispunjeno i ograničenje na kalorije. Suočeni smo s novim fenomenom - neka ograničenja s matematičkog stajališta mogu biti suvišna. S ekonomskog stajališta one su neophodne, odražavaju bitna obilježja tvrdnje problema, ali u ovom slučaju pokazalo se da je unutarnja struktura problema takva da restrikcija kalorija ne sudjeluje u formiranju dopuštene vrijednosti. raspon parametara i pronalaženje rješenja.
Pravac (4) je pravac 0.1 Do + 0,25 IZ= 1 (ograničenje na tvar T). Prolazi, kao što je prikazano na slici, kroz točke (10,0) na apscisnoj osi i (0,4) na ordinatnoj osi. Imajte na umu da važeće vrijednosti parametara ( Do, IZ) leže iznad linije (4) ili na njoj, kao i za liniju (1).
Stoga, raspon dopuštenih vrijednosti parametara ( Do, IZ) je neomeđena odozgo. Od cijele ravnine razlikuje se po koordinatnim osima (nalazi se u prvom kvadrantu) i ravnim crtama (1) i (4) (nalazi se iznad ovih linija, a uključuje i rubne segmente). Područje prihvatljivih vrijednosti parametara, tj. bodovi ( Do, IZ) može se nazvati "neomeđeni poligon". Funkcija minimalnog cilja 3.8 Do + 4,2 IZ može doći samo do vrhova ovog "poligona". Postoje samo tri vrha. To su sjecišta s apscisnom (10,0) i ordinatnom (0,20) osi pravaca (1) i (4) (u svakom slučaju, iz dvaju sjecišta uzima se onaj koji zadovoljava oba ograničenja). Treći vrh je točka ALI sjecište pravaca (1) i (4) čije se koordinate nalaze pri rješavanju sustava jednadžbi
0,10Do + 0,25 IZ = 1,00 ,
1,00 Do + 0,25 IZ = 5,00 .
Iz druge jednadžbe Do = 5 - 0,25 IZ, od prvog 0,10 (5 - 0,25 IZ) + 0,25 IZ = 0,5 - 0,025 IZ + 0,25 IZ = 0,5 + 0,225 IZ= 1, odakle IZ= 0,5/0,225 = 20/9 i Do= 5 - 5/9 = 40/9. Tako, ALI = (40/9; 20/9).
Pravac (3) na slici 4 je pravac koji odgovara funkciji cilja 3.8 Do + 4,2IZ. Prolazi između ravnih linija (1) i (4) koje definiraju ograničenja, a minimum se postiže u točki ALI, kroz koji prolazi pravac (3). Stoga je minimum 3,8x40/9 + 4,2x20/9 = 236/9. Problem optimizacije smjese je potpuno riješen.
Dualni problem, izgrađen prema gore opisanim pravilima, ima sljedeći oblik (ovdje ponavljamo izvorni problem optimizacije smjese kako bismo jasno demonstrirali tehnologiju konstruiranja dualnog problema):
3,8 Do + 4,2 IZ→ min , W 1 + 5 W 2 + 400 W 3 → max ,
0,10 Do + 0,25 IZ ≥ 1,00 , 0,1 W 1 + 1,10 W 2 + 110 W 3 ≤ 3,8 ,
1,00 Do + 0,25 IZ ≥ 5,00 , 0,25W 1 + 0,25 W 2 + 120 W 3 ≤ 4,2 ,
110,00 Do + 120,00 IZ ≥ 400,00 , W 1 ≥ 0 ,
Do ≥ 0 , W 2 ≥ 0 ,
IZ ≥ 0 . W 3 ≥ 0 .
Minimalna vrijednost u izravnom problemu, kao što bi i trebala biti, jednaka je maksimalnoj vrijednosti u dualnom problemu, tj. oba broja su 236/9. Tumačenje dualnih varijabli: W 1 - "trošak" jedinice tvari T, i W 2 - "trošak" jedinice tvari H, mjeren "prema njihovom doprinosu" funkciji cilja. pri čemu W 3 = 0, budući da ograničenje kalorija ni na koji način ne pridonosi stvaranju optimalne otopine. Tako, W 1 , W 2 , W 3 - to je tzv. objektivno uvjetovane procjene (prema L.V. Kantorovichu) resursa (tvari T i H, kalorije).
Planiranje nomenklature i volumena izdavanja. Vratimo se organizaciji proizvodnje. Poduzeće može proizvoditi automatske kuhinje (vrste tava), aparate za kavu i samovare. U tablici 2 prikazani su podaci o proizvodnim kapacitetima kojima raspolaže poduzeće (u komadima proizvoda).
Tablica 2.
Kapacitet proizvodnje (u kom.)
|
Aparati za kavu |
Samovari |
||
|
Žigosanje |
|||
|
Svezak izdanja |
|||
|
Specifična dobit (po proizvodu) |
U ovom slučaju, žigosanje i dorada se izvode na istoj opremi. Omogućuje vam da u određenom vremenu napravite 20 000 kuhinja ili 30 000 aparata za kavu ili oboje, i ništa manje. Ali montaža se provodi u odvojenim područjima.
Problem linearnog programiranja ima oblik:
x 1 ≥ 0 , x 2 ≥ 0 , x 3 ≥ 0 , (0)
x 1 / 200 + x 2 / 300 + x 3 / 120 ≤ 100 , (1)
x 1 / 300 + x 2 / 100 + x 3 / 100 ≤ 100 , (2)
x 1 / 200 ≤ 100 , (3)
H 2 / 120 ≤ 100 , (4)
x 3 / 80 ≤ 100 , (5)
F\u003d 15 X 1 + 12 X 2 + 14 x 3 → maks.
(0) je uobičajeni uvjet u ekonomiji za nenegativnost varijabli,
(1) - ograničenje mogućnosti žigosanja (izraženo radi lakše percepcije kao postotak),
(2) - ograničenje mogućnosti dorade,
(3) - granica montaže za kuhinje,
(4) - isto za mlince za kavu,
(5) - isto za samovare (kao što je već spomenuto, sve tri vrste proizvoda sastavljene su na zasebnim linijama).
Konačno, funkcija cilja F je ukupna dobit poduzeća.
Uočimo da nejednakost (3) slijedi iz nejednakosti (1), a nejednakost (4) proizlazi iz (2). Stoga se nejednakosti (3) i (4) mogu eliminirati iz formulacije problema linearnog programiranja.
Odmah napomenimo jednu zanimljivu činjenicu. Kako će se utvrditi, optimalno x 3 = 0, tj. neisplativo je proizvoditi samovare.
Metode rješavanja problema linearnog programiranja. Metode za rješavanje problema linearnog programiranja pripadaju računalnoj matematici, a ne ekonomiji. Međutim, korisno je da ekonomist bude svjestan svojstava pametnog alata koji koristi.
Kako snaga računala raste, potreba za korištenjem sofisticiranih matematičkih metoda se smanjuje, jer u mnogim slučajevima vrijeme brojanja prestaje biti ograničavajući faktor, ono je vrlo malo (frakcije sekunde). Stoga ćemo analizirati samo tri metode.
Jednostavno nabrajanje. Uzmimo neki višedimenzionalni paralelopiped koji sadrži poliedar definiran ograničenjima. Kako ga izgraditi? Na primjer, ako postoji ograničenje tipa 2 x 1 + 5x 2 ≤ 10, tada je očito 0 ≤ x 1 ≤ 10/2 = 5 i 0 ≤ x 2 ≤ 10/5 = 2. Slično, može se prijeći s općih linearnih ograničenja na ograničenja na pojedinačne varijable. Ostaje uzeti maksimalne granice za svaku varijablu. Ako je ograničeni poliedar neomeđen, kao što je bio slučaj u problemu prehrane, moguće je na sličan, ali nešto kompliciraniji način, izolirati njegov dio "okrenut" ishodištu, koji sadrži rješenje, i zatvoriti ga u višedimenzionalni paralelopiped.
Nabrojimo točke paralelopipeda s korakom 1/10 n sekvencijalno na n=2,3,…, izračunavanje vrijednosti funkcije cilja i provjera ispunjenja ograničenja. Od svih točaka koje zadovoljavaju ograničenja, uzimamo onu u kojoj je funkcija cilja maksimalna. Rješenje pronađeno! (Striktno govoreći, pronađeno s točnošću od 1/10 n.)
Usmjerena iteracija. Počnimo s točkom koja zadovoljava ograničenja (može se pronaći jednostavnim nabrajanjem). Sekvencijalno (ili slučajno – tzv. metodom slučajnog pretraživanja) mijenjat ćemo mu koordinate za određenu vrijednost ∆, svaki put do točke s višom vrijednošću funkcije cilja. Ako dođemo do restrikcijske ravnine, kretat ćemo se duž nje (tražeći jednu od koordinata pomoću restrikcijske jednadžbe). Zatim kretanje po rubu (kada se dva ograničenja-nejednakosti pretvaraju u jednakosti) ... Zaustavite se - na vrhu linearnog poliedra. Rješenje pronađeno! (Strože govoreći, nalazi se do ∆. Ako je potrebno, u blizini pronađenog rješenja provodimo usmjereno nabrajanje s korakom ∆/2 , ∆/4 itd.)
Simpleks metoda. Ovo je jedna od prvih specijaliziranih optimizacijskih metoda usmjerenih na rješavanje problema linearnog programiranja, dok se jednostavne i usmjerene metode nabrajanja mogu primijeniti za rješavanje gotovo svakog optimizacijskog problema. Simpleks metodu predložio je Amerikanac G. Danzig 1951. godine. Glavna ideja joj je kretanje po konveksnom poliedru ograničenja od vrha do vrha, pri čemu se u svakom koraku vrijednost funkcije cilja poboljšava sve dok se ne postigne optimum. Analizirajmo primjer na temelju podataka u tablici 2.
Razmotrite gore formulirani problem linearnog programiranja kada razmatrate optimizaciju opsega i izlaznih volumena:
F = 15 x 1 + 12 x 2 + 14 x 3 → maks.
x 1 / 200 + x 2 / 300 + x 3 / 120 ≤ 100 ,
x 1 / 300 + x 2 / 100 + x 3 / 100 ≤ 100 ,
x 3 / 80 ≤ 100 .
Nenegativnost varijabli neće biti posebno naznačena, jer je ova pretpostavka uvijek prihvaćena u problemima linearnog programiranja.
Sukladno simpleks metodi uvodimo tzv "slobodne varijable" x 4 , x 5 , x 6 što odgovara nedovoljno iskorištenim kapacitetima, tj. iz sustava nejednadžbi prelazimo na sustav jednadžbi:
x 1 / 200 + x 2 / 300 + x 3 / 120 + x 4 = 100 ,
x 1 / 300 + x 2 / 100 + x 3 / 100 + x 5 = 100 ,
x 3 / 80 + x 6 = 100 ,
15 x 1 + 12 x 2 + 14 x 3 = F.
Ovaj sustav ima očito rješenje koje odgovara jednom od vrhova poliedra dopuštenih varijabilnih vrijednosti:
x 1 = x 2 = x 3 = 0, x 4 = x 5 = x 6 = 100, F = 0.
U smislu izvornog problema, to znači da ništa ne treba izdati. Ovo rješenje je prihvatljivo samo za vrijeme ljetnih praznika.
U skladu s simpleks metodom odabiremo varijablu koja je uključena u funkciju cilja F s najvećim pozitivnim koeficijentom. to x 1 .
Uspoređujemo kvocijente slobodnih članova u prve tri jednadžbe s koeficijentima s upravo odabranom varijablom x 1:
100 / (1/200) = 20000, 100 / (1/300) =30000, 100/0 = + ∞ .
Odaberemo liniju iz sustava jednadžbi koja odgovara minimumu svih pozitivnih omjera. U ovom primjeru, ovo je prvi redak koji odgovara omjeru 20000.
Pomnožite prvi red s 200 da biste dobili x 1 s koeficijentom jedinice:
x 1 + 2/3 x 2 + 2/1,2 x 3 + 200 x 4 = 20000 .
Zatim pomnožimo novodobiveni redak s (-1/300) i dodamo ga u drugi red kako bismo eliminirali član s x 1, dobivamo
7/900 x 2 + 4/900 x 3 - 2/3 x 4 + x 5 = 100/3.
Pomnožite isti konvertirani prvi niz s (-15) i dodajte ga nizu na čijoj je desnoj strani F, dobivamo:
2 x 2 - 11 x 3 - 3000 x 4 = F - 300000.
Kao rezultat toga, sustav jednadžbi se transformira u oblik u kojem varijabla x 1 je uključen samo u prvu jednadžbu:
x 1 + 2/3 x 2 + 2/1,2 x 3 + 200 x 4 = 20000 ,
7/900 x 2 + 4/900 x 3 - 2/3 x 4 + x 5 = 100/3,
x 3 / 80 + x 6 = 100 ,
2 x 2 - 11 x 3 - 3000 x 4 = F - 300000.
Očito, novi sustav ima poboljšano rješenje u odnosu na originalno, koje odgovara drugom vrhu konveksnog poliedra u šestodimenzionalnom prostoru:
x 1 = 20000, x 2 = x 3 = x 4 = 0, x 5 = 100/3, x 6 = 100, F = 300000.
U smislu izvornog problema, ovo rješenje znači da se proizvode samo kuhinje. Takvo rješenje je prihvatljivo ako je dopuštena proizvodnja samo jedne vrste proizvoda.
Ponovimo gornju operaciju. U skladu s F postoji još jedan pozitivan koeficijent - at x 2 (da ima više pozitivnih koeficijenata, uzeli bismo najveći od njih). Na temelju koeficijenata pri x 2 (ne na x 1, kao i prvi put) kvocijente formiramo dijeljenjem odgovarajućih slobodnih članova ovim koeficijentima:
20000 / (2/3) = 30000, (100/3) / (7/900) = 30000/7, 100/0 = + ∞.
Dakle, trebamo izabrati drugi red, za koji imamo najmanji pozitivni omjer od 30000/7. Pomnožite drugi redak s 900/7 (tako da koeficijent at x 2 je bilo jednako 1). Zatim dodajte ažurirani redak u sve retke koji sadrže x 2, prethodno ih pomnoživši odgovarajućim brojevima, tj. tako da svi koeficijenti pri x 2 bi nakon zbrajanja postao 0, osim koeficijenta drugog retka koji je već postao jednak 1. Dobivamo sustav jednadžbi:
x 1 + 9/7 x 3 + 1800/7 x 4 - 600/7 x 5 = 120000/7 ,
x 2 + 4/7 x 3 - 600/7 x 4 + 900/7 x 5 = 30000/7,
x 3 / 80 + x 6 = 100 ,
85/7 x 3 - 19800/7 x 4 - 1800/7 x 5 = F - 308571.
Budući da su sve varijable nenegativne, iz posljednje jednadžbe proizlazi da profit F dostiže najveću vrijednost od 308571 at x 3 = x 4 = x 5 = 0. Iz preostalih jednadžbi slijedi da je u ovom slučaju x 1 = 120000/7 = 17143, x 2 = 30000/7 = 4286, x 6 = 100. Budući da je u liniji sa F nije preostao niti jedan pozitivni koeficijent varijabli, tada je algoritam simpleks metode završio svoj posao, pronađeno je optimalno rješenje.
Praktične preporuke su sljedeće: potrebno je proizvesti 17143 kuhinje, četiri puta manje, tj. 4286, mlinci za kavu, uopće ne proizvode samovare. U ovom slučaju dobit će biti maksimalna i jednaka 308571. Sve oprema za proizvodnju bit će u potpunosti napunjen, osim trake za montažu samovara.
transportni zadatak. Razni tehnički, ekonomski i ekonomski zadaci upravljanja proizvodnjom, od optimalnog opterećenja stroja i krojenja čeličnog lima ili tkanine do analize međusektorske ravnoteže i procjene stope rasta gospodarstva zemlje u cjelini, vode na potrebu rješavanja pojedinih problema linearnog programiranja. Knjiga sadrži opsežan popis publikacija posvećenih brojnim primjenama linearnog programiranja u metalurgiji, industriji ugljena, kemijskoj, naftnoj, papirnoj i drugim industrijama, u problemima transporta i komunikacija, planiranju proizvodnje, dizajnu i skladištenju proizvoda, poljoprivredi, u znanstvenim istraživanja, uključujući brojna gospodarska, pa i u regulaciji prometa.
Kao drugi primjer razmotrite tzv. transportni zadatak. Postoje skladišta čije su zalihe poznate. Poznati su potrošači i njihove potrebe. Potrebno je isporučiti robu iz skladišta potrošačima. Možete organizirati "pričvršćivanje" potrošača na skladišta na različite načine, tj. odrediti iz kojeg skladišta kojem potrošaču i koliko nositi. Osim toga, poznata je cijena isporuke jedinice robe iz određenog skladišta do određenog potrošača. Potrebno je minimizirati troškove prijevoza.
Na primjer, možemo govoriti o prijevozu pijeska - sirovine za proizvodnju opeke. Pijesak se obično dostavlja u Moskvu najjeftinijim prijevozom - vodom. Stoga se luke mogu smatrati skladištima, a njihov dnevni protok rezervama. Potrošači su tvornice opeke, a njihove potrebe određuju se dnevnom proizvodnjom (sukladno postojećim narudžbama). Za dostavu je potrebno ukrcati vozila, voziti određenom rutom i istovariti. Trošak ovih operacija izračunava se prema dobro poznatim pravilima, na kojima se nema smisla zadržavati. Stoga se trošak isporuke robe iz određenog skladišta do određenog potrošača može smatrati poznatim.
Razmotrimo primjer transportnog problema, čiji su početni podaci prikazani u tablici. 3.
U tablici 3, osim obujma potreba i vrijednosti zaliha, prikazan je trošak isporuke jedinice robe sa skladišta ja, ja = 1,2,3, potrošač j, j = 1,2,3,4. Na primjer, najjeftinija je isporuka iz skladišta 2 potrošačima 1 i 3, te iz skladišta 3 potrošaču 2. Međutim, skladište 2 ima 80 jedinica robe, a potrošači 1 i 3 zahtijevaju 50 + 70 = 120 jedinica, pa će roba moraju se voziti do njih i iz drugih skladišta. Napominjemo da su u tablici 3 zalihe u skladištima jednake ukupnim potrebama. Na primjer, kod isporuke pijeska tvornicama opeke, to je sasvim prirodno ograničenje - ako se takvo ograničenje ne poštuje, ili će luke biti prekrivene planinama pijeska ili tvornice opeke neće ispunjavati narudžbe.
Tablica 3
Početni podaci za transportni problem.
|
Potrošač 1 |
Potrošač 2 |
Potrošač 3 |
Potrošač 4 |
Zalihe u skladištima |
|
|
Potrebe |
Potrebno je planirati prijevoz, tj. odaberite količine H ij isporuke robe iz skladišta ja potrošač j, gdje ja = 1,2,3; j= 1,2,3,4. Dakle, u problemu postoji ukupno 12 varijabli. Zadovoljavaju dvije skupine ograničenja. Prvo se postavljaju zalihe u skladištima:
x 11 + x 12 + x 13 + x 14 = 60 ,
x 21 + x 22 + x 23 + x 24 = 80 ,
x 31 + x 32 + x 33 + x 34 = 60 .
Drugo, poznate su potrebe kupaca:
x 11 + x 21 + x 31 = 50 ,
x 12 + x 22 + x 32 = 40 ,
x 13 + x 23 + x 33 = 70 ,
x 14 + x 24 + x 34 = 40 .
Dakle, postoji ukupno 7 ograničenja tipa jednakosti. Osim toga, sve varijable su nenegativne - još 12 ograničenja.
Funkcija cilja su troškovi prijevoza koje je potrebno minimizirati:
F = 2 x 11 + 5 x 12 + 4 x 13 + 5 x 14 + x 21 + 2 x 22 + x 23 + 4 x 24 +
3 x 31 + x 32 + 5 x 33 + 2 x 34 → min.
Osim ove razmatrane, razmatraju se i razne druge varijante prometnog problema. Na primjer, ako se isporuka vrši vagonima, tada obujam isporuka mora biti višekratnik kapaciteta vagona.
Broj varijabli i ograničenja u prometnom problemu je takav da se ne može riješiti bez računala i odgovarajućeg programskog proizvoda.
3.2.2. Cjelobrojno programiranje
Problemi optimizacije u kojima varijable uzimaju cjelobrojne vrijednosti povezani su s cjelobrojnim programiranjem. Razmotrimo neke od ovih problema.
Problem odabira opreme. Za nabavu opreme za novi dio radionice izdvojeno je 20.000 američkih dolara. U ovom slučaju možete zauzeti površinu ne veću od 38 m 2. Dostupni su strojevi tipa A i strojevi tipa B. Strojevi tipa A koštaju 5000 američkih dolara, zauzimaju površinu od 8 m2 (uključujući potrebne tehnološke prolaze) i imaju kapacitet od 7000 jedinica po smjeni. Strojevi tipa B koštaju 2000 dolara, zauzimaju površinu od 4 m2 i imaju kapacitet od 3000 jedinica po smjeni. Treba izračunati najbolja opcija nabava opreme koja, pod zadanim ograničenjima, maksimizira ukupnu produktivnost mjesta.
Neka je X broj strojeva tipa A, a Y broj strojeva tipa B uključenih u komplet opreme. Potrebno je odabrati set opreme tako da se maksimizira učinak IZ površina (u tisućama jedinica po smjeni):
IZ= 7 X + 3 Na → maks.
U tom slučaju moraju se poštovati sljedeća ograničenja:
po cijeni (u tisućama američkih dolara)
5 x+ 2 Na ≤ 20,
prema zauzetoj površini (u m 2)
8 x + 4 Na ≤ 38,
kao i novonastala specifična ograničenja na cijele brojeve, naime,
x ≥ 0 , Na ≥ 0 , x i Na- cijeli brojevi.
Formulirani matematički problem razlikuje se od problema linearnog programiranja samo u posljednjem cjelobrojnom uvjetu. Međutim, postojanje ovog uvjeta omogućuje (u ovom konkretnom slučaju) jednostavno rješavanje problema nabrajanjem. Doista, i ograničenje troškova i ograničenje područja to daju x≤ 4. Dakle, X može imati samo jednu od 5 vrijednosti: 0, 1, 2, 3, 4.
Ako a x= 4, onda iz ograničenja troškova slijedi da Na= 0, i stoga IZ = 7 x = 28.
Ako a x= 3, onda prvo ograničenje implicira da Na≤ 2, od drugog Na≤ 3. Dakle, maksimum IZ Na=2, naime IZ = 21 + 6 = 27.
Ako a x= 2, tada iz prvog ograničenja slijedi da je Na≤ 5, također iz drugog Na≤ 5. Dakle, maksimum IZ uz ispunjenje ograničenja postiže se kada Na=5, naime IZ = 14 + 15 = 29.
Ako a x= 1, tada iz prvog ograničenja imamo Na≤ 7, također iz drugog Na≤ 7. Dakle, maksimum IZ uz ispunjenje ograničenja postiže se kada Na= 7, naime IZ = 7 + 21 = 28.
Ako a x= 0, tada prvo ograničenje implicira Na≤ 10, od drugog Na≤ 9. Dakle, maksimum IZ uz ispunjenje ograničenja postiže se kada Na= 9, naime, IZ = 27.
Razmotreni su svi mogući slučajevi. Maksimalna izvedba IZ= 29 (tisuću jedinica proizvodnje po smjeni) postiže se s X = 2, Na= 5. Dakle, trebate kupiti 2 stroja tipa A i 5 strojeva tipa B.
Problem s naprtnjačom. Ukupna težina ruksaka je unaprijed ograničena. Koje predmete staviti u ruksak kako bi ukupna korisnost odabranih predmeta bila što veća? Težina svakog artikla je poznata.
Postoji mnogo ekvivalentnih formulacija. Na primjer, umjesto naprtnjače, možemo razmotriti svemirska letjelica- satelit Zemlje, a kao objekti - znanstveni instrumenti. Tada se problem tumači kao odabir uređaja za lansiranje u orbitu. Istina, to pretpostavlja da je preliminarni problem riješen - procjena komparativne vrijednosti studija za koje je potreban jedan ili drugi instrument.
Sa stajališta ekonomije poduzeća i organizacije proizvodnje, relevantnije je drugo tumačenje problema naprtnjače, u kojem se narudžbe (ili opcije za proizvodnju serija određene robe) smatraju "predmetima", profitom. od ispunjenja narudžbe smatra se korisnošću, a težinom - troškom narudžbe.
Prijeđimo na matematičku formulaciju. Pretpostavlja se da postoji n predmeta, a za svaki od njih potrebno je odlučiti hoće li se staviti u torbu ili ne. Za opis rješenja uvode se Booleove varijable X k ,k = 1,2,…, n(tj. varijable koje imaju dvije vrijednosti, naime 0 i 1). pri čemu X k= 1 ako je predmet stavljen u naprtnjaču, i X k= 0 ako nije, k = 1,2,…, n. Za svaku stavku poznate su dvije konstante: A k- težina k-ti predmet, i s k- korisnost k-ti predmet, k = 1,2,…, n. Označavamo najveći mogući kapacitet naprtnjače NA. Optimizacijski problem ima oblik
C 1 X 1 + C 2 X 2 + C 3 X 3 + .... + C n X n→ max ,
A 1 X 1 + A 2 X 2 + A 3 X 3 + .... + A n H n ≤ V.
Za razliku od prethodnih zadataka, kontrolni parametri X k , k = 1,2,…, n, uzimaju vrijednosti iz skupa koji sadrži dva elementa - 0 i 1.
Cjelobrojno programiranje uključuje probleme postavljanja (proizvodnih objekata), teoriju rasporeda, kalendar i operativno planiranje, imenovanja osoblja itd. (vidi npr. monografiju).
Navodimo dvije uobičajene metode za rješavanje problema cjelobrojnog programiranja
Metoda aproksimacije kontinuiranim problemima. U skladu s njim, problem linearnog programiranja prvo se rješava bez razmatranja cijelog broja, a zatim se traže cjelobrojne točke u blizini optimalnog rješenja.
Metode usmjerenog nabrajanja. Od njih je najpoznatija metoda grananja i vezanja. Suština metode je sljedeća. Svaki podskup x postavlja moguća rješenja X 0 je dodijeljen broj - "border" A (x). Pri rješavanju problema minimizacije potrebno je da ALI(X 1) ≥ A (X 2), ako x 1 je uključen u x 2 ili isto kao x 2 .
Svaki korak metode grananja i vezanja sastoji se od dijeljenja odabranog prema prethodni korak postavlja X C na dva - X 1C i X 2C. Istodobno, raskrižje X 1C i X 2C je prazna, a njihova unija je ista kao X C. Zatim izračunajte granice ALI(X 1C) i ALI(X 2C) i dodijeli "granu" X C+1 - jedan od setova X 1C i X 2C, za koje je granica manja. Algoritam se zaustavlja kada je promjer novoodabrane grane manji od unaprijed određenog malog broja
Za svaki specifični problem cjelobrojnog programiranja (drugim riječima, diskretne optimizacije), metoda grananja i vezanja implementirana je na svoj način. Postoje mnoge modifikacije ove metode.
3.2.3. Teorija grafova i optimizacija
Jedna od grana diskretne matematike koja se često koristi u donošenju odluka je teorija grafova (vidi, na primjer, vodiči za učenje). Graf je skup točaka, zvanih vrhovi grafa, od kojih su neki povezani lukovima (lukovi se također nazivaju bridovima). Primjeri grafova prikazani su na sl.5.
|
Novouvedenom pojmu grafa "pridaju" se nova svojstva. Izvornom objektu pripisuju se nove kvalitete. Na primjer, uvodi se i koristi pojam usmjerenog grafa. U takvom grafu, lukovi imaju strelice usmjerene od jednog vrha do drugog. Primjeri usmjerenih grafova dati su na sl.6.
sl.6. Primjeri usmjerenih grafova.
Usmjereni graf bio bi koristan, na primjer, za ilustraciju organizacije prijevoza u problemu prijevoza. U ekonomiji se brojevi često dodjeljuju lukovima usmjerenog ili običnog grafa, kao što su troškovi putovanja ili prijevoza robe od točke A (početnog vrha luka) do točke B (konačnog vrha luka).
Razmotrimo neke tipične probleme donošenja odluka vezane uz optimizaciju na grafovima.
Problem trgovačkog putnika. Potrebno je posjetiti sve vrhove grafa i vratiti se na izvorni vrh, minimizirajući troškove putovanja (ili minimizirajući vrijeme).
Početni podatak ovdje je graf čiji su lukovi dodijeljeni pozitivni brojevi - putni troškovi ili vrijeme potrebno za prelazak s jednog vrha na drugi. Općenito, graf je usmjeren, a svaka dva vrha povezuju dva luka - naprijed i natrag. Doista, ako se točka A nalazi na planini, a točka B je u nizini, tada je vrijeme putovanja od A do B očito kraće od vremena putovanja natrag od B do A.
Mnoge izjave ekonomskog sadržaja svode se na problem trgovačkog putnika. Na primjer:
Sastaviti najprofitabilniju rutu za zaobilaženje regulatora u trgovini (kontrolora, zaštitara, policajca) odgovornog za ispravno funkcioniranje zadanog skupa objekata (svaki od tih objekata modeliran je vrhom grafa);
Sastavite najprofitabilniju rutu za dostavu dijelova radnicima ili kruha iz pekare u određeni broj pekara i dr. prodajna mjesta(parking kod pekare).
Problem s najkraćim putem. Koji je najkraći put od jednog do drugog vrha grafa? U smislu upravljanja proizvodnjom: kao najkraći put (a time i s najmanji trošak gorivo i vrijeme, najjeftinije) doći od točke A do točke B? Da bi se riješio ovaj problem, svakom luku usmjerenog grafa mora biti pridružen broj - vrijeme potrebno za pomicanje po tom luku od početnog vrha do konačnog. Razmotrimo primjer (slika 7).
sl.7. Početni podaci za problem najkraćeg puta.
Situacija se može opisati ne samo usmjerenim grafom s težinama dodijeljenim lukovima, već i tablicom (tablica 7). U ovoj tablici dva vrha - početak puta i kraj puta - pridružena su vremenu putovanja. Tablica 7 razmatra staze bez međuzaustavljanja. Složenije rute sastoje se od elementarnih segmenata navedenih u tablici 4.
Tablica 4
Početni podaci za problem najkraćeg puta.
|
Početak luka |
Kraj luka |
Vrijeme putovanja |
Postavlja se pitanje: koji je najkraći put od vrha 1 do vrha 4?
Riješenje. Uvedimo oznaku: IZ(T) - duljina najkraćeg puta od vrha 1 do vrha T. (Budući da se svaki put koji treba razmotriti sastoji od lukova, a postoji konačan broj lukova, a svaki luk ulazi najviše jednom, postoji konačno mnogo natjecatelja za najkraći put, a minimum od konačnog broja elemenata je uvijek dostignut .) Problem koji se razmatra je izračunati IZ(4) i indikaciju staze na kojoj je taj minimum postignut.
Za početne podatke prikazane na sl. 7 i tablici 4, samo jedna strelica ulazi u vrh 3, upravo iz vrha 1, a blizu te strelice nalazi se njezina duljina jednaka 1, dakle IZ(3) = 1. Štoviše, očito je da IZ(1) = 0.
Do vrha 4 možete doći ili iz vrha 2, prešavši put jednak 4, ili iz vrha 5, prešavši put jednak 5. Prema tome, relacija
IZ(4) = min(S(2) + 4; IZ(5) + 5}.
Time je izvršeno restrukturiranje (pojednostavljenje) problema - nalaz S(4) sveden je na nalaz S(2) i IZ(5).
Do vrha 5 možete doći ili iz vrha 3, prešavši put jednak 2, ili iz vrha 6, prešavši put jednak 3. Prema tome, relacija
IZ(5) = min ( IZ(3) + 2; IZ(6) + 3}.
Mi to znamo IZ(3) = 1. Prema tome
S(5) = min(3; IZ(6) + 3}.
Kako je očito da je C(6) pozitivan broj, iz posljednje relacije slijedi da IZ(5) = 3.
Do vrha 2 možete doći ili iz vrha 1, prešavši put jednak 7, ili iz vrha 3, prešavši put jednak 5, ili iz vrha 5, prešavši put jednak 2. Prema tome, relacija
IZ(2) = min (S(1) + 7; S(3) + 5; IZ(5) + 2}.
Znamo da je S(1) = 0, IZ(3) = 1, IZ(5) = 3. Prema tome
IZ(2) = min(0 + 7; 1 + 5; 3 + 2) = 5.
Sada možemo pronaći IZ(4):
IZ(4) = min ( IZ(2) + 4; IZ(5) + 5) = min(5 + 4; 3 + 5) = 8.
Dakle, duljina najkraćeg puta je 8. Iz zadnje relacije jasno je da se mora ići do vrha 4 kroz vrh 5. Vratimo se na izračun IZ(5), vidimo da do vrha 5 moramo ići kroz vrh 3. A do vrha 3 možemo doći samo iz vrha 1. Dakle, najkraći put je sljedeći:
1 → 3 → 5 → 4 .
Problem najkraćeg puta za određene početne podatke (slika 7. i tablica 4.) u potpunosti je riješen.
Optimizacijski problemi na grafovima koji se javljaju tijekom pripreme upravljačke odluke u upravljanju proizvodnjom su vrlo raznolike. Kao primjer, razmotrite drugi problem vezan uz prijevoz.
Problem maksimalnog protoka. Kako (tj. kojim rutama) poslati maksimalnu moguću količinu robe od početne do krajnje točke, ako propusnost je li put između točaka ograničen?
Da bi se riješio ovaj problem, svakom luku usmjerenog grafa koji odgovara transportnom sustavu mora biti pridružen broj - kapacitet tog luka. Razmotrimo primjer (slika 8).
sl.8. Početni podaci za problem maksimalnog protoka
Početni podaci o transportnom sustavu, npr. unutartvorničkom, prikazanom na sl. 8, mogu se postaviti i u tablici (tablica 5).
Rješenje problema maksimalnog protoka može se dobiti iz sljedećih razmatranja.
Očito maksimalna propusnost transportni sustav ne prelazi 6, budući da se s početne točke 0 ne može poslati više od 6 jedinica tereta, odnosno 2 jedinice do točke 1, 3 jedinice do točke 2 i 1 jedinica do točke 3.
Tablica 5
Početni podaci za problem maksimalnog protoka
|
Polazište |
Odredište |
Širina pojasa |
Dalje, potrebno je osigurati da svih 6 jedinica tereta koje napuštaju točku 0 dođu do konačne točke 4. Očito, 2 jedinice tereta koje su stigle u točku 1 mogu se izravno poslati u točku 4. Roba koja je stigla u točku 2 imat će podijeliti: 2 jedinice odmah poslane u točku 4, a 1 jedinica - u međutočku 3 (zbog ograničenog kapaciteta dionice između točaka 2 i 4). Na točku 3 isporučeni su sljedeći tereti: 1 jedinica iz točke 0 i 1 jedinica iz točke 2. Šaljemo ih na točku 4.
Dakle, maksimalni kapacitet transportnog sustava koji se razmatra je 6 jedinica tereta. Istodobno se ne koriste unutarnji odsjeci (granovi) između točaka 1 i 2, kao i između točaka 1 i 3. Grana između točaka 1 i 4 nije potpuno opterećena - duž nje se šalju 2 jedinice tereta s propusnost 3 jedinice.
Rješenje se može prikazati u obliku tablice (tablica 6).
Tablica 6
Rješavanje problema maksimalnog protoka
|
Polazište |
Odredište |
Plan prijevoza |
Širina pojasa |
Problem linearnog programiranja za maksimiziranje protoka. Formulirajmo problem maksimalnog protoka u smislu linearnog programiranja. Neka X KM- obujam prometa od točke Do paragrafu M. Prema sl.8 Do = 0,1,2,3, M= 1,2,3,4, a prijevoz je moguć samo do točke s većim brojem. Dakle, ima ukupno 9 varijabli. X KM, naime, x 01 , x 02 , x 03 , x 12 , x 13 , x 14 , x 23 , x 24 , x 34 . Problem linearnog programiranja čiji je cilj maksimiziranje protoka ima oblik:
F→ max ,
x 01 + x 02 + X 03 = F (0)
- X 01 + x 12 + x 13 + x 14 = 0 (1)
- x 02 - X 12 + x 23 + x 24 = 0 (2)
- x 03 - x 13 - X 23 + x 34 = 0 (3)
- x 14 - x 24 - x 34 = -F (4)
x 01 ≤ 2
x 02 ≤ 3
x 03 ≤ 1
x 12 ≤ 4
x 13 ≤ 1
x 14 ≤ 3
x 23 ≤ 1
x 24 ≤ 2
x 34 ≤ 2
X KM ≥ 0 , K, M = 0, 1, 2, 3, 4
F ≥ 0 .
Ovdje F- funkcija cilja, uvjet (0) opisuje ulazak robe u prometni sustav. Uvjeti (1) - (3) postavljaju omjere ravnoteže za čvorove 1-3 sustava. Drugim riječima, za svaki od unutarnjih čvorova dolazni tok teret je jednak izlaznom toku, tereti se ne akumuliraju unutar sustava i ne "rađaju" se u njemu. Uvjet (4) je uvjet za "izlazak" robe iz sustava. Zajedno s uvjetom (0) čini omjer ravnoteže za sustav kao cjelinu ("input" je jednak "outputu"). Sljedećih devet nejednakosti postavlja ograničenja kapaciteta pojedinih "grana" transportnog sustava. Zatim se u sustavu ograničenja problema linearnog programiranja ukazuje na nenegativnost opsega prometa i funkcije cilja. Jasno je da posljednja nejednakost proizlazi iz oblika funkcije cilja (odnos (0) ili (4)) i nenegativnosti obujma prometa. Međutim, posljednja nejednakost nosi nešto opće informacije- ili pozitivna količina robe, ili nula (npr. ako postoji kretanje u krugu unutar sustava), ali ne negativna (nema ekonomskog smisla, ali formalni matematički model za to "ne zna" ) može se proći kroz sustav.
O raznolikosti optimizacijskih problema. U različitim problemima odlučivanja pojavljuje se veliki broj problema optimizacije. Za njihovo rješavanje koristi se jedna ili druga metoda, točna ili približna. Problemi optimizacije često se koriste u teorijskim i ekonomskim studijama. Dovoljno je prisjetiti se optimizacije gospodarskog rasta zemlje korištenjem input-output matrice Wassilyja Leontijeva ili mikroekonomskih problema određivanja optimalnog obujma outputa u smislu troškovne funkcije pri fiksnoj cijeni (ili pod monopolskim uvjetima) ili minimiziranja troškova za zadani obujam outputa odabirom optimalnog omjera faktora proizvodnje (uzimajući u obzir plaćanje za njih).
Uz gore navedene metode rješavanja problema optimizacije, podsjećamo da se glatke funkcije optimiziraju postavljanjem derivacije na 0 (za funkcije više varijabli, parcijalne derivacije). Ako postoje ograničenja, koriste se Lagrangeovi množitelji. Ove se metode obično podučavaju u naprednim tečajevima matematike i stoga su ovdje izostavljene.
Od interesa su problemi optimizacije s neizrazitim varijablama, kao i problemi optimizacije koji se javljaju u ekonometriji. O njima se raspravlja u relevantnoj literaturi.
Književnost
1. Gass S. Putovanje u zemlju linearnog programiranja / Per. s engleskog. - M.: Mir, 1973. - 176 str.
2. Kofman A., Fore R. Učinimo istraživačke operacije / Per. s francuskog - M: Mir, 1966. -280 str.
3. Belov V.V., Vorobyov E.M., Shatalov V.E. Teorija grafova. - M.: Viša škola, 1976. - 392 str.
4. Burkov V.N., Zalozhnev A.Yu., Novikov D.A. Teorija grafova u upravljanju organizacijskim sustavima. – M.: Sinteg, 2001. – 124 str.
5. Orlov A.I. Problemi optimizacije i neizrazite varijable. - M.: Znanje, 1980. - 64 str.
6. Orlov A.I. Ekonometrija. - M .: Izdavačka kuća "Ispit", 2002. - 576 str.
Zadaci po metodama odlučivanja
1. Nacrtajte problem linearnog programiranja na ravnini ograničenja i riješite ga (grafički):
400 W 1 + 450 W 2 → min ,
5 W 1 + 10 W 2 ≥ 45,
20 W 1 + 15 W 2 ≥ 80,
W 1 ≥ 0, W 2 ≥ 0.
2. Riješite problem linearnog programiranja:
W 1 + 5 W 2 → max,
0,1 W 1 + W 2 ≤ 3,8 ,
0,25 W 1 + 0,25 W 2 ≤ 4,2 ,
W 1 ≥ 0, W 2 ≥ 0.
3. Riješite problem cjelobrojnog programiranja:
10 x + 5 Na→ maks.
8x + 3 Na ≤ 40,
3 x + 10 Na ≤ 30,
x ≥ 0 , Na ≥ 0 , x i Y su cijeli brojevi.
4. Riješite problem s naprtnjačom:
x 1 + X 2 + 2 X 3 + 2 x 4 + X 5 + X 6 → max,
0,5x 1 +x 2 + 1,5 x 3 + 2x 4 + 2,5x 5 + 3x 6 ≤ 3.
Kontrolni parametri X k,k= 1,2,…, 6 , uzimaju vrijednosti iz skupa koji sadrži dva elementa - 0 i 1.
5. Prometna mreža (s naznakom udaljenosti) prikazana je na slici 9. Pronađite najkraći put od točke 1 do točke 4.
|
|
Sl.9. Početni podaci za problem najkraćeg puta.
7. Riješite problem trgovačkog putnika za četiri grada (ruta mora biti zatvorena i bez uzvratnih posjeta). Putni troškovi prikazani su u tablici 7.
Tablica 7
Početni podaci za problem trgovačkog putnika
|
Grad polaska |
Grad odredišta |
Putni troškovi |
8. Kako poslati maksimalnu količinu tereta od početne točke 1 do krajnje točke 8, ako je kapacitet staza između točaka transportne mreže (slika 10) ograničen (tablica 8)?
Sl.9. Prometna mreža do problema maksimalnog protoka.
Tablica 8
Početni podaci za problem maksimalnog protoka
|
Polazište |
Odredište |
Širina pojasa |
Teme izvješća i sažetaka
1. Klasifikacija optimizacijskih problema odlučivanja.
2. Pareto optimalna rješenja.
3. Problemi višekriterijskog odlučivanja: različite metode konvolucije kriterija.
4. Problemi optimizacije i neizrazite varijable (na temelju rada).
5. Simulacija i stručna mišljenja prilikom donošenja odluka.
6. Interaktivni sustavi odlučivanja.
7. Metode uzimanja u obzir nesigurnosti odlučivanja: probabilistički modeli, neizrazita teorija, intervalna matematika.
8. Ekonometrijske metode odlučivanja (na temelju monografije).
9. Simulacijsko modeliranje i metoda statističkog ispitivanja (Monte Carlo) u odlučivanju.
11. Metode teorije igara (teorija sukoba), uloga informacije i Nashove ravnoteže u teoriji odlučivanja.
12. Problemi kombinirane primjene različitih metoda u konkretnom primijenjenom radu.
13. Informatička podrška odlučivanju.
| Prethodno |
