Řešení úloh lineárního programování v Excelu - Abstrakt. Cvičení: Technologie pro řešení problémů lineárního programování pomocí aplikace Excel Application Finding Solutions

Odeslat svou dobrou práci do znalostní báze je jednoduché. Použijte níže uvedený formulář

Studenti, postgraduální studenti, mladí vědci, kteří využívají znalostní základnu ve svém studiu a práci, vám budou velmi vděční.

Vloženo na http://www.allbest.ru/

Vloženo na http://www.allbest.ru/

Soukromá vzdělávací instituce vyššího vzdělávání "St. Petersburg University of Management Technologies and Economics"

Katedra ekonomiky a managementu

TEST

Podle disciplíny: OPTIMÁLNÍ METODY ŘEŠENÍ

Dokončeno:

student (ka) 3 kurz, číslo skupiny 19731D/3-2

Kryuk Albina Vladimirovna

Dozorce:

Kandidát ekonomie, docent Zh.M. Kozlov.

Barnaul2016

• Úvod
• Závěr
• ÚVOD
• Řešení široké škály problémů v elektroenergetice a dalších odvětvích národního hospodářství je založeno na optimalizaci složitého souboru závislostí popsaných matematicky pomocí nějaké „objektivní funkce“ (TF). Podobné funkce lze napsat pro stanovení nákladů na palivo pro elektrárny, ztrátu elektřiny při její přepravě z elektrárny ke spotřebitelům a mnoho dalších problematických úkolů. V takových případech je nutné najít digitální filtr za určitých omezení uložených na jeho proměnné. Jestliže digitální filtr lineárně závisí na jeho základních proměnných a všechna omezení tvoří lineární systém rovnic a nerovnic, pak se taková konkrétní forma optimalizačního problému nazývá „problémy lineárního programování“.
• Témata testu "Řešení úloh lineárního programování v MS Excel", získání praktických dovedností v používání tabulek Microsoft Excel a řešení úloh optimalizace lineárního programování.

1. Typické optimalizační problémy a jejich ekonomické a matematické modely

Ekonomické a matematické modelování je proces vyjadřování ekonomických jevů matematickými modely. Ekonomický model je schematické znázornění ekonomického jevu nebo procesu pomocí vědecké abstrakce, odraz jejich charakteristických rysů. Matematické modely jsou hlavním nástrojem pro řešení optimalizačních úloh jakékoli činnosti. Tyto modely jsou v podstatě prostředkem plánovaných výpočtů. Jejich hodnota pro ekonomickou analýzu a optimalizaci rozhodování spočívá v tom, že nám umožňují odhadnout intenzitu plánovaných cílů, určit limitující skupinu zařízení, typy zdrojů, získat odhady jejich nedostatku atd. Matematické modelování ekonomických jevů a procesů umožňuje získat jasnou představu o studovaném objektu, charakterizovat a kvantitativně popsat jeho vnitřní strukturu a vnější vztahy. Model je podmíněným obrazem řídicího objektu /1/.

Ekonomicko-matematický model by měl být adekvátní realitě, odrážet podstatné aspekty a souvislosti zkoumaného objektu. Všimněme si hlavních rysů charakteristických pro konstrukci ekonomicko-matematického modelu jakéhokoli druhu. Proces modelování lze rozdělit do tří fází:

1) analýza teoretických zákonitostí obsažených ve studovaném jevu nebo procesu a empirických údajů o jeho struktuře a rysech; na základě takové analýzy se tvoří modely;

2) stanovení metod, kterými lze problém řešit;

3) analýza získaných výsledků.

Nejdůležitějším momentem první fáze modelování je jasná formulace konečného cíle sestavení modelu a také definice kritéria, podle kterého budou různá řešení srovnávána. Taková kritéria v systému řízení mohou být:

a) maximalizace příznivého účinku produktu při současném omezení celkových nákladů;

b) maximalizace zisků firmy za předpokladu, že nedojde ke snížení kvality zboží; c) snížení ceny zboží, pokud se nesníží jeho kvalita, nevzrostou náklady pro spotřebitele;

d) zvýšení produktivity práce, zlepšení využití zařízení nebo materiálů, zvýšení obratu pracovního kapitálu za předpokladu, že se nesníží kvalita zboží a nezhorší se další kritéria.

