Prehod iz omejitev linearnega matematičnega modela. Ustvarite matematični model problema linearnega programiranja. Izbira obsega prerazporeditve

Predavanje 2

V kanonska oblika

sprejemljiva odločitev ZJN(sprejemljiv načrt).

optimalna rešitev LPP.

Potreba

Primer.

Zapišimo nalogo vanjo kanonska oblika

Posebne situacije grafične rešitve LPP

Razen, če je težava edina optimalna rešitev za in morda posebne situacije:

1. problem ima neskončno število optimalnih rešitev - ekstrem funkcije je dosežen na intervalu ( alternativa optimalna)- slika 2;

2. opravilo ni rešljivo zaradi neomejenosti IDT ali - slika 3;

3. SDT - enotno točko Ah, potem;

4. opravilo ni rešljivo če je ODR prazno območje.

A

Slika 2 Slika 3

Če je črta ravni vzporedna s strani območja izvedljivih rešitev, potem je ekstrem dosežen na vseh točkah stranice. Problem ima nešteto optimalnih rešitev - alternativni optimum ... Optimalno rešitev najde formula

kje je parameter Za katero koli vrednost od 0 do 1 je mogoče pridobiti vse točke odseka, za vsako od katerih ima funkcija enako vrednost. Od tod tudi ime - alternativni optimum.

Primer... Problem rešite grafično linearno programiranje (alternativni optimum):

Vprašanja za samokontrolo

1. Zapišite problem linearnega programiranja na splošno.

2. Zapišite problem linearnega programiranja v kanonični in standardni obliki.

3. Katere transformacije lahko uporabite za prehod iz splošne ali standardne oblike problema linearnega programiranja v kanonski?

4. Podajte opredelitev izvedljivih in optimalnih rešitev problema linearnega programiranja.

5. Katera od rešitev je "najboljša" za problem minimiziranja funkcije, če ?

6. Katera od rešitev je "najboljša" za problem maksimiziranja funkcije, če ?

7. Zapišite standardno obliko matematičnega modela problema linearnega programiranja z dvema spremenljivkama.

8. Kako v dveh spremenljivkah zgraditi pol ravnino, podano z linearno neenakostjo ?

9. Kaj imenujemo rešitev sistema linearnih neenakosti v dveh spremenljivkah? Na ravnini konstruirajte območje izvedljivih rešitev takega sistema linearnih neenakosti, ki:

1) ima edinstveno rešitev;

2) ima neskončno število rešitev;

3) nima ene same rešitve.

10. Zapišite si za linearna funkcija vektorski gradient, poimenujte vrsto ravni ravni. Kako sta liniji nagiba in ravni postavljeni drug glede drugega?

11. Oblikujte algoritem za grafično metodo za reševanje standardnega LPP z dvema spremenljivkama.

12. Kako najti koordinate in vrednosti rešitve?

13. Narišite območje izvedljivih rešitev, nagibne in nivojske črte za probleme linearnega programiranja, v katerih:

1) je dosežen na eni točki in - na segmentu ODR;

2) je dosežen na eni točki ODR in.

14. Podajte geometrijsko ponazoritev LPP, če je:

1) ima edine optimalne rešitve za in;

2) ima veliko optimalnih rešitev za.

Predavanje 2

grafična metoda iskanje optimalne rešitve

1. Oblike linearnih matematičnih modelov in njihova transformacija

2. Grafična metoda za reševanje problema linearnega programiranja

3. Posebne situacije grafične rešitve LPP

4. Grafična rešitev ekonomskih problemov linearnega programiranja

Oblike linearnih matematičnih modelov in njihova transformacija

Matematični model problema linearnega programiranja (LPP) je mogoče zapisati v eni od treh oblik.

V splošna oblika matematičnega modela potrebno je najti največjo ali najnižjo vrednost ciljne funkcije; sistem omejitev vsebuje neenakosti in enačbe; niso vse spremenljivke lahko negativne.

V kanonska oblika matematični model je potreben za iskanje maksimuma ciljne funkcije; sistem omejitev je sestavljen samo iz enačb; vse spremenljivke so negativne.

V standardni obliki matematičnega modela je treba najti največjo ali najnižjo vrednost funkcije; vse omejitve so neenakosti; vse spremenljivke so negativne.

Rešitev sistema omejitev, ki izpolnjuje pogoje nenegativnosti spremenljivk, se imenuje sprejemljiva odločitev ZJN(sprejemljiv načrt).

Niz izvedljivih rešitev se imenuje območje dopustnih rešitev LPP.

Uresničljiva rešitev, pri kateri ciljna funkcija doseže ekstremno vrednost, se imenuje optimalna rešitev LPP.

Tri oblike pisanja LPP so enakovredne v smislu, da se lahko vsaka od njih z matematičnimi transformacijami zmanjša na drugo obliko.

Potreba prehod iz ene oblike matematičnega modela v drugega je povezana z metodami reševanja problemov: na primer preprosta metoda, ki se pogosto uporablja v linearnem programiranju, se uporablja za problem, napisan v kanonični obliki, grafična metoda pa za standardno obliko matematičnega modela.

Prehod v kanonsko obliko pisanja ZLP.

Primer.

Zapišimo nalogo vanjo kanonska oblika, uvedbo dodatne (bilančne) spremenljivke z znakom "+" na levi strani prve neenakosti sistema omejitev in dodatne spremenljivke z znakom minus na levi strani druge neenakosti.

Ekonomski pomen različnih dodatnih spremenljivk morda ni enak: odvisen je od ekonomskega pomena omejitev, v katere so te spremenljivke vključene.

Tako v problemu uporabe surovin prikazujejo preostanek surovin, v problemu izbire optimalnih tehnologij pa neizkoriščen čas podjetja za določeno tehnologijo; pri problemu rezanja - sproščanje praznih delov določene dolžine nad načrtom itd.

Opredelitev. Linearno programiranje (LP) - znanost o raziskovalnih metodah in iskanju skrajnih (največjih in najmanjših) vrednosti linearne funkcije, za katere neznanke so naložene linearne omejitve.

Ta linearna funkcija se imenuje cilj, in se imenujejo omejitve, ki so matematično zapisane v obliki enačb ali neenakosti sistem omejitev.

Opredelitev. Matematični izraz ciljne funkcije in njene omejitve se imenuje matematični model ekonomskega problema.

Na splošno je matematični model problema linearnega programiranja (LP) zapisan kot

z omejitvami:

kje x j- neznano; a ij, b i, c j- dane konstantne vrednosti.

Vse ali nekatere enačbe sistema omejitev lahko zapišemo v obliki neenakosti.

Matematični model v bolj jedrnatem zapisu ima obliko

z omejitvami:

