Prijelaz s ograničenja linearnog matematičkog modela. Napravite matematički model problema linearnog programiranja. Izbor volumena preraspodjele

Predavanje 2

V kanonski oblik

prihvatljiva odluka ZJN -a(prihvatljiv plan).

optimalno rješenje za LPP.

Potreba

Primjer.

Zapišimo zadatak u kanonski oblik

Posebne situacije grafičkog rješenja LPP-a

Osim kada ima problema jedino optimalno rješenje za i možda posebne situacije:

1.problem ima beskonačan broj optimalnih rješenja - ekstrem funkcije je postignut na intervalu ( alternativni optimum)- slika 2;

2.zadatak nije rješivo zbog neograničenosti IDT -a, ili - slika 3;

3. SDT - pojedinačna točka Ah, dakle;

4.zadatak nije rješivo ako je ODR prazno područje.

A

Slika 2 Slika 3

Ako je linija razine paralelna sa stranicom područja izvedivih rješenja, tada je ekstremum postignut u svim točkama stranice. Problem ima bezbroj optimalnih rješenja - alternativni optimum ... Optimalno rješenje nalazi se po formuli

gdje je parametar Za bilo koju vrijednost od 0 do 1 moguće je dobiti sve točke segmenta, za svaku od kojih funkcija uzima istu vrijednost. Odatle i naziv - alternativni optimum.

Primjer... Riješite problem grafički linearno programiranje (alternativni optimum):

Pitanja za samokontrolu

1. Zapišite problem linearnog programiranja u općenitom obliku.

2. Zapišite problem linearnog programiranja u kanonske i standardne oblike.

3. Koje se transformacije mogu koristiti za prijelaz s općeg ili standardnog oblika problema linearnog programiranja na kanonski?

4. Dajte definiciju izvedivih i optimalnih rješenja problema linearnog programiranja.

5. Koje je rješenje „najbolje“ za problem minimiziranja funkcije, ako ?

6. Koje je rješenje „najbolje“ za problem maksimiziranja funkcije, ako ?

7. Zapišite standardni oblik matematičkog modela problema linearnog programiranja s dvije varijable.

8. Kako konstruirati poluravninu zadanu linearnom nejednakošću u dvije varijable ?

9. Što se naziva rješenjem sustava linearnih nejednadžbi u dvije varijable? Konstruirajte na ravnini područje mogućih rješenja takvog sustava linearnih nejednakosti, koje:

1) ima jedinstveno rješenje;

2) ima beskonačan broj rješenja;

3) nema jedinstveno rješenje.

10. Zabilježite za linearna funkcija vektorski gradijent, imenujte vrstu linija. Kako su linije gradijenta i razine postavljene jedna prema drugoj?

11. Formulirajte algoritam za grafičku metodu za rješavanje standardnog LPP-a s dvije varijable.

12. Kako pronaći koordinate i vrijednosti rješenja?

13. Nacrtajte područje izvedivih rješenja, linije gradijenta i razine za probleme linearnog programiranja, u kojima:

1) se postiže u jednoj točki, i - na segmentu ODR;

2) se postiže na jednoj točki ODR -a, i.

14. Navedite geometrijsku ilustraciju LPP -a, ako je:

1) ima jedina optimalna rješenja za i;

2) ima mnogo optimalnih rješenja za.

Predavanje 2

grafička metoda pronalaženje optimalnog rješenja

1. Oblici linearnih matematičkih modela i njihova transformacija

2. Grafička metoda za rješavanje problema linearnog programiranja

3. Posebne situacije grafičkog rješenja ZJN -a

4. Grafičko rješenje ekonomskih problema linearnog programiranja

Oblici linearnih matematičkih modela i njihova transformacija

Matematički model problema linearnog programiranja (LPP) može se napisati u jednom od tri oblika.

V opći oblik matematičkog modela potrebno je pronaći maksimum ili minimum funkcije cilja; sustav ograničenja sadrži nejednakosti i jednadžbe; ne mogu sve varijable biti nenegativne.

V kanonski oblik matematički model je potreban za pronalaženje maksimuma ciljne funkcije; sustav ograničenja sastoji se samo od jednadžbi; sve varijable su negativne.

U standardnom obliku matematičkog modela potrebno je pronaći maksimum ili minimum funkcije; sva ograničenja su nejednakosti; sve varijable nisu negativne.

Rješenje sustava ograničenja koje zadovoljava uvjete nenegativnosti varijabli naziva se prihvatljiva odluka ZJN -a(prihvatljiv plan).

Skup izvedivih rješenja naziva se područje dopuštenih rješenja ZJN-a.

Zove se izvedivo rješenje pri kojem funkcija cilja doseže ekstremnu vrijednost optimalno rješenje za LPP.

Tri oblika pisanja LPP-a su ekvivalentna u smislu da se svaki od njih može svesti na drugačiji oblik pomoću matematičkih transformacija.

Potreba prijelaz s jednog oblika matematičkog modela na drugi odnosi se na metode rješavanja problema: na primjer, simpleks metoda, koja se široko koristi u linearnom programiranju, primjenjuje se na problem napisan u kanonskom obliku, a grafička metoda primjenjuje se na standardni oblik matematičkog modela.

Prijelaz na kanonski oblik pisanja ZLP -a.

Primjer.

Zapišimo zadatak u kanonski oblik uvođenjem dodatne (bilančne) varijable sa znakom "+" u lijevoj strani prve nejednakosti sustava ograničenja, te dodatne varijable sa znakom minus u lijevoj strani druge nejednakosti.

Ekonomsko značenje različitih dodatnih varijabli ne mora biti isto: ovisi o ekonomskom značenju ograničenja u koja su ove varijable uključene.

Dakle, u problemu uporabe sirovina oni pokazuju ostatak sirovina, a u problemu odabira optimalnih tehnologija - neiskorišteno vrijeme poduzeća za određenu tehnologiju; u problemu rezanja - oslobađanje praznina zadane duljine preko plana itd.

Definicija. Linearno programiranje (LP) - znanost o metodama istraživanja i pronalaženju ekstremnih (najvećih i najmanjih) vrijednosti linearne funkcije, čije nepoznanice podliježu linearnim ograničenjima.

Ova linearna funkcija se zove cilj, a pozivaju se ograničenja koja su matematički napisana u obliku jednadžbi ili nejednakosti sustav ograničenja.

Definicija. Zove se matematički izraz ciljne funkcije i njezinih ograničenja matematički model ekonomskog problema.

Općenito, matematički model problema linearnog programiranja (LP) zapisuje se kao

s ograničenjima:

gdje x j- nepoznato; a ij, b i, c j- zadane konstantne vrijednosti.

Sve ili neke jednadžbe sustava ograničenja mogu se napisati u obliku nejednakosti.

Matematički model u sažetijem zapisu ima oblik

s ograničenjima:

Definicija. Izvedivo rješenje (plan) problema linearnog programiranja je vektor = ( x 1 , x 2 ,..., x n), zadovoljavajući sustav ograničenja.

Skup izvedivih rješenja čini područje izvedivih rješenja (ODS).

