Splošni pogled na model linearnega programiranja. Oblike linearnih matematičnih modelov in njihova transformacija. Oblikovanje glavnih vrst problemov LP, izgradnja njihovih matematičnih modelov

ZVEZNA AGENCIJA ZA IZOBRAŽEVANJE

FGOU PO "PSKOV KOLEKS GRADBENIŠTVA IN GOSPODARSTVA"

Zadeva "Matematične metode"

Naloga linearno programiranje

Tečajno delo

Študentska skupina 315-PO

Andrejev Dmitrij Aleksandrovič

Vodja tečajnega dela

Vasilyeva Natalia Anatolievna

Pskov 2009

Uvod

Poglavje Ι Linearno programiranje

§ 1 Splošna formulacija problema linearnega programiranja

§ 2 Matematični model problema linearnega programiranja

§ 3 Kanonična oblika problema linearnega programiranja

Poglavje ΙΙ Reševanje težave z metodo Simplex

§ 1 Izjava o problemu

§ 2 Sestavljanje matematičnega modela problema

§ 3 Algoritmi za reševanje problema s preprosto metodo

§ 4 Konstrukcija začetne nosilne rešitve po Gaussovi metodi

§ 5 Rešitev problema

Zaključek

Literatura

Uvod

Trenutno se mnogi problemi načrtovanja in upravljanja v sektorjih nacionalnega gospodarstva ter velik obseg posebnih uporabnih problemov rešujejo z matematičnimi metodami programiranja. Najbolj razvite na področju reševanja optimizacijskih problemov so metode linearnega programiranja. Te metode vam omogočajo, da z zadostno natančnostjo opišete široko paleto nalog komercialnih dejavnosti, kot je načrtovanje prometa; umestitev maloprodajne trgovske mreže mesta; načrtovanje dobave blaga v mesto, okrožje; povezovanje trgovskih podjetij z dobavitelji; organizacija racionalnega prevoza blaga; razporeditev trgovskih delavcev na delovna mesta; organizacija racionalnega naročanja živil; dodelitev virov; naložbeno načrtovanje; optimizacija medsektorskih odnosov; zamenjava komercialne opreme; določitev optimalne ponudbe blaga na omejenem območju; vzpostavitev racionalnega načina delovanja.

Pri problemih linearnega programiranja sta merilo učinkovitosti in funkcije v sistemu omejitev linearna.

Če je v matematičnem programskem problemu časovna spremenljivka in je merilo učinkovitosti izraženo z enačbami, ki opisujejo tok operacij v času, potem je tak problem problem dinamičnega programiranja.

V mnogih ekonomskih modelih lahko razmerje med stalnimi in spremenljivimi dejavniki štejemo za linearno.

Uporaba metod matematičnega programiranja v komercialnih dejavnostih je povezana z zbiranjem potrebnih informacij s strani trgovca, ekonomista, financerja, nato pa skupaj z matematiko postavlja problem. Ker so bile metode matematičnega programiranja že implementirane na računalniku v obliki paketa standardnih programov, je dostop do njih običajno preprost, avtomatiziran in ne predstavlja posebnih težav.

Nato delovanje modela vključuje zbiranje in obdelavo informacij, vnos obdelanih informacij v računalnik, izračune na podlagi razvitih programov urnikov in na koncu izdajo rezultatov izračunov (v obliki, ki je primerna za uporabnike) za njihovo uporabo na področju proizvodnih dejavnosti.

Poglavje Ι Linearno programiranje

§ 1 Splošna formulacija problema linearnega programiranja

Linearno programiranje je veja matematičnega programiranja, ki preučuje metode za reševanje skrajnih problemov, za katere je značilno linearno razmerje med spremenljivkami in linearno ciljno funkcijo. Za reševanje problemov linearnega programiranja se pripravi matematični model problema in izbere metoda rešitve.

Izjavo o problemu komercialne dejavnosti lahko predstavimo v obliki matematičnega modela linearnega programiranja, če je lahko ciljno funkcijo predstavljeno v obliki linearne oblike, razmerje z omejenimi viri pa lahko opišemo s pomočjo linearnega enačbe ali neenakosti. Poleg tega je uvedena dodatna omejitev - vrednosti spremenljivk morajo biti negativne, saj predstavljajo take količine, kot so promet, čas delovanja, stroški in drugi ekonomski kazalniki.

Geometrijska interpretacija ekonomskih problemov omogoča vizualizacijo njihove strukture, prepoznavanje značilnosti in odpiranje načinov za proučevanje kompleksnejših lastnosti. Problem linearnega programiranja z dvema spremenljivkama je vedno mogoče rešiti grafično. Vendar se že v tridimenzionalnem prostoru takšna rešitev zaplete, v prostorih, katerih dimenzija je več kot tri, pa je grafična rešitev na splošno nemogoča. Primer dveh spremenljivk nima posebnega praktičnega pomena, vendar njeno upoštevanje razjasni lastnosti problemov linearnega programiranja, pripelje do ideje o njegovem reševanju, daje geometrijsko jasne načine reševanja in načine njihove praktične izvedbe.

§ 2 Matematični model problema linearnega programiranja

Preden rešimo problem, sestavimo njegov matematični model.

Matematični model je niz razmerij, ki jih sestavljajo linearna ciljna funkcija in linearne omejitve spremenljivke.

Načelo sestavljanja matematičnega modela.

1. Izberite spremenljivke opravil.

Spremenljivke problema so količine

Ki v celoti označujejo gospodarski proces, opisan v nalogi. Običajno je zapisan v obliki vektorja X = () Poleg tega )

2. Ustvarite sistem za omejevanje težave.

Sistem omejitev je niz enačb in neenakosti, ki jih zadovoljujejo spremenljivke problema in ki izhajajo iz omejenih ekonomskih pogojev problema.

V splošen pogled sistem je zapisan kot

3. Določite ciljno funkcijo.

Ciljna funkcija je funkcija Z (X), ki označuje kakovost naloge, katere ekstrem je treba najti. Na splošno je ciljna funkcija zapisana Z (X) =

potem. matematični model je najti spremenljivke problema

izpolnjujejo sistem omejitev:

in pogoj negativnosti

0 (j =), ki zagotavlja skrajnost ciljne funkcije Z (Y) =

Vsak niz vrednosti spremenljivk, ki izpolnjuje sistem omejitev in pogojno nenegativnost, se imenuje dopustna rešitev problema linearnega programiranja.

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

Optimalna rešitev je izvedljiva rešitev problema, pri katerem ciljna funkcija doseže ekstrem.

§ 3 Kanonična oblika problema linearnega programiranja

Matematični model problema mora imeti kanonično obliko.

Če je omejevalni sistem sestavljen samo iz enačbe in vse spremenljivke izpolnjujejo pogoj nenegativnosti, potem ima problem kanonično obliko.

