Řešení úloh MOP (optimalizační metody). Metodický základ pro rozvoj manažerských rozhodnutí Řešení se nazývá optimální

Lineární programování je obor matematiky, který studuje metody pro nalezení minima nebo maxima lineární funkce konečného počtu proměnných za předpokladu, že proměnné splňují konečný počet omezení ve formě lineárních rovnic nebo lineárních nerovností.

Tedy obecný úkol lineární programování(ZLP) lze formulovat následovně.

Najděte hodnoty skutečných proměnných, pro které objektivní funkce

má minimální hodnotu na množině bodů, jejichž souřadnice vyhovují systém omezení

Jak známo, uspořádaná sbírka hodnot n proměnné , , … jsou reprezentovány bodem v n-rozměrném prostoru. V následujícím budeme tento bod označovat X=( , , … ).

V maticové formě lze problém lineárního programování formulovat následovně:

, A- velikostní matice,

Tečka X Zavolá se =( , , … ), splňující všechny podmínky platný bod . Volá se množina všech přípustných bodů platná oblast .

Optimální řešení (optimální plán) problém lineárního programování se nazývá řešení X=( , , … ), patřící do přípustné oblasti a pro kterou je lineární funkce Q nabývá optimální (maximální nebo minimální) hodnoty.

Teorém. Množina všech možných řešení systému omezení úlohy lineárního programování je konvexní.

Množina bodů se nazývá konvexní , pokud spolu s libovolnými dvěma svými body obsahuje jejich libovolnou konvexní lineární kombinaci.

Tečka X volal konvexní lineární kombinace bodů, pokud jsou splněny podmínky

Množina všech proveditelných řešení problému lineárního programování je konvexní polyedrická oblast, kterou budeme dále nazývat mnohostěn řešení .

Teorém. Pokud má ZLP optimální řešení, pak účelová funkce nabývá maximální (minimální) hodnoty v jednom z vrcholů mnohostěnu řešení. Pokud účelová funkce nabývá maximální (minimální) hodnoty ve více než jednom bodě, pak tuto hodnotu nabývá v libovolném bodě, který je konvexní lineární kombinací těchto bodů.

Mezi mnoha řešeními systému m lineární rovnice popisující mnohostěn řešení, rozlišují se tzv. základní řešení.

Základní řešení systému m lineární rovnice s n proměnnými je řešení, ve kterém vše n-m vedlejší proměnné jsou nulové. V úlohách lineárního programování se taková řešení nazývají přípustná základní řešení (referenční plány).

Teorém. Každé přípustné základní řešení úlohy lineárního programování odpovídá vrcholu mnohostěnu řešení a naopak každému vrcholu mnohostěnu řešení odpovídá přípustné základní řešení.

Z výše uvedených teorémů vyplývá důležitý důsledek:

Pokud má problém lineárního programování optimální řešení, pak se shoduje s alespoň jedním z jeho proveditelných základních řešení.

Optimum lineární funkce cíle problému lineárního programování je tedy třeba hledat mezi konečným počtem jeho proveditelných základních řešení.

Základem řešení ekonomických problémů jsou matematické modely.

Matematický model problém je soubor matematických vztahů, které popisují podstatu problému.

• výběr problémových proměnných
• sestavení systému omezení
• volba objektivní funkce

Úkolové proměnné se nazývají veličiny X1, X2, Xn, které zcela charakterizují ekonomický proces. Obvykle se zapisují jako vektor: X=(X 1, X 2,...,X n).

Systém omezení problémy jsou souborem rovnic a nerovností, které popisují omezené zdroje v uvažovaném problému.

Objektivní funkceúkoly se nazývají funkce proměnných úkolu, které charakterizují kvalitu úkolu a jejichž extrém je třeba najít.

V obecný případ Problém lineárního programování lze napsat takto:

Tento záznam znamená následující: najděte extrém účelové funkce (1) a odpovídající proměnné X=(X 1 , X 2 ,...,X n) za předpokladu, že tyto proměnné splňují systém omezení (2) a podmínky nezápornosti (3) .

Platné řešení(plán) úlohy lineárního programování je libovolný n-rozměrný vektor X=(X 1 , X 2 ,...,X n), který vyhovuje systému omezení a podmínek nezápornosti.

Soubor možných řešení (plánů) problému tvoří region proveditelných řešení(ODR).

Optimální řešení(plán) úlohy lineárního programování je takové přípustné řešení (plán) úlohy, ve kterém účelová funkce dosahuje extrému.

Příklad sestavení matematického modelu

Problém využití zdrojů (surovin)