Optimalizačním kritériem tedy může být celá nebo jakákoli složka zisku, efektivita produktu, objem trhu za předpokladu, že se nezhorší ostatní složky.

Například rovnice účelové funkce (L) a systém omezení optimalizace zisku firmy (ačkoli autoři nemají žádná omezení na kvalitu zboží) budou mít následující podobu:

kde xj je počet vyrobených produktů j-tého typu ve fyzickém vyjádření;

Pj - zisk získaný z produkce jednotky produkce j-tého typu;

aij je míra spotřeby i-tého výrobního zdroje na výrobu jednotky j-tého typu produktu;

uj - zásoby i-tého typu produkčního zdroje za uvažované období.

Ne každý ekonomický úkol potřebuje svůj vlastní model. Některé procesy jsou z matematického hlediska stejného typu a lze je popsat stejnými modely. Například v lineárním programování, teorii front a dalších existují typické modely, které vedou k mnoha specifickým problémům.

Druhou etapou modelování ekonomických procesů je volba nejracionálnější matematické metody řešení problému. Například je známo mnoho metod pro řešení problémů lineárního programování: simplex, potenciály atd. Nejlepší model není ten nejsložitější a nejpodobnější reálnému jevu, ale ten, který vám umožní získat nejracionálnější řešení a nejvíce přesné ekonomické odhady. Přílišná podrobnost ztěžuje sestavení modelu a nadměrné zvětšování modelu vede ke ztrátě významných ekonomických informací, k nedostatečnému odrazu reality.

Třetí etapou modelování je komplexní analýza výsledku získaného při studiu ekonomického jevu. Konečným kritériem spolehlivosti a kvality modelu je praxe, soulad výsledků a závěrů s reálnými podmínkami, ekonomický obsah získaných odhadů. Pokud výsledky neodpovídají reálným podmínkám, pak je nutný rozbor příčin nesouladu, kterými může být nespolehlivost informací, nesoulad modelu s ekonomickými podmínkami apod. Na základě výsledků rozboru příčin nesrovnalosti nesoulad, ekonomický a matematický model se opraví a řešení úlohy se zopakuje.

Vyřešme typický optimalizační problém pomocí grafické metody

Některé společnosti vyrábí dvě sady trávníkových hnojiv: běžná a vylepšená. Běžná sada obsahuje 3 kg dusíku, 4 kg fosforu a 1 kg potašových hnojiv a vylepšená sada obsahuje 2 kg dusíku, 6 kg fosforu a 3 kg potašových hnojiv. Je známo, že pro některé trávníky je potřeba minimálně 10 kg dusíku, 20 kg fosforu a 7 kg potašových hnojiv. Běžná sada stojí 3 den. Jednotka a vylepšená - 4 den. Jednotka Jaké a kolik sad hnojiv by se mělo zakoupit, aby bylo možné efektivně živit půdu a minimalizovat náklady?

Sestavte ekonomicko-matematický model problému, uveďte potřebné komentáře k jeho prvkům a získejte řešení pomocí grafické metody. Co se stane, když problém vyřešíte na maximum, a proč?

Pojďme formulovat přímou optimalizační úlohu.

Nechť x1 je počet pravidelných sad hnojiv;

x2 - počet vylepšených sad hnojiv.

A pro některé trávníky je potřeba alespoň 10 kg dusíkatého hnojiva, proto:

3x1 + 2x2? 10

4x1 + 6x2? 20

Náklady na požadované sady hnojiv budou:

Získáme tak následující ekonomický a matematický model problému:

min(x) = 3x1 + 4x2

3x1 + 2x2? 10

4x1 + 6x2? 20

Sestrojme doménu řešení systému omezení. Chcete-li to provést, zvažte rovnosti a vytvořte jejich grafy - přímky.

1) 3x1 + 2x2? 10

3x1 + 2x2 = 10

3) x1 + 3x2? 7

Nerovnice není splněna, což znamená, že původní nerovnost odpovídá polorovině, která neobsahuje bod O(0;0).

x1 = 0 - osa OX2.

x2 = 0 - osa OX1.

Oblast řešení omezovacího systému se tedy nachází pouze v první čtvrtině kartézského souřadnicového systému.

Obr. 1. Grafické řešení ZLP

Najdeme společnou část všech sestrojených polorovin. Toto je konvexní stínovaná oblast.

Abychom našli optimální řešení problému, graficky znázorníme cílovou funkci:

(x) = d1x1 + d2x2

(x) = 3x1 + 4x2

K tomu sestrojíme vektor d, jehož začátek je v bodě (0;0) a konec v bodě (d1;d2).

A postavíme jednu z čar úrovně cílové funkce (to je čára, na které cílová funkce nabývá konstantní hodnoty).

Pro určení minima této funkce posuneme linii hladiny ve směru opačném k vektoru d a vidíme, že se naposledy dotýká oblasti řešení v bodě B, kde bude dosaženo min(x).

Určete souřadnice bodu B:

3x1 + 2x2 = 10 *(-3)

4x1 + 6x2 = 20

9x1 - 6x2 = -30

4x1 + 6x2 = 20

Sečteme rovnice člen po členu a dostaneme:

(x) \u003d 3 * 2 + 4 * 2 \u003d 14 (den. jednotky)

Abyste minimalizovali náklady na hnojivo, musíte si koupit 2 běžné sady hnojiv a 2 vylepšené sady hnojiv. Současně budou minimální náklady na nákup hnojiv 14 peněžních jednotek. microsoft excel programovací matematika

Pokud tento problém vyřešíme na maximum, pak nenajdeme konečné optimum, protože cílová funkce je neomezená, oblast řešení systému omezení je nekonečná.

2. Problémy lineárního programování, řešení pomocí MS Excel

Lineární programování je obor, ze kterého se začala rozvíjet disciplína „matematické programování“. Pojem „programování“ v názvu disciplíny nemá nic společného s pojmem „programování (tedy psaní programů) pro počítače“, protože disciplína „lineární programování“ vznikla ještě před dobou, kdy byly počítače široce používány při řešení matematických, inženýrské problémy, ekonomické a jiné úkoly. Pojem „lineární programování“ vznikl v důsledku nepřesného překladu anglického „lineárního programování“. Jedním z významů slova „programování“ je vytváření plánů, plánování. Správný překlad „lineárního programování“ by tedy nebyl „lineární programování“, ale „lineární plánování“, které přesněji odráží obsah disciplíny. Nicméně termín lineární programování, nelineární programování atp. se staly běžnou součástí naší literatury. Úlohy lineárního programování jsou vhodným matematickým modelem pro velké množství ekonomických problémů (plánování výroby, spotřeba materiálu, doprava atd.). Použití metody lineárního programování je důležité a cenné – optimální varianta se vybírá z poměrně značného množství alternativních možností. Také všechny ekonomické problémy řešené pomocí lineárního programování se vyznačují alternativními řešeními a určitými omezujícími podmínkami.
V tabulkách aplikace Excel můžete pomocí funkce najít řešení vyhledat hodnotu v cílové buňce a změnit hodnotu proměnných. V tomto případě můžete pro každou proměnnou nastavit omezení, například horní mez. Před zahájením hledání řešení je nutné v modelu jasně formulovat řešený problém, tzn. určit podmínky, které jsou při optimalizaci splněny. Výchozím bodem při hledání optimálního řešení je výpočtový model vytvořený v pracovním listu. Program pro hledání řešení potřebuje následující data. 1. Cílová buňka je buňka ve výpočtovém modelu, jejíž hodnota má být maximalizována, minimalizována nebo rovna určité zadané hodnotě. Musí obsahovat vzorec, který přímo nebo nepřímo odkazuje na upravované buňky, nebo musí být sám o sobě proměnlivý. 2. Hodnoty v buňkách, které mají být změněny, budou postupně (iterovány), dokud nebude v cílové buňce získána požadovaná hodnota. Tyto buňky proto musí přímo nebo nepřímo ovlivnit hodnotu cílové buňky. 3. Můžete nastavit limity a okrajové podmínky pro cílovou buňku i buňku, kterou chcete změnit. Můžete také nastavit limity pro další buňky. Přímo nebo nepřímo přítomné v modelu. Program poskytuje možnost nastavit speciální parametry, které určují proces hledání řešení. Po nastavení všech potřebných parametrů můžete začít hledat řešení. Funkce hledání řešení vygeneruje na základě výsledků své práce tři sestavy, které lze označit v sešitu Omezení jsou podmínky, které musí splňovat aparát pro vyhledávání řešení při optimalizaci modelu.

