Formy lineárních matematických modelů a jejich transformace. Sestavte matematický model úlohy lineárního programování Obecný pohled na model lineárního programování

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 ne -podmínky negativity (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ý typ 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 produkce j-tého typu produkt.

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ě, že všechna omezení jsou 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ě.

MODEL LINEÁRNÍHO PROGRAMOVÁNÍ

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

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

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

Model lineárního programování(LP) probíhá, pokud ve studovaném systému (objektu) jsou omezení na proměnné a účelová funkce lineární.

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

1) optimální plánování v jakékoli sféře lidské činnosti – sociální, ekonomické, vědecké, technické i vojenské. Například při optimálním plánování výroby: rozdělování finančních, pracovních a jiných zdrojů, zásobování surovinami, řízení zásob atp.

2) dopravní úkol (nalezení optimálního plánu pro různé druhy dopravy, optimálního plánu rozmístění různých prostředků po objektech pro různé účely atd.)

MATEMATICKÝ POPIS MODELU LINEÁRNÍHO PROGRAMOVÁNÍ

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

uspokojování lineárních omezení ve formě rovností a nerovností

,

Kde - daná čísla,

a poskytnutí extrému lineární účelové funkce

,

kde jsou uvedena čísla, která se zapisuje jako

Přijatelné řešení nazývá se jakákoliv sada , splňující podmínky.

Oblast přípustných řešení je množina všech přípustných řešení.

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

Poznámky

1. Zmenšený model LP je Všeobecné. Jsou tu také Standard A kanonický formy LP modelů.

2. Podmínky existence implementace modelu LP:

– soubor přípustných řešení není prázdný;

- Objektivní funkce omezena (alespoň shora při hledání maxima a zdola při hledání minima).

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

Věta 1. hromada G, definovaný systémem omezení formuláře, je konvexní uzavřená množina ( konvexní mnohostěn s rohovými body - vrcholy.)

Věta 2. Lineární forma , definovaný na konvexním mnohostěnu

j=1,2,…,s

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

dosáhne extrému v jednom z vrcholů tohoto mnohostěnu.

Tato věta se nazývá teorém lineárního tvaru.

V souladu s Weierstrassovou větou je optimální řešení jedinečné a je globálním extrémem.

Existuje obecný analytický přístup k implementaci modelu LP - simplexní metoda. Při řešení úloh lineárního programování poměrně často neexistuje žádné řešení. To se děje z následujících důvodů.

Ukažme si první důvod na příkladu.

Z tohoto důvodu říkají, že omezení jsou nekonzistentní. Doménou přípustných řešení je prázdná množina.

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

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

V návaznosti na tradice lineárního programování dáme problému LP ekonomickou interpretaci. Nechte nás m typy zdrojů. Číslo typu zdroje j rovná se . Tyto zdroje jsou potřeba k výrobě n druhy zboží. Množství tohoto zboží označme symboly respektive. Typ položky i náklady . Výroba druhu zboží i by měla být omezena na respektive. Pro výrobu jednotky zboží typu i typ spotřebovaného zdroje j. Je nutné stanovit takový plán výroby zboží ( ), aby jejich celkové náklady byly minimální.

Problémy lineárního programování používané k optimalizaci fungování reálných objektů obsahují značné množství proměnných a omezení. To znemožňuje jejich řešení grafickými metodami. Při velkém množství proměnných a omezení se používají algebraické metody, které jsou založeny na iterativních výpočetních postupech. V lineárním programování bylo vyvinuto mnoho algebraických metod, které se liší ve způsobech konstrukce počátečního proveditelného řešení a v podmínkách přechodu z jedné iterace do druhé. Všechny tyto metody však vycházejí z obecných teoretických principů.

Obecnost hlavních teoretických ustanovení vede k tomu, že algebraické metody řešení úloh lineárního programování jsou si do značné míry podobné. Zejména téměř každý z nich vyžaduje předběžnou redukci problému lineárního programování na standardní (kanonickou) formu.

Algebraické metody pro řešení problému LP začínají jeho redukcí na standardní (kanonická) forma:

,

,

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

Jakýkoli problém lineárního programování lze zredukovat na standardní formu. Porovnání obecného modelu s kanonickým modelem nám umožňuje dospět k závěru, že pro redukci problému LP do standardního tvaru je nutné za prvé přejít od systému nerovností k rovnostem a za druhé transformovat všechny proměnné tak, aby že jsou nezáporné.

Přechod na rovnosti se provádí přidáním nezáporné zbytkové proměnné k levé straně omezení pro nerovnosti typu a odečtením nezáporné přebytečné proměnné z levé strany pro nerovnosti typu . Například nerovnost při přechodu do standardního tvaru se přemění na rovnost a nerovnost - k rovnosti . V tomto případě jsou jak reziduální, tak nadbytečná proměnná nezáporné.

Předpokládá se, že pravá strana nerovností je nezáporná. Jinak toho lze dosáhnout vynásobením obou stran nerovnosti "-1" a změnou jejího znaménka na opačné.

Pokud v původním problému lineárního programování není proměnná omezena znaménkem, lze ji reprezentovat jako rozdíl dvou nezáporných proměnných , Kde .

Důležitá vlastnost proměnných je, že pro jakékoli přípustné řešení může mít kladnou hodnotu pouze jeden z nich. To znamená, že pokud , Že a naopak. Proto ji lze považovat za reziduální, ale - za nadbytečnou proměnnou.

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

,

.

Musíte to přinést na standardní formulář. Všimněte si, že první nerovnost původní úlohy má znaménko , proto je nutné do ní zavést reziduální proměnnou. V důsledku toho dostaneme .

Druhá nerovnost má znaménko a pro transformaci do standardního tvaru vyžaduje zavedení redundantní proměnné , provedením této operace získáme .

Proměnná také není ohraničena znaménkem. Proto jak v účelové funkci, tak v obou omezeních musí být nahrazena rozdílem . Po provedení substituce získáme problém lineárního programování ve standardním tvaru, ekvivalentní původnímu problému:

.

Problém lineárního programování, psaný ve standardním tvaru, je problém nalezení extrému účelové funkce na množině vektorů, které jsou řešením soustavy lineárních rovnic, při zohlednění podmínek nezápornosti. Jak víte, systém lineárních rovnic nemusí mít žádná řešení, mít jediné řešení nebo mít nekonečný počet řešení. Optimalizace účelové funkce je možná pouze v případě, že systém má nekonečno mnoho řešení. Systém lineárních rovnic má nekonečný počet řešení, pokud je konzistentní (hodnota hlavní matice se rovná hodnosti rozšířené) a pokud je hodnost hlavní matice menší než počet neznámé.

Nechť je hodnost matice omezovacího systému rovna m. To znamená, že matice má alespoň jednu vedlejší mřád se nerovná nule. Bez ztráty obecnosti můžeme předpokládat, že minor je umístěn v levém horním rohu matice. Toho lze vždy dosáhnout změnou číslování proměnných. Tato nenulová vedlejší kategorie m se nazývá základna. Udělejme systém od začátku m rovnice soustavy a zapište ji takto:

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

FEDERÁLNÍ AGENTURA PRO VZDĚLÁVÁNÍ