Opredelitev. Možna rešitev (načrt) problema linearnega programiranja je vektor = ( x 1 , x 2 ,..., x n), sistem omejitev.

Niz izvedljivih rešitev tvori področje izvedljivih rešitev (ODS).

Opredelitev. Izvedljiva rešitev, pri kateri ciljna funkcija doseže svojo ekstremno vrednost, se imenuje optimalna rešitev problema linearnega programiranja in jo označimo z opt.

Osnovna izvedljiva rešitev (NS 1 , NS 2 , ..., x r , 0, …, 0) je referenčna rešitev, kjer r - rang sistema omejitev.

Matematični model problema LP je lahko kanoničen in nekanoničen.

7. Reševanje problemov linearnega programiranja z grafično metodo... Grafi funkcijskih omejitev. Ravne črte.

Grafična metoda za reševanje problemov linearnega programiranja

Najenostavnejša in najbolj intuitivna metoda linearnega programiranja je grafična metoda. Uporablja se za reševanje problemov LP z dvema spremenljivkama, podanima v nekanonski obliki, in številnimi spremenljivkami v kanonični obliki, pod pogojem, da vsebujejo največ dve prosti spremenljivki.

Z geometrijskega vidika se pri problemu linearnega programiranja išče takšna kotna točka ali niz točk iz izvedljivega niza rešitev, pri katerih je dosežena najvišja (najnižja) raven črta, ki se nahaja dlje (bližje) kot drugi v smeri najhitrejše rasti.

Če želite v grafični rešitvi problemov LP najti ekstremno vrednost ciljne funkcije, uporabite vektor L() na površini NS 1 OH 2 , ki jih označujemo . Ta vektor prikazuje smer najhitrejše spremembe ciljne funkcije. Z drugimi besedami, vektor je normala ravni ravni L()

kje e 1 in e 2 - vektorji enot vzdolž osi VL 1 in VL 2 oziroma 2; tako = (∂L / ∂х 1 , ∂L / ∂х 2 ). Koordinate vektorja so koeficienti ciljne funkcije L (). Konstrukcija nivojske črte bo podrobno obravnavana pri reševanju praktičnih problemov.

Algoritem za reševanje problemov

1. Poiščite območje izvedljivih rešitev sistema omejitev problema.

2. Ustvarjanje vektorja .

3. Narišite ravninsko črto L 0 , ki je pravokotna .

4. Premaknite črto ravni v smeri vektorja za naloge do maksimuma in v nasprotni smeri , za naloge na minimum.

Črtna črta se premakne, dokler nima le ene skupne točke s področjem dopustnih rešitev. Ta točka, ki določa edino rešitev problema LP, bo skrajna točka.

Če se izkaže, da je nivojska črta vzporedna z eno od stranic ODR, potem je ekstrem dosežen na vseh točkah ustrezne strani in problem LP bo imel neskončno število rešitev. Rečeno je, da ima takšen problem LP alternativni optimum, rešitev pa najdemo po formuli:

Kjer 0 ≤ t≤ 1, 1 in 2 - optimalne rešitve na vogalnih točkah ODR.

Problem LP je lahko nerešljiv, če se izkaže, da so omejitve, ki ga opredeljujejo, protislovne.

5. Poiščite koordinate ekstremne točke in vrednost ciljne funkcije v njej.

Primer 3. Izbira optimalne možnosti sproščanja izdelka

Podjetje proizvaja dve vrsti sladoleda: kremasto in čokoladno. Za izdelavo sladoleda se uporabljata dva začetna proizvoda: mleko in polnila, katerih stroški na 1 kg sladoleda in dnevne zaloge so podani v tabeli.

Študija prodajnega trga je pokazala, da dnevno povpraševanje po sladoledu presega povpraševanje po čokoladnem sladoledu, vendar za največ 100 kg.

Poleg tega je bilo ugotovljeno, da povpraševanje po čokoladnem sladoledu ne presega 350 kg na dan. Maloprodajna cena 1 kg kremastega sladoleda 16 rubljev, čokolade - 14 rubljev.

Koliko sladoleda vsake vrste bi moralo podjetje proizvesti, da bi povečalo prihodek od prodaje izdelkov?

Rešitev. Označimo: x 1 - dnevni obseg proizvodnje sladoleda, kg; x 2 - dnevna proizvodnja čokoladnega sladoleda, kg.

Sestavimo matematični model naloge.

Cene sladoleda so znane: 16 rubljev oziroma 14 rubljev, zato bo funkcija cilja videti tako:

Določili bomo omejitve mleka za sladoled. Njegova poraba za kremast sladoled - 0,8 kg, za čokolado - 0,5 kg. Mlečna zaloga 400 kg. Zato bo prva neenakost videti tako:

0,8x 1 + 0,5x 2 ≤400 - prva neenakost je omejitev. Preostale neenakosti so sestavljene na podoben način.

Rezultat je sistem neenakosti. to je področje reševanja vsake neenakosti. To lahko naredimo tako, da v vsako od neenakosti zamenjamo koordinate točke O (0: 0). Kot rezultat dobimo:

Slika OABDEF - področje dopustnih rešitev. Gradimo vektor (16; 14). Ravna linija L 0 je podano z enačbo 16x 1 + 14x 2 = Const. Izberemo poljubno število, na primer število 0, nato 16x 1 + 14x 2 = 0. Na sliki je za vrstico L 0 izbrano določeno pozitivno število, ki ni enako nič. Vse ravni ravni so vzporedne med seboj. Normalni vektor ravni črte.

Premaknite črto ravni v smeri vektorja. Izhodna točka L 0 iz področja izvedljivih rešitev je točka D, so njegove koordinate določene kot presečišče ravnih črt, določenih z enačbami:

Ko rešimo sistem, dobimo koordinate točke D(312,5; 300), v katerem bo optimalna rešitev, t.j.

Tako bi moralo podjetje dnevno proizvesti 312,5 kg sladoleda in 300 kg čokoladnega sladoleda, prihodki od prodaje pa bodo znašali 9 200 rubljev.

8. Zmanjšanje poljubnega problema linearnega programiranja na glavni problem. Pretvarjanje omejitev neenakosti v ustrezne enačbe.

9. Poenostavljena metoda... Opis in algoritem metode, njena uporabnost.

Za rešitev problema s preprosto metodo je potrebno:

1. Navedite način za iskanje optimalne rešitve podpore

2. Navedite način prehoda iz ene podporne rešitve v drugo, pri kateri bo vrednost ciljne funkcije bližje optimalni, tj. navesti način za izboljšanje referenčne rešitve

3. Določite merila, ki vam omogočajo, da pravočasno ustavite iskanje podpornih rešitev glede optimalne rešitve ali sprejmete sklep o odsotnosti optimalne rešitve.

