Konveksni skupovi i njihova svojstva. Da bismo proučavali svojstva konveksnog skupa, potrebno je dati strogu definiciju konveksnog skupa. Prethodno je konveksni skup definiran kao skup koji, zajedno s bilo koje dvije svoje točke, sadrži segment koji ih povezuje.

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

Točka X se zove konveksna linearna kombinacija bodova, ako su ispunjeni uvjeti

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

Možemo dokazati sljedeći teorem o prikazu konveksnog poliedra.

Teorem 1.1. Konveksni n-dimenzionalni poliedar je konveksna linearna kombinacija njegovih kutnih točaka.

Iz teorema 1.1 slijedi da je konveksni poliedar generiran svojim kutnim točkama ili vrhovima: isječak s dvije točke, trokut s tri, tetraedar s četiri točke itd. U isto vrijeme, konveksna poliedarska regija, budući da je neograničen skup, nije jednoznačno definirana svojim kutnim točkama: nijedna od njegovih točaka ne može se predstaviti kao konveksna linearna kombinacija kutnih točaka.

Svojstva problema linearnog programiranja. Prethodno su razmatrani različiti oblici problema linearnog programiranja i pokazano je da se bilo koji problem linearnog programiranja može prikazati kao opći ili kanonski problem.

Da bi se potkrijepila svojstva problema linearnog programiranja i metode za njegovo rješavanje, preporučljivo je razmotriti još dvije vrste notacije kanonskog problema.

Obrazac za snimanje matrice:

Ovdje S– matrica reda, A– matrica sustava, x– matrica-stupac varijabli, U– matrica-stupac slobodnih članova:

Vektorski oblik snimanja:

gdje vektori odgovaraju stupcima koeficijenata za nepoznanice.

Formulirano je gore, ali nije dokazano opći pogled sljedeći teorem.

Teorem 1.2. Skup svih mogućih rješenja sustava ograničenja problema linearnog programiranja je konveksan.

Dokaz: Neka - dva izvediva rješenja PLP-a, dana u matričnom obliku. Zatim . Razmotrimo konveksnu linearnu kombinaciju rješenja, tj.

i pokazati da je to i dopustivo rješenje sustava (1.3). Doista

tj. riješenje x zadovoljava sustav (1.3). Ali od , dakle x>0, tj. rješenje zadovoljava uvjet nenegativnosti.

Dakle, dokazano je da je skup svih mogućih rješenja problema linearnog programiranja konveksan, točnije, predstavlja konveksni poliedar ili konveksnu poliedarsku regiju, koju ćemo dalje zvati jednim pojmom - poliedar rješenja.

Moguć je odgovor na pitanje u kojoj točki poliedra rješenja optimalno rješenje problem linearnog programiranja dan je u sljedećem temeljnom teoremu.

Teorem 1.3. Ako problem linearnog programiranja ima optimalno rješenje, tada linearna funkcija poprima najveću vrijednost u jednoj od kutnih točaka poliedra rješenja. Ako linearna funkcija poprimi maksimalnu vrijednost u više od jedne kutne točke, tada je uzima u bilo kojoj točki koja je konveksna linearna kombinacija tih točaka.

Dokaz: Pretpostavit ćemo da je poliedar rješenja ograničen. Označimo njegove kutne točke s , a optimalno rješenje je kroz X*. Zatim F(X*)³ F(X) za sve točke x poliedar rješenja. Ako X* je kutna točka, tada je prvi dio teorema dokazan.

Hajdemo to pretvarati X* nije kutna točka, dakle, na temelju teorema 1.1 X* može se prikazati kao konveksna linearna kombinacija kutnih točaka poliedra rješenja, tj.

Jer F(X) je linearna funkcija, dobivamo

U ovoj dekompoziciji biramo najveću među vrijednostima. Neka odgovara kutnoj točki X k(1 £ k£ R); označimo to sa M, oni. . Zamijenimo svaku vrijednost u izrazu (1.5) ovom maksimalnom vrijednošću M. Zatim

