Matematické modely úloh lineárního programování. Lineární matematické modely Přechod z omezení lineárního 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 proměnné úlohy
• sestavení systému omezení
• volba objektivní funkce

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

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

cílová funkceúloha se nazývá funkce proměnných úlohy, která charakterizuje kvalitu úlohy a jejíž 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=(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).

Přijatelné ř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ří řadu proveditelných řešení(ODR).

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

Příklad sestavení matematického modelu

Úkol využívat zdroje (suroviny)

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

Známý:

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

Je nutné sestavit plán výroby produktů, které poskytují maximální zisk s daným omezením zdrojů (surovin).

Řešení:

Zavedeme vektor proměnných X=(X 1 , X 2 ,...,X n), kde x j (j = 1,2,...,n) je objem výroby j-tého typu produktu.

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

Odpovědět- 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 jak rovnice, tak nerovnice jsou omezení a proměnné mohou být buď nezáporné, nebo se libovolně mění.

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 je sloupcová matice proměnných úlohy
• Ao je maticový sloupec pravý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ěte lineární nerovnost a 1 x 1 +a 2 x 2 +...+a n x n ≤b a přidejte na její levou stranu nějakou hodnotu x n+1 tak, 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á.

Zvažme vše na příkladu.

Redukujte problém lineárního programování na kanonickou formu:

Řešení:
Přejděme k problému hledání maxima účelové funkce.
K tomu měníme znaménka koeficientů účelové funkce.
Pro převedení druhé a třetí nerovnosti systému omezení na rovnice zavedeme nezáporné doplňkové proměnné x 4 x 5 (tato operace je na matematickém modelu označena písmenem D).
Proměnná x 4 se zadává na levé straně druhé nerovnosti se znaménkem "+", protože nerovnost má tvar "≤".
Proměnná x 5 se zadává na levé straně 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ě.

T10. Sdělení problému lineárního programování

matematický model Ekonomický problém je soubor matematických vztahů, které popisují ekonomický proces.

Pro sestavení matematického modelu je nutné:

1. vybrat proměnné úlohy;

2. vypracovat systém omezení;

3. nastavte účelovou funkci.

Úkolové proměnné jsou nazývány veličiny x 1 , x 2 ,…, x n, které plně charakterizují ekonomický proces. Obvykle jsou zapsány jako vektor X \u003d (x 1, x 2, ..., x n).

Systém omezení úkolů je soubor rovnic a nerovnic, které jsou splněny proměnnými problému a které vyplývají z omezených zdrojů a dalších ekonomických podmínek, např. z pozitivity proměnných. Obecně vypadají takto:

Zavolá se účelová funkce funkce F(X) = f(x 1 , x 2 ,…, x n) proměnných úlohy, která charakterizuje kvalitu úlohy a jejíž extrém je třeba najít.

Obecný problém matematického programování je formulován následovně: najděte proměnné úlohy x 1 , x 2 ,…, x n, které poskytují extrém účelové funkce

F (X) \u003d f (x 1, x 2, ..., x n) ® max (min) (2)

a splnit systém omezení (1).

Pokud jsou účelová funkce (2) a omezující systém (1) lineární, pak se problém matematického programování nazývá problém lineárního programování (LPP).

Zavolá se vektor X (soubor úlohových proměnných). přijatelné řešení nebo plán PLP, pokud splňuje systém omezení (1). Zavolá se proveditelný plán X, který poskytuje extrém účelové funkce optimální řešení ZLP.

2. Příklady sestavování matematických modelů ekonomických problémů

Studium konkrétních výrobních situací vede k ZLP, které jsou interpretovány jako problémy optimálního využití omezených zdrojů.

1.Problém optimálního plánu výroby

Pro výrobu dvou typů výrobků T 1 a T 2 se používají tři druhy zdrojů S 1, S 2, S 3. Zásoby zdrojů, počet jednotek zdrojů vynaložených na výrobu jednotky výroby, jakož i zisk z prodeje jednotky výroby jsou uvedeny v tabulce:

Je třeba najít takový plán výroby produktů, ve kterém bude zisk z jeho prodeje maximální.