Če ima sistem vsaj eno neenakost ali je katera koli spremenljivka neomejena s pogojem negativnosti, potem ima problem standardno obliko. Če želite nalogo prenesti v kanonično obliko, morate:

preidemo iz neenakosti v enačbo na naslednji način: na levi strani neenakosti uvedemo dodatno spremenljivko s koeficientom (+1) za neenakost (

) in (-1) za neenakost () dodatnim spremenljivkam niso naložene ciljne nenegativnosti, nato pa se nadomesti z razliko dveh nenegativnih spremenljivk, to je: = - (

Splošni pogled na kanonsko obliko:

Poglavje ΙΙ Reševanje težave z metodo Simplex

Enostavna metoda je metoda zaporednega izboljšanja načrta (rešitve), najučinkovitejša in se uporablja za reševanje kakršnega koli problema linearnega programiranja.

Ime metode je iz latinščine simplecx - preprosto zato, ker iz začetnega območja možnih rešitev problema najpreprostejši pogled... Ideje metode je predlagal ruski matematik L. V. Kontarovich. leta 1939, nato pa je to idejo razvil in razvil J. Danzig leta 1949.

Enostavna metoda v končnem številu korakov omogoča iskanje optimalne rešitve ali dokazovanje, da ne obstaja.

§ 1 Izjava o problemu

Podjetje v proizvodnem procesu uporablja 3 vrste strojev: Ι, ІΙ, ІVІ. V tem primeru se porabijo surovine, delovni viri in upoštevajo režijski stroški.

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 negativnosti. Maksimiziranje neke funkcije je enakovredno minimizaciji iste funkcije, sprejete z nasprotnim predznakom, in obratno.

Pravilo za reduciranje problema linearnega programiranja na kanonično obliko je naslednje:

• če je v prvotni težavi potrebno določiti največ linearna funkcija, potem morate spremeniti znak in poiskati minimum te funkcije;
• če je desna stran omejitev negativna, je treba to omejitev pomnožiti z -1;
• če med omejitvami obstajajo neenakosti, se z uvedbo dodatnih negativnih spremenljivk spremenijo v enakovrednosti;
• če je kakšna spremenljivka x j nima omejitev predznakov, se nadomesti (v funkciji cilja in pri vseh omejitvah) z razliko med dvema novimi negativnimi spremenljivkami:
  x 3 = x 3 + - x 3 - , kje x 3 +, x 3 - ≥ 0 .

Primer 1... Zmanjšanje problema linearnega programiranja v kanonično obliko:

min L = 2x 1 + x 2 - x 3;
2x 2 - x 3 ≤ 5;
x 1 + x 2 - x 3 ≥ -1;
2x 1 - x 2 ≤ -3;
x 1 ≤ 0; x 2 ≥ 0; x 3 ≥ 0.

V vsako enačbo sistema omejitev uvedemo izravnalne spremenljivke x 4, x 5, x 6... Sistem bo zapisan v obliki enakovrednosti, v prvi in ​​tretji enačbi sistema omejitev pa spremenljivke x 4, x 6 se vnesejo na levi strani z znakom "+", v drugi enačbi pa spremenljivko x 5 vneseni z znakom "-".

2x 2 - x 3 + x 4 = 5;
x 1 + x 2 - x 3 - x 5 = -1;
2x 1 - x 2 + x 6 = -3;
x 4 ≥ 0; x 5 ≥ 0; x 6 ≥ 0.

Prosti izrazi v kanonični obliki morajo biti pozitivni, za to zadnji dve enačbi pomnožimo z -1:

2x 2 - x 3 + x 4 = 5;
-x 1 - x 2 + x 3 + x 5 = 1;
-2x 1 + x 2 - x 6 = 3.

V kanonski obliki pisanja problemov linearnega programiranja morajo biti vse spremenljivke, vključene v sistem omejitev, negativne. Predpostavimo, da x 1 = x 1 '- x 7 , kje x 1 '' ≥ 0, x 7 ≥ 0 .

Če ta izraz nadomestimo v sistem omejitev in ciljno funkcijo ter spremenljivke zapišemo v naraščajočem vrstnem redu indeksa, dobimo problem linearnega programiranja, predstavljen v kanonični obliki:

L min = 2x 1 '+ x 2 - x 3 - 2x 7;
2x 2 - x 3 + x 4 = 5;
-x 1 '- x 2 + x 3 + x 5 + x 7 = 1;
-2x 1 ' + x 2 - x 6 + 2x 7 = 3;
x 1 '≥ 0; x i ≥ 0, i = 2, 3, 4, 5, 6, 7.

Pogoj optimalnosti za osnovni načrt kanonskega problema LP. Simplex metoda in njena konvergenca.

Enostavna metoda je univerzalno, saj vam omogoča reševanje skoraj vseh problemov linearnega programiranja, napisanih v kanonska oblika.

Ideja o simpleksni metodi dosledno izboljševanje načrta, je v tem, da izhajajoč iz neke začetne rešitve podpore, dosledno usmerjeno gibanje s podpornimi rešitvami problema na optimalno.

Vrednost ciljne funkcije se s tem premikom za naloge ne zmanjša največ.

Ker je število podpornih rešitev končno, potem po končnem številu korakov dobimo optimalno podporno rešitev.

Osnovna negativna rešitev se imenuje referenčna rešitev.

Algoritem metode Simplex

1. Matematični model problema bi moral biti kanonski. Če ni nekanoničen, ga je treba pripeljati v kanonično obliko.

2. Poiščite izvirno rešitev za podporo in jo preverite glede optimalnosti.
Če želite to narediti, izpolnite simpleksno tabelo 1.
Izpolnimo vse vrstice tabele 1. koraka glede na podatke sistema omejitev in ciljne funkcije.

Pri reševanju težav so možni naslednji primeri največ:

1. Če so vsi koeficienti zadnje vrstice tabele simpleksa Dj ³ 0, nato najden

rešitev optimalno.

2 Če je vsaj en koeficient Dj £ 0, vendar za ustrezno spremenljivko ni enotnega pozitivnega ocenjevalnega razmerja, potem je rešitev ustavimo naloge, ker je F (X) ® ¥, torej ciljna funkcija ni omejena na področju izvedljivih rešitev.

Če je vsaj en koeficient zadnje vrstice negativen in za ustrezno spremenljivko obstaja vsaj eno pozitivno ocenjevalno razmerje, potem morate iti na drugo referenčno rešitev.

E če torej je v zadnji vrstici več negativnih koeficientov v stolpec osnovne spremenljivke(Bp) to uvedite spremenljivka ki ustreza največji negativni koeficient v absolutni vrednosti.

5. Če je vsaj en koeficient Dk< 0 , potem k - th stolpec sprejemamo za gostitelja.

6. Za vodilna linija sprejmemo tistega, ki mu ustreza minimalno svoboden odnos članov bi do pozitivnih koeficientov vodilni, k - to stolpec.

7. Element, ki se nahaja na presečišču vodilnih vrstic in stolpca, se imenuje vodilni element.

Prenašanje enostavne tabele 2 :

· osnovni stolpec napolnite z ničlami ​​in enotami

· vodilno vrstico prepišite tako, da jo delite z vodilnim elementom

Če ima vodilna vrstica ničle, se lahko ustrezni stolpci prenesejo v naslednjo preprosto tabelo

· ostale koeficiente najdemo po pravilu "pravokotnika"

Dobili smo novo rešitev za podporo, ki jo preverimo za optimalnost:

Če so vsi koeficienti zadnje vrstice Dj ³ 0, potem najdeno rešitev največ.

Če ne, izpolnite tabelo simpleksa v 8. koraku in tako naprej.

Če je funkcija cilja F (X) zahteva iskanje minimalna vrednost, potem merilo optimalnost problema je ne-pozitivne kvote D j za vse j = 1,2,… n.

Konvergenca simpleksne metode. Degeneracija pri težavah z LP. Najpomembnejša lastnost katerega koli računskega algoritma je konvergenca, to je možnost, da med njegovo uporabo v končnem številu korakov (ponovitev) dobimo želene rezultate (z določeno natančnostjo).

Z lahkoto je razvidno, da lahko težave s konvergenco simpleksne metode potencialno nastanejo na stopnji izbire vrednosti r (postavka 2 ") v primeru, ko so enake minimalne vrednosti razmerja

bo doseženo za več vrstic tabele T (q) hkrati. Nato bo na naslednji ponovitvi stolpec b (β (q + 1)) vseboval nič elementov.

⇐ Prejšnja12345Naslednja ⇒

Datum objave: 2015-11-01; Preberite: 4190 | Kršitev avtorskih pravic strani

Studopedia.org - Studopedia.Org - 2014-2018. (0,002 s) ...

Optimalna rešitev - problem - linearno programiranje

Stran 1

Optimalna rešitev problema linearnega programiranja je dosežena na eni od referenčnih točk, kjer je vsaj k p, - m spremenljivk enakih nič.

Z optimalno rešitvijo problema linearnega programiranja je mogoče najti dopustne spremembe v DS, za katere tudi L ostane nespremenjen.

Če obstaja optimalna rešitev problema linearnega programiranja, potem obstaja osnovna optimalna rešitev.

Dokazano je, da se optimalna rešitev problema linearnega programiranja nahaja na meji območja dopustnih vrednosti nadzorovanih spremenljivk, ki je polieder v n-dimenzionalnem prostoru in je določena s sistemom linearnih omejitev.

Ker je z optimalna rešitev problema linearnega programiranja z m omejitvami, ta rešitev vsebuje največ m strogo pozitivnih spremenljivk.

Dokazano je, da je optimalna rešitev problema linearnega programiranja na meji območja dopustnih vrednosti nadzorovanih spremenljivk, ki je polieder v n-dimenzionalnem prostoru, definiran s sistemom linearnih omejitev. Koordinate vsakega oglišča se določijo z reševanjem sistema enačb (omejitev), ob prisotnosti n nadzorovanih spremenljivk in m omejitev pa je treba rešiti sistem m enačb. Kombinacija Cm n (m - n zelo hitro narašča z naraščajočim tipom, zato iskanje rešitve zahteva zelo veliko izračunov, ki so nedostopni tudi za računalnik.

Torej se v primeru D 1 optimalna rešitev problema linearnega programiranja izkaže za samodejno celo število.

Kot je prikazano v 1. delu, optimalna rešitev problema linearnega programiranja ni nujno integralna, hkrati pa obstaja veliko težav, katerih narava zahteva integralno rešitev. Nekatere od teh težav na prvi pogled niso težave s celoštevilčnim programiranjem, vendar jih je mogoče oblikovati kot take.

Očitno ni vsaka osnovna rešitev optimalna rešitev problema linearnega programiranja. Vendar mora biti optimalna rešitev nedegeneriranega problema vedno osnovna za sistem enačb (VIII, 42), zato je problem iskanja optimalne rešitve našteti le osnovne rešitve sistema enačb ( VIII, 42), med katerimi najdemo optimalnega.

Očitno ni vsaka osnovna rešitev optimalna rešitev problema linearnega programiranja. Vendar mora biti optimalna rešitev nedegeneriranega problema vedno osnovna za sistem enačb (VIII42), zato je problem iskanja optimalne rešitve našteti le osnovne rešitve sistema enačb (VIII42), med katerimi je najde se optimalna.

Po več ponovitvah koraka 3 se lahko pojavijo številne alternativne optimalne rešitve problema linearnega programiranja.

PROBLEM LINEARNEGA PROGRAMIRANJA

To zanko včasih imenujemo neprekinjena degeneracija. Na žalost se ta pojav pogosto pojavlja pri srednjih PI problemih velike razsežnosti. Obstaja tudi veliko primerov problemov z nizkimi dimenzijami (največ 10 spremenljivk in enačb), ki zahtevajo na tisoče ponovitev, da se doseže konvergenca.

V teh primerih se uporablja simpleksna metoda, ki je iterativni (korak za korakom) postopek za določitev optimalne rešitve problema linearnega programiranja. Izračuni po simpleksni metodi se začnejo z določitvijo izvedljive rešitve, nato pa poiščejo druge izvedljive rešitve in preverijo možnosti za njihovo izboljšanje. Prehod iz ene rešitve v drugo se nadaljuje, dokler nove izboljšave niso možne. Standardno računalniških programov ki uporabljajo simpleksno metodo za reševanje problemov upravljanja, ki jih lahko predstavimo kot probleme linearnega programiranja.

Če ima sistem linearnih omejitev posebno strukturo, na primer, če tvori model omrežja, potem lahko pri 2. koraku pri iskanju optimalne rešitve problema linearnega programiranja uporabimo to okoliščino.

Ideja o sorazmerni porazdelitvi je bila izvedena v obliki dvostopenjskega izračunskega algoritma, ki ga je predlagal II Dikin, v katerem se lastnost metode notranje točke v bistvu uporablja za ustvarjanje razmeroma notranje točke niza optimalnih rešitev za problem linearnega programiranja. Ta lastnost pomeni, da so mejne vrednosti v skladu s pogoji neenakosti (2.3.2) - (2.3.4) dosežene le za tiste spremenljivke, ki imajo te mejne vrednosti za katero koli drugo optimalno rešitev.

Strani: 1 2

Grafična metoda za reševanje problema linearnega programiranja

Upoštevajte LPP v standardni obliki za primer dveh spremenljivk:

(10)

Naj bo sistem neenakosti (10) skladen (ima vsaj eno rešitev). Vsaka neenakost tega sistema geometrijsko definira polravnino z mejno črto Pogoji negativnosti opredeljujejo polovice z ustreznimi mejnimi črtami in.

Ker je sistem skladen, pol ravnine kot konveksne množice, ki se sekajo, tvorijo skupen del, ki je konveksna množica in je zbir točk, katerih koordinate vsake so rešitev tega sistema. Zbiranje vseh teh točk se imenuje poligonske rešitve. Lahko je točka, odsek črte, žarek, ravna črta, zaprt poligon, neomejeno poligonalno območje.

Rešitev LPP je geometrijsko iskanje takšne točke poligona rešitve, katere koordinate dajejo največji (najmanjši) vrednosti ciljni funkciji. Poleg tega so vse točke poliedra veljavna rešitev.

Razmislite o t.i raven črta ciljno funkcijo z, to je črta, po kateri ta funkcija prevzame isto fiksno vrednost: ali

Algoritem za reševanje problema linearnega programiranja z grafično metodo (število spremenljivk).

1. Poligonalno območje izvedljivih rešitev na ravnini je zgrajeno v skladu z omejitvami. Nato se konstruira vektorski gradient

ciljno funkcijo z na kateri koli točki območje izvedljivih rešitev.

2. Ravna črta (črta na ravni funkcije z), pravokotno na vektor gradienta, se v primeru največjega problema (in v nasprotni smeri - v primeru minimalnega problema) premika vzporedno s seboj v smeri vektorja gradienta, dokler ne zapusti območja izvedljivih rešitev. Omejitvene točke (ali točke) regije so optimalne točke.

3. Za iskanje koordinat optimalne točke je treba rešiti sistem enačb, ki ustreza ravnim črtam, katerih presečišče tvori to točko.

Oblikovanje glavnih vrst problemov LP, izgradnja njihovih matematičnih modelov

Vrednost ciljne funkcije na tej točki bo optimalna, koordinate točke pa bodo rešitev problema LP .

Primer. Geometrijsko rešite težavo:

Zgradite poligon vseh izvedljivih rešitev OABCD in smerni vektor ciljne funkcije (slika 1). Smer vektorja gradienta označuje smer povečanja ciljne funkcije. Ker je obravnavana težava najti maksimum, premikamo ravno črto pravokotno na vektor v smeri tega vektorja vzporedno s samim seboj, dokler ta ravna črta ne zapusti območja dopustnih rešitev. Na meji regije, v našem primeru na točki Z, in rešitev problema bo. Točka Z je na presečišču ravnih črt in. Zato se njegove koordinate določijo z reševanjem sistema teh enačb v enačbo:

od kod tj. točka Z ima koordinate (6, 4).

Največja (največja vrednost ciljne funkcije) je: Odgovor: z optimalno rešitvijo, tj. največji dobiček je mogoče doseči s proizvodnjo 6 enot prvega in 4 enot drugega izdelka.

UVOD

Sodobna ekonomska teorija, tako na mikro - kot na makro ravni, vključuje kot naraven, nujen element matematični modeli in metode. Uporaba matematike v ekonomiji omogoča, prvič, izpostaviti in formalno opisati najpomembnejše, pomembne odnose med ekonomskimi spremenljivkami in objekti: preučevanje tako zapletenega predmeta zahteva visoko stopnjo abstrakcije. Drugič, iz jasno oblikovanih začetnih podatkov in razmerij je mogoče uporabiti deduktivne metode za pridobitev zaključkov, ki so v enaki meri kot predmetni pogoji primerni za predmet, ki se preučuje. Tretjič, matematične in statistične metode omogočajo induktivno pridobivanje novega znanja o objektu: oceniti obliko in parametre odvisnosti njegovih spremenljivk, ki v največji meri ustrezajo razpoložljivemu opazovanju. Četrtič, uporaba jezika matematike omogoča natančno in kompaktno predstavitev določb ekonomske teorije, oblikovanje njenih konceptov in zaključkov.

Matematične modele, ki se uporabljajo v ekonomiji, lahko razdelimo v razrede glede na številne značilnosti, povezane z značilnostmi modeliranega predmeta, namenom modeliranja in uporabljenimi orodji: mikro- in makroekonomski modeli, teoretični in ravnotežni, statistični in dinamični.

Bistvo optimizacijskih metod je v tem, da se na podlagi razpoložljivosti določenih virov izbere način njihove uporabe (distribucije), ki zagotavlja največji (minimalni) kazalnik, ki nas zanima.

Vsi glavni oddelki matematičnega programiranja (načrtovanja) se uporabljajo kot optimizacijske metode v ekonomiji.

Matematična disciplina, ki se ukvarja s preučevanjem skrajnih (največjih ali minimalnih) problemov nadzora, načrtovanja in razvoja metod za njihovo rešitev matematično programiranje.

Na splošno je matematična formulacija ekstremnega problema sestavljena iz določanja največje ali najmanjše vrednosti ciljne funkcije
pod pogojem ,

kjer in so dane funkcije in so nekaj realnih števil.

Odvisno od vrste ciljne funkcije in omejitev je matematično programiranje razdeljeno na linearno in nelinearno. Večina

preučeni del matematičnega programiranja je linearno programiranje.

Opredelitev.

Problem linearnega programiranja (stran 1 od 3)

Linearno programiranje - znanost o metodah uporabe in iskanja skrajnih (največjih in najmanjših) vrednosti linearne funkcije, katerih neznanke so podvržene linearnim omejitvam.

Ta linearna funkcija se imenuje cilj, omejitve v obliki enačb ali neenakosti pa sistem omejitev.

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

Razmislimo o nekaterih težavah linearnega programiranja (LPP).

1. Problem rabe virov (problem načrtovanja proizvodnje).

Za izdelavo različnih izdelkov podjetje uporablja tri različne vrste surovin. Stopnje porabe surovin za proizvodnjo enega izdelka , pa tudi skupno število

surovine vsake vrste, ki jih lahko uporablja podjetje, so navedene v tabeli.

Naredite načrt za proizvodnjo proizvodov, v katerem so skupni stroški vseh izdelkov, ki jih proizvaja podjetje, največji.

Zgradimo matematični model tega problema.

Označimo skozi želeno proizvodnjo izdelkov, skozi - izdelke,

stranski izdelki.

Ker obstajajo stroški za vsako vrsto surovine, potem lahko ugotovimo skupne stroške vsake vrste surovine za izdelavo vseh izdelkov. Iz tabele izhaja, da bo skupna količina surovin tipa I, II -
,

III -
... In ker obstajajo zaloge surovin, zato skupna količina surovin vsake vrste ne sme biti večja od skupne količine surovin, tj.

dobimo naslednji sistem neenakosti

(1)

Ekonomsko gledano spremenljivke lahko sprejme samo negativne vrednosti:

(2)

Stroški vseh izdelkov te vrste bodo – – V skladu s tem bodo skupni stroški izdelkov, ki jih proizvaja podjetje (3)

Moramo najti to funkcijo. Tako je med vsemi negativnimi rešitvami sistema (1) treba najti tisto, za katero ima funkcija (3) svojo največjo vrednost.

To nalogo je mogoče zlahka posplošiti na primer sproščanja vrst izdelkov z uporabo vrst surovin (virov).

Označimo z - število enot proizvodov, načrtovanih za proizvodnjo, - zaloga virov - vrsta, - specifična poraba virov za proizvodnjo - ih izdelkov. - dobiček od prodaje enote izdelka - prva vrsta.

Potem bo ekonomsko -matematični model problema rabe virov v splošnem okolju dobil obliko: poiščite takšen načrt
izhod, ki ustreza osnovnemu sistemu omejitev

dodatni sistem omejitev

v katerem je ciljna funkcija

prevzame največjo vrednost.

Komentiraj.Če želite sestaviti matematični model LPP, morate:

- uvesti označevanje spremenljivk;

- na podlagi cilja ekonomskih raziskav pripraviti ciljno funkcijo;

- ob upoštevanju omejitev pri uporabi ekonomskih kazalnikov problema in njihovih količinskih zakonov zapišite sistem omejitev.

Reševanje problemov linearnega programiranja temelji na konceptih analitične geometrije v dimenzionalnem vektorskem prostoru.

Prinašanje splošnega LPP v kanonično obliko.

Splošno stališče LPP je naslednje:

(1)

(2)

(3)

kjer je relacija (1) ciljna funkcija, (2) sistem osnovnih omejitev, (3) sistem dodatnih omejitev.

Oblika (2) in (3) je v obliki celoten sistem omejitve.

Zmanjšanje sistema osnovnih omejitev na kanonično obliko se izvede z uvedbo dodatnih negativnih spremenljivk s koeficienti "+1", če so neenakosti oblike, in "-1", če so neenakosti oblike , na levi strani neenakosti. Dodatne spremenljivke vstopijo v ciljno funkcijo z ničelnimi koeficienti.

Opredelitev ... LPP se imenuje kanonično definiran, če je njegov sistem osnovnih omejitev predstavljen z enačbami.

Opredelitev. LPP se imenuje dano v standardni obliki kanonične oblike, če so izpolnjeni naslednji pogoji:

1) sistem osnovnih omejitev predstavljajo enačbe in so vse linearno neodvisne;

2) število enačb je manjše od števila spremenljivk;

3) se rešuje problem minimiziranja ciljne funkcije;