Po pretpostavci x* je, dakle, s jedne strane optimalno rješenje, ali, s druge strane, dokazano je da
F(X*)£ M, dakle, , gdje X k– kutna točka. Dakle, postoji kutna točka X k, u kojem linearna funkcija poprima najveću vrijednost.

Da dokažemo drugi dio teorema, pretpostavimo da ciljna funkcija ima maksimalnu vrijednost u više od jedne kutne točke, na primjer, u točkama , Gdje , Zatim

Neka x– konveksna linearna kombinacija ovih kutnih točaka, tj.

U ovom slučaju, s obzirom da funkcija F(X)– linearno, dobivamo

oni. linearna funkcija F poprima najveću vrijednost u proizvoljnoj točki x, što je konveksna linearna kombinacija kutnih točaka.

Komentar. Zahtjev da poliedar rješenja bude ograničen u teoremu je bitan, jer u slučaju neograničene poliedarske regije, kao što je navedeno u teoremu 1.1, ne može se svaka točka takve regije predstaviti konveksnom linearnom kombinacijom njezinih kutnih točaka.

Dokazani teorem je temeljan jer ukazuje na temeljni način rješavanja problema linearnog programiranja. Doista, prema ovom teoremu, umjesto proučavanja beskonačnog skupa izvedivih rješenja kako bi se među njima pronašlo željeno optimalno rješenje, potrebno je proučavati samo konačni broj kutnih točaka poliedra rješenja.

Sljedeći teorem posvećen je analitičkoj metodi pronalaženja kutnih točaka.

Teorem 1.4. Svakom dopustivom osnovnom rješenju problema linearnog programiranja odgovara kutna točka poliedra rješenja, i obrnuto, svakoj kutnoj točki poliedra rješenja odgovara prihvatljivo bazno rješenje.

Dokaz: Neka je dopustivo osnovno rješenje sustava ograničenja LLP (1.4), u kojem je prvi T komponente su glavne varijable i ostalo p - t komponenta – neglavne varijable jednake nuli u osnovnom rješenju (ako to nije slučaj, tada se odgovarajuće varijable mogu prenumerirati). Pokažimo to x

Pretpostavimo suprotno, tj. Što x nije kutna točka. Zatim točka x može se prikazati unutarnjom točkom segmenta koji povezuje dva različita koji se ne podudaraju s X, bodova

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

gdje (pretpostavljamo da , jer inače točka x poklapa s toč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 je , tj. u odlukama x 1 , x 2 i x sustav jednadžbi (1.4) vrijednosti p - t komponente su u ovom slučaju jednake nuli. Ove komponente se mogu smatrati vrijednostima neprimarnih varijabli. Ali vrijednosti nebazičnih varijabli jedinstveno određuju vrijednosti glavnih, dakle,

Dakle sve P komponenta u rješenjima x 1 , x 2 i x podudaraju, a time i točke x 1 i x 2 spojiti, što je u suprotnosti s pretpostavkom. Stoga, x– kutna točka poliedra rješenja.

Dokažimo obrnutu tvrdnju. Neka bude kutna točka rješenja poliedra i njegova prva T koordinate su pozitivne. Pokažimo to x– dopušteno osnovno rješenje. nije kutna točka, što je u suprotnosti s uvjetom. Stoga je naša pretpostavka netočna, tj. vektori su linearno neovisni i x je prihvatljivo osnovno rješenje problema (1.4).

Važan korolar izravno slijedi iz teorema 1.3 i 1.4: ako problem linearnog programiranja ima optimalno rješenje, onda se ono podudara, prema barem, s jednim od njegovih dopuštenih osnovnih rješenja.

Tako, optimalno linearna funkcija Probleme linearnog programiranja treba tražiti među konačnim brojem njegovih izvedivih osnovnih rješenja.

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

i maksimiziranje linearne funkcije ovih varijabli

Radi jednostavnosti, pretpostavljamo da su svi uvjeti (1) linearno neovisni (r=m), i provest ćemo svoje razmišljanje pod tom pretpostavkom.

Nazovimo dopustivim rješenjem OLP-a svaki skup nenegativnih vrijednosti x1, x2, ..., xn koji zadovoljava uvjete (1). Optimalnim nazovimo ono od dopustivih rješenja koje maksimizira funkciju (2). Moramo pronaći optimalno rješenje.

Ima li ovaj problem uvijek rješenje? Ne, ne uvijek.

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

Zbog nekompatibilnosti sustava ograničenja. Oni. sustav nema jedno rješenje, kao što je prikazano na slici 1.

Slika 1 - Nekonzistentnost sustava ograničenja

Zbog neograničenosti funkcije cilja na skupu rješenja. Drugim riječima, kada se rješava LLP na max, vrijednost funkcije cilja teži beskonačnosti, au slučaju LLP 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 točke. Također je optimalno, kao što je prikazano na slici 3.

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

Jedino optimalno rješenje ZLP. Pravac koji odgovara funkciji cilja na graničnom položaju siječe se sa skupom rješenja u jednoj toč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 toč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 simpleks metodom

Simpleks metoda je algoritam za rješavanje LP problema koji implementira nabrajanje kutnih točaka područja mogućih rješenja u smjeru poboljšanja vrijednosti funkcije cilja C. Simpleks metoda je glavna u linearnom programiranju.

Korištenje ove metode u diplomskom projektu za rješavanje problema LP uzrokovano je sljedećim čimbenicima:

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

Algoritamska priroda metode omogućuje njezino uspješno programiranje i implementaciju tehničkim sredstvima.

Ekstrem funkcije cilja uvijek se postiže u kutnim točkama područja izvedivih rješenja. Najprije se pronađe neko izvodljivo početno (referentno) rješenje, tj. bilo kojoj kutnoj točki regije izvedivih rješenja. Postupak metode omogućuje vam da odgovorite na pitanje je li ovo rješenje optimalno. Ako da, onda je problem riješen. Ako je "ne", tada se prelazi na susjednu kutnu točku područja mogućih rješenja, gdje se vrijednost funkcije cilja poboljšava. Proces nabrajanja kutnih točaka područja izvodljivih rješenja ponavlja se sve dok se ne pronađe točka koja odgovara ekstremumu funkcije cilja.

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

Sustav ograničenja ovdje je sustav linearnih jednadžbi u kojima broj nepoznanica više količine jednadžbe. Ako je rang sustava jednak, tada je moguće odabrati nepoznanice koje su izražene preko preostalih nepoznanica. Da bismo bili sigurni, obično se pretpostavlja da su odabrane prve uzastopne nepoznanice. Te se nepoznanice (varijable) nazivaju osnovnima, ostale su slobodne. Broj osnovnih varijabli uvijek je jednak broju ograničenja.

Dodjeljivanjem određenih vrijednosti slobodnim varijablama i izračunavanjem vrijednosti osnovnih (izraženih preko slobodnih) dobivaju se različita rješenja sustava ograničenja. Posebno su zanimljiva rješenja dobivena u slučaju kada su slobodne varijable jednake nuli. Takva rješenja nazivaju se osnovnim. Osnovno rješenje se naziva dopustivo osnovno rješenje ili potporno rješenje ako su vrijednosti njegovih varijabli nenegativne. Zadovoljava sva ograničenja.

Imajući sustav ograničenja, može se pronaći bilo koje osnovno rješenje za ovaj sustav. Ako se prvo pronađeno osnovno rješenje pokaže izvedivim, tada se provjerava njegova optimalnost. Ako nije optimalno, tada se prelazi na drugo izvedivo osnovno rješenje.

Simpleks metoda jamči da će se ovim novim rješenjem linearna forma, ako ne postigne optimum, približiti istom. Isto rade s novim izvedivim osnovnim rješenjem dok ne nađu optimalno rješenje.

Ako se prvo pronađeno osnovno rješenje pokaže neprihvatljivim, tada se pomoću simpleks metode prelazi 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 nekonzistentnosti. sustava ograničenja.

Dakle, primjena simpleks metode podijeljena je u dvije faze:

Pronalaženje prihvatljivog osnovnog rješenja sustava ograničenja ili utvrđivanje činjenice njegove nekonzistentnosti;

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

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

U retku koeficijenata funkcije cilja odabire se najmanji negativni broj pri pronalasku maksimuma. Serijski broj koeficijenta je . Ako nema, tada je izvorno osnovno rješenje optimalno;

Među elementima matrice s brojem stupca (taj se stupac naziva vodeći ili razlučujući stupac) biraju se pozitivni elementi. Ako ih nema, tada je funkcija cilja neograničena u rasponu dopuštenih vrijednosti varijabli i problem nema rješenja;

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

Osnovnu varijablu koja odgovara retku vodećeg elementa potrebno je prebaciti u kategoriju slobodnih, a slobodnu varijablu koja odgovara stupcu vodećeg elementa unijeti u broj osnovnih. Konstruirano je novo rješenje koje sadrži nove brojeve osnovnih varijabli.

Uvjet optimalnosti plana pri maksimalnom rješavanju problema: među koeficijentima funkcije cilja nema negativnih elemenata.

Provedena je optimizacija linearnih modela u MS Excelu simpleks metoda- svrhovito traženje referentnih rješenja problema linearnog programiranja. Algoritam simpleksne 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.

Djelotvorna sredstva linearno programiranječine osnovu i cjelobrojnog i nelinearnog programiranja za rješavanje složenijih problema optimizacije. Ove metode, međutim, zahtijevaju duže vrijeme izračuna.

Naredna predavanja detaljno će obraditi primjere rješavanja tipičnih optimizacijskih problema 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 povezan s ostalim parametrima sustava, koji treba optimizirati (naći njegovu maksimalnu, minimalnu ili određenu numeričku vrijednost);
• postoje ograničenja, obično izražena u obliku nejednakosti (na primjer, količina upotrijebljenih sirovina ne smije premašiti zalihe sirovina u skladištu ili vrijeme rada stroja dnevno ne smije biti dulje od 24 sata minus održavanje vrijeme);
• postoji skup vrijednosti ulaznih varijabli koje utječu na optimizirane vrijednosti i ograničenja.

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

• broj nepoznanica – 200;
• broj formulacijskih ograničenja na nepoznanice – 100;
• broj ograničavajućih uvjeta za nepoznanice je 400.

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

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

Slijed potrebnih pripremnih radnji koje se izvode prilikom rješavanja problema ekonomsko-matematičkog modeliranja u MS Excelu prikazan je na blok dijagramu na slici 1.6.

Riža. 1.6.

Od pet točaka plana pripremnih radova samo je peta točka moguće formalizirati. Ostatak posla zahtijeva kreativnost – a različiti ljudi to mogu učiniti na različite načine. Objasnimo ukratko bit teksta stavki plana.

Pri postavljanju problema poznati su ciljni koeficijenti i normalizirani koeficijenti. U prethodnom primjeru, koeficijenti koji tvore funkciju cilja bili su vrijednosti normalizirane dobiti po polici vrste ( ) i jednu vrstu police ( ). Normirani koeficijenti bili su normativi 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 tjedna zaliha ploča i mogućnost korištenja strojnog 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 optimizacijskog programa "Traži rješenje" moramo postaviti sljedeći ciljni algoritam:

Ciljna funkcija jednaka je umnošku vektora željenih vrijednosti varijable s vektorom ciljnih koeficijenata

Normalizirani koeficijenti za vektor potrebnih vrijednosti varijabli ne bi smjeli premašiti vrijednost zadanog vektora resursa

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

Broj početnih elemenata sustava

Broj navedenih vrsta resursa

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

Riža. 1.7.

• ako se ne dobije prihvatljivo rješenje, tada prilagoditi izvorni model podataka;
• ako nije primljeno optimalno rješenje, zatim uvedite dodatna ograničenja.

Problemi s programom optimalno rješenje samo za model stvarnog problema, a ne rješenje samog problema. Prilikom konstruiranja modela napravljene su razne pojednostavljujuće pretpostavke o stvarnoj situaciji. To je omogućilo formaliziranje procesa, približno prikazujući stvarne kvantitativne odnose između parametara sustava 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 modelnog rješenja.

Analiza optimalno rješenje, ugrađen u program, predstavlja završnu fazu matematičkog modeliranja ekonomskih procesa. Omogućuje dublju provjeru usklađenosti modela s procesom, kao i pouzdanost optimalnog rješenja. Temelji se na podacima optimalno rješenje i izvješća koja se izdaju u “Potrazi 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:

• određivanje mogućih posljedica u sustavu kao cjelini i njegovim elementima pri promjeni parametra modela;
• procjena stabilnosti optimalnog plana na promjene pojedinih parametara problema: ako nije stabilan na promjene većine parametara, smanjuje se jamstvo njegove provedbe i postizanja izračunatog optimuma;
• izvođenje proračuna varijanti i dobivanje novih opcija plana bez ponovnog rješavanja problema iz izvorne osnove korištenjem prilagodbi.

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

Nakon dobivanja optimalnog rješenja, ono se analizira na temelju zaprimljenih izvješća. Analiza stabilnosti- proučavanje utjecaja promjena pojedinih parametara modela na pokazatelje optimalnog rješenja. Analiza granica- analiza dopuštenih promjena optimalnog plana, pri čemu plan ostaje optimalan.

S obzirom na odgovornost prihvaćanja ekonomske odluka uprave, menadžer se mora pobrinuti da dobiveni optimalni plan bude jedini ispravan. Za to je na temelju modela potrebno dobiti odgovore na sljedeća pitanja:

• "što se događa ako..."
• "što je potrebno za..."

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

Analiza varijanti može biti sljedećih vrsta:

• Parametarski- analiza, koja se sastoji u rješavanju problema za različite vrijednosti određenog parametra.
• Strukturna analiza- kada se rješenje optimizacijskog problema traži pod drugačijom strukturom ograničenja.
• Višekriterijska analiza je rješenje problema korištenjem različitih funkcija cilja.
• Analiza s uvjetnim početnim podacima- kada početni podaci korišteni za rješavanje problema ovise o ispunjavanju dodatnih uvjeta.

Nakon analize potrebno je grafički prikazati rezultate te sastaviti izvješće s preporukama za donošenje odluka uzimajući u obzir specifičnu gospodarsku situaciju.

Trenutačno obrazovni program specijalnosti vezanih uz ekonomiju, financije i menadžment uključuje disciplinu pod nazivom „Metode optimalnih odluka“. U okviru ove discipline studenti proučavaju matematičku stranu optimizacije, operacijsko istraživanje, odlučivanje i modeliranje. glavna značajka Ova disciplina određena je zajedničkim proučavanjem matematičkih metoda s njihovom primjenom u rješavanju ekonomskih problema.

Zadaci optimizacije: opće informacije

Ako razmotrimo opći slučaj, tada je smisao optimizacijskog problema pronaći tzv. optimalno rješenje koje maksimizira (minimizira) funkciju cilja pod određenim uvjetima ograničenja.

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

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

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

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

SZB: formulacija, klasifikacija

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

Opći ZLP je problem forme

pod ograničenjima

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

Bitna značajka ZLP je da se ekstrem 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 smjesom

Rješenje problema smjesa sastoji se u pronalaženju najjeftinijeg skupa koji se sastoji od određenih početnih materijala koji daju smjesu sa željenim svojstvima.

Problem raspodjele resursa

Tvrtka proizvodi n razne proizvode, čija proizvodnja zahtijeva m razne vrste resursa. Rezerve iskorištenih resursa su ograničene i iznose odn b 1, b 2,…, b m c.u. Osim toga, poznati su tehnološki koeficijenti a ij, koji pokazuju koliko jedinica ja-ti resurs je potreban za proizvodnju jedne jedinice proizvoda j-ti tip (). Dobit koju poduzeće ostvaruje prodajom proizvoda j-th vrsta, iznosi c j monetarne jedinice Potrebno je izraditi plan proizvodnje proizvoda čija će dobit poduzeća tijekom provedbe biti najveća.

Problemi koji uključuju mješavine i raspodjelu resursa često su napisani u obliku tablice.

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

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

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

Transportni problem odnosi se na klasu zadataka koji imaju određenu specifičnu strukturu. Najjednostavniji prometni problem je problem prijevoza proizvoda do odredišta s polazišta u minimalni troškovi za prijevoz svih proizvoda.

Radi jasnoće i lakše percepcije, uvjet transportnog problema obično se piše u sljedećoj tablici:

Općenito, rješavanje transportnog problema odvija 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 kuta, Vogelova metoda i metoda minimalnih troškova.

Optimalnost plana provjerava se metodom potencijala:

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

Ako plan nije optimalan, tada se gradi ciklus i transport se redistribuira.

Zaključak

Nije moguće pokriti cjelokupnu teoriju i praksu metoda optimalnog rješenja u okviru jednog članka, stoga se razmatraju samo neke točke koje nam omogućuju davanje opće ideje o ovoj disciplini, problemima i metodama za njihovo rješavanje.

Osim toga, dobro je napomenuti da za provjeru dobivenih rješenja optimizacijskih problema vrlo učinkovito možete koristiti dodatak “Solution Search” paketa MS Excel. 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 optimalnog rješenja:

1. Bandi B. Osnove linearnog programiranja: Trans. s engleskog – M.: Radio i veze, 1989. – 176 str.
2. Kremer N.Sh. Operacijska istraživanja u ekonomiji: Zbornik. priručnik za sveučilišta / N.Sh. Kremer, B.A. Putko, I.M. Trishin, M.N. Friedman; ur. prof. N.Sh. Kremer. – M.: JEDINSTVO, 2005. – 407 str.

Rješenje prilagođenih metoda optimizacije

Možemo vam pomoći riješiti bilo koji problem koristeći optimalne metode rješenja. Na našoj web stranici možete naručiti rješenja problema. Potrebno je samo navesti rok i priložiti datoteku 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 uvjetom da varijable zadovoljavaju konačan broj ograničenja u obliku linearnih jednadžbi ili linearnih nejednadžbi.

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 točaka čije koordinate zadovoljavaju sustav ograničenja

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

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

, A– matrica veličine,

Točka x Poziva se =( , , … ), koji zadovoljava sve uvjete valjana točka . Skup svih dopustivih točaka naziva se važeće područje .

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

Teorema. Skup svih mogućih rješenja sustava ograničenja problema linearnog programiranja je konveksan.

Skup točaka naziva se konveksan , ako on, zajedno s bilo koje dvije svoje točke, sadrži njihovu proizvoljnu konveksnu linearnu kombinaciju.

Točka x nazvao konveksna linearna kombinacija bodova ako su ispunjeni uvjeti

Skup svih mogućih rješenja problema linearnog programiranja je konveksna poliedarska regija, koju ćemo ubuduće zvati poliedar rješenja .

Teorema. Ako ZLP ima optimalno rješenje, tada funkcija cilja poprima najveću (minimalnu) vrijednost na jednom od vrhova poliedra rješenja. Ako funkcija cilja poprima maksimalnu (minimalnu) vrijednost u više od jedne točke, tada uzima tu vrijednost u bilo kojoj točki koja je konveksna linearna kombinacija tih točaka.

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

Osnovno rješenje sustava m linearne jednadžbe s n varijabli je rješenje u kojem su svi n-m non-core varijable su nula. U problemima linearnog programiranja takva se rješenja nazivaju dopuštena osnovna rješenja (referentni planovi).

Teorema. Svakom dopustivom osnovnom rješenju problema linearnog programiranja odgovara vrh poliedra rješenja, i obrnuto, svakom vrhu poliedra rješenja odgovara jedno dopustivo osnovno rješenje.

Važan korolar slijedi iz gornjih teorema:

Ako problem linearnog programiranja ima optimalno rješenje, onda se ono podudara s barem jednim od svojih izvedivih osnovnih rješenja.

Posljedično, optimum linearne funkcije cilja problema linearnog programiranja mora se tražiti među konačnim brojem njegovih izvedivih osnovnih rješenja.