FGOU NA "PSKOVSKÉ VYSOKÉ ŠKOLE STAVEBNÍ A EKONOMICKÉ"

Předmět "Matematické metody"

Problém lineárního programování

Práce na kurzu

Studentská skupina 315-PO

Andrejev Dmitrij Alexandrovič

Vedoucí kurzu

Vasiljeva Natalia Anatolievna

Pskov 2009

Úvod

Kapitola Ι Lineární programování

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

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

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

Kapitola ΙΙ Řešení úlohy simplexovou metodou

§ 1 Prohlášení o problému

§ 2 Sestavení matematického modelu problému

§ 3 Algoritmy pro řešení úlohy simplexovou metodou

§ 4 Konstrukce výchozího referenčního řešení Gaussovou metodou

§ 5 Řešení problému

Závěr

Literatura

Úvod

V současné době je řada problémů plánování a řízení v sektorech národního hospodářství, stejně jako velké množství konkrétních aplikačních problémů, řešena metodami matematického programování. Nejrozvinutější v oblasti řešení optimalizačních úloh jsou metody lineárního programování. Tyto metody umožňují dostatečně přesně popsat širokou škálu úkolů obchodní činnosti, jako je plánování prodeje; umístění maloobchodní sítě města; plánování komoditního zásobování města, okresu; připojování obchodních podniků k dodavatelům; organizace racionální přepravy zboží; distribuce obchodních pracovníků na pozice; organizace racionálních nákupů potravinářských výrobků; alokace zdrojů; plánování investic; optimalizace mezisektorových vztahů; výměna komerčního vybavení; stanovení optimálního sortimentu zboží v omezené oblasti; zavedení racionálního způsobu provozu.

V úlohách lineárního programování jsou kritérium účinnosti a funkce v systému omezení lineární.

Pokud v matematickém programovacím problému existuje časová proměnná a kritérium účinnosti je vyjádřeno pomocí rovnic popisujících průběh operací v čase, pak je takový problém problémem dynamického programování.

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

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

Provoz modelu pak zahrnuje sběr a zpracování informací, vkládání zpracovaných informací do počítače, výpočty na základě vyvinutých programů rozvrhů a nakonec vydávání výsledků výpočtu (ve formě vhodné pro uživatele) pro jejich využití v oblasti výrobní činnosti.

Kapitola Ι Lineární programování

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

Lineární programování je směr matematického programování, který studuje metody řešení extrémních problémů, které se vyznačují lineárním vztahem mezi proměnnými a lineární účelovou funkcí. Pro řešení úloh lineárního programování je sestaven matematický model úlohy a zvolena metoda řešení.

Výrok o problému komerční činnosti lze znázornit jako matematický model lineárního programování, pokud lze účelovou funkci znázornit jako lineární formu a vztah s omezenými zdroji lze popsat pomocí lineárních rovnic nebo nerovnic. Kromě toho je zavedeno další omezení - hodnoty proměnných musí být nezáporné, protože představují takové veličiny, jako je obrat, pracovní doba, náklady a další ekonomické ukazatele.

Geometrický výklad ekonomických problémů umožňuje vizualizovat jejich strukturu, identifikovat rysy a otevírá cesty ke studiu složitějších vlastností. Úlohu lineárního programování se dvěma proměnnými lze vždy vyřešit graficky. Již v trojrozměrném prostoru se však takové řešení stává komplikovanějším a v prostorech, jejichž rozměry jsou větší než tři, je grafické řešení, obecně řečeno, nemožné. Případ dvou proměnných nemá zvláštní praktický význam, ale jeho zohlednění objasňuje vlastnosti problémů lineárního programování, vede k myšlence jeho řešení, geometricky přehledné způsoby řešení a způsoby jejich praktické realizace.

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

Před řešením úlohy vytvoříme její matematický model.

Matematický model je soubor vztahů sestávající z lineární účelové funkce a lineárních omezení proměnné.

Princip sestavení matematického modelu.

1. Vyberte proměnné úlohy.

Proměnnými problému jsou množství

Které plně charakterizují ekonomický proces popsaný v úloze. Obvykle se zapisuje jako vektor X = () Navíc, )

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

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

Obecně je systém napsán jako

3. Cílová funkce je nastavena.

Účelová funkce je funkce Z(X), která charakterizuje kvalitu úlohy, jejíž extrém je třeba najít. Obecně se účelová funkce zapisuje Z(X) =

Že. matematický model má formu najít proměnné problému

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

a podmínku nezápornosti

0 (j = ), která poskytuje extrém účelové funkce Z(Y) =

Přijatelné řešení problému lineárního programování je jakákoliv sada proměnných hodnot, která vyhovuje systému omezení a podmíněné nezápornosti.

Množina přípustných řešení tvoří oblast přípustných řešení problému (ODD).

Optimální řešení je proveditelné řešení problému, ve kterém cílová funkce dosahuje extrému.

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

Matematický model problému musí mít kanonickou formu.

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

Pokud má systém alespoň jednu nerovnost nebo je jakákoli proměnná neomezená podmínkou nezápornosti, pak má problém standardní tvar. Chcete-li problém převést do kanonické podoby, musíte:

přejděte od nerovností k rovnici následovně: na levé straně nerovností zavedeme další proměnnou s koeficientem (+1) pro nerovnost (

) a (-1) pro nerovnost () další proměnné nejsou vnuceny cílovou nezáporností, pak je nahrazena rozdílem dvou nezáporných proměnných, tedy: = - (

Celkový pohled na kanonickou formu:

Kapitola ΙΙ Řešení úlohy simplexovou metodou

Simplexová metoda je metoda postupného zlepšování plánu (řešení), nejefektivnější a používá se k řešení libovolného problému lineárního programování.

Název metody je z latinského simplecx – jednoduchý protože. z počáteční oblasti přípustných řešení úlohy měl nejjednodušší formu. Myšlenky metody navrhl ruský matematik Kontarovič L.V. v roce 1939 a poté tuto myšlenku rozvinul a rozvinul v roce 1949 J. Danzig.

Simplexová metoda umožňuje konečný počet kroků k nalezení optimálního řešení nebo k prokázání, že neexistuje.

§ 1 Prohlášení o problému

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

Jakýkoli problém lineárního programování lze redukovat na problém lineárního programování v kanonické formě. K tomu 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. Maximalizace nějaké funkce je ekvivalentní minimalizaci stejné funkce s opačným znaménkem a naopak.

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

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

Příklad 1. Redukce úlohy lineárního programování na kanonickou formu:

min L \u003d 2x 1 + x 2 - x 3;
2x 2 - x 3 < 5;
x 1 + x 2 - x 3 > -1;
2x 1 - x 2 < -3;
x1 < 0; x2 > 0; x3 ≥ 0.

Zaveďme vyrovnávací proměnné do každé rovnice omezovacího systému x 4, x 5, x 6. Systém bude zapsán ve formě rovnosti a v první a třetí rovnici systému omezení budou proměnné x 4, x 6 se zadávají na levé straně se znaménkem "+" a ve druhé rovnici proměnná x5 zadáno se znaménkem „-“.

2x 2 - x 3 + x 4 \u003d 5;
x 1 + x 2 - x 3 - x 5 \u003d -1;
2x 1 - x 2 + x 6 \u003d -3;
x4 > 0; x5 > 0; x6 ≥ 0.

Volné členy v kanonickém tvaru musí být kladné, proto vynásobíme poslední dvě rovnice -1:

2x 2 - x 3 + x 4 \u003d 5;
-x 1 - x 2 + x 3 + x 5 = 1;
-2x1 + x2 - x6 = 3.

V kanonické formě psaní úloh lineárního programování musí být všechny proměnné zahrnuté v systému omezení záporné. Předpokládejme to x 1 \u003d x 1 '- x 7 , Kde x 1‘ ≥ 0, x 7 ≥ 0 .

Dosazením tohoto výrazu do systému omezení a účelové funkce a zápisem proměnných ve vzestupném pořadí indexu získáme problém lineárního programování prezentovaný v kanonické podobě:

L min \u003d 2x 1' + x 2 - x 3 - 2x 7;
2x 2 - x 3 + x 4 \u003d 5;
-xi'- x 2 + x 3 + x 5 + x 7 = 1;
-2x 1 ' + x 2 - x 6 + 2x 7 = 3;
x 1' > 0; x i ≥ 0, i=2, 3, 4, 5, 6, 7.

Podmínka optimálnosti pro základní návrh kanonické úlohy LP. Simplexová metoda a její konvergence.

Simplexová metoda je univerzální, protože umožňuje řešit téměř jakýkoli problém lineárního programování zapsaný kanonická forma.

Myšlenka simplexové metody postupné zlepšování plánu, je to, že počínaje nějakým počátečním referenčním řešením, postupně řízený pohyb referenčním řešením problému k optimálnímu.

Hodnota účelové funkce neklesá s tímto posunem pro úkoly na maximum.

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

Základní nezáporné řešení se nazývá podpůrné řešení.

Algoritmus simplexní metody

1. Matematický model problému musí být kanonický. Pokud je nekanonický, musí být redukován na kanonickou formu.

2. Najdeme výchozí referenční řešení a zkontrolujeme jeho optimalitu.
Chcete-li to provést, vyplňte simplexní tabulku 1.
Všechny řádky tabulky 1. kroku se vyplňují podle údajů systému omezení a účelové funkce.

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

1. Pokud jsou všechny koeficienty posledního řádku simplexní tabulky Dj³ 0, pak nalezen

řešení optimální.

2 Pokud alespoň jeden koeficient DJ £ 0, ale s odpovídající proměnnou neexistuje jediný kladný odhadovaný vztah, pak řešení zastavujeme úkoly, protože F(X) ® ¥ , tj. účelová funkce není omezena v oblasti přípustných řešení.

Pokud je alespoň jeden koeficient posledního řádku záporný a odpovídající proměnná má alespoň jeden pozitivní hodnotící vztah, pak musíte jít na jinou základní linii.

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

5. Pokud alespoň jeden koeficient Dk< 0 ,Že k - tis sloupec přijmout pro vedoucího.

6. Pro vedoucí linie přijmout ten, který odpovídá minimální poměr volných členů bi na kladné koeficienty vůdce, k - to sloupec.

7. Zavolá se prvek v průsečíku vedoucích řádků a sloupců vedoucí prvek.

Vyplnění simplexní tabulky 2 :

· vyplňte základní sloupec nulami a jedničkou

· přepište úvodní čáru jejím rozdělením na úvodní prvek

pokud má úvodní řádek nuly, pak lze odpovídající sloupce přenést do další simplexní tabulky

· zbývající koeficienty se zjistí podle pravidla „obdélník“.

Získáme nové referenční řešení, které zkontrolujeme pro optimalizaci:

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

Pokud ne, pak vyplníme simplexovou tabulku 8. kroku a tak dále.

Je-li účelová funkce F(X) vyžaduje nalezení minimální hodnota, pak kritérium optimalita problému je nekladnost koeficientů D j pro všechna j = 1,2,…n.

Konvergence simplexové metody. Degenerace v problémech LP. Nejdůležitější vlastností každého výpočetního algoritmu je konvergence, tj. možnost získat požadované výsledky (s danou přesností) v konečném počtu kroků (iterací) při jeho aplikaci.

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

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

⇐ Předchozí12345Další ⇒

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

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

Optimální řešení - Problém - Lineární programování

Strana 1

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

Pomocí optimálního řešení úlohy lineárního programování je možné nalézt přípustné změny v DS, pro které L stále zůstává konstantní.

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

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

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

Je dokázáno, že optimální řešení problému lineárního programování se nachází na hranici oblasti přípustných hodnot řízených veličin, což je mnohostěn v /r-rozměrném prostoru, definovaný systémem lineárních vazeb. Souřadnice každého vrcholu jsou určeny řešením soustavy rovnic (omezení) a za přítomnosti n řízených proměnných a m omezení musí St p vyřešit soustavu m rovnic. Kombinace Spn n (m - n velmi rychle roste s rostoucím typem, takže hledání řešení vyžaduje velmi velké množství výpočtů, které jsou nepřístupné ani pro počítač.

V případě D 1 se tedy optimální řešení úlohy lineárního programování ukazuje jako automaticky celočíselné.

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

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

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

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

PROBLÉM LINEÁRNÍHO PROGRAMOVÁNÍ

Takové cyklování se někdy nazývá kontinuální degenerace. Bohužel se tento jev často vyskytuje u problémů s vysokorozměrným středním PI. Existuje také mnoho příkladů nízkorozměrných problémů (ne více než 10 proměnných a rovnic), které k dosažení konvergence vyžadují tisíce iterací.

V těchto případech se používá simplexová metoda, což je iterativní (krok za krokem) postup pro určení optimálního řešení úlohy lineárního programování. Výpočty simplexovou metodou začínají určením proveditelného řešení a následně se nalézají další proveditelná řešení a kontrolují se možnosti jejich zlepšení. Přechod z jednoho řešení na druhé pokračuje, dokud nebudou možná nová vylepšení. Existují široce rozšířené standardní počítačové programy, které používají simplexovou metodu k řešení takových problémů řízení, které lze reprezentovat jako problémy lineárního programování.

Má-li systém lineárních vazeb speciální strukturu, například tvoří-li síťový model, lze v kroku 2 při hledání optimálního řešení problému lineárního programování této okolnosti využít.

Myšlenka proporcionálního rozdělení byla implementována ve formě dvoufázového výpočetního algoritmu navrženého I.I. Dikinem, který v podstatě využívá vlastnosti metody vnitřních bodů k vývoji relativně vnitřního bodu množiny optimálních řešení lineárního programování. problém. Tato vlastnost znamená, že okrajové hodnoty podle podmínek nerovnosti (2.3.2) - (2.3.4) jsou dosaženy pouze pro ty proměnné, které mají tyto okrajové hodnoty pro jakékoli jiné optimální řešení.

Stránky:     1   2

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

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

(10)

Nechť je soustava nerovnic (10) kompatibilní (má alespoň jedno řešení). Jakákoli nerovnost této soustavy geometricky definuje polorovinu s hraniční čárou Podmínky nezápornosti definují poloroviny s odpovídajícími hraničními čarami A.

Vzhledem k tomu, že systém je kompatibilní, tvoří poloroviny jako konvexní množiny, protínající se, společnou část, která je konvexní množinou a je souborem bodů, z nichž souřadnice každého jsou řešením této soustavy. Souhrn všech těchto bodů se nazývá řešení polygon. Může to být bod, úsečka, paprsek, přímka, uzavřený mnohoúhelník, neomezená polygonální plocha.

Řešením LLP je geometricky hledání takového bodu polygonu řešení, jehož souřadnice dodávají cílové funkci největší (nejmenší) hodnotu. Navíc všechny body mnohostěnu jsou přípustná řešení.

Zvažte tzv nivelační čára Objektivní funkce z, tj. čára, podél které tato funkce nabývá stejné pevné hodnoty: nebo

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

1. Na rovině odpovídající omezením je vytvořena polygonální oblast proveditelných řešení. Poté se vytvoří gradientní vektor

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

2. Přímka (přímka funkční úrovně z) kolmý na gradientový vektor se pohybuje rovnoběžně sám se sebou ve směru gradientového vektoru v případě maximálního problému (a v opačném směru v případě minimálního problému), dokud neopustí oblast proveditelných řešení. Mezní bod (nebo body) regionu jsou optimálními body.

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

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

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

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

Sestrojme mnohoúhelník všech přípustných řešení OABCD a směrový vektor účelové funkce (obr. 1). Směr vektoru gradientu udává směr rostoucí účelové funkce. Protože uvažovaným problémem je najít maximum, posuneme čáru kolmo k vektoru ve směru tohoto vektoru rovnoběžně se sebou samým, dokud tato čára neopustí oblast přípustných řešení. Na hranici kraje, v našem případě na bod S a bude existovat řešení problému. Tečka S je na průsečíku čar a . Proto jsou jeho souřadnice určeny řešením soustavy těchto rovnic:

odkud, tj. tečka S má souřadnice (6, 4).

Maximum (maximální hodnota účelové funkce) se rovná: Odpovědět: při optimálním řešení, tj. maximálního zisku lze dosáhnout výrobou 6 kusů prvního a 4 kusů druhého výrobku.

ÚVOD

Moderní ekonomická teorie na mikro i makro úrovni zahrnuje matematické modely a metody jako přirozený, nezbytný prvek. Využití matematiky v ekonomii umožňuje za prvé identifikovat a formálně popsat nejdůležitější, podstatné vztahy mezi ekonomickými proměnnými a objekty: studium tak složitého objektu vyžaduje vysoký stupeň abstrakce. Za druhé, z jasně formulovaných výchozích dat a vztahů lze dedukčními metodami získat závěry, které jsou adekvátní zkoumanému objektu ve stejném rozsahu jako učiněné předpoklady. Za třetí, metody matematiky a statistiky umožňují získat nové poznatky o objektu induktivním způsobem: vyhodnotit formu a parametry závislostí jeho proměnných, které nejvíce odpovídají dostupnému pozorování. Konečně, za čtvrté, používání jazyka matematiky nám umožňuje přesně a kompaktně uvádět ustanovení ekonomické teorie, formulovat její pojmy a závěry.

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

Podstata optimalizačních metod spočívá v tom, že na základě dostupnosti určitých zdrojů se volí takový způsob jejich využití (distribuce), který poskytuje maximum (minimum) pro nás zajímavého ukazatele.

Jako metody optimalizace v ekonomice se využívají všechny hlavní úseky matematického programování (plánování).

Matematická disciplína, která studuje extrémní (maximální nebo minimální) problémy řízení, plánování a vývoje metod jejich řešení, je tzv. matematického programování.

Obecně platí, že matematická formulace extrémního problému spočívá v určení největší nebo nejmenší hodnoty účelové funkce
vzhledem k tomu ,

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

Podle typu cílové funkce a omezení se matematické programování dělí na lineární a nelineární. Většina

studovaná sekce matematického programování je lineární programování.

Definice.

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

Lineární programování - nauka o metodách používání a hledání extrémních (maximálních a minimálních) hodnot lineární funkce, na jejichž neznámé jsou kladena lineární omezení.

Tato lineární funkce se nazývá účelová funkce a omezení ve formě rovnic nebo nerovnic se nazývá systém omezení.

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

Zvažte některé problémy lineárního programování (LPP).

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

Pro výrobu různých produktů Společnost používá tři různé druhy surovin. Míry spotřeby surovin pro výrobu jednoho výrobku , stejně jako celkem

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

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

Vytvořme matematický model tohoto problému.

Označte požadovaným výstupem produktů , průchozí produkty ,

prostřednictvím produktů.

Vzhledem k tomu, že pro každý typ suroviny existují nákladové normy, můžeme pro výrobu všech produktů zjistit celkové náklady na každý druh suroviny. Z tabulky vyplývá, že celkový objem surovin I. druhu bude, II -
,

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

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

(1)

Ekonomicky, proměnné může mít pouze nezáporné hodnoty:

(2)

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

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

Tento problém lze snadno zobecnit na případ uvolňování typů výrobků využívajících druhy surovin (zdrojů).

Označit podle - počet jednotek výrobků plánovaných k výrobě, - zásoba zdrojů - -tého typu, - měrná spotřeba - -tého zdroje na výrobu -tých výrobků. - zisk z prodeje jednotky produktu - druh.

Pak bude mít ekonomický a matematický model problému využití zdrojů v obecném nastavení podobu: najděte takový plán
výstup, který splňuje hlavní systém omezení

další systém omezení

kde je účelová funkce

nabývá maximální hodnoty.

Komentář. K vytvoření matematického modelu ZLP potřebujete:

– zadejte zápis proměnných;

- na základě účelu ekonomického výzkumu sestavit objektivní funkci;

- s přihlédnutím k omezením v použití ekonomických ukazatelů úkolu a jejich kvantitativním vzorcům sepište systém omezení.

Řešení úloh lineárního programování je založeno na konceptech analytické geometrie v -rozměrném vektorovém prostoru.

Redukce obecného LLP na kanonickou formu.

Celkový pohled na ZLP je následující:

(1)

(2)

(3)

kde relace (1) je účelová funkce, (2) je systém základních omezení, (3) je systém dalších omezení.

Vztahy (2) a (3) tvoří úplný systém omezení.

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

Definice . LLP se uvádí v kanonické podobě, pokud je jeho systém základních omezení reprezentován rovnicemi.

Definice. LLP se uvádí ve standardní kanonické formě, pokud jsou splněny následující podmínky:

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

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

3) problém minimalizace účelové funkce je vyřešen;

4) pravé části systému základních omezení jsou nezáporné;

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

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ů mnoha 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.

