Konveksni skupovi i njihova svojstva. Da bi se proučavala svojstva konveksnog skupa, potrebno je dati striktnu definiciju konveksnog skupa. Ranije je konveksan skup bio definiran kao skup koji, zajedno sa bilo koje dvije svoje tačke, sadrži segment koji ih povezuje.

Generalizacija koncepta segmenta za nekoliko tačaka je njihova konveksna linearna kombinacija.

Tačka X se zove konveksna linearna kombinacija bodova, ako su uslovi ispunjeni

Skup tačaka je konveksan, ako ono, zajedno sa bilo koje dvije svoje točke, sadrži njihovu proizvoljnu konveksnu, linearnu kombinaciju.

Možemo dokazati sljedeću teoremu o reprezentaciji konveksnog poliedra.

Teorema 1.1. Konveksni n-dimenzionalni poliedar je konveksna linearna kombinacija njegovih kutnih tačaka.

Iz teoreme 1.1 proizilazi da je konveksni poliedar generisan njegovim uglovima ili vrhovima: segment sa dve tačke, trougao sa tri, tetraedar sa četiri tačke, itd. Istovremeno, konveksna poliedarska oblast, budući da je neograničen skup, nije jednoznačno definisana svojim ugaonim tačkama: nijedna od njegovih tačaka ne može biti predstavljena kao konveksna linearna kombinacija uglovnih tačaka.

Svojstva problema linearnog programiranja. Prethodno su razmatrani različiti oblici problema linearnog programiranja i pokazano je da se svaki problem linearnog programiranja može predstaviti kao opšti ili kanonski problem.

Da bismo potkrijepili svojstva problema linearnog programiranja i metode za njegovo rješavanje, preporučljivo je razmotriti još dva tipa notacije kanonskog problema.

Obrazac za matrix snimanje:

Evo WITH– matrica reda, A– sistemska matrica, X– matrica-kolona varijabli, IN– matrica-kolona slobodnih članova:

Vektorski oblik snimanja:

gdje vektori odgovaraju stupcima koeficijenata za nepoznate.

Formulisano je gore, ali nije dokazano u opšti pogled sledeća teorema.

Teorema 1.2. Skup svih izvodljivih rješenja za sistem ograničenja problema linearnog programiranja je konveksan.

dokaz: Neka - dva izvodljiva rješenja PLP-a, data u matričnom obliku. Onda . Razmotrimo konveksnu linearnu kombinaciju rješenja, tj.

i pokažu da je i to dopušteno rješenje sistema (1.3). Zaista

tj. rješenje X zadovoljava sistem (1.3). Ali od tada X>0, tj. rješenje zadovoljava uslov nenegativnosti.

Dakle, dokazano je da je skup svih izvodljivih rješenja za problem linearnog programiranja konveksan, tačnije, on predstavlja konveksni poliedar ili konveksno poliedarsko područje, koje ćemo dalje zvati jednim pojmom - poliedar rješenja.

Odgovor na pitanje u kojoj tački poliedra rješenja je moguć optimalno rešenje Problem linearnog programiranja je dat u sljedećoj fundamentalnoj teoremi.

Teorema 1.3. Ako problem linearnog programiranja ima optimalno rješenje, tada linearna funkcija uzima svoju maksimalnu vrijednost u jednoj od kutnih tačaka poliedra rješenja. Ako linearna funkcija uzima maksimalnu vrijednost u više od jedne kutne točke, tada je uzima u bilo kojoj tački koja je konveksna linearna kombinacija ovih tačaka.

dokaz: Pretpostavit ćemo da je poliedar rješenja ograničen. Označimo njegove kutne tačke sa , a optimalno rješenje je gotovo X*. Onda F(X*)³ F(X) za sve bodove X poliedar rješenja. Ako X* je tačka ugla, onda je prvi dio teoreme dokazan.

Pretvarajmo se to X* nije ugaona tačka, dakle, na osnovu teoreme 1.1 X* može se predstaviti kao konveksna linearna kombinacija ugaonih tačaka poliedra rješenja, tj.

