Celkový pohled na model lineárního programování. Formy lineárních matematických modelů a jejich transformace. Formulace hlavních typů úloh LP, konstrukce jejich matematických modelů

FEDERÁLNÍ VZDĚLÁVACÍ AGENTURA

FGOU PO "PSKOV COLLEGE OF CONSTRUCTION AND ECONOMY"

Předmět „Matematické metody“

Úkol lineární programování

Práce v kurzu

Studentská skupina 315-PO

Andreev Dmitrij Alexandrovič

Vedoucí kurzu

Vasilyeva Natalia Anatolyevna

Pskov 2009

Úvod

Kapitola Ι Lineární programování

§ 1 Obecná formulace problému lineárního programování

§ 2 Matematický model úlohy lineárního programování

§ 3 Kanonická forma problému lineárního programování

Kapitola ΙΙ Řešení problému pomocí jednoduché metody

§ 1 Prohlášení o problému

§ 2 Sestavení matematického modelu úlohy

§ 3 Algoritmy pro řešení problému simplexovou metodou

§ 4 Konstrukce počátečního řešení podpory Gaussovou metodou

§ 5 Řešení problému

Závěr

Literatura

Úvod

V současné době je mnoho problémů plánování a řízení v sektorech národního hospodářství, stejně jako velký objem konkrétních aplikovaných problémů, řešeno metodami matematického programování. Nejrozvinutější v oblasti řešení optimalizačních problémů jsou metody lineárního programování. Tyto metody vám umožňují s dostatečnou přesností popsat širokou škálu úkolů komerčních aktivit, jako je plánování obratu; umístění maloobchodní sítě města; plánování dodávky zboží do města, okresu; připojení obchodních podniků k dodavatelům; organizace racionální přepravy zboží; distribuce pracovníků obchodu na pozice; organizace racionálního nákupu potravin; přidělení zdrojů; investiční plánování; optimalizace meziodvětvových vztahů; výměna komerčního vybavení; stanovení optimálního sortimentu zboží v omezené oblasti; vytvoření racionálního provozního režimu.

V problémech lineárního programování je kritérium účinnosti a funkce v systému omezení lineární.

Pokud v problému matematického programování existuje časová proměnná a kritérium účinnosti je vyjádřeno rovnicemi popisujícími tok operací v čase, pak je takový problém problémem dynamického programování.

V mnoha ekonomických modelech lze vztah mezi konstantními a variabilními faktory považovat za lineární.

Využití metod matematického programování v komerčních aktivitách je spojeno se shromažďováním potřebných informací obchodníkem, ekonomem, finančníkem a následným stanovením problému spolu s matematikou. Protože metody matematického programování již byly na počítači implementovány ve formě balíčku standardních programů, přístup k nim je obvykle jednoduchý, automatizovaný a nepředstavuje žádné zvláštní potíže.

Poté operace modelu zahrnuje sběr a zpracování informací, zadávání zpracovaných informací do počítače, výpočty na základě vyvinutých plánovacích programů a nakonec vydávání výsledků výpočtů (ve formě vhodné pro uživatele) pro jejich využití v oblasti výrobních činností.

Kapitola Ι Lineární programování

§ 1 Obecná formulace problému lineárního programování

Lineární programování je odvětví matematického programování, které studuje metody řešení extrémních problémů, pro které je charakteristický lineární vztah mezi proměnnými a lineární objektivní funkce. Pro řešení problémů lineárního programování je sestaven matematický model úlohy a je vybrána metoda řešení.

Prohlášení o problému komerční činnosti lze prezentovat ve formě matematického modelu lineárního programování, pokud lze objektivní funkci reprezentovat formou lineární formy a vztah k omezeným zdrojům lze popsat pomocí lineárního rovnice nebo nerovnice. Kromě toho je zavedeno další omezení - hodnoty proměnných musí být nezáporné, protože představují taková množství, jako je obrat, provozní doba, náklady a další ekonomické ukazatele.

Geometrická interpretace ekonomických problémů umožňuje vizualizovat jejich strukturu, identifikovat rysy a otevřít způsoby studia složitějších vlastností. Lineární programovací problém se dvěma proměnnými lze vždy vyřešit graficky. Již v trojrozměrném prostoru se však takové řešení stává komplikovanějším a v prostorech, jejichž rozměr je více než tři, je grafické řešení, obecně řečeno, nemožné. Případ dvou proměnných nemá žádný zvláštní praktický význam, ale jeho zvážení objasňuje vlastnosti problémů lineárního programování, vede k myšlence jeho řešení, činí geometricky jasné způsoby řešení a způsoby jejich praktické implementace.

§ 2 Matematický model úlohy lineárního programování

Před řešením problému sestavíme jeho matematický model.

Matematický model je sada vztahů skládajících se z lineární objektivní funkce a lineárních vazeb na proměnnou.

Princip sestavování matematického modelu.

1. Vyberte proměnné úkolu.

Proměnnými problému jsou veličiny

Které plně charakterizují ekonomický proces popsaný v úkolu. Obvykle psáno ve formě vektoru X = () Navíc )

2. Vytvořte systém pro omezení problému.

Systém omezení je soubor rovnic a nerovností, které jsou splněny proměnnými problému a který vyplývá z omezených ekonomických podmínek problému.

PROTI obecný pohled systém je zapsán jako

3. Definujte objektivní funkci.

Objektivní funkce je funkce Z (X), která charakterizuje kvalitu úkolu, jehož extrém je třeba najít. Objektivní funkce je obecně zapsána Z (X) =

pak. matematický model je najít proměnné problému

splňující systém omezení:

a stav bez negativity

0 (j =), který poskytuje extrém objektivní funkce Z (Y) =

Jakákoli sada hodnot proměnných, která splňuje systém omezení a podmíněných negativ, se nazývá přípustné řešení problému lineárního programování.

Soubor proveditelných řešení tvoří oblast proveditelných řešení problému (ODS).

Optimálním řešením je proveditelné řešení problému, ve kterém objektivní funkce dosáhne extrému.

§ 3 Kanonická forma problému lineárního programování

Matematický model úlohy musí mít kanonickou podobu.

Pokud se omezovací systém skládá pouze z rovnice a všechny proměnné splňují podmínku nezápornosti, pak má problém kanonický tvar.

Pokud má systém alespoň jednu nerovnost nebo je jakákoli proměnná neomezená podmínkou non-negativity, pak má problém standardní formu. Aby byl úkol uveden do kanonické podoby, musíte:

přejít z nerovností do rovnice následovně: na levé straně nerovností zavedeme pro nerovnost další proměnnou s koeficientem (+1) (

) a (-1) pro nerovnost () další proměnné nejsou uloženy cílové nezáporné hodnoty, pak jsou nahrazeny rozdílem dvou záporných proměnných, to znamená: = - (

Celkový pohled na kanonickou formu:

Kapitola ΙΙ Řešení problému pomocí jednoduché metody

Metoda simplex je metoda postupného vylepšování plánu (řešení), nejúčinnější a používá se k řešení jakéhokoli problému s lineárním programováním.

Název metody je z latiny simplecx - jednoduché, protože z počáteční oblasti proveditelných řešení problému nejjednodušší pohled... Myšlenky metody navrhl ruský matematik L. V. Kontarovich. v roce 1939 a poté tuto myšlenku vyvinul a rozvinul J. Danzig v roce 1949.

Metoda simplex umožňuje v konečném počtu kroků buď najít optimální řešení, nebo dokázat, že neexistuje.

§ 1 Prohlášení o problému

Společnost ve výrobním procesu používá 3 typy strojů: Ι, ІΙ, ІVІ. V tomto případě se spotřebovávají suroviny, pracovní zdroje a zohledňují se režijní náklady.

Jakýkoli problém lineárního programování lze redukovat na problém lineárního programování v kanonické formě. K tomu je v obecném případě nutné umět redukovat problém maximalizace na problém minimalizace; přejít od omezení nerovnosti k omezením rovnosti a nahradit proměnné, které nedodržují podmínku non-negativity. Maximalizace některé funkce je ekvivalentní minimalizaci stejné funkce, která je brána s opačným znaménkem, a naopak.

Pravidlo pro redukci problému lineárního programování na kanonickou formu je následující:

• pokud je v původním problému požadováno stanovení maxima lineární funkce, pak byste měli změnit znaménko a hledat minimum této funkce;
• pokud je pravá strana vazeb záporná, pak by toto omezení mělo být vynásobeno -1;
• pokud mezi omezeními existují nerovnosti, pak se zavedením dalších nezáporných proměnných transformují na rovnosti;
• pokud nějaká proměnná x j nemá žádná znaménková omezení, pak je nahrazen (v objektivní funkci a ve všech omezeních) rozdílem mezi dvěma novými nezápornými proměnnými:
  x 3 = x 3 + - x 3 - , kde x 3 +, x 3 - ≥ 0 .

Příklad 1... Redukce problému lineárního programování na kanonickou formu:

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.

Do každé rovnice systému omezení zavádíme vyrovnávací proměnné x 4, x 5, x 6... Systém bude zapsán ve formě rovností a v první a třetí rovnici systému omezení proměnné x 4, x 6 se zadávají na levé straně znaménkem „+“ a ve druhé rovnici proměnná x 5 zadáno znakem „-“.

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.

Volné termíny v kanonické formě musí být kladné, proto vynásobíme poslední dvě rovnice -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 kanonické formě psaní problémů lineárního programování musí být všechny proměnné zahrnuté v systému omezení záporné. Předpokládejme to x 1 = x 1 '- x 7 , kde x 1 '' ≥ 0, x 7 ≥ 0 .

Dosazením tohoto výrazu do systému omezení a objektivní funkce a zápisem proměnných ve vzestupném pořadí indexu získáme lineární programovací problém prezentovaný v kanonické formě:

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.

Podmínka optimality pro základní plán kanonické úlohy LP. Simplexní metoda a její konvergence.

Metoda simplex je univerzální, protože vám umožňuje vyřešit téměř jakýkoli problém lineárního programování napsaný v kanonická forma.

Myšlenka simplexové metody důsledné zlepšování plánu, spočívá v tom, že počínaje nějakým počátečním řešením podpory, důsledně usměrněný pohyb podporou řešení problému na optimální.

Hodnota objektivní funkce se tímto pohybem u úkolů nesnižuje na maximum.

Protože počet řešení podpory je konečný, získáme po konečném počtu kroků optimální řešení podpory.

Základní nezáporné řešení se nazývá referenční řešení.

Simplexní algoritmus metody

1. Matematický model problému by měl být kanonický. Pokud je nekanonický, musí být uveden do kanonické podoby.

2. Najděte původní řešení podpory a zkontrolujte jeho optimálnost.
Chcete -li to provést, vyplňte tabulku simplex 1.
Vyplňujeme všechny řádky tabulky 1. kroku podle údajů systému omezení a objektivní funkce.

Při řešení problémů na jsou možné následující případy maximum:

1. Pokud jsou všechny koeficienty posledního řádku simplexové tabulky DJ ³ 0, poté nalezeno

řešení optimální.

2 Pokud alespoň jeden koeficient Dj £ 0, ale pro odpovídající proměnnou neexistuje jediný kladný poměr hodnocení, pak řešení zastavujeme úkoly, protože F (X) ® ¥, tj. objektivní funkce není v oblasti proveditelných řešení omezena.

Pokud je alespoň jeden koeficient posledního řádku záporný a pro odpovídající proměnnou existuje alespoň jeden pozitivní hodnotící vztah, pak musíte jít na jiné referenční řešení.

E -li v posledním řádku je tedy několik záporných koeficientů do sloupce základní proměnné(Bp) představte to proměnnáčemuž odpovídá největší záporný koeficient v absolutní hodnotě.

5. Pokud je alespoň jeden koeficient Dk< 0 ,pak k - th sloupec přijímáme pro hostitele.

6. Pro vedoucí linie přijímáme ten, který odpovídá minimální přístup členů zdarma bi na kladné koeficienty vedoucí, k - to sloupec.

7. Volá se prvek umístěný v průsečíku předních řádků a sloupce vedoucí prvek.

Naplnění simplexové tabulky 2 :

· naplňte základní sloupec nulami a jedničkami

· přepište vedoucí čáru jejím vydělením úvodním prvkem

Pokud má přední řádek nuly, pak lze odpovídající sloupce přenést do další simplexové tabulky

· zbývající koeficienty se nacházejí podle pravidla „obdélník“

Získáváme nové řešení podpory, které kontrolujeme pro optimálnost:

Pokud jsou všechny koeficienty posledního řádku DJ ³ 0, pak nalezené řešení maximum.

Pokud ne, vyplňte simplexovou tabulku v 8. kroku atd.

Pokud objektivní funkce F (X) vyžaduje nalezení minimální hodnota, potom kritérium optimálnost problému je kladné kurzy D j pro všechny j = 1,2,… n.

Konvergence simplexové metody. Degenerace v problémech LP. Nejdůležitější vlastností každého výpočetního algoritmu je konvergence, to znamená možnost získání požadovaných výsledků (s danou přesností) v konečném počtu kroků (iterací) během jeho aplikace.

Je snadné vidět, že problémy s konvergencí simplexové metody mohou potenciálně nastat ve fázi výběru hodnoty r (položka 2 ") v případě, že stejné minimální hodnoty poměru

bude dosaženo pro několik řádků tabulky T (q) současně. Potom při další iteraci bude sloupec b (β (q + 1)) obsahovat nulové prvky.

⇐ Předchozí12345Další ⇒

Datum zveřejnění: 2015-11-01; Přečteno: 4190 | Porušení autorských práv na stránku

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

Optimální řešení - problém - lineární programování

Strana 1

Optimálního řešení problému lineárního programování je dosaženo v jednom z referenčních bodů, kde je alespoň k p, - m proměnných rovných nule.

Pomocí optimálního řešení úlohy lineárního programování je možné najít přípustné změny v DS, u nichž L také zůstává konstantní.

Pokud existuje optimální řešení problému lineárního programování, pak existuje základní optimální řešení.

Je dokázáno, že optimální řešení úlohy lineárního programování se nachází na hranici oblasti přípustných hodnot řízených proměnných, což je mnohostěn v n-dimenzionálním prostoru a je určen soustavou lineárních vazeb.

Protože z je optimální řešení pro problém lineárního programování s m omezeními, toto řešení obsahuje maximálně m přísně kladných proměnných.

Je dokázáno, že optimální řešení úlohy lineárního programování je na hranici oblasti přípustných hodnot řízených proměnných, což je mnohostěn v n-dimenzionálním prostoru definovaném soustavou lineárních vazeb. Souřadnice každého vrcholu jsou určeny řešením soustavy rovnic (vazeb) a za přítomnosti n řízených proměnných a m omezení je nutné vyřešit soustavu m rovnic. Kombinace Cm n (m - n roste velmi rychle s rostoucím typem, proto hledání řešení vyžaduje velmi velké množství výpočtů, které jsou nedostupné i pro počítač.

Takže v případě D 1 je optimálním řešením problému lineárního programování automaticky celé číslo.

Jak je ukázáno v části 1, optimální řešení problému lineárního programování není v žádném případě nutně integrální a současně existuje mnoho problémů, jejichž povaha vyžaduje integrální řešení. Některé z těchto problémů na první pohled nejsou problémy s celočíselným programováním, ale lze je tak formulovat.

Je zřejmé, že ne každé základní řešení je optimálním řešením problému s lineárním programováním. Optimální řešení nedegenerovaného problému však musí být pro soustavu rovnic vždy základní (VIII, 42), a proto problém nalezení optimálního řešení spočívá ve výčtu pouze základních řešení soustavy rovnic ( VIII, 42), mezi nimiž se nachází optimální.

Je zřejmé, že ne každé základní řešení je optimálním řešením problému s lineárním programováním. Optimální řešení nedegenerovaného problému však musí být vždy základní pro soustavu rovnic (VIII42), a proto problém nalezení optimálního řešení spočívá ve vyjmenování pouze základních řešení soustavy rovnic (VIII42), mezi nimiž najde se ten optimální.

Po provedení několika iterací v kroku 3 se může objevit řada alternativních optimálních řešení problému s lineárním programováním.

LINEÁRNÍ PROGRAMOVACÍ PROBLÉM

Tato smyčka se někdy nazývá kontinuální degenerace. Tento jev se bohužel často vyskytuje u středních problémů PI vysoké dimenze. Existuje také mnoho příkladů nízko dimenzionálních problémů (ne více než 10 proměnných a rovnic), které k dosažení konvergence vyžadují tisíce iterací.

V těchto případech se používá simplexová metoda, což je iterační (krok za krokem) postup k určení optimálního řešení problému s lineárním programováním. Výpočty pomocí simplexové metody začínají určením proveditelného řešení a poté hledají další proveditelná řešení a kontrolují možnosti jejich vylepšení. Přechod z jednoho řešení na druhé pokračuje, dokud nejsou možná nová vylepšení. Standard počítačové programy které používají simplexovou metodu k řešení takových problémů správy, které lze reprezentovat jako problémy s lineárním programováním.

Pokud má systém lineárních omezení speciální strukturu, například pokud tvoří síťový model, pak v kroku 2 při hledání optimálního řešení problému lineárního programování lze tuto okolnost použít.

Myšlenka proporcionálního rozdělení byla implementována ve formě dvoustupňového algoritmu výpočtu navrženého II Dikinem, ve kterém je vlastnost metody vnitřního bodu v zásadě použita ke generování sady optimálních řešení problému lineárního programování s ohledem na do vnitřního bodu. Tato vlastnost znamená, že hraniční hodnoty podle podmínek nerovnosti (2.3.2) - (2.3.4) jsou dosaženy pouze pro ty proměnné, které mají tyto hraniční hodnoty pro jakékoli jiné optimální řešení.

Stránky: 1 2

Grafická metoda pro řešení problému lineárního programování

Zvažte LPP ve standardní podobě pro případ dvou proměnných:

(10)

Nechť je systém nerovností (10) konzistentní (má alespoň jedno řešení). Jakákoli nerovnost tohoto systému geometricky definuje polorovinu s hraniční čárou Podmínky bez negativity definují poloroviny s odpovídajícími hraničními čarami a.

Protože je systém konzistentní, poloroviny, jako konvexní množiny, protínající se, tvoří společnou část, což je konvexní množina a je to soubor bodů, jejichž souřadnice každého z nich jsou řešením tohoto systému. Sbírání všech těchto bodů se nazývá polygonová řešení. Může to být bod, úsečka, paprsek, přímka, uzavřený mnohoúhelník, neomezená polygonální oblast.

Řešení LPP je geometricky hledáním takového bodu polygonu řešení, jehož souřadnice dodávají největší (nejmenší) hodnotě objektivní funkci. Kromě toho jsou všechny body mnohostěnu platným řešením.

Zvažte tzv vodorovná čára Objektivní funkce z, tj. řádek, po kterém tato funkce nabývá stejné pevné hodnoty: nebo

Algoritmus pro řešení úlohy lineárního programování grafickou metodou (počet proměnných).

1. Polygonální oblast proveditelných řešení v rovině je konstruována tak, aby odpovídala omezením. Potom je sestrojen vektorový gradient

Objektivní funkce z v každém bodě oblast proveditelných řešení.

2. Přímka (čára na úrovni funkce z), kolmo na gradientový vektor, se pohybuje rovnoběžně se sebou ve směru gradientového vektoru v případě maximálního problému (a v opačném směru - v případě minimálního problému), dokud neopustí oblast proveditelných řešení. Omezující bod (nebo body) oblasti jsou optimální body.

3. Pro nalezení souřadnic optimálního bodu je nutné vyřešit soustavu rovnic, která odpovídá přímkám, jejichž průsečík tvoří tento bod.

Formulace hlavních typů úloh LP, konstrukce jejich matematických modelů

Hodnota objektivní funkce v tomto bodě bude optimální a souřadnice bodu samotného budou řešením problému LP .

Příklad. Vyřešte problém geometricky:

Vytvořte mnohoúhelník všech možných řešení OABCD a směrový vektor objektivní funkce (obr. 1). Směr vektoru gradientu udává směr zvýšení objektivní funkce. Protože uvažovaným problémem je najít maximum, pohybujeme přímkou ​​kolmo na vektor ve směru tohoto vektoru rovnoběžně k sobě, dokud tato přímka neopustí oblast přípustných řešení. Na hranici regionu, v našem případě v bodě S, a bude existovat řešení problému. Směřovat S je na průsečíku přímek a. V důsledku toho jsou jeho souřadnice určeny řešením soustavy těchto rovnic na rovnici:

odkud tj. směřovat S má souřadnice (6, 4).

Maximum (maximální hodnota objektivní funkce) je: Odpovědět: s optimálním řešením, tj. maximálního zisku lze dosáhnout výrobou 6 jednotek prvního a 4 jednotek druhého produktu.

ÚVOD

Moderní ekonomická teorie, jak na mikro -, tak na makroúrovni, zahrnuje jako přirozený, nezbytný prvek matematické modely a metody. Využití matematiky v ekonomii umožňuje za prvé zdůraznit a formálně popsat nejdůležitější významné vztahy mezi ekonomickými proměnnými a objekty: studium tak složitého objektu vyžaduje vysoký stupeň abstrakce. Za druhé, z jasně formulovaných počátečních dat a vztahů lze použít deduktivní metody k získání závěrů, které jsou adekvátní studovanému objektu ve stejné míře jako učiněné předpoklady. Za třetí, metody matematiky a statistiky umožňují induktivně získat nové znalosti o objektu: vyhodnotit formu a parametry závislostí jeho proměnných, v největší míře odpovídající dostupnému pozorování. A konečně, za čtvrté, použití matematického jazyka umožňuje člověku přesně a kompaktně prezentovat ustanovení ekonomické teorie, formulovat její pojmy a závěry.

Matematické modely používané v ekonomii lze rozdělit do tříd podle řady znaků souvisejících s vlastnostmi modelovaného objektu, účelem modelování a použitými nástroji: mikro- a makroekonomické modely, teoretické a rovnovážné, statistické a dynamické.

Podstata optimalizačních metod spočívá v tom, že na základě dostupnosti určitých zdrojů je zvolen způsob jejich využití (distribuce), který zajišťuje maximum (minimum) ukazatele, který nás zajímá.

Všechny hlavní části matematického programování (plánování) se používají jako optimalizační metody v ekonomii.

Byla pojmenována matematická disciplína zabývající se studiem extrémních (maximálních nebo minimálních) problémů kontroly, plánování a vývoje metod pro jejich řešení matematické programování.

Matematická formulace extrémního problému obecně spočívá v určení největší nebo nejmenší hodnoty objektivní funkce
pod podmínkou ,

kde a jsou jim dány funkce a jsou nějaká reálná čísla.

V závislosti na typu cílové funkce a omezeních je matematické programování rozděleno na lineární a nelineární. Většina

studovanou částí matematického programování je lineární programování.

Definice.

Problém lineárního programování (strana 1 ze 3)

Lineární programování - věda o metodách používání a hledání extrémních (největších a nejmenších) hodnot lineární funkce, jejíž neznámé podléhají lineárním omezením.

Tato lineární funkce se nazývá objektivní a omezení ve formě rovnic nebo nerovností se nazývají vazebný systém.

Definice. Nazývá se matematické vyjádření objektivní funkce a její omezení matematický model ekonomického problému.

Uvažujme některé problémy s lineárním programováním (LPP).

1. Problém využití zdrojů (problém plánování výroby).

Pro výrobu různých produktů společnost používá tři různé druhy surovin. Sazby spotřeby surovin na výrobu jednoho produktu , stejně jako celkový počet

suroviny každého druhu, které může podnik použít, jsou uvedeny v tabulce.

Vypracujte plán výroby produktů, ve kterém jsou celkové náklady na všechny výrobky vyráběné podnikem maximální.

Pojďme sestavit matematický model tohoto problému.

Označujeme prostřednictvím požadovaného výstupu produktů, prostřednictvím - produktů,

prostřednictvím - produktů.

Protože pro každý druh suroviny existují sazby nákladů, můžeme pro výrobu všech produktů najít celkové náklady na každý druh suroviny. Z tabulky vyplývá, že celkový objem surovin typu I bude, II -
,

III -
... A protože na zásoby surovin existují omezení, celkový objem surovin každého druhu by neměl být větší než celkové množství surovin, tj.

získáme následující systém nerovností

(1)

Ekonomicky proměnné může nabývat pouze nezáporných hodnot:

(2)

Náklady na všechny produkty tohoto typu budou – – V souladu s tím budou celkové náklady na výrobky vyráběné podnikem (3)

Musíme najít tuto funkci. Mezi všemi nezápornými řešeními systému (1) je tedy nutné najít takové, pro které funkce (3) nabývá maximální hodnoty.

Tento úkol lze snadno zobecnit na případ uvolňování typů produktů pomocí typů surovin (zdrojů).

Označme podle - počet jednotek produktů plánovaných pro výrobu, - zásoby zdrojů - druh, - měrná spotřeba zdrojů na výrobu - výrobky. - zisk z prodeje jednotky výrobku - první typ.

Poté bude mít ekonomicko -matematický model problému využívání zdrojů v obecném nastavení podobu: najít takový plán
výstup, který splňuje základní systém omezení

další systém omezení

při kterém je objektivní funkce

nabývá maximální hodnoty.

Komentář. Chcete -li sestavit matematický model LPP, musíte:

- zadejte označení proměnných;

- na základě cíle ekonomického výzkumu vypracovat cílovou funkci;

- s přihlédnutím k omezením používání ekonomických ukazatelů problému a jejich kvantitativních zákonů sepište systém omezení.

Řešení problémů s lineárním programováním je založeno na konceptech analytické geometrie bezrozměrného vektorového prostoru.

Uvedení obecného LPP do kanonické podoby.

Obecný pohled na LPP je následující:

(1)

(2)

(3)

kde vztah (1) je objektivní funkce, (2) je systém základních omezení, (3) je systém dalších omezení.

Vztahy (2) a (3) tvoří kompletní systém omezení.

Redukce systému základních omezení na kanonickou formu se provádí zavedením dalších nezáporných proměnných s koeficienty „+1“, pokud jsou nerovnosti ve formě, a „-1“, pokud jsou nerovnosti ve tvaru , na levé straně nerovností. Do objektivní funkce vstupují další proměnné s nulovými koeficienty.

Definice ... LPP se nazývá kanonicky definovaný, pokud je jeho systém základních omezení reprezentován rovnicemi.

Definice. LPP se nazývá uveden ve standardní formě kanonické formy, pokud jsou splněny následující podmínky:

1) systém základních vazeb je reprezentován rovnicemi a všechny jsou lineárně nezávislé;

2) počet rovnic je menší než počet proměnných;

3) problém minimalizace objektivní funkce se řeší;