Algoritem simpleksne metode za reševanje problemov linearnega programiranja

1. Prenesite težavo v kanonično obliko

2. Poiščite začetno podporno rešitev z "enoto osnove" (če rešitve podpore ni, potem problem nima rešitve zaradi nezdružljivosti sistema omejitev)

3. Izračunajte ocene vektorskih razširitev na podlagi podporne rešitve in izpolnite tabelo simpleksne metode

4. Če je izpolnjeno merilo edinstvenosti optimalne rešitve, se rešitev problema konča

5. Če je izpolnjen pogoj za obstoj niza optimalnih rešitev, potem s preprostim naštevanjem najdemo vse optimalne rešitve

10. Problem transporta. Opredelitev, vrste, metode iskanja začetne rešitve transportnega problema.

Transportni problem je eden najpogostejših problemov linearnega programiranja. Njegov cilj je razviti najbolj racionalne načine in sredstva za prevoz blaga, odpraviti pretirano dolge razdalje, prihajajoče, ponavljajoče se prevoze.

1. Iskanje začetne rešitve podpore;

2. preverjanje optimalnosti te rešitve;

3. Prehod iz ene podporne rešitve v drugo.

3.1. Splošni problem linearnega programiranja

Linearno programiranje- to je najbolj razvit odsek matematično programiranje, s pomočjo katerih se izvaja analiza in reševanje skrajnih problemov z linearnimi povezavami in omejitvami.

Linearno programiranje vključuje številne hevristične (približne) rešitvene metode, ki v danih pogojih omogočajo vse možne možnosti rešitve proizvodnih težav, da izberejo najboljše, optimalne. Te metode vključujejo naslednje - grafično, simpleksno, potencialno metodo (spremenjena distribucijska metoda - MODI), Hitchkovo, Kreko, Voglovo približevalno metodo in druge.

Nekatere od teh metod združuje skupno ime - distribucijska ali transportna metoda.

Rojstni kraj linearnega programiranja je Rusija. Prva dela o linearnem programiranju bodočega akademika L.V. Kantorovich so izšli leta 1939. Leta 1975 je prejel Nobelovo nagrado za ekonomijo za razvoj metod linearnega programiranja. Ker je večina del akademika L.V. Kantorovich je namenjen reševanju prometnih problemov, lahko se šteje, da navedena Nobelova nagrada priznava tudi zasluge ruske transportne znanosti.

V cestnem prometu se metode linearnega programiranja že od šestdesetih let uporabljajo za reševanje velikega števila najpomembnejših proizvodnih problemov, in sicer: zmanjšanje razdalje prevoza tovora; priprava optimalne sheme prevoza; izbira najkrajših poti gibanja; naloge prevoza različnih, vendar zamenljivih tovorov; dnevno načrtovanje izmene; načrtovanje prevoza manjšega tovora; distribucija avtobusov po progah in drugo.

Značilnosti modela linearnega programiranja so naslednje:

Ciljna funkcija in omejitve so izražene z linearnimi odvisnostmi (enakovrednosti ali neenakosti);

Število odvisnosti je vedno manjše od števila neznank (pogoj negotovosti);

Nenegativnost iskanih spremenljivk. Splošna oblika pisanja linearnega programskega modela v skrajšani obliki je naslednja:

Najti NS ij ≥ 0 (j = 1, 2 ... n) pod omejitvami naslednjega tipa:

Te omejitve minimizirajo (ali povečajo) ciljno funkcijo

Standardna oblika pisanja linearnega programskega modela je sistem linearne enačbe posneto v kanonski obliki, to je v obliki linearnih enakovrednosti, v negativnih številkah:

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 ..

Če je model zapisan v obliki neenakosti v negativnih številkah, to pomeni, da ima obliko

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, ..

potem se ta zapis zmanjša na kanonski(3.1) z uvedbo dodatnih spremenljivk x n +1> 0 (jaz=1,2…m) levo od neenakosti (ali preklic števila spremenljivk, če je znak neenakosti usmerjen v drugo smer). Dodatne spremenljivke so osnova.

Standardna oblika reševanja problema linearnega programiranja je iskanje rešitev sistema linearnih enačb v negativnih številkah, ki minimizirajo ciljno funkcijo. V tem primeru ima funkcija cilja obliko

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

kje s 1, s 2 ... s n- koeficiente ciljne funkcije L s spremenljivkami NS j.

Dodatne spremenljivke vstopijo v ciljno funkcijo z ničelnimi koeficienti.

V primeru maksimiziranja ciljne funkcije L predznake spremenljivk ciljne funkcije je treba obrniti in spet pridemo do problema minimizacije, tj. ena naloga se z zamenjavo zmanjša na drugo L na - L ali maks L= min (- L).

Osnovna rešitev sistema linearnih enačb (3.1) je rešitev, v kateri so neosnovnim spremenljivkam podane nič vrednosti.

Osnovna rešitev se imenuje dopustna, pri kateri so spremenljivke, vključene v osnovo, negativne.

Optimalna rešitev je izvedljiva rešitev, ki maksimizira (ali minimizira) ciljno funkcijo (3.3).

Vsak problem linearnega programiranja ustreza drugemu, ki se imenuje problem dvojnega linearnega programiranja. Prvotni problem v zvezi z dvojnim se imenuje neposreden. Neposredni in dvojni problemi tvorijo par, ki se v linearnem programiranju imenuje dvojni par. Neposredni in dvojni par tvorita asimetričen par, ko je neposredni problem zapisan v kanonični obliki, in simetrični par, ko so pogoji problema zapisani z neenakostmi.

Pravila za sestavljanje matematičnega modela dvojnega problema temeljijo na pravilih matričnega računa.

Koncept dvojnosti se pogosto uporablja pri analizi problemov linearnega programiranja. Lastnost dvojnosti je podrobno obravnavana v vsakem posameznem primeru.

3.2. Grafično-analitična metoda

Grafoanalitična metoda je ena najpreprostejših metod linearnega programiranja. Jasno razkriva bistvo linearnega programiranja, njegovo geometrijsko interpretacijo. Njegova pomanjkljivost je, da omogoča reševanje problemov z 2 ali 3 neznankami, se pravi, da se uporablja za ozek spekter težav. Metoda temelji na pravilih analitične geometrije.

Reševanje problema z dvema spremenljivkama x 1 in x 2, ki v smislu problema ne bi smel biti negativen, se izvaja v kartezijanskem koordinatnem sistemu. Enačbe x 1= 0 in x 2= 0 so osi koordinatnega sistema prvega kvadranta

Razmislimo o rešitveni metodi s posebnim primerom.

Primer 3.1. V skladišču je 300 ton izdelkov iz penastega betona in 200 ton jekla. Avtomobilsko podjetje mora te izdelke dostaviti v objekt v izgradnji. Avtomobilsko podjetje ima tovornjake KamAZ - 5320 in

ZIL-4314. Za eno potovanje lahko KamAZ-5320 dostavi 6 ton penastega betona in 2 toni jekla, dobiček od vožnje pa bo 4 tisoč rubljev. ZIL-4314 v enem potovanju dostavi 2 toni penastega betona in 4 tone jekla, dobiček od potovanja je 6 tisoč rubljev. Prevoz je treba organizirati tako, da bo avtomobilskemu podjetju zagotovljen največji dobiček.

Zgradimo matematični model problema. Označimo s x 1 potrebno število voznikov KamAZ-5320 in skozi NS 2 potrebno število kolesarjev ZIL-4314.

Skupni prevoz v t izdelkov iz penastega betona je 6 x 1 + 2x 2 in iz jekla 2 x 1 + 4x 2... Omejitve prevoza glede na število razpoložljivih predmetov so 6 x 1 + 2x 2 ≤ 300t za penasti beton in 2 x 1 + 4x 2 ≤ 200t za jeklo.

Skupni dobiček v tisoč rubljih je izraženo kot 4 NS 1 + 6NS 2, ki ga je treba maksimizirati in ki je merilo optimalnosti pri obravnavanem problemu. Tako je matematični model problema videti na naslednji način. Potrebno je čim bolj povečati ciljno funkcijo

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

Razmislite o enačbi 6 x 1 + 2x 2 = 300. Za izgradnjo ravne črte, opisane s to enačbo, najdemo dve točki, ki ležita na tej ravni črti. Ob x 1= 0 iz enačbe ravne črte najdemo 2 x 2 = 300, od koder je x 2 = 150. Zato točka A s koordinatami (0,150) leži na želeni ravni črti. Ob x 2= 0 imamo 6 x 1= 300, od tod x 1 = 50 in točka D s koordinatami (50,0) je tudi na iskani črti. Skozi ti dve točki potegnite ravno črto AD(slika 3.1).

Linearna neenakost 6 x 1 + 2x 2 ≤ 300 je polravnina, ki se nahaja na eni od strani zgrajene ravne črte 6 x 1 + 2x 2 = 300. Če želimo izvedeti, na kateri strani te ravne črte se nahajajo točke zahtevane polravnine, nadomestimo 6 x 1 + 2x 2 ≤ 300 koordinat katere koli točke, ki ne leži na mejni črti. Na primer, izvor je 0- (0,0). Zanj je neenakost 6 ∙ 0 + 2 ∙ 0 = 0< 300. Это значит, что начало координат лежит в области допустимых значений, которая находится слева от прямой AD in na sl. 3.1 je zasenčeno.

Enačba 2 x 1 + 4x 2= 200 bomo zgradili na dveh točkah. Ob x 1 = 0 4x 2 = 200, od kod x 2 = 50. Potem točka E ima koordinate (0,50) in pripada želeni ravni črti. Ob x 2= 0, 2x 2 = 200, točka z se nahaja na dani črti s koordinatami (100,0). Koordinate točke zamenjamo v neenakosti z(0,0) dobimo 2 ∙ 0 + 4 ∙ 0 = 0< 200. Значит, начало координат находится в области допустимых значений от прямой 2x 1+ 4x 2= 200.

Sistem omejitev nalog zahteva, da načrti ( x 1; x 2) izpolnjujejo vse štiri neenakosti, tj. dovoljene zasnove so točke ( x 1; x 2) morajo biti v vseh štirih polravninah hkrati. To zahtevo izpolnjujejo le točke, ki se nahajajo znotraj in na meji poligona. OEKD, ki je poligon izvedljivih rešitev.

Točke poligona izvedljivih rešitev so točke O, E, K, D, linijski odseki OE, EK, KD, OD- njegova rebra. Vsaka točka poligona OEKD je načrt problema, ki izpolnjuje vse njegove pogoje. Točke poligona nastanejo s presečiščem dveh ravnih črt in ustrezajo osnovnim načrtom problema, med katerimi je najboljši (optimalen) načrt. Tako bo temeljnih načrtov toliko, koliko je točk poligona izvedljivih rešitev.

Za ciljno funkcijo je mogoče dobiti tudi jasen geometrijski prikaz. L = 4x 1 + 6x 2... Popravimo na primer neko vrednost ciljne funkcije L= 120. enačba 4 x 1 + 6x 2 = 120 definira črto skozi točko V s koordinatami (x 1 = 0; x 2 = 20) in točko L s koordinatami (( NS 1 = 30; NS 2 = 0). Oddelek BL leži znotraj poligona OEKD... Zato je za vse načrte (točke) tega segmenta vrednost ciljne funkcije enaka in enaka 120. Z dodelitvijo drugih vrednosti ciljni funkciji dobimo vzporedne črte, ki jih imenujemo ravni ravni ciljno funkcijo.

Premikanje naravnost L vzporedno s seboj v eni smeri dobimo povečanje ciljne funkcije, v nasprotni smeri pa njeno zmanjšanje. V tem primeru gibanje ravne črte BL na desni določa povečanje ciljne funkcije, ki jo maksimiramo. To počnemo, dokler je naravnost BL bo imel vsaj eno skupno točko s poligonom izvedljivih rešitev OEKD... Sl. 3.1 iz tega sledi, da bo zadnja točka, ki jo prečka ravna črta ravni ciljne funkcije, točka TO... To pomeni, da je bistvo TO določa optimalen načrt nalog.

Naraščajoča smer, pravokotna na ravninsko črto, se imenuje smer največjega povečanja ciljno funkcijo in določa njeno največjo rast. To smer lahko nastavite brez risanja ravni ravni. Za to je potrebno na osi x 1 in x 2 odložiti odseke, enake koeficientom ciljne funkcije, in iz njih kot koordinate zgraditi vektor največjega povečanja ciljne funkcije. V matematiki se imenuje gradient in označimo z grad. Gradient za delovanje L = 4x 1 + 6x 2 bo vektor n| 4; 6 | ... Za udobje njegove gradnje bomo koordinate povečali na primer 10 -krat, tj. n | 40; 60 | ... Konstruirajte gradient ciljne funkcije L, za katero točko s koordinatami (40; 60) povežemo z začetkom. Črte ravni ciljne funkcije so narisane pravokotno na smer nagiba.

Tako je bilo tako ali drugače ugotovljeno, da je bistvo TO določa optimalen načrt problema, katerega vrednosti spremenljivk ustrezajo koordinatam dane točke. Za določitev koordinat je potrebno rešiti sistem enačb ravnih črt, ki tvorijo to točko:

6x 1 + 2x 2= 300;

2x 1 + 4x 2= 200.

Izenačimo koeficiente pri x 1 tako, da drugo enačbo pomnožimo s 3 in od druge enačbe odštejemo prvo. Dobimo 10 x 2= 300,x 2 = 30. Če vrednost x 2 = 30 nadomestimo v kateri koli enačbi, na primer v prvi, določimo vrednost NS 1:

6x 1+ 2NS · 30 = 300,

od kod 6 x 1 = 300 - 60 = 240, torej x 1 = 40.

Tako mora avtomobilsko podjetje za največji dobiček opraviti 40 potovanj na KamAZ-5320 in 30 potovanj na ZIL-4314. Največji dobiček v tem primeru bo

L = 4x 1 + 6x 2= 4 40 + 6 30 = 340 tisoč rubljev.

Na podlagi obravnavanega primera in geometrijske interpretacije optimizacijskega problema z dvema spremenljivkama lahko sklepamo naslednje:

1) v dvodimenzionalnem prostoru je območje izvedljivih rešitev poligon;

2) vsaka stran poligona ustreza vrednosti ene spremenljivke, ki je enaka nič;

3) vsako oglišče poligona izvedljivih rešitev ustreza vrednostim dveh spremenljivk, ki so enake nič;

4) ravna črta ustreza vsaki vrednosti ciljne funkcije;

5) optimalna rešitev problema ustreza oglišču poligona, pri katerem ciljna funkcija pridobi optimalno vrednost, medtem ko so koordinate tega oglišča optimalne spremenljivke.

Na splošno imajo optimizacijski problemi podobno geometrijsko interpretacijo. Niz načrtov problema bo polieder, katerega oglišča ustrezajo referenčnim načrtom. Pri reševanju problema se izvede prehod iz enega oglišča poliedra v drugega z veliko vrednostjo ciljne funkcije, dokler ni dosežena njegova optimalna vrednost. Upoštevajte, da je učinkovitost optimizacijskih metod ravno v tem, da iskanje točk (iteracija) poteka le v smeri največjega povečanja ciljne funkcije. Zato se ne upoštevajo vsi vrhovi, ki jih je ogromno, ampak le tisti, ki so bližje skrajnosti.

Pri določanju razreda optimizacijskih problemov in izbiri metode za njegovo reševanje je treba vedeti, ali je niz izvedljivih rešitev konveksna ali nekonveksna, linearna ali nelinearna ciljna funkcija.

Po definiciji se niz imenuje izbočenače za kateri koli dve točki pripada celotnemu segmentu, ki povezuje te točke. Primeri konveksnih množic so na primer segment (slika 3.2, a), ravnina v obliki kroga, kocka, paralelepiped, pa tudi poligoni, ki se v celoti nahajajo na eni strani vsake od njegovih strani itd.

Na sl. 3.2b prikazuje nekonveksne množice. V nekonveksnih nizih lahko označimo vsaj dve točki odseka AB, ki ne pripadata obravnavanemu nizu.

3.3. Enostavna metoda

Enostavna metoda Je običajna metoda za reševanje problemov linearnega programiranja. Metoda je dobila ime po besedi "simplex", kar pomeni najpreprostejši konveksni mnogokotnik, katerega število točk je vedno eno več kot dimenzija prostora. Enostavno metodo je v ZDA v poznih 1940 -ih letih razvil matematik J. Danzig.

Enostavna metoda vključuje pridobivanje nenegativne osnovne rešitve sistema kanoničnih linearnih enačb tipa (3.1), naknadno minimiziranje (maksimiziranje) ciljne funkcije (3.3) in na ta način najti optimalne vrednosti iskanih spremenljivk x 1, x 2 ... x n.

Zamisel o simpleksni metodi je, da se v procesu računalništva zaporedno preide iz prve osnovne rešitve v drugo, tretjo itd. skozi tako imenovane simpleksa preobrazbe. Pretvorbe se izvajajo v obliki tabel simpleksa, kar močno poenostavi in ​​pospeši izračune.

Za pridobitev negativnih osnovnih rešitev sistema linearnih enačb je treba postopek odpravljanja neznank izvesti tako, da prosti izrazi enačb ostanejo negativni v vseh fazah procesa. V tem primeru je treba voditi naslednje pravilo: kot novo osnovno spremenljivko se vzame katera koli prosta spremenljivka, za katero obstaja vsaj en pozitivni koeficient; spremenljivka izhaja iz osnove, ki ustreza najmanjšemu razmerju prostih členov enačb do ustreznih pozitivnih koeficientov enačb za spremenljivko, vneseno v osnovo. Takšne transformacije imenujemo enostavni pretvorniki.

To je zelo pomembno, saj za določitev določene negativne rešitve, ki ustreza največji možni vrednosti katere koli proste spremenljivke pri ničelnih vrednostih drugih prostih spremenljivk, namesto da bi določili obseg navedene spremenljivke in nadomestili njeno največjo vrednost možne vrednosti v splošno rešitev, je dovolj, da to spremenljivko vzamemo kot osnovno in sistem podvržemo simpleksni transformaciji, ki preide na novo osnovo, kar močno poenostavi izračune.

Izračune je priročno izvesti s preprostimi tabelami. Prehod iz ene tabele v drugo ustreza eni ponovitvi, torej prehodu iz ene osnove v drugo, medtem ko se vrednost ciljne funkcije zmanjša. Za določeno število ponovitev gremo na osnovo, za katero dobimo optimalno (minimalno ali največjo) vrednost ciljne funkcije. Na splošno razmislimo o simpleksni metodi.

Splošni problem linearnega programiranja je minimiziranje (maksimiziranje) ciljne funkcije, katere spremenljivke so med seboj povezane s sistemom linearnih enačb, pod pogojem nenegativnosti.

Naj bo treba linearno obliko čim bolj zmanjšati

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

Pod pogoji (zaradi jasnosti se v enačbah ohrani nič in en koeficient):

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.

V tem sistemu enačb že obstaja že pripravljena podlaga, saj vsaka enačba omejitev vsebuje neznanko s koeficientom enakim, ki je v drugih enačbah ni, torej iz koeficientov spremenljivk NS 1 , NS 2 …, x m lahko sestavite matriko identitete.

Rešimo enačbe za osnovne spremenljivke:

x 1 = b 1 - (a 1m + 1 x 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),

ciljno funkcijo pa izrazimo v obliki prostih spremenljivk, pri čemer njihove izraze nadomestimo z prostimi spremenljivkami namesto osnovnih spremenljivk:

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 ..

Spremenljivke x 1, x 2 ..., x m, s pomočjo katerih je bil najden prvi osnovni načrt, so osnovni, preostali x m +1, x m +2, ... x n - prost. Osnovnih spremenljivk mora biti vedno toliko, kolikor je enačb v sistemu. Na podlagi pogoja nenegativnosti je najmanjša vrednost prostih spremenljivk nič. Dobljena osnovna rešitev sistema enačb je njegova začetna dopustna rešitev, t.j. x 1 = b 1, x 2 = b 2, ... x m = b m, x m +1 = 0,…, X n = 0.

Ta rešitev ustreza vrednosti ciljne funkcije

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

Začetna rešitev je preizkušena za optimalnost. Če ni optimalno, potem z uvedbo prostih spremenljivk v osnovo najdemo naslednje izvedljive rešitve z manjšo vrednostjo ciljne funkcije. To naredite tako, da določite brezplačno spremenljivko, ki jo je treba vnesti v osnovo, in spremenljivko, ki mora biti izpeljana iz osnove. Nato se premaknete iz prejšnjega sistema v naslednji enakovreden sistem. To se naredi s preprostimi tabelami. Rešitev problema se nadaljuje, dokler ni dosežena optimalna vrednost ciljne funkcije.

Enostavne tabele so sestavljene na naslednji način (glej tabelo 3.1). Vse spremenljivke so postavljene na vrh tabele NS 1 , NS 2 …, x n in koeficiente c j, s katerim so ustrezne spremenljivke vključene v funkcijo cilja. Prvi stolpec c i je sestavljen iz koeficienta ciljne funkcije za spremenljivke, vključene v osnovo. Sledi stolpec osnovnih spremenljivk in prostih izrazov enačb. Elementi preostalih stolpcev tabele predstavljajo koeficiente spremenljivk, s katerimi so slednje vključene v sistem enačb. Tako vsaka vrstica tabele ustreza enačbi sistema, rešeni glede na osnovno spremenljivko. Tabela prikazuje tudi varianto načrta, ki ustreza ciljni funkciji za dano podlago.

Spodnja vrstica tabele se imenuje kazalo... Vsak njen element (ocena) ∆ j opredeliti

∆j = z j - c j,

kje c j- koeficiente za ustrezne spremenljivke v ciljni funkciji; z j - vsota produktov koeficientov ciljne funkcije za osnovne spremenljivke z ustreznimi spremenljivkami - elementi j-Th stolpec tabele.

miza 3.1

Simplex tabela z začetno veljavnostjo

V praksi omejitve v problemu linearnega programiranja pogosto niso določene z enačbami, ampak z neenakostmi.

Pokažimo, kako lahko preidemo od problema z omejitvami neenakosti do glavnega problema linearnega programiranja.

Naj obstaja problem linearnega programiranja s spremenljivkami, pri katerem so omejitve, ki jih nalagajo spremenljivke, v obliki linearnih neenakosti. V nekaterih od njih je lahko znak neenakosti, v drugih (druga vrsta se s preprosto spremembo znaka obeh delov zmanjša na prvo). Zato vse omejitve neenakosti postavimo v standardni obliki:

Poiskati je treba niz negativnih vrednosti, ki bi zadovoljile neenakosti (4.1) in poleg tega zmanjšale linearno funkcijo:

S tako postavljene naloge je enostavno preiti na glavno nalogo linearnega programiranja. Dejansko uvedimo zapis:

kje so nekatere nove spremenljivke, ki jih bomo poimenovali "dodatne". V skladu s pogoji (4.1) bi morale biti te dodatne spremenljivke tudi negativne.

Tako se soočamo s problemom linearnega programiranja v naslednji formulaciji: poiščite take negativne vrednosti spremenljivk, da ustrezajo sistemu enačb (4.3), hkrati pa linearno funkcijo teh spremenljivk zmanjšajte na minimum:

Kot lahko vidite, imamo v svoji čisti obliki glavno nalogo linearnega programiranja (LPP). Enačbe (4.3) so podane v že dovoljeni obliki za osnovne spremenljivke, ki so izražene kot proste spremenljivke Skupno število spremenljivk je enako, od tega "začetne" in "dodatne". Funkcija L je izražena le kot "začetne" spremenljivke (koeficienti "dodatnih" spremenljivk v njej so enaki nič).

Tako smo problem linearnega programiranja z omejitvami neenakosti zmanjšali na glavni problem linearnega programiranja, vendar z večjim številom spremenljivk, kot je bilo prvotno v problemu.

Primer 1 Obstaja problem linearnega programiranja z omejitvami neenakosti: poiščite negativne vrednosti spremenljivk, ki izpolnjujejo pogoje

in minimiziranje linearne funkcije

To nalogo je treba prenesti v obliko OZLP.

Rešitev. Neenakosti (4.4) zmanjšamo na standardni obrazec;

Predstavljamo dodatne spremenljivke:

Naloga se zmanjša na iskanje negativnih vrednosti spremenljivk

izpolnjevanje enačb (4.6) in minimiziranje linearne funkcije (4.5).

Pokazali smo, kako lahko preidemo od problema linearnega programiranja z omejitvami neenakosti do problema z omejitvami enakosti (LPPP). Obratni prehod je vedno možen - od LPP do problema z omejitvami neenakosti. Če smo v prvem primeru povečali število spremenljivk, ga bomo v drugem primeru zmanjšali in tako odpravili osnovne spremenljivke ter pustili samo proste.

Primer 2. Obstaja problem linearnega programiranja z omejitvami enakosti (LPPP):

in funkcijo, ki jo je treba zmanjšati

Zapisati ga je treba kot problem linearnega programiranja z omejitvami neenakosti.

Rešitev. Ker bomo potem izbrali dve spremenljivki kot brezplačni. Upoštevajte, da spremenljivk ni mogoče izbrati kot proste spremenljivke, saj so povezane s prvo enačbo (4-7): vrednost ene od njih je v celoti določena z vrednostjo druge, proste spremenljivke pa morajo biti neodvisne

Iz istega razloga ni mogoče izbrati spremenljivk kot prostih (povezane so z drugo enačbo). Izberemo kot proste spremenljivke in skozi njih izrazimo vse ostale:

Ker lahko pogoje (4 9) nadomestimo z neenakostmi:

Preidemo v izraz linearne funkcije L na proste spremenljivke, ki nadomeščajo z L namesto njihovih izrazov (4.9). dobimo.

Osnovni koncepti modeliranja

V procesu človekove dejavnosti se razvijajo predstave o določenih lastnostih resničnih predmetov in njihovih interakcijah. Te predstavitve oblikuje oseba v obliki opisov predmetov, za katere se uporablja opisni jezik. To je lahko besedni opis (verbalni modeli), risba, risba, graf, postavitev itd. Vse zgoraj je povzeto z enim pojmom model, in proces izdelave modelov je modeliranje.