To lze provést takto:

Vezměte lineární nerovnost

a přidejte na jeho levou stranu nějakou hodnotu , takže se nerovnost změní na rovnost

V tomto případě je tato hodnota nezáporná.

Příklad

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.

Problém zapíšeme v kanonické podobě:

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

Tato metoda je metodou účelového výčtu referenčních řešení úlohy lineárního programování. Umožňuje konečný počet kroků buď k nalezení optimálního řešení, nebo ke zjištění, že žádné optimální řešení neexistuje.

Algoritmus simplexové metody pro řešení úloh lineárního programování

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

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

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

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

3. Vypočítejte odhady rozšíření vektorů z hlediska báze referenčního řešení a vyplňte tabulku simplexové metody.

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

5. Je-li splněna podmínka existence množiny optimálních řešení, pak prostým výčtem jsou nalezena všechna optimální řešení

Příklad řešení úlohy simplexovou metodou

Příklad 1

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

Minimalizujte hodnotu funkce

F = 10×1 - 4×3 max

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

Dovedeme problém do kanonické podoby.

K tomu zavedeme další proměnnou x 5 s koeficientem +1 na levou stranu prvního omezení nerovnosti. Proměnná x 5 je zahrnuta v účelové funkci s nulovým koeficientem (tj. není zahrnuta).

Dostaneme:

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

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

Najdeme výchozí referenční řešení. Abychom to udělali, srovnáme volné (nevyřešené) proměnné s nulou x1 = x3 = 0.

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

Odhady expanzí vektorů podmínek z hlediska báze referenčního řešení vypočítáme pomocí vzorce:

Δ k \u003d C b X k - c k

· C b = (с 1 , с 2 , … , с m) - vektor koeficientů účelové funkce se základními proměnnými

· X k = (x 1k , x 2k , … , x mk) - expanzní vektor odpovídajícího vektoru A k bázi referenčního řešení

· C to - koeficient účelové funkce pro proměnnou x to.

Odhady vektorů zahrnutých do základu jsou vždy rovny nule.

Referenční řešení, koeficienty expanzí a odhady expanzí vektorů podmínek z hlediska báze referenčního řešení jsou zapsány v simplexní tabulce:

Nad tabulkou jsou pro usnadnění výpočtu odhadů zapsány koeficienty účelové funkce. První sloupec "B" obsahuje vektory zahrnuté v základu referenčního roztoku. Pořadí zápisu těchto vektorů odpovídá počtu povolených neznámých v omezujících rovnicích. Ve druhém sloupci tabulky "S b" jsou zapsány koeficienty účelové funkce se základními proměnnými ve stejném pořadí. Při správném uspořádání koeficientů účelové funkce ve sloupci "C b" jsou odhady jednotkových vektorů zahrnutých do báze vždy rovny nule.

V posledním řádku tabulky s odhady Δ k ve sloupci "A 0" jsou hodnoty účelové funkce zapsány na referenčním řešení Z(X 1).

Počáteční referenční řešení není optimální, protože v úloze maxima jsou odhady Δ 1 = -2, Δ 3 = -9 pro vektory A 1 a A 3 záporné.

Podle věty o zlepšení referenčního řešení, pokud má alespoň jeden vektor v maximální úloze negativní odhad, pak je možné najít nové referenční řešení, na kterém bude hodnota účelové funkce větší.

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

Přírůstek účelové funkce se zjistí podle vzorce:

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

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

Přírůstek účelové funkce zjistíme, když je do báze zaveden první vektor

ΔZ 1 \u003d - 6 * (- 2) \u003d 12,

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

Pro rychlejší přiblížení se k optimálnímu řešení je tedy nutné zavést do báze referenčního řešení místo prvního vektoru báze A6 vektor A3, neboť minima parametru θ 03 je dosaženo v prvním řádku. (l = 1).

Jordanovu transformaci provedeme s prvkem X13 = 2, získáme druhé referenční řešení

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

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

(tabulka 26.2)

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

Pro zlepšení řešení je nutné zavést vektor A2 do báze referenčního řešení.

Určíme číslo vektoru odvozené z báze. K tomu vypočítáme parametr θ 02 pro druhý sloupec, je roven 7 pro l = 2.

Ze základu tedy odvodíme druhý vektor základu A4.

Jordanovu transformaci provedeme s prvkem x 22 = 3, získáme třetí referenční řešení

X3 = (0.7.10.0.63.0)

B2 \u003d (A3, A2, A5) (tabulka 26.3).

Toto řešení je jediné optimální, protože pro všechny vektory, které nejsou zahrnuty v základu, jsou odhady kladné

Δ 1 \u003d 7/2, Δ 4 \u003d 2, Δ 6 \u003d 7/2.

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

⇐ Předchozí123456789Další ⇒

V praxi jsou omezení v problému lineárního programování často dána ne rovnicemi, ale nerovnicemi.

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

Nechť existuje problém lineárního programování s proměnnými , ve kterém omezení uložená na proměnné mají formu lineárních nerovností. V některých z nich může být znaménko nerovnosti a v jiných (druhý typ je redukován na první prostou změnou znaménka obou částí). Proto nastavíme všechna omezení nerovnosti ve standardním tvaru:

Je potřeba najít takovou sadu nezáporných hodnot, která by uspokojila nerovnosti (4.1) a navíc by minimalizovala lineární funkci:

Od takto nastoleného problému lze snadno přejít k hlavnímu problému lineárního programování. Skutečně zavádíme notaci:

kde jsou nějaké nové proměnné, které budeme nazývat "doplňkové". Podle podmínek (4.1) tyto dodatečné proměnné, jak by měly být, musí být nezáporné.

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

Jak vidíte, máme před sebou v čisté podobě hlavní problém lineárního programování (LPP). Rovnice (4.3) jsou uvedeny v již vyřešené podobě vzhledem k základním proměnným, které jsou vyjádřeny pomocí volných proměnných. Funkce L je vyjádřena pouze pomocí „počátečních“ proměnných (koeficienty „dodatečných“ proměnných v ní jsou rovny nule).

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

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

a minimalizaci lineární funkce

Je třeba tento problém zredukovat na formu OLP.

Řešení. Přivedeme nerovnosti (4.4) do standardního formuláře;

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

Úkolem je najít nezáporné hodnoty proměnných

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

Ukázali jsme, jak je možné přejít od problému lineárního programování s omezeními nerovnosti k problému s omezeními rovnosti (ELP). Obrácený přechod je vždy možný – od LLP k problému s omezeními nerovností. Pokud jsme v prvním případě zvýšili počet proměnných, tak v druhém případě jej snížíme, vyřadíme základní proměnné a ponecháme pouze ty volné.

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

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

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

Řešení. Od , vybereme některé dvě z proměnných jako volné. Všimněte si, že proměnné nelze vybrat jako volné, protože jsou spojeny první z rovnic (4 7): hodnota jedné z nich je zcela určena hodnotou druhé a volné proměnné musí být nezávislé.

Ze stejného důvodu nelze volit proměnné jako volné (spojuje je druhá rovnice). Vybíráme jako volné proměnné a vše ostatní vyjadřujeme v nich:

Protože podmínky (4 9) lze nahradit nerovnostmi:

Předejme ve vyjádření lineární funkce L volným proměnným Dosazení v L místo a jejich vyjádření (4.9). dostat.

3.1. Obecný problém lineárního programování

Lineární programování- jedná se o nejrozvinutější sekci matematického programování, pomocí které se provádí analýza a řešení extrémních úloh s lineárními vazbami a omezeními.

Lineární programování zahrnuje řadu heuristických (přibližných) metod řešení, které umožňují za daných podmínek ze všech možných možností řešení výrobních problémů vybrat tu nejlepší, optimální. Mezi tyto metody patří - grafická, simplexní, potenciální metoda (modifikovaný distribuční způsob - MOD), Khičkovova, Kreko, Vogelova aproximační metoda a další.

