Konveksni skupovi i njihova svojstva. Da bi se proučavala svojstva ZLP-a, potrebno je dati rigoroznu 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 ispunjeni uslovi

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

Može se dokazati sljedeća teorema o reprezentaciji konveksnog poliedra.

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

Iz teoreme 1.1 proizlazi da je konveksni poliedar generisan svojim 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 određena 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 pisanja kanonskog problema.

Matrična notacija:

Evo OD– matrica reda, ALI je matrica sistema, X– matrična-kolona varijabli, IN– matrica-kolona slobodnih članova:

Vektorska notacija:

gdje vektori odgovaraju stupcima koeficijenata za nepoznate.

Sljedeća teorema je gore navedena, ali nije dokazana u opštem obliku.

Teorema 1.2. Skup svih dopuštenih rješenja sistema ograničenja jednog problema linearnog programiranja je konveksan.

dokaz: Neka bude - dva izvodljiva rješenja za LLP data u matričnom obliku. Zatim i . Razmotrimo konveksnu linearnu kombinaciju rješenja, tj.

i pokazuju da je to također izvodljivo rješenje za sistem (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 dopuštenih rješenja problema linearnog programiranja konveksan, odnosno da predstavlja konveksni poliedar ili konveksno poliedarsko područje koje će se u nastavku nazivati ​​jednim pojmom - razna rješenja.

Odgovor na pitanje u kojoj tački poliedra rješenja je moguće optimalno rješenje problema linearnog programiranja dat je 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: Pretpostavljamo da je poliedar rješenja ograničen. Njegove kutne tačke označavamo sa , a optimalno rješenje je gotovo X*. Onda F(X*)³ F(X) za sve bodove X rastvor poliedra. Ako X* je tačka ugla, onda je prvi dio teoreme dokazan.

Pretvarajmo se to X* nije ugaona tačka, onda 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 ekspanziji, među vrijednostima biramo maksimum. 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, dakle, s jedne strane optimalno rješenje, ali, s druge strane, to je i dokazano
F(X*)£ M, dakle, gde X k- ugaona tačka. Dakle, postoji ugaona tačka X k, u kojem linearna funkcija uzima maksimalnu vrijednost.

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

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

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

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

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

Dokazana teorema je fundamentalna, jer ukazuje na osnovni način rješavanja problema linearnog programiranja. Zaista, prema ovoj teoremi, umjesto proučavanja beskonačnog skupa dopuštenih 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 za pronalaženje 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 LLP sistema ograničenja (1.4) u kojem je prvo T komponenta - glavne varijable, i ostalo p - t komponenta - nebazične varijable jednake nuli u osnovnom rješenju (ako to nije slučaj, tada se odgovarajuće varijable mogu prenumerisati). Hajde da to pokažemo X

Pretpostavimo suprotno, tj. šta X nije ugaona tačka. Onda pokažite X može se predstaviti kao unutrašnja tačka segmenta koji povezuje dva različita, a ne podudaraju se sa 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 nula u ovom slučaju. Ove komponente se mogu smatrati vrijednostima nebazičnih 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, što znači da su tačke X 1 i X 2 spajanje, što je u suprotnosti sa pretpostavkom. shodno tome, X je 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. Hajde da to pokažemo X je prihvatljivo osnovno rješenje. nije tačka ugla, što je u suprotnosti sa uslovom. Stoga je naša pretpostavka pogrešna, tj. vektori su linearno nezavisni i X je dopustivo osnovno rješenje problema (1.4).

Važna posledica odmah sledi iz teorema 1.3 i 1.4: ako problem linearnog programiranja ima optimalno rješenje, onda se ono poklapa s barem jednim od njegovih izvodljivih osnovnih rješenja.

dakle, Optimum linearne funkcije problema linearnog programiranja treba tražiti među konačnom broju njegovih dopuštenih osnovnih rješenja.

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

Efikasni lekovi linearno programiranje leže u osnovi i cjelobrojnog i nelinearnog programiranja za rješavanje složenijih problema optimizacije. Za ove metode je, međutim, potrebno više vremena za izračunavanje.

U narednim predavanjima će se detaljno analizirati primjeri rješavanja tipičnih problema optimizacije i donošenja menadžerskih odluka pomoću 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 (pronaći njegov maksimum, minimum ili određenu numeričku vrijednost);
• postoje ograničenja, koja se obično izražavaju u obliku nejednakosti (npr. količina utrošenih 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 vrijeme za održavanje);
• postoji skup ulaznih vrijednosti-varijabli koje utječu na optimizirane vrijednosti i ograničenja.

Parametri zadatka su ograničeni sljedećim ograničenjima:

• broj nepoznatih je 200;
• broj ograničenja formule 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 rješenja;
• analiza rješenja.

Redoslijed potrebnih pripremnih radova pri rješavanju zadataka ekonomsko-matematičkog modeliranja pomoću MS Excel-a prikazan je na dijagramu toka 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 tačaka 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 ( ). Norme utroška materijala i strojnog vremena po jednoj polici svake vrste poslužile su kao normalizirani koeficijenti. 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 zadacima, vrijednosti varijabli moraju biti ograničene. Stoga je potrebno odrediti donju i gornju granicu područja njihovih promjena.

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

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

Normalizirani koeficijenti na vektoru željenih vrijednosti varijabli ne bi trebali prelaziti vrijednosti datog vektora resursa

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

Broj početnih elemenata sistema

Broj specificiranih vrsta resursa

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

Rice. 1.7.

• ako se ne dobije valjano rješenje, ispraviti početni model podataka;
• ako nije primljen optimalno rešenje, zatim uvesti dodatna ograničenja.

Problemi sa programom optimalno rešenje samo za modeliranje stvarnog problema, a ne za rješavanje samog problema. Prilikom konstruisanja modela napravljene su razne pojednostavljujuće pretpostavke realnog stanja. Ovo 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 u modelu, kako će se odluka promijeniti? Da bi se to saznalo, prije donošenja upravljačke odluke, vrši se analiza rješenja modela.

Analiza optimalno rešenje, ugrađen u program, završna je faza matematičkog modeliranja ekonomskih procesa. Omogućava dublju provjeru uklapanja modela u proces, kao i pouzdanost optimalnog rješenja. Zasnovan je na podacima optimalno rešenje i izvještaje koji se izdaju u "Traganju za rješenjem". Ali to ne isključuje niti zamjenjuje tradicionalnu analizu plana sa ekonomskih pozicija 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 pojedinačnih parametara problema: ako nije otporan na promjene većine parametara, smanjuje se garancija njegove implementacije i postizanja izračunatog optimuma;
• izvođenje varijantnih proračuna i dobijanje novih varijanti plana bez ponovnog rješavanja problema sa prvobitne osnove uz pomoć prilagođavanja.

Moguće metode analize prikazane su u šemi na slici 1.8.

Nakon dobijanja optimalnog rješenja, analizira se prema primljenim izvještajima. Analiza stabilnosti- proučavanje uticaja promjena pojedinačnih parametara modela na indikatore optimalnog rješenja. Limit Analysis- analiza prihvatljivih promjena u optimalnom planu, pri čemu plan ostaje optimalan.

S obzirom na odgovornost ekonomičnosti 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 dešava ako..."
• "Šta treba da..."

Poziva se analiza za odgovor na prvo pitanje varijantna analiza; analiza za odgovor na drugo pitanje se zove rješenja po mjeri.

Varijanta analiza je 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 optimizacijskog problema traži sa različitom strukturom ograničenja.
• Višekriterijumska analiza je rješenje problema za različite ciljne funkcije.
• Analiza pod uslovnim početnim podacima- kada početni podaci korišteni u rješavanju problema zavise od ispunjavanja dodatnih uslova.

Nakon analize, rezultate treba prikazati u grafičkom obliku i pripremiti izvještaj sa preporukama za donošenje odluke uzimajući u obzir konkretnu ekonomsku situaciju.

Definicija. Bilo koje rješenje sistema ograničenja naziva se prihvatljivo LLP rješenje.
Definicija. Izvedivo rješenje u kojem ciljna funkcija dosegne maksimalnu ili minimalnu vrijednost naziva se optimalno rješenje.

Na osnovu ovih definicija, LP problem se može formulirati na sljedeći način: između svih tačaka konveksne domene koja je rješenje za sistem ograničenja, odaberite onu čije koordinate minimiziraju (maksimiziraju) linearnu funkciju F = od 1 x + od 2 y.
Imajte na umu da su varijable x, y u LLP uzimaju, po pravilu, nenegativne vrijednosti ( x≥ 0, y≥ 0), tako da se region nalazi u prvoj četvrtini koordinatne ravni.

Razmotrimo linearnu funkciju F = od 1 x + od 2 y i popravi neku vrijednost F. Neka, na primjer, F= 0, tj. od 1 x + od 2 y= 0. Grafikon ove jednačine će biti prava linija koja prolazi kroz početak (0; 0) (Sl.).
Slika
Prilikom promjene ove fiksne vrijednosti F = d, ravno od 1 x+ od 2 y=d kretat će se paralelno i "crtati" cijelu ravan. Neka bude D- poligon - površina rješenja sistema ograničenja. Kada se promeni d ravno od 1 x + od 2 y = d, za neku vrijednost d = d 1 će doći do poligona D, nazovimo ovu tačku ALI"ulazna tačka", a zatim, nakon prolaska poligona, na određenoj vrijednosti d = d 2 imaćemo poslednju zajedničku tačku sa njim IN, pozovimo IN"izlazna tačka".
Očigledno je da je ciljna funkcija njegove najmanje i najveće vrijednosti F=od 1 x + od 2 y dosegnuti na ulaznim tačkama ALI i "izlaz" IN.
Uzimajući u obzir da funkcija cilja uzima optimalnu vrijednost na skupu izvodljivih rješenja na vrhovima regije D, možemo predložiti sljedeći plan za rješavanje LLP:

1. konstruirati domen rješenja sistema ograničenja;
2. konstruisati pravu liniju koja odgovara funkciji cilja, i paralelnim prevođenjem ove prave linije pronaći tačku "ulaska" ili "izlaska" (u zavisnosti od zahteva za minimiziranjem ili maksimiziranjem funkcije cilja);
3. odrediti koordinate ove tačke, izračunati vrijednost ciljne funkcije u njima.

Imajte na umu da vektor ( od 1 , od 2), okomito na pravu liniju, pokazuje smjer rasta ciljne funkcije.

U grafičkom rješenju LLP-a moguća su dva slučaja koja zahtijevaju posebnu raspravu.

Slučaj 1
Slika 6
Kada se krećete pravo od 1 x + od 2 y= d"ulazak" ili "izlaz" (kao na slici) će se pojaviti duž strane poligona. Ovo će se dogoditi ako poligon ima stranice paralelne s linijom. od 1 X+ od 2 at = d .
U ovom slučaju postoji beskonačan broj „izlaznih“ („ulaznih“) tačaka, odnosno bilo koje tačke segmenta AB. To znači da funkcija cilja uzima maksimalnu (minimalnu) vrijednost ne u jednoj tački, već u svim tačkama koje leže na odgovarajućoj strani poligona D.

Slučaj 2
Razmotrimo slučaj kada je raspon dopuštenih vrijednosti neograničen.
U slučaju neograničene domene, ciljna funkcija se može specificirati na takav način da linija koja joj odgovara nema "izlaznu" (ili "ulaznu") tačku. Tada maksimalna vrijednost funkcije (minimum) nikada nije dostignuta - kažu da funkcija nije ograničena.
Slika
Potrebno je pronaći maksimalnu vrijednost funkcije cilja F = 4x + 6y→ max , sa sistemom ograničenja
Konstruirajmo domenu dopuštenih rješenja, tj. grafički riješiti sistem nejednačina. Da bismo to učinili, konstruiramo svaku pravu liniju i definiramo poluravnine date nejednačinama.
x + y = 18

x	12	9
y	6	9

0,5x + y = 12

x	12	18
y	6	3

x= 12 - paralelno sa osom OY ;
y= 9 - paralelno sa osom OX ;
x= 0 - osa OY ;
y = 0 - osa OX;
x OY;
y≥ 0 – poluravnina iznad ose OX;
y≤ 9 - poluravan ispod y = 9;
x ≤ 12 - poluravan lijevo x = 12;
0,5x + yx + y = 12;
x + y x + y = 18.
Slika
Presjek svih ovih poluravni je očito pentagon OAVSD, sa vrhovima u tačkama O(0; 0), ALI(0; 9), IN(6; 9), OD(12; 6), D(12; 0). Ovaj pentagon čini područje izvodljivih rješenja problema.

F = 4x + 6y→ max.

x	3	0
y	–2	0

F = 0: 4x + 6y x+ 6y OD(12; 6). U njoj je F = 4x + 6y
Dakle, u x = 12, y= 6 funkcija F F= 4 ∙ 12 + 6 ∙ 6 = 84, jednako 84. Tačka sa koordinatama (12; 6) zadovoljava sve nejednakosti sistema ograničenja, a vrijednost funkcije cilja u njoj je optimalna F* = 84 (optimalna vrijednost će biti označena sa "*").
Problem riješen. Dakle, potrebno je proizvesti 12 proizvoda tipa I i 6 proizvoda tipa II, dok će profit biti 84 hiljade rubalja.

Grafička metoda se koristi za rješavanje problema koji imaju samo dvije varijable u sistemu ograničenja. Ova metoda se može primijeniti i na sisteme nejednačina sa tri varijable. Geometrijski, situacija će biti drugačija, ulogu pravih će imati ravni u trodimenzionalnom prostoru, a rješenje nejednakosti u tri varijable će biti poluprostor koji se nalazi na jednoj strani ravnine. Ulogu regiona imaće poliedri, koji su preseci poluprostora.

Primjer #2. Rudnik razvija dva sloja. Prinos finoće u prvom sloju je a1%; na drugom - a2%. Maksimalna produktivnost zaustavljanja u prvom sloju je B1 hiljada tona godišnje, u drugom sloju - B2 hiljade tona godišnje. Prema tehnologiji rada, proizvodnja iz drugog sloja ne može biti veća od proizvodnje iz prvog sloja. Proizvodnja kazni kroz rudnik ne bi trebalo da prelazi C1 hiljada tona godišnje. Ukupno opterećenje na dva šava godišnje ne bi trebalo da bude manje od C2 hiljade tona godišnje. Sastavite matematički model i izgradite skup dozvoljenih vrijednosti opterećenja za prvi i drugi sloj godišnje.

Primjer #3. U prodavnici se prodaju 2 vrste bezalkoholnih pića: kola i limunada. Prihod od jedne limenke kole je 5 centi, dok je prihod od jedne konzerve limunade 7 centi. U prosjeku, trgovina ne proda više od 500 limenki oba pića dnevno. Uprkos činjenici da kola proizvodi poznati brend, kupci preferiraju limunadu jer je mnogo jeftinija. Izračunato je da prodaja kole i limunade treba da bude u omjeru najmanje 2:1, a poznato je da se u radnji dnevno proda najmanje 100 limenki kole. Koliko limenki svakog pića bi prodavnica trebala imati na početku radnog dana da bi povećala prihod?

Primjer #4. Riješite problem linearnog programiranja na približno grafički način, nakon čega slijedi izračunavanje tačne vrijednosti i max(min) vrijednosti ciljne funkcije.

Primjer broj 5. Putničkoj kompaniji ne treba više od autobusa od tri tone i ne više od pet tona. Prodajna cijena autobusa prve marke je 20.000 USD, druge marke je 40.000 USD. Turistička kompanija može izdvojiti za kupovinu autobusa najviše c.u. Koliko autobusa svake marke treba kupiti posebno da bi njihova ukupna (ukupna) nosivost bila maksimalna. Riješite problem grafički.

Primjer broj 6. Grafičkom metodom pronađite optimalni plan proizvodnje u zadatku datom u tabeli.

Primjer broj 7. Riješite problem linearnog programiranja koristeći grafičku metodu, podvrgavajući sistem ograničenja Jordan-Gaussovim transformacijama. Sistem ograničenja problema ima oblik:
a 11 x 1 + a 12 x 2 + a 13 x 3 + a 14 x 4 + a 15 x 5 = b 1
a 21 x 1 + a 22 x 2 + a 23 x 3 + a 24 x 4 + a 25 x 5 = b 2
a 31 x 1 + a 32 x 2 + a 33 x 3 + a 34 x 4 + a 35 x 5 = b 3
Smjernice. Jordano-Gaussova transformacija se može obaviti pomoću ove usluge ili putem SLAE istraživanja.

Primjer broj 8. Kompanija proizvodi dvije vrste proizvoda A i B, za čiju proizvodnju se koriste tri vrste sirovina. Za proizvodnju jedinice proizvoda A potrebno je potrošiti sirovine svake vrste a1, a2, a3 kg, respektivno, a za jedinicu proizvoda B - v1, v2, v3 kg. Proizvodnja je obezbeđena sirovinama svake vrste u količini od P1, P2, P3 kg, respektivno. Trošak jedinice proizvoda A je C1 rub., a jedinice proizvoda B je C2 rub. Potrebno je izraditi plan za proizvodnju proizvoda A i B, koji osigurava maksimalnu cijenu gotovog proizvoda.

Primjer #2. Potrebno je pronaći maksimalnu vrijednost funkcije cilja F = 4x + 6y→ max, sa sistemom ograničenja:

Konstruirajmo domenu dopuštenih rješenja, tj. grafički riješiti sistem nejednačina. Da biste to učinili, odaberite broj ograničenja jednak 4 (slika 1).
Slika 1

Zatim popunjavamo koeficijente za varijable i sama ograničenja (slika 2).
Slika 2

Slika 3
x= 12 - paralelno sa osom OY;
y= 9 - paralelno sa osom OX;
x>= 0 - osa OY
y= 0 - osa OX;
x≥ 0 – poluravnina desno od ose OY;
y≥0 – poluravnina iznad ose OX;
y≤ 9 - poluravan ispod y = 9;
x≤ 12 - poluravan lijevo x = 12;
0,5x + y≤ 12 - poluravan ispod prave 0,5 x + y = 12;
x + y≤ 18 - poluravan ispod prave linije x + y = 18.

Presjek svih ovih poluravnina je petougao ABCDE, sa vrhovima u tačkama A(0; 0), B(0;9), C(6; 9), D(12;6), E(12;0). Ovaj pentagon čini područje izvodljivih rješenja problema.

Razmotrite ciljnu funkciju problema F = 4x + 6y→ max.

x	3	0
y	–2	0

Konstruirajmo pravu liniju koja odgovara vrijednosti funkcije F = 0: 4x + 6y= 0. Pomerićemo ovu liniju na paralelan način. Iz cijele porodice linija 4 x + 6y= const posljednji vrh kroz koji linija prolazi kada ide izvan granice poligona bit će vrh OD(12; 6). U njoj je F = 4x + 6y dostiže svoju maksimalnu vrijednost.

Dakle, u x = 12, y= 6 funkcija F dostiže svoju maksimalnu vrijednost F= 4 ∙ 12 + 6 ∙ 6 = 84, jednako 84. Tačka sa koordinatama (12;6) zadovoljava sve nejednakosti sistema ograničenja, a vrijednost funkcije cilja je u njoj optimalna F* = 84.

Test iz discipline "Operaciono istraživanje"

(tačni odgovori su prvi)

1. Termin „operativno istraživanje” je skovan…

tokom Drugog svetskog rata

50-ih godina XX veka

60-ih godina XX veka

70-ih godina XX veka

90-ih godina XX veka

početkom 21. veka

2. Operativno istraživanje se podrazumijeva kao (odaberite najprikladniju opciju) ...

skup naučnih metoda za rešavanje problema efikasnog upravljanja organizacionim sistemima

skup mera koje se preduzimaju za sprovođenje određenih operacija

skup metoda za implementaciju plana

naučne metode alokacije resursa u organizaciji proizvodnje

3. Navedite korake kroz koje obično prolazi svako operativno istraživanje:

formulisanje problema

konstrukcija smislenog (verbalnog) modela razmatranog objekta (procesa)

izgradnja matematičkog modela

rješavanje problema formulisanih na osnovu konstruisanog matematičkog modela

verifikacija dobijenih rezultata za adekvatnost prirode sistema koji se proučava

implementacija dobijenog rješenja u praksi

4. U operacijskom istraživanju, operacija se podrazumijeva kao ...

bilo koji događaj (sistem akcija), ujedinjen jednim planom i usmjeren na postizanje nekog cilja

bilo koji događaj bez upravljanja

skup tehničkih mjera koje osiguravaju proizvodnju potrošačkih proizvoda

5. Rješenje se naziva optimalnim, ...

ako je iz ovog ili onog razloga poželjniji od drugih

ako je racionalno

ako je to dogovoreno sa nadležnima

ako to odobri generalna skupština

6. Matematičko programiranje...

bavi se proučavanjem ekstremnih problema i razvojem metoda za njihovo rješavanje

je proces kreiranja kompjuterskih programa pod vodstvom matematičara

rješava matematičke probleme na računaru

7. Zadatak linearnog programiranja je ...

pronalaženje najveće (najmanje) vrijednosti linearne funkcije u prisustvu linearnih ograničenja

kreiranje linearnog programa u odabranom programskom jeziku, dizajniranog za rješavanje zadanog problema

opis linearnog algoritma za rješavanje zadatog problema

8. U problemu kvadratnog programiranja ...

ciljna funkcija je kvadratna

izvodljiva površina rješenja je kvadrat

ograničenja sadrže kvadratne funkcije

9. U problemima cjelobrojnog programiranja...

nepoznate mogu uzeti samo cjelobrojne vrijednosti

ciljna funkcija mora nužno imati cjelobrojnu vrijednost, a nepoznanice mogu biti bilo koje

ciljna funkcija je numerička konstanta

10. U problemima parametarskog programiranja ...

funkcija cilja i/ili ograničenje sadrži parametar(e)

domen izvodljivih rješenja je paralelogram ili paralelepiped

broj varijabli može biti samo paran

11. U problemima dinamičkog programiranja…

proces pronalaženja rješenja je višestepeni

potrebno je racionalizirati proizvodnju dinamita

potrebno je optimizirati korištenje zvučnika

12. Postavlja se sljedeći problem linearnog programiranja:

F(X 1, X 2) = 5X 1 + 6X 2→ max

0.2X 1 + 0.3X 2 ≤ 1.8,

0.2X 1 + 0.1X 2 ≤ 1.2,

0.3X 1 + 0.3X 2 ≤ 2.4,

X 1 ≥ 0, X 2 ≥ 0.

Odaberite zadatak koji je ekvivalentan ovom zadatku.

F(X 1, X 2)= 5X 1 + 6X 2 → max,

2X 1 + 3X 2 ≤ 18,

2X 1 + X 2 ≤ 12,

X 1 + X 2 ≤ 8,

X 1 ≥ 0,

X 2 ≥ 0.

F(X 1, X 2)= 6X 1 + 5X 2 → min,

2X 1 + 3X 2 ≤ 18,

2X 1 + X 2 ≤ 12,

X 1 + X 2 ≤ 8,

X 1 ≥ 0,

X 2 ≥ 0.

F(X 1, X 2)= 50X 1 + 60X 2 → max,

2X 1 + 3X 2 ≤ 18,

2X 1 + X 2 ≤ 12,

X 1 + X 2 ≤ 8,

X 1 ≥ 0,

X 2 ≥ 0.

F(X 1, X 2)= 5X 12 + 6X 22 → max,

2X 1 + 3X 2 ≤ 18,

2X 1 + X 2 ≤ 12,

3X 1 + X 2 ≤ 2.4,

X 1 ≥ 0,

X 2 ≥ 0.

13. Ciljna funkcija problema linearnog programiranja može biti funkcija:

F=12x1+20x2–3 0x3→min

F= →min

F=→max

F=→max.

14. Sistem ograničenja za problem linearnog programiranja može biti sistem:

15. Simpleksna metoda je:

analitička metoda za rješavanje glavnog problema linearnog programiranja

metoda za pronalaženje područja izvodljivih rješenja za problem linearnog programiranja;

grafička metoda za rješavanje glavnog problema linearnog programiranja;

metoda za svođenje opšteg problema linearnog programiranja na kanonski oblik.

16. Zadatak linearnog programiranja je:

pronalaženje najveće ili najmanje vrijednosti linearne funkcije u prisustvu linearnih ograničenja

razvoj linearnog algoritma i njegova implementacija na računaru

sastavljanje i rješavanje sistema linearnih jednačina

traženje linearne putanje razvoja procesa opisanog datim sistemom ograničenja.

17. Područje dopuštenih rješenja problema linearnog programiranja ne mogu izgleda ovako:

18. Ciljna funkcija problema linearnog programiranja može biti funkcija:

F=12x1+20x2–3 0x3→min

F= →min

F=→max

F=→max.

19. Sistem ograničenja za problem linearnog programiranja može biti sistem:

20. Područje prihvatljivih rješenja problema linearnog programiranja ima oblik:

F(X 1, X 2)= 3X 1 + 5X 2 jednako...

21. Područje prihvatljivih rješenja problema linearnog programiranja ima oblik:

Zatim maksimalna vrijednost funkcije F(X 1, X 2)= 5X 1 + 3X 2 jednako...

22. Područje prihvatljivih rješenja problema linearnog programiranja ima oblik:

Zatim maksimalna vrijednost funkcije F(X 1, X 2)= 2X 1 - 2X 2 jednako...

23. Područje prihvatljivih rješenja problema linearnog programiranja ima oblik:

F(X 1, X 2)= 2X 1 - 2X 2 jednako...

24. Područje prihvatljivih rješenja problema nelinearnog programiranja ima oblik:

Zatim maksimalna vrijednost funkcije F(X 1, X 2)= X 2 – X 12 je jednako...

25. Maksimalna vrijednost funkcije cilja F(X 1, X 2)= 5X 1 + 2X 2 pod ograničenjima
X 1 + X 2 ≤ 6,

X 1 ≤ 4,

X 1 ≥ 0, X 2 ≥ 0, jednako ...

26. Mala firma proizvodi dvije vrste proizvoda. Za proizvodnju jednog proizvoda tipa A utroši se 2 kg sirovina, za proizvodnju jednog proizvoda tipa B - 1 kg. Ukupno ima 60 kg sirovina. Potrebno je izraditi proizvodni plan koji osigurava najveći prihod, ako je prodajna cijena jednog proizvoda tipa A 3 CU, tipa B 1 c.u. Odnosno, štaviše, proizvoda tipa A treba napraviti najviše 25, a tipa B - ne više od 30.

Ovaj zadatak je…

problem linearnog programiranja

problem riješen dinamičkim programiranjem

zadatak planiranja mreže.

27. Mala firma proizvodi dvije vrste proizvoda. Za proizvodnju jednog proizvoda tipa A utroši se 2 kg sirovina, za proizvodnju jednog proizvoda tipa B - 1 kg. Ukupno ima 60 kg sirovina. Potrebno je izraditi proizvodni plan koji osigurava najveći prihod, ako je prodajna cijena jednog proizvoda tipa A 3 CU, tipa B 1 c.u. Odnosno, štaviše, proizvoda tipa A treba napraviti najviše 25, a tipa B - ne više od 30.

Ciljna funkcija ovog problema je funkcija ...

F(x1,x2)=3x1+x2→max

F(x1,x2)=25x1+30x2→max

F(x1,x2)=2x1+x2→max

F(x1,x2)=60-2x1-x2→min

28. Mala firma proizvodi dvije vrste proizvoda. Za proizvodnju jednog proizvoda tipa A utroši se 2 kg sirovina, za proizvodnju jednog proizvoda tipa B - 1 kg. Ukupno ima 60 kg sirovina. Potrebno je izraditi proizvodni plan koji osigurava najveći prihod, ako je prodajna cijena jednog proizvoda tipa A 3 CU, tipa B 1 c.u. e., a proizvoda tipa A potrebno je napraviti najviše 25, a tipa B - ne više od 30

Važeći plan za ovaj zadatak je plan:

X=(20, 20)

X=(25, 15)

X=(20, 25)

X=(30, 10)

29. U dvije tačke A1 i A2 nalazi se 60 odnosno 160 jedinica robe. Sva roba se mora transportovati do tačaka B1, B2, B3 u količini od 80, 70 i 70 jedinica. Tarifna matrica je sljedeća: . Planirajte transport tako da njihov trošak bude minimalan.

Ovaj zadatak je…

transportni zadatak

problem nelinearnog programiranja

problem trgovaca

zadatak zadatka

30. U dvije tačke A1 i A2 nalazi se 60 odnosno 160 jedinica robe. Sva roba se mora transportovati do tačaka B1, B2, B3 u količini od 80, 70 i 70 jedinica. Tarifna matrica je sljedeća: . Planirajte transport tako da njihov trošak bude minimalan

Osnovni plan za ovaj zadatak je plan:

;

31. U dvije tačke A1 i A2 nalazi se 60 odnosno 160 jedinica robe. Sva roba se mora transportovati do tačaka B1, B2, B3 u količini od 80, 70 i 70 jedinica. Tarifna matrica je sljedeća: . Planirajte transport tako da njihov trošak bude minimalan.

Ciljna funkcija ovog zadatka je funkcija:

F=4x11+6x12+ 8x13+5x21+8x22+7x23→min

F= →min

F=60x1+160x2+ 80x3+70x4+705 →max

F=60x1+160x2– 80x3– 70x4– 705 →min

32. U dvije tačke A1 i A2 nalazi se 60 odnosno 160 jedinica robe. Sva roba se mora transportovati do tačaka B1, B2, B3 u količini od 80, 70 i 70 jedinica. Tarifna matrica je sljedeća: . Planirajte transport tako da njihov trošak bude minimalan.

Optimalni plan za ovaj zadatak je plan:

;

.

;

;

33. Transportni zadatak

biće zatvoren ako...

34. Transportni zadatak

je…

otvoren

zatvoreno

nerastvorljiv

35. Transportni zadatak

je…

zatvoreno

otvoren

nerastvorljiv

36. Za rješavanje sljedećeg transportnog problema

potrebno je da unesete...

fiktivni potrošač

fiktivni dobavljač;

efektivna tarifa

37. Za rješavanje sljedećeg transportnog problema

potrebno je da unesete...

fiktivni dobavljač;

fiktivni potrošač

efektivna tarifa

efektivna kamatna stopa.

38. Među ovim transportnim zadacima

zatvoreni su…

39. Početni osnovni plan transportnog zadatka može se izraditi ...

sve gore navedene metode

metoda sjeverozapadnog ugla

metod minimalne tarife

metoda dvostruke preferencije

Vogelova metoda aproksimacije

40. Ako je ciljna funkcija problema linearnog programiranja postavljena na maksimum, onda je ... ciljna funkcija dualnog problema postavljena na minimum

nema objektivne funkcije u dualnom problemu

dvojni problem nema rješenja

dualni problem ima beskonačno mnogo rješenja

41. S obzirom na problem linearnog programiranja:

F(X 1, X 2)= 2X 1 + 7X 2 → max,

2X 1 + 3X 2 ≤ 14,

X 1 + X 2 ≤ 8,

X 1 ≥ 0, X 2 ≥ 0.

Dual za ovaj problem je sljedeći…

f*(y1, y2)= 14y1 + 8y2 → min,

3g 1 + y2 ³ 7,

y 1 ≥ 0, y2 ≥ 0.

f*(y1, y2)= 2y1 + 7y2 → min,

2y1 + 3y2 ³ 14,

y 1 + y2 ³ 8,

y 1 £ 0, y2 0 £.

f*(y1, y2)= 2y1 + 7y2 → min,

3 y 1 + y2 ³ 7,

y 1 £ 0, y2 0 £.

f*(y1, y2)= 14y1 + 8y2 → min,

y 1 + y2 ³ 7,

y 1 ≥ 0, y2 ≥ 0.

42. Ako jedan od par dvojnih problema ima optimalan plan, onda ...

a drugi ima optimalan plan

drugi nema optimalan plan

drugi nema valjana rješenja

43. Ako jedan od par dvojnih problema ima optimalan plan, onda...

a drugi ima optimalan plan i vrijednosti ciljnih funkcija pod njihovim optimalnim planovima su međusobno jednake

a drugi ima optimalan plan, ali vrijednosti ciljnih funkcija za njihove optimalne planove nisu međusobno jednake

drugi problem možda nema optimalan plan, ali ima izvodljiva rješenja

44. Ako ciljna funkcija jednog od para dualnih problema nije ograničena (za maksimalni problem - odozgo, za minimalni problem - odozdo), tada

drugi zadatak nema valjane planove

drugi zadatak ima važeće planove, ali nema optimalan plan

ciljna funkcija drugog zadatka također nije ograničena

45. Prilikom rješavanja nekih problema nelinearnog programiranja, ...

Lagrangeova metoda množenja

Gaussova metoda

Vogelova metoda aproksimacije

Gomory metoda

46. ​​Dat je problem nelinearnog programiranja

F(X 1, X 2)= X 12 + X 22 → max,

X 1 + X 2 =6,

X 1 ≥ 0, X 2 ≥ 0.

F(X 1, X 2) …

nije ostvarivo (+ ¥)

47. Dat je problem nelinearnog programiranja

F(X 1, X 2)= X 12 + X 22 → min,

X 1 + X 2 =6,

X 1 ≥ 0, X 2 ≥ 0.

F(X 1, X 2) …

48. Dat je problem nelinearnog programiranja

F(X 1, X 2)= X 12 + X 22 → max,

X 1 + X 2 =6,

X 1, X 2 - bilo koji.

Najveća vrijednost funkcije cilja F(X 1, X 2) …

nije ostvarivo (+ ¥)

49. Dat je problem nelinearnog programiranja

F(X 1, X 2)= X 12 + X 22 → min,

X 1 + X 2 =6,

X 1, X 2 - bilo koji.

Najmanja vrijednost funkcije cilja F(X 1, X 2) …

nije ostvarivo (- ¥)

50. Područje prihvatljivih rješenja problema nelinearnog programiranja ima oblik:

Zatim maksimalna vrijednost funkcije F(X 1, X 2)= X 12 +X 22 je jednako...

51. Područje prihvatljivih rješenja problema nelinearnog programiranja ima oblik:

Zatim minimalna vrijednost funkcije F(X 1, X 2)= X 12 +X 22 je jednako...

52. Za rješavanje transportnog problema može se koristiti...

potencijalna metoda

Lagrangeova metoda množenja

Gaussova metoda

metoda dezorijentacije

53. U sistemu ograničenja opšteg problema linearnog programiranja ...

54. U sistemu ograničenja standardnog (simetričnog) problema linearnog programiranja ...

mogu biti prisutne samo nejednakosti

mogu biti prisutne i jednačine i nejednačine

mogu biti prisutne samo jednačine

55. U sistemu ograničenja kanonskog (osnovnog) problema linearnog programiranja ...

mogu biti prisutne samo jednadžbe (pod uslovom da varijable nisu negativne)

mogu biti prisutne samo nejednakosti (pod uslovom da varijable nisu negativne)

mogu biti prisutne i jednadžbe i nejednačine (pod uvjetom da su varijable nenegativne)

56. Problem linearnog programiranja

F(X 1, X 2)= 2X 1 + 7X 2 → max,

2X 1 + 3X 2 ≤ 14,

X 1 + X 2 ≤ 8,

X 1 ≥ 0, X 2 ≥ 0.

upisan u...

standardni (simetrični) oblik

kanonski (osnovni) oblik

verbalni oblik

57. Za snimanje zadatka

F(X 1, X 2)= 2X 1 + 7X 2 → max,

2X 1 + 3X 2 ≤ 14,

X 1 + X 2 ≤ 8,

X 1 ≥ 0, X 2 ≥ 0.

u kanonskom obliku...

58. Za snimanje zadatka

F(X 1, X 2)= 2X 1 + 7X 2 → max,

2X 1 + 3X 2 ≤ 14,

X 1 + X 2 ≤ 8,

X 1 + 4X 2 ≥ 10,

X 1 ≥ 0, X 2 ≥ 0.

u kanonskom obliku...

potrebno je uvesti tri dodatne nenegativne varijable

potrebno je uvesti dvije dodatne nenegativne varijable

potrebno je uvesti četiri dodatne nenegativne varijable

59. Za snimanje zadatka

F(X 1, X 2)= 2X 1 + 7X 2 → max,

2X 1 + 3X 2 = 14,

X 1 + X 2 ≤ 8,

X 1 + 4X 2 ≥ 10,

X 1 ≥ 0, X 2 ≥ 0.

u kanonskom obliku...

potrebno je uvesti dvije dodatne nenegativne varijable

potrebno je uvesti tri dodatne nenegativne varijable

potrebno je uvesti četiri dodatne nenegativne varijable

potrebno je uvesti pet dodatnih nenegativnih varijabli

60. Prilikom rješavanja problema cjelobrojnog programiranja, ...

Gomory metoda

Lagrangeova metoda množenja

Gaussova metoda

Vogelova metoda aproksimacije

61. Osnova rješavanja problema metodom dinamičkog programiranja je ...

princip "Occamovog brijača"

princip "zub za zub, oko za oko"

hajzenbergov princip

62 . Situacija u kojoj učestvuju stranke čiji su interesi potpuno ili djelimično suprotstavljeni naziva se ...

(konflikt, sukob, sukob, sukob)

63. Pravi ili formalni sukob u kojem postoje najmanje dva učesnika (igrača), od kojih svaki teži ostvarivanju vlastitih ciljeva, naziva se ...

(igra, igra)

64. Dozvoljene radnje svakog od igrača u cilju postizanja određenog cilja nazivaju se ...

(pravila igre, pravila igre)

65. Kvantitativno vrednovanje rezultata igre naziva se ...

(plaćanje, plaćanje, plaćanje)

66. Ako u igri učestvuju samo dvije strane (dvije osobe), igra se naziva ...

(dvostruka, dupla, dupla igra, dupla igra)

67. Ako je u igri parova zbir uplata jednak nuli, odnosno gubitak jednog igrača jednak je dobitku drugog, tada se igra naziva igrom...

(nulti zbroj)

68. Nedvosmislen opis igračevog izbora u svakoj od mogućih situacija u kojoj mora napraviti lični potez se zove..

(strategija igrača, strategija igrača, strategija, strategija)

69. Ako, uz ponovljeno ponavljanje igre, strategija pruža igraču maksimalnu moguću prosječnu dobit (minimalni mogući prosječni gubitak), tada se takva strategija naziva ...

(optimalna, optimalna, optimalna strategija, optimalna strategija)

70. Neka je a najniža cijena, a b najviša cijena u igri parova sa nultom sumom. Onda je izjava tačna...

71. Neka je a najniža cijena, a b najviša cijena igre parova sa nultom sumom. Ako je a = b = v, tada se broj v naziva ...

po cijenu igre

bilansna tačka

optimalna strategija

mješovita strategija

72. Neka je a najniža cijena, a b najviša cijena u igri parova sa nultom sumom. Ako je a = b, onda se igra zove...

saddle point igra

nerešivi sukob

igra bez pravila

73. Vektor, čija svaka komponenta pokazuje relativnu učestalost igračeve upotrebe odgovarajuće čiste strategije, naziva se ...

mješovita strategija

vodeći vektor

normalni vektor

gradijent

74. Niža cijena matrične igre koju daje matrica isplate je…

Više od najniže cijene

jednaka nižoj cijeni

ne postoji

81. Matrična igra data matricom isplate, …

ima sedlo

nema sedlo

nije par

82. Cijena igre data matricom isplate je…

83. Matrična igra data matricom isplate, …

je parna soba

ima sedlo

nije par

84. Igra parova sa nultom sumom s obzirom na njenu matricu isplate može se svesti na...

problem linearnog programiranja

problem nelinearnog programiranja

problem cjelobrojnog linearnog programiranja

klasični problem optimizacije

85. Niža cijena matrične igre koju daje matrica isplate je…

Više od najniže cijene

jednaka nižoj cijeni

ne postoji

92. Matrična igra data matricom isplate, …

nema sedlo

ima sedlo

nije par

93. Cijena igre data matricom isplate je unutar...

94. Ako događaji u toku događaja slijede jedan za drugim u unaprijed određenim i strogo određenim vremenskim intervalima, onda se takav tok naziva ...

redovno

organizovano

95. Ako vjerovatnoća da bilo koji broj događaja pogodi vremenski interval zavisi samo od dužine ovog intervala i ne zavisi od toga koliko je ovaj interval udaljen od početka vremenske reference, tada se odgovarajući tok događaja naziva:

stacionarno

teče bez posledica

najjednostavniji

Poisson

96. Ako broj događaja koji pada na jedan od proizvoljno odabranih vremenskih intervala ne zavisi od broja događaja koji pada na drugi, također proizvoljno odabran vremenski interval, pod uslovom da se ti intervali ne sijeku, tada se odgovarajući tok događaja naziva ...

teče bez posledica

redovno

otkrivajući

normalno

97. Ako je vjerovatnoća pogađanja dva ili više događaja odjednom u vrlo kratkom vremenskom periodu zanemarljiva u poređenju sa vjerovatnoćom pogađanja samo jednog događaja, tada se odgovarajući tok događaja naziva ...

običan

izvanredno

normalno

Poisson

98. Ako tok događaja istovremeno ima svojstva stacionarnosti, običnosti i odsustva posledica, onda se naziva:

najjednostavniji (Poisson)

normalno

99. Jednokanalni CMO sa kvarovima je mjesto svakodnevnog održavanja za autopraonicu. Aplikaciji - automobilu koji je stigao u vrijeme kada je pošta zauzeta - odbijena je usluga. Intenzitet protoka automobila λ=1,0 (auto na sat). Prosečno vreme servisiranja je 1,8 sati. Protok automobila i tok usluga su najjednostavniji. Zatim, u stabilnom stanju, relativna propusnost q jednako...

100. Jednokanalni CMO sa kvarovima je mjesto svakodnevnog održavanja za autopraonicu. Aplikaciji - automobilu koji je stigao u vrijeme kada je pošta zauzeta - odbijena je usluga. Intenzitet protoka automobila λ=1,0 (auto na sat). Prosečno vreme servisiranja je 1,8 sati. Protok automobila i tok usluga su najjednostavniji. Tada, u stabilnom stanju, postotak automobila kojima je uskraćen servis jednak je ...

Opća formulacija problema linearnog programiranja (LPP). PLP primjeri

Linearno programiranje je grana matematike koja proučava metode za rješavanje ekstremnih problema koje karakterizira linearni odnos između varijabli i linearni kriterij optimalnosti. Nekoliko riječi o samom terminu linearnog programiranja. To zahtijeva ispravno razumijevanje. U ovom slučaju, programiranje, naravno, nije kompajliranje kompjuterskih programa. Programiranje ovdje treba tumačiti kao planiranje, formiranje planova, razvoj programa djelovanja. Matematički problemi linearnog programiranja obuhvataju proučavanje specifičnih proizvodnih i ekonomskih situacija, koje se u jednom ili drugom obliku tumače kao problemi optimalnog korišćenja ograničenih resursa. Raspon problema koji se rješavaju primjenom metoda linearnog programiranja prilično je širok. Ovo je na primjer:

• - problem optimalnog korišćenja resursa u planiranju proizvodnje;
• - problem mješavina (planiranje sastava proizvoda);
• - problem pronalaženja optimalne kombinacije različitih vrsta proizvoda za skladištenje u skladištima (upravljanje zalihama ili "problem ranca");
• - transportni poslovi (analiza lokacije preduzeća, kretanje robe). Linearno programiranje je najrazvijeniji i najšire korišteni dio matematičkog programiranja (osim toga, ovo uključuje: cjelobrojno, dinamičko, nelinearno, parametarsko programiranje). Ovo se objašnjava na sljedeći način:
• - matematički modeli velikog broja ekonomskih problema su linearni u odnosu na tražene varijable;
• - ova vrsta problema je trenutno najviše proučavana. Za njega su razvijene posebne metode uz pomoć kojih se ovi problemi rešavaju i odgovarajući kompjuterski programi;
• - mnogi problemi linearnog programiranja, koji se rješavaju, našli su široku primjenu;
• - neki problemi koji u originalnoj formulaciji nisu linearni, nakon niza dodatnih ograničenja i pretpostavki, mogu postati linearni ili se svesti u takav oblik da se mogu riješiti metodama linearnog programiranja. Ekonomski i matematički model bilo kojeg problema linearnog programiranja uključuje: ciljnu funkciju čija se optimalna vrijednost (maksimalna ili minimalna) mora pronaći; ograničenja u obliku sistema linearnih jednačina ili nejednačina; zahtjev nenegativnosti varijabli. Općenito, model je napisan na sljedeći način:
• - ciljna funkcija:

C1x1 + c2x2 + ... + cnxn > max(min);- ograničenja:

a11x1 + a12x2 + ... + a1nxn(?=?)b1,

a21x1 + a22x2 + ... + a2nxn(?=?)b2

am1x1 + am2x2 + ... + amnxn (? = ?) bm;

Zahtjev nenegativnosti:

U ovom slučaju, aij, bi, cj () su date konstante. Problem je pronaći optimalnu vrijednost funkcije (2.1) podložna ograničenjima (2.2) i (2.3). Sistem ograničenja (2.2) naziva se funkcionalnim ograničenjima problema, a ograničenja (2.3) direktnim. Vektor koji zadovoljava ograničenja (2.2) i (2.3) naziva se izvodljivo rješenje (plan) problema linearnog programiranja. Plan za koji funkcija (2.1) dostigne svoju maksimalnu (minimalnu) vrijednost naziva se optimalnim.

Zatim dajemo primjere nekih tipičnih problema riješenih korištenjem metoda linearnog programiranja. Takvi zadaci imaju pravi ekonomski sadržaj. Sada ćemo ih samo formulirati u smislu LLP-a, a u nastavku ćemo razmotriti metode za rješavanje takvih problema.

1. Problem optimalnog korištenja resursa u planiranju proizvodnje. Opšte značenje problema ove klase je sljedeće. Kompanija proizvodi n različitih proizvoda. Njihova proizvodnja zahtijeva m različitih vrsta resursa (sirovine, materijali, radno vrijeme itd.). Resursi su ograničeni, njihove rezerve u planskom periodu su, redom, b1, b2,..., bm konvencionalne jedinice. Poznati su i tehnološki koeficijenti aij, koji pokazuju koliko je jedinica i-tog resursa potrebno za proizvodnju jedinice proizvoda j-te vrste (). Dobit koju preduzeće primi od prodaje proizvoda j-te vrste jednaka je cj. U planskom periodu vrijednosti aij, bi i cj ostaju konstantne. Potrebno je izraditi takav plan proizvodnje proizvoda, u čijoj implementaciji bi profit preduzeća bio najveći. U nastavku dajemo jednostavan primjer problema ove klase.

Kompanija je specijalizovana za proizvodnju hokejaških palica i šahovskih garnitura. Svaki štap kompaniji donosi profit od 2$, a svaki šahovski set -4$. Za stvaranje jednog kluba potrebno je četiri sata rada na lokaciji A i dva sata rada na lokaciji B. -sati dnevno, sekcija B - 72 n-sata i sekcija C - 10 n-sati. Koliko palica i šahovskih garnitura treba da proizvodi kompanija dnevno da bi maksimizirala profit?

Uslovi problema ove klase često su predstavljeni u obliku tabele (videti tabelu 2.1).

Pod ovim uslovom, formulišemo problem linearnog programiranja. Označimo: x1 - broj hokejaških palica proizvedenih dnevno, x2 - broj šahovskih garnitura proizvedenih dnevno. PLP formulacija:

4x1 + 6x2 ? 120

Naglašavamo da svaka nejednakost u sistemu funkcionalnih ograničenja u ovom slučaju odgovara jednom ili drugom proizvodnom mestu, i to: prva - sekciji A, druga - sekciji B, treća - sekciji C.

Sistem varijabli u problemu optimizacije strukture zasejanih površina, uzimajući u obzir plodorede