Řešení.

Označme x 1, x 2 - počet jednotek produkce, respektive T 1 a T 2, plánovaných k výrobě. K jejich výrobě bude zapotřebí (x 1 + x 2) jednotek zdroje S 1, (x 1 + 4x 2) jednotek zdroje S 2, (x 1) jednotek zdroje S 3. Spotřeba zdrojů S 1 , S 2 , S 3 by neměla překročit jejich zásoby, respektive 8, 20 a 5 jednotek.

Pak lze ekonomicko-matematický model problému formulovat takto:

Najděte plán výroby X \u003d (x 1, x 2), který vyhovuje systému omezení:

a stav

pod kterou funkci nabývá maximální hodnoty.

Problém lze snadno zobecnit na případ výroby n typů výrobků s využitím m typů zdrojů.

2.Optimální dietní problém

Existují dva typy potravin K 1 a K 2 obsahující živiny S 1 , S 2 a S 3 . Obsah počtu živných jednotek v 1 kg každého druhu krmiva, požadované minimum živin, jakož i náklady na 1 kg krmiva jsou uvedeny v tabulce:

Je nutné sestavit denní krmnou dávku, která má minimální náklady, ve které by obsah každého druhu živin nebyl nižší než stanovený limit.

Řešení.

Označme x 1, x 2 - množství krmiva K 1 a K 2 zahrnuté v denní stravě. Pak bude tato strava obsahovat (3x 1 + x 2) jednotky živiny S 1, (x 1 + 2x 2) jednotky látky S 2, (x 1 + 6x 2) jednotky živiny S 3. Protože obsah živin S 1 , S 2 a S 3 ve stravě by měl být 9, 8 a 12 jednotek, lze ekonomicko-matematický model problému formulovat následovně:

Sestavte denní stravu X \u003d (x 1, x 2), splňující systém omezení:

a stav

pod kterou funkci nabývá minimální hodnoty.

Záznamové formuláře PLP

V LLP je nutné najít extrém lineární účelové funkce:

s omezeními:

a podmínku nezápornosti

kde a ij , b i , c j ( , ) jsou dané konstanty.

Tak se píše ZLP Všeobecné formulář. Pokud systém omezení obsahuje pouze nerovnosti, pak je LLP reprezentován v Standard formulář. Kanonický (hlavní) forma zápisu ZLP je zápis, kdy systém omezení obsahuje pouze rovnosti. Výše uvedené LLP jsou tedy psány ve standardní formě.

Obecná, standardní a kanonická forma LLP jsou ekvivalentní v tom smyslu, že každou z nich lze pomocí jednoduchých transformací přepsat do jiné formy. To znamená, že pokud existuje způsob, jak vyřešit jeden z těchto problémů, pak lze určit optimální plán pro kterýkoli z problémů.

Abychom mohli přejít z jedné formy zápisu LLP do druhé, musíme být schopni přejít od omezení nerovností k omezením rovnosti a naopak.

Omezení nerovnosti (£) lze převést na omezení rovnosti přidáním další nezáporné proměnné na její levou stranu a omezení nerovnosti (³) lze převést na omezení rovnosti odečtením další nezáporné proměnné od její levé strany. Počet zavedených dalších nezáporných proměnných se rovná počtu transformovaných omezení nerovností.

Představeno další proměnné dávají určitý ekonomický smysl. Pokud tedy omezení původní PLP odrážejí spotřebu a dostupnost zdrojů, pak se hodnota dodatečné proměnné PLP v kanonické formě rovná objemu nevyužitého odpovídajícího zdroje.

Příklad 1. Napište v kanonickém tvaru ZLP:

s omezeními:

Řešení.

Účelová funkce zůstává nezměněna:

Systém nerovností se transformuje na systém rovnosti:

Při řešení LLP grafickou metodou je nutný přechod z kanonické formy do standardní formy.

Chcete-li převést LLP do standardní formy, použijte Jordan-Gaussova metodaŘešení SLAU. Na rozdíl od Gaussovy metody, ve které je rozšířená matice systému redukována na stupňovitou formu, v Jordan-Gaussově metodě je matice identity tvořena jako součást rozšířené matice. Proto zde není nutný zpětný pohyb.