Definicija. Izvodljivo rješenje pri kojem ciljna funkcija doseže svoju ekstremnu vrijednost naziva se optimalno rješenje problema linearnog programiranja i označava se s opt.

Osnovno izvedivo rješenje (NS 1 , NS 2 , ..., x r , 0, …, 0) je referentno rješenje, gdje r - rang sustava ograničenja.

Matematički model LP problema može biti kanonski i nekanonski.

7.Rješenje zadataka linearnog programiranja grafičkom metodom... Grafovi ograničenja funkcija. Linije razine.

Grafička metoda za rješavanje problema linearnog programiranja

Najjednostavnija i najintuitivnija metoda linearnog programiranja je grafička metoda. Koristi se za rješavanje LP zadataka s dvije varijable date u nekanonskom obliku i mnogim varijablama u kanonskom obliku, pod uvjetom da sadrže najviše dvije slobodne varijable.

S geometrijskog stajališta, u problemu linearnog programiranja, traži se takva kutna točka ili skup točaka iz izvedivog skupa rješenja na kojem se postiže najviša (najniža) linija razine, smještena dalje (bliže) od drugi u smjeru najbržeg rasta.

Da biste pronašli ekstremnu vrijednost ciljne funkcije u grafičkom rješenju LP problema, upotrijebite vektor L() na površini NS 1 OH 2 , koje označavamo . Ovaj vektor prikazuje smjer najbrže promjene funkcije cilja. Drugim riječima, vektor je normala linije razine L()

gdje e 1 i e 2 - jedinični vektori duž osi VOL 1 i VOL 2 respektivno; dakle = (∂L / ∂h 1 , ∂L / ∂h 2 ). Koordinate vektora su koeficijenti ciljne funkcije L (). Izgradnja linije razine potanko će se razmotriti pri rješavanju praktičnih problema.

Algoritam za rješavanje problema

1. Pronađite područje izvedivih rješenja za sustav ograničenja problema.

2. Izgradnja vektora .

3. Nacrtajte ravnu liniju L 0 , koji je okomit .

4. Pomaknite liniju razine u smjeru vektora za zadatke do maksimuma i u suprotnom smjeru , za zadatke na minimum.

Linija se pomiče sve dok ne dobije samo jednu zajedničku točku s područjem dopuštenih rješenja. Ova točka, koja određuje jedino rješenje LP problema, bit će točka ekstrema.

Ako se pokaže da je linija razine paralelna s jednom od stranica ODR -a, tada je ekstrem dosegnut u svim točkama odgovarajuće stranice, a problem LP -a imat će beskonačan broj rješenja. Kaže se da takav LP problem ima alternativni optimum, a njegovo rješenje se nalazi po formuli:

Gdje je 0 ≤ t≤ 1, 1 i 2 - optimalna rješenja na kutnim točkama ODR-a.

Problem LP -a može biti nerješiv ako se pokaže da su ograničenja koja ga definiraju kontradiktorna.

5. Pronađi koordinate ekstremne točke i vrijednost funkcije cilja u njoj.

Primjer 3. Odabir optimalne opcije puštanja proizvoda

Tvrtka proizvodi 2 vrste sladoleda: kremasti i čokoladni. Za proizvodnju sladoleda koriste se dva početna proizvoda: mlijeko i punila, čiji su troškovi po 1 kg sladoleda i dnevne zalihe navedeni u tablici.

Studija prodajnog tržišta pokazala je da dnevna potražnja za sladoledom premašuje potražnju za čokoladnim sladoledom, ali za najviše 100 kg.

Osim toga, utvrđeno je da potražnja za čokoladnim sladoledom ne prelazi 350 kg dnevno. Maloprodajna cijena 1 kg kremastog sladoleda 16 rubalja, čokolade - 14 rubalja.

Koliko sladoleda svake vrste tvrtka treba proizvesti kako bi maksimizirala prihod od prodaje proizvoda?

Riješenje. Označimo: x 1 - dnevni volumen proizvodnje sladoleda, kg; x 2 - dnevna proizvodnja čokoladnog sladoleda, kg.

Sastavimo matematički model zadacima.

Poznate su cijene sladoleda: 16 rubalja, odnosno 14 rubalja, pa će funkcija cilja izgledati ovako:

Ograničit ćemo mlijeko za sladoled. Njegova potrošnja za kremasti sladoled - 0,8 kg, za čokoladu - 0,5 kg. Zaliha mlijeka 400kg. Stoga će prva nejednakost izgledati ovako:

0,8x 1 + 0,5x 2 ≤400 - prva nejednakost je ograničenje. Ostatak nejednakosti sastavljen je na sličan način.

Rezultat je sustav nejednakosti. to je područje rješenja svake nejednakosti. To se može učiniti zamjenom koordinata točke O (0:0) u svaku od nejednadžbi. Kao rezultat toga, dobivamo:

Lik OABDEF - područje dopuštenih rješenja. Gradimo vektor (16; 14). Linija razine L 0 je zadan jednadžbom 16x 1 + 14x 2 = Const. Odaberemo bilo koji broj, na primjer broj 0, zatim 16x 1 + 14x 2 = 0. Na slici je za liniju L 0 odabran određeni pozitivan broj koji nije jednak nuli. Sve linije razine su paralelne jedna s drugom. Normalni vektor linije razine.

Pomaknite liniju razine u smjeru vektora. Izlazna točka L 0 iz područja izvedivih rješenja je točka D, njegove koordinate su određene kao sjecište ravnih linija danih jednadžbama:

Rješavajući sustav, dobivamo koordinate točke D(312.5; 300), u kojem će postojati optimalno rješenje, t.j.

Tako bi tvrtka trebala proizvoditi 312,5 kg sladoleda i 300 kg čokoladnog sladoleda dnevno, dok će prihod od prodaje iznositi 9 200 rubalja.

8.Svođenje proizvoljnog problema linearnog programiranja na glavni problem. Pretvaranje ograničenja nejednakosti u odgovarajuće jednadžbe.

9.Simplex metoda... Opis i algoritam metode, njezina primjenjivost.

Za rješavanje problema simpleks metodom potrebno je:

1. Navedite način pronalaženja optimalnog rješenja podrške

2. Navedite metodu prijelaza s jednog potpornog rješenja na drugo, pri čemu će vrijednost ciljne funkcije biti bliža optimalnoj, tj. naznačiti način poboljšanja referentnog rješenja

3. Postavite kriterije koji vam omogućuju pravodobno zaustavljanje traženja rješenja podrške za optimalno rješenje ili donošenje zaključka o nepostojanju optimalnog rješenja.

Algoritam simpleks metode za rješavanje problema linearnog programiranja

1. Dovedite problem u kanonski oblik

2. Pronađite početno rješenje za podršku s "jedinicom osnove" (ako nema rješenja za podršku, onda problem nema rješenja, zbog nekompatibilnosti sustava ograničenja)

3. Izračunajte procjene vektorskih proširenja u osnovi rješenja za podršku i popunite tablicu simpleks metode

4. Ako je zadovoljen kriterij jedinstvenosti optimalnog rješenja, tada rješenje problema završava