4) desne strani sistema osnovnih omejitev niso negativne;

5) vse spremenljivke so tudi negativne.

Pri večini metod za reševanje problemov linearnega programiranja se domneva, da je sistem omejitev sestavljen iz enačb in naravnih pogojev za nenegativnost spremenljivk.

Pri sestavljanju modelov številnih težav pa se omejitve oblikujejo predvsem v obliki sistema neenakosti, zato je treba biti sposoben preiti iz sistema neenakosti v sistem enačb.

To je mogoče storiti na naslednji način:

Vzemimo linearno neenakost

in levi strani dodamo neko količino, tako da se neenakost spremeni v enakost

Poleg tega ta vrednost ni negativna.

Primer

Problem linearnega programiranja pripeljimo v kanonično obliko:

Rešitev:

Naj se obrnemo na problem iskanja maksimuma ciljne funkcije.

V ta namen spremenimo znake koeficientov ciljne funkcije.

Za pretvorbo druge in tretje neenakosti sistema omejitev v enačbe uvedemo dodatne negativne spremenljivke x 4 x 5 (pri matematičnem modelu je ta operacija označena s črko D).

Spremenljivka x 4 se vnese na levi strani druge neenakosti s predznakom "+", saj ima neenakost obliko "≤".

Spremenljivka x 5 se vnese na levi strani tretje neenakosti z znakom "-", saj ima neenakost obliko "≥".