Stav: K výrobě n druhů výrobků se používá m druhů zdrojů. Vytvořte matematický model.

Známý:

• b i (i = 1,2,3,...,m) — zásoby každého i-tého typu zdroje;
• a ij (i = 1,2,3,...,m; j=1,2,3,...,n) - náklady každého i-tého druhu zdroje na výrobu jednotky objemu j-tého typu produktu;
• c j (j = 1,2,3,...,n) - zisk z prodeje jednotky objemu j-tého druhu produktu.

Je třeba sestavit plán výroby, který zajistí maximální zisk při daných omezeních zdrojů (surovin).

Řešení:

Zaveďme vektor proměnných X=(X 1, X 2,...,X n), kde x j (j = 1,2,...,n) je objem produkce j-tého typu produkt.

Náklady i-tého druhu zdroje na výrobu daného objemu x j výrobků se rovnají a ij x j , proto omezení využití zdrojů na výrobu všech druhů výrobků má podobu:
Zisk z prodeje j-tého typu produktu se rovná c j x j, takže účelová funkce je rovna:

Odpověď- Matematický model má tvar:

Kanonická forma úlohy lineárního programování

V obecném případě je problém lineárního programování napsán tak, že omezeními jsou jak rovnice, tak nerovnosti a proměnné mohou být buď nezáporné, nebo libovolně se měnící.

V případě, kdy jsou všechna omezení rovnicemi a všechny proměnné splňují podmínku nezápornosti, nazývá se problém lineárního programování kanonický.

Může být reprezentován v souřadnicovém, vektorovém a maticovém zápisu.

Kanonický problém lineárního programování v souřadnicovém zápisu má tvar:

Kanonický problém lineárního programování v maticovém zápisu má tvar:

• A je matice koeficientů soustavy rovnic
• X – maticový sloupec proměnných úlohy
• Ао — maticový sloupec správných částí systému omezení

Často se používají problémy lineárního programování, nazývané symetrické, které v maticovém zápisu mají tvar:

Redukce obecného problému lineárního programování na kanonickou formu

Ve většině metod řešení problémů lineárního programování se předpokládá, že systém omezení se skládá z rovnic a přirozených podmínek pro nezápornost proměnných. Při sestavování modelů ekonomických problémů se však omezení tvoří především v podobě soustavy nerovnic, proto je nutné umět přejít od soustavy nerovnic k soustavě rovnic.

Vezměme lineární nerovnost a 1 x 1 +a 2 x 2 +...+a n x n ≤b a na její levou stranu připočtěme určitou hodnotu x n+1 takovou, aby se z nerovnosti stala rovnost a 1 x 1 +a 2 x 2 + ...+a n x n +x n+1 =b. Navíc tato hodnota x n+1 je nezáporná.

Podívejme se na vše na příkladu.

Převeďte problém lineárního programování do kanonické podoby:

Řešení:
Přejděme k problému hledání maxima účelové funkce.
K tomu měníme znaménka koeficientů účelové funkce.
Pro transformaci druhé a třetí nerovnosti systému omezení do rovnic zavedeme nezáporné doplňkové proměnné x 4 x 5 (v matematickém modelu je tato operace označena písmenem D).
Proměnná x 4 je zavedena do levé strany druhé nerovnosti se znaménkem „+“, protože nerovnost má tvar „≤“.
Proměnná x 5 je zavedena do levé strany třetí nerovnosti se znaménkem „-“, protože nerovnost má tvar „≥“.
Proměnné x 4 x 5 se zadávají do účelové funkce s koeficientem. rovna nule.
Úlohu zapisujeme v kanonické podobě.

Operační výzkum je komplexní matematická disciplína, která se zabývá konstrukcí, analýzou a aplikací matematických modelů pro optimální rozhodování během operací.

Předmět operačního výzkumu- systémy řízení organizace nebo organizace, které se skládají z velkého počtu vzájemně se ovlivňujících jednotek, které nejsou vždy vzájemně konzistentní a mohou být opačné.

Účel operačního výzkumu- kvantitativní zdůvodnění přijatých rozhodnutí o řízení organizací

Operace- systém řízených akcí, spojených jediným plánem a zaměřených na dosažení konkrétního cíle.

Je volána sada řídicích parametrů (proměnných) během operace rozhodnutí. Řešení se nazývá přijatelný , pokud splňuje soubor určitých podmínek. Řešení se nazývá optimální

, pokud je to přijatelné a podle určitých kritérií lepší než ostatní, nebo alespoň ne horší. Znak preference

