2. Koncept linearnog programiranja. Vrste problema linearnog programiranja
Linearno programiranje (LP) jedno je od prvih i najtemeljnije proučavanih oblasti matematičkog programiranja. Upravo je linearno programiranje bio dio iz kojeg se počela razvijati sama disciplina "matematičko programiranje". Termin "programiranje" u nazivu discipline nema nikakve veze sa pojmom "programiranje (tj. pisanje programa) za računar", jer disciplina "linearnog programiranja" nastala je čak i prije vremena kada su kompjuteri bili široko korišteni za rješavanje matematičkih, inženjerskih, ekonomskih i drugih problema.
Termin "linearno programiranje" proizašao je iz netačnog prijevoda engleskog "linearnog programiranja". Jedno od značenja riječi "programiranje" je pravljenje planova, planiranje. Dakle, ispravan prevod engleskog "linearnog programiranja" ne bi bio "linearno programiranje", već "linearno planiranje", što preciznije odražava sadržaj discipline. Međutim, termini linearno programiranje, nelinearno programiranje, matematičko programiranje itd. u našoj književnosti postali su opšteprihvaćeni i stoga će biti sačuvani.
Dakle, linearno programiranje je nastalo nakon Drugog svjetskog rata i počelo se ubrzano razvijati, privlačeći pažnju matematičara, ekonomista i inženjera zbog mogućnosti široke praktične primjene, kao i matematičke harmonije.
Možemo reći da je linearno programiranje primenljivo za rešavanje matematičkih modela tih procesa i sistema, koji se mogu zasnivati na hipotezi o linearnom predstavljanju realnog sveta.
Linearno programiranje se koristi za rješavanje ekonomskih problema, u zadacima kao što su upravljanje i planiranje proizvodnje; na poslovima određivanja optimalnog smještaja opreme na brodovima, u radionicama; u poslovima utvrđivanja optimalnog plana transporta robe (transportni problem); u problemima optimalne distribucije kadrova itd.
Problem linearnog programiranja (LP), kao što je već jasno iz onoga što je gore rečeno, sastoji se u pronalaženju minimuma (ili maksimuma) linearne funkcije pod linearnim ograničenjima.
Postoji nekoliko metoda za rješavanje LP problema. Ovaj rad će razmotriti neke od njih, posebno:
Grafička metoda za rješavanje LP problema;
Simpleks metoda;
Rješavanje LP problema pomoću Excel procesora proračunskih tablica;
3. Koncept nelinearnog programiranja
U većini inženjerskih problema, konstrukcija matematičkog modela ne može se svesti na problem linearnog programiranja.
Matematički modeli u projektnim problemima stvarnih objekata ili tehnoloških procesa trebaju odražavati stvarne fizičke i po pravilu nelinearne procese koji se u njima odvijaju. Varijable ovih objekata ili procesa su međusobno povezane fizičkim nelinearnim zakonima, kao što su zakoni održanja mase ili energije. Oni su ograničeni graničnim rasponima koji osiguravaju fizičku izvodljivost datog objekta ili procesa. Kao rezultat toga, većina problema matematičkog programiranja koji se susreću u istraživačkim projektima i problemima dizajna su problemi nelinearnog programiranja (NP).
U ovom radu ćemo razmotriti takav metod za rješavanje NP problema kao što je metoda Lagrangeovih množitelja.
Metoda Lagrangeovog množitelja omogućava vam da pronađete maksimum (ili minimum) funkcije pod ograničenjima jednakosti. Osnovna ideja metode je prijeći sa problema o uvjetnom ekstremumu na problem pronalaženja bezuvjetnog ekstremuma određene konstruirane Lagrangeove funkcije.
4. Dinamičko programiranje
Dinamičko programiranje je matematički aparat koji omogućava brzo pronalaženje optimalnog rješenja u slučajevima kada analizirana situacija ne sadrži faktore neizvjesnosti, ali postoji veliki broj ponašanja koja donose različite rezultate, među kojima je potrebno odabrati najbolje. Dinamičko programiranje pristupa rješavanju određene klase problema tako što ih razlaže na dijelove, male i manje složene probleme. U principu, problemi ove vrste se mogu riješiti nabrajanjem svih mogućih opcija i odabirom najbolje među njima, međutim, takvo nabrajanje je često vrlo teško. U ovim slučajevima, proces donošenja optimalne odluke može se podijeliti na korake (etape) i istražiti metodom dinamičkog programiranja.
Rješavanje problema metodama dinamičkog programiranja provodi se na osnovu principa optimalnosti koji je formulirao RE Bellman: optimalno ponašanje ima svojstvo da bez obzira na početno stanje sistema i početno rješenje, naknadno rješenje treba odrediti optimalno ponašanje u odnosu na stanje dobijeno kao rezultat početnog rješenja.
Dakle, planiranje svakog koraka treba provoditi uzimajući u obzir sveukupne koristi dobivene na kraju cijelog procesa, što omogućava optimizaciju konačnog rezultata prema odabranom kriteriju.
Međutim, dinamičko programiranje nije univerzalna metoda rješenja. Gotovo svaki problem riješen ovom metodom karakteriziraju svoje karakteristike i zahtijeva potragu za najprihvatljivijim skupom metoda za njegovo rješenje. Osim toga, veliki obim i mukotrpnost rješavanja problema u više koraka sa mnogim stanjima dovode do potrebe da se izaberu problemi niske dimenzije ili da se koriste komprimirane informacije.
Dinamičko programiranje se koristi za rješavanje problema kao što su: raspodjela oskudnih kapitalnih investicija između novih područja njihove upotrebe; razvoj pravila za upravljanje potražnjom i zalihama; izradu plana tekućih i kapitalnih popravki opreme i njene zamjene; traženje najkraćih udaljenosti na transportnoj mreži itd.
Neka se proces optimizacije podijeli na n koraka. U svakom koraku potrebno je definirati dvije vrste varijabli - varijablu stanja S i kontrolnu varijablu X. Varijabla S određuje u kojim se stanjima sistem može naći na datom k-tom koraku. U zavisnosti od S, u ovom koraku se mogu primijeniti neke kontrole koje karakterizira varijabla X. Primjena kontrole X na k-tom koraku daje neki rezultat Wk (S, Xk) i prenosi sistem u neko novo stanje S"(S , Xk). Za svako moguće stanje u k-tom koraku, među svim mogućim kontrolama, bira se optimalna kontrola X * k tako da se rezultat koji se postiže u koracima od k-tog do n-tog pokaže optimalnim. Numerička karakteristika ovaj rezultat se naziva Bellmanova funkcija Fk (S) i zavisi od broja koraka k i stanja sistema S.
Sva rješenja problema podijeljena su u dvije faze. U prvoj fazi, koja se zove uslovna optimizacija, Bellmanova funkcija i optimalne kontrole se pronalaze za sva moguća stanja u svakom koraku, počevši od posljednjeg.
Nakon što se pronađu Bellmanova funkcija i odgovarajuće optimalne kontrole za sve korake od n-og do prvog, izvodi se druga faza rješavanja problema koja se naziva neograničena optimizacija.
Općenito, problem dinamičkog programiranja je formuliran na sljedeći način: potrebno je definirati kontrolu X * koja prenosi sistem iz početnog stanja S0 u konačno stanje Sn, pri čemu funkcija cilja F (S0, X *) uzima najveća (najmanja) vrijednost.
Karakteristike matematičkog modela dinamičkog programiranja su sljedeće:
problem optimizacije je formuliran kao završni proces upravljanja u više koraka;
ciljna funkcija je aditivna i jednaka zbroju ciljnih funkcija svakog koraka
izbor kontrole Xk u svakom koraku zavisi samo od stanja sistema do ovog koraka Sk-1 i ne utiče na prethodne korake (nema povratne informacije);
stanje sistema Sk nakon svakog kontrolnog koraka zavisi samo od prethodnog stanja sistema Sk-1 i ove kontrolne akcije Xk (bez naknadnog efekta) i može se zapisati u obliku jednačine stanja:
na svakom koraku, kontrola Xk zavisi od konačnog broja kontrolnih varijabli, a stanje sistema Sk zavisi od konačnog broja varijabli;
optimalna kontrola X * je vektor određen nizom optimalnih kontrola korak po korak:
X * = (X * 1, X * 2, ..., X * k, ..., X * n),
čiji broj određuje broj koraka u zadatku.
Uslovna optimizacija. Kao što je gore navedeno, u ovoj fazi traže se Bellmanova funkcija i optimalne kontrole za sva moguća stanja u svakom koraku, počevši od posljednjeg, u skladu s algoritmom povratnog sweep-a. U zadnjem n-tom koraku nije teško pronaći optimalnu kontrolu X * n i vrijednost Bellmanove funkcije Fn (S), jer
Fn (S) = max (Wn (S, Xn)),
gdje se traži maksimum preko svih mogućih vrijednosti Xn.
Daljnji proračuni se izvode prema rekurentnoj relaciji koja povezuje Bellmanovu funkciju u svakom koraku sa istom funkcijom, ali izračunatom u prethodnom koraku:
Fk (S) = max (Wk (S, Xk) + Fk + 1 (S "(S, Xk))). (1)
Ovaj maksimum (ili minimum) se određuje za sve moguće vrijednosti kontrolne varijable X za k i S.
Bezuslovna optimizacija. Nakon što se pronađe Bellmanova funkcija i odgovarajuće optimalne kontrole za sve korake od n-tog do prvog (na prvom koraku k = 1 stanje sistema je jednako njegovom početnom stanju S0), druga faza rješavanja problema se sprovodi. Optimalna kontrola se nalazi na prvom koraku X1, čijom primenom će se sistem dovesti u stanje S1 (S, x1 *), znajući za koje, koristeći rezultate uslovne optimizacije, možemo naći optimalno upravljanje u drugom koraku , i tako redom do posljednjeg n-og koraka.
Laboratorijski rad br. 1 (Zadatak linearnog programiranja)
Za datu matematičku formulaciju LP problema, uzimajući dodatni uslov nenegativnosti varijabli, izvršite sljedeće radnje:
Riješite problem grafički;
Dovedite zadatak u kanonski oblik zapisa;
Kreirajte simpleks tablicu;
Riješite problem koristeći simpleks metodu ručno ili pomoću računara;
Izvršite izjavu dvojnog LP problema;
Dobiti rješenje dualnog problema iz prethodno dobijene simpleks tabele i analizirati dobijene rezultate;
Provjerite rezultate rješenja u Excel tabeli;
Sastavite izvještaj koji sumira rezultate za svaku stavku.
| Resursi | dionice | Proizvodi | |
| R1 | P2 | ||
| S1 | 18 | 0.2 | 3 |
| S2 | 13.1 | 0.7 | 2 |
| MV | 23 | 2.3 | 2 |
| Dobit po jedinici proizvodnje u USD | 3 | 4 | |
Grafička metoda. Da bismo konstruirali poligon rješenja, transformiramo originalni sistem
, dobijamo 
predstavljamo granične linije.
Linearna funkcija F = f (x) je jednačina prave c1x1 + c2x2 = const. Napravimo graf ciljne funkcije sa f (x) = 0. da bismo izgradili pravu liniju 3x1 + 4x2 = 0, konstruišemo radijus vektor N = (3; 4) i kroz tačku 0 povučemo pravu liniju okomitu na nju. Konstruisana linija F = 0 pomera se paralelno sa sobom u pravcu vektora N.
|
Sa slike 1 proizilazi da ova prava linija postaje oslonac u odnosu na konstruisani poligon rješenja u tački B, gdje funkcija F poprima svoju maksimalnu vrijednost. Tačka B leži na preseku pravih 0,7x1 + 2x2 ≤ 13,1 i 2,3x1 + 2x2 = 23 / Da bismo odredili njene koordinate, rešavamo sistem jednačina:
Optimalni plan zadatka: h1 = 6,187; x2 = 4,38, zamjenom vrijednosti x1 i x2 u ciljnu funkciju, dobijamo Fmax = 3 * 6,187 + 4 * 4,38 = 36,08.
Dakle, da biste dobili maksimalnu zaradu od 36,06 dolara, morate planirati proizvodnju 6 jedinica. proizvodi P1 i 4 jedinice. P2 proizvodi.
Kanonski oblik LP problema. Zapišimo problem alokacije resursa u kanonskom obliku. Dodajući originalnom sistemu ograničenja nenegativnih varijabli x3 ≥ 0, x4 ≥ 0, x5 ≥ 0, imamo:
LP simpleks stol. U slučaju osnovnih varijabli (x3, x4, x5), početna simpleks tabela će izgledati ovako:
Tabela 1.
| -x1 | -x2 | ||
| x3 = | 0,2 | 3 | 18 |
| x4 = | 0,7 | 2 | 13,1 |
| x5 = | 2,3 | 2 | 23 |
| f (x) = | 3 | 4 |
Već odgovara osnovnom planu x (0) = T (kolona slobodnih članova).
Među problemima optimizacije u teoriji odlučivanja, najpoznatiji su problemi linearnog programiranja u kojima je maksimizirana funkcija F (X) linearna, a ograničenja A određena su linearnim nejednačinama. Počnimo s primjerom (vidi).
Proizvodni zadatak. U radionici se mogu proizvoditi stolice i stolovi. Za izradu stolice potrebno je 5 jedinica materijala, a za izradu stola 20 jedinica (stopa od mahagonija). Za stolicu je potrebno 10 čovjek-sati, za sto 15. Ima 400 komada materijala i 450 čovjek-sati. Zarada stolice je 45 dolara, a zarada stola 80 dolara. Koliko stolica i stolova trebate napraviti da biste ostvarili najveći profit?
Označimo: X 1 - broj napravljenih stolica, X 2 - broj napravljenih stolova. Problem optimizacije je sljedeći:
45 X 1 + 80 X 2 → max,
5 X 1 + 20 X 2 ≤ 400,
10 X 1 + 15 X 2 ≤ 450,
Prvi red sadrži funkciju cilja - profit od proizvodnje X 1 stolica i X 2 stola. Potrebno ga je maksimizirati odabirom optimalnih vrijednosti varijabli X 1 i X 2. Ograničenja materijala (drugi red) moraju biti ispunjena - ne potroši se više od 400 stopa mahagonija. Kao i ograničenja rada (treća linija) - ne više od 450 provedenih sati. Također, zapamtite da broj stolova i broj stolica nisu negativni. Ako je X 1 = 0, to znači da se stolice ne proizvode. Ako se napravi barem jedna stolica, tada je X 1 pozitivan. Ali nemoguće je zamisliti negativan učinak - X 1 ne može biti negativan sa ekonomske tačke gledišta, iako se sa matematičke tačke gledišta takvo ograničenje ne može vidjeti. U četvrtom i petom redu problema stoji da su varijable nenegativne.
Uslovi proizvodnog problema mogu se prikazati na koordinatnoj ravni. Nacrtaćemo vrednosti X 1 duž horizontalne ose apscise, a vrednosti X 2 duž vertikalne ose ordinata. Zatim ograničenja materijala i zadnja dva reda optimizacijskog problema ističu moguće vrijednosti (X 1, X 2) izlaznih volumena u obliku trokuta (slika 1).
Stoga su materijalna ograničenja prikazana kao konveksni poligon, konkretno trokut. Ovaj trougao se dobija odsecanjem zone koja se nalazi pored ishodišta iz prvog kvadranta. Odsijecanje se vrši pravom linijom koja odgovara drugoj liniji izvornog problema, uz zamjenu nejednakosti jednakošću. Prava linija siječe X-osu 1, koja odgovara stolicama, u tački (80,0). To znači da ako se sav materijal iskoristi za izradu stolica, biće napravljeno 80 stolica. Ista prava linija preseca os X 2, koja odgovara tabelama, u tački (0,20). To znači da ako se sav materijal iskoristi za izradu stolova, biće napravljeno 20 stolova. Za sve tačke unutar trougla, zadovoljena je nejednakost, a ne jednakost - materijal će ostati.
Ograničenja rada mogu se prikazati na sličan način (slika 2).
Stoga su ograničenja rada također prikazana kao trokut. Ovaj trougao se takođe dobija odsecanjem zone koja se nalazi pored ishodišta iz prvog kvadranta. Odsijecanje se vrši pravom linijom koja odgovara trećem redu izvornog problema, uz zamjenu nejednakosti jednakošću. Prava linija siječe X-osu 1, koja odgovara stolicama, u tački (45,0). To znači da ako se sva radna snaga iskoristi za izradu stolica, biće napravljeno 45 stolica. Ista ravna linija u tački (0,30) preseca os X 2, koja odgovara tabelama. To znači da ako se svi radnici postave da prave stolove, onda će biti napravljeno 30 stolova. Za sve tačke unutar trougla ispunjena je nejednakost, a ne jednakost – neki od radnika će biti neaktivni.
Vidimo da nema očiglednog rješenja - ima materijala za izradu 80 stolica, ali nema dovoljno radnika, a za proizvodnju 30 stolova ima radne snage, ali nema materijala, što znači da je neophodno za proizvodnju oboje. Ali u kom omjeru?
Da bi se odgovorilo na ovo pitanje, potrebno je "kombinirati" slike 1 i 2, dobivši područje mogućih rješenja, a zatim pratiti koje vrijednosti prima funkcija cilja na ovom skupu (slika 3).
Dakle, skup mogućih vrijednosti volumena proizvodnje stolica i stolova (X 1, X 2), ili, drugim riječima, skup A, koji postavlja ograničenja na kontrolni parametar u općem problemu optimizacije, je presek dva trougla, tj konveksni četvorougao prikazan na slici 3. Njegova tri vrha su očigledna - to su (0,0), (45,0) i (0,20). Četvrti je presek dve prave - granice trouglova na sl. 1 i sl. 2, tj. rješenje sistema jednačina
5 X 1 + 20 X 2 = 400,
10 X 1 + 15 X 2 = 450.
Iz prve jednačine: 5 X 1 = 400 - 20 X 2, X 1 = 80 - 4 X 2. Zamijenite u drugu jednačinu: 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 = 80 - 4 x 14 = 80 -56 = 24. Dakle, četvrti vrh četvorougla je (24, 14).
Potrebno je pronaći maksimum linearne funkcije na konveksnom poligonu. (U opštem slučaju linearnog programiranja, maksimum linearne funkcije na konveksnom politopu koji leži u konačnodimenzionalnom linearnom prostoru.) Glavna ideja linearnog programiranja je da se maksimum postiže na vrhovima poligona. Generalno, to je na jednom vrhuncu, i to je jedina maksimalna tačka. U količniku - u dva, a zatim segment koji ih povezuje također se sastoji od maksimalnih tačaka.
Funkcija cilja 45 X 1 + 80 X 2 uzima minimalnu vrijednost od 0 na vrhu (0,0). Kako se argumenti povećavaju, ova funkcija se povećava. Na vrhu (24.14) uzima vrijednost 2200. U ovom slučaju, prava linija 45 X 1 + 80 X 2 = 2200 prolazi između pravih linija ograničenja 5 X 1 + 20 X 2 = 400 i 10 X 1 + 15 X 2 = 450, sijeku se u istoj tački. Iz ovoga, kao i iz direktne provjere dva preostala vrha, proizlazi da je maksimum ciljne funkcije, jednak 2200, postignut na vrhu (24, 14).
Dakle, optimalni izlaz je 24 stolice i 14 stolova. U ovom slučaju se koriste svi materijalni i svi radni resursi, a dobit iznosi 2200 američkih dolara.
Dvostruki zadatak... Svaki problem linearnog programiranja odgovara takozvanom dualnom problemu. U njemu se, u poređenju sa originalnim problemom, redovi pretvaraju u kolone, nejednakosti menjaju predznak, a umesto maksimuma traži se minimum (ili obrnuto, umesto minimuma, maksimum). Dvostruki prema dvojakom problemu je sam izvorni problem. Uporedimo originalni problem (na lijevoj strani) i njegov dvojni (desno):
45 X 1 + 80 X 2 → max, 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 dvostruki zadatak toliko važan? Može se dokazati da se optimalne vrijednosti ciljnih funkcija u originalnom i dualnom problemu poklapaju (tj. maksimum u originalnom problemu se poklapa s minimumom u dualnom). U ovom slučaju, optimalne vrijednosti W 1 i W 2 pokazuju trošak materijala i rada, ako se ocjenjuju njihovim doprinosom funkciji cilja. Da se ne brkaju sa tržišnim cenama ovih faktora proizvodnje, W 1 i W 2 se nazivaju "objektivno utvrđenim vrednovanjem" sirovina i rada.
Linearno programiranje kao naučna i praktična disciplina. Od svih optimizacijskih problema, problemi linearnog programiranja se razlikuju po tome što su ograničenja u njima sistemi linearnih nejednakosti ili jednakosti. Ograničenja definiraju konveksne linearne politope u konačnom linearnom prostoru. Ciljne funkcije su također linearne.
Po prvi put takve probleme je riješio sovjetski matematičar L.V. Kantorovich (1912-1986) 1930-ih godina kao zadaci upravljanja proizvodnjom u cilju optimizacije organizacije proizvodnje i proizvodnih procesa, na primjer, procesa utovara mašina i rezanja limova materijala. Nakon Drugog svjetskog rata, sličnim zadacima su se bavile i Sjedinjene Američke Države. 1975. T. Koopmans (1910-1985, rođen u Holandiji, radio uglavnom u SAD) i akademik Akademije nauka SSSR-a L.V. Kantoroviću su dodijeljene Nobelove nagrade za ekonomiju.
Razmotrimo nekoliko problema linearnog programiranja.
Problem optimizacije mješavine (pojednostavljena verzija). U hemijskom postrojenju, radi optimizacije tehnološkog procesa, potrebno je sastaviti najjeftiniju mešavinu koja sadrži potrebnu količinu određenih supstanci (naznačićemo ih kao T i H). Energetska vrijednost mješavine (u kalorijama) ne smije biti manja od navedene. Radi jednostavnosti, neka smjesa bude sastavljena od dvije komponente - K i C. Koliko svake od njih uzeti za uključivanje u smjesu? Početni podaci za proračun su dati u tabeli 3.
Tabela 3. Početni podaci u problemu optimizacije smjese.
3,8 K + 4,2 C → min,
0,10 K + 0,25 C ≥ 1,00,
1,00 K + 0,25 C ≥ 5,00,
110,00 K + 120,00 C ≥ 400,00,
Njegovo grafičko rješenje je prikazano na slici 4.
Slika 4. Grafičko rješenje problema optimizacije smjese.
Na slici 4, radi lakše percepcije, četiri prave linije označene su brojevima (1) - (4). Prava linija (1) je prava linija 1,00K + 0,25C = 5,00 (ograničenje na supstancu H). Prolazi, kao što je prikazano na slici, kroz tačke (5,0) na osi apscise i (0,20) na osi ordinata. Imajte na umu da dozvoljene vrijednosti parametara (K, C) leže iznad prave linije (1), za razliku od prethodno razmatranih slučajeva u prethodnom proizvodnom zadatku.
Prava linija (2) je prava linija 110,00 K + 120,00 C = 400,00 (ograničenje kalorija). Imajte na umu da se u području nenegativnog S nalazi svuda ispod prave linije (1). Zaista, ovo važi za K = 0, prava linija (1) prolazi kroz tačku (0,20), a prava (2) kroz tačku (0, 400/120). Tačka preseka dve prave nalazi se rešavanjem sistema jednačina
1,00 K + 0,25 C = 5,00,
110,00 K + 120,00 C = 400,00.
Iz prve jednačine K = 5 - 0,25 S. Zamjena u drugoj: 110 (5 - 0,25 S) + 120 S = 400, odakle je 550 - 27,5 S + 120 S = 400. Dakle, 150 = - 92 , 5 S, tj rješenje se postiže za negativan C. To znači da za sve pozitivne C prava linija (2) leži ispod prave (1). To znači da ako je ograničenje H ispunjeno, onda i ograničenje kalorija mora biti ispunjeno. Suočeni smo s novim fenomenom - neka ograničenja s matematičke tačke gledišta mogu biti suvišna. Sa ekonomske tačke gledišta, oni su neophodni, odražavaju bitne karakteristike formulacije problema, ali se u ovom slučaju ispostavilo da je unutrašnja struktura problema takva da ograničenje kalorija ne učestvuje u formiranju dozvoljenog raspona parametara. i pronalaženje rješenja.
Prava linija (4) je prava linija 0,1 K + 0,25 C = 1 (ograničenje na supstancu T). Prolazi, kao što je prikazano na slici, kroz tačke (10.0) na apscisi i (0.4) na ordinati. Imajte na umu da dozvoljene vrijednosti parametara (K, C) leže iznad prave linije (4), kao i za ravnu liniju (1).
Shodno tome, raspon dozvoljenih vrijednosti parametara (K, C) je neograničen odozgo. Od cijele ravni se razlikuje po koordinatnim osa (leži u prvom kvadrantu) i pravim linijama (1) i (4) (leži iznad ovih pravih). Raspon dozvoljenih vrijednosti parametara (K, C) može se nazvati "neograničeni poligon". Minimum funkcije cilja od 3,8 K + 4,2 C može se postići samo na vrhovima ovog "poligona". Postoje samo tri vrha. To su preseci sa apscisnim (10.0) i ordinatnim (0.20) osama pravih (1) i (4) (u svakom slučaju, onaj koji zadovoljava oba ograničenja uzima se iz dva preseka). Treći vrh je tačka preseka pravih (1) i (4), čije se koordinate nalaze pri rešavanju sistema jednačina
0,10 K + 0,25 C = 1,00,
1,00 K + 0,25 C = 5,00.
Iz druge jednačine K = 5 - 0,25 C, iz prve 0,10 (5 - 0,25 C) + 0,25 C = 0,5 - 0,025 C + 0,25 C = 0,5 + 0,225 C = 1, odakle je C = 0,5 / 0,225 i K = 5 - 5/9 = 40/9. Dakle, A = (40/9; 20/9).
Prava linija (3) na slici 4 je prava linija koja odgovara ciljnoj funkciji 3,8 K + 4,2 C. Ona prolazi između pravih linija (1) i (4), postavljajući ograničenja, a minimum se postiže u tački A, kroz koju prolazi prava linija (3). Dakle, minimum je 3,8x40 / 9 + 4,2x20 / 9 = 236/9. Problem optimizacije smjese je u potpunosti riješen.
Dualni problem konstruiran prema gore opisanim pravilima ima sljedeći oblik (ovdje ponavljamo originalni problem optimizacije smjese kako bismo jasno demonstrirali tehnologiju za izradu dualnog problema):
3,8 K + 4,2 C → min, W 1 + 5 W 2 + 400 W 3 → max,
0,10 K + 0,25 C ≥ 1,00, 0,1 W 1 + 1,10 W 2 + 110 W 3 ≤ 3,8,
1,00 K + 0,25 C ≥ 5,00, 0,25 W 1 + 0,25 W 2 + 120 W 3 ≤ 4,2,
110,00 K + 120,00 C ≥ 400,00, W 1 ≥ 0,
K ≥ 0, W 2 ≥ 0,
C ≥ 0. W 3 ≥ 0.
Minimalna vrijednost u direktnom zadatku, kako i treba, jednaka je maksimalnoj vrijednosti u dualnom problemu, tj. oba broja su 236/9. Tumačenje dualnih varijabli: W 1 je “trošak” jedinice supstance T, a W 2 je “trošak” jedinice supstance H, mjereno “njihovim doprinosom” ciljnoj funkciji. U ovom slučaju, W 3 = 0, budući da ograničenje broja kalorija ni na koji način ne učestvuje u formiranju optimalnog rješenja. Dakle, W 1, W 2, W 3 su tzv. objektivno određene procjene (prema L.V. Kantorovichu) resursa (supstance T i H, kalorije).
Planiranje nomenklature i obima proizvodnje. Vratimo se organizaciji proizvodnje. Preduzeće može da proizvodi automatske kuhinje (vrste lonaca), aparate za kafu i samovare. U tabeli 4 prikazani su podaci o raspoloživim proizvodnim kapacitetima u preduzeću (u komadima proizvoda).
Tabela 4. Kapacitet proizvodnje (u kom.)
Aparati za kafu |
Samovari |
||
Štancanje |
|||
Obim izdanja |
|||
Specifična dobit (po artiklu) |
U ovom slučaju, štancanje i dorada se izvode na istoj opremi. Omogućava vam da u određenom vremenu otisnete ili 20.000 kuhinja, ili 30.000 aparata za kafu, ili oboje, ništa manje. Ali montaža se vrši u odvojenim područjima.
Problem linearnog programiranja je:
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)
X 2/120 ≤ 100, (4)
X 3/80 ≤ 100, (5)
F = 15 X 1 + 12 X 2 + 14 X 3 → max.
ovdje:
(0) je uobičajeno u ekonomiji stanje nenegativnosti varijabli,
(1) - ograničenje mogućnosti štancanja (izraženo radi lakše percepcije u postocima),
(2) - ograničenje mogućnosti završne obrade,
(3) - ograničenja montaže za kuhinje,
(4) - isto za mlin za kafu,
(5) - isto za samovare (kao što je već spomenuto, sve tri vrste proizvoda se sklapaju na odvojenim linijama).
Konačno, funkcija cilja F je ukupna dobit preduzeća.
Imajte na umu da nejednakost (3) proizlazi iz nejednakosti (1), a nejednakost (4) - iz (2). Stoga se nejednakosti (3) i (4) mogu odjednom odbaciti.
Odmah da primetimo jednu zanimljivu činjenicu. Kako će se ustanoviti, u optimalnom planu X 3 = 0, tj. samovare je neisplativo proizvoditi.
| Prethodno |
U vezi sa razvojem tehnologije, rastom industrijske proizvodnje, sve važniju ulogu imaju zadaci pronalaženja optimalnih rješenja u različitim sferama ljudske djelatnosti. Glavni alat u rješavanju ovih problema bilo je matematičko modeliranje – formalni opis fenomena koji se proučava i istražuje korištenjem matematičkog aparata.
Svaki model realnog procesa pretpostavlja idealizaciju i apstrakciju, ali oni ne bi trebali ići predaleko od sadržaja problema kako konstruisani model ne bi izgubio bitne karakteristike objekta koji se modelira, odnosno bio mu adekvatan. S druge strane, ako izgradite složeni model koji uzima u obzir sve suptilne karakteristike procesa koji se proučava, onda to može narušiti značenje modeliranja, čiji je jedan od ciljeva da se pojednostavi formulacija problema tako da lakše ga je proučavati (previše složen model, u pravilu, nije podložan analizi) ...
U velikom broju slučajeva, prvi stepen aproksimacije stvarnosti je model u kojem se pretpostavlja da su sve zavisnosti između varijabli koje karakterišu stanje objekta linearne. Ovdje postoji potpuna analogija s tim koliko se vrlo važne i često iscrpne informacije o ponašanju proizvoljne funkcije dobijaju na osnovu proučavanja njene derivacije - ova funkcija je zamijenjena linearnom ovisnošću u blizini svake tačke. Značajan broj ekonomskih, tehničkih i drugih procesa prilično je dobro i u potpunosti opisan linearnim modelima. Prethodno navedeno određuje važnost uloge koju ima linearno programiranje - metoda pronalaženja uslovnog ekstremuma linearne funkcije na skupu datom pomoću linearnih odnosa kao što su jednakosti i nejednakosti (linearna ograničenja).
Uslovi primjenjivosti linearnog modela
djeljivost. Ako se metoda primjenjuje sa intenzitetima a i b (a< b), то его можно применять с любой интенсивностью x .
Ovaj uslov nije trivijalan. Ako se, na primjer, intenzitet posla mjeri brojem dodijeljenih radnika, tada su dozvoljene samo cjelobrojne vrijednosti intenziteta. Ako se intenzitet mjeri brojem čovjek-sati dnevno, onda je princip djeljivosti očigledno ispunjen.
Proporcionalnost. Troškovi, rezultati i korisnost koju generiše svaka metoda proporcionalni su njenom intenzitetu.
Ovo je uslov stalnog povrata (u svakom smislu), odsustva ekonomije obima. Posebnu pažnju treba posvetiti utvrđivanju opsega intenziteta tehnološke metode, u kojoj ova metoda zadovoljava uslov proporcionalnosti. Na primjer, ako zavarivač prokuha posudu za 6 sati, onda dva zavarivača vjerovatno mogu obaviti posao za 3 sata. Ali šest - za sat - neće zavariti kontejner.
Aditivnost. Komunalne usluge i - za svaki sastojak - troškovi i rezultati proizvedeni svim metodama se zbrajaju.
Princip aditivnosti zahtijeva tačan i dosljedan opis nomenklature uključene u model: tehnološke metode, sastojci, upotrebne vrijednosti.
Oblici pisanja zadataka linearnog programiranja
U svom najopćenitijem obliku, LP problem se piše na sljedeći način:
- 2 (2)
- 3 (3)
- 4 (4)
- 5 (5)
Definicija 1. Matrica se naziva matrica problema (1) - (5). ?
Jedinstveniji prikaz LP zadatka je standardni obrazac:
za i (1, ..., m), x 0.
Karakteristike standardnog oblika: sve varijable su nenegativne (n1 = n), nema ograničenja jednakosti (m1 = 0). Ako je CF maksimiziran, tada je m2 = 0 i nema ograničenja oblika (3); inače m2 = m i nema ograničenja oblika (4). Pod pretpostavkom i, standardni obrazac se može napisati na sljedeći način:
6c x max (min) na Ax () b, x 0. (6)
Ali kanonski oblik pisanja LP problema ima najjednostavniji oblik.
Definicija 2. Problem (1) - (4) je predstavljen u kanonskom obliku ako su sva ograničenja, osim uslova nenegativnosti varijabli, jednakosti (m1 = m) i sve varijable nisu negativne (n1 = n) . ?
Problem LP u kanonskom obliku je, dakle, oblika
- 7c x max (min) za Ax = b, x 0. (7)
- 1.2 Osnove simpleks metode
Razmotrimo LP problem u kanonskom obliku:
- 9 (9)
- 10x 0 (10)
Neka su i red i i kolona j matrice A0, respektivno. Pretpostavićemo da su redovi matrice linearno nezavisni.
Svaki LP problem se može svesti na kanonski oblik; ako je problem rješiv u kanonskom obliku, tada među njegovim rješenjima postoji barem jedna ekstremna tačka skupa izvodljivih rješenja; ekstremne tačke skupa izvodljivih rješenja LP problema u kanonskom obliku poklapaju se sa BDR.
Na osnovu navedenih činjenica može se zamisliti sljedeći postupak rješavanja problema. Provjerimo na neki način da li problem ima rješenje i, ako ima, dovedemo ga u kanonski oblik. Neka matrica A0 kanonskog oblika ima dimenziju m × n i rang m. Konstruišemo sve m × m-podmatrice matrice A0, odbacujući degenerisane, preostale podmatrice odgovaraju bazama matrice A0. Odaberimo od njih dopustive baze, konstruirajmo odgovarajući BDR. Odaberimo BDR koji daje maksimum funkcije cilja.
Ali takav algoritam se ne može implementirati u praksi, jer broj BDR-ova raste eksponencijalno sa rastom dimenzije problema (broj varijabli i/ili ograničenja). Procedura se može ubrzati ako je organizirate tako da se vrijednost CF-a ne smanjuje tokom traženja BDR-a (dosljedno poboljšanje plana). Ovo je originalna ideja simpleks metode, koja se implementira na sljedeći način.
1.3 Simpleksne tablice
Simpleks optimizacija linearnog programiranja
Transformacije LP problema u kanonskom obliku, izvedene simpleks metodom, zgodno su predstavljene kao transformacije simpleks tablica. Opšti prikaz simpleks tabele, koji odgovara trenutnoj iteraciji simpleks metode, prikazan je u tabeli 1.
Gornji red sadrži: naslov prve kolone, identifikatore svih (glavnih, dodatnih, pomoćnih, itd.) varijabli zadatka i naslov posljednje kolone. Sljedećih m redaka opisuju jednačine problema u obliku:
koje imaju na početku iteracije. Prvo je naznačen identifikator osnovne varijable (u trenutnoj bazi) za odgovarajuću jednačinu. Zatim slijede koeficijenti varijabli (redom kojim su varijable upisane u prvom redu). Posljednji element linije je desna strana ograničenja.
Donja linija odgovara jednačini
12, gdje i. (12)
predstavlja CF. Varijabla z igra osnovnu ulogu u njoj (ima koeficijent 1 i ne ulazi u druge jednačine); broj F je desna strana jednačine (12), vrijednost CF kod trenutnog osnovnog rješenja.
Tabela 1. Opšti pogled na simpleks tablicu
Komentar. U tabeli je opisan sistem jednačina (11), pa se trenutni BDR može dobiti pretpostavkom da su osnovne varijable jednake odgovarajućim elementima posljednje kolone, a nebazične varijable jednake nuli. ?
Na razmatranoj iteraciji događa se sljedeće.
Ako nema negativnih elemenata u z-redu, u kolonama koje odgovaraju varijablama, tada je trenutni MDD optimalan i varijable optimalne baze se upisuju u prvu kolonu tabele. Inače, stupac varijable xs za koji je s< 0, становится направляющим.
Ako su svi elementi kolone za vođenje nepozitivni, onda je problem neograničen. U suprotnom, izračunajte omjer elemenata posljednje i vodeće kolone za sve redove koji imaju pozitivan element u vodećoj koloni. Niz r, za koji je ovaj omjer minimalan, postaje smjernica. U prvoj koloni sljedeće simpleks tabele, varijabla xs će zauzeti mjesto varijable xj (r).
Ars je sada permisivni element. Elementi sljedeće simpleks tablice izračunavaju se po formulama:
13 za za i r (13)
- 14 (14)
- 15 (15)
Uzmimo j = j (k). Iz (11) i (12) slijedi da stupac j (osnovni) ima 1 u redu k i nule u preostalim redovima: j = 0, aij = 1 za i = k, inače aij = 0. Neka je kr (kolona j je sačuvana u novoj osnovi). Tada je ari = 0 i iz (13), (14), (16) slijedi da za sve i i. Uzimajući to u obzir, formuliraćemo pravila za transformaciju simpleks tablice u prijelazu na novu osnovu:
- · U naslov vodećeg reda stavite naslov vodeće kolone;
- · Svi brojevi vodeće linije podijeljeni su elementom za razrješenje;
- · Vodeći stupac postaje jedan, s jednim u vodećim redu;
- · Kolone tekuće osnove sa brojevima drugačijim od j (r) se ne mijenjaju;
- · Svi ostali brojevi u tabeli (uključujući elemente donjeg reda i zadnje kolone) se preračunavaju prema formulama (13) - (15), (16).
Linearno programiranje
Linearno programiranje- matematička disciplina posvećena teoriji i metodama rješavanja ekstremnih problema na skupovima -dimenzionalnog vektorskog prostora, datih sistemima linearnih jednačina i nejednačina.
Linearno programiranje je poseban slučaj konveksnog programiranja, što je zauzvrat poseban slučaj matematičkog programiranja. Istovremeno je osnova za nekoliko metoda za rješavanje problema cjelobrojnog i nelinearnog programiranja. Jedna od generalizacija linearnog programiranja je frakciono linearno programiranje.
Mnoga svojstva problema linearnog programiranja mogu se interpretirati kao svojstva poliedara i tako ih geometrijski formulisati i dokazati.
Priča
Metodu unutrašnjih tačaka prvi je spomenuo I.I.Dikin 1967. godine.
Zadaci
Glavni (standardni) zadatak linearnog programiranja je problem pronalaženja minimuma linearne ciljne funkcije (linearni oblik) oblika:
pod uslovima
, .Problem linearnog programiranja će imati kanonski pogled ako u glavnom zadatku, umjesto prvog sistema nejednačina, postoji sistem jednačina:
,Glavni zadatak se može svesti na kanonski uvođenjem dodatnih varijabli.
Problemi linearnog programiranja najopćenitijeg oblika (problemi sa mješovitim ograničenjima: jednakosti i nejednakosti, prisustvo varijabli bez ograničenja) mogu se svesti na ekvivalent (koji imaju isti skup rješenja) promjenom varijabli i zamjenom jednakosti sa parom nejednakosti .
Lako je vidjeti da se problem nalaženja maksimuma može zamijeniti problemom nalaženja minimuma uzimanjem koeficijenata suprotnog predznaka.
Primjeri zadataka
Maksimalno podudaranje
Razmotrimo problem maksimalnog podudaranja u bipartitnom grafu: postoji nekoliko dječaka i djevojčica, a za svakog dječaka i djevojčicu se zna da li su privlačni jedno drugom. Potrebno je vjenčati maksimalan broj parova uz obostrane simpatije.
Hajde da uvedemo varijable koje odgovaraju paru -th dječak i -th djevojka i zadovoljavaju ograničenja:
sa ciljnom funkcijom. Može se pokazati da među optimalnim rješenjima ovog problema postoji jedno cjelobrojno. Varijable jednake 1 će odgovarati parovima koji će se vjenčati.
Maksimalni protok
Neka postoji graf (sa usmjerenim rubovima) u kojem je njegov kapacitet naznačen za svaku ivicu. I data su dva vrha: odvod i izvor. Za svaku ivicu je potrebno naznačiti koliko će tekućine teći kroz nju (ne više od njenog protoka) kako bi se maksimizirao ukupan protok od izvora do drena (tečnost se ne može pojaviti ili nestati na svim vrhovima, osim na drenažu i izvor).
Uzmimo kao varijable količinu tekućine koja teče kroz rebro. Onda
,gdje je propusnost ivice. Ove nejednakosti se moraju dopuniti jednakošću količine tečnosti koja ulazi i izlazi za svaki vrh, osim za odvod i izvor. Kao funkciju, prirodno je uzeti razliku između količine tečnosti koja izlazi i doliva na izvoru.
Generalizacija prethodnog problema je maksimalni protok minimalnih troškova. U ovom zadatku su dati troškovi za svaku ivicu i potrebno je među maksimalnim tokovima odabrati tok sa minimalnim troškovima. Ovaj problem se svodi na dva problema linearnog programiranja: prvo morate riješiti problem maksimalnog protoka, a zatim ovom problemu dodati ograničenje, gdje je maksimalna vrijednost protoka, i riješiti problem novom funkcijom - troškom protoka.
Ovi problemi se mogu riješiti brže od općih algoritama za rješavanje problema linearnog programiranja zbog posebne strukture jednačina i nejednačina.
Transportni zadatak
Postoji određeni homogeni teret koji treba prebaciti iz skladišta u fabrike. Za svako skladište se zna koliko se tereta nalazi u njemu, a za svaki pogon je poznata njegova potreba za teretom. Troškovi transporta su proporcionalni udaljenosti od skladišta do pogona (poznate su sve udaljenosti od -tog skladišta do -tog pogona). Potrebno je izraditi najjeftiniji plan transporta.
Odlučujuće varijable u ovom slučaju su količina tereta koja se transportuje od -tog skladišta do -tog pogona. Oni zadovoljavaju ograničenja:
Ciljna funkcija ima oblik:, koji mora biti minimiziran.
Igra nulte sume
Postoji matrica veličine. Prvi igrač bira broj od 1 do, drugi - od 1 do. Zatim provjeravaju brojeve i prvi igrač dobiva bodove, a drugi bodove (- broj koji je izabrao prvi igrač - drugi). Morate pronaći optimalnu strategiju za prvog igrača.
Pretpostavimo da se u optimalnoj strategiji, na primjer, prvog igrača, broj mora odabrati s vjerovatnoćom. Tada je optimalna strategija rješenje sljedećeg problema linearnog programiranja:
, , (),u kojoj želite maksimizirati funkciju. Vrijednost u optimalnom rješenju će biti očekivana isplata prvog igrača u najgorem slučaju.
Algoritmi rješenja
Najpoznatija i najšire korišćena u praksi za rešavanje opšteg problema linearnog programiranja (LP) je simpleks metoda. Uprkos činjenici da je simpleks metoda prilično efikasan algoritam koji je pokazao dobre rezultate u rješavanju primijenjenih LP problema, riječ je o algoritmu eksponencijalne složenosti. Razlog tome leži u kombinatornoj prirodi simpleks metode, koja sekvencijalno nabraja vrhove poliedra izvodljivih rješenja pri traženju optimalnog rješenja.
Prvi polinomski algoritam, metodu elipsoida, predložio je 1979. sovjetski matematičar L. Khachiyan, čime je riješen problem koji je dugo ostao neriješen. Metoda elipsoida ima potpuno drugačiju, nekombinatornu prirodu od simpleks metode. Međutim, u računskom smislu, pokazalo se da ova metoda nije obećavajuća. Ipak, sama činjenica polinomske složenosti problema dovela je do stvaranja čitave klase efikasnih LP algoritama - metode unutrašnje tačke, od kojih je prvi bio algoritam N. Karmarkara, predložen 1984. godine. Algoritmi ovog tipa koriste kontinuiranu interpretaciju LP problema, kada se, umjesto nabrajanja vrhova poliedra rješenja LP problema, vrši pretraga duž trajektorija u prostoru varijabli problema koje ne prolaze kroz vrhovima poliedra. Metoda unutrašnje tačke, koja, za razliku od simpleks metode, zaobilazi točke iz unutrašnjosti raspona, koristi metode nelinearnog programiranja log barijere koje su razvili 1960-ih od strane Fiaccoa i McCormicka.
vidi takođe
- Grafička metoda za rješavanje problema linearnog programiranja
Bilješke (uredi)
Književnost
- Thomas H. Cormen et al. Poglavlje 29. Linearno programiranje // Algoritmi: konstrukcija i analiza = UVOD U ALGORITME. - 2. izd. - M.: "Williams", 2006. - S. 1296. - ISBN 5-8459-0857-4
- Akulich I.L. Poglavlje 1. Problemi linearnog programiranja, Poglavlje 2. Posebni problemi linearnog programiranja // Matematičko programiranje u primjerima i problemima. - M.: Viša škola, 1986.-- 319 str. - ISBN 5-06-002663-9
- V. G. Karmanov Matematičko programiranje. - 3. izdanje. - M.: Nauka, 1986.-- 288 str.
- Danzig George Bernard "Sjećanja na početak linearnog programiranja"
Linkovi
- - Besplatan paket za optimizaciju dizajniran za rješavanje problema linearnog, cjelobrojnog i ciljnog programiranja.
- Vershik A. M. "O L. V. Kantorovichu i linearnom programiranju"
- Bolshakova I. V., Kuralenko M. V. „Linearno programiranje. Vodič za učenje za testni rad."
- Barsov A.S. "Šta je linearno programiranje", Popularna predavanja iz matematike, Gostekhizdat, 1959.
- M.N. Vyaly Linearne nejednačine i kombinatorika. - MCNMO, 2003.
Wikimedia fondacija. 2010.
- Zalten, Felix
- Glagov, Martina
Pogledajte šta je "Linearno programiranje" u drugim rječnicima:
linearno programiranje- - linearno programiranje Područje matematičkog programiranja posvećeno teoriji i metodama rješavanja ekstremnih problema, karakteriziranih linearnim odnosom između ... ... Vodič za tehničkog prevodioca
Linearno programiranje
Linearno programiranje- područje matematičkog programiranja, posvećeno teoriji i metodama rješavanja ekstremnih problema, koje karakterizira linearni odnos između varijabli. U svom najopštijem obliku, problem L.p. može se napisati ovako. Daju se…… Ekonomsko-matematički rječnik
Linearno programiranje je jedna od najvažnijih grana matematike koja proučava teorije i metode za rješavanje određenih problema. Posljednjih godina ova matematička disciplina je dobila široku primjenu u različitim oblastima ekonomije, tehnologije i vojnih poslova, gdje matematičko planiranje i upotreba automatskih digitalnih računara igraju važnu ulogu u njihovom razvoju. Ova grana nauke proučava modele linearne optimizacije. Drugim riječima, linearno programiranje je posvećeno broju
Po prvi put termin "linearno programiranje" predložio je američki ekonomista T. Koopmans 1951. godine. Godine 1975. Ruski matematičar L.V. Kantorovič i T.Kupmans dobili su Nobelovu nagradu za ekonomiju za doprinos teoriji optimalne alokacije resursa. T.Kupmans je promovirao metode linearnog programiranja i branio prioritete L.V. Kantorovicha, koji je otkrio ove metode.
Istorija linearnog programiranja u Sjedinjenim Državama seže do 1947. godine, kada je o tome pisao J. Danzig u svom radu. LV Kantorovich je proučavao mogućnost primjene matematike na pitanja planiranja, na osnovu čega je 1939. objavljena njegova monografija "Matematičke metode organizacije i planiranja proizvodnje". Najvažnije otkriće (otkriće) L.V. Kantorovicha bila je sposobnost da se matematički jasno formulišu najvažniji proizvodni problemi, što omogućava pronalaženje kvantitativnog pristupa ovim problemima, kao i njihovo rješavanje numeričkim metodama.
Da su prvi radovi L.V. Kantoroviča pravovremeno dobili odgovarajuću ocjenu, tada bi postojala velika vjerovatnoća još većeg napretka u linearnom programiranju u današnje vrijeme. Nažalost, njegov rad je ostao u sjeni kako u Sovjetskom Savezu, tako i šire, i, kako Danzig napominje: "...i za to vrijeme linearno programiranje postalo je prava umjetnost."
Optimalni plan bilo kojeg linearnog programa treba automatski biti povezan s optimalnim cijenama ili, prema L. V. Kantorovichu, s "objektivno određenim procjenama". Ova hrpa riječi imala je za cilj da poveća "otpor na kritiku" tog termina. Suština ekonomskog otkrića L.V. Kantorovicha leži u odnosu između optimalnih rješenja i optimalnih cijena.
Tehnike linearnog programiranja
Uz pomoć metoda linearnog programiranja rješava se veliki broj ekstremnih problema vezanih za ekonomiju. U tim slučajevima se pronalaze ekstremne vrijednosti (maksimalne i minimalne) nekih funkcija promjenjivih veličina.
Osnova linearnog programiranja je rješenje sistema linearnih jednačina, koje se pretvaraju u jednačine i nejednačine. Odlikuje se matematičkim izrazom varijabli, određenim redosledom, nizom proračuna i logičkom analizom. Primjenjivo je:
- u prisustvu matematičke sigurnosti i kvantitativnog ograničenja između proučavanih varijabli i faktora;
- sa zamenljivošću faktora zbog redosleda proračuna;
- u slučaju kombinovanja matematičke logike sa razumevanjem suštine proučavanih pojava.
U industrijskoj proizvodnji ova metoda pomaže da se izračunaju optimalne ukupne performanse mašina, agregata, proizvodnih linija (ako je specificiran asortiman proizvoda i odgovarajuće količine), kao i da se reši problem racionalne upotrebe materijala (sa najpovoljnijim brojem praznina).
U poljoprivredi se ovom metodom utvrđuje minimalni trošak obroka hrane, uzimajući u obzir datu količinu hrane (na osnovu vrste i nutrijenata koje sadrže).
U livačkoj industriji ova metoda pomaže u rješavanju problema mješavina koje čine metalurško punjenje. Isti metod omogućava da se reši problem transporta, problem najoptimalnije vezanosti preduzeća potrošača za preduzeća koja proizvode proizvode.
Posebnost svih ekonomskih problema koji se mogu riješiti primjenom metoda linearnog programiranja je izbor rješenja, kao i određeni granični uvjeti. Rješavanje takvog problema znači odabir najoptimalnije od svih alternativa.
Suštinska vrijednost primjene metoda linearnog programiranja u ekonomiji je izbor najoptimalnije opcije od ogromnog broja svih mogućih opcija. Na druge načine, takve probleme je gotovo nemoguće riješiti kako bi se pronašao stepen racionalnosti korištenja resursa u proizvodnji.
Jedan od glavnih zadataka koji se rješavaju primjenom linearnog programiranja je transportni zadatak, koji ima za cilj minimiziranje prometa robe široke potrošnje tokom njihove isporuke od proizvođača do potrošača.