Modeliranje Je univerzalen način preučevanja procesov in pojavov v resničnem svetu. Modeliranje je še posebej pomembno pri preučevanju objektov, ki niso dostopni neposrednemu opazovanju in raziskovanju. Ti vključujejo zlasti družbeno-ekonomske pojave in procese.

Študija katerega koli predmeta, katere koli oblike gibanja je razkritje ne le njegovih kvalitativnih, ampak tudi kvantitativnih zakonov, ki jih proučuje matematika. Navedeno v celoti velja za gospodarstvo.

Gospodarstvo- To je sistem družbene proizvodnje, ki dejansko izvaja proizvodnjo, distribucijo, izmenjavo in porabo materialnih dobrin, potrebnih za družbo.

Skladno s tem, ekonomski in matematični model Je ekonomska abstrakcija, izražena v formalnih matematičnih izrazih, katerih logična struktura je določena tako z objektivnimi lastnostmi predmeta opisa kot tudi s subjektivnim ciljnim faktorjem študije, za katero se ta opis izvaja.

Ekonomski in matematični problemi v kmetijstvu se rešujejo z uporabo matematičnih metod. Med njimi so najbolj razvite metode linearnega programiranja (LP). Takšne metode se uporabljajo za reševanje ekonomskih in matematičnih problemov, pri katerih so količinska razmerja izražena linearno, tj. vsi pogoji so izraženi kot sistem linearnih enačb in neenakosti, kriterij optimalnosti pa kot linearna funkcija, ki teži k minimumu ali maksimumu (do ekstrema).

Problem linearnega programiranja je sestavljen iz ciljne funkcije, sistema omejitev in nenegativnega pogoja za spremenljivke.

Dobila funkcijo n spremenljivke Najti je treba največjo ali najmanjšo vrednost te funkcije, pod pogojem, da je argument

Tako zastavljeni optimizacijski problem se imenuje problem matematičnega programiranja. Veliko NS se imenuje niz izvedljivih odločitev, funkcija pa je ciljna funkcija ali ciljna funkcija. Možna rešitev, pri kateri funkcija sprejme največjo (ali najmanjšo) vrednost, se imenuje optimalna rešitev problema.

Če je ciljna funkcija linearna in nastavljena NS je podana s sistemom linearnih enačb in neenakosti, potem se problem imenuje problem linearnega programiranja (LPP). Tako je splošna trditev problema linearnega programiranja naslednja:

poiščite skrajnost funkcije

z omejitvami

pod negativnimi pogoji

Uvedimo zapis:

Zaloge jaz-vrsta vira;

stroški jaz-Vrsta vira za proizvodnjo j-vrsta izdelka;

dobiček na enoto j-Vrsta izdelka.

V kompaktni obliki ima problem linearnega programiranja obliko:

Kompaktni zapis kaže, da splošni model problema linearnega programiranja vključuje pet glavnih elementov:

Spremenljivke, katerih vrednost najdemo v procesu reševanja problema;

Tehnični in ekonomski koeficienti za spremenljivke v omejitvah;

Volumen desne strani neenakosti, ki jih imenujemo konstante problema;

Koeficienti spremenljivk v ciljni funkciji, ki se imenujejo spremenljive ocene;

Spremenljiv indeks;

Indeks omejitev.

Ciljna funkcija(funkcija cilja) je matematični izraz, za katerega želite najti skrajnost, to je največjo ali najmanjšo vrednost.

Spremenljivke x j označujejo take vrste in načine dejavnosti, katerih velikost ni znana in jih je treba določiti med reševanjem problema. Običajno pri težavah s kmetijstvom spremenljivke pomenijo zahtevane velikosti gospodarskih panog, vrste krme v prehrani, znamke traktorjev in kmetijskih strojev itd. Glede na posebne pogoje je lahko isti posevek ali vrsta živine izražen z več spremenljivkami. Na primer žito in krmo; koruza za žito, silažo, zeleno krmo; trajnice za seno, senože, zeleno krmo, travno moko in semena itd.

Spremenljivke se lahko poljubno spreminjajo v pogojih obravnavane težave. Spremenljivka , katerih koeficienti tvorijo enotni stolpec osnovno. Oblika osnovnih spremenljivk osnova enote sistemov. Spremenljivke, ki niso vključene v osnovo enote, se imenujejo prost.

Skupno število spremenljivk, vključenih v nalogo, je določeno z naravo naloge, posebnimi proizvodnimi pogoji, zmožnostjo zbiranja informacij itd.

Spremenljivke lahko izrazimo v različnih merskih enotah: ha, q, kg, kos, glave itd. Po svoji naravi so spremenljivke razdeljene na glavne, dodatne in pomožne. Glavne spremenljivke vključujejo iskane dejavnosti: industrijo, vrste krme, znamke avtomobilov. Spremenljivke, ki nastanejo pri pretvorbi neenakosti v enačbe, imenujemo dodatne. Lahko pomenijo premalo izkoriščen del virov, presežek desna stran neenakost (če gre za neenakost tipa "ne več"). Pomožne spremenljivke so vključene v nalogo za določitev ocenjenih vrednosti pridobljenih proizvodnih virov, ocenjenih vrednosti kazalnikov gospodarske učinkovitosti proizvodnje.

Dodatne in pomožne spremenljivke imajo vedno enotne koeficiente (+1 ali –1).

Tehnični in ekonomski koeficienti (a ij) pri spremenljivkah v sistemu omejitev so izražene stopnje proizvodnih virov ali stopnja proizvodnje na mersko enoto spremenljivke.

V obeh primerih je potrebno, da tehnični in ekonomski koeficienti natančno ustrezajo načrtovalnemu obdobju, za katerega se težava rešuje. Na primer, če je problem rešen za ekonomsko -matematično analizo proizvodnje za preteklo obdobje, bodo koeficienti izračunani glede na poročane podatke. Če se odločimo za prihodnost, je treba za to perspektivo izračunati koeficiente.

Stopnje porabe virov najpogosteje določajo referenčne knjige, prilagoditi jih je treba ustreznim posebnim pogojem. Razmerje pridelka se izračuna na podlagi načrtovanih pridelkov in produktivnosti živali.

V primerih, ko je treba določiti vnaprej določena razmerja med spremenljivkami, tehnični in ekonomski koeficienti predstavljajo koeficiente sorazmernosti. Na primer delež poljščin v kolobarju ali delež neke krme v skupni krmi itd.

Desna stran omejitev (b i) imenujemo konstante, tj. konstantne vrednosti. Ti vključujejo obseg proizvodnih virov - zemlje, dela, strojev, gnojil, naložb itd. Proizvodne vire je treba določiti ob upoštevanju njihovega dejanskega stanja, pri čemer je nujno upoštevati načrtovalno obdobje. Poleg tega se tisti proizvodni viri, katerih poraba je med letom neenakomerna, izračunajo ne le za celotno leto, ampak tudi za posamezna intenzivna obdobja ali mesece (delovna sredstva).