nazýváno kritériem optimality. Kritérium optimality

zahrnuje účelovou funkci, směr optimalizace nebo soubor účelových funkcí a odpovídajících směrů optimalizace. Objektivní funkce

je kvantitativní ukazatel preference či efektivity řešení. Směr optimalizace

- toto je maximum (minimum), pokud je největší (nejmenší) hodnota účelové funkce nejvýhodnější.

Kritériem může být například maximalizace zisku nebo minimalizace nákladů.

Matematický model problému IO zahrnuje:

1) popis proměnných, které je třeba najít;

2) popis kritérií optimality;– kvantitativně a kvalitativně odůvodnit učiněné rozhodnutí. Konečné rozhodnutí činí odpovědná osoba nebo skupina lidí nazývaná rozhodovatel.

Vektor, který splňuje systém omezení, se nazývá přijatelné řešenínebo plán ZLP. Soubor všech plánů se nazývá platná oblast nebooblast proveditelných řešení. Zavolá se plán, který poskytuje maximum (minimum) cílové funkceoptimální plán nebooptimální řešení pro ZLP. Tedy,vyřešit PIL – znamená najít jeho optimální plán.

Je velmi jednoduché přivést obecný ZLP k hlavnímu pomocí následujících zřejmých pravidel.

Minimalizace účelové funkce F je ekvivalentní maximalizaci funkce G = – F.

Omezení nerovnosti je ekvivalentní rovnici za předpokladu, že další proměnná.

Pokud pro nějakou proměnnou x j není vnucena podmínka nezápornosti, pak je provedena změna proměnné.

Linie úrovně funkcí F, tj. čára, podél které tato funkce nabývá stejné pevné hodnoty S, tj. F(x 1 , x 2)= C

Množina bodů se nazývá konvexní, jestliže spolu s libovolnými dvěma svými body obsahuje celý segment spojující tyto body.

V případě dvou proměnných je množinou řešení lineární nerovnice (rovnice) polorovina (přímka).

Průsečík těchto polorovin (a přímek, pokud má systém omezení rovnice) představuje proveditelnou oblast. Pokud není prázdná, pak je to konvexní množina a je volána.

řešení polygon V případě tří proměnných je přípustnou oblastí ZLP průsečík poloprostorů a případně rovin a je tzv.

mnohostěn řešeníSystém lineárních rovnic se nazývá, systém se zákl jestliže každá rovnice obsahuje neznámou s koeficientem rovným 1, který v ostatních rovnicích soustavy chybí. Těmto neznámým se říká, základní – odpočinek.

uvolnit Budeme nazývat soustavu lineárních rovnic, kanonickýpokud je to systém se základem a to je vše b i ≥ 0. Základním řešením se v tomto případě ukazuje být plán, protože jeho složky jsou nezáporné. Zavolejme mu základní (nebo) plán vedlejší

kanonický systém. Budeme nazývat soustavu lineárních rovnic Budeme tomu říkat OZLP

(KZLP), pokud je soustava lineárních rovnic této úlohy kanonická a účelová funkce je vyjádřena pouze pomocí volných neznámých. Pokud je v simplexové tabulce mezi koeficienty alespoň jeden kladný prvek pro jakoukoli volnou neznámou, pak je možný přechod na nový kanonický problém, ekvivalentní původnímu, ve kterém se zadaná volná neznámá ukáže jako základní (v v tomto případě se jedna ze základních neznámých stává volnou) .

Věta 2. (o zlepšení základní linie) j a ve sloupci x j Pokud existuje alespoň jeden kladný prvek a klíčový vztah je >0, pak je možný přechod na ekvivalentní kanonický problém s ne horším základním návrhem.

Věta 3. (dostatečná podmínka pro optimalitu). 0 Pokud jsou všechny prvky řádku indexu simplexové tabulky maximalizačního problému nezáporné, pak je základní návrh tohoto problému optimální a s

na množině problémových plánů je maximum účelové funkce.. Věta 4(případ neomezené účelové funkce) j . j Pokud řádek indexu simplexní tabulky problému maximalizace obsahuje záporný prvek s

a v neznámém sloupci x

všechny prvky jsou nekladné, pak na množině problémových plánů není účelová funkce shora ohraničena.

Simplexní metoda:

Tento KZLP zapíšeme do původní simplexové tabulky.

Pokud jsou všechny prvky indexového řádku simplexní tabulky nezáporné, pak je základní plán úlohy optimální (Věta 3).

Pokud řádek indexu obsahuje záporný prvek, nad kterým v tabulce není žádný kladný prvek, pak účelová funkce není shora ohraničena na množině plánů a problém nemá řešení (Věta 4).