Jer F(X) je linearna funkcija, dobijamo

U ovoj dekompoziciji biramo maksimum između vrijednosti. Neka odgovara tački ugla X k(1 £ k£ R); označimo ga sa M, one. . Zamenimo svaku vrednost u izrazu (1.5) ovom maksimalnom vrednošću M. Onda

Po pretpostavci X* je optimalno rješenje, dakle, s jedne strane, ali, s druge strane, to je i dokazano
F(X*)£ M, dakle, , gdje X k– ugaona tačka. Dakle, postoji ugaona tačka X k, u kojem linearna funkcija poprima svoju maksimalnu vrijednost.

Da bismo dokazali drugi dio teoreme, pretpostavimo da ciljna funkcija uzima maksimalnu vrijednost u više od jedne kutne tačke, na primjer, u tačkama , Gdje , Onda

Neka X– konveksna linearna kombinacija ovih kutnih tačaka, tj.

U ovom slučaju, s obzirom da je funkcija F(X)– linearni, dobijamo

one. linearna funkcija F uzima maksimalnu vrijednost u proizvoljnoj tački X, što je konveksna linearna kombinacija kutnih tačaka.

Komentar. Zahtjev da je poliedar rješenja ograničen u teoremi je bitan, jer u slučaju neograničene poliedarske regije, kao što je navedeno u teoremi 1.1, ne može svaka tačka takvog područja biti predstavljena konveksnom linearnom kombinacijom njegovih kutnih tačaka.

Dokazana teorema je fundamentalna, jer ukazuje na fundamentalni način rješavanja problema linearnog programiranja. Zaista, prema ovoj teoremi, umjesto proučavanja beskonačnog skupa izvodljivih rješenja da bi se među njima pronašlo željeno optimalno rješenje, potrebno je proučavati samo konačan broj kutnih tačaka poliedra rješenja.

Sljedeća teorema je posvećena analitičkoj metodi pronalaženja kutnih tačaka.

Teorema 1.4. Svako dopušteno osnovno rješenje problema linearnog programiranja odgovara kutnoj tački poliedra rješenja, i obrnuto, svakoj ugaonoj tački poliedra rješenja odgovara dopušteno osnovno rješenje.

dokaz: Neka je dopušteno osnovno rješenje sistema ograničenja LLP (1.4), u kojem je prvo T komponenta su glavne varijable i ostalo p - t komponenta – ne-glavne varijable jednake nuli u osnovnom rješenju (ako to nije slučaj, tada se odgovarajuće varijable mogu prenumerisati). Pokažimo to X

Pretpostavimo suprotno, tj. Šta X nije ugaona tačka. Onda pokažite X može se predstaviti unutrašnjom tačkom segmenta koji povezuje dva različita segmenta koji se ne poklapaju X, bodova

drugim riječima, konveksna linearna kombinacija tačaka poliedar rješenja, tj.

gdje (pretpostavljamo da , jer u suprotnom tačka X poklapa se sa tačkom X 1 ili X 2).

Zapišimo vektorsku jednakost (1.6) u koordinatnom obliku:

Jer sve varijable i koeficijenti su nenegativni, zatim od posljednjeg p-t jednakosti slijedi da , tj. u odlukama X 1 , X 2 i X sistem jednačina (1.4) vrijednosti p - t komponente su u ovom slučaju jednake nuli. Ove komponente se mogu smatrati vrijednostima neprimarnih varijabli. Ali vrijednosti ne-osnovnih varijabli na jedinstven način određuju vrijednosti glavnih, dakle,

Dakle sve P komponenta u rastvorima X 1 , X 2 i X poklapaju, a samim tim i tačke X 1 i X 2 spajanje, što je u suprotnosti sa pretpostavkom. dakle, X– kutna tačka poliedra rješenja.

Hajde da dokažemo obrnutu tvrdnju. Neka je kutna točka rješenja poliedra i njegova prva T koordinate su pozitivne. Pokažimo to X– dopustivo osnovno rješenje. nije tačka ugla, što je u suprotnosti sa uslovom. Stoga je naša pretpostavka netačna, tj. vektori su linearno nezavisni i X je dopustivo osnovno rješenje problema (1.4).