Spremenljivke x 4 x 5 se vnesejo v funkcijo cilja s koeficientom. enako nič.

Nalogo zapišemo v kanonski obliki:

SIMPLEX METODA REŠEVANJA PROGRAMOV LINEARNEGA PROGRAMIRANJA

Ta metoda je metoda namenskega naštevanja podpornih rešitev problema linearnega programiranja. V končnem številu korakov omogoča bodisi iskanje optimalne rešitve bodisi ugotovitev, da optimalne rešitve ni.

Algoritem simpleksne metode za reševanje problemov linearnega programiranja

Če želite težavo rešiti s preprosto metodo, morate narediti naslednje:

1. Prenesite težavo v kanonično obliko

Tema 8. Linearno programiranje

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 za edinstvenost 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

Primer reševanja problema s preprosto metodo

Primer 1

Težavo rešite s preprosto metodo:

Zmanjšajte vrednost funkcije

F = 10 × 1 - 4 × 3 max

Ob prisotnosti omejitev v obliki neenakosti

Problem pripeljemo v kanonično obliko.

Če želite to narediti, na levi strani prve omejitve neenakosti uvedemo dodatno spremenljivko x 5 s koeficientom +1. Spremenljivka x 5 je vključena v funkcijo cilja s koeficientom nič (torej ni vključena).