Některé z těchto metod jsou spojeny společným názvem – distribuční neboli transportní metoda.

Rodištěm lineárního programování je Rusko. První práce o lineárním programování od budoucího akademika L.V. Kantorovich byly publikovány v roce 1939. V roce 1975 obdržel Nobelovu cenu za ekonomii za vývoj metod lineárního programování. Protože většina prací akademika L.V. Kantorovič se věnuje řešení dopravních problémů, lze mít za to, že zmíněná Nobelova cena značí i zásluhy ruské dopravní vědy.

V silniční dopravě se od 60. let 20. století používají metody lineárního programování k řešení velkého množství nejdůležitějších výrobních problémů, a to: zmenšování vzdálenosti nákladní dopravy; sestavení optimálního dopravního schématu; výběr nejkratších tras pohybu; úkoly přepravy různých, ale zaměnitelných nákladů; denní plánování směn; plánování přepravy malosériových nákladů; rozmístění autobusů po trasách a další.

Vlastnosti modelu lineárního programování jsou následující:

Cílová funkce a omezení jsou vyjádřeny lineárními závislostmi (rovnicemi nebo nerovnicemi);

Počet závislostí je vždy menší než počet neznámých (podmínka nejistoty);

Nezápornost požadovaných proměnných. Obecná forma psaní modelu lineárního programování ve zkrácené formě je následující:

Nalézt X ij ≥ 0 (j = 1, 2…n) při následujícím typu omezení:

Tato omezení minimalizují (nebo maximalizují) účelovou funkci

Standardní formou psaní lineárního programovacího modelu je systém lineárních rovnic zapsaných v kanonický tvaru, tj. ve tvaru lineárních rovností, v nezáporných číslech:

a 11 x 1 + a 12 x 2 + ... + a 1 n x n \u003d b 1;

a 21 x 1 + a 22 x 2 + ... + a 2 n x n \u003d b 2 ; (3.1)

……………………………..

a m x 1 + a m 2 x 2 + ...+ a mn x n = b m ..

Pokud je model zapsán ve tvaru nerovností v nezáporných číslech, tj. má tvar

a 11 x 1 + a 12 x 2 + ... + a 1 n x n ≤ b 1;

a 21 x 1 + a 22 x 2 + ... + a 2 n x n ≤ b 2 ; (3.2)

……………………………..

a m x 1 + a m 2 x 2 + …+ a mn x n ≤ b m,..

pak se tento záznam redukuje na kanonický formulář (3.1) zavedením dalších proměnných x n +1> 0 (i=1,2…m) na levou stranu nerovnosti (nebo snížení počtu proměnných, pokud znaménko nerovnosti směřuje opačným směrem). Základ tvoří další proměnné.

Standardní formou řešení problému lineárního programování je nalezení řešení soustavy lineárních rovnic v nezáporných číslech, která minimalizují účelovou funkci. Účelová funkce pak má tvar

L = c 1 x 1 + c 2 x 2 ... c n x n → min, (3,3)

Kde s 1, s 2 … s n jsou objektivní funkční koeficienty L s proměnnými X j

Další proměnné vstupují do účelové funkce s nulovými koeficienty.

V případě maximalizace účelové funkce L znaménka proměnných účelové funkce by se měla obrátit a opět se dostaneme k problému minimalizace, tzn. jeden úkol je redukován na jinou náhradu L na - L nebo max L=min(- L).

Základní řešení soustavy lineárních rovnic (3.1) je řešení, ve kterém jsou nebázickým proměnným dány nulové hodnoty.

Základní řešení se nazývá přípustné, ve kterém jsou proměnné zahrnuté v bázi nezáporné.

Přípustné řešení, které maximalizuje (nebo minimalizuje) účelovou funkci (3.3), se nazývá optimální.

Každý problém lineárního programování odpovídá jinému problému, nazývanému problém duálního lineárního programování. Původní problém s ohledem na duální se nazývá přímý problém. Prvotní a duální problémy tvoří pár, který se v lineárním programování nazývá duální pár. Prvotní a duální pár tvoří asymetrický pár, když je primární problém zapsán v kanonické formě, a symetrický pár, když jsou podmínky problémů zapsány jako nerovnosti.

Pravidla pro sestavení matematického modelu duálního problému vycházejí z pravidel maticového počtu.

Koncept duality je široce používán při analýze problémů lineárního programování. Vlastnost duality je podrobně zvažována v každém konkrétním případě.

3.2. Grafo-analytická metoda

Grafoanalytická metoda je jednou z nejjednodušších metod lineárního programování. Jasně odhaluje podstatu lineárního programování, jeho geometrickou interpretaci. Jeho nevýhodou je, že umožňuje řešit problémy se 2 nebo 3 neznámými, tj. je použitelný na úzký okruh problémů. Metoda je založena na pravidlech analytické geometrie.

Řešení problému se dvěma proměnnými x 1 A x 2, která by podle smyslu úlohy neměla být záporná, se provádí v systému kartézských souřadnic. Rovnice x 1=0 a x 2= 0 jsou osy souřadnicového systému prvního kvadrantu

Zvažme metodu řešení na konkrétním příkladu.

Příklad 3.1. Na skladě je 300 tun výrobků z pěnového betonu a 200 tun výrobků z oceli. Automobilový podnik potřebuje dodávat tyto produkty do zařízení ve výstavbě. Automobilka disponuje nákladními vozy KAMAZ - 5320 a

ZIL-4314. Na jednu cestu může KamAZ-5320 dodat 6 tun pěnového betonu a 2 tuny oceli a zisk z cesty bude 4 tisíce rublů. ZIL-4314 dodává 2 tuny pěnového betonu a 4 tuny oceli na jednu cestu, zisk z cesty je 6 tisíc rublů. Je nutné organizovat dopravu tak, aby poskytla automobilovému podniku co největší zisk.

Sestavme matematický model problému. Označte x 1 požadovaný počet jízd KamAZ-5320 a skrz X 2 požadovaný počet jezdců ZIL-4314.

Celková přeprava v tunách výrobků z pěnového betonu je 6 x 1+ 2x 2 a z oceli 2 x 1+ 4x 2. Limit dopravy, založený na počtu dostupných položek, je 6 x 1+ 2x 2 ≤ 300t pro pěnobeton a 2 x 1+ 4x 2 ≤ 200t na ocel.

Celkový zisk v tisících rublech. vyjádřeno jako 4 X 1 + 6X 2 , který je třeba maximalizovat a který je kritériem optimality v uvažovaném problému. Matematický model problému tedy vypadá následovně. Je nutné maximalizovat účelovou funkci

L = 4x 1+ 6x 2 → max za podmínek: 6 x 1+ 2x 2 ≤ 300; 2x 1+ 4x 2 ≤ 200; x 1 ≥ 0;x 2 ≥ 0.

Zvažte rovnici 6 x 1+ 2x 2 = 300. Pro sestrojení přímky popsané touto rovnicí najdeme dva body ležící na této přímce. Na x 1= 0 z rovnice přímky najdeme 2 x 2 = 300, odkud x 2 \u003d 150. Proto bod A se souřadnicemi (0,150) leží na požadované čáře. Na x 2= 0 máme 6 x 1\u003d 300, odkud x 1 \u003d 50, a bod D se souřadnicemi (50,0) je také na požadovaném řádku. Nakreslete čáru přes tyto dva body INZERÁT(obr. 3.1).