Važan zaključak direktno slijedi iz teorema 1.3 i 1.4: ako problem linearnog programiranja ima optimalno rješenje, onda se ono poklapa, prema najmanje, sa jednim od svojih prihvatljivih osnovnih rješenja.

dakle, optimalno linearna funkcija Probleme linearnog programiranja treba tražiti između konačnog broja njegovih izvodljivih osnovnih rješenja.

Razmotrimo glavni problem linearnog programiranja (LPLP): pronađite nenegativne vrijednosti varijabli x1, x2, ..., xn, koje zadovoljavaju m uslova - jednakosti

i maksimiziranje linearne funkcije ovih varijabli

Radi jednostavnosti, pretpostavljamo da su svi uslovi (1) linearno nezavisni (r=m), i mi ćemo svoje rezonovanje voditi pod ovom pretpostavkom.

Dopustivim rješenjem OLP-a nazovimo bilo koji skup nenegativnih vrijednosti x1, x2, ..., xn koji zadovoljava uslove (1), a optimalnim nazovimo ono od dopuštenih rješenja koje maksimizira funkciju (2). Moramo pronaći optimalno rješenje.

Da li ovaj problem uvijek ima rješenje? Ne, ne uvek.

ZLP je nerješiv (nema optimalno rješenje):

Zbog nekompatibilnosti sistema ograničenja. One. sistem nema jedinstveno rešenje, kao što je prikazano na slici 1.

Slika 1 – Nedosljednost sistema ograničenja

Zbog neograničenosti funkcije cilja na skupu rješenja. Drugim riječima, pri rješavanju LLP-a na max vrijednost ciljne funkcije teži beskonačnosti, a u slučaju LLP-a na min - minus beskonačnosti, kao što je prikazano na slici 2.

Slika 2 - Neograničenost funkcije cilja na skupu rješenja

ZLP je rješiv:

Skup rješenja sastoji se od jedne tačke. Takođe je optimalan, kao što je prikazano na slici 3.

Slika 3 - Skup rješenja sastoji se od jedne tačke

Jedino optimalno rješenje za ZLP. Prava linija koja odgovara ciljnoj funkciji na graničnoj poziciji seče se sa skupom rješenja u jednoj tački, kao što je prikazano na slici 4.

Slika 4 – Jedino optimalno rješenje

Optimalno rješenje ZLP-a nije jedinstveno. Vektor N je okomit na jednu od stranica skupa rješenja. U ovom slučaju, bilo koja tačka na segmentu AB je optimalna, kao što je prikazano na slici 5.

Slika 5 – Optimalno rješenje nije jedinstveno

Rješavanje problema linearnog programiranja primjenom simpleks metode

Simpleks metoda je algoritam za rješavanje LP problema koji implementira nabrajanje kutnih tačaka regije izvodljivih rješenja u pravcu poboljšanja vrijednosti ciljne funkcije C. Simpleks metoda je glavna u linearnom programiranju.

Upotreba ove metode u diplomskom projektu za rješavanje problema LP je posljedica sljedećih faktora:

Metoda je univerzalna, primjenjiva na bilo koji problem linearnog programiranja u kanonskom obliku;

Algoritamska priroda metode omogućava da se ona uspješno programira i implementira korištenjem tehničkih sredstava.

Ekstremum ciljne funkcije se uvijek postiže na uglovima područja izvodljivih rješenja. Prije svega, nađe se neko izvodljivo početno (referentno) rješenje, tj. bilo koju ugaonu tačku regije izvodljivih rješenja. Postupak metode omogućava vam da odgovorite na pitanje da li je ovo rješenje optimalno. Ako da, onda je problem riješen. Ako je „ne“, onda se vrši prijelaz na susjednu kutnu tačku regije izvodljivih rješenja, gdje se vrijednost ciljne funkcije poboljšava. Proces nabrajanja uglovnih tačaka regiona izvodljivih rešenja se ponavlja dok se ne pronađe tačka koja odgovara ekstremumu ciljne funkcije.