Dobimo:

F = 10 × 1 - 4 × 3 + 0 ∙ x5 max

Ob prisotnosti omejitev v obliki neenakosti

Poiščite prvotno rešitev za podporo. Za to so proste (nerazrešene) spremenljivke enake nič x1 = x3 = 0.

Dobimo referenčno rešitev X1 = (0,0,0,5,9 / 15,6) z enoto osnove B1 = (A4, A5, A6).

Izračunamo ocene razširitev vektorjev pogojev na podlagi podporne rešitve po formuli:

Δ k = C b X k - c k

· C b = (s 1, s 2, ..., s m) - vektor koeficientov ciljne funkcije z osnovnimi spremenljivkami

X k = (x 1k, x 2k, ..., x mk) je vektor raztezanja ustreznega vektorja A na osnovo referenčne rešitve

· С к - koeficient ciljne funkcije pri spremenljivki х к.

Ocene vektorjev, vključenih v osnovo, so vedno nič.

Podporna rešitev, koeficienti razširitve in ocene razširitev vektorjev pogojev na podlagi podporne rešitve so zapisani v simpleksni tabeli:

Nad tabelo so za lažje izračunavanje ocen zapisani koeficienti ciljne funkcije. Prvi stolpec "B" vsebuje vektorje, vključene v osnovo referenčne raztopine. Vrstni red pisanja teh vektorjev ustreza številkam dovoljenih neznank v enačbah omejitev. Drugi stolpec tabele "C b" beleži koeficiente ciljne funkcije z osnovnimi spremenljivkami v istem vrstnem redu. S pravilnim umeščanjem koeficientov ciljne funkcije v stolpec "C b" so ocene enotnih vektorjev, vključenih v osnovo, vedno enake nič.

Zadnja vrstica tabele z ocenami Δ k v stolpcu "A 0" beleži vrednosti ciljne funkcije na referenčni rešitvi Z (X 1).

Začetna podporna rešitev ni optimalna, saj so pri največjem problemu ocene Δ 1 = -2, Δ 3 = -9 za vektorja A1 in A3 negativne.

V skladu z izrekom o izboljšanju podporne rešitve, če ima pri največjem problemu vsaj en vektor negativno oceno, je mogoče najti novo podporno rešitev, na kateri bo vrednost ciljne funkcije večja.

Ugotovimo, kateri od obeh vektorjev bo privedel do večjega povečanja ciljne funkcije.

Prirastek ciljne funkcije najdemo po formuli:

Izračunamo vrednosti parametra θ 01 za prvi in ​​tretji stolpec po formuli:

Dobimo θ 01 = 6 z l = 1, θ 03 = 3 z l = 1 (tabela 26.1).

Pri vnosu prvega vektorja v osnovo poiščite prirastek ciljne funkcije

ΔZ 1 = - 6 * ( - 2) = 12,

in tretji vektor ΔZ 3 = - 3 * ( - 9) = 27.

Zato je za hitrejši približek optimalni rešitvi treba v osnovo nosilne rešitve vnesti vektor A3 namesto prvega vektorja osnove A6, saj je v prvi vrstici dosežen minimum parametra θ 03 (l = 1).

Izvedemo Jordanovo transformacijo z elementom X13 = 2, dobimo drugo nosilno rešitev

X2 = (0,0,3,21,42,0)

z osnovo B2 = (A3, A4, A5).

(tabela 26.2)

Ta rešitev ni optimalna, saj ima vektor A2 negativno oceno Δ2 = - 6.

Za izboljšanje rešitve je treba v osnovo podporne raztopine vnesti vektor A2.

Določite število vektorja, ki izhaja iz osnove. Če želite to narediti, izračunajte parameter θ 02 za drugi stolpec, ki je enak 7 za l = 2.

Zato iz osnove izpeljemo drugi bazični vektor A4.

Izvedemo Jordanovo transformacijo z elementom x 22 = 3, dobimo tretjo nosilno rešitev

X3 = (0.7.10.0.63.0)

B2 = (A3, A2, A5) (tabela 26.3).

Ta rešitev je edina optimalna, saj je za vse vektorje, ki niso vključeni v osnovo ocene, pozitiven

Δ 1 = 7/2, Δ 4 = 2, Δ 6 = 7/2.

Odgovor: max Z (X) = 201 pri X = (0,7,10,0,63).

Prejšnja123456789 Naslednja ⇒

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) so te dodatne spremenljivke, kot bi morale biti, negativne.

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

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, pri čemer bomo odpravili osnovne spremenljivke in 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:

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

LINEARNI MODEL PROGRAMIRANJA

1 Matematični opis modela linearnega programiranja

2 Metode za izvajanje modelov linearnega programiranja

3 Problem dvojnega linearnega programiranja

Model linearnega programiranja(LP) poteka, če so v preučenem sistemu (objektu) omejitve spremenljivk in ciljna funkcija linearno.

Modeli LP se uporabljajo za reševanje dveh glavnih vrst uporabljenih problemov:

1) optimalno načrtovanje na vseh področjih človekove dejavnosti - družbeni, gospodarski, znanstveni, tehnični in vojaški. Na primer z optimalnim načrtovanjem proizvodnje: razporeditev finančnih, delovnih in drugih virov, dobava surovin, upravljanje zalog itd.

2) transportni problem (iskanje optimalnega načrta za različne vrste prevoza, optimalen načrt za razdeljevanje različnih sredstev na predmete za različne namene itd.)

MATEMATIČNI OPIS LINEARNEGA MODELA PROGRAMIRANJA

Poiskati je treba negativne vrednosti spremenljivk

izpolnjevanje linearnih omejitev v obliki enakovrednosti in neenakosti

,

kje - podane številke,

in zagotavljanje ekstrema linearne ciljne funkcije

,

kje so podane številke, ki je zapisana kot

Veljavna rešitev kateri koli niz se pokliče izpolnjujejo pogoje.

Področje izvedljivih rešitev- nabor vseh izvedljivih rešitev.

Optimalna rešitev
, za kar .

Opombe

1. Navedeni model LP je splošno... Razlikovati tudi standard in kanonski oblike modelov LP.

2... Pogoji obstoja Izvajanje modela LP:

- nabor izvedljivih rešitev ni prazen;

- ciljna funkcija omejeno (vsaj od zgoraj pri iskanju maksimuma in od spodaj pri iskanju minimuma).

3. LP temelji na dveh izrekih

Izrek 1. Veliko G definirano s sistemom omejitev oblike, je konveksna zaprta množica ( konveksni polieder z vogalnimi točkami - vrhovi.)

Izrek 2. Linearna oblika definirano na konveksnem politopu

j=1,2,…,s

i = s+ 1, s + 2, ..., m,

doseže ekstrem na enem od točkov tega poliedra.

Ta izrek se imenuje ekstremni izrek linearne oblike.

Po Weierstrassovem izreku je optimalna rešitev edinstvena in je globalni ekstrem.

Obstaja splošen analitični pristop k implementaciji modela LP - simpleksna metoda. Pri reševanju problemov linearnega programiranja pogosto ni rešitve. To se zgodi iz naslednjih razlogov.

Naj ponazorimo prvi razlog s primerom

Iz tega razloga pravijo, da so omejitve nezdružljive. Območje izvedljivih rešitev je prazen niz.

Drugi razlog komentira naslednji primer:

V tem primeru območje izvedljivih rešitev ni omejeno od zgoraj. Področje dopustnih rešitev ni omejeno.

Sledimo tradicijam linearnega programiranja, dajmo problemu LP ekonomsko interpretacijo. Naj nam bodo na voljo m vrste virov. Število vrst vira j enako. Ti viri so potrebni za proizvodnjo n vrste blaga. Količino tega blaga označimo s simboli oz. Enota vrste predmeta jaz stroški. Proizvodnja vrste blaga jaz je treba omejiti na vrednosti oz. Za proizvodnjo enote blaga jaz vrsta vira se porabi j... Takšen načrt proizvodnje blaga je treba določiti ( ), tako da so njihovi skupni stroški minimalni.

Problemi linearnega programiranja, ki se uporabljajo za optimizacijo delovanja resničnih objektov, vsebujejo veliko število spremenljivk in omejitev. To onemogoča njihovo reševanje. grafične metode... Z velikim številom spremenljivk in omejitev se uporabljajo algebrske metode, ki temeljijo na iterativnih računskih postopkih. V linearnem programiranju je bilo razvitih veliko algebrskih metod, ki se med seboj razlikujejo po metodah konstruiranja začetne izvedljive rešitve in pogojih za prehod iz ene iteracije v drugo. Vse te metode pa temeljijo na splošnih teoretičnih načelih.

Splošnost osnovnih teoretičnih določb vodi do dejstva, da so algebrske metode za reševanje problemov linearnega programiranja v marsičem podobne. Skoraj vsak od njih zahteva predhodno redukcijo problema linearnega programiranja na standardno (kanonično) obliko.

Algebrske metode za reševanje problema LP se začnejo z zmanjševanjem na standardna (kanonska) oblika:

,

,

jaz=1,..,n;j=1,..,m.

Vsak problem linearnega programiranja se lahko zmanjša na standardno obliko. Primerjava splošnega modela s kanoničnim modelom nam omogoča, da sklepamo, da je za zmanjšanje problema LP na standardno obliko treba najprej preiti iz sistema neenakosti v enakosti in, drugič, preoblikovati vse spremenljivke, tako da niso negativne.

Prehod na enakosti se izvede z dodajanjem na levo stran omejitev nenegativne preostale spremenljivke za neenakosti tipa in odštevanjem od leve strani nenegativne redundantne spremenljivke za neenakosti tipa. Na primer neenakost se ob prehodu v standardno obliko pretvori v enakost , neenakost - v enakost ... Poleg tega sta preostala in odvečna spremenljivka negativni.

Predpostavlja se, da je desna stran neenakosti nenegativna. V nasprotnem primeru je to mogoče doseči z množenjem obeh strani neenakosti z "-1" in spreminjanjem njenega znaka v nasprotno.

Če v izvirnem problemu linearnega programiranja spremenljivka ni omejena z znakom, jo ​​lahko predstavimo kot razliko dveh nenegativnih spremenljivk , kje .

Pomembna značilnost spremenljivk je, da lahko za vsako dopustno rešitev le ena od njih sprejme pozitivno vrednost. To pomeni, da če , potem in obratno. Zato ga lahko obravnavamo kot preostale, vendar - kot odvečne spremenljivke.

Primer Naj bo dan problem linearnega programiranja:

,

.

Treba ga je pripeljati v standardni obrazec. Upoštevajte, da ima prva neenakost izvirnega problema znak, zato je treba vanj vnesti preostalo spremenljivko. Kot rezultat dobimo.

Druga neenakost ima predznak in za pretvorbo v standardni obrazec je potrebna uvedba odvečne spremenljivke, ki izvaja to operacijo, dobimo.

Poleg tega spremenljivka ni omejena z znakom. Zato jo je treba tako v funkciji cilja kot v obeh omejitvah nadomestiti z razliko ... Po zamenjavi dobimo linearni programski problem v standardni obliki, ki je enakovreden prvotnemu problemu:

.

Problem linearnega programiranja, zapisan v standardni obliki, je problem iskanja ekstrema ciljne funkcije na množici vektorjev, ki so rešitve sistema linearnih enačb ob upoštevanju pogojev nenegativnosti. Kot je znano, sistem linearnih enačb morda nima rešitev, ima edinstveno rešitev ali ima neskončen nabor rešitev. Optimizacija ciljne funkcije je možna le, če sistem ima neskončno veliko rešitev. Sistem linearnih enačb ima neskončen niz rešitev, če je skladen (rang glavne matrike je enak rangu razširjene) in če je rang glavne matrice manjši od števila neznanka.

Naj bo rang matrice omejevalnega sistema enak m... To pomeni, da ima matrika vsaj eno manjšo m vrstni red ni enak nič. Brez izgube splošnosti lahko domnevamo, da se minor nahaja v zgornjem levem kotu matrice. To je vedno mogoče doseči s spremembo oštevilčevanja spremenljivk. Ta ničelni rang minor m običajno ga imenujemo osnovni. Naredimo sistem prvih m enačbe sistema, ki jih zapišemo na naslednji način:

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

Najenostavnejši so tako imenovani linearni deterministični modeli. Določeni so v obliki linearne oblike nadzornih spremenljivk ( NS):

W = a 0 + a 1 x 1 + … + a k x k

ob linearne omejitve take vrste

b 1 j x 1 + b 2 j x 2 + … + b kj x k ³ b j , j = 1,…, q 1 ;

c 1 j x 1 + c 2 j x 2 + … + c kj x k = c j , j = 1,…, q 2 ;

d 1 j x 1 + d 2 j x 2 + … + d kj x k £ d j , j = 1,…, q 3 .

Skupno število omejitev m = q 1 + q 2 + q 3 lahko presega število spremenljivk (m> k). Poleg tega se običajno uvede pogoj za pozitivnost spremenljivk ( x i ³ 0).

Odzivna površina linearnega modela je hiperplan... Na primer, razmislite o linearnem modelu dveh spremenljivk naslednje oblike:

W =–2x 1 –3x 2 (2.2)

pod naslednjimi omejitvami

(2.3)

2x 1 + 3x 2 18 £;

x 1 – 4x 2 £ 4;

–2x 1 + x 2 £;

NS 1 ³ 0; x 2 ³ 0.

Obseg veljavnih vrednosti (obseg definicije) OABCD za model (2.2) tvorijo omejitve (2.3) (slika 2.2). Odzivna površina je raven poligon OA "B" C "D"(slika 2.2, b).

Za določeno razmerje omejitev je niz možnih rešitev lahko odsoten (prazen). Primer takega niza je prikazan na sl. 2.3. Neposredno AS in Sonce omejite območje dovoljenih vrednosti od zgoraj. Tretja omejitev odreže območje dovoljenih vrednosti od dna ravne črte AB. Tako ni skupnega območja, ki bi zadovoljilo vse tri omejitve.

Linearni modeli so precej preprosti in zato po eni strani pomenijo znatno poenostavitev naloge, po drugi strani pa omogočajo razvoj enostavnih in učinkovite metode rešitve.

Pri preučevanju DLA se linearni modeli redko uporabljajo in skoraj izključno za približen opis težav.

Linearne modele lahko uporabimo za postopno približevanje nelinearnih modelov (linearizacija problema). Ta tehnika je še posebej učinkovita pri preučevanju majhnih površin preiskovanega prostora. Predstavitev posameznih odsekov nelinearne odzivne površine z linearnim modelom je osnova velike skupine optimizacijskih metod, tako imenovanih metod z linearno taktiko.

Študija linearnih modelov ni težka. Zlasti vpliv vsake spremenljivke na značilnosti modela oblike

W = a 0 + a 1 x 1 + a 2 x 2 + …+ a k x k

podano s svojimi koeficienti:

, jaz = 1,…, k.

Za iskanje optimalnega linearnega modela W opt razvil učinkovito preprosto metodo.

Najenostavnejši stroški se včasih zmanjšajo na linearne, kar velja za skupek nastalih stroškov.

Primer takšnega modela je klasika model stroškov prevoza (transportni problem)(Slika 2.4).

Tukaj je k proizvodnih mestih
(jaz = 1,…, k) in m točke porabe
(j = 1,…, m) nekega izdelka. Količina proizvedenega izdelka v vsakem k proizvodne točke so enake a i; količina potrebnega izdelka v vsakem od m točke porabe so enake b j.

Enakost celotne proizvodnje in porabe se predvideva:

Količina prepeljanega izdelka iz jaz-to proizvodno mesto v j-na točka porabe je enaka x ij; stroški prevoza enote tega izdelka - z ij.

Skupni stroški prevoza Z Podan je S linearni model:

pod naslednjimi omejitvami

Linearni modeli vključujejo tudi modele v obliki linearnih diferencialnih enačb (navadni ali delni derivati).

Linearna navadna diferencialna enačba n-naročilo ima obliko

Začetni pogoji so zapisani kot

Linearna parcialna diferencialna enačba ima obliko

Model, podan v obliki delne diferencialne enačbe, vključuje začetne in robne pogoje (pogoje na meji področja opredelitve funkcije F ( t)).

2.3. Študija najpreprostejšega matematičnega modela
delovanje plinskoturbinskega motorja

Plinskoturbinski motor (GTE) je glavna elektrarna sodobnih letal.

Diagram GTE ima obliko, prikazano na sl. 2.5.

Tukaj 1 - vstopni difuzor; 2 - kompresor; 3 - zgorevalna komora; 4 - turbina;
5 - izhodna šoba.

Delovni cikel GTE vključuje naslednje faze:

1) Prihod s hitrostjo V pretok zraka skozi difuzor vstopi v kompresor.

2) Kompresor, ki se vrti na isti gredi s turbino, stisne zrak, ki vstopi v zgorevalno komoro.

3) Gorivo (kerozin) se nenehno vbrizgava v zgorevalno komoro, ki se zmeša s stisnjenim zrakom.

4) Plin, ki nastane pri zgorevanju, vstopi v turbino, kar jo pospeši do hitrosti W.

5) Pri tej hitrosti se plin vrže v šobo skozi šobo.

Zaradi dejstva da W > V, nastane vlečna sila R ki letalu omogoča letenje v ozračju.

Spreminjanje potiska se izvede s spreminjanjem hitrosti vbrizgavanja goriva v zgorevalno komoro s premikanjem gumba za upravljanje motorja (plina). Premik potiska plina do določenega kota d plina izvede pilot ročno ali s pomočjo aktuatorja v skladu s signali ACS med letom. Povečanje vrednosti d plina povzroči povečanje moči R, zmanjšanje pa je zmanjšanje te sile.

GTE je kompleksen tehnični sistem, v katerem poteka veliko fizikalnih in kemičnih procesov. Motor je opremljen z vsemi vrstami naprav za avtomatizacijo, sistemi za obračanje in hlajenje turbinskih lopatic itd. Seveda bo tudi matematični opis delovanja GTE precej okoren, vključno s sistemi delnih diferencialnih enačb, navadnimi diferencialnimi enačbami, transcendentalnimi funkcijami, algoritmi digitalnega krmilnega sistema motorja. Takšni modeli se uporabljajo pri načrtovanju plinskoturbinskega motorja.

Za reševanje težav z nadzorom leta se uporablja enostavnejši model GTE, ki je odvisen od sile potiska R od kota d plina, odstopanje plina. Postopek spreminjanja vlečne sile opisuje navaden diferencialna enačba prijazno:

, (2.11)

kjer je t> 0 časovna konstanta motorja, ki je poleg konstrukcijskih značilnosti odvisna tudi od temperature okolice, njegove vlažnosti in drugih zunanjih dejavnikov; k[kg / deg] - koeficient sorazmernosti.

Začetni pogoj za enačbo (2.11) je zapisan kot

R(0) = R 0 . (2.12)

Tako je enačba (2.11) skupaj z začetnim pogojem (2.12) enaka najpreprostejši matematični model delovanja GTE, zapisan v obliki navadne diferencialne enačbe 1naročilo.

Za določitev razmerja stranic k uporabljeni kalibracijski grafi odvisnosti potiska od kota vrtenja dušilke, zgrajeni na podlagi eksperimentalnih podatkov. Tangenta naklona grafa je enaka želenemu koeficientu.

Integracija enačbe (2.11) z začetnim pogojem (2.12) nam omogoča, da ugotovimo, kako se sila potiska spreminja v času (slika 2.6).

Ko se plin odklopi, se potiska R poveča in nato stabilizira pri določeni mejni vrednosti, t.j. GTE je inercijski objekt.

Meja vlečne sile dobimo iz (2.11), ko je hitrost njegove spremembe enaka nič:

. (2.13)

Trajanje dviga odvisna od vrednosti časovne konstante motorja t. Postopek velja za stabilen, kadar t = t usta, ko potisk vstopi v tako imenovani petodstotni hodnik mejne vrednosti sile potiska (slika 2.6). Več kot je t, bolj inercijski je motor in zato bolj t usta

Na sl. 2.7 prikazuje obnašanje potisne sile kot kota odklona dušilke pri t = 0,5.

Sila potiska med vzletom, ko se plin odkloni za 10 °, v tretji sekundi doseže stabilno stanje in doseže 3390 kg. Deset sekund po vzletu, ko je plin odklonjen za 20 °, je sila potiska nastavljena na 6780 kg, po nadaljnjih desetih sekundah, ko se plin odkloni za 30 °, pa potisk nastavimo na 10170 kg. Mejna vrednost vlečne sile je
14270 kg.

Podobne informacije.

Osnovni koncepti modeliranja

V procesu človekove dejavnosti se razvijajo ideje 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 so nedostopni za neposredno opazovanje in raziskovanje. 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 pogoja negativnosti 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 formulacija 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 v 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; trajne trave 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 enota osnove 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. Dodatne spremenljivke imenujemo spremenljivke, ki nastanejo v procesu pretvorbe neenakosti v enačbe. 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, se bodo koeficienti izračunali 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ž 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, kapitalskih 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, ne izračunajo le za celotno leto, ampak tudi za posamezna intenzivna obdobja ali mesece (delovna sredstva).

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

Tako ugotavljanje razpoložljivosti 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 virov, temveč tudi obseg proizvodnje 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 osnovni 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 območje 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. Lahko je predstavljena 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 zapisano v obliki matrice (tabele), vneseno v računalnik in po ustreznem programu se izvede izračun in analiza rezultatov. i = 1, ..., m, (1.5)

j = 1, …, n. (1.6)

Vektor x = (x 1 , x 2 , …, x n), komponente 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 negativnosti.

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

1) če je v prvotni nalogi potrebno določiti maksimum linearne funkcije, je treba znak spremeniti in poiskati minimum te funkcije;

2) če je pri omejitvah desna stran 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.