Lineární nerovnost 6 x 1+ 2x 2 ≤ 300 je polorovina umístěná na jedné straně zkonstruované linie 6 x 1+ 2x 2 = 300. Abychom zjistili, na které straně této přímky se nacházejí body požadované poloroviny, dosadíme do nerovnosti 6 x 1+ 2x 2 ≤ 300 souřadnic nějakého bodu neležícího na hraniční čáře. Počátek je například 0-(0,0). Vyhovuje nerovnosti 6∙0 + 2∙0 = 0< 300. Это значит, что начало координат лежит в области допустимых значений, которая находится слева от прямой INZERÁT a na Obr. 3.1 je stínovaný.

Rovnice 2 x 1+ 4x 2= 200 bude sestrojeno ze dvou bodů. Na x 1 = 0 4x 2 = 200 odkud x 2 = 50. Pak bod E má souřadnice (0,50) a patří k požadované linii. Na x 2= 0, 2x 2 = 200 bodů S je na daném řádku se souřadnicemi (100,0). Dosazením souřadnic bodu do nerovnice S(0,0), dostaneme 2∙0 + 4∙0 = 0< 200. Значит, начало координат находится в области допустимых значений от прямой 2x 1+ 4x 2= 200.

Systém omezení úkolů vyžaduje, aby plány ( x 1; x 2) splňují všechny čtyři nerovnosti, tj. přípustné návrhy jsou body ( x 1; x 2) musí být současně ve všech čtyřech polorovinách. Tento požadavek splňují pouze body umístěné uvnitř a na hranici polygonu. OEKD, což je mnohoúhelník přípustných řešení.

Vrcholy mnohoúhelníku proveditelných řešení jsou body O, E, K, Dúsečky OE, EK, KD, OD- jeho žebra. Jakýkoli bod mnohoúhelníku OEKD je plán úkolu, splňující všechny jeho podmínky. Vrcholy polygonu jsou tvořeny průsečíkem dvou přímek a odpovídají základním plánům úlohy, mezi nimiž je nejlepší (optimální) plán. Referenčních plánů tedy bude tolik, kolik je vrcholů v polygonu proveditelných řešení.

Pro účelovou funkci lze také získat vizuální geometrickou reprezentaci L = 4x 1+ 6x 2. Opravíme například nějakou hodnotu účelové funkce L= 120. rovnice 4 x 1+ 6x 2 = 120 definuje přímku procházející bodem V se souřadnicemi (x 1 \u003d 0; x 2 \u003d 20) a bodem L se souřadnicemi (( X 1 = 30; X 2 = 0). Úsečka BL leží uvnitř polygonu OEKD. Proto je pro všechny plány (body) tohoto segmentu hodnota účelové funkce stejná a rovna 120. Zadáním jiných hodnot účelové funkce získáme rovnoběžné čáry, které se nazývají úrovňové čáry cílová funkce.

Přesouvání čáry L rovnoběžně se sebou v jednom směru dostaneme zvýšení účelové funkce a v opačném směru její snížení. V tomto příkladu pohyb po přímce BL vpravo určuje zvýšení účelové funkce, kterou maximalizujeme. Toto děláme až do čáry BL bude mít alespoň jeden společný bod s mnohoúhelníkem přípustných řešení OEKD. Z Obr. 3.1 vyplývá, že posledním bodem, který přímka hladiny účelové funkce protíná, bude bod NA. To znamená, že bod NA určuje optimální plán úkolů.

Směr nárůstu kolmo k linii hladiny se nazývá směr největšího nárůstu objektivní funkci a určuje její maximální zisk. Tento směr lze nastavit bez kreslení nivelačních čar. K tomu je třeba na osách x 1 A x 2 vyčlenit segmenty rovnající se koeficientům účelové funkce a pomocí nich, stejně jako v souřadnicích, sestrojit vektor největšího nárůstu účelové funkce. V matematice se tomu říká spád a značí se znakem grad. Přechod pro funkci L = 4x 1 + 6x 2 bude vektor n| 4; 6 | . Pro pohodlí jeho konstrukce zvětšíme souřadnice např. 10x, tzn. n | 40; 60 | . Sestrojme gradient účelové funkce L, u kterého spojíme bod se souřadnicemi (40; 60) s počátkem. Čáry úrovně objektivní funkce jsou nakresleny kolmo ke směru gradientu.

Tak či onak je stanoveno, že bod NA určuje optimální plán úkolů, jehož hodnoty proměnných odpovídají souřadnicím daného bodu. Pro stanovení souřadnic je nutné vyřešit soustavu rovnic přímek, které tvoří tento vrchol:

6x 1+ 2x 2= 300;

2x 1+ 4x 2= 200.

Koeficienty na x 1 vyrovnáme vynásobením druhé rovnice 3 a první odečteme od druhé rovnice. Dáme 10 x 2= 300,x 2 = 30. Dosazením hodnoty x 2 \u003d 30 do kterékoli z rovnic, například do první, určíme hodnotu X 1:

6x 1+ 2X · 30 = 300,

odkud 6 x 1 = 300 – 60 = 240, tedy x 1 = 40.

Aby tedy automobilka dosáhla co největšího zisku, je nutné absolvovat 40 cest na KamAZ-5320 a 30 cest na ZIL-4314. Maximální zisk v tomto případě bude

L = 4x 1+ 6x 2\u003d 4 40 + 6 30 \u003d 340 tisíc rublů.

Na základě uvažovaného příkladu a geometrické interpretace optimalizační úlohy se dvěma proměnnými můžeme vyvodit následující závěry:

1) ve dvourozměrném prostoru je oblastí možných řešení mnohoúhelník;

2) každá strana mnohoúhelníku odpovídá hodnotě jedné proměnné rovné nule;

3) každý vrchol polygonu přípustných řešení odpovídá hodnotám dvou proměnných rovných nule;

4) každá hodnota účelové funkce odpovídá přímce;

5) optimálnímu řešení úlohy odpovídá vrchol polygonu, ve kterém účelová funkce nabývá optimální hodnoty, přičemž optimálními proměnnými jsou souřadnice tohoto vrcholu.

V obecném případě mají optimalizační problémy podobnou geometrickou interpretaci. Soubor plánů úloh bude mnohostěn, jehož vrcholy odpovídají referenčním plánům. Při řešení úlohy se provádí přechod z jednoho vrcholu mnohostěnu do druhého s velkou hodnotou účelové funkce, dokud není získána jeho optimální hodnota. Všimněte si, že účinnost optimalizačních metod spočívá právě v tom, že výčet vrcholů (iterace) se provádí pouze ve směru největšího nárůstu účelové funkce. Neberou se tedy v úvahu všechny vrcholy, kterých je obrovské množství, ale jen ty, které se blíží extrému.

Při určování třídy optimalizačních úloh a volbě metody jejich řešení je nutné vědět, zda je množina proveditelných řešení konvexní nebo nekonvexní, lineární nebo nelineární účelová funkce.