5. Ako je zadovoljen uvjet za postojanje skupa optimalnih rješenja, tada se jednostavnim nabrajanjem pronađu sva optimalna rješenja

10. Problem transporta. Definicija, vrste, metode pronalaska početnog rješenja transportnog problema.

Problem transporta jedan je od najčešćih problema linearnog programiranja. Njegov je cilj razviti najracionalnije načine i sredstva prijevoza robe, eliminirajući pretjerano velike udaljenosti, nadolazeći, ponovljeni prijevoz.

1. Pronalaženje početnog rješenja podrške;

2. Provjera optimalnosti ovog rješenja;

3. Prijelaz s jednog rješenja podrške na drugo.

3.1. Opći problem linearnog programiranja

Linearno programiranje- ovo je najrazvijeniji odjeljak matematičko programiranje, uz pomoć kojih se provodi analiza i rješavanje ekstremnih problema s linearnim vezama i ograničenjima.

Linearno programiranje uključuje niz heurističkih (približnih) rješenja koja omogućuju, pod zadanim uvjetima, sve moguće opcije rješenja proizvodnih problema odabrati najbolje, optimalno. Ove metode uključuju sljedeće - grafičku, simpleksnu, potencijalnu metodu (modificirana metoda distribucije - MODI), Hitchkovu, Kreku, Vogelovu metodu aproksimacije i druge.

Neke od ovih metoda ujedinjene su zajedničkim imenom - metoda distribucije ili transporta.

Rodno mjesto linearnog programiranja je Rusija. Prvi radovi o linearnom programiranju budućeg akademika L.V. Kantorovich objavljeni su 1939. 1975. dobio je Nobelovu nagradu za ekonomiju za razvoj metoda linearnog programiranja. Budući da je većina djela akademika L.V. Kantorovich je posvećen rješavanju transportnih problema, može se smatrati da navedena Nobelova nagrada također odaje počast zaslugama ruske transportne znanosti.

U cestovnom prometu metode linearnog programiranja koriste se od 1960-ih za rješavanje velikog broja najvažnijih proizvodnih problema, a to su: smanjenje udaljenosti prijevoza tereta; izrada optimalne sheme transporta; izbor najkraćih ruta kretanja; poslovi prijevoza različitog, ali zamjenjivog tereta; smjena-dnevno planiranje; planiranje prijevoza sitnoserijskog tereta; distribucija autobusa po rutama i drugo.

Karakteristike modela linearnog programiranja su sljedeće:

Objektivna funkcija i ograničenja izraženi su linearnim ovisnostima (jednakosti ili nejednakosti);

Broj ovisnosti uvijek je manji od broja nepoznanica (uvjet neizvjesnosti);

Nenegativnost traženih varijabli. Opći oblik pisanja linearnog programskog modela u skraćenom obliku je sljedeći:

Pronaći NS ij ≥ 0 (j = 1, 2 ... n) pod ograničenjima sljedećeg tipa:

Ta ograničenja minimiziraju (ili maksimiziraju) ciljnu funkciju

Standardni oblik pisanja linearnog programskog modela je sustav linearne jednadžbe snimljeno u kanonski obliku, odnosno u obliku linearnih jednakosti, u negativnim brojevima:

a 11 x 1 + a 12 x 2 + ... + a 1 n x n = b 1;

a 21 x 1 + a 22 x 2 + ... + a 2 n x n = b 2 ; (3.1)

……………………………..

a m x 1 + a m 2 x 2 +… + a mn x n = b m ..

Ako je model napisan u obliku nejednadžbi u nenegativnim brojevima, odnosno ima oblik

a 11 x 1 + a 12 x 2 +… + a 1 n x n ≤ b 1;

a 21 x 1 + a 22 x 2 + ... + a 2 n x n ≤ b 2 ; (3.2)

……………………………..

a m x 1 + a m 2 x 2 +… + a mn x n ≤ b m, ..

tada se ovaj zapis svodi na kanonski obliku (3.1) uvođenjem dodatnih varijabli x n +1> 0 (i=1,2…m) lijevo od nejednakosti (ili poništavanje broja varijabli, ako je znak nejednakosti usmjeren u drugom smjeru). Dodatne varijable čine osnovu.

Standardni oblik rješavanja problema linearnog programiranja je pronaći rješenja sustava linearnih jednadžbi u negativnim brojevima koji minimiziraju ciljnu funkciju. U tom slučaju funkcija cilja ima oblik

L = s 1 x 1 + s 2 x 2 ... s n x n → min, (3.3)

gdje s 1, s 2 ... s n- koeficijenti funkcije cilja L s varijablama NS j.

Dodatne varijable ulaze u funkciju cilja s nula koeficijenata.

U slučaju maksimiziranja ciljne funkcije L treba preokrenuti predznake varijabli ciljne funkcije i opet dolazimo do problema minimiziranja, t.j. jedan zadatak zamjenom se svodi na drugi L na - L ili max L= min (- L).

Osnovno rješenje sustava linearnih jednadžbi (3.1) je rješenje u kojem se nebazičnim varijablama daju nulte vrijednosti.

Osnovno rješenje naziva se dopuštenim u kojemu su varijable uključene u bazu nenegativne.

Optimalno rješenje je izvedivo rješenje koje maksimizira (ili minimizira) ciljnu funkciju (3.3).

Svaki problem linearnog programiranja odgovara drugom, koji se naziva problem dualnog linearnog programiranja. Izvorni problem s obzirom na dual naziva se izravnim. Izravni i dvostruki problemi tvore par, koji se u linearnom programiranju naziva dvojni par. Izravni i dualni par tvore asimetrični par kada je izravni problem napisan u kanonskom obliku, i simetričan par kada su uvjeti problema zapisani nejednadžbama.

Pravila za sastavljanje matematičkog modela dvojnog problema temelje se na pravilima matričnog računa.

Koncept dualnosti naširoko se koristi u analizi problema linearnog programiranja. Svojstvo dualnosti detaljno se razmatra u svakom konkretnom slučaju.

3.2. Grafičko-analitička metoda

Grafoanalitička metoda jedna je od najjednostavnijih metoda linearnog programiranja. On jasno otkriva bit linearnog programiranja, njegovu geometrijsku interpretaciju. Nedostatak mu je što vam omogućuje rješavanje problema s 2 ili 3 nepoznanice, odnosno primjenjiv je za uski raspon problema. Metoda se temelji na pravilima analitičke geometrije.

Rješavanje problema s dvije varijable x 1 i x 2, koji u smislu problema ne bi trebao biti negativan, izvodi se u kartezijanskom koordinatnom sustavu. Jednadžbe x 1= 0 i x 2= 0 su osi koordinatnog sustava prvog kvadranta

Razmotrimo metodu rješenja na konkretnom primjeru.

Primjer 3.1. U skladištu se nalazi 300 tona pjenastih betonskih proizvoda i 200 tona čelika. Automobilska tvrtka mora isporučiti ove proizvode u objekt u izgradnji. Automobilska tvrtka ima kamione KamAZ - 5320 i