Chcete-li převést původní kanonický LLP na ekvivalentní standardní LLP:

a) v rozšířené matici omezovacího systému je zvolen nenulový prvek a qp. Tento prvek se nazývá povolný a q - i řádek a p-tý sloupec nazvaný povolit řádek a povolit sloupec.

b) rozlišovací řetězec je přepsán beze změny a všechny prvky rozlišovacího sloupce, kromě rozlišovacího sloupce, jsou nahrazeny nulami. Zbývající prvky rozšířené matice jsou určeny pomocí „pravidla obdélníku“:

Uvažujme čtyři prvky rozšířené matice: prvek a ij k transformaci, rozlišovací prvek a qp a prvky a i p a a qj . K nalezení prvku a ij plyne od prvku a ij odečíst součin prvků a i p a a qj umístěných v opačných vrcholech obdélníku, dělený rozlišovacím prvkem a qp:

c) povolené neznámé jsou současně vyloučeny z účelové funkce. K tomu se koeficienty účelové funkce zapisují do rozšířené matice v posledním řádku. Výpočty berou v úvahu, že aktivační prvek v posledním řádku nelze vybrat.

Příklad 2. Změna na standardní formulář:

Řešení.

Pomocí Jordan-Gaussovy metody přivedeme systém LLP omezujících rovnic na ekvivalentní systém nerovnic. Zvolme třetí prvek prvního řádku jako rozlišovací prvek:

Číslo -9 získané v posledním sloupci posledního řádku je nutné zapsat do účelové funkce s opačným znaménkem. V důsledku transformací má LLP podobu:

Protože proměnné x 2 a x 3 jsou nezáporné, pak je zahodíme, můžeme ZLP zapsat v symetrickém tvaru:

V kanonické formě LLP může být objektivní funkce jak minimalizována, tak maximalizována. Chcete-li přejít od nalezení maxima k nalezení minima nebo naopak, stačí změnit znaménka koeficientů účelové funkce: F 1 = - F. Výsledný problém a původní LLP mají stejné optimální řešení a hodnoty účelových funkcí na tomto řešení se liší pouze znaménkem.

Vlastnosti ZLP

1. Množina všech přípustných řešení soustavy omezení úlohy lineárního programování je konvexní.

Množina bodů se nazývá konvexní, pokud obsahuje celý segment spojující libovolné dva body této množiny.

Podle této definice je mnohoúhelník na obr. 1a konvexní množinou, zatímco mnohoúhelník na obr. 1b nikoliv, protože segment MN mezi jeho dvěma body M a N do tohoto mnohoúhelníku zcela nepatří.

Konvexní množiny mohou být nejen polygony. Příklady konvexních množin jsou kruh, sektor, segment, krychle, pyramida atd.

2. Pokud má LLP optimální řešení, pak lineární funkce nabývá maximální (minimální) hodnoty v jednom z rohových bodů rozhodovacího mnohostěnu. Pokud lineární funkce nabývá maximální (minimální) hodnoty ve více než jednom rohovém bodě, pak ji nabývá v libovolném bodě, který je konvexní lineární kombinací těchto bodů.

Bod X se nazývá konvexní lineární kombinace body X 1 , X 2 ,…, X n, jsou-li splněny tyto podmínky:

X \u003d α 1 X 1 + α 2 X 2 + ... + α n X n,

αj ≥ 0, Σαj = 1.

Je zřejmé, že ve speciálním případě pro n = 2 je konvexní lineární kombinace dvou bodů úsečkou, která je spojuje.

3. Každé přípustné základní řešení kanonického omezovacího systému LLP odpovídá rohovému bodu mnohostěnu řešení a naopak každému rohovému bodu mnohostěnu řešení odpovídá přípustné základní řešení.

Z posledních dvou vlastností vyplývá, že pokud má LLP optimální řešení, pak se shoduje s alespoň jedním z jeho přípustných základních řešení.

Extrém lineární funkce LLP je tedy třeba hledat mezi konečným počtem jejích přípustných základních řešení.