Proizvodni viri so določeni v različnih enotah: zemljišče - v hektarjih, delovni viri - v delovnih dneh ali v delovnih urah, oprema - v številu premikov strojev, izmenah ali dnevni proizvodnji itd.

Tako določiti razpoložljivost proizvodnih virov ni enostavno. Treba je skrbno analizirati proizvodno dejavnost gospodarstva, porabo delovne sile, zemljišča, tehničnih in drugih virov in šele nato njihov obseg vključiti v omejitve.

Desna stran omejitev ne odraža le količine sredstev, ampak tudi količino proizvodov, proizvedenih na zgornji ali spodnji ravni. Nižja raven je prikazana v primerih, ko je obseg proizvodnje vnaprej znan, manjši od tistega, na katerem kmetija ne bi smela pridelovati, zgornja raven pa ne dovoljuje proizvodnje proizvodov nad določenim obsegom. Te omejitve niso vedno potrebne. Vendar pa skoraj noben problem, ki vključuje opredelitev kombinacije panog, ne mine brez ustreznih omejitev za izdelke, sicer se bo izkazala enostranska rešitev. To je posledica dejstva, da učinkovitost industrije ni enaka.

Pri vseh drugih omejitvah so ničle na desni strani, saj oblikujejo pogoje za proizvodnjo in uporabo izdelkov ali odražajo omejitve sorazmerne komunikacije.

Omejitev Je matematični izraz, ki veže spremenljivke v obliki enakovrednosti in neenakosti. Vse omejitve so oblikovane sistem omejitev naloge. Matematični sistem omejitev označuje pogoje problema. Popolnost refleksije teh pogojev je odvisna od sestave omejitev. Zato je treba pri določanju števila omejitev upoštevati dve okoliščini:

v v nalogi upoštevajte le tiste pogoje, ki resnično omejujejo možnosti proizvodnje;

v preveč omejitev povečuje velikost problema in ga otežuje reševanje

Obstajajo tri vrste omejitev: enakost (=), neenakost tipov, manjša ali enaka (≤), neenakost tipa večja ali enaka (≥). Na primer,

kje jaz = 1, 2, … , m... Označimo spremenljive koeficiente a ij kje indeks jaz- omejitvena številka, indeks j- spremenljivo število, označeni so prosti člani (desna stran omejitev) b i, kazalo jaz- omejitvena številka.

Omejitve prve vrste se imenujejo zgornje omejitve, saj leva stran neenakosti ne more biti višja od določene vrednosti (konstante). Omejitve tretje vrste se imenujejo omejitve od spodaj, saj leva stran neenakosti ne more biti nižja od določene vrednosti (konstante).

Po pomenu lahko vse omejitve razdelimo na glavne, dodatne in pomožne.

Glavne omejitve so - to so tiste, ki se prekrivajo z vsemi ali večino spremenljivk naloge. Praviloma se z njihovo pomočjo odražajo glavni pogoji problema - glede zemlje, dela, krme, hranil, tehnologije itd.

Dodatne omejitve se prekrivajo na delu spremenljivk ali na eni spremenljivki. Te omejitve se uvedejo v primerih, ko je treba omejiti velikost posameznih spremenljivk od zgoraj ali spodaj, na primer ob upoštevanju zahtev po kolobarjenju ali ob upoštevanju fizioloških omejitev nasičenosti prehrane s posameznimi krmami ali njihovimi skupinami. Tako dodatne omejitve odražajo različne dodatne pogoje, ki se pojavijo med simulacijo. Toda vsaka dodatna omejitev zoži obseg svobode izbire. Zato jih je treba v nalogo vnesti previdno, v razumnih mejah in po potrebi.

Pomožne omejitve, praviloma nimajo samostojnega pomena in se v problematiko vnesejo zaradi formalizacije posameznih pogojev. Te vključujejo omejitve, ki vzpostavljajo sorazmerno razmerje med posameznimi spremenljivkami ali njihovimi skupinami.

Ocena spremenljivk v ciljni funkciji (s j) so koeficienti, ki izražajo znesek skupnega prihodka ali stroškov na mersko enoto spremenljivke. Ocena spremenljivke praviloma izraža sprejeto merilo optimalnosti. Predstavi se lahko tako v naravi kot v denarju, tj. stroški na enoto (stroški proizvodnje).

Pogoj za nenegativnost spremenljivk je zapisan v obliki

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

V resničnem življenju proizvodnje se na podlagi pogojev naloge iz tega zapisa strukturnega ekonomsko -matematičnega modela (EMM) sestavi seznam spremenljivk in omejitev, pripravijo se začetne informacije, zgradi se podroben problem EMM, ki je nato se zapiše v obliki matrice (tabele), vnese v računalnik, izračun in analiza rezultatov pa se izvede po ustreznem programu. i = 1, ..., m, (1.5)

j = 1, …, n. (1.6)

Vektor x = (x 1 , x 2 , …, x n), sestavni deli x j ki izpolnjujejo omejitve (1.2) in (1.3) [ali (1.5) in (1.6) v minimalnem problemu] se imenuje sprejemljiva odločitev ali sprejemljiv načrt LP naloge. Zbiranje vseh veljavnih načrtov se imenuje veliko veljavnih načrtov.

Kanonično za obliko problema linearnega programiranja je značilno, da vsebuje objektivno funkcijo, vse omejitve enakost, vse spremenljivke niso negativne.

Vsak problem linearnega programiranja lahko reduciramo na problem linearnega programiranja v kanonični obliki. Če želite to narediti, morate v splošnem primeru zmanjšati problem maksimizacije na problem minimizacije; pojdite od omejitev neenakosti do omejitev enakosti in zamenjajte spremenljivke, ki ne upoštevajo pogoja nenegativnosti.

Pravilo za reduciranje problema linearnega programiranja na kanonično obliko kot sledi:

1) če je v prvotni nalogi potrebno določiti maksimum linearne funkcije, potem spremenite znak in poiščite minimum te funkcije;

2) če je desna stran omejitev negativna, je treba to omejitev pomnožiti z - 1;

3) če med omejitvami obstajajo neenakosti, se z uvedbo dodatnih spremenljivk nenegativnih spremenljivk pretvorijo v enakosti. Na primer dodatne spremenljivke S j v omejitve tipa manjše ali enako (£) se vnese z znakom plus:

Dodatne spremenljivke S j pri tipu omejitve, ki so večje ali enake (≥), se vnesejo z znakom minus:

Za odpravo negativnosti dodatnih spremenljivk - S j uvesti umetne spremenljivke z znakom plus + M j z zelo velikimi vrednostmi.