Budući da je broj vrhova poliedra ograničen, u konačnom broju koraka garantovano je pronaći optimalnu vrijednost ili utvrditi činjenicu da je problem nerješiv.

Sistem ograničenja ovdje je sistem linearnih jednačina u kojima je broj nepoznatih veća količina jednačine. Ako je rang sistema jednak, tada je moguće odabrati nepoznanice koje se izražavaju u terminima preostalih nepoznanica. Da bismo bili sigurni, obično se pretpostavlja da su odabrane prve uzastopne nepoznanice. Ove nepoznanice (varijable) se nazivaju osnovnim, ostale su besplatne. Broj osnovnih varijabli je uvijek jednak broju ograničenja.

Dodeljivanjem određenih vrednosti slobodnim varijablama i izračunavanjem vrednosti osnovnih (izraženih u terminima slobodnih) dobijaju se različita rešenja sistema ograničenja. Posebno su zanimljiva rješenja dobijena u slučaju kada su slobodne varijable jednake nuli. Takva rješenja se nazivaju osnovnim. Osnovno rješenje naziva se dopušteno osnovno rješenje ili potporno rješenje ako su vrijednosti njegovih varijabli nenegativne. Ispunjava sva ograničenja.

Imajući sistem ograničenja, pronalazi se bilo koje osnovno rješenje za ovaj sistem. Ako se prvo nađeno osnovno rješenje pokaže izvodljivim, onda se provjerava optimalnost. Ako nije optimalno, onda se prelazi na drugo izvodljivo osnovno rješenje.

Simpleks metoda garantuje da će se ovim novim rješenjem linearni oblik, ako ne dosegne optimalni, približiti. Isto rade s novim izvodljivim osnovnim rješenjem dok ne pronađu rješenje koje je optimalno.

Ako se prvo nađeno osnovno rješenje pokaže neprihvatljivim, onda se primenom simpleks metode vrši prijelaz na druga osnovna rješenja, sve dok se u nekom koraku rješenja osnovno rješenje ne pokaže prihvatljivim ili se može izvesti zaključak o nedosljednosti sistema ograničenja.

Dakle, primjena simpleks metode podijeljena je u dvije faze:

Pronalaženje prihvatljivog osnovnog rješenja za sistem ograničenja ili utvrđivanje činjenice njegove nedosljednosti;

Pronalaženje optimalnog rješenja u slučaju kompatibilnosti sistema ograničenja.

Algoritam za prelazak na sljedeće izvodljivo rješenje je sljedeći:

U redu koeficijenata ciljne funkcije odabire se najmanji negativni broj pri pronalaženju maksimuma. Redni broj koeficijenta je . Ako ga nema, onda je originalno osnovno rješenje optimalno;

Među elementima matrice s brojem stupca (ova kolona se naziva vodeći ili razrješavajući stupac) odabiru se pozitivni elementi. Ako ih nema, onda je ciljna funkcija neograničena u rasponu dozvoljenih vrijednosti varijabli i problem nema rješenja;

Među odabranim elementima vodeće kolone matrice, odabire se onaj za koji je vrijednost omjera odgovarajućeg slobodnog člana prema ovom elementu minimalna. Ovaj element se naziva vodeći, a linija u kojoj se nalazi naziva se vodeći;

Osnovna varijabla koja odgovara redu vodećeg elementa mora se prenijeti u kategoriju slobodnih, a slobodna varijabla koja odgovara stupcu vodećeg elementa mora se unijeti u broj osnovnih. Konstruira se novo rješenje koje sadrži nove brojeve osnovnih varijabli.

Uslov za optimalnost plana pri maksimalnom rešavanju problema: među koeficijentima funkcije cilja nema negativnih elemenata.

Izvršena je optimizacija linearnih modela u MS Excel-u simpleks metoda- svrsishodno traženje referentnih rješenja za problem linearnog programiranja. Algoritam simpleks metode svodi se na konstruiranje konveksnog poliedra u višedimenzionalnom prostoru, a zatim nabrajanje njegovih vrhova kako bi se pronašla ekstremna vrijednost ciljna funkcija.