ZIL-4314. Za jedno putovanje KamAZ-5320 može isporučiti 6 tona pjenastog betona i 2 tone čelika, a dobit od vožnje bit će 4 tisuće rubalja. ZIL-4314 isporučuje 2 tone pjenastog betona i 4 tone čelika u jednom putovanju, dobit od putovanja je 6 tisuća rubalja. Prijevoz je potrebno organizirati na način da se automobilskoj tvrtki osigura najveći profit.

Izgradimo matematički model problema. Označimo s x 1 potreban broj vozača KamAZ-5320 i kroz NS 2 potreban broj jahača ZIL-4314.

Totalni prijevoz u t proizvoda od pjenastog betona je 6 x 1 + 2x 2, a od čelika 2 x 1 + 4x 2... Ograničenja prijevoza ovisno o broju dostupnih artikala su 6 x 1 + 2x 2 ≤ 300t za pjenasti beton i 2 x 1 + 4x 2 ≤ 200t za čelik.

Ukupna dobit u tisućama rubalja izražava se kao 4 NS 1 + 6NS 2, koji je potrebno maksimizirati i koji je kriterij optimalnosti u razmatranom problemu. Dakle, matematički model problema izgleda ovako. Potrebno je maksimizirati ciljnu funkciju

L = 4x 1 + 6x 2 → max pod uvjetima: 6 x 1 + 2x 2 ≤ 300; 2x 1 + 4x 2 ≤ 200; x 1 ≥ 0;x 2 ≥ 0.

Razmotrite jednadžbu 6 x 1 + 2x 2 = 300. Za izgradnju ravne crte opisane ovom jednadžbom nalazimo dvije točke koje leže na ovoj ravnoj liniji. Na x 1= 0 iz jednadžbe ravne linije nalazimo 2 x 2 = 300, odakle je x 2 = 150. Stoga točka A s koordinatama (0,150) leži na željenoj pravoj liniji. Na x 2= 0 imamo 6 x 1= 300, odakle je x 1 = 50 i točka D s koordinatama (50,0) također je na traženoj liniji. Povucite ravnu liniju kroz ove dvije točke OGLAS(slika 3.1).

Linearna nejednakost 6 x 1 + 2x 2 ≤ 300 je poluravnina koja se nalazi na jednoj od strana konstruirane ravne linije 6 x 1 + 2x 2 = 300. Da bismo saznali na kojoj se strani ove ravne linije nalaze točke potrebne poluravnine, zamjenjujemo 6 x 1 + 2x 2 ≤ 300 koordinata bilo koje točke koja ne leži na graničnoj crti. Na primjer, ishodište je 0- (0,0). Za njega je nejednakost 6 ∙ 0 + 2 ∙ 0 = 0< 300. Это значит, что начало координат лежит в области допустимых значений, которая находится слева от прямой OGLAS a na si. 3.1 je zasjenjena.

Jednadžba 2 x 1 + 4x 2= 200 gradit ćemo na dvije točke. Na x 1 = 0 4x 2 = 200, odakle x 2 = 50. Zatim točka E ima koordinate (0,50) i pripada traženoj liniji. Na x 2= 0, 2x 2 = 200, točka s nalazi se na zadanoj liniji s koordinatama (100,0). Zamjenom koordinata točke u nejednakost s(0,0), dobivamo 2 ∙ 0 + 4 ∙ 0 = 0< 200. Значит, начало координат находится в области допустимых значений от прямой 2x 1+ 4x 2= 200.

Sustav ograničenja zadataka zahtijeva da planovi ( x 1; x 2) zadovoljavaju sve četiri nejednakosti, tj. dopušteni projekti su točke ( x 1; x 2) moraju biti istovremeno u sve četiri poluravnine. Taj zahtjev zadovoljavaju samo točke koje se nalaze unutar i na granici poligona. OEKD, što je poligon izvedivih rješenja.

Vrhovi poligona izvedivih rješenja su točke O, E, K, D, segmenti linija OE, EK, KD, OD- njegova rebra. Bilo koja točka poligona OEKD je plan problema koji zadovoljava sve njegove uvjete. Vrhovi poligona nastaju presjekom dviju ravnih linija i odgovaraju osnovnim planovima problema, među kojima je najbolji (optimalan) plan. Dakle, bit će onoliko temeljnih planova koliko ima vrhova poligona izvedivih rješenja.

Za ciljnu funkciju također se može dobiti jasan geometrijski prikaz. L = 4x 1 + 6x 2... Popravimo, na primjer, vrijednost funkcije cilja L= 120.jednadžba 4 x 1 + 6x 2 = 120 definira liniju kroz točku V s koordinatama (x 1 = 0; x 2 = 20) i točkom L sa koordinatama (( NS 1 = 30; NS 2 = 0). Odjeljak BL leži unutar poligona OEKD... Stoga je za sve planove (točke) ovog segmenta vrijednost funkcije cilja jednaka i jednaka 120. Dodjelom drugih vrijednosti funkciji cilja dobivamo paralelne crte, koje se nazivaju ravnine linije ciljna funkcija.

Krećući se ravno L paralelno sa samim sobom u jednom smjeru, dobivamo povećanje funkcije cilja, a u suprotnom smjeru - njeno smanjenje. U ovom primjeru, kretanje ravne linije BL udesno određuje povećanje ciljne funkcije koju maksimiziramo. Činimo to sve dok je ravno BL imat će barem jednu zajedničku točku s poligonom izvedivih rješenja OEKD... sl. 3.1 slijedi da će posljednja točka koju prelazi ravna linija razine ciljne funkcije biti točka DO... To znači da je točka DO određuje optimalni plan zadatka.

Uzlazni smjer okomit na liniju razine naziva se smjeru najvećeg porasta ciljnu funkciju i određuje njezin maksimalni rast. Ovaj smjer se može postaviti bez crtanja linija razine. Za to je potrebno na osi x 1 i x 2 odgoditi segmente jednake koeficijentima ciljne funkcije i iz njih, kao koordinate, konstruirati vektor najvećeg povećanja ciljne funkcije. U matematici se to zove gradijent i označiti gradom. Gradijent za funkciju L = 4x 1 + 6x 2 bit će vektor n| 4; 6 | ... Radi praktičnosti njegove izgradnje povećat ćemo koordinate, na primjer, 10 puta, t.j. n | 40; 60 | ... Konstruirajte gradijent ciljne funkcije L, za koje povezujemo točku s koordinatama (40; 60) s ishodištem. Linije razine ciljne funkcije iscrtavaju se okomito na smjer gradijenta.

Dakle, na ovaj ili onaj način je utvrđeno da je točka DO određuje optimalni plan problema, čije vrijednosti varijabli odgovaraju koordinatama zadane točke. Za uspostavu koordinata potrebno je riješiti sustav jednadžbi ravnih linija koje tvore ovaj vrh:

6x 1 + 2x 2= 300;

2x 1 + 4x 2= 200.

Izjednačimo koeficijente na x 1 množenjem druge jednadžbe s 3 i oduzmimo prvu od druge jednadžbe. Dobivamo 10 x 2= 300,x 2 = 30. Zamjenom vrijednosti x 2 = 30 u bilo kojoj od jednadžbi, na primjer, u prvoj, određujemo vrijednost NS 1:

6x 1+ 2NS · 30 = 300,

odakle 6 x 1 = 300 - 60 = 240, dakle x 1 = 40.

Dakle, kako bi ostvario najveći profit, automobilsko poduzeće mora dovršiti 40 putovanja na KamAZ-5320 i 30 putovanja na ZIL-4314. Maksimalna dobit u ovom slučaju bit će

L = 4x 1 + 6x 2= 4 40 + 6 30 = 340 tisuća rubalja.

Na temelju razmatranog primjera i geometrijske interpretacije problema optimizacije s dvije varijable mogu se izvući sljedeći zaključci:

1) u dvodimenzionalnom prostoru područje izvedivih rješenja je poligon;

2) svaka strana poligona odgovara vrijednosti jedne varijable jednake nuli;

3) svaki vrh poligona izvedivih rješenja odgovara vrijednostima dviju varijabli jednakih nuli;

4) ravna vrijednost odgovara svakoj vrijednosti ciljne funkcije;

5) optimalnom rješenju zadatka odgovara vrh poligona, u kojem ciljna funkcija poprima optimalnu vrijednost, a koordinate ovog vrha su optimalne varijable.

Općenito, optimizacijski problemi imaju slično geometrijsko tumačenje. Skup planova problema bit će poliedar, čiji vrhovi odgovaraju referentnim planovima. Pri rješavanju problema vrši se prijelaz s jednog vrha poliedra u drugi s velikom vrijednošću funkcije cilja sve dok se ne dobije njegova optimalna vrijednost. Napominjemo da učinkovitost optimizacijskih metoda leži upravo u činjenici da se pretraga vrhova (iteracija) provodi samo u smjeru najvećeg povećanja ciljne funkcije. Stoga se ne razmatraju svi vrhovi, kojih ima ogroman broj, već samo oni koji su bliži ekstremu.

Prilikom definiranja klase optimizacijskih problema i odabira metode za njezino rješavanje potrebno je znati je li skup izvedivih rješenja konveksan ili nekonveksan, linearna ili nelinearna ciljna funkcija.

Po definiciji skup se zove konveksan ako za bilo koje dvije točke cijeli segment koji povezuje te točke pripada ovom skupu. Primjeri konveksnih skupova su, na primjer, segment (slika 3.2, a), ravnina u obliku kružnice, kocke, paralelepipeda, kao i poligoni koji se u cijelosti nalaze na jednoj strani svake od njegovih stranica , itd.

Na sl. 3.2b prikazuje nekonveksne skupove. U nekonveksnim skupovima mogu se naznačiti najmanje dvije točke segmenta AB koje ne pripadaju skupu koji se razmatra.

3.3. Simplex metoda

Simplex metoda Uobičajena je metoda za rješavanje problema linearnog programiranja. Metoda je dobila ime po riječi "simplex", koja označava najjednostavniji konveksni poligon, čiji je broj vrhova uvijek jedan veći od dimenzije prostora. Simpleksnu metodu razvio je u SAD-u matematičar J. Danzig kasnih 1940-ih.

Simplex metoda uključuje dobivanje nenegativnog osnovnog rješenja sustava kanonskih linearnih jednadžbi tipa (3.1), naknadno minimiziranje (maksimiziranje) ciljne funkcije (3.3) i pronalaženje na ovaj način optimalnih vrijednosti traženih varijabli x 1, x 2 ... x n.

Ideja simpleks metode je da se u procesu računanja sekvencijalno prelazi s prvog osnovnog rješenja na drugo, treće itd. kroz tzv simplex transformacije. Pretvorbe se izvode u obliku simpleks tablica, što uvelike pojednostavljuje i ubrzava izračune.

Za dobivanje nenegativnih osnovnih rješenja sustava linearnih jednadžbi potrebno je provesti postupak eliminacije nepoznanica na način da slobodni članovi jednadžbe ostanu nenegativni u svim fazama procesa. U tom slučaju treba se voditi sljedećim pravilom: kao nova bazna varijabla uzima se svaka slobodna varijabla za koju postoji barem jedan pozitivan koeficijent; iz baze se izvodi varijabla koja odgovara najmanjem omjeru slobodnih članova jednadžbi prema odgovarajućim pozitivnim koeficijentima jednadžbi za varijablu uvedenu u bazu. Takve transformacije nazivaju se simpleks pretvarači.

To je vrlo važno jer kako bi se pronašlo određeno negativno rješenje koje odgovara najvećoj mogućoj vrijednosti bilo koje slobodne varijable pri nultim vrijednostima drugih slobodnih varijabli, umjesto da se odredi raspon navedene varijable i zamijeni njezin maksimum moguće vrijednosti u opće rješenje, dovoljno je uzeti ovu varijablu kao osnovnu i podvrgnuti sustav simpleks transformaciji, prelazeći na novu osnovu, što uvelike pojednostavljuje izračune.

Izračuni se prikladno izvode pomoću jednostavnih tablica. Prijelaz iz jedne tablice u drugu odgovara jednoj iteraciji, tj. Prijelazu iz jedne baze u drugu, dok se vrijednost funkcije cilja smanjuje. Za određeni broj ponavljanja ide se do osnove za koju se dobiva optimalna (minimalna ili maksimalna) vrijednost funkcije cilja. Razmotrimo općenito simpleks metodu.

Opći problem linearnog programiranja je minimizirati (maksimizirati) ciljnu funkciju, čije su varijable međusobno povezane sustavom linearnih jednadžbi, podliježu uvjetu nenegativnosti.

Neka je potrebno minimizirati linearni oblik

L = s 1 x 1 + s 2 x 2 + ... s n x n.

Pod uvjetima (radi jasnoće, koeficijenti nula i jedan u jednadžbama su sačuvani):

1x 1+ 0x 2 + ... 0x m + a 1m + 1x m + 1 ... + a 1n x n = b 1;

0x 1 + 1x 2 +… 0x m + a 2m + 1x m + 1 ... + a 2n x n = b 2;

……………………………………………

0x 1+ 0x 2 + ... 1x m + a mm + 1x m +1 ... + a mn x n = b m.

Ovaj sustav jednadžbi već ima gotovu osnovu, budući da svaka jednadžba ograničenja sadrži nepoznatu s koeficijentom jednakim koji nedostaje u drugim jednadžbama, odnosno iz koeficijenata varijabli NS 1 , NS 2 …, x m možete sastaviti matricu identiteta.

Riješimo jednadžbe za osnovne varijable:

x 1 = b 1 - (a 1m + 1 · x m + 1 ... + a 1n x n);

x 2 = b 2 - (a 2m + 1 x m + 1 ... + a 2n x n);

………………………………

x m = b m - (a mm + 1x m + 1 ... + a mn x n),

i izražavamo ciljnu funkciju u terminima slobodnih varijabli, zamjenjujući njihove izraze u terminima slobodnih varijabli umjesto osnovnih varijabli:

L = c 1 b 1 + c 2 b 2 + cmbm - (c 1 a 1m + c 2 a 2m + 1 +… + cma mn + 1) x m + 1 -… - (c 1 a 1n + c 2 a 2n +… + cma mn) xn… + cnx n ..

Varijable x 1, x 2 ..., x m, uz pomoć kojih se nalazi prvi osnovni plan, osnovni su, a ostali x m +1, x m +2, ... x n - besplatno. Uvijek treba postojati onoliko osnovnih varijabli koliko ima jednadžbi u sustavu. Na temelju uvjeta nenegativnosti, najmanja vrijednost slobodnih varijabli je nula. Dobiveno osnovno rješenje sustava jednadžbi njegovo je početno dopušteno rješenje, t.j. x 1 = b 1, x 2 = b 2, ... x m = b m, x m +1 = 0,…, X n = 0.

Ovo rješenje odgovara vrijednosti funkcije cilja

L = c 1 b 1 + c 2 b 2 + ... c m b m.

Inicijalno rješenje testira se na optimalnost. Ako nije optimalno, tada se uvođenjem slobodnih varijabli u bazu pronalaze sljedeća izvediva rješenja s manjom vrijednošću ciljne funkcije. Da biste to učinili, definirajte slobodnu varijablu koja se mora unijeti u bazu, kao i varijablu koja mora biti izvedena iz baze. Zatim se prelazi iz prethodnog sustava u sljedeći ekvivalentni sustav. To se radi pomoću simpleksnih tablica. Rješavanje zadatka nastavlja se sve dok se ne dobije optimalna vrijednost ciljne funkcije.

Simpleksne tablice sastavljene su na sljedeći način (vidi tablicu 3.1). Sve se varijable nalaze na vrhu tablice NS 1 , NS 2 …, x n i koeficijenti c j, s kojim su odgovarajuće varijable uključene u ciljnu funkciju. Prva kolona c i sastoji se od koeficijenta funkcije cilja za varijable uključene u bazu. Nakon toga slijedi stupac osnovnih varijabli i slobodnih pojmova jednadžbi. Elementi preostalih stupaca tablice predstavljaju koeficijente varijabli s kojima su potonje uključene u sustav jednadžbi. Dakle, svaki red tablice odgovara jednadžbi sustava, riješenoj s obzirom na osnovnu varijablu. U tablici je prikazana i varijanta plana koja odgovara funkciji cilja za zadanu osnovu.

Donji red tablice naziva se indeks... Svaki njegov element (procjena) ∆ j definirati

∆j = z j - c j,

gdje c j- koeficijenti za odgovarajuće varijable u funkciji cilja; z j - zbroj umnožaka koeficijenata ciljne funkcije za osnovne varijable odgovarajućim varijablama - elementima j-Ti stupac tablice.

stol 3.1

Simplex tablica s početnim vrijednostima

U praksi, ograničenja u problemu linearnog programiranja često se ne određuju jednadžbama, već nejednačinama.

Pokažimo kako možemo preći s problema s ograničenjima nejednakosti na glavni problem linearnog programiranja.

Neka postoji problem linearnog programiranja s varijablama, u kojem su ograničenja nametnuta varijablama u obliku linearnih nejednakosti. U nekima od njih znak nejednakosti može biti na drugima (druga vrsta se svodi na prvu jednostavnim preokretom predznaka oba dijela). Stoga sva ograničenja nejednakosti postavljamo u standardni oblik:

Potrebno je pronaći skup nenegativnih vrijednosti koje bi zadovoljile nejednakosti (4.1), a štoviše, minimizirale linearnu funkciju:

Lako je preći s ovako postavljenog zadatka na glavni zadatak linearnog programiranja. Doista, uvedemo oznaku:

gdje su neke nove varijable koje ćemo nazvati "dodatnim". Prema uvjetima (4.1), te dodatne varijable, kao i trebale bi biti negativne.

Dakle, suočeni smo s problemom linearnog programiranja u sljedećoj formulaciji: pronaći takve nenegativne vrijednosti varijabli tako da zadovoljavaju sustav jednadžbi (4.3) i istovremeno minimizirati linearnu funkciju ovih varijabli:

Kao što vidite, pred nama je u svom čistom obliku glavni zadatak linearnog programiranja (LPP). Jednadžbe (4.3) date su u već dopuštenom obliku za osnovne varijable izražene slobodnim varijablama. Ukupan broj varijabli je jednak, od kojih su "početne" i "dodatne". Funkcija L izražena je samo u smislu "početnih" varijabli (koeficijenti "dodatnih" varijabli u njoj jednaki su nuli).

Stoga smo problem linearnog programiranja s ograničenjima nejednakosti sveli na glavni problem linearnog programiranja, ali s većim brojem varijabli nego što je to bilo izvorno u problemu.

Primjer 1 Postoji problem linearnog programiranja s ograničenjima nejednakosti: pronađite nenegativne vrijednosti varijabli koje zadovoljavaju uvjete

i minimiziranje linearne funkcije

Ovaj zadatak je potrebno dovesti u formu OZLP-a.

Riješenje. Nejednakosti (4.4) svodimo u standardni oblik;

Uvodimo dodatne varijable:

Zadatak se svodi na pronalaženje negativnih vrijednosti varijabli

zadovoljavanje jednadžbi (4.6) i minimiziranje linearne funkcije (4.5).

Pokazali smo kako možemo prijeći od problema linearnog programiranja s ograničenjima nejednakosti do problema s ograničenjima jednakosti (LPPP). Obrnuti prijelaz je uvijek moguć – od LPP-a do problema s ograničenjima nejednakosti. Ako smo u prvom slučaju povećali broj varijabli, onda ćemo ga u drugom slučaju smanjiti, eliminirajući osnovne varijable i ostavljajući samo slobodne.

Primjer 2. Postoji problem linearnog programiranja s ograničenjima jednakosti (LPPP):

a funkcija koju treba minimizirati

Potrebno ga je zapisati kao problem linearnog programiranja s ograničenjima nejednakosti.

Riješenje. Budući da ćemo tada neke dvije varijable odabrati kao slobodne. Imajte na umu da se varijable ne mogu odabrati kao slobodne varijable, budući da su povezane prvom od jednadžbi (4-7): vrijednost jedne od njih potpuno je određena vrijednošću druge, a slobodne varijable moraju biti neovisne

Iz istog razloga je nemoguće odabrati varijable kao slobodne (povezane su drugom jednadžbom). Odaberimo kao slobodne varijable i kroz njih izrazimo sve ostale:

Budući da se uvjeti (4 9) mogu zamijeniti nejednačinama:

Prijeđimo u izrazu linearne funkcije L na slobodne varijable Zamjenjujući u L umjesto njihovih izraza (4.9). dobivamo.

Osnovni koncepti modeliranja

U procesu ljudske aktivnosti razvijaju se ideje o određenim svojstvima stvarnih objekata i njihovom međudjelovanju. Ove prikaze formira osoba u obliku opisa objekata za koje se koristi opisni jezik. To može biti verbalni opis (verbalni modeli), crtež, crtež, graf, izgled itd. Sve navedeno sažeto je u jedan koncept model, a proces izgradnje modela je modeliranje.

Modeliranje Univerzalni je način proučavanja procesa i pojava stvarnog svijeta. Modeliranje je od posebne važnosti u proučavanju objekata nedostupnih za izravno promatranje i istraživanje. To uključuje, posebice, društveno-ekonomske pojave i procese.

Proučavanje bilo kojeg objekta, bilo kojeg oblika kretanja otkriva ne samo njegove kvalitativne, već i kvantitativne zakone koje proučava matematika. Gore navedeno u potpunosti se odnosi na gospodarstvo.

Ekonomija- Ovo je sustav društvene proizvodnje koji zapravo provodi proizvodnju, distribuciju, razmjenu i potrošnju materijalnih dobara potrebnih društvu.

Odnosno, ekonomsko-matematički model Je li ekonomska apstrakcija izražena formalnim matematičkim izrazima čija je logička struktura određena objektivnim svojstvima predmeta opisa i subjektivnim ciljnim čimbenikom istraživanja za koje se ovaj opis poduzima.

Ekonomski i matematički problemi u poljoprivredi rješavaju se matematičkim metodama. Među njima su najrazvijenije metode linearnog programiranja (LP). Takve se metode koriste za rješavanje ekonomskih i matematičkih problema u kojima su kvantitativni odnosi izraženi linearno, t.j. svi su uvjeti izraženi kao sustav linearnih jednadžbi i nejednakosti, a kriterij optimalnosti izražen je kao linearna funkcija koja teži minimumu ili maksimumu (ekstremu).

Problem linearnog programiranja sastoji se od objektivne funkcije, sustava ograničenja i uvjeta nenegativnosti za varijable.

Neka je dana funkcija n varijable Potrebno je pronaći najveću ili najmanju vrijednost ove funkcije, pod uvjetom da je argument

Ovako postavljeni optimizacijski problem naziva se problemom matematičkog programiranja. Mnogo NS naziva se skup izvedivih odluka, a funkcija je ciljna funkcija ili ciljna funkcija. Izvedivo rješenje pri kojem funkcija zauzima najveću (ili najmanju) vrijednost naziva se optimalno rješenje problema.

Ako je ciljna funkcija linearna i skup NS je specificiran pomoću sustava linearnih jednadžbi i nejednadžbi, tada se problem naziva problemom linearnog programiranja (LPP). Dakle, opći iskaz problema linearnog programiranja je sljedeći:

pronaći ekstrem funkcije

s ograničenjima

pod nenegativnim uvjetima

Uvedimo zapis:

Dionice i-Vrsta izvora;

troškovi i-Tu vrstu resursa za proizvodnju j-Tu vrstu proizvoda;

jedinični profit j-Tu vrstu proizvoda.

U kompaktnom zapisu, problem linearnog programiranja ima oblik:

Kompaktni zapis pokazuje da opći model problema linearnog programiranja uključuje pet glavnih elemenata:

Varijable čija se vrijednost nalazi u procesu rješavanja problema;

Tehnički i ekonomski koeficijenti za varijable u ograničenjima;

Volumen desne strane nejednadžbi, koje se nazivaju konstantama problema;

Koeficijenti varijabli u funkciji cilja, koje se nazivaju varijabilne procjene;

Varijabilni indeks;

Indeks ograničenja.

Ciljna funkcija(funkcija cilja) je matematički izraz za koji želite pronaći krajnost, odnosno maksimalnu ili minimalnu vrijednost.

Varijable x j označavaju takve vrste i metode djelovanja čija je veličina nepoznata i mora se utvrditi tijekom rješavanja problema. Obično, u poljoprivrednim problemima, varijable označavaju potrebne veličine grana gospodarstva, vrste hrane za prehranu, marke traktora i poljoprivrednih strojeva itd. Prema posebnim uvjetima, isti usjev ili vrsta stoke mogu se izraziti s nekoliko varijabli. Na primjer, žitarice i krmna zrna; kukuruz za zrno, silaža, zelena krma; višegodišnje trave za sijeno, sjenažu, zelenu krmu, travnatu sačmu i sjeme itd.

Varijable se mogu proizvoljno mijenjati u uvjetima problema koji se razmatra. Promjenjivo , čiji se koeficijenti tvore jedinični stupac nazivaju se Osnovni, temeljni. Formiraju se osnovne varijable jedinična osnova sustava. Varijable koje nisu uključene u jedinicu osnove zovu se besplatno.

Ukupan broj varijabli uključenih u zadatak određen je prirodom zadatka, specifičnim uvjetima proizvodnje, sposobnošću prikupljanja informacija itd.

Varijable se mogu izraziti u raznim jedinicama: ha, q, kg, kom., Glave itd. Po svojoj prirodi varijable se dijele na glavne, dodatne i pomoćne. Glavne varijable uključuju tražene aktivnosti: industrije, vrste hrane za životinje, marke automobila. Dodatne varijable nazivaju se varijable koje nastaju u procesu transformacije nejednadžbi u jednadžbe. Mogu značiti nedovoljno iskorišten dio resursa, višak preko desna strana nejednakost (ako se radi o nejednakosti tipa "nema više"). Pomoćne varijable uključene su u zadatak kako bi se utvrdile procijenjene vrijednosti stečenih proizvodnih resursa, procijenjene vrijednosti pokazatelja ekonomske učinkovitosti proizvodnje.

Dodatne i pomoćne varijable uvijek imaju jedinične koeficijente (+1 ili –1).

Tehnički i ekonomski koeficijenti (a ij) s varijablama u sustavu ograničenja izražene su stope proizvodnih resursa ili stopa outputa po mjernoj jedinici varijable.

U oba slučaja potrebno je da tehnički i ekonomski koeficijenti točno odgovaraju planskom razdoblju za koje se problem rješava. Primjerice, ako se riješi problem za ekonomsko-matematičku analizu proizvodnje za proteklo razdoblje, tada će se koeficijenti izračunati prema prijavljenim podacima. Ako se odluči za budućnost, tada bi se za ovu perspektivu trebali izračunati koeficijenti.

Stope potrošnje resursa najčešće se utvrđuju u referentnim knjigama, moraju se prilagoditi odgovarajućim posebnim uvjetima. Omjeri prinosa izračunavaju se na temelju planiranih prinosa usjeva i produktivnosti životinja.

U slučajevima kada je potrebno osigurati unaprijed određene odnose između varijabli, tehnički i ekonomski koeficijenti predstavljaju koeficijente proporcionalnosti. Na primjer, udio usjeva u plodoredu ili udio neke hrane za životinje u ukupnoj grupi hrane za životinje itd.

Desna strana ograničenja (b i) nazivaju se konstantama, tj. konstantne vrijednosti. To uključuje opseg proizvodnih resursa - zemljišta, rada, strojeva, gnojiva, kapitalnih ulaganja itd. Proizvodne resurse treba odrediti uzimajući u obzir njihovo stvarno stanje, a imperativ je uzeti u obzir i razdoblje planiranja. Osim toga, oni proizvodni resursi, čija je upotreba neravnomjerna tijekom cijele godine, računaju se ne samo za godinu u cjelini, već i za pojedina intenzivna razdoblja ili mjesece (radni resursi).