Studium literatury ukázalo, že:

1. Lineární programování je jednou z prvních a nejdůkladněji prostudovaných částí matematického programování. Právě lineární programování byl úsek, ze kterého se začala vyvíjet samotná disciplína „matematické programování“.

Lineární programování je nejpoužívanější optimalizační technika. Problémy lineárního programování zahrnují:

racionální využívání surovin a materiálů; úkoly optimalizace řezání;

· optimalizace výrobního programu podniků;

Optimální umístění a koncentrace výroby;

sestavení optimálního plánu dopravy, dopravního provozu;

řízení výrobních zásob;

a mnoho dalších spadajících do oblasti optimálního plánování.

2. Grafická metoda je celkem jednoduchá a přehledná pro řešení úloh lineárního programování se dvěma proměnnými. Je založen na geometrické reprezentaci proveditelných řešení a digitálním filtru problému.

Podstata grafické metody je následující. Ve směru (proti směru) vektoru v ODR se provádí hledání optimálního bodu. Optimální bod je bod, kterým prochází úrovňová linie, odpovídající největší (nejmenší) hodnotě funkce. Optimální řešení se vždy nachází na hranici ODT, např. u posledního vrcholu polygonu ODT, kterým prochází cílová linie, nebo na celé její straně.

ZÁVĚR

Při správné formulaci problému plánování výroby a dostupnosti základních parametrů výroby dokážeme najít plán výroby, který dosáhne maximálního zisku.

Díky softwarovému produktu Excel, který je součástí balíku MS Office, se řešení našich úloh urychluje několikanásobně. A díky přesným matematickým výpočtům tohoto softwaru můžeme bezesporu najít ty nejpřesnější výsledky výzkumu.

Hostováno na Allbest.ru

Podobné dokumenty

Stručné informace o tabulkách MS Excel. Řešení úlohy lineárního programování. Řešení problému ekonomické optimalizace pomocí nástrojů Microsoft Excel, na příkladu "problém dopravy". Vlastnosti návrhu dokumentu MS Word.

semestrální práce, přidáno 27.08.2012


Historie vývoje a funkcí lineárního programování. Studium podmínek typických úloh a schopností tabulkového procesoru. Řešení problémů s dietou, plánem výroby, nářezem materiálu a racionální přepravou zboží v MS Excel.

semestrální práce, přidáno 28.04.2014


Principy řešení úloh lineárního programování v prostředí excelových tabulek, v prostředí balíku Mathcad. Jak vyřešit problém se zadáním v prostředí tabulkového procesoru Excel. Analýza ekonomických dat pomocí Paretových diagramů, vyhodnocení výsledků.

laboratorní práce, přidáno 26.10.2013


Algoritmus pro řešení úloh lineárního programování simplexovou metodou. Konstrukce matematického modelu úlohy lineárního programování. Řešení úlohy lineárního programování v Excelu. Nalezení zisku a optimální plán výroby.

semestrální práce, přidáno 21.03.2012


Prostudování a posílení v praxi všech aspektů grafické metody řešení úloh lineárního programování na produkci časopisů "Automechanic" a "Instrument". Konstrukce matematického modelu. Řešení problémů pomocí excelové tabulky.

semestrální práce, přidáno 6.10.2014


Obecná koncepce a charakteristika úlohy lineárního programování. Řešení dopravního problému pomocí MS Excel. Doporučení pro řešení optimalizačních problémů pomocí doplňku „Hledat řešení“. Duální problém lineárního programování.

práce, přidáno 20.11.2010


Analýza metody lineárního programování pro řešení problémů řízení optimalizace. Grafická metoda řešení úlohy lineárního programování. Kontrola optimálního řešení v prostředí MS Excel pomocí doplňku „Vyhledat řešení“.

semestrální práce, přidáno 29.05.2015


Vývoj tabulek v Excelu pomocí metod lineárního programování za účelem optimalizace nákladů na zdroje a zásoby na výrobu produktů: určování proměnných, struktura účelové funkce, sestavení matematického modelu a blokových diagramů pro řešení problémů.

semestrální práce, přidáno 06.07.2010


Metody řešení problémů lineárního programování: plánování výroby, příděl, problémy řezání materiálů a dopravy. Vývoj ekonomicko-matematického modelu a řešení problémů pomocí počítačové simulace.

semestrální práce, přidáno 13.03.2015