Efikasna sredstva linearno programiranječine osnovu i celobrojnog i nelinearnog programiranja za rešavanje složenijih problema optimizacije. Ove metode, međutim, zahtijevaju duže vrijeme izračunavanja.

U narednim predavanjima će se detaljno govoriti o primjerima rješavanja tipičnih problema optimizacije i donošenja upravljačkih odluka korištenjem MS Excel dodatka „Traži rješenje“. Zadaci koje ovaj alat najbolje rješava imaju tri glavna svojstva:

• postoji jedan cilj, funkcionalno vezan za ostale parametre sistema, koji treba optimizirati (da se pronađe njegov maksimum, minimum ili određena brojčana vrijednost);
• postoje ograničenja koja se obično izražavaju u obliku nejednakosti (na primjer, količina upotrijebljenih sirovina ne može premašiti zalihe sirovina u skladištu, ili radno vrijeme mašine dnevno ne smije biti duže od 24 sata minus održavanje vrijeme);
• postoji skup vrijednosti ulaznih varijabli koje utječu na optimizirane vrijednosti i ograničenja.

Parametri zadataka su ograničeni na sljedeće granične indikatore:

• broj nepoznatih – 200;
• broj formulačkih ograničenja na nepoznate – 100;
• broj graničnih uslova za nepoznate je 400.

Algoritam za pronalaženje optimalnih rješenja uključuje nekoliko faza:

• pripremni rad;
• otklanjanje grešaka u rešenju;
• analiza rješenja.

Redoslijed potrebnih pripremnih radova pri rješavanju zadataka ekonomsko-matematičkog modeliranja pomoću MS Excel-a prikazan je na blok dijagramu na slici 1.6.

Rice. 1.6.

Od pet tačaka pripremnog plana rada, samo peta tačka je formalizovana. Ostatak posla zahtijeva kreativnost – a različiti ljudi to mogu učiniti na različite načine. Objasnimo ukratko suštinu formulacije stavki plana.

Prilikom postavljanja problema poznati su ciljni koeficijenti i normalizirani koeficijenti. U prethodnom primjeru, koeficijenti koji formiraju funkciju cilja bili su vrijednosti normalizirane dobiti po polici tipa ( ) i jednu vrstu police ( ). Normalizirani koeficijenti su norme utroška materijala i strojnog vremena po polici svake vrste. Matrica je izgledala ovako:

Osim toga, vrijednosti resursa su uvijek poznate. U prethodnom primjeru, ovo je bila sedmična zaliha ploča i mogućnost korištenja mašinskog vremena: , . Često u problemima vrijednosti varijabli moraju biti ograničene. Stoga je potrebno odrediti donju i gornju granicu raspona njihovih promjena.

Dakle, u dijaloškom okviru programa za optimizaciju "Traži rješenje" moramo postaviti sljedeći ciljni algoritam:

Ciljna funkcija je jednaka umnošku vektora željenih vrijednosti varijabli sa vektorom ciljnih koeficijenata

Normalizirani koeficijenti za vektor traženih vrijednosti varijabli ne bi trebali prelaziti vrijednost datog vektora resursa

Vrijednosti varijable moraju biti unutar navedenih granica broja početnih elemenata sistema

Broj početnih elemenata sistema

Broj specificiranih tipova resursa

Otklanjanje grešaka rješenja je neophodno kada program prikaže poruku o negativnim rezultatima (slika 1.7):

Rice. 1.7.

• ako se ne dobije prihvatljivo rješenje, prilagodite izvorni model podataka;
• ako nije primljeno optimalno rešenje, zatim uvesti dodatna ograničenja.

Problemi sa programom optimalno rešenje samo za model stvarnog problema, a ne za rješenje samog problema. Prilikom konstruisanja modela napravljene su razne pojednostavljujuće pretpostavke o stvarnoj situaciji. To je omogućilo formalizaciju procesa, približno prikazujući stvarne kvantitativne odnose između parametara sistema i cilja. A ako se stvarni parametri razlikuju od onih uključenih u model, kako će se rješenje promijeniti? Da bi se to saznalo, prije donošenja upravljačke odluke, provodi se analiza modelskog rješenja.

Analiza optimalno rešenje, ugrađen u program, predstavlja završnu fazu matematičkog modeliranja ekonomskih procesa. Omogućava dublju provjeru usklađenosti modela sa procesom, kao i pouzdanost optimalnog rješenja. Zasnovan je na podacima optimalno rešenje i izvještaje koji se izdaju u okviru „Traganje za rješenjem“. Ali to ne isključuje niti zamjenjuje tradicionalnu analizu plana iz ekonomske perspektive prije donošenja upravljačke odluke.

Ekonomska analiza ima sljedeće ciljeve:

• utvrđivanje mogućih posledica u sistemu u celini i njegovim elementima pri promeni parametra modela;
• procjena stabilnosti optimalnog plana na promjene pojedinih parametara problema: ako nije stabilan na promjene većine parametara, smanjuje se garancija njegove implementacije i postizanja izračunatog optimuma;
• izvođenje varijantnih proračuna i dobijanje novih planskih opcija bez ponovnog rješavanja problema sa prvobitne osnove korištenjem prilagođavanja.

Moguće metode analize prikazane su na dijagramu na slici 1.8.

Nakon dobijanja optimalnog rješenja, ono se analizira na osnovu primljenih izvještaja. Analiza stabilnosti- proučavanje utjecaja promjena u pojedinim parametrima modela na indikatore optimalnog rješenja. Limit Analysis- analiza dozvoljenih promjena u optimalnom planu, pri čemu plan ostaje optimalan.

S obzirom na odgovornost prihvatanja ekonomskih odluka menadžmenta, menadžer se mora pobrinuti da dobijeni optimalni plan bude jedini ispravan. Da biste to učinili, na osnovu modela potrebno je dobiti odgovore na sljedeća pitanja:

• "šta se desi ako..."
• "šta je potrebno za..."

Poziva se analiza za odgovor na prvo pitanje varijantna analiza; analiza za odgovor na drugo pitanje se zove prilagođena rješenja.

Analiza varijanti može biti sljedećih tipova:

• Parametrijski- analiza, koja se sastoji u rješavanju problema za različite vrijednosti određenog parametra.
• Strukturna analiza- kada se rješenje problema optimizacije traži pod drugačijom strukturom ograničenja.
• Višekriterijumska analiza je rješenje problema korištenjem različitih ciljnih funkcija.
• Analiza sa uslovnim početnim podacima- kada početni podaci koji se koriste za rješavanje problema zavise od ispunjavanja dodatnih uslova.

Nakon analize, rezultate treba prikazati u grafičkom obliku i sastaviti izvještaj sa preporukama za donošenje odluka uzimajući u obzir specifičnu ekonomsku situaciju.

Trenutno obrazovni program specijalnosti vezanih za ekonomiju, finansije i menadžment uključuje disciplinu pod nazivom „Metode optimalnih odluka“. U okviru ove discipline studenti izučavaju matematičku stranu optimizacije, istraživanje operacija, donošenje odluka i modeliranje. glavna karakteristika Ova disciplina je određena zajedničkim proučavanjem matematičkih metoda sa njihovom primjenom u rješavanju ekonomskih problema.

Zadaci optimizacije: opće informacije

Ako uzmemo u obzir opći slučaj, onda je smisao problema optimizacije pronaći takozvano optimalno rješenje koje maksimizira (minimizira) ciljnu funkciju pod određenim uvjetima ograničenja.

Ovisno o svojstvima funkcija, problemi optimizacije se mogu podijeliti u dvije vrste:

• problem linearnog programiranja (sve funkcije su linearne);
• problem nelinearnog programiranja (barem jedna od funkcija nije linearna).