Proizvodni resursi određuju se u različitim jedinicama: zemljište - u hektarima, radna snaga - u radnim danima ili u radnim satima, oprema - u broju izmjena strojeva, smjenama ili dnevnoj proizvodnji itd.

Stoga utvrđivanje dostupnosti proizvodnih resursa nije lako. Potrebno je pažljivo analizirati proizvodnu djelatnost gospodarstva, korištenje radne snage, zemljišta, tehničkih i drugih resursa, pa tek nakon toga uključiti njihove količine u ograničenja.

Desna strana ograničenja ne odražava samo količinu resursa, već i obujam proizvodnje na gornjoj ili donjoj razini. Niža razina prikazuje se u slučajevima kada je unaprijed poznat obujam proizvodnje, manji od kojeg poljoprivredno gospodarstvo ne bi trebalo proizvoditi, a gornja razina ne dopušta proizvodnju proizvoda iznad određenog volumena. Ova ograničenja nisu uvijek potrebna. Međutim, gotovo nijedan problem koji uključuje definiciju kombinacije industrija ne prolazi bez odgovarajućih ograničenja za proizvode, u protivnom će se pokazati jednostrano rješenje. To je zbog činjenice da učinkovitost industrija nije ista.

U svim ostalim ograničenjima, nule se stavljaju s desne strane, jer formuliraju uvjete za proizvodnju i korištenje proizvoda ili odražavaju ograničenja proporcionalne komunikacije.

Ograničenje Je matematički izraz koji veže varijable u obliku jednakosti i nejednakosti. Obrazac za sva ograničenja sustav ograničenja zadacima. Sustav ograničenja u matematičkom obliku karakterizira uvjete problema. Potpunost odraza ovih uvjeta ovisi o sastavu ograničenja. Stoga se pri određivanju broja ograničenja moraju uzeti u obzir dvije okolnosti:

v odražavati u zadatku samo one uvjete koji doista ograničavaju mogućnosti proizvodnje;

v previše ograničenja povećava veličinu problema i otežava njegovo rješavanje

Postoje tri vrste ograničenja: jednakost (=), nejednakost tipa manja ili jednaka (≤), nejednakost tipa veća ili jednaka (≥). Na primjer,

gdje i = 1, 2, … , m... Označavaju se promjenjivi koeficijenti a ij gdje indeks i- restrikcijski broj, indeks j- promjenjivi broj, označeni su slobodni članovi (desna strana ograničenja) b i, indeks i- broj ograničenja.

Ograničenja prvog tipa nazivaju se gornja ograničenja, budući da lijeva strana nejednakosti ne može biti veća od određene vrijednosti (konstante). Ograničenja trećeg tipa nazivaju se ograničenjima odozdo, budući da lijeva strana nejednadžbe ne može biti niža od određene vrijednosti (konstante).

U smislu značenja, sva se ograničenja mogu podijeliti na glavna, dodatna i pomoćna.

Glavna ograničenja su - to su oni koji se preklapaju sa svim ili većinom varijabli zadatka. U pravilu se uz njihovu pomoć odražavaju osnovni uvjeti problema - u smislu zemlje, rada, hrane za životinje, hranjivih tvari, tehnologije itd.

Dodatna ograničenja nadovezuju se na dio varijabli ili na jednu varijablu. Ova ograničenja se uvode u slučajevima kada je potrebno ograničiti veličinu pojedinih varijabli odozgo ili odozdo, na primjer, uzimajući u obzir zahtjeve plodoreda ili uzimajući u obzir fiziološke granice zasićenosti prehrane pojedinim krmivima ili njihovim skupinama. Dakle, dodatna ograničenja odražavaju različite dodatne uvjete koji nastaju tijekom simulacije. No svako dodatno ograničenje sužava opseg slobode izbora. Stoga ih treba pažljivo uvoditi u zadatak, u razumnim granicama i kada je to potrebno.

Pomoćna ograničenja, u pravilu nemaju neovisno značenje i uvode se u problem radi formalizacije pojedinačnih uvjeta. To uključuje ograničenja koja uspostavljaju proporcionalni odnos između pojedinih varijabli ili njihovih skupina.

Procjena varijabli u funkciji cilja (s j) su koeficijenti koji izražavaju iznos ukupnog prihoda ili troškova po jedinici mjere varijable. Procjena varijable, u pravilu, izražava prihvaćeni kriterij optimalnosti. Može se prikazati i u naravi i u gotovini, tj. jedinični troškovi (trošak proizvodnje).

Uvjet za nenegativnost varijabli zapisuje se u obliku

x j≥ 0, j = 1, 2, ..., n.

U stvarnom životu proizvodnje, na temelju uvjeta zadatka, iz ovog zapisa strukturnog ekonomsko -matematičkog modela (EMM) sastavlja se popis varijabli i ograničenja, pripremaju se početne informacije, gradi detaljan problem EMM -a, koji je zatim se zapisuje u obliku matrice (tablice), unosi u računalo i prema odgovarajućem programu vrši se izračun i analiza rezultata. i = 1, ..., m, (1.5)

j = 1, …, n. (1.6)

Vektor x = (x 1 , x 2 , …, x n), komponente x j koja zadovoljavaju ograničenja (1.2) i (1.3) [ili (1.5) i (1.6) u minimalnom problemu] naziva se prihvatljiva odluka ili prihvatljiv plan LP zadaci. Poziva se zbirka svih važećih planova mnogo valjanih planova.

Kanonski oblik problema linearnog programiranja karakterizira činjenica da sadrži ciljnu funkciju, sva ograničenja jednakost, sve varijable nisu negativne.

Svaki problem linearnog programiranja može se svesti na problem linearnog programiranja u kanonskom obliku. Da biste to učinili, u općem slučaju morate biti u mogućnosti problem maksimizacije svesti na problem minimiziranja; idite od ograničenja nejednakosti do ograničenja jednakosti i zamijenite varijable koje ne poštuju uvjet nenegativnosti.

Pravilo za svođenje problema linearnog programiranja na kanonski oblik je kako slijedi:

1) ako je u izvornom zadatku potrebno odrediti maksimum linearne funkcije, tada treba promijeniti predznak i potražiti minimum ove funkcije;

2) ako je u ograničenjima desna strana negativna, to ograničenje treba pomnožiti s - 1;

3) ako među ograničenjima postoje nejednakosti, onda se uvođenjem dodatnih varijabli nenegativnih varijabli one pretvaraju u jednakosti. Na primjer, dodatne varijable S j u ograničenja tipa manje ili jednako (£) unose se sa znakom plus:

Dodatne varijable S j u tip ograničenja veća ili jednaka (≥) unose se sa znakom minus:

Da biste uklonili negativnost dodatnih varijabli - S j uvesti umjetne varijable sa znakom plus + M j s vrlo velikim vrijednostima.