Podle definice se nazývá množina konvexní jestliže pro libovolné dva body celý segment spojující tyto body patří do této množiny. Příklady konvexních množin jsou například úsečka (obr. 3.2, a), rovina ve tvaru kruhu, krychle, rovnoběžnostěnu a také mnohoúhelníky, které jsou zcela umístěny na jedné straně každé z jejích stran. , atd.

Na Obr. 3.2b ukazuje nekonvexní množiny. V nekonvexních množinách lze označit alespoň dva body segmentu AB, které nepatří do uvažované množiny.

3.3. Simplexní metoda

Simplexní metoda je běžná metoda pro řešení problémů lineárního programování. Metoda dostala svůj název od slova „simplex“, označující nejjednodušší konvexní mnohoúhelník, jehož počet vrcholů je vždy o jeden větší než rozměr prostoru. Simplexovou metodu vyvinul v USA matematik J. Dantzig koncem 40. let 20. století.

Simplexová metoda zahrnuje získání nezáporného základního řešení soustavy kanonických lineárních rovnic typu (3.1), následnou minimalizaci (maximizaci) účelové funkce (3.3) a tím nalezení optimálních hodnot neznámé proměnné x 1, x 2… x n.

Myšlenka simplexové metody spočívá v tom, že v průběhu výpočtu se postupně přechází od prvního základního řešení ke druhému, třetímu atd. prostřednictvím tzv simplexní transformací. Transformace jsou prováděny formou simplexních tabulek, což značně zjednodušuje a urychluje výpočty.

Pro získání nezáporných základních řešení soustavy lineárních rovnic je nutné provést proces eliminace neznámých tak, aby volné členy rovnic zůstaly nezáporné ve všech fázích procesu. V tomto případě bychom se měli řídit následujícím pravidlem: jakákoli volná proměnná, pro kterou existuje alespoň jeden kladný koeficient, je brána jako nová základní proměnná; z báze je odvozena proměnná, která odpovídá nejmenšímu poměru volných členů rovnic k odpovídajícím kladným koeficientům rovnic s proměnnou zavedenou do báze. Takové transformace se nazývají simplexní převodníky.

To je velmi důležité, protože pro nalezení konkrétního nezáporného řešení, které odpovídá největší možné hodnotě jedné volné proměnné s nulovými hodnotami ostatních volných proměnných, místo určení variačního rozsahu zadané proměnné a dosazení její největší možnou hodnotu do obecného řešení, stačí vzít tuto proměnnou jako základní a podrobit systém simplexní transformaci, přecházející na nový základ, což značně zjednodušuje výpočty.

Výpočty se pohodlně provádějí pomocí simplexních tabulek. Přechod z jedné tabulky do druhé odpovídá jedné iteraci, tj. přechodu z jedné báze na druhou, přičemž hodnota účelové funkce klesá. Pro určitý počet iterací přecházejí k základně, pro kterou se získá optimální (minimální nebo maximální) hodnota účelové funkce. Uvažujme simplexovou metodu v obecné podobě.

Obecným úkolem lineárního programování je minimalizovat (maximalizovat) účelovou funkci, jejíž proměnné jsou propojeny soustavou lineárních rovnic za podmínky nezápornosti.

Nechť je nutné minimalizovat lineární formu

L = c 1 x 1 + c 2 x 2 + ... c n x n.

Za následujících podmínek (pro přehlednost jsou v rovnicích zachovány nulové a jednotkové koeficienty):

1x 1+ 0x 2 +... 0x m + a 1 m+ 1 x m+1 ... + a 1n x n \u003d b 1;

0x 1+ 1x 2+… 0x m + a 2m+ 1x m+1 ... + a 2n x n \u003d b 2;

……………………………………………

0x 1+ 0x 2 + ... 1x m + a mm + 1x m +1 ... + a mn x n \u003d b m.

Tento systém rovnic má již hotový základ, protože každá omezující rovnice obsahuje neznámou s koeficientem rovným jedné, což v jiných rovnicích není, tedy z koeficientů proměnných. X 1 , X 2 …, x m můžete vytvořit matici identity.

Pojďme řešit rovnice pro základní proměnné:

x 1 \u003d b 1 - (a 1 m + 1 x m + 1 ... + a 1 n x n);

x 2 \u003d b 2 - (a 2m + 1 x m + 1 ... + a 2n x n);

………………………………

x m \u003d b m - (a mm + 1x m + 1 ... + a mn x n),

a vyjádříme účelovou funkci pomocí volných proměnných, dosadíme do ní místo základních proměnných jejich vyjádření pomocí volných proměnných:

L=c 1 b 1 +c 2 b 2 +c mb m –(c 1 a 1m +c 2 a 2m+1 +…+c m a mn+1)x m+1 -…-(c 1 a 1n +c 2 a 2n +…+c m a mn)x n …+c n x n..

Proměnné x 1, x 2 ..., x m, s jejichž pomocí je nalezen první základní plán, jsou základní a ostatní x m +1 , x m +2 ,…x n – volný, uvolnit. Základních proměnných by mělo být vždy tolik, kolik je rovnic v systému. Na základě podmínky nezápornosti je nejmenší hodnota volných proměnných rovna nule. Výsledné základní řešení soustavy rovnic je jejím počátečním proveditelným řešením, tzn. x 1 \u003d b 1, x 2 \u003d b 2, ... x m \u003d b m, x m +1 \u003d 0,…, x n = 0.

Toto řešení odpovídá hodnotě účelové funkce

L = c 1 b 1 + c 2 b 2 + ... c m b m.

Počáteční řešení je zkontrolováno z hlediska optimálnosti. Pokud to není optimální, pak zavedením volných proměnných do báze se najdou následující proveditelná řešení s menší hodnotou účelové funkce. K tomu je určena volná proměnná, která musí být zadána do základu, a také proměnná, která musí být ze základu odstraněna. Poté se přesunou z předchozího systému do dalšího ekvivalentního systému. To se provádí pomocí simplexních tabulek. Řešení úlohy pokračuje, dokud není získána optimální hodnota účelové funkce.

Simplexní tabulky jsou sestaveny následovně (viz tabulka 3.1). Všechny proměnné umístěte na začátek tabulky X 1 , X 2 …, x n a koeficienty cj, se kterou jsou odpovídající proměnné zahrnuty do účelové funkce. První sloupec c i sestává z koeficientu účelové funkce pro proměnné zahrnuté v bázi. Následuje sloupec základních proměnných a volných členů rovnic. Prvky zbývajících sloupců tabulky jsou koeficienty proměnných, s nimiž tyto vstupují do soustavy rovnic. Každý řádek tabulky tedy odpovídá rovnici soustavy, řešené vzhledem k základní proměnné. V tabulce je také uvedena varianta plánu, která odpovídá účelové funkci pro daný základ.

Spodní řádek tabulky se nazývá index. Každý jeho prvek (odhad) ∆ j určit

∆j = z j – c j ,

Kde cj jsou koeficienty pro odpovídající proměnné v účelové funkci; zj – součet součinů koeficientů účelové funkce se základními proměnnými a odpovídajícími proměnnými - prvky j-tý sloupec tabulky.

Stůl 3.1

Simplexní tabulka s počáteční platnou