Posebni slučajevi optimizacijskih problema su problemi frakciono-linearnog, dinamičkog i stohastičkog programiranja.

Najviše proučavani problemi optimizacije su problemi linearnog programiranja (LPP), čija rješenja imaju samo cjelobrojne vrijednosti.

JPP: formulacija, klasifikacija

Problem linearnog programiranja u opštem slučaju sastoji se od pronalaženja minimuma (maksimuma) linearne funkcije pod određenim linearnim ograničenjima.

Opšti ZLP je problem forme

pod ograničenjima

gdje su varijable, su dati realni brojevi, su ciljna funkcija, su plan problema, (*)-(***) su ograničenja.

Važna karakteristika ZLP-a je da se ekstremum funkcije cilja postiže na granici područja izvodljivih rješenja.

Praktične ekonomske primjene metoda optimalnog rješenja nalaze se u rješavanju problema sljedećih vrsta:

• problemi s mješavinama (tj. planiranje sastava proizvoda);
• problemi optimalne alokacije resursa u planiranju proizvodnje;

PAP: primjeri

Problem sa mešavinom

Rješenje problema mješavina sastoji se u pronalaženju najjeftinijeg skupa, koji se sastoji od određenih polaznih materijala koji daju mješavinu željenih svojstava.

Problem alokacije resursa

Kompanija proizvodi n raznih proizvoda čija je proizvodnja potrebna m razne vrste resursa. Rezerve korišćenih resursa su ograničene i iznose respektivno b 1, b 2,…, b m c.u. Osim toga, poznati su i tehnološki koeficijenti a ij, koji pokazuju koliko jedinica i-ti resurs je potreban za proizvodnju jedne jedinice proizvoda j-ti tip (). Dobit koju preduzeće ostvaruje prodajom proizvoda j-ti tip, iznosi c j novčane jedinice Neophodno je izraditi plan proizvodnje proizvoda čija će dobit preduzeća tokom realizacije biti najveća.

Problemi koji uključuju mješavine i alokaciju resursa često se pišu u obliku tabele.

Resursi	Potrebe			Rezerve
	B 1	…	Bn
A 1				b 1
…				…
Am				b m
Profit	c 1	…	c n

Problemi s mješavinom i alokacijom resursa mogu se riješiti na nekoliko načina:

• grafička metoda (u slučaju malog broja varijabli u matematički model);
• simpleks metoda (ako je broj varijabli u matematičkom modelu veći od dvije).

Transportni problem se odnosi na klasu zadataka koji imaju određenu specifičnu strukturu. Najjednostavniji transportni problem je problem transporta proizvoda do odredišta od mjesta polaska na minimalni troškovi za transport svih proizvoda.

Radi jasnoće i lakše percepcije, stanje transportnog problema obično se zapisuje u sljedećoj tabeli:

Općenito, rješavanje transportnog problema provodi se u nekoliko faza:

• Faza I: izrada početnog referentnog plana;
• Faza II: provjera optimalnosti referentnog plana;
• Faza III: pojašnjenje referentnog plana ako nije optimalan.

Postoji nekoliko metoda za dobivanje početnog referentnog plana, na primjer, metoda sjeverozapadnog ugla, Vogelova metoda i metoda minimalnih troškova.

Plan se provjerava za optimalnost korištenjem potencijalne metode:

- za zauzete ćelije,
- za nezauzete ćelije.

Ako plan nije optimalan, onda se gradi ciklus i transport se preraspoređuje.

Zaključak

U okviru jednog članka nije moguće obuhvatiti cjelokupnu teoriju i praksu metoda optimalnog rješenja, stoga se razmatraju samo neke točke koje nam omogućavaju da damo opću predstavu o ovoj disciplini, problemima i metodama za njihovo rješavanje.

Osim toga, dobro je napomenuti da za provjeru dobijenih rješenja problema optimizacije možete vrlo efikasno koristiti dodatak “Solution Search” iz MS Excel paketa. Ali to je zapravo druga priča, kao i detaljno razmatranje metoda za rješavanje problema optimizacije.

Evo nekoliko udžbenika za proučavanje metoda optimalnih rješenja:

1. Bandi B. Osnove linearnog programiranja: Trans. sa engleskog – M.: Radio i veze, 1989. – 176 str.
2. Kremer N.Sh. Operacijska istraživanja u ekonomiji: Proc. priručnik za univerzitete / N.Sh. Kremer, B.A. Putko, I.M. Trišin, M.N. Friedman; Ed. prof. N.Sh. Kremer. – M.: JEDINSTVO, 2005. – 407 str.

Rješenje prilagođenih metoda optimizacije

Možemo vam pomoći da riješite sve probleme koristeći optimalne metode rješenja. Na našoj web stranici možete naručiti rješenja za probleme. Potrebno je samo naznačiti rok i priložiti fajl sa zadatkom. Vaša narudžba je besplatna.

Linearno programiranje je grana matematike koja proučava metode za pronalaženje minimuma ili maksimuma linearne funkcije konačnog broja varijabli, pod uslovom da varijable zadovoljavaju konačan broj ograničenja u obliku linearnih jednačina ili linearnih nejednačina.

Dakle, opći problem linearnog programiranja (GLP) može se formulirati na sljedeći način.

Pronađite vrijednosti realnih varijabli za koje ciljna funkcija

uzima minimalnu vrijednost na skupu tačaka čije koordinate zadovoljavaju sistem ograničenja

Kao što je poznato, uređena zbirka vrijednosti n varijable , , … je predstavljen tačkom u n-dimenzionalnom prostoru. U nastavku ćemo označiti ovu tačku X=( , , … ).

U matričnom obliku, problem linearnog programiranja može se formulirati na sljedeći način:

, A– matrica veličine,

Dot X=( , , … ), koji zadovoljava sve uslove, se poziva validna tačka . Poziva se skup svih dozvoljenih tačaka važeće područje .

Optimalno rješenje (optimalni plan) problem linearnog programiranja naziva se rješenje X=( , , … ), koji pripada dozvoljenom području i za koji je linearna funkcija Q uzima optimalnu (maksimalnu ili minimalnu) vrijednost.

Teorema. Skup svih izvodljivih rješenja za sistem ograničenja problema linearnog programiranja je konveksan.

Skup tačaka se zove konveksan , ako ono, zajedno sa bilo koje dvije svoje točke, sadrži njihovu proizvoljnu konveksnu linearnu kombinaciju.

Dot X pozvao konveksna linearna kombinacija bodova ako su ispunjeni uslovi

Skup svih izvodljivih rješenja za problem linearnog programiranja je konveksno poliedarsko područje, koje ćemo od sada zvati poliedar rješenja .

Teorema. Ako ZLP ima optimalno rješenje, onda ciljna funkcija uzima maksimalnu (minimalnu) vrijednost na jednom od vrhova poliedra rješenja. Ako ciljna funkcija uzima maksimalnu (minimalnu) vrijednost u više od jedne točke, tada uzima ovu vrijednost u bilo kojoj tački koja je konveksna linearna kombinacija ovih tačaka.

Među brojnim rješenjima sistema m linearne jednadžbe koje opisuju poliedar rješenja, razlikuju se tzv. osnovna rješenja.

Osnovno rješenje sistema m linearne jednadžbe sa n varijabli je rješenje u kojem sve n-m neosnovne varijable su nula. U problemima linearnog programiranja takva rješenja se nazivaju prihvatljiva osnovna rješenja (referentni planovi).

Teorema. Svako dopušteno osnovno rješenje problema linearnog programiranja odgovara vrhu poliedra rješenja, i obrnuto, svakom vrhu poliedra rješenja odgovara dopušteno osnovno rješenje.

Važan zaključak slijedi iz gornjih teorema:

Ako problem linearnog programiranja ima optimalno rješenje, onda se ono poklapa s barem jednim od njegovih izvodljivih osnovnih rješenja.

Prema tome, optimum linearne funkcije cilja problema linearnog programiranja mora se tražiti među konačnom broju njegovih izvodljivih osnovnih rješenja.