Grafické řešení problémů. Sestavení matematického modelu. Stanovení maximální hodnoty účelové funkce. Řešení simplexní metodou s umělým základem úlohy kanonického lineárního programování. Kontrola optimálnosti řešení.

Pro řešení problémů lineárního programování simplexní metoda v prostředí MS Excel se buňky plní počátečními údaji v číselném režimu a vzorci matematického modelu.

MS Excel umožňuje získat optimální řešení bez omezení dimenze soustavy nerovnic účelové funkce.

Vyřešme problematiku vyráběných výrobků simplexovou metodou pomocí doplňku "Hledat řešení" v MS Excel.

1. Vyplňte tabulku Excel v číselném režimu (obr. 1)

2. Vyplňte tabulku Excel v režimu vzorce (obr. 2)

Obr.1 Tabulka v číselném režimu

Obr.1 Tabulka v režimu vzorce

Zde: В9:С9 - výsledek (optimální počet produktů každého typu);

В6:С6 – koeficienty účelové funkce;

В10 – hodnota objektivní funkce;

В3:С5 - koeficienty omezení;

D12:D14 - pravá strana omezení;

B12:B14 - vypočtené (skutečné) hodnoty levé strany omezení.

Vyřešme problém pomocí příkazu Data/Search for Solution. Na obrazovce se objeví dialogové okno Najít řešení.

V poli Nastavit funkci cíle se zobrazí odkaz na aktivní buňku, tzn. na B10. A tento odkaz je absolutní. V sekci Equal nastavte přepínač na Maximum (minimum) hodnotu v závislosti na účelové funkci. Omezení se nastavují pomocí tlačítka Přidat, které vyvolá dialogové okno pro jejich zadání Přidání omezení.

Ve vstupním poli Cell Reference: zadejte adresu buňky obsahující vzorec na levé straně omezení. Poté se ze seznamu vybere poměrový znak. Pole Omezení určuje adresu buňky obsahující pravou stranu omezení. Klikněte na tlačítko Přidat a opakujte až do dalšího omezení. Po zadání všech omezení klepněte na OK.

Protože všechny proměnné nesou podmínky nezápornosti, jejich pozitivita se nastavuje pomocí tlačítka Parametry v dialogovém okně Hledat řešení. Po kliknutí na něj se na obrazovce objeví okno Možnosti hledání řešení.

Zaškrtněte políčko Udělat proměnné bez omezení na nezáporné a vyberte Metoda řešení Hledání řešení lineárních úloh pomocí simplexní metody. Klikněte na tlačítko Najít řešení.

Excel zobrazí okno Výsledky hledání řešení se zprávou, že řešení bylo nalezeno nebo že nemůže najít vhodné řešení.

Pokud byly výpočty úspěšné, Excel zobrazí následující souhrnné okno. Mohou být ponechány nebo opuštěny. Kromě toho můžete získat jeden ze tří typů přehledů (Výsledky , Udržitelnost , Limity), což vám umožní lépe porozumět výsledkům, včetně posouzení jejich spolehlivosti.

Po nalezeném řešení se v buňkách B9: C9 objeví optimální počet produktů každého typu.

Při ukládání reportu zvolte - Report by results (obr. 3).

Ze zprávy je vidět, že zdroj 1 není plně využit o 150 kg, zatímco zdroj 2 a 3 jsou plně využity.

Výsledkem byl optimální plán, ve kterém musí být vyrobeny výrobky 1. typu v množství 58 kusů a výrobky 2. typu v množství 42 kusů. Zároveň je zisk z jejich prodeje maximální a činí 4660 tisíc rublů.

Obr.3 Zpráva o výsledcích

1. Osobní a rychlíky, složené z vyhrazených místenek, kupé a měkkých vozů, odjíždějí denně z nástupní stanice. Počet míst ve voze s vyhrazeným místem je 54, v oddílovém voze - 36, v měkkém voze - 18. Tabulka ukazuje složení jednotlivých typů vlaků a počet vozů různých typů ve vozovém parku. Určete počet rychlíků a osobních vlaků, které je třeba denně sestavit tak, aby počet přepravených cestujících byl maximální.

Řešení dopravních problémů

Přepravní úkoly jsou úkoly stanovení optimálního plánu přepravy zboží z daných výchozích míst do daných míst spotřeby.