4) pravé strany systému základních omezení nejsou záporné;

5) všechny proměnné jsou také nezáporné.

Ve většině metod pro řešení problémů lineárního programování se předpokládá, že systém omezení se skládá z rovnic a přírodních podmínek pro non-negativitu proměnných.

Při kompilaci modelů mnoha problémů se však omezení tvoří hlavně ve formě soustavy nerovností, takže je nutné umět přejít ze soustavy nerovností do soustavy rovnic.

To lze provést následujícím způsobem:

Vezměte lineární nerovnost

a přidejte na jeho levou stranu nějaké množství, aby se nerovnost proměnila v rovnost

Tato hodnota navíc není záporná.

Příklad

Přesuňte problém lineárního programování do kanonické formy:

Řešení:

Vraťme se k problému nalezení maxima objektivní funkce.

Za tímto účelem změníme znaky koeficientů objektivní funkce.

Abychom transformovali druhou a třetí nerovnost soustavy vazeb na rovnice, zavedeme nezáporné doplňkové proměnné x 4 x 5 (na matematickém modelu je tato operace označena písmenem D).

Proměnná x 4 je uvedena na levé straně druhé nerovnosti se znaménkem „+“, protože nerovnost má tvar „≤“.

Proměnná x 5 je zavedena na levé straně třetí nerovnosti se znaménkem „-“, protože nerovnost má tvar „≥“.