Pokud je v tabulce nad každým záporným prvkem řádku indexu alespoň jeden kladný prvek, měli byste přejít k nové simplexní tabulce, jejíž základní plán není horší než předchozí (Věta 2). Za tímto účelem (viz důkaz věty 1) pokud je to systém se základem a to je vše b vyberte klíčový sloupec v tabulce, na jehož základně je jakýkoli záporný prvek řádku indexu;

vyberte klíčový vztah (nejmenší ze vztahů

Při zvažování výsledné simplexové tabulky se jistě objeví jeden ze tří případů popsaných v odstavcích. 2, 3, 4. Nastanou-li situace v odstavcích. 2 nebo 3, pak proces řešení problému končí, ale pokud nastane situace v kroku 4, pak proces pokračuje.

Pokud vezmeme v úvahu, že počet různých základních plánů je konečný, jsou možné dva případy:

po konečném počtu kroků bude problém vyřešen (nastanou situace 2 nebo 3);

počínaje od určitého kroku se objeví smyčkování(periodické opakování simplexových tabulek a základních plánů).

Tyto úkoly se nazývají symetrické duální problémy.

Všimněme si následujících vlastností, které tyto úkoly spojují:

Jeden z problémů je problém maximalizace a druhý problém minimalizace.

V problému maximalizace jsou všechny nerovnosti ≤ a v problému minimalizace jsou všechny nerovnosti ≥.

Počet neznámých jednoho problému se rovná počtu nerovností druhého.

Koeficientové matice pro neznámé v nerovnicích obou úloh jsou vzájemně transponovány.

Volné členy nerovnic jednoho z problémů se rovnají koeficientům odpovídajících neznámých ve vyjádření účelové funkce druhého problému.

Algoritmus pro konstrukci duálního problému.

1. Převést všechny nerovnosti systému omezení původního problému do jednoho smyslu - do kanonické podoby.

2. Vytvořte rozšířenou matici systému A, která obsahuje sloupec b i a koeficienty účelové funkce F.

3. Najděte transponovanou matici A T.

4. Zapište duální problém. Věta 5.

F(x) ≤ G(Hodnota objektivní funkce problému maximalizace pro žádný z jejích plánů nepřesahuje hodnotu objektivní funkce jejího problému duální minimalizace pro žádný z jejích plánů, tj. platí následující nerovnost:),

y volal.

základní dualitní nerovnost (Věta 6.dostatečné podmínky pro optimalizaci

). (Pokud jsou pro některé plány duálních problémů hodnoty cílových funkcí stejné, pak jsou tyto plány optimální.Věta 7. základní věta o dualitě).

Pokud má ZLP konečné optimum, pak jeho duál má také konečné optimum, a (optimální hodnotycílové funkce se shodují. Není-li objektivní funkce jednoho z duálních problémů omezena, pak jsou podmínky druhého problému protichůdné.

Věta 8.

Složky optimálního řešení duálního ZLP se rovnají odpovídajícím prvkům řádku indexu optimální simplexové tabulky přímé úlohy, odpovídajícím doplňkovým proměnným.

Věta 11.(kritérium optimálnosti plánu dopravních problémů). Aby byl plán přepravy optimální, je nutné a postačující, aby existovala čísla () a (), která splňují následující podmínky:

a) pro všechny základní buňky plánu (>0);

b) pro všechny volné buňky (=0).

Potenciální metoda

Krok 1 Zkontrolujte, zda je tato přepravní úloha uzavřena. Pokud ano, pokračujte druhým krokem. Pokud ne, redukujte to na uzavřený problém tím, že představíte buď fiktivního dodavatele, nebo fiktivního spotřebitele.

Krok 2 Najděte počáteční referenční řešení (počáteční referenční plán) problému uzavřené dopravy.

Krok 3 Zkontrolujte, zda je výsledné řešení podpory optimální:

vypočítat pro něj potenciál dodavatele u i a spotřebitelé proti j

pro všechny volné buňky ( b, j) vypočítat odhady;

pokud jsou všechny odhady nekladné (), pak je řešení problému dokončeno: původní referenční plán je optimální. Pokud je mezi hodnocením alespoň jedno kladné, přejdeme ke čtvrtému kroku.

Krok 4. Vyberte buňku ( b * ,j * ) s největším kladným odhadem a vybudovat pro něj uzavřený cyklus přerozdělování nákladu. Cyklus začíná a končí ve vybrané buňce. b * , j * Získáme nové podpůrné řešení, ve kterém buňka (

) bude zaneprázdněn. Vraťme se ke třetímu kroku.

Po konečném počtu kroků bude získáno optimální řešení, tedy optimální plán přepravy produktů od dodavatelů ke spotřebitelům. Bod se nazývá bod místní maximum

, pokud existuje okolí tohoto bodu takové, že

Nezbytné podmínky pro optimalitu x * Aby funkce jedné proměnné měla v bodě

lokální extrém, je nutné, aby derivace funkce v tomto bodě byla rovna nule,

Aby funkce měla v bodě lokální extrém, je nutné, aby všechny její parciální derivace v tomto bodě zmizely x * Pokud v bodě x * první derivace funkce je rovna nule a druhá derivace >0, pak funkce v bodě<0 то функция в точке x * má místní minimum, pokud 2 produkty,

má lokální maximum. Věta 4. x * Má-li funkce jedné proměnné v bodě n - deriváty až (

1) řád se rovná nule a derivace řádu n není rovna 0, pak, n Li x * dokonce, pak tečka

je minimální bod if,fn(x)>0<0.

maximální bod, pokud fn(x) n Li x * lichý, pak bod

– inflexní bod. matice kvadratického tvaru .

Nazývá se kvadratická forma (5). pozitivní definitivní, pokud pro Q(X) >0 a negativně definované, pokud pro.Q(X)<0

Symetrická matice A volal pozitivní definitivní, je-li z něj sestrojená kvadratická forma (5) kladně definitní.

Nazývá se symetrická matice negativně definované, je-li z něj sestrojená kvadratická forma (6) záporně definitní.

Sylvesterovo kritérium: matice je kladně určitá, pokud jsou všechny její úhlové minority větší než nula.

Matice je záporně definitivní, pokud se znaky rohových nezletilých střídají.

Aby byla matice kladně definitní, musí být všechna její vlastní čísla větší než nula.

Vlastní čísla– kořeny polynomu.

Postačující podmínka pro optimalitu je dána následující větou.

Věta 5. Pokud je ve stacionárním bodě Hessova matice kladně definitní, pak je tento bod lokálním minimálním bodem, pokud je Hessovská matice záporně definitní, pak je tento bod lokálním maximálním bodem.

Konflikt je rozpor způsobený protichůdnými zájmy stran.

Konfliktní situace- situace, kdy strany, jejichž zájmy jsou zcela nebo částečně protichůdné.

hra - jde o skutečný nebo formální konflikt, ve kterém jsou alespoň dva účastníci, z nichž každý usiluje o dosažení svých vlastních cílů

Pravidla hry pojmenujte přípustné akce každého hráče směřující k dosažení určitého cíle.

Platbou se nazývá kvantitativní hodnocení výsledků hry.

Hra čtyřhry– hra, které se účastní pouze dvě strany (dva hráči).

Hra s nulovým součtem nebo antagonistický - hra ve čtyřhře, ve které je částka platby nulová, to znamená, pokud se ztráta jednoho hráče rovná zisku druhého.

Volba a provedení jedné z akcí stanovených pravidly se nazývá hráč je na řadě. Pohyby mohou být osobní a náhodné.

Osobní tah je vědomá volba hráče jedné z možných akcí (například tah v šachové hře).

Náhodný pohyb je náhodně vybraná akce (například výběr karty ze zamíchaného balíčku).

Strategie hráč - jedná se o jednoznačnou volbu hráče v každé z možných situací, kdy tento hráč musí provést osobní tah.

Optimální strategie- jedná se o strategii hráče, která mu, když se hra mnohokrát opakuje, poskytuje maximální možnou průměrnou výhru nebo minimální možnou průměrnou prohru.

Platební matice– výsledná matice A nebo, jinými slovy, herní matrice s.

Konečná hra dimenzí(m  n) je hra definovaná maticí A o rozměru (m  n).

Maximin nebo nejnižší cena hry nazvěme číslo alpa = max(i)(min aij)(j)

a odpovídající strategie (řetězec) maximin.

Minimax nebo nejvyšší cena hry nazveme číslo Beta = min(j)(max aij)i

a odpovídající strategie (sloupec) minimax.

Nižší cena hry vždy nepřevyšuje horní cenu hry.

Hra se sedlovou špičkou nazývaná hra, pro kterou. Alp = beta

Za cenu hry se nazývá veličina v if.v = alp = beta

Smíšená strategie hráč je vektor, jehož každá složka ukazuje relativní frekvenci hráčského použití odpovídající čisté strategie.

Teorém 2 .

Hlavní věta teorie maticových her.

Každá maticová hra s nulovým součtem má řešení ve smíšených strategiích.3

T

Pokud jeden z hráčů používá optimální smíšenou strategii, pak se jeho výplata rovná ceně hry  bez ohledu na frekvenci, s jakou druhý hráč používá své strategie (včetně čistých strategií).

hra s přírodou - hra, ve které nemáme informace o chování partneraRiziko r ij

Riziko r = pokud je to systém se základem a to je vše j - hráč při volbě strategie A i za podmínek H j se nazývá rozdíl b ,

A pokud je to systém se základem a to je vše j Kde j- maximální prvek v

- tý sloupec.

Graf je kolekce neprázdné množiny tzv

množina vrcholů grafu a množina dvojic vrcholů, které se nazývají

okraje grafu.

Pokud jsou uvažované dvojice vrcholů seřazeny, pak graf

se nazývá orientovaný (digraf), jinak –

neorientovaný.

V

Trasa (cesta) v grafu spojující vrcholy A a B se nazývá

sled hran, z nichž první pochází z vrcholu A, zač

následující se shoduje s koncem předchozího a poslední hrana je zahrnuta do

nahoře V.

Graf se nazývá spojený, pokud pro libovolné dva jeho vrcholy existuje cesta

jejich propojení. Jinak se graf nazývá odpojený.

Graf se nazývá konečný, pokud je počet jeho vrcholů konečný.

Pokud je vrchol začátkem nebo koncem hrany, pak vrchol a hrana

se nazývají incidenty. Stupeň (pořadí) vrcholu je počet hran, které k němu dopadají.

Eulerova cesta (eulerovský řetězec) v grafu je cesta procházející všemi

okraje grafu a navíc jen jednou.

Eulerovský cyklus je eulerovská cesta, která je cyklem.

Eulerovský graf je graf obsahující eulerovský cyklus.

Eulerův cyklus existuje právě tehdy, když je graf propojen a je v něm

neexistují žádné vrcholy lichého stupně.

Teorém. Eulerova cesta v grafu existuje právě tehdy, když graf existuje

spojené a počet vrcholů lichého stupně je nula nebo dva.

Strom je souvislý graf bez cyklů, který má počáteční vrchol

(kořen) a extrémní vrcholy (1. stupeň); cesty ze zdrojového vrcholu k vnějším vrcholům se nazývají větve.

Síť (nebo síťový diagram) je orientovaná konečnost

souvislý graf, který má počáteční vrchol (zdroj) a koncový vrchol (sink).

Váha cesty v grafu je součtem vah jejích hran.

Nejkratší cesta z jednoho vrcholu do druhého se bude nazývat cesta

minimální hmotnost.

Hmotnost této cesty se bude nazývat vzdálenost mezi

vrcholy.

Práce je časově náročný proces, který vyžaduje zdroje,

nebo logická závislost mezi dvěma nebo více úlohami

Událost je výsledkem provedení jedné nebo více úloh

Cesta je řetězec po sobě jdoucích děl, které se spojují

počáteční a koncové vrcholy.

Doba trvání cesty je určena součtem dob

jeho ustavující díla.

Pravidla pro tvorbu síťových diagramů.

1. V síťovém diagramu by neměly být žádné události uváznutí (kromě

konečné), tedy takové, po kterých nenásleduje žádná práce.

2. Neměly by existovat žádné události (kromě počáteční), kterým nepředchází ačkoli

jen jedna práce.

3. V síťovém diagramu by neměly být žádné cykly.

4. Jakékoli dvě události nejsou spojeny více než jednou úlohou.

5. Schéma sítě by mělo být uspořádané.

Jakákoli cesta, jejíž začátek se shoduje s počáteční událostí a jejíž konec se shoduje s

ukončení se nazývá úplná cesta. Plná cesta s maximem

doba trvání práce se nazývá kritická cesta

Hierarchie je určitý typ systému založený na předpokladu, že prvky systému lze seskupit do nesouvisejících množin

Popis metody hierarchické analýzy

Konstrukce párových srovnávacích matic

Najděte lambda max a vyřešte soustavu s ohledem na vektor vah

Syntéza místních priorit

Kontrola konzistence párových srovnávacích matic

Syntéza globálních priorit

Posouzení konzistence celé hierarchie

Simplexová metoda je metoda řešení problému lineárního programování. Podstatou metody je najít prvotní proveditelný plán a následně plán vylepšovat, dokud není dosaženo maximální (nebo minimální) hodnoty účelové funkce v dané konvexní polyedrické množině nebo není určena neřešitelnost problému.

Zvažte následující problém lineárního programování v kanonické podobě:

Metoda umělé báze

Jak je ukázáno výše, pro problém zapsaný v kanonické formě, pokud je mezi sloupcovými vektory matice A Existuje m jednotku a lineárně nezávislou, můžete přímo zadat referenční plán. Nicméně pro mnoho problémů lineárního programování napsaných v kanonické formě a majících referenční plány mezi sloupcové vektory matice A ne vždy k dispozici m jednotkové a lineárně nezávislé. Zvažte následující problém:

Předpokládejme, že potřebujeme najít maximum funkce

za podmínek

kde jsou první n prvky jsou nulové. Proměnné se nazývají umělé. Vektorové sloupce

(28)

tvoří tzv. umělý základ m-rozměrný vektorový prostor.

Protože rozšířený problém má referenční plán, jeho řešení lze nalézt simplexovou metodou.

Věta 4. Pokud v optimálním plánu rozšířený problém (24)−(26) hodnoty umělých proměnných , To je optimální plán pro problém (21)−(23).

Pokud jsou tedy v nalezeném optimálním plánu pro rozšířený problém hodnoty umělých proměnných rovny nule, pak je získán optimální plán pro původní problém. Pojďme se podrobněji zabývat hledáním řešení rozšířeného problému.

Hodnota účelové funkce pro referenční plán (27):

Všimneme si toho F(X) a skládají se ze dvou nezávislých částí, z nichž jedna je závislá na M, a druhý - ne.

Po výpočtu F(X) a jejich hodnoty, stejně jako počáteční data rozšířené úlohy, se zadají do simplexní tabulky, jak je uvedeno výše. Jediný rozdíl je v tom, že tato tabulka obsahuje o jeden řádek více než běžná simplexní tabulka. Zároveň v ( m+1) řádek obsahuje koeficienty, které neobsahují M a v ( m+2) řádek − koeficienty pro M.

Při přechodu z jednoho referenčního plánu do druhého vektor odpovídající největšímu zápornému číslu v absolutní hodnotě ( m+2) řádky. Umělý vektor vyloučený ze základu nemá smysl znovu zavádět do základu. Při přechodu na jiný referenční plán se může stát, že žádný z umělých vektorů není ze základu vyloučen. Přepočet simplexové tabulky při přechodu z jednoho referenčního plánu do druhého se provádí podle obvyklých pravidel simplexové metody (viz výše).

Iterační proces se provádí podle m+2 řádek dlouhý jako prvky m+2 řádky odpovídající proměnným se nestane negativní. Pokud jsou navíc ze základu vyloučeny umělé proměnné, pak nalezený plán rozšířeného problému odpovídá nějakému referenčnímu plánu původního problému.

m+2 řádky, sloupce x 0 je záporná, pak původní problém nemá řešení.

Pokud ne všechny umělé proměnné jsou vyloučeny ze základu a prvku m+2 řádky, sloupce x 0 se rovná nule, pak je referenční plán původní úlohy zdegenerovaný a báze obsahuje alespoň jeden z vektorů umělé báze.

Pokud původní problém obsahuje několik jednotkových vektorů, pak by měly být zahrnuty do umělé báze.

Pokud během iterací m+2 řádek již neobsahuje záporné prvky, pak proces iterace pokračuje m+1 řádek, dokud není nalezen optimální plán rozšířeného problému nebo odhalena neřešitelnost problému.

Proces hledání řešení problému lineárního programování (21)−(23) pomocí metody umělé báze tedy zahrnuje následující hlavní fáze:

• Sestavte rozšířenou úlohu (24)−(26).
• Najděte referenční plán rozšířeného problému.
• Pomocí simplexové metody jsou umělé vektory vyloučeny z báze. V důsledku toho je nalezen referenční plán původního problému nebo je zaznamenána jeho neřešitelnost.
• Pomocí nalezeného referenčního plánu ZLP (21)−(23) buď naleznou optimální plán původního problému, nebo zjistí jeho neřešitelnost.

K řešení problémů lineárního programování online použijte kalkulačku

Komponenty matematického modelu

Základem řešení ekonomických problémů jsou matematické modely.

Matematický model problém je soubor matematických vztahů, které popisují podstatu problému.

• výběr problémových proměnných
• sestavení systému omezení
• volba objektivní funkce

Úkolové proměnné se nazývají veličiny X1, X2, Xn, které zcela charakterizují ekonomický proces. Obvykle se zapisují jako vektor: X=(X1, X2,...,Xn).

Systém omezení problémy jsou souborem rovnic a nerovností, které popisují omezené zdroje v uvažovaném problému.

Objektivní funkceúkoly se nazývají funkce proměnných úkolu, které charakterizují kvalitu úkolu a jejichž extrém je třeba najít.

Obecně lze problém lineárního programování napsat takto:

Tento záznam znamená následující: najděte extrém účelové funkce (1) a odpovídající proměnné X=(X1, X2,...,Xn) za předpokladu, že tyto proměnné splňují systém omezení (2) a nezápornost podmínky (3).

Platné řešení(plán) úlohy lineárního programování je libovolný n-rozměrný vektor X=(X1, X2,...,Xn), který vyhovuje systému omezení a podmínek nezápornosti.

Soubor možných řešení (plánů) problému tvoří region proveditelných řešení(ODR).

Optimální řešení(plán) úlohy lineárního programování je takové přípustné řešení (plán) úlohy, ve kterém účelová funkce dosahuje extrému.

Stav: K výrobě n druhů výrobků se používá m druhů zdrojů. Vytvořte matematický model.

Známý:

• bi (i = 1,2,3,...,m) - rezervy každého i-tého typu zdroje;
• aij (i = 1,2,3,...,m; j=1,2,3,...,n) - náklady každého i-tého druhu zdroje na výrobu jednotky objemu j-tý typ produktu;
• cj (j = 1,2,3,...,n) - zisk z prodeje jednotky objemu j-tého druhu produktu.

Je třeba sestavit plán výroby, který zajistí maximální zisk při daných omezeních zdrojů (surovin).

Řešení:

Zaveďme vektor proměnných X=(X1, X2,...,Xn), kde xj (j = 1,2,...,n) je objem výroby j-tého typu produktu.

Náklady i-tého druhu zdroje na výrobu daného objemu xj výrobků se rovnají aijxj, proto omezení využití zdrojů na výrobu všech druhů výrobků má podobu:
Zisk z prodeje j-tého typu produktu se rovná cjxj, takže účelová funkce je rovna:

Odpověď- Matematický model vypadá takto:

Kanonická forma úlohy lineárního programování

V obecném případě je problém lineárního programování napsán tak, že omezeními jsou jak rovnice, tak nerovnosti a proměnné mohou být buď nezáporné, nebo libovolně se měnící.

V případě, kdy jsou všechna omezení rovnicemi a všechny proměnné splňují podmínku nezápornosti, nazývá se problém lineárního programování kanonický.

Může být reprezentován v souřadnicovém, vektorovém a maticovém zápisu.

Kanonický problém lineárního programování v souřadnicovém zápisu má tvar:

Kanonický problém lineárního programování v maticovém zápisu má tvar:

• A - matice koeficientů soustavy rovnic
• X - matice-sloupec úkolových proměnných
• Ао - maticový sloupec správných částí systému omezení

Často se používají problémy lineárního programování, nazývané symetrické, které v maticovém zápisu mají tvar:

Redukce obecného problému lineárního programování na kanonickou formu

Ve většině metod řešení problémů lineárního programování se předpokládá, že systém omezení se skládá z rovnic a přirozených podmínek pro nezápornost proměnných. Při sestavování modelů ekonomických problémů se však omezení tvoří především v podobě soustavy nerovnic, proto je nutné umět přejít od soustavy nerovnic k soustavě rovnic.

Vezměme lineární nerovnost a1x1+a2x2+...+anxn≤b a na její levou stranu připočtěme určitou hodnotu xn+1 tak, aby se z nerovnosti stala rovnost a1x1+a2x2+...+anxn+xn+1=b . Navíc tato hodnota xn+1 je nezáporná.

Podívejme se na vše na příkladu.

Převeďte problém lineárního programování do kanonické podoby:

Řešení:
Přejděme k problému hledání maxima účelové funkce.
K tomu měníme znaménka koeficientů účelové funkce.
Pro transformaci druhé a třetí nerovnosti systému omezení do rovnic zavádíme nezáporné doplňkové proměnné x4 x5 (v matematickém modelu je tato operace označena písmenem D).
Proměnná x4 je zavedena do levé strany druhé nerovnosti se znaménkem „+“, protože nerovnost má tvar „≤“.
Proměnná x5 je zavedena do levé strany třetí nerovnosti se znaménkem „-“, protože nerovnost má tvar „≥“.
Proměnné x4 x5 se zadávají do účelové funkce s koeficientem. rovna nule.
Problém zapíšeme v kanonické podobě: