Objektivní funkce- reálná nebo celočíselná funkce několika proměnných, která podléhá optimalizaci (minimalizace nebo maximalizace) za účelem vyřešení nějakého optimalizačního problému. Termín používaný v matematickém programování, operačním výzkumu, lineárním programování, teorii statistická řešení a další oblasti matematiky především aplikovaného charakteru, i když cílem optimalizace může být i řešení samotného matematického problému. kromě Objektivní funkce V optimalizačním problému mohou být pro proměnné specifikována omezení ve formě systému rovností nebo nerovností. V obecný případ argumenty cílové funkce lze zadat na libovolných množinách.
Příklady
Hladké funkce a soustavy rovnic
Problém řešení libovolné soustavy rovnic
( F 1 (x 1, x 2, …, x M) = 0 F 2 (x 1, x 2, …, x M) = 0 … F N (x 1, x 2, …, x M) = 0 ( \displaystyle \left\((\begin(matrix)F_(1)(x_(1),x_(2),\ldots ,x_(M))=0\\F_(2)(x_(1),x_ (2),\ldots ,x_(M))=0\\\ldots \\F_(N)(x_(1),x_(2),\ldots ,x_(M))=0\end(matice) )\že jo.)
lze formulovat jako problém minimalizace účelové funkce
S = ∑ j = 1 N F j 2 (x 1 , x 2 , … , x M) (1) (\displaystyle S=\sum _(j=1)^(N)F_(j)^(2)( x_(1),x_(2),\ldots ,x_(M))\qquad (1))
Pokud jsou funkce hladké, lze problém minimalizace vyřešit pomocí gradientních metod.
Pro jakoukoli hladkou účelovou funkci lze parciální derivace vzhledem ke všem proměnným přirovnat k 0 (\displaystyle 0). Optimum účelové funkce bude jedním z řešení takové soustavy rovnic. V případě funkce (1) (\displaystyle (1)) to bude soustava rovnic metody nejmenší čtverce(MNC). Každé řešení původního systému je řešením systému nejmenších čtverců. Pokud je původní systém nekonzistentní, pak systém nejmenších čtverců, který má vždy řešení, nám umožňuje získat přibližné řešení původního systému. Počet rovnic v systému nejmenších čtverců se shoduje s počtem neznámých, což někdy usnadňuje řešení společných počátečních soustav.
Lineární programování
Ostatním slavný příkladÚčelová funkce je lineární funkce, která vzniká v úlohách lineárního programování. Na rozdíl od kvadratické účelové funkce je optimalizace lineární funkce možná pouze tehdy, pokud existují omezení v podobě systému lineárních rovností nebo nerovnic.
Kombinatorická optimalizace
Typickým příkladem kombinatorické objektivní funkce je objektivní funkce problému obchodního cestujícího. Tato funkce je rovna délce hamiltonovského cyklu na grafu. Je definován na množině permutací n − 1 (\displaystyle n-1) vrcholů grafu a je určen maticí délek hran grafu. Přesné řešení takových problémů často spočívá ve výčtu možností.
Kapitola 1. Vysvětlení hlavního problému lineárního programování
Lineární programování
Lineární programování je odvětví matematického programování, které studuje metody řešení extrémních problémů, které se vyznačují lineární závislost mezi proměnnými a lineárním testem. Tyto problémy nacházejí široké uplatnění v různých oblastech lidské činnosti. Systematické studium problémů tohoto typu začalo v letech 1939–1940. v dílech L.V. Kantorovič.
Matematické problémy lineárního programování zahrnují studie specifických výrobních a ekonomických situací, které jsou v té či oné podobě interpretovány jako problémy optimálního využití omezených zdrojů.
Spektrum problémů řešených metodami lineárního programování je poměrně široké. Jsou to například:
problém optimálního využití zdrojů při plánování výroby;
problém se směsí (plánování složení produktu);
problém najít optimální kombinaci různé typy produkty pro skladování ve skladech (řízení zásob nebo);
dopravní úkoly (analýza umístění podniku, pohyb zboží).
Lineární programování je nejrozvinutější a nejrozšířenější částí matematického programování (kromě toho sem patří: celočíselné, dynamické, nelineární, parametrické programování). To je vysvětleno následovně:
matematické modely velkého množství ekonomických problémů jsou lineární s ohledem na požadované proměnné;
Tento typ problému je v současnosti nejvíce studován. Navrženo pro něj speciální metody, s jehož pomocí jsou tyto problémy řešeny, a odpovídající počítačové programy;
mnoho problémů lineárního programování, které byly vyřešeny, našlo široké uplatnění;
Některé problémy, které v původní formulaci nejsou lineární, se po řadě dalších omezení a předpokladů mohou stát lineárními nebo je lze redukovat do takové podoby, že je lze řešit metodami lineárního programování.
Ekonomický a matematický model jakéhokoli problému lineárního programování zahrnuje: objektivní funkci, optimální hodnotu které (maximum nebo minimum) je třeba najít; omezení v podobě systému lineární rovnice nebo nerovnosti; požadavek nezápornosti proměnných.
V obecný pohled model je napsán takto:
Objektivní funkce
(1.1) s omezeními
(1.2) požadavky na nezápornost
(1.3) kde X j– proměnné (neznámé);
- koeficienty úlohy lineárního programování.
Problém je najít optimální hodnotu funkce (1.1) za podmínek (1.2) a (1.3).
Systém omezení (1.2) se nazývá funkční omezení problému a omezení (1.3) se nazývají přímé.
Vektor, který splňuje podmínky (1.2) a (1.3), se nazývá přípustné řešení (plán) úlohy lineárního programování. Plán, ve kterém funkce (1.1) dosáhne své maximální (minimální) hodnoty, se nazývá optimální.
1.2. Simplexní metoda pro řešení úloh lineárního programování
Simplexovou metodu vyvinul a poprvé použil k řešení úloh v roce 1947 americký matematik J. Danzig.
Úlohy dvourozměrného lineárního programování jsou řešeny graficky. Pro případ N=3 můžeme uvažovat trojrozměrný prostor a účelová funkce dosáhne své optimální hodnoty v jednom z vrcholů mnohostěnu.
Přípustné řešení (přípustný plán) úlohy LP zadané ve standardním tvaru je uspořádaná množina čísel (x1, x2, ..., xn) splňující omezení; je to bod v n-rozměrném prostoru.
Množina přípustných řešení tvoří oblast přípustných řešení (ADS) úlohy LP. ODR je konvexní mnohostěn (polygon).
Obecně, když problém zahrnuje N-neznámé, můžeme říci, že oblast proveditelných řešení, definovaná soustavou omezujících podmínek, je reprezentována konvexním mnohostěnem v n-rozměrném prostoru a je dosaženo optimální hodnoty účelové funkce. v jednom nebo více vrcholech.
Základní řešení je řešení, ve kterém jsou všechny volné proměnné rovny nule.
Podpůrné řešení je základní nezáporné řešení. Podpůrný roztok může být nedegenerovaný a degenerovaný. Referenční řešení se nazývá nedegenerované, pokud se počet jeho nenulových souřadnic rovná hodnosti systému, jinak je degenerované.
Přípustné řešení, při kterém účelová funkce dosáhne své krajní hodnoty, se nazývá optimální a označuje se 
.
Je velmi obtížné vyřešit tyto problémy graficky, když je počet proměnných větší než 3. Existuje univerzální způsob řešení problémů lineárního programování, který se nazývá simplexová metoda.
Simplexová metoda je univerzální metoda pro řešení úloh LP, což je iterativní proces, který začíná jedním řešením a při hledání nejlepší možnosti se pohybuje podél rohových bodů oblasti proveditelných řešení, dokud nedosáhne optimální hodnoty.
Lze jej použít k řešení jakéhokoli problému lineárního programování.
Simplexová metoda je založena na myšlence postupného zlepšování výsledného řešení.
Geometrickým významem simplexové metody je sekvenční přechod z jednoho vrcholu omezujícího mnohostěnu do sousedního, ve kterém účelová funkce nabývá nejlepší (nebo alespoň ne nejhorší) hodnoty, dokud není nalezeno optimální řešení - vrchol, kde optimální hodnota je dosažena funkcí cíle (pokud má problém konečné optimum).
Tím, že mají systém omezení zredukovaný na kanonickou formu (všechna funkční omezení mají formu rovnosti), najdou jakékoli základní řešení tohoto systému a starají se pouze o jeho co nejjednodušší nalezení. Pokud se první nalezené základní řešení ukáže jako proveditelné, pak se zkontroluje jeho optimálnost. Pokud není optimální, pak se přechází k jinému, nutně přípustnému, základnímu řešení. Simplexová metoda zaručuje, že s tímto novým řešením se objektivní funkce, pokud nedosáhne optima, k ní přiblíží (nebo se od ní alespoň nevzdálí). Totéž se provádí s novým proveditelným základním řešením, dokud není nalezeno řešení, které je optimální.
Proces aplikace simplexové metody zahrnuje implementaci jejích tří hlavních prvků:
způsob pro stanovení jakéhokoli počátečního proveditelného základního řešení problému;
pravidlo přechodu k nejlepšímu (přesněji ne horšímu) řešení;
kritérium pro kontrolu optimálnosti nalezeného řešení.
Simplexová metoda zahrnuje řadu fází a může být formulována ve formě jasného algoritmu (jasné instrukce pro provádění sekvenčních operací). To vám umožní úspěšně jej naprogramovat a implementovat na počítači. Problémy s malým počtem proměnných a omezení lze řešit ručně pomocí simplexní metody.
6.1.Úvod
Optimalizace. Část 1
Metody optimalizace vám umožňují vybrat si nejlepší možnost návrhy od všech možné možnosti. V minulé roky tyto metody byly uvedeny velká pozornost a v důsledku toho byla vyvinuta řada vysoce účinných algoritmů, které umožňují najít optimální variantu návrhu pomocí počítače. Tato kapitola nastiňuje základy teorie optimalizace, zkoumá principy konstrukce algoritmů pro optimální řešení, popisuje nejznámější algoritmy a analyzuje jejich výhody a nevýhody.
6.2.Základy teorie optimalizace
Termín „optimalizace“ v literatuře označuje proces nebo sekvenci operací, které umožňují získat rafinované řešení. Přestože konečným cílem optimalizace je najít nejlepší nebo „optimální“ řešení, člověk se obvykle musí spokojit spíše se zlepšováním známých řešení než s jejich zdokonalováním. Optimalizace je proto chápána spíše jako touha po dokonalosti, které nemusí být dosaženo.
Uvážíme-li nějaký libovolný systém popsaný m rovnic s n neznámými, můžeme rozlišit tři hlavní typy problémů. Jestliže m=n, problém se nazývá algebraický. Tento problém má obvykle jedno řešení. Je-li m>n, pak je problém přeurčen a zpravidla nemá řešení. Nakonec pro m
Než začneme diskutovat o otázkách optimalizace, představíme si řadu definic.
Designové parametry
Tento pojem označuje nezávisle proměnné parametry, které zcela a jednoznačně určují řešený návrhový problém. Konstrukční parametry jsou neznámé veličiny, jejichž hodnoty se počítají během procesu optimalizace. Jako parametry návrhu mohou sloužit jakékoli základní nebo odvozené veličiny, které slouží ke kvantitativnímu popisu systému. Ano, může být neznámé hodnoty délka, hmotnost, čas, teplota. Počet návrhových parametrů charakterizuje stupeň složitosti daného konstrukčního problému. Obvykle se počet návrhových parametrů označuje n a samotné návrhové parametry x s odpovídajícími indexy. Tedy n návrhových parametrů tohoto problému bude označeno
X1, x2, x3,...,xn.
Objektivní funkce
Je to výraz, jehož hodnotu se inženýr snaží dosáhnout maxima nebo minima. Objektivní funkce umožňuje kvantitativně porovnat dvě alternativní řešení. Z matematického hlediska účelová funkce popisuje nějakou (n+1)-rozměrnou plochu. Jeho hodnota je určena konstrukčními parametry
M=M(x 1, x 2,..., x n).
Příklady objektivních funkcí, které se často vyskytují ve strojírenské praxi, jsou náklady, hmotnost, pevnost, rozměry, účinnost. Pokud existuje pouze jeden návrhový parametr, pak účelová funkce může být reprezentována křivkou v rovině (obr. 6.1). Pokud existují dva parametry návrhu, pak bude účelová funkce znázorněna jako plocha v trojrozměrném prostoru (obr. 6.2). Se třemi nebo více parametry návrhu se povrchy určené účelovou funkcí nazývají hyperplochy a nelze je zobrazit.
manželství běžnými prostředky. Topologické vlastnosti povrchu účelové funkce hrají v optimalizačním procesu velkou roli, protože na nich závisí výběr nejúčinnějšího algoritmu.
Objektivní funkce může v některých případech nabývat nejneočekávanějších forem. Například není vždy možné to vyjádřit
Obr. 1. Jednorozměrná účelová funkce.
6.2 Dvourozměrná účelová funkce.
uzavřený matematický tvar, v ostatních případech může
představují po částech hladkou funkci. Specifikace objektivní funkce může někdy vyžadovat tabulku technických údajů (například tabulku stavu vodní páry) nebo může vyžadovat experiment. V některých případech nabývají parametry návrhu pouze celočíselné hodnoty. Příkladem může být počet zubů v převodovka nebo počet šroubů v přírubě. Někdy mají parametry návrhu pouze dva významy – ano nebo ne. Kvalitativní parametry, jako je spokojenost kupujícího, který si produkt zakoupil, spolehlivost, estetika, je obtížné zohlednit v procesu optimalizace, protože je téměř nemožné je kvantitativně charakterizovat. Ať je však účelová funkce prezentována jakkoli, musí se jednat o jednoznačnou funkci návrhových parametrů.
Řada optimalizačních problémů vyžaduje zavedení více než jedné účelové funkce. Někdy se může ukázat, že jeden z nich není kompatibilní s druhým. Příkladem je konstrukce letadla, kde je současně požadována maximální pevnost, minimální hmotnost a minimální náklady. V takových případech musí projektant zavést systém priorit a každé účelové funkci přiřadit určitý bezrozměrný multiplikátor. V důsledku toho se objeví „kompromisní funkce“, která umožňuje použití jedné složené cílové funkce během procesu optimalizace.
Hledání minima a maxima
Některé optimalizační algoritmy jsou navrženy k nalezení maxima, jiné k nalezení minima. Bez ohledu na typ řešeného extrémního problému však můžete použít stejný algoritmus, protože problém minimalizace lze snadno změnit na problém maximálního hledání obrácením znaménka účelové funkce. Tato technika je znázorněna na obr. 6.3.
Designový prostor
Toto je název oblasti definované všemi n návrhovými parametry. Designový prostor není tak velký, jak by se mohlo zdát, protože je obvykle omezen řadou
stavy související s fyzikální podstatou problému. Omezení mohou být tak silná, že problém nebude mít žádný
Obr.6.3.Změna znaménka účelové funkce na opak
maximální úkol se změní na minimální úkol.
uspokojivé řešení. Omezení se dělí do dvou skupin: omezení – rovnost a omezení – nerovnost.
Omezení - Rovnosti
Omezení – rovnosti – jsou závislosti mezi parametry návrhu, které je třeba vzít v úvahu při hledání řešení. Odrážejí přírodní zákony, ekonomiku, právo, převládající vkus a dostupnost potřebné materiály. Počet omezení - rovnosti může být libovolný. Vypadají jako
C1 (x 1, x 2,...,x n)=0,
C2 (x 1, x 2,...,x n)=0,
..................
Cj(x1,x2,...,xn)=0.
Pokud lze některý z těchto vztahů vyřešit s ohledem na jeden z parametrů návrhu, pak to umožňuje vyloučit tento parametr z procesu optimalizace. Tím se snižuje počet rozměrů návrhového prostoru a zjednodušuje se řešení problému.
Omezení – nerovnosti
Jedná se o speciální typ omezení vyjádřený nerovnostmi. Obecně jich může být tolik, kolik chcete, a všechny mají formu
z 1 r 1 (x 1, x 2,...,x n) Z 1
z 2 r 2 (x 1, x 2,...,x n) Z 2
.......................
z k r k (x 1, x 2,...,x n) Z k
Je třeba poznamenat, že velmi často se díky omezením dosáhne optimální hodnoty účelové funkce ne tam, kde má její povrch nulový gradient. Často nejlepší řešení odpovídá jedné z hranic designového prostoru.
Lokální optimum
Toto je název bodu v návrhovém prostoru, ve kterém se nachází účelová funkce nejvyšší hodnotu ve srovnání s jeho hodnotami ve všech ostatních bodech v jeho bezprostřední blízkosti.
Obr. 6.4. Libovolná účelová funkce může mít několik
lokální optima.
Na Obr. Obrázek 6.4 ukazuje jednorozměrnou účelovou funkci, která má dvě lokální optima. Návrhový prostor často obsahuje mnoho lokálních optim a je třeba dbát na to, aby se první nezaměnilo za optimální řešení problému.
Globální optimum
Globální optimum je optimálním řešením pro celý designový prostor. Je lepší než všechna ostatní řešení odpovídající místnímu optimu a je to, co projektant hledá. Je možné, že se v nich nachází několik stejných globálních optim různé části designový prostor. Jak vzniká optimalizační problém, nejlépe ilustruje příklad.
Příklad 6.1
Předpokládejme, že potřebujete navrhnout obdélníkový kontejner o objemu 1 m určený pro přepravu nebaleného vlákna. Je žádoucí, aby na výrobu takových nádob bylo vynaloženo co nejméně materiálu (za předpokladu konstantní tloušťky stěny to znamená, že povrch by měl být minimální), protože to bude levnější. Aby bylo možné kontejner pohodlně vyzvednout vysokozdvižným vozíkem, musí být jeho šířka minimálně 1,5 m.
Zformulujme tento problém ve formě vhodné pro použití optimalizačního algoritmu.
Designové parametry: x 1, x 2, x 3.
Cílovou funkcí (kterou je třeba minimalizovat) je plocha bočního povrchu nádoby:
A=2(x 1 x 2 +x 2 x 3 +x 1 x 3), m2.
Omezení – rovnost:
Objem = x 1 x 2 x 3 = 1m3.
Omezení – nerovnost:
Problémy lineárního programování
Lineární programování (LP) je jedním z oborů matematického programování - disciplína, která studuje extremální (optimalizační) problémy a vyvíjí metody jejich řešení.
Problém s optimalizací je matematický problém, který spočívá v nalezení optimální (tj. maximální nebo minimální) hodnoty účelové funkce a hodnoty proměnných musí patřit do určitého rozsahu přijatelných hodnot (APV).
Obecně platí, že formulace extremního problému matematického programování spočívá v určení největšího resp nejnižší hodnota volaná funkce cílová funkce, za podmínek (omezení), kde a jsou dány funkce a jsou jim dány konstantní hodnoty. V tomto případě omezení v podobě rovností a nerovností určují množinu (plochu) přípustných řešení (ADS), a jsou tzv. konstrukční parametry.
Úlohy matematického programování se podle typu funkcí dělí do řady tříd (lineární, nelineární, konvexní, celočíselné, stochastické, dynamické programování atd.).
V obecný pohled problém LP má následující podobu:
, (5.1)
, , (5.2)
, 
, (5.3)
kde , , jsou dané konstantní hodnoty.
Funkce (5.1) se nazývá účelová funkce; systémy (5.2), (5.3) – systém omezení; podmínka (5.4) – podmínka nezápornosti návrhových parametrů.
Množina návrhových parametrů splňujících omezení (5.2), (5.3) a (5.4) se nazývá přijatelné řešení nebo plán.
Optimální řešení nebo optimální plánÚloha LP se nazývá přípustné řešení, ve kterém účelová funkce (5.1) nabývá optimální (maximální nebo minimální) hodnoty.
Standardní úkol LP je problém nalezení maximální (minimální) hodnoty účelové funkce (5.1) za podmínky (5.2) a (5.4), kde , , tzn. těch. omezení pouze ve formě nerovností (5.2) a všechny parametry návrhu splňují podmínku nezápornosti a neexistují žádné podmínky ve formě rovnosti:
,
, , (5.5)
.
Kanonický (hlavní) úkol LP je problém nalezení maximální (minimální) hodnoty účelové funkce (5.1) za podmínky (5.3) a (5.4), kde , , tzn. těch. omezení pouze ve formě rovností (5.3) a všechny parametry návrhu splňují podmínku nezápornosti a neexistují žádné podmínky ve formě nerovností:
,
.
Kanonický problém LP lze také zapsat v maticové a vektorové formě.
Maticový tvar kanonické úlohy LP má následující tvar:
Vektorová forma kanonické úlohy LP.
Sestrojme na rovině množinu možných řešení soustavy lineárních nerovnic a geometricky nalezneme minimální hodnotu účelové funkce.
Stavíme přímky v souřadnicovém systému x 1 x 2
Najdeme poloroviny definované systémem. Protože nerovnosti soustavy jsou splněny pro libovolný bod v odpovídající polorovině, stačí je zkontrolovat pro libovolný jeden bod. Použijeme bod (0;0). Dosadíme její souřadnice do první nerovnosti soustavy. Protože , pak nerovnost definuje polorovinu, která neobsahuje bod (0;0). Podobně definujeme zbývající poloroviny. Množinu možných řešení najdeme jako společnou část výsledných polorovin - to je zastíněná plocha.
Sestrojíme vektor a na něj kolmou přímku nulové úrovně.
Pohybujeme-li se přímkou (5) ve směru vektoru, vidíme, že maximální bod oblasti bude v bodě A průsečíku přímky (3) a přímky (2). Najdeme řešení soustavy rovnic:
To znamená, že jsme dostali bod (13;11) a.
Pohybujeme-li se přímkou (5) ve směru vektoru, vidíme, že minimální bod oblasti bude v bodě B průsečíku přímky (1) a přímky (4). Najdeme řešení soustavy rovnic:
To znamená, že jsme dostali bod (6;6) a.
2. Nábytkářská společnost vyrábí kombinované skříně a počítačové stoly. Jejich výroba je limitována dostupností surovin (kvalitní desky, kování) a provozní dobou strojů, které je zpracovávají. Každá skříň vyžaduje 5 m2 desek, pro stůl - 2 m2. Kování stojí 10 dolarů za jednu skříň a 8 dolarů za jeden stůl. Společnost může od svých dodavatelů získat až 600 m2 desek měsíčně a příslušenství v hodnotě 2 000 USD. Každá skříň vyžaduje 7 hodin provozu stroje a stůl vyžaduje 3 hodiny. Celkem lze měsíčně využít 840 provozních hodin stroje.
Kolik kombinovaných skříní a počítačových stolů by měla společnost vyrobit za měsíc, aby maximalizovala zisk, pokud jedna skříň přináší zisk 100 USD a každý stůl přináší 50 USD?
- 1. Skládat matematický model problém a vyřešit jej pomocí simplexní metody.
- 2. Vytvořte matematický model duální úlohy, zapište její řešení na základě řešení původního.
- 3. Stanovte míru vzácnosti použitých zdrojů a zdůvodněte ziskovost optimálního plánu.
- 4. Prozkoumat možnosti dalšího zvyšování produkce produkce v závislosti na využití každého typu zdroje.
- 5. Posoudit proveditelnost zavedení nového typu produktu - regálů, pokud výroba jednoho regálu stojí 1 m 2 desek a příslušenství v hodnotě 5 $ a je nutné vynaložit 0,25 hodiny provozu stroje a zisk z prodeje jedna police stojí 20 dolarů.
- 1. Vytvořme matematický model pro tento problém:
Označme x 1 objem výroby skříní a x 2 objem výroby stolů. Vytvořme systém omezení a cílovou funkci:
Úlohu řešíme simplexovou metodou. Zapišme to v kanonické podobě:
Zapišme data úlohy ve formě tabulky:
stůl 1
Protože Nyní jsou všechny delty větší než nula, pak je další zvýšení hodnoty cílové funkce f nemožné a získali jsme optimální plán.
Úvod
Současná etapa lidského vývoje se vyznačuje tím, že věk energie je nahrazován věkem informatiky. Dochází k intenzivnímu zavádění nových technologií do všech sfér lidské činnosti. Existuje skutečný problém přechodu k informační společnosti, pro který by se rozvoj vzdělávání měl stát prioritou. Mění se i struktura znalostí ve společnosti. Stále důležitější pro praktický život získat základní znalosti, které přispívají ke kreativnímu rozvoji jedince. Důležitá je také konstruktivnost získaných znalostí a schopnost je strukturovat v souladu s cílem. Na základě poznatků se tvoří nové informační zdroje společnost. Utváření a získávání nových znalostí by mělo být založeno na přísné metodice systémového přístupu, v rámci kterého zaujímá zvláštní místo modelový přístup. Možnosti modelového přístupu jsou nesmírně rozmanité, a to jak z hlediska použitých formálních modelů, tak i ve způsobech implementace metod modelování. Fyzikální modelování umožňuje získat spolehlivé výsledky pro poměrně jednoduché systémy.
V současné době není možné pojmenovat oblast lidské činnosti, ve které by se metody modelování v té či oné míře nepoužívaly. To platí zejména v oblasti řízení různé systémy, kde hlavními procesy jsou rozhodování na základě obdržených informací.
1. Vyjádření problému
minimální objektivní funkce
Úlohu nalezení minima účelové funkce pro soustavu omezení zadanou polygonem řešení řešte v souladu s možností č. 16 úlohy. Polygon řešení je znázorněn na obrázku 1:
Obrázek 1 - Mnohoúhelník řešení problému
Systém omezení a objektivní funkce problému jsou uvedeny níže:
Problém je nutné vyřešit pomocí následujících metod:
Grafická metoda řešení úloh LP;
Algebraická metoda řešení úloh LP;
Simplexní metoda pro řešení úloh LP;
Metoda hledání přípustného řešení problémů LP;
Řešení úlohy duálního LP;
Metoda větví a vazeb pro řešení celočíselných úloh LP;
Gomoriho metoda pro řešení celočíselných úloh LP;
Balazsova metoda pro řešení booleovských LP problémů.
Porovnejte výsledky řešení různé metody vyvodit z práce patřičné závěry.
2. Grafické řešení úlohy lineárního programování
Grafická metoda řešení úloh lineárního programování se používá v případech, kdy počet neznámých nepřesahuje tři. Vhodné pro kvalitativní výzkum vlastností roztoků a používá se ve spojení s jinými metodami (algebraické, větvené a vázané atd.). Myšlenka metody je založena na grafickém řešení systému lineárních nerovností.
Rýže. 2 Grafické řešení úlohy LP
Minimální bod
Rovnice přímky procházející dvěma body A1 a A2:
AB: (0;1); (3;3)
VS: (3;3); (4;1)
CD: (4;1); (3;0)
EA: (1;0); (0;1)
CF: (0;1); (5;2)
s omezeními:
Řešení úlohy lineárního programování pomocí algebraické simplexové metody
Aplikace algebraické metody pro řešení problému vyžaduje zobecnění reprezentace problému LP. Původní systém omezení, specifikovaný ve formě nerovností, je převeden na standardní zápis, když jsou omezení specifikována ve formě rovnosti. Transformace systému omezení na standardní pohled zahrnuje následující kroky:
Nerovnice transformujte tak, aby nalevo byly proměnné a volné členy a napravo 0, tzn. na levá strana byla větší nebo rovna nule;
Zaveďte další proměnné, jejichž počet se rovná počtu nerovností v systému omezení;
Zavedením dalších omezení na nezápornost přidaných proměnných nahraďte znaky nerovnosti přísnými znaky rovnosti.
Při řešení úlohy LP pomocí algebraické metody se přidává podmínka: účelová funkce musí směřovat k minimu. Li tento stav není splněna, je nutné odpovídajícím způsobem transformovat účelovou funkci (vynásobit -1) a vyřešit problém minimalizace. Po nalezení řešení dosaďte hodnoty proměnných do původní funkce a vypočítejte její hodnotu.
Řešení problému pomocí algebraické metody se považuje za optimální, když jsou hodnoty všech základních proměnných nezáporné a koeficienty volných proměnných v rovnici účelové funkce jsou také nezáporné. Pokud tyto podmínky nejsou splněny, je nutné transformovat systém nerovností, vyjadřujících některé proměnné jinými (měnící se volné a základní proměnné), aby bylo dosaženo splnění výše uvedených omezení. Hodnota všech volných proměnných se považuje za rovnou nule.
Algebraická metoda pro řešení úloh lineárního programování je jednou z nejvíce efektivní metody při ručním řešení problémů malého rozsahu, protože nevyžaduje velké množství aritmetických výpočtů. Strojová realizace této metody je složitější než např. u simplexové metody, protože Algoritmus řešení pomocí algebraické metody je do jisté míry heuristický a efektivita řešení do značné míry závisí na osobní zkušenosti.
Volné proměnné
St. lane - další souprava
Podmínky nezápornosti jsou splněny, proto bylo nalezeno optimální řešení.
3. Řešení úlohy lineárního programování pomocí simplexní tabulky
Řešení: Uveďme problém do standardního formuláře pro řešení pomocí simplexní tabulky.
Zredukujeme všechny rovnice soustavy do tvaru:
Sestavíme simplexní tabulku:
V horním rohu každé buňky tabulky zadáme koeficienty ze soustavy rovnic;
Vybereme maximální kladný prvek v řádku F, kromě toho, že to bude obecný sloupec;
Abychom našli obecný prvek, budujeme vztah pro všechny pozitivní. 3/3; 9/1;- minimální poměr v řádku x3. Proto - obecný řetězec a =3 - obecný prvek.
Najdeme =1/=1/3. Přivedeme jej do spodního rohu buňky, kde se nachází obecný prvek;
Do všech prázdných dolních rohů obecného řádku zadáme součin hodnoty v horním rohu buňky o;
Vyberte horní rohy obecné čáry;
Do všech dolních rohů obecného sloupce zadáme součin hodnoty v horním rohu pomocí - a vybereme výsledné hodnoty;
Zbývající buňky tabulky jsou vyplněny jako produkty odpovídajících vybraných prvků;
Poté sestavíme novou tabulku, ve které se prohodí označení buněk prvků obecného sloupce a řádku (x2 a x3);
Hodnoty, které byly dříve v dolním rohu, jsou zapsány do horního rohu předchozího obecného řádku a sloupce;
Součet hodnot horních a dolních rohů těchto buněk v předchozí tabulce je zapsán v horním rohu zbývajících buněk
4. Řešení úlohy lineárního programování nalezením přípustného řešení
Nechť je dána soustava lineárních algebraických rovnic:
Můžeme předpokládat, že vše je, jinak příslušnou rovnici vynásobíme -1.
Zavádíme pomocné proměnné:
Zavádíme také pomocnou funkci
Budeme minimalizovat systém za omezení (2) a podmínek.
PRAVIDLO PRO HLEDÁNÍ POVOLENÉHO ŘEŠENÍ: Abychom našli přípustné řešení systému (1), minimalizujeme formu (3) pod omezením (2), přičemž xj bereme jako volné neznámé a xj bereme jako základní.
Při řešení problému pomocí simplexové metody mohou nastat dva případy:
min f=0, pak se všechna i musí rovnat nule. A výsledné hodnoty xj budou představovat přípustné řešení systému (1).
min f>0, tzn. původní systém nemá proveditelné řešení.
Zdrojový systém:
Použije se podmínka problému z předchozího tématu.
Pojďme si představit další proměnné:
Bylo nalezeno přípustné řešení původního problému: x1 = 3, x2 = 3, F = -12. Na základě získaného proveditelného řešení najdeme optimální řešení původní úlohy pomocí simplexové metody. Za tímto účelem vytvoříme novou simplexní tabulku z tabulky získané výše, přičemž odstraníme řádek a řádek s cílovou funkcí pomocného problému:
Při analýze sestrojené simplexové tabulky vidíme, že optimální řešení pro původní problém již bylo nalezeno (prvky v řádku odpovídající účelové funkci jsou záporné). Schůdné řešení nalezené při řešení pomocného problému se tedy shoduje s optimálním řešením původního problému:
6. Problém duálního lineárního programování
Původní systém omezení a objektivní funkce problému jsou znázorněny na obrázku níže.
s omezeními:
Řešení: Převeďme systém omezení do standardní podoby:
Problém duální k tomuto bude mít tvar:
Řešení duální úlohy bude provedeno pomocí jednoduché simplexní metody.
Transformujme účelovou funkci tak, aby byl minimalizační problém vyřešen, a zapišme systém omezení ve standardním tvaru pro řešení pomocí simplexové metody.
y6 = 1 - (-2 y1 + 2y2 + y3 + y4+ y5)
y7 = 5 - (-3y1 - y2 + y3 + y4)
Ф = 0 - (3y1 + 9y2 + 3y3 + y4) ??min
Vytvořme počáteční simplexovou tabulku pro řešení duálního problému LP.
Druhý krok simplexové metody
Takže ve třetím kroku simplexové metody bylo nalezeno optimální řešení minimalizačního problému s následujícími výsledky: y2 = -7 /8, y1 = -11/8, Ф = 12. Abychom našli hodnotu objektivní funkce duálního problému, dosadíme nalezené hodnoty základních a volných proměnných do maximalizační funkce:
Фmax = - Фmin = 3*(-11/8) + 9(-7/8) + 3*0 + 0 = -12
Protože se hodnota účelové funkce přímé a duální úlohy shoduje, řešení přímé úlohy je nalezeno a je rovno 12.
Fmin = Фmax = -12
7. Řešení celočíselného lineárního programování metodou větví a vazeb
Transformujme původní problém tak, aby při řešení konvenčními metodami nebyla splněna celočíselná podmínka.
Počáteční mnohoúhelník řešení celočíselného programovacího problému.
Pro transformovaný mnohoúhelník řešení sestrojíme nový systém omezení.
Zapišme si systém omezení ve formě rovnosti k řešení pomocí algebraické metody.
V důsledku řešení byl nalezen optimální plán úlohy: x1 = 9/4, x2 = 5/2, F = -41/4. Toto řešení nesplňuje celočíselnou podmínku nastavenou v problému. Rozdělme původní polygon řešení na dvě oblasti, vyjma oblasti 3 z něj Upravený polygon řešení problému Vytvořme nové systémy omezení pro výsledné oblasti polygonu řešení. Levá oblast je čtyřúhelník (lichoběžník). Systém omezení pro levou oblast polygonu řešení je uveden níže. Omezovací systém pro levou oblast Pravá oblast představuje bod C. Systém omezení pro správný rozhodovací region je uveden níže. Nové omezovací systémy představují dva pomocné problémy, které je třeba řešit nezávisle na sobě. Pojďme vyřešit celočíselný programovací problém pro levou oblast polygonu řešení. V důsledku řešení byl nalezen optimální plán úlohy: x1 = 3, x2 = 3, F = -12. Tento plán splňuje podmínku, že proměnné v problému jsou celočíselné a lze jej přijmout jako optimální referenční plán pro původní celočíselný problém lineárního programování. Nemá smysl řešit pro správný region řešení. Obrázek níže ukazuje postup řešení úlohy celočíselného lineárního programování ve formě stromu. Průběh řešení úlohy celočíselného lineárního programování pomocí Gomoriho metody. V mnoha praktických aplikacích je velmi zajímavý problém celočíselného programování, ve kterém je dán systém lineárních nerovností a lineární tvar. Je potřeba najít celočíselné řešení systému (1), které minimalizuje účelovou funkci F, a všechny koeficienty jsou celá čísla. Jedna z metod řešení problému celočíselného programování byla navržena Gomorim. Myšlenkou metody je použití metod spojitého lineárního programování, zejména simplexové metody. 1) Simplexovou metodou se určí řešení úlohy (1), (2), u které je odstraněn požadavek na celočíselné řešení; pokud se ukáže, že řešení je celočíselné, bude také nalezeno požadované řešení celočíselného problému; 2) V opačném případě, pokud některá souřadnice není celé číslo, je výsledné řešení úlohy zkontrolováno na možnost existence celočíselného řešení (přítomnost celočíselných bodů v přípustném mnohostěnu): jestliže se v libovolném řádku s volným zlomkem všechny ostatní koeficienty ukáží jako celá čísla, pak v přípustném mnohostěnu nejsou žádná celá čísla ani body a problém celočíselného programování nemá řešení; V opačném případě je zavedeno další lineární omezení, které odřízne část přípustného mnohostěnu, který je neslibný pro nalezení řešení problému celočíselného programování; 3) Chcete-li sestavit další lineární vazbu, vyberte l-tý řádek s volným zlomkem a napište další vazbu kde a jsou v tomto pořadí zlomkové části koeficientů a volné člen. Zaveďme pomocnou proměnnou do omezení (3): Pojďme určit koeficienty a zahrnuté do omezení (4): kde a jsou nejbližší celá čísla zdola pro a resp. Gomori dokázal, že konečný počet podobných kroků vede k problému lineárního programování, jehož řešení je celočíselné, a tedy požadované. Řešení: Převeďme systém lineárních omezení a cílovou funkci do kanonické podoby: Stanovme optimální řešení systému lineárních vazeb, dočasně zahoďme celočíselnou podmínku. K tomu používáme simplexovou metodu. Níže, postupně v tabulkách, je uvedeno původní řešení problému a jsou uvedeny transformace původní tabulky za účelem získání optimálního řešení problému: Řešení booleovských LP úloh pomocí Balazsovy metody. Vytvořte si vlastní verzi úlohy celočíselného lineárního programování s booleovskými proměnnými s přihlédnutím k následujícím pravidlům: úloha používá alespoň 5 proměnných, alespoň 4 omezení, koeficienty omezení a účelová funkce se volí libovolně, ale v takovém způsobem, že systém omezení je kompatibilní. Úkolem je vyřešit LCLP s booleovskými proměnnými pomocí Balazsova algoritmu a určit snížení složitosti výpočtů ve vztahu k řešení problému metodou vyčerpávajícího vyhledávání. Provádění omezení Hodnota F Omezení filtrování: Stanovení snížení výpočetní náročnosti Řešením úlohy metodou vyčerpávajícího vyhledávání je 6*25=192 vypočítaných výrazů. Řešením úlohy pomocí Balazsovy metody je 3*6+(25-3)=47 vypočítaných výrazů. Celkové snížení složitosti výpočtů ve vztahu k řešení problému pomocí metody vyčerpávajícího vyhledávání je: Závěr Proces navrhování informačních systémů, které implementují nové informační technologie, se neustále zdokonaluje. Zaměření systémových inženýrů se stále více zaměřuje na komplexní systémy, což ztěžuje použití fyzikálních modelů a zvyšuje význam matematických modelů a strojové simulace systémů. Strojová simulace se stala účinným nástrojem pro studium a navrhování složitých systémů. Relevance matematických modelů neustále roste díky jejich flexibilitě, přiměřenosti reálným procesům a nízkým nákladům na implementaci na bázi moderních PC. Stále více příležitostí je poskytováno uživateli, tedy specialistovi na modelování systémů pomocí výpočetní techniky. Použití modelování je zvláště efektivní v raných fázích navrhování automatizovaných systémů, kdy jsou náklady na chybná rozhodnutí nejvýznamnější. Moderní výpočetní nástroje umožnily výrazně zvýšit komplexnost modelů používaných při studiu systémů, bylo možné sestavit kombinované, analytické a simulační modely, které zohledňují celou řadu faktorů vyskytujících se v reálných systémech, tzn. , použití modelů, které jsou více adekvátní zkoumaným jevům. Literatura: 1. Ljaščenko I.N. Lineární a nelineární programování / I.N. Lyashchenko, E.A. Karagodova, N.V. Chernikova, N.Z. Shor. - K.: „Vysoká škola“, 1975, 372 s. 2. Směrnice pro absolvování projektu předmětu v oboru „Aplikovaná matematika“ pro studenty oboru „Počítačové systémy a sítě“ prezenční a kombinované formy studia / Zpracovali: I.A. Balakireva, A.V. Skatkov - Sevastopol: SevNTU Nakladatelství , 2003. - 15 s. 3. Směrnice pro studium oboru „Aplikovaná matematika“, oddíl „Metody globálního vyhledávání a jednorozměrné minimalizace“ / Comp. A.V. Skatkov, I.A. Balakireva, L.A. Litvinová - Sevastopol: Nakladatelství SevGTU, 2000. - 31 s. 4. Pokyny pro studium oboru „Aplikovaná matematika“ pro studenty specializace „Počítačové systémy a sítě“ Sekce „Řešení úloh lineárního programování s celočíselným“ pro prezenční i kombinovanou výuku / Zpracovali: I.A. Balakireva, A.V. Skatkov - Sevastopol : Nakladatelství SevNTU, 2000. - 13 s. 5. Akulich I.L. Matematické programování v příkladech a problémech: 6. Učebnice příspěvek pro studenty ekonomie. specialista. univerzit.-M.: Vyšší. škola, 1986.- 319 s., ill. 7. Andronov S.A. Optimální metody návrhu: Text přednášek / SPbSUAP. Petrohrad, 2001. 169 s.: ill. 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. práce v kurzu, přidáno 21.03.2012 Řešení grafických problémů. Sestavení matematického modelu. Stanovení maximální hodnoty účelové funkce. Řešení simplexovou metodou s umělým základem úlohy kanonického lineárního programování. Kontrola optimálnosti řešení. test, přidáno 04.05.2016 Teoretické základy lineárního programování. Úlohy lineárního programování, metody řešení. Analýza optimálního řešení. Řešení úlohy lineárního programování s jedním indexem. Vyjádření problému a zadávání dat. Stavba modelu a fáze řešení. práce v kurzu, přidáno 12/09/2008 Konstrukce matematického modelu. Výběr, zdůvodnění a popis metody řešení úlohy přímého lineárního programování simplexovou metodou, pomocí simplexní tabulky. Formulace a řešení duálního problému. Citlivostní analýza modelu. práce v kurzu, přidáno 31.10.2014 Konstrukce matematického modelu za účelem získání maximálního zisku pro podnik, grafické řešení problému. Řešení problému pomocí doplňku SOLVER. Analýza změn zásob zdrojů. Stanovení limit pro změnu koeficientů účelové funkce. práce v kurzu, přidáno 17.12.2014 Matematické programování. Lineární programování. Problémy lineárního programování. Grafická metoda řešení úloh lineárního programování. Ekonomická formulace problému lineárního programování. Konstrukce matematického modelu. práce v kurzu, přidáno 13.10.2008 Řešení úlohy lineárního programování grafickou metodou, její kontrola v MS Excel. Analýza vnitřní struktury řešení problému v programu. Optimalizace výrobního plánu. Řešení úlohy simplexovou metodou. Vícekanálový systém řazení do fronty. test, přidáno 05.02.2012 Řešení úlohy lineárního programování simplexovou metodou: zadání úlohy, konstrukce ekonomického a matematického modelu. Řešení dopravního problému metodou potenciálu: sestavení výchozího referenčního plánu, stanovení jeho optimální hodnoty. test, přidáno 4.11.2012 Sdělení problému nelineárního programování. Určení stacionárních bodů a jejich typu. Konstrukce úrovňových čar, trojrozměrný graf účelové funkce a omezení. Grafické a analytické řešení problému. Uživatelská příručka a schéma algoritmu. práce v kurzu, přidáno 17.12.2012 Analýza řešení úlohy lineárního programování. Simplexní metoda pomocí simplexních tabulek. Modelování a řešení úloh LP na počítači. Ekonomická interpretace optimálního řešení problému. Matematická formulace dopravní úlohy. Vydělte třetí řádek klíčovým prvkem rovným 5, získáme třetí řádek nové tabulky. Základní sloupce odpovídají jednotkovým sloupcům. Výpočet dalších tabulkových hodnot: „BP – základní plán“: ; "x1": "x5": Hodnoty indexového řetězce jsou nezáporné, proto získáme optimální řešení: , ; Odpovědět: maximální zisk z prodeje vyrobených výrobků ve výši 160/3 jednotek je zajištěn výrobou pouze výrobků druhého typu ve výši 80/9 jednotek. Je dán problém nelineárního programování. Najděte maximum a minimum účelové funkce pomocí graficko-analytické metody. Sestavte Lagrangeovu funkci a ukažte, že v extrémních bodech jsou splněny dostatečné podmínky pro minimum (maximum). Protože poslední číslice šifry je 8, pak A=2; B=5. Protože předposlední číslice šifry je 1, pak byste měli zvolit úkol č. 1. Řešení: 1) Nakreslete oblast definovanou soustavou nerovnic. Tato oblast je trojúhelník ABC se souřadnicemi vrcholu: A(0; 2); B(4; 6) a C(16/3; 14/3). Úrovně účelové funkce jsou kruhy se středem v bodě (2; 5). Čtverce poloměrů budou hodnotami cílové funkce. Pak obrázek ukazuje, že minimální hodnota účelové funkce je dosažena v bodě H, maximální - buď v bodě A nebo v bodě C. Hodnota účelové funkce v bodě A: ; Hodnota účelové funkce v bodě C: ; To znamená, že nejvyšší hodnota funkce je dosažena v bodě A(0; 2) a je rovna 13. Zjistíme souřadnice bodu H. Chcete-li to provést, zvažte systém: Přímka je tečnou ke kružnici, pokud má rovnice jednoznačné řešení. Kvadratická rovnice má jedinečné řešení, pokud je diskriminant 0. 2) Vytvořme Lagrangeovu funkci, abychom našli minimální řešení: Na X 1
=2.5;
X 2
=4.5
dostaneme: Systém má řešení na , tzn. jsou splněny dostatečné podmínky pro extrém. Pojďme sestavit Lagrangeovu funkci, abychom našli maximální řešení: Dostatečné podmínky pro extrém: Na X 1
=0;
X 2
=2
dostaneme: Systém má i řešení, tzn. jsou splněny dostatečné podmínky pro extrém. Odpovědět: minima účelové funkce je dosaženo, když Dvěma podnikům jsou přiděleny finanční prostředky ve výši d Jednotky. Při přidělení prvního podniku na rok X jednotky fondů, které poskytuje příjem k 1
X jednotek a při přidělení druhému podniku y jednotek fondů, poskytuje příjem k 1
y Jednotky. Stav prostředků na konci roku u prvního podniku je roven nx a za druhé můj. Jak rozložit všechny prostředky do 4 let tak, aby celkový příjem byl co největší? Vyřešte problém pomocí metody dynamického programování. i=8, k=1. A = 2200; ki = 6; k2 = 1; n = 0,2; m=0,5. Řešení: Celé období 4 let je rozděleno do 4 etap, z nichž každá je roven jednomu roku. Očíslujme etapy počínaje prvním rokem. Nechť X k a Y k jsou finanční prostředky přidělené podnikům A a B v k-té fázi. Potom součet X k + Y k = a k je celkový objem prostředků použitých ve fázi k – ono a zbytek z předchozí fáze k – 1. v první fázi jsou využity všechny přidělené prostředky a a 1 = 2200 jednotek . příjem, který bude obdržen ve fázi k, s přidělením jednotek X k a Y k bude 6X k + 1Y k. nechť maximální příjem obdržený v posledních fázích počínaje k – v této fázi je f k (ak) jednotek. Zapišme si funkcionální Bellmanovu rovnici vyjadřující princip optimality: ať je počáteční stav a počáteční řešení jakýkoli, následné řešení musí být optimální vzhledem ke stavu získanému jako výsledek počátečního stavu: Pro každou fázi je třeba vybrat hodnotu X k a hodnotu Yk=ak- Xk. Když to vezmeme v úvahu, najdeme příjem v k-té fázi: Bellmanova funkční rovnice bude: Zvažme všechny fáze, počínaje posledním. (protože maxima lineární funkce je dosaženo na konci segmentu v x 4 = a 4);
Podobné dokumenty
;
; 
;
; 
.
.
Úkol č. 2
ó
ó 
Pak 
; ; 
- minimální hodnota funkce.
ó 
ó 
ó 
; ; maximum účelové funkce je dosaženo při 
; .
Úkol č. 3