Proměnné x 4 x 5 se zadávají do objektivní funkce s koeficientem. rovná nule.

Úkol napíšeme v kanonické podobě:

JEDNODUCHÁ METODA ŘEŠENÍ PROBLÉMŮ S LINEÁRNÍM PROGRAMOVÁNÍM

Tato metoda je metodou účelného výčtu podpůrných řešení problému lineárního programování. Umožňuje v konečném počtu kroků buď najít optimální řešení, nebo zjistit, že žádné optimální řešení neexistuje.

Algoritmus simplexové metody pro řešení problémů lineárního programování

Chcete -li problém vyřešit pomocí simplexové metody, musíte provést následující:

1. Přiveďte problém do kanonické podoby

Téma 8. Lineární programování

Najděte počáteční řešení podpory s „jednotkovým základem“ (pokud neexistuje řešení podpory, pak problém nemá řešení kvůli nekompatibilitě systému omezení)

3. Vypočítejte odhady vektorových expanzí na základě řešení podpory a vyplňte tabulku simplexové metody

4. Pokud je splněno kritérium jedinečnosti optimálního řešení, řešení problému končí

5. Pokud je splněna podmínka existence sady optimálních řešení, pak jednoduchým výčtem se najdou všechna optimální řešení

Příklad řešení problému pomocí simplexové metody

Příklad 1

Vyřešte problém pomocí simplexové metody:

Minimalizujte hodnotu funkce

F = 10 × 1 - 4 × 3 max

Za přítomnosti omezení ve formě nerovností

Přinášíme problém do kanonické podoby.

Za tímto účelem zavedeme na levé straně prvního omezení nerovnosti další proměnnou x 5 s koeficientem +1. Proměnná x 5 je zahrnuta do objektivní funkce s nulovým koeficientem (to znamená, že není zahrnuta).

Dostaneme:

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

Za přítomnosti omezení ve formě nerovností

Najděte počáteční řešení podpory. K tomu se volné (nevyřešené) proměnné rovnají nule x1 = x3 = 0.

Získáme referenční řešení X1 = (0,0,0,5,9 / 15,6) s jednotkovým základem B1 = (A4, A5, A6).

Odhady expanzí vektorů podmínek vypočítáme na základě řešení podpory podle vzorce:

Δ k = C b X k - c k

· C b = (s 1, s 2, ..., s m) - vektor koeficientů objektivní funkce se základními proměnnými

X k = (x 1k, x 2k, ..., x mk) je vektor expanze odpovídajícího vektoru A na základ referenčního řešení

· С к - koeficient objektivní funkce při proměnné х к.

Odhady vektorů zahrnutých v základu jsou vždy nulové.

Řešení podpory, koeficienty expanze a odhady rozšíření vektorů podmínek na základě řešení podpory jsou zapsány v simplexové tabulce:

Nad tabulkou jsou pro usnadnění výpočtu odhadů zapsány koeficienty objektivní funkce. První sloupec "B" obsahuje vektory zahrnuté v základu referenčního roztoku. Pořadí zápisu těchto vektorů odpovídá počtům povolených neznámých v rovnicích omezení. Druhý sloupec tabulky „C b“ zaznamenává koeficienty objektivní funkce se základními proměnnými ve stejném pořadí. Při správném umístění koeficientů objektivní funkce ve sloupci "C b" jsou odhady jednotkových vektorů zahrnutých v základu vždy rovny nule.

Do posledního řádku tabulky s odhady Δ k ve sloupci "A 0" jsou zapsány hodnoty objektivní funkce na referenčním roztoku Z (X 1).

Počáteční řešení podpory není optimální, protože v maximálním problému jsou odhady Δ 1 = -2, Δ 3 = -9 pro vektory A1 a A3 negativní.

Podle věty o vylepšení řešení podpory, pokud má v maximálním problému alespoň jeden vektor negativní odhad, pak lze nalézt nové řešení podpory, na kterém bude hodnota objektivní funkce větší.

Určeme, který z těchto dvou vektorů povede k většímu přírůstku objektivní funkce.

Přírůstek objektivní funkce zjistíme podle vzorce:

Hodnoty parametru θ 01 pro první a třetí sloupec vypočítáme podle vzorce:

Dostaneme θ 01 = 6 s l = 1, θ 03 = 3 s l = 1 (tabulka 26.1).

Zjistěte přírůstek objektivní funkce při zavádění prvního vektoru do základu

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

a třetí vektor ΔZ 3 = - 3 * ( - 9) = 27.