Základní pojmy modelování

V procesu lidského života se rozvíjejí představy o určitých vlastnostech reálných předmětů a jejich interakcích. Tyto reprezentace jsou tvořeny osobou ve formě popisů objektů, pro které se používá popisný jazyk. Může se jednat o slovní popis (slovní modely), kresbu, kresbu, graf, rozvržení atd. Vše výše uvedené shrnuje jeden pojem. Modelka, a proces stavby modelu modelování.

Modelování je univerzální způsob, jak studovat procesy a jevy reálného světa. Modelování má zvláštní význam při studiu objektů, které jsou nepřístupné přímému pozorování a výzkumu. Patří mezi ně zejména socioekonomické jevy a procesy.

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

Ekonomika- jedná se o systém společenské výroby, který provádí skutečnou výrobu, rozdělování, směnu a spotřebu hmotných statků nezbytných pro společnost.

resp. ekonomický a matematický model je ekonomická abstrakce vyjádřená formálně matematickými pojmy, jejíž logická struktura je určena jak objektivními vlastnostmi předmětu popisu, tak subjektivním cílovým faktorem studia, pro které je tento popis prováděn.

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

Problém lineárního programování se skládá z objektivní funkce, systému omezení a podmínky, aby proměnné nebyly záporné.

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

Takto položený optimalizační problém se nazývá problém matematického programování. hromada X se nazývá množina možných řešení a funkce se nazývá účelová funkce nebo cílová funkce. Možné řešení, pro které funkce nabývá největší (nebo nejmenší) hodnoty, se nazývá optimální řešení problému.

Je-li účelová funkce lineární a množina X je zadán pomocí soustavy lineárních rovnic a nerovnic, pak se úloha nazývá úloha lineárního programování (LPP). Obecná formulace problému lineárního programování je tedy následující:

najít extrém funkce

pod omezeními

za podmínek nezápornosti

Představme si notaci:

Zásoby i-tý typ zdroje;

výdaje i-tý typ zdroje pro výrobu j-tý typ produktu;

jednotkový zisk j-tý typ produktu.

V kompaktním zápisu má problém lineárního programování tvar:

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

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

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

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

Koeficienty pro proměnné v účelové funkci, které se nazývají odhady proměnných;

Variabilní index;

index omezení.

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

Proměnné x j označují takové druhy a způsoby činnosti, jejichž rozměry jsou neznámé a musí být stanoveny v průběhu řešení problému. Obvykle se v úkolech v zemědělství pod proměnnými rozumí požadovaná velikost odvětví hospodářství, druhy krmiv ve stravě, značky traktorů a zemědělských strojů atd. Stejná plodina nebo druh hospodářských zvířat může být vyjádřen více než jednou proměnnou podle konkrétních podmínek. Například komodita a krmné obilí; kukuřice na zrno, siláž, zelené krmivo; víceleté trávy na seno, senáž, zelené krmivo, travní moučku a semena atd.

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

Celkový počet proměnných zahrnutých do úkolu je dán povahou úkolu, konkrétními výrobními podmínkami, schopností sbírat informace atp.

Proměnné mohou být vyjádřeny v různých měrných jednotkách: ha, q, kg, ks, hlavy atd. Podle povahy se proměnné dělí na hlavní, doplňkové a pomocné. Mezi hlavní proměnné patří typy hledaných činností: odvětví hospodářství, druhy krmiv, značky automobilů. Další proměnné se nazývají proměnné, které se tvoří v procesu přeměny nerovností na rovnice. Mohou znamenat nedostatečně využitou část zdrojů, přebytek nad pravou stranou nerovnosti (pokud se jedná o nerovnost typu „ne více“). V úloze jsou zahrnuty pomocné proměnné za účelem stanovení odhadovaných hodnot získaných výrobních zdrojů, odhadovaných hodnot ukazatelů ekonomické efektivnosti výroby.

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

Technické a ekonomické koeficienty (a ij) s proměnnými v systému omezení vyjadřují míry vstupů výrobních zdrojů nebo míru výstupu na jednotku měření proměnné.

V obou případech je nutné, aby technicko-ekonomické koeficienty přesně odpovídaly plánovacímu období, pro které je problém řešen. Pokud je například problém vyřešen pro ekonomickou a matematickou analýzu výroby za minulé období, pak budou koeficienty vypočteny podle údajů z vykazování. Pokud je rozhodnuto pro budoucnost, pak by se koeficienty měly počítat pro tuto perspektivu.

Míry čerpání zdrojů se nejčastěji určují z referenčních knih, musí být přizpůsobeny příslušným konkrétním podmínkám. Faktory výnosu produktu se vypočítávají na základě plánovaných výnosů plodin a produktivity zvířat.

V případech, kdy je nutné zajistit předem stanovené vztahy mezi proměnnými, představují technické a ekonomické koeficienty koeficienty proporcionality. Například podíl plodin v osevním postupu nebo podíl některých krmiv v celkové skupině krmiv atd.

Omezení na pravé straně (b i) se nazývají konstanty, tzn. konstantní hodnoty. Patří sem objemy výrobních zdrojů – půda, práce, zařízení, hnojiva, investice atd. Výrobní zdroje je nutné určit s ohledem na jejich skutečný stav a bezpodmínečně zohlednit plánovací období. Navíc ty výrobní zdroje, jejichž využití je v průběhu roku nerovnoměrné, se počítají nejen za rok jako celek, ale i za jednotlivá vytížená období či měsíce (pracovní zdroje).

Výrobní zdroje jsou definovány v různých jednotkách: půda - v ha, pracovní zdroje - v člověkodnech nebo člověkohodinách, vybavení - v počtu strojních směn, směnný nebo denní výkon atd.

Určení dostupnosti produktivních zdrojů tedy není jednoduchá záležitost. Je nutné pečlivě analyzovat výrobní činnost ekonomiky, využití práce, půdy, technických a jiných zdrojů a teprve poté zahrnout jejich objemy do omezení.

Pravá strana omezení odráží nejen množství zdrojů, ale také objem vyrobených produktů na horní či spodní úrovni. Spodní úroveň se zobrazuje v těch případech, kdy je předem znám objem produkce, menší, než který by farma neměla vyrábět, a horní úroveň neumožňuje výrobu produktů nad určitý objem. Tato omezení nejsou vždy vyžadována. Téměř žádný problém zahrnující definici kombinace odvětví se však neobejde bez příslušných omezení produktů, jinak bude výsledkem jednostranné řešení. To je způsobeno tím, že efektivita průmyslových odvětví není stejná.

Ve všech ostatních omezeních jsou nuly umístěny na pravou stranu, protože formulují podmínky pro výrobu a použití produktů nebo odrážejí omezení proporcionální komunikace.

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

v promítnout do problému pouze ty podmínky, které skutečně omezují možnosti výroby;

v příliš mnoho omezení zvětšuje velikost problému a činí jej neřešitelným

Omezení jsou tří typů: rovná se (=), nerovnosti typu menší nebo rovné (≤), nerovnosti typu větší nebo rovné (≥). Například,

Kde i = 1, 2, … , m. Koeficienty pro proměnné jsou označeny aij, kde je index i– číslo omezení, index j je číslo proměnné, označují se volné členy (pravá strana omezení). b i, index i– číslo omezení.

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

Významově lze všechna omezení rozdělit na základní, doplňková a pomocná.

Hlavní omezení jsou to jsou ty, které se překrývají se všemi nebo většinou proměnných úlohy. S jejich pomocí se zpravidla odrážejí hlavní podmínky úkolu - pro půdu, práci, krmivo, živiny, technologii atd.

Další omezení jsou superponovány na část proměnných nebo na jednu proměnnou. Tato omezení se zavádějí v případech, kdy je nutné omezit velikost jednotlivých proměnných shora nebo zdola, například s přihlédnutím k požadavkům na střídání plodin nebo s přihlédnutím k fyziologickým limitům saturace stravy jednotlivými krmivy nebo jejich skupinami. Další omezení tedy odrážejí různé dodatečné podmínky, které vznikají během procesu modelování. Ale každé další omezení zužuje oblast svobody výběru. Proto by se měli do problému zavádět opatrně, v rozumných mezích a v nutných případech.

pomocná omezení, zpravidla nemají samostatný význam a do problému se zavádějí k formalizaci jednotlivých podmínek. Patří sem omezení, která zakládají proporcionální vztah mezi jednotlivými proměnnými nebo jejich skupinami.

Vyhodnocení proměnných v účelové funkci (s j) jsou koeficienty vyjadřující výši celkových příjmů nebo nákladů na měrnou jednotku proměnné. Hodnocení proměnné zpravidla vyjadřuje přijaté kritérium optimality. Může být předložen jak v naturáliích, tak v hotovosti, tzn. náklady na jednotku výroby (výrobní náklady).

Podmínka nezápornosti proměnných se zapisuje jako

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

V reálném životě výroby se na základě podmínek úlohy podle tohoto záznamu strukturálního ekonomicko-matematického modelu (EMM) sestaví seznam proměnných a omezení, připraví se výchozí informace, sestaví se podrobný EMM problému, který se následně zapíše ve formě matice (tabulky), zadá do počítače a výsledky se vypočítají a analyzují pomocí příslušného programu. i = 1, ..., m, (1.5)

j = 1, …, n. (1.6)

Vektor X = (X 1 , X 2 , …, X n), komponenty x j které splňují omezení (1.2) a (1.3) [nebo (1.5) a (1.6) v minimální úloze] se nazývá přijatelné řešení nebo přijatelný plán LP úkoly. Soubor všech přípustných plánů se nazývá mnoho možných plánů.

Kanonický forma úlohy lineárního programování se vyznačuje tím, že obsahuje účelovou funkci, všechna omezení rovnost, všechny proměnné jsou nezáporné.

Jakýkoli problém lineárního programování lze redukovat na problém lineárního programování v kanonické formě. K tomu musíte být v obecném případě schopni zredukovat problém maximalizace na problém minimalizace; přejít od omezení nerovností k omezením rovnosti a nahradit proměnné, které nepodléhají podmínce nezápornosti.

Pravidlo pro redukci problému lineárního programování na kanonickou formu se skládá z následujícího:

1) pokud je v původním problému požadováno určit maximum lineární funkce, pak byste měli změnit znaménko a hledat minimum této funkce;

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

3) pokud jsou mezi omezeními nerovnosti, pak se zavedením dalších proměnných nezáporných proměnných přemění na rovnosti. Například další proměnné S j Omezení typu menší nebo rovno (£) se zadávají se znaménkem plus:

Další proměnné S j větší nebo rovno (≥) omezení typu se zadávají se znaménkem mínus:

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

Přednáška 2

V kanonická forma

přípustné řešení PLP(přijatelný plán).

optimální řešení LLP.

Nutnost

Příklad.

Zapišme si problém kanonická forma

Speciální situace grafického řešení ZLP

Kromě případů, kdy je úkol jediné optimální řešení pro a , může být zvláštní situace:

1. úkol má nekonečné množství optimálních řešení – je dosaženo extrému funkce na segmentu ( alternativní optimum)- Obrázek 2;

2. úkol neřešitelný z důvodu neomezenosti ODR, nebo - Obrázek 3;

3. ODR - jediný bod Ah, pak;

4. úkol neřešitelný pokud má ODR prázdnou oblast.

A

Obrázek 2 Obrázek 3

Pokud je čára úrovně rovnoběžná se stranou oblasti možných řešení, pak je extrém dosaženo ve všech bodech strany. Problém má nekonečné množství optimálních řešení - alternativní optimum . Optimální řešení se najde podle vzorce

kde je parametr. Pro jakoukoli hodnotu od 0 do 1 můžete získat všechny body segmentu, pro každý z nich má funkce stejnou hodnotu. Odtud název – alternativní optimum.

Příklad. Vyřešte graficky problém lineárního programování ( alternativní optimum):

Otázky pro sebeovládání

1. Zapište úlohu lineárního programování v obecném tvaru.

2. Zapište úlohu lineárního programování v kanonické a standardní formě.

3. Jaké transformace lze použít k přechodu od obecné nebo standardní formy problému lineárního programování ke kanonickému?

4. Definujte možná a optimální řešení problému lineárního programování.

5. Které z řešení je „nejlepší“ pro problém minimalizace funkce if ?

6. Které z řešení je „nejlepší“ pro problém maximalizace funkce if ?

7. Napište standardní tvar matematického modelu úlohy lineárního programování se dvěma proměnnými.

8. Jak sestrojit polorovinu danou lineární nerovností se dvěma proměnnými ?

9. Jak se nazývá řešení soustavy lineárních nerovnic se dvěma proměnnými? Sestrojte na rovině obor proveditelných řešení takového systému lineárních nerovností, který:

1) má jedinečné řešení;

2) má nekonečnou množinu řešení;

3) nemá řešení.

10. Napište pro lineární funkci vektorový gradient, pojmenujte typ linií úrovně. Jak jsou čáry gradientu a úrovně umístěny vzájemně vůči sobě?

11. Formulujte algoritmus pro grafickou metodu řešení standardního LLP se dvěma proměnnými.

12. Jak zjistit souřadnice a hodnoty řešení, ?

13. Sestrojte oblast proveditelných řešení, gradientu a úrovňových čar pro úlohy lineárního programování, ve kterých:

1) je dosaženo v jediném bodě a - na segmentu ODR;

2) je dosaženo v jediném bodě ODS, a .

14. Uveďte geometrické znázornění LLP, pokud:

1) má jedinečná optimální řešení pro a ;

2) má sadu optimálních řešení pro .

Přednáška 2

grafická metoda pro nalezení optimálního řešení

1. Formy lineárních matematických modelů a jejich transformace

2. Grafická metoda řešení úlohy lineárního programování

3. ZVLÁŠTNÍ SITUACE GRAFICKÉHO ŘEŠENÍ LLP

4. Grafické řešení ekonomických problémů lineárního programování

Formy lineárních matematických modelů a jejich transformace

Matematický model úlohy lineárního programování (LPP) lze napsat v jedné ze tří forem.

V obecná podoba matematického modelu je nutné najít maximum nebo minimum účelové funkce; omezovací systém obsahuje nerovnosti a rovnice; ne všechny proměnné mohou být nezáporné.

V kanonická forma matematický model potřebuje najít maximum účelové funkce; omezovací systém se skládá pouze z rovnic; všechny proměnné jsou nezáporné.

Ve standardní formě matematického modelu je požadováno najít maximum nebo minimum funkce; všechna omezení jsou nerovnosti; všechny proměnné jsou nezáporné.

Řešením systému omezení, které splňuje podmínky nezápornosti proměnných, je tzv. přípustné řešení PLP(přijatelný plán).

Množina možných řešení se nazývá oblast proveditelných řešení LLP.

Volá se proveditelné řešení, ve kterém účelová funkce dosáhne extrémní hodnoty optimální řešení LLP.

Tyto tři formy LLP jsou ekvivalentní v tom smyslu, že každou z nich lze pomocí matematických transformací redukovat na jinou formu.

Nutnost přechod z jedné formy matematického modelu do druhé spojené s metodami řešení problémů: například simplexová metoda, široce používaná v lineárním programování, je aplikována na problém napsaný v kanonické formě a grafická metoda je aplikována na standardní formu matematického modelu.

Přechod ke kanonické notaci ZLP.

Příklad.

Zapišme si problém kanonická forma, zavedením další proměnné (zůstatek) se znaménkem „+“ do levé strany první nerovnosti systému omezení a další proměnnou se znaménkem „mínus“ do levé strany druhé nerovnosti.

Ekonomický význam různých doplňkových proměnných nemusí být stejný: závisí na ekonomickém smyslu omezení, do kterých jsou tyto proměnné zahrnuty.

Takže v problému využití surovin ukazují zbytek surovin a v problému výběru optimálních technologií ukazují nevyužitý čas podniku využívajícího určitou technologii; v problému řezání - uvolňování přířezů dané délky přesahující plán atd.