Pro rychlejší přiblížení k optimálnímu řešení je proto nutné do základu řešení podpory zavést vektor A3 místo prvního vektoru základu A6, protože minima parametru θ 03 je dosaženo v první řadě (l = 1).

Provedeme Jordanovu transformaci s prvkem X13 = 2, získáme druhé řešení podpory

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

se základem B2 = (A3, A4, A5).

(tabulka 26.2)

Toto řešení není optimální, protože vektor A2 má negativní odhad Δ2 = - 6.

Pro vylepšení řešení je nutné zavést vektor A2 do základu řešení podpory.

Určete počet vektorů odvozených od základu. Chcete -li to provést, vypočtěte parametr θ 02 pro druhý sloupec, který se rovná 7 pro l = 2.

Proto od základu odvodíme druhý základový vektor A4.

Provedeme Jordanovu transformaci s prvkem x 22 = 3, získáme třetí řešení podpory

X3 = (0,7.10.0.63.0)

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

Toto řešení je jediné optimální, protože pro všechny vektory, které nejsou zahrnuty do odhadu, kladné

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

Odpovědět: max Z (X) = 201 při X = (0,7,10,0,63).

⇐ Předchozí123456789Další ⇒

V praxi jsou omezení v problému lineárního programování často specifikována nikoli rovnicemi, ale nerovnostmi.

Ukažme si, jak můžeme přejít od problému s omezeními nerovností k hlavnímu problému lineárního programování.

U proměnných budiž problém lineárního programování, ve kterém jsou omezení proměnných ve formě lineárních nerovností. V některých z nich může být znak nerovnosti, zatímco v jiných (druhý typ je redukován na první jednoduchou změnou znaménka obou částí). Proto nastavíme všechna omezení nerovnosti ve standardní podobě:

Je nutné najít sadu nezáporných hodnot, které by splňovaly nerovnosti (4.1) a navíc by minimalizovaly lineární funkci:

Z takto nastaveného úkolu lze snadno přejít na hlavní úkol lineárního programování. Ve skutečnosti si představme notaci:

kde jsou nějaké nové proměnné, které budeme nazývat „dodatečné“. Podle podmínek (4.1) tyto dodatečné proměnné, jak by měly, nejsou záporné.

Stojíme tedy před problémem lineárního programování v následující formulaci: najděte takové nezáporné hodnoty proměnných, aby vyhovovaly soustavě rovnic (4.3) a zároveň minimalizovaly lineární funkci těchto proměnných:

Jak vidíte, máme před sebou ve své čisté podobě hlavní úkol lineárního programování (LPP). Rovnice (4.3) jsou uvedeny ve formě již povolené pro základní proměnné, které jsou vyjádřeny jako volné proměnné. Celkový počet proměnných je stejný, z toho „počáteční“ a „doplňkový“. Funkce L je vyjádřena pouze pomocí „počátečních“ proměnných (koeficienty „doplňkových“ proměnných v ní jsou rovny nule).

Zredukovali jsme tedy problém lineárního programování s omezeními nerovností na hlavní problém lineárního programování, ale s větším počtem proměnných, než bylo původně v problému.

Příklad 1 Existuje problém lineárního programování s omezeními nerovností: najděte nezáporné hodnoty proměnných splňujících podmínky

a minimalizace lineární funkce

Je nutné přenést tento úkol do podoby OZLP.

Řešení. Redukujeme nerovnosti (4.4) na standardní formu;

Zavádíme další proměnné:

Úkol je omezen na nalezení nezáporných hodnot proměnných

splnění rovnic (4.6) a minimalizace lineární funkce (4.5).

Ukázali jsme, jak můžeme přejít od problému lineárního programování s omezeními nerovnosti k problému s omezeními rovnosti (LPPP). Zpětný přechod je vždy možný - od LPP k problému s omezeními nerovností. Pokud jsme v prvním případě zvýšili počet proměnných, pak ve druhém případě jej snížíme, odstraníme základní proměnné a ponecháme pouze volné.

Příklad 2. Existuje problém lineárního programování s omezeními rovnosti (LPPP):

a funkce, která má být minimalizována

Je nutné jej zapsat jako problém lineárního programování s omezeními nerovnosti.

Řešení. Od té doby vybereme nějaké dvě proměnné jako volné. Pamatujte, že proměnné nelze vybrat jako volné proměnné, protože jsou vztaženy k první z rovnic (4-7): hodnota jedné z nich je zcela určena hodnotou druhé a volné proměnné musí být nezávislé

Ze stejného důvodu je nemožné vybrat proměnné jako volné (jsou spojeny druhou rovnicí). Vyberme si jako volné proměnné a vyjádřme prostřednictvím nich všechny ostatní:

Protože podmínky (4 9) mohou být nahrazeny nerovnostmi:

Pojďme předat výraz lineární funkce L volným proměnným Substituce v L místo jejich výrazů (4.9). dostaneme.

LINEÁRNÍ PROGRAMOVACÍ MODEL

1 Matematický popis modelu lineárního programování

2 Metody implementace modelů lineárního programování

3 Problém duálního lineárního programování

Lineární programovací model(LP) nastane, pokud ve studovaném systému (objektu) omezení proměnných a objektivní funkce lineární.

LP modely se používají k řešení dvou hlavních typů aplikovaných problémů:

1) optimální plánování v jakékoli oblasti lidské činnosti - sociální, ekonomické, vědecké, technické a vojenské. Například s optimálním plánováním výroby: rozdělení finančních, pracovních a jiných zdrojů, dodávky surovin, řízení zásob atd.

2) dopravní problém (nalezení optimálního plánu pro různé druhy dopravy, optimální plán pro distribuci různých finančních prostředků do objektů pro různé účely atd.)

MATEMATICKÝ POPIS LINEÁRNÍHO PROGRAMOVACÍHO MODELU

Je nutné najít nezáporné hodnoty proměnných

uspokojující lineární omezení ve formě rovností a nerovností

,

kde - daná čísla,

a poskytnutí extrému lineární objektivní funkce

,

kde jsou daná čísla, která jsou zapsána jako

Platné řešení jakákoli sada se nazývá splnění podmínek.

Doména realizovatelných řešení- soubor všech možných řešení.

Optimální řešení
, pro který .

Poznámky

1. Daný model LP je Všeobecné... Rozlišujte také Standard a kanonický formy LP modelů.

2... Podmínky existence Implementace modelu LP:

- sada proveditelných řešení není prázdná;

- Objektivní funkce ohraničeno (alespoň shora při hledání maxima a zespodu při hledání minima).

3. LP je založen na dvou větách

Věta 1. Hodně G definovaný soustavou omezení formuláře je konvexní uzavřená množina ( konvexní mnohostěn s rohovými hroty - vrcholy.)

Věta 2. Lineární forma definována na konvexním mnohostěnu

j=1,2,…,s

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

dosahuje extrému v jednom z vrcholů tohoto mnohostěnu.

Tato věta se nazývá lineární forma extrémní věta.

Podle Weierstrassovy věty je optimální řešení jedinečné a jde o globální extrém.

Existuje obecný analytický přístup k implementaci LP modelu - simplexové metody. Při řešení problémů s lineárním programováním poměrně často neexistuje řešení. K tomu dochází z následujících důvodů.

Ukážeme si první důvod na příkladu

Z tohoto důvodu říkají, že omezení jsou nekompatibilní. Oblast proveditelných řešení je prázdná množina.

Druhý důvod je komentován následujícím příkladem:

V tomto případě není oblast proveditelných řešení shora omezena. Oblast přípustných řešení není omezena.

V návaznosti na tradice lineárního programování uveďme problém LP s ekonomickou interpretací. Budiž nám k dispozici m typy zdrojů. Číslo typu zdroje j rovná se . Tyto zdroje jsou nutné pro výrobu n druhy zboží. Označme množství tohoto zboží symboly resp. Jednotka typu položky já náklady . Výroba typu zboží já by měla být omezena na hodnoty resp. Pro výrobu jednotky typu komodity já typ zdroje je spotřebován j... Je nutné určit takový plán výroby zboží ( ) tak, aby jejich celkové náklady byly minimální.

Problémy lineárního programování používané k optimalizaci fungování skutečných objektů obsahují značný počet proměnných a omezení. To znemožňuje jejich řešení. grafické metody... S velkým počtem proměnných a omezení se používají algebraické metody, které jsou založeny na iteračních výpočetních postupech. V lineárním programování bylo vyvinuto mnoho algebraických metod, které se navzájem liší metodami konstrukce počátečního proveditelného řešení a podmínkami pro přechod z jedné iterace do druhé. Všechny tyto metody jsou však založeny na obecných teoretických principech.

Obecnost základních teoretických ustanovení vede k tomu, že algebraické metody řešení problémů lineárního programování jsou si v mnoha ohledech navzájem podobné. Zejména téměř každý z nich vyžaduje předběžnou redukci problému lineárního programování na standardní (kanonickou) formu.

Algebraické metody řešení problému LP začínají jeho redukcí na standardní (kanonickou) formu:

,

,

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

Jakýkoli problém lineárního programování lze redukovat na standardní formu. Porovnání obecného modelu s kanonickým modelem nám umožňuje dojít k závěru, že za účelem redukce problému LP na standardní formu je nejprve nutné přejít ze systému nerovností na rovnosti a za druhé transformovat všechny proměnné tak, aby nebyly záporné.

Přechod na rovnosti se provádí tak, že se na levou stranu přidají omezení nezáporné zbytkové proměnné pro nerovnosti typu a odečtením od levé strany záporné nadbytečné proměnné pro nerovnosti typu. Například nerovnost převádí na rovnost při přechodu na standardní formu , nerovnost - do rovnosti ... Zbytková i nadbytečná proměnná navíc nejsou záporné.

Předpokládá se, že pravá strana nerovností není záporná. Jinak toho lze dosáhnout vynásobením obou stran nerovnosti „-1“ a změnou jejího znaménka na opak.

Pokud v původním problému lineárního programování není proměnná ohraničena znaménkem, může být reprezentována jako rozdíl dvou nezáporných proměnných , kde .

Důležitá vlastnost proměnných je, že pro každé přípustné řešení může mít kladnou hodnotu pouze jeden z nich. To znamená, že pokud , pak a naopak. Proto jej lze považovat za zbytkové a - jako nadbytečné proměnné.

Příklad Nechť je zadán problém lineárního programování:

,

.

Je nutné jej uvést do standardní podoby. Všimněte si, že první nerovnost původního problému má znaménko, proto je nutné do něj vložit zbytkovou proměnnou. V důsledku toho dostaneme.

Druhá nerovnost má znaménko a pro převod na standardní formu vyžaduje zavedení nadbytečné proměnné, provádějící tuto operaci, dostaneme.

Proměnná navíc není omezena znaménkem. Proto, jak v objektivní funkci, tak v obou omezeních, musí být nahrazen rozdílem ... Po provedení substituce získáme problém lineárního programování ve standardní formě, který je ekvivalentní původnímu problému:

.

Problém lineárního programování, napsaný ve standardní formě, je problém nalezení extrému objektivní funkce na sadě vektorů, které jsou řešením systému lineárních rovnic s přihlédnutím k podmínkám nezápornosti. Jak je známo, systém lineárních rovnic nemusí mít žádná řešení, mít jedinečné řešení nebo mít nekonečnou množinu řešení. Optimalizace objektivní funkce je možná pouze v případě, že systém má nekonečno mnoho řešení. Systém lineárních rovnic má nekonečnou množinu řešení, pokud je konzistentní (hodnost hlavní matice se rovná hodnosti rozšířené) a je -li hodnost hlavní matice menší než počet neznámých.

Nechť je hodnost matice omezovacího systému m... To znamená, že matice má alespoň jednu vedlejší m pořadí není rovno nule. Bez ztráty obecnosti můžeme předpokládat, že moll se nachází v levém horním rohu matice. Toho lze vždy dosáhnout změnou číslování proměnných. Tato nenulová hodnost menší m je obvyklé tomu říkat základní. Pojďme vytvořit systém prvního m rovnice systému, zapište jej následovně:

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

Nejjednodušší jsou takzvané lineární deterministické modely. Jsou specifikovány ve formě lineární formy řídicích proměnných ( NS):

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

na lineární omezení svého druhu

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 .

Celkový počet omezení m = q 1 + q 2 + q 3 může překročit počet proměnných (m> k). Kromě toho je obvykle zavedena podmínka pozitivity proměnných ( x i ³ 0).

Plocha odezvy pro lineární model je hyperplane... Zvažte například lineární model dvou proměnných následující formy:

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

za následujících omezení

(2.3)

2X 1 + 3X 2 £ 18;

X 1 – 4X 2 £ 4;

–2X 1 + X 2 £;

NS 1 ³ 0; X 2 ³ 0.

Rozsah platných hodnot (rozsah definice) OABCD pro model (2.2) je tvořen vazbami (2.3) (obr. 2.2). Povrch odezvy je plochý mnohoúhelník OA "B" C "D"(obr. 2.2, b).

Pro určitý poměr omezení může soubor proveditelných řešení chybět (prázdný). Příklad takové sady je uveden na obr. 2.3. Přímo TAK JAKO a slunce shora omezte rozsah přípustných hodnot. Třetí omezení odřízne rozsah přípustných hodnot od spodní části přímky AB. Neexistuje tedy žádná společná oblast, která by splňovala všechna tři omezení.

Lineární modely jsou poměrně jednoduché, a proto na jedné straně znamenají výrazné zjednodušení úkolu a na druhé straně umožňují vývoj jednoduchých a efektivní metodyřešení.

Při studiu DLA se lineární modely používají jen zřídka a téměř výhradně pro přibližný popis problémů.

Lineární modely lze použít pro postupnou aproximaci nelineárních modelů (linearizace úlohy). Tato technika je zvláště účinná při studiu malých oblastí zkoumaného prostoru. Reprezentace jednotlivých úseků nelineární reakční plochy lineárním modelem tvoří základ velké skupiny optimalizačních metod, takzvaných metod s lineární taktikou.

Studium lineárních modelů není obtížné. Zejména vliv každé z proměnných na vlastnosti modelu formuláře

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

dáno jeho koeficienty:

, já = 1,…, k.

Najít optimální lineární model W opt vyvinul efektivní simplexovou metodu.

Nejjednodušší nákladové modely jsou někdy redukovány na lineární, považovány za soubor vynaložených nákladů.

Příkladem takového modelu je klasika model nákladů na dopravu (problém s přepravou)(Obr. 2.4).

Tady je k místa výroby
(já = 1,…, k) a m odběrná místa
(j = 1,…, m) nějakého produktu. Množství produktu vyrobeného v každém k výrobní body se rovnají a i; množství produktu požadované v každém z m spotřeba se rovná b j.

Předpokládá se rovnost celkové produkce a spotřeby:

Množství produktu přepravovaného z já-th výrobní bod v j-th spotřeba bod se rovná x ij; náklady na přepravu jednotky tohoto produktu - s ij.

Celkové náklady na dopravu S S je dáno lineární model:

za následujících omezení

Lineární modely také zahrnují modely ve formě lineárních diferenciálních rovnic (obyčejné nebo parciální derivace).

Lineární obyčejná diferenciální rovnice n-objednávka má formu

Počáteční podmínky jsou zapsány jako

Lineární parciální diferenciální rovnice má tvar

Model uvedený ve formě parciální diferenciální rovnice obsahuje počáteční a okrajové podmínky (podmínky na hranici definiční oblasti funkce F ( t)).

2.3. Studium nejjednoduššího matematického modelu
provoz motoru s plynovou turbínou

Motor s plynovou turbínou (GTE) je hlavní elektrárnou moderních letadel.

Obvod GTE má tvar znázorněný na obr. 2.5.

Tady 1 - vstupní difuzor; 2 - kompresor; 3 - spalovací komora; 4 - turbína;
5 - výstupní tryska.

Pracovní cyklus GTE zahrnuje následující fáze:

1) Přicházející s rychlostí PROTI proud vzduchu difuzorem vstupuje do kompresoru.

2) Kompresor, rotující na stejné hřídeli s turbínou, stlačuje vzduch, který vstupuje do spalovací komory.

3) Do spalovací komory se neustále vstřikuje palivo (petrolej), které se mísí se stlačeným vzduchem.

4) Plyn generovaný spalováním vstupuje do turbíny, což ji zrychluje na rychlost W.

5) Při této rychlosti je plyn vyhozen tryskou do atmosféry.

Vzhledem k tomu že W > PROTI, je generována tažná síla R. což umožňuje letadlu létat v atmosféře.

Změna tahu se provádí změnou rychlosti vstřikování paliva do spalovací komory pohybem ovládacího knoflíku motoru (škrticí klapka). Pohyb ovládání škrticí klapky do určitého úhlu d škrticí klapky se provádí buď ručně pilotem, nebo pomocí ovladače podle signálů z ACS za letu. Zvýšení hodnoty škrticí klapky d způsobí zvýšení síly R., a pokles je pokles této síly.

GTE je komplexní technický systém, ve kterém probíhá značný počet fyzikálních a chemických procesů. Motor je vybaven všemi druhy automatizačních zařízení, systémy pro otáčení a chlazení lopatek turbíny atd. Matematický popis fungování GTE bude přirozeně také docela těžkopádný, včetně systémů parciálních diferenciálních rovnic, obyčejných diferenciálních rovnic, transcendentálních funkcí, algoritmů systému řízení digitálního motoru. Takové modely se používají při navrhování motoru s plynovou turbínou.

K řešení problémů s řízením letu se používá jednodušší model GTE, což je závislost tlačné síly R. od úhlu d škrticí klapky, odchylka škrticí klapky. Proces změny tažné síly popisuje obyčejný člověk diferenciální rovnice druh:

, (2.11)

kde t> 0 je časová konstanta motoru, která kromě konstrukčních charakteristik závisí také na okolní teplotě, její vlhkosti a dalších vnějších faktorech; k[kg / deg] - koeficient proporcionality.

Počáteční podmínka pro rovnici (2.11) je zapsána jako

R.(0) = R. 0 . (2.12)

Rovnice (2.11) spolu s počáteční podmínkou (2.12) tedy je nejjednodušší matematický model operace GTE, psaný ve formě obyčejné diferenciální rovnice 1pořadí.

K určení poměru stran k použity kalibrační grafy závislosti tahu na úhlu otáčení škrticí klapky, postavené na základě experimentálních údajů. Tečna sklonu grafu se rovná požadovanému koeficientu.

Integrace rovnice (2.11) s počáteční podmínkou (2.12) nám umožňuje zjistit, jak se tahová síla v čase mění (obr. 2.6).

Když je plyn vychýlen, tah R. zvyšuje a poté se stabilizuje na určité mezní hodnotě, tj. GTE je setrvačný objekt.

Mez tažné síly získáme z (2.11), když je rychlost jeho změny rovna nule:

. (2.13)

Trvání náběhu závisí na hodnotě časové konstanty motoru t. Proces je považován za stabilní, když t = tústí, kdy tah vstupuje do takzvaného pětiprocentního koridoru mezní hodnoty tahové síly (obr. 2.6). Čím více t, tím je motor setrvačnější, a tím více tústa

Na obr. 2.7 ukazuje chování tlačné síly v závislosti na úhlu vychýlení škrticí klapky při t = 0,5.

Tahová síla při vzletu, kdy je plyn vychýlen o 10 °, dosáhne ustáleného stavu ve třetí vteřině a dosáhne 3390 kg. Deset sekund po vzletu, kdy je plyn vychýlen o 20 °, je tahová síla nastavena na 6780 kg a po dalších deseti sekundách, kdy je plyn vychýlen o 30 °, je tah nastaven na 10170 kg. Mezní hodnota tažné síly je
14270 kg.

Podobné informace.

Základní pojmy modelování

V procesu lidské činnosti se rozvíjejí představy o určitých vlastnostech skutečných předmětů a jejich interakcích. Tyto reprezentace jsou tvořeny osobou ve formě popisů objektů, pro které je používán popisný jazyk. Může to být verbální popis (verbální modely), kresba, kresba, graf, rozložení atd. Vše výše uvedené je shrnuto do jednoho konceptu Modelka, a proces vytváření modelů je modelování.

Modelování Je to univerzální způsob studia procesů a jevů reálného světa. Modelování je zvláště důležité při studiu objektů, které nejsou přístupné přímému pozorování a výzkumu. Patří sem zejména socioekonomické jevy a procesy.

Studium jakéhokoli předmětu, jakékoli formy pohybu je odhalením nejen jeho kvalitativních, ale i kvantitativních zákonů studovaných matematikou. Výše uvedené platí plně pro ekonomiku.

Ekonomika- Jedná se o systém sociální výroby, který ve skutečnosti provádí produkci, distribuci, výměnu a spotřebu hmotných statků nezbytných pro společnost.

Respektive ekonomický a matematický model Je ekonomická abstrakce vyjádřená formálně matematickými termíny, jejíž logická struktura je dána jak objektivními vlastnostmi předmětu popisu, tak subjektivním cílovým faktorem studie, pro kterou se tento popis provádí.

Ekonomické a matematické problémy v zemědělství jsou řešeny pomocí matematických metod. Mezi nimi jsou nejrozvinutější metody lineárního programování (LP). Takové metody se používají k řešení ekonomických a matematických problémů, ve kterých jsou kvantitativní vztahy vyjádřeny lineárně, tj. všechny podmínky jsou vyjádřeny jako soustava lineárních rovnic a nerovnic a kritérium optimality je vyjádřeno jako lineární funkce směřující k minimu nebo maximu (k extrému).

Lineární programovací problém se skládá z objektivní funkce, systému omezení a podmínky pro negativitu proměnných.

Daná funkce n proměnné Je nutné najít největší nebo nejmenší hodnotu této funkce za předpokladu, že argument

Takto představovaný problém optimalizace se nazývá problém matematického programování. Hodně NS se nazývá soubor proveditelných rozhodnutí a funkce je objektivní funkce nebo objektivní funkce. Realizovatelné řešení, při kterém funkce nabývá největší (nebo nejmenší) hodnoty, se nazývá optimální řešení problému.

Pokud je funkce objektivu lineární a množina NS je specifikován pomocí systému lineárních rovnic a nerovnic, pak se problému říká problém lineárního programování (LPP). Obecné tvrzení o problému lineárního programování je tedy následující:

najít extrém funkce

s omezeními

za podmínek bez negativity

Představíme notaci:

Zásoby já-Th typ zdroje;

výdaje já-Th typ zdroje pro produkci j-Th typ výrobku;

jednotkový zisk j-Th typ produktu.

V kompaktní podobě má problém lineárního programování podobu:

Kompaktní zápis ukazuje, že obecný model problému lineárního programování obsahuje pět hlavních prvků:

Proměnné, jejichž hodnota se nachází v procesu řešení problému;

Technické a ekonomické koeficienty pro proměnné v omezeních;

Objem pravé strany nerovností, které se nazývají konstanty problému;

Koeficienty proměnných v objektivní funkci, které se nazývají variabilní odhady;

Proměnný index;

Index omezení.

Cílová funkce(funkce cíle) je matematický výraz, pro který chcete najít extrém, tj. maximální nebo minimální hodnotu.

Proměnné x j označují takové druhy a metody činnosti, jejichž velikost není známa a musí být stanovena v průběhu řešení problému. V problémech v zemědělství obvykle proměnné znamenají požadované velikosti ekonomických odvětví, druhy krmiv ve stravě, značky traktorů a zemědělských strojů atd. Podle konkrétních podmínek může být stejná plodina nebo druh hospodářských zvířat vyjádřena několika proměnnými. Například obilí a krmné obilí; kukuřice na zrno, siláž, zelené krmivo; víceleté trávy na seno, senáž, zelené píce, travní moučku a semena atd.

Proměnné lze libovolně měnit za podmínek uvažovaného problému. Variabilní , jejichž koeficienty tvoří jednotkový sloupec se nazývají základní. Forma základních proměnných jednotkový základ systémy. Proměnné, které nejsou zahrnuty v jednotkové bázi, se nazývají volný, uvolnit.

Celkový počet proměnných zahrnutých v úkolu je určen povahou úkolu, konkrétními výrobními podmínkami, schopností shromažďovat informace atd.

Proměnné lze vyjádřit v široké škále jednotek: ha, q, kg, ks, hlavy atd. Proměnné jsou ze své podstaty rozděleny na hlavní, doplňkové a pomocné. Mezi hlavní proměnné patří vyhledávané činnosti: průmyslová odvětví, druhy krmiv, značky automobilů. Další proměnné se nazývají proměnné, které se tvoří v procesu transformace nerovností na rovnice. Mohou znamenat nevyužitou část zdrojů, přebytek pravá strana nerovnost (jde -li o nerovnost typu „už ne“). Do úkolu jsou zahrnuty pomocné proměnné za účelem stanovení odhadovaných hodnot získaných výrobních zdrojů, odhadovaných hodnot indikátorů ekonomické efektivity výroby.

Doplňkové a pomocné proměnné mají vždy jednotkové koeficienty (+1 nebo –1).

Technické a ekonomické koeficienty (a ij) s proměnnými v systému omezení jsou vyjádřeny míry výrobních zdrojů nebo rychlost produkce na jednotku měření proměnné.

V obou případech je nutné, aby technické a ekonomické koeficienty přesně odpovídaly plánovacímu období, pro které se problém řeší. Pokud je například problém vyřešen pro ekonomickou a matematickou analýzu výroby za uplynulé období, pak se koeficienty vypočítají podle vykázaných údajů. Pokud je rozhodnuto do budoucna, pak by měly být koeficienty vypočítány pro tuto perspektivu.

Míry spotřeby zdrojů jsou nejčastěji určeny referenčními knihami, musí být přizpůsobeny odpovídajícím konkrétním podmínkám. Poměry výnosů se vypočítají na základě plánovaných výnosů plodin a produktivity zvířat.

V případech, kdy je nutné zajistit předem stanovené vztahy mezi proměnnými, představují technické a ekonomické koeficienty koeficienty proporcionality. Například podíl plodin na střídání plodin nebo podíl nějakého krmiva na celkové krmné skupině atd.

Pravá strana omezení (b i) se nazývají konstanty, tj. konstantní hodnoty. Patří sem objem výrobních zdrojů - půda, práce, stroje, hnojiva, investice atd. Výrobní zdroje by měly být stanoveny s přihlédnutím k jejich skutečnému stavu a je nutné vzít v úvahu plánovací období. Kromě toho se tyto výrobní zdroje, jejichž použití je v průběhu roku nerovnoměrné, počítají nejen za rok jako celek, ale také za jednotlivá intenzivní období nebo měsíce (pracovní zdroje).

Výrobní zdroje se určují v různých jednotkách: půda - v hektarech, pracovní zdroje - v člověkohodinách nebo v hodinách, zařízení - v počtu směn stroje, směny nebo denního výkonu atd.

Určení dostupnosti produktivních zdrojů tedy není snadné. Je nutné pečlivě analyzovat výrobní aktivitu ekonomiky, využití pracovní síly, půdy, technických a dalších zdrojů a až poté zahrnout jejich objemy do omezení.

Pravá strana omezení odráží nejen množství zdrojů, ale také objem výroby na horní nebo dolní úrovni. Nižší úroveň je uvedena v případech, kdy je objem výroby znám předem, méně než by farma neměla vyrábět, a horní úroveň neumožňuje produkci produktů nad určitý objem. Tato omezení nejsou vždy požadována. Téměř žádný problém zahrnující definici kombinace průmyslových odvětví se však neobejde bez odpovídajících omezení produktů, jinak se ukáže jednostranné řešení. To je způsobeno skutečností, že účinnost průmyslových odvětví není stejná.

Ve všech ostatních omezeních jsou nuly uvedeny na správnou stranu, protože formulují podmínky pro výrobu a používání produktů nebo odrážejí omezení proporcionální komunikace.

Omezení Je matematický výraz, který váže proměnné ve formě rovností a nerovností. Formulář všech omezení systém omezeníúkoly. Systém omezení v matematické formě charakterizuje podmínky problému. Úplnost odrazu těchto podmínek závisí na složení omezení. Při určování počtu omezení je proto třeba vzít v úvahu dvě okolnosti:

v reflektovat v úkolu pouze ty podmínky, které skutečně omezují možnosti produkce;

v příliš mnoho omezení zvyšuje velikost problému a ztěžuje jeho řešení

Existují tři typy omezení: rovnost (=), nerovnost typu menší nebo rovna (≤), nerovnost typu větší nebo rovna (≥). Například,

kde já = 1, 2, … , m... Variabilní koeficienty jsou označeny a ij kde index já- číslo omezení, index j- proměnný počet, volné členy (pravá strana vazeb) jsou označeny b i, index já- číslo omezení.

Omezení prvního typu se nazývají horní omezení, protože levá strana nerovnosti nemůže být vyšší než určitá hodnota (konstanta). Omezení třetího typu se nazývají omezení zespodu, protože levá strana nerovnosti nemůže být nižší než určitá hodnota (konstanta).

Z hlediska významu lze všechna omezení rozdělit na hlavní, doplňková a pomocná.

Hlavní omezení jsou - to jsou ty, které se překrývají se všemi nebo většinou proměnných úkolu. S jejich pomocí se zpravidla odrážejí hlavní podmínky problému - půda, práce, krmiva, živiny, technologie atd.

Další omezení jsou superponovány na část proměnných nebo na jednu proměnnou. Tato omezení jsou zavedena v případech, kdy je nutné omezit velikost jednotlivých proměnných shora nebo zdola, například s přihlédnutím k požadavkům na střídání plodin nebo s přihlédnutím k fyziologickým limitům nasycení stravy jednotlivými krmivy nebo jejich skupinami. Další omezení tedy odrážejí různé další podmínky, které vznikají během simulace. Každé další omezení však zužuje rozsah svobody volby. Proto by měli být do úkolu zavedeni opatrně, v rozumných mezích a v případě potřeby.

Pomocná omezení, zpravidla nemají žádný nezávislý význam a jsou zavedeny do problému za účelem formalizace jednotlivých podmínek. Patří sem omezení, která vytvářejí proporcionální vztah mezi jednotlivými proměnnými nebo jejich skupinami.

Odhad proměnných v objektivní funkci (s j) jsou koeficienty, které vyjadřují výši celkových příjmů nebo nákladů na měrnou jednotku proměnné. Odhad proměnné zpravidla vyjadřuje přijaté kritérium optimality. Může být předložen v naturáliích i v hotovosti, tj. jednotkové náklady (výrobní náklady).

Podmínka pro nezápornost proměnných je zapsána ve formuláři

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

V reálném životě výroby je na základě podmínek úkolu sestaven seznam proměnných a omezení z tohoto záznamu strukturálního ekonomického a matematického modelu (EMM), jsou připraveny počáteční informace, je sestaven podrobný problém EMM, který je poté je zapsán ve formě matice (tabulky), vložen do počítače a výpočet a analýza výsledků se provádí podle příslušného programu. i = 1, ..., m, (1.5)

j = 1, …, n. (1.6)

Vektor X = (X 1 , X 2 , …, X n), součásti x j které splňují omezení (1.2) a (1.3) [nebo (1.5) a (1.6) v minimálním problému] se nazývá přijatelné řešení nebo přijatelný plán LP úkoly. Sbírání všech platných plánů se nazývá mnoho platných plánů.

Kanonický forma problému lineárního programování je charakterizována skutečností, že obsahuje objektivní funkci, všechna omezení rovnost, všechny proměnné nejsou záporné.

Jakýkoli problém lineárního programování lze redukovat na problém lineárního programování v kanonické formě. K tomu je v obecném případě nutné umět redukovat problém maximalizace na problém minimalizace; přejít od omezení nerovnosti k omezením rovnosti a nahradit proměnné, které nedodržují podmínku non-negativity.

Pravidlo pro redukci problému lineárního programování na kanonickou formu je následující:

1) pokud je v původním problému požadováno určit maximum lineární funkce, pak by mělo být znaménko změněno a hledáno minimum této funkce;

2) pokud je pravá strana vazeb záporná, pak by toto omezení mělo být vynásobeno - 1;

3) pokud mezi omezeními existují nerovnosti, pak zavedením dalších proměnných nezáporných proměnných se transformují na rovnosti. Například další proměnné S j v omezeních typu menšího nebo rovného (£) se zadávají se znaménkem plus:

Další proměnné S j v typových omezeních větších nebo rovných (≥) se zadávají se znaménkem minus:

Chcete -li odstranit negativitu dalších proměnných - S j zavést umělé proměnné se znaménkem plus + M j s velmi velkými hodnotami.