Přechod z omezení lineárního matematického modelu. Vytvořte matematický model úlohy lineárního programování. Volba objemu přerozdělování

Přednáška 2

PROTI kanonická forma

přijatelné rozhodnutí LPP(přijatelný plán).

optimální řešení LPP.

Potřeba

Příklad.

Zapíšeme úkol kanonická forma

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

Kromě případů, kdy problém má jediné optimální řešení pro a možná speciální situace:

1. problém má nekonečné množství optimálních řešení - Extrém funkce je dosažen v intervalu ( alternativní optimum)- obrázek 2;

2. úkol neřešitelné kvůli neomezenosti IDT, nebo - obrázek 3;

3. SDT - jediný bod Ach, pak;

4. úkol neřešitelné pokud je ODR prázdná oblast.

A

Obrázek 2 Obrázek 3

Pokud je vodorovná čára rovnoběžná se stranou oblasti proveditelných řešení, pak je extrém dosažen ve všech bodech strany. Problém má nespočet optimálních řešení - alternativní optimum ... Optimální řešení najde vzorec

kde je parametr. Pro libovolnou hodnotu od 0 do 1 je možné 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 problém graficky lineární programování (alternativní optimum):

Otázky na sebeovládání

1. Zapište obecný problém lineárního programování.

2. Zapište si problém lineárního programování v kanonických a standardních formách.

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

4. Uveďte definici proveditelných a optimálních řešení problému lineárního programování.

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

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

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

8. Jak sestrojit polorovinu danou lineární nerovností ve dvou proměnných ?

9. Jak se nazývá řešení soustavy lineárních nerovností ve dvou proměnných? Sestrojte v rovině oblast proveditelných řešení takového systému lineárních nerovností, který:

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

2) má nekonečný počet řešení;

3) nemá jediné řešení.

10. Poznamenejte si pro lineární funkce vektorový přechod, pojmenujte druh liniových úrovní. Jak jsou čáry přechodu a úrovně umístěny vůči sobě navzájem?

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

12. Jak najít souřadnice a hodnoty řešení?

13. Vykreslete oblast proveditelných řešení, přechodové a vodorovné čáry pro problémy lineárního programování, ve kterých:

1) je dosaženo v jednom bodě a - na segmentu ODR;

2) je dosaženo v jednom bodě ODR a.

14. Uveďte geometrický obrázek LPP, pokud je:

1) má jediná optimální řešení pro a;

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

Přednáška 2

grafická metoda 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í LPP

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 zapsat v jedné ze tří forem.

PROTI obecná forma matematického modelu je nutné najít maximum nebo minimum objektivní funkce; soustava omezení obsahuje nerovnosti a rovnice; ne všechny proměnné mohou být nezáporné.

PROTI kanonická forma k nalezení maxima objektivní funkce je nutný matematický model; soustava omezení se skládá pouze z rovnic; všechny proměnné nejsou záporné.

Ve standardní formě matematického modelu je požadováno nalezení maxima nebo minima funkce; všechna omezení jsou nerovnosti; všechny proměnné nejsou záporné.

Říká se řešení systému omezení, které splňuje podmínky nezápornosti proměnných přijatelné rozhodnutí LPP(přijatelný plán).

Sada proveditelných řešení se nazývá oblast přípustných řešení LPP.

Nazývá se proveditelné řešení, při kterém objektivní funkce dosáhne extrémní hodnoty optimální řešení LPP.

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

Potřeba přechod z jedné formy matematického modelu do druhého souvisí 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 psaný kanonickou formou a grafická metoda je aplikována na standardní formu matematického modelu.

Přechod na kanonickou formu LPP.

Příklad.

Zapíšeme úkol kanonická forma zavedením doplňkové (rovnovážné) proměnné se znaménkem „+“ na levé straně první nerovnosti systému omezení a další proměnné se znaménkem minus na levé straně druhé nerovnosti.

Ekonomický význam různých další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í zbývající suroviny a v problému výběru optimálních technologií - nevyužitý čas podniku pro určitou technologii; v řezném problému - uvolnění polotovarů dané délky přes plán atd.

Definice. Lineární programování (LP) - věda o výzkumných metodách a hledání extrémních (největších a nejmenších) hodnot lineární funkce, jejíž neznámé podléhají lineárním omezením.

Tato lineární funkce se nazývá cílová, a nazývají se omezení, která jsou matematicky zapsána ve formě rovnic nebo nerovnic systém omezení.

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

Matematický model úlohy lineárního programování (LP) je obecně psán jako

s omezeními:

kde x j- neznámý; a ij, b i, c j- dané konstantní hodnoty.

Všechny nebo některé rovnice soustavy omezení lze zapsat ve formě nerovností.

Matematický model ve výstižnějším zápisu má formu

s omezeními:

Definice. Realizovatelné řešení (plán) lineárního programovacího problému je vektor = ( X 1 , X 2 ,..., x n), splnění systému omezení.

Soubor proveditelných řešení tvoří oblast proveditelných řešení (ODS).

Definice. Realizovatelné řešení, při kterém objektivní funkce dosáhne své extrémní hodnoty, se nazývá optimální řešení problému lineárního programování a je označeno opt.

Základní proveditelné řešení (NS 1 , NS 2 , ..., X r , 0, …, 0) je referenční řešení, kde r - hodnost systému omezení.

Matematický model úlohy LP může být kanonický i nekanonický.

7. Řešení úloh lineárního programování grafickou metodou... Grafy omezení funkcí. Úrovně.

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

Nejjednodušší a nejintuitivnější metodou lineárního programování je grafická metoda. Používá se k řešení problémů LP se dvěma proměnnými uvedenými v nekanonické formě a mnoha proměnnými v kanonické formě za předpokladu, že obsahují maximálně dvě volné proměnné.

Z geometrického hlediska v problému s lineárním programováním hledáme takový rohový bod nebo sadu bodů z proveditelné sady řešení, ve kterých je dosaženo nejvyšší (nejnižší) úrovně, která se nachází dále (blíže) než ostatní ve směru nejrychlejšího růstu.

Chcete -li najít extrémní hodnotu objektivní funkce v grafickém řešení úloh LP, použijte vektor L() na povrchu NS 1 ACH 2 , které označujeme . Tento vektor ukazuje směr nejrychlejší změny objektivní funkce. Jinými slovy, vektor je normála čáry úrovně L()

kde E 1 a E 2 - jednotkové vektory podél os VŮL 1 a VŮL 2 příslušně; tedy = (∂L / ∂х 1 , ∂L / ∂х 2 ). Souřadnice vektoru jsou koeficienty objektivní funkce L (). Při řešení praktických problémů bude podrobně zvážena konstrukce vyrovnávací čáry.

Algoritmus pro řešení problémů

1. Najděte oblast proveditelných řešení systému omezení problému.

2. Budování vektoru .

3. Nakreslete vodorovnou čáru L 0 , která je kolmá .

4. Posuňte čáru úrovně ve směru vektoru pro úkoly na maximum a v opačném směru , pro úkoly na minimum.

Hladinová čára se posune, dokud nebude mít pouze jeden společný bod s oblastí přípustných řešení. Tento bod, který určuje jediné řešení problému LP, bude extrémní bod.

Pokud se ukáže, že čára úrovně je rovnoběžná s jednou ze stran ODR, pak se v tomto případě dosáhne extrému ve všech bodech odpovídající strany a problém LP bude mít nekonečný počet řešení. Říká se, že takový problém s LP má alternativní optimum, a jeho řešení je nalezeno podle vzorce:

Kde 0 ≤ t≤ 1, 1 a 2 - optimální řešení v rohových bodech RSO.

Problém LP může být neřešitelný, když se omezení, která jej definují, ukáží být rozporuplná.

5. Najděte souřadnice extrémního bodu a hodnotu objektivní funkce v něm.

Příklad 3. Výběr optimální možnosti vydání produktu

Společnost vyrábí 2 druhy zmrzliny: krémovou a čokoládovou. Pro výrobu zmrzliny se používají dva výchozí produkty: mléko a plniva, jejichž náklady na 1 kg zmrzliny a denní zásoby jsou uvedeny v tabulce.

Studie prodejního trhu ukázala, že denní poptávka po zmrzlině převyšuje poptávku po čokoládové zmrzlině, ne však o více než 100 kg.

Navíc bylo zjištěno, že poptávka po čokoládové zmrzlině nepřesahuje 350 kg za den. Maloobchodní cena 1 kg krémové zmrzliny 16 rublů, čokoláda - 14 rublů.

Kolik zmrzliny z každého druhu by měla firma vyrobit, aby maximalizovala příjem z prodeje produktů?

Řešení. Označme: X 1 - denní objem výroby zmrzliny, kg; X 2 - denní produkce čokoládové zmrzliny, kg.

Pojďme skládat matematický modelúkoly.

Ceny za zmrzlinu jsou známé: 16 rublů, respektive 14 rublů, takže objektivní funkce bude vypadat takto:

Nastavíme limity na mléko pro zmrzlinu. Jeho spotřeba pro krémovou zmrzlinu - 0,8 kg, pro čokoládu - 0,5 kg. Zásoba mléka 400 kg. Proto bude první nerovnost vypadat takto:

0,8x 1 + 0,5x 2 ≤400 - první nerovnost je omezení. Zbytek nerovností je složen podobným způsobem.

Výsledkem je systém nerovností. to je oblast řešení každé nerovnosti. To lze provést substitucí souřadnic bodu O (0: 0) do každé z nerovností. V důsledku toho získáme:

Postava OABDEF - oblast přípustných řešení. Sestavíme vektor (16; 14). Vodorovná čára L 0 je dána rovnicí 16x 1 + 14x 2 = konst. Vybereme libovolné číslo, například číslo 0, pak 16x 1 + 14x 2 = 0. Na obrázku je pro řádek L 0 vybráno určité kladné číslo, které se nerovná nule. Všechny čáry úrovně jsou navzájem rovnoběžné. Normální vektor čáry úrovně.

Posuňte čáru úrovně ve směru vektoru. Výstupní bod L 0 z oblasti proveditelných řešení je bod D, jeho souřadnice jsou určeny jako průsečík přímek daných rovnicemi:

Vyřešením systému získáme souřadnice bodu D(312,5; 300), ve kterém bude optimální řešení, tj.

Společnost by tedy měla denně vyrobit 312,5 kg zmrzliny a 300 kg čokoládové zmrzliny, přičemž příjem z prodeje bude činit 9 200 rublů.

8. Redukce problému libovolného lineárního programování na hlavní problém. Převod omezení nerovností na odpovídající rovnice.

9. Jednoduchá metoda... Popis a algoritmus metody, její použitelnost.

K vyřešení problému pomocí simplexové metody je nutné:

1. Uveďte způsob, jak najít optimální řešení podpory

2. Uveďte způsob přechodu z jednoho podpůrného řešení do druhého, při kterém se hodnota objektivní funkce bude blížit té optimální, tzn. naznačit způsob, jak zlepšit referenční řešení

3. Nastavte kritéria, která vám umožní včasné zastavení hledání řešení podpory pro optimální řešení nebo vyvodit závěr o neexistenci optimálního řešení.

Algoritmus simplexové metody pro řešení problémů lineárního programování

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

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

3. Vypočítejte odhady vektorových expanzí na základě řešení podpory a vyplňte tabulku simplexové metody

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

5. Pokud je splněna podmínka existence souboru optimálních řešení, pak jednoduchým výčtem se najdou všechna optimální řešení

10. Problém dopravy. Definice, typy, metody hledání počátečního řešení dopravního problému.

Transportní problém je jedním z nejčastějších problémů lineárního programování. Jejím cílem je vyvinout co nejracionálnější způsoby a prostředky přepravy zboží a eliminovat nadměrně dlouhé, protijedoucí, opakované přepravy.

1. Nalezení původního řešení podpory;

2. Kontrola optimality tohoto řešení;

3. Přechod z jednoho řešení podpory na druhé.

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

Lineární programování- toto je nejrozvinutější část matematické programování, pomocí kterého se provádí analýza a řešení extrémních problémů s lineárními spoji a vazbami.

Lineární programování zahrnuje řadu heuristických (přibližných) metod řešení, které za daných podmínek umožňují všechny možné možnostiřešení výrobních problémů s cílem vybrat nejlepší, optimální. Mezi tyto metody patří následující - grafická, simplexová, potenciální metoda (modifikovaná distribuční metoda - MODI), Hitchkova, Kreko, Vogelova aproximační metoda a další.

Některé z těchto metod spojuje společný název - distribuční neboli transportní metoda.

Rodištěm lineárního programování je Rusko. První práce na lineárním programování 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. Kantorovich se věnuje řešení dopravních problémů, lze mít za to, že uvedená Nobelova cena ctí také zásluhy ruské dopravní vědy.

V silniční dopravě se od 60. let používají metody lineárního programování k vyřešení velkého počtu nejdůležitějších výrobních problémů, a to: zmenšení vzdálenosti nákladní dopravy; vypracování optimálního přepravního schématu; výběr nejkratších tras pohybu; úkoly přepravy různého, ​​ale zaměnitelného zboží; plánování denních směn; plánování přepravy malých zásilek; distribuce autobusů po trasách a další.

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

Objektivní funkce a omezení jsou vyjádřeny lineárními závislostmi (rovnosti nebo nerovnosti);

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

Nezápornost hledaných proměnných. Obecná forma psaní lineárního programovacího modelu ve zkrácené podobě je následující:

Nalézt NS ij ≥ 0 (j = 1, 2 ... n) za omezení následujícího typu:

Tato omezení minimalizují (nebo maximalizují) objektivní funkci

Standardní formou psaní lineárního programovacího modelu je systém lineární rovnice zaznamenáno v kanonický forma, tj. ve formě lineárních rovností, v nezáporných číslech:

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.1)

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

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

Pokud je model zapsán ve formě nerovností v nezáporných číslech, má tedy 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 sníží na kanonický formulář (3.1) zavedením dalších proměnných x n +1> 0 (já=1,2…m) nalevo od nerovnosti (nebo zrušení počtu proměnných, pokud je znak nerovnosti nasměrován opačným směrem). Další proměnné tvoří základ.

Standardní formou řešení problému s lineárním programováním je nalezení řešení systému lineárních rovnic v nezáporných číslech, která minimalizují objektivní funkci. V tomto případě má objektivní funkce formu

L = s 1 x 1 + s 2 x 2 ... s n x n → min, (3.3)

kde s 1, s 2 ... s n- koeficienty objektivní funkce L s proměnnými NS j.

Do objektivní funkce vstupují další proměnné s nulovými koeficienty.

V případě maximalizace objektivní funkce L znaménka proměnných objektivní funkce by měla být obrácena a opět se dostáváme k problému minimalizace, tj. jeden úkol je nahrazen druhým úkolem L na - L nebo max L= min (- L).

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

Základní řešení se nazývá přípustné, přičemž proměnné zahrnuté v základu nejsou záporné.

Optimálním řešením je proveditelné řešení, které maximalizuje (nebo minimalizuje) objektivní funkci (3.3).

Každý problém lineárního programování odpovídá jinému, kterému se říká problém duálního lineárního programování. Původní problém ve vztahu k duálu se nazývá přímý. Přímé a duální problémy tvoří pár, kterému se v lineárním programování říká dvojice. Přímý a duální pár tvoří asymetrický pár, když je přímý problém zapsán v kanonické formě, a symetrický pár, když jsou problémové podmínky zapsány nerovnostmi.

Pravidla pro sestavování matematického modelu duální úlohy 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. Graficko-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 vám umožňuje řešit problémy se 2 nebo 3 neznámými, to znamená, že je použitelný pro úzký rozsah 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 ve smyslu problému neměl být negativní, se provádí v kartézském souřadném systému. Rovnice x 1= 0 a x 2= 0 jsou osy prvního kvadrantového souřadnicového systému

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

Příklad 3.1. Ve skladu je 300 tun výrobků z pěnového betonu a 200 tun oceli. Automobilka musí tyto výrobky dodat do rozestavěného zařízení. Automobilka má kamiony 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 jízdy bude 4 tisíce rublů. ZIL-4314 dodává 2 tuny pěnobetonu a 4 tuny oceli v rámci jedné cesty, zisk z cesty je 6 tisíc rublů. Je nutné organizovat dopravu takovým způsobem, aby byl pro automobilku zajištěn největší zisk.

Pojďme sestavit matematický model problému. Označme x 1 požadovaný počet jezdců KamAZ-5320 a skrz NS 2 požadovaný počet jezdců ZIL-4314.

Celková přeprava v t výrobků z pěnobetonu je 6 x 1 + 2x 2 a z oceli 2 x 1 + 4x 2... Přepravní omezení založená na počtu dostupných položek jsou 6 x 1 + 2x 2 ≤ 300 t pro pěnový beton a 2 x 1 + 4x 2 ≤ 200 t na ocel.

Celkový zisk v tisících rublů je vyjádřen jako 4 NS 1 + 6NS 2, který je třeba maximalizovat a který je kritériem optimality uvažovaného problému. Matematický model problému tedy vypadá následovně. Je nutné maximalizovat objektivní funkci

L = 4x 1 + 6x 2 → maximálně 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. K 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 = 150. Proto bod A se souřadnicemi (0,150) leží na požadované přímce. Na x 2= 0 máme 6 x 1= 300, odkud x 1 = 50, a bod D se souřadnicemi (50,0) je také na hledané lince. Těmito dvěma body nakreslete přímku INZERÁT(obr. 3.1).

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

Rovnice 2 x 1 + 4x 2= 200 budeme stavět na dvou bodech. Na x 1 = 0 4x 2 = 200, odkud x 2 = 50. Pak pointa E má souřadnice (0,50) a patří k požadované přímce. Na x 2= 0, 2x 2 = 200, bod s se nachází na daném řádku se souřadnicemi (100,0). Nahrazení souřadnic bodu nerovností 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á provedení jsou body ( x 1; x 2) musí být ve všech čtyřech polorovinách současně. Tento požadavek splňují pouze body umístěné uvnitř a na okraji mnohoúhelníku. OEKD, což je mnohoúhelník proveditelný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 problému, splňující všechny jeho podmínky. Vrcholy mnohoúhelníku 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. Základních plánů tedy bude tolik, kolik bude vrcholů polygonu proveditelných řešení.

Pro objektivní funkci lze také získat jasné geometrické znázornění. L = 4x 1 + 6x 2... Opravme například nějakou hodnotu objektivní funkce L= 120. rovnice 4 x 1 + 6x 2 = 120 definuje čáru procházející bodem PROTI se souřadnicemi (x 1 = 0; x 2 = 20) a bodem L se souřadnicemi (( NS 1 = 30; NS 2 = 0). Sekce BL leží uvnitř mnohoúhelníku OEKD... V důsledku toho je pro všechny plány (body) tohoto segmentu hodnota objektivní funkce stejná a rovná se 120. Přiřazením dalších hodnot k objektivní funkci získáme rovnoběžky, které se nazývají úrovňové čáry Objektivní funkce.

Pohybující se rovně L paralelně k sobě v jednom směru, získáme zvýšení objektivní funkce a v opačném směru - její snížení. V tomto případě pohyb přímky BL napravo určuje nárůst objektivní funkce, kterou maximalizujeme. Děláme to tak dlouho, jak rovinka BL bude mít alespoň jeden společný bod s polygonem proveditelných řešení OEKD... Obr. 3.1 vyplývá, že posledním bodem protnutým přímkou ​​úrovně objektivní funkce bude bod NA... To znamená, že pointu NA určuje optimální plán úkolů.

Nazývá se vzestupný směr kolmý na vodorovnou čáru směr největšího nárůstu objektivní funkci a určuje její maximální růst. Tento směr lze nastavit bez kreslení linek úrovně. K tomu je nutné na osách x 1 a x 2 odložit segmenty rovnající se koeficientům objektivní funkce a z nich jako souřadnice sestrojit vektor největšího nárůstu objektivní funkce. V matematice se tomu říká spád a označte gradem. Přechod pro funkci L = 4x 1 + 6x 2 bude tam vektor n| 4; 6 | ... Pro pohodlí jeho konstrukce zvýšíme souřadnice například 10krát, tj. n | 40; 60 | ... Sestrojte gradient objektivní funkce L, pro který spojíme bod se souřadnicemi (40; 60) s počátkem. Čáry úrovně objektivní funkce jsou vykresleny kolmo ke směru přechodu.

Tak či onak bylo prokázáno, že smysl NA určuje optimální plán úlohy, jehož hodnoty proměnných odpovídají souřadnicím daného bodu. K určení 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.

Vyrovnáme koeficienty na x 1 vynásobením druhé rovnice 3 a od druhé rovnice odečteme první. Dostáváme 10 x 2= 300,x 2 = 30. Dosazením hodnoty x 2 = 30 v kterékoli z rovnic, například v první určíme hodnotu NS 1:

6x 1+ 2NS · 30 = 300,

odkud 6 x 1 = 300 - 60 = 240, proto x 1 = 40.

Aby tedy automobilový podnik získal co největší zisk, musí 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= 4 40 + 6 30 = 340 tisíc rublů.

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

1) v dvourozměrném prostoru je oblast proveditelných řešení polygon;

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

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

4) přímka odpovídá každé hodnotě objektivní funkce;

5) optimální řešení úlohy odpovídá vrcholu mnohoúhelníku, ve kterém objektivní funkce získává optimální hodnotu, přičemž souřadnice tohoto vrcholu jsou optimální proměnné.

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

Při definování třídy optimalizačních problémů a výběru metody jejich řešení je nutné vědět, zda je množina možných řešení konvexní nebo nekonvexní, lineární nebo nelineární objektivní funkce.

Podle definice se sada nazývá konvexní pokud pro jakékoli dva body celý segment spojující tyto body patří do této sady. Příklady konvexních množin jsou například segment (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 jeho stran , atd.

Na obr. 3.2b zobrazuje nekonvexní sady. V nekonvexních sadách lze označit alespoň dva body segmentu AB, které nepatří do uvažované sady.

3.3. Simplexní metoda

Simplexní metoda Je běžnou metodou řešení problémů lineárního programování. Metoda dostala svůj název od slova „simplex“, které označuje nejjednodušší konvexní mnohoúhelník, jehož počet vrcholů je vždy o jeden více než rozměr prostoru. Metodu simplex vyvinul v USA matematik J. Danzig na konci čtyřicátých let minulého století.

Metoda simplex 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 (maximalizaci) objektivní funkce (3.3) a nalezení tímto způsobem optimální hodnoty hledaných proměnných x 1, x 2 ... x n.

Myšlenka simplexové metody spočívá v tom, že v procesu výpočtu člověk postupuje postupně z prvního základního řešení do druhého, třetího atd. prostřednictvím tzv simplex transformace. Převody se provádějí formou simplexových tabulek, což výpočty výrazně zjednodušuje a zrychluje.

K získání nezáporných základních řešení soustavy lineárních rovnic je třeba provést proces eliminace neznámých, aby volné členy rovnic zůstaly ve všech fázích procesu nezáporné. V tomto případě by se měl člověk řídit následujícím pravidlem: jako nová základní proměnná se bere jakákoli volná proměnná, pro kterou existuje alespoň jeden kladný koeficient; proměnná je odvozena od základu, který odpovídá nejmenšímu poměru volných členů rovnic k odpovídajícím kladným koeficientům rovnic pro proměnnou zavedenou do základu. Takové transformace se nazývají simplexové převaděče.

To je velmi důležité, protože za účelem nalezení konkrétního nezáporného řešení, které odpovídá největší možné hodnotě libovolné volné proměnné při nulových hodnotách jiných volných proměnných, místo určování rozsahu zadané proměnné a nahrazování jejího maxima možnou hodnotu do obecného řešení, stačí vzít tuto proměnnou jako základní a podrobit systém simplexové transformaci, přecházející na nový základ, který výpočty značně zjednodušuje.

Výpočty se pohodlně provádějí pomocí simplexových tabulek. Přechod z jedné tabulky do druhé odpovídá jedné iteraci, tj. Přechodu z jednoho základu do druhého, přičemž hodnota objektivní funkce klesá. U určitého počtu iterací přejdeme k základu, pro který se získá optimální (minimální nebo maximální) hodnota objektivní funkce. Uvažujme obecně o simplexové metodě.

Obecným problémem lineárního programování je minimalizace (maximalizace) objektivní funkce, jejíž proměnné jsou propojeny systémem lineárních rovnic, podléhají podmínce non-negativity.

Nechť je nutné minimalizovat lineární formu

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

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

1x 1+ 0x 2 + ... 0x m + a 1m + 1x m + 1 ... + a 1n x n = b 1;

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

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

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

V tomto systému rovnic již existuje připravený základ, protože každá rovnice omezení obsahuje neznámou s koeficientem rovným jedné, která v jiných rovnicích chybí, tj. Z koeficientů proměnných NS 1 , NS 2 …, x m můžete sestavit matici identity.

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

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

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

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

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

a objektivní funkci vyjadřujeme pomocí volných proměnných, které nahrazujeme jejich výrazy volnými proměnnými místo základních proměnných:

L = c 1 b 1 + c 2 b 2 + cmbm - (c 1 a 1m + c 2 a 2m + 1 +… + cma mn + 1) x m + 1 -… - (c 1 a 1n + c 2 a 2n +… + Cma mn) xn… + cnx n ..

Proměnné x 1, x 2 ..., x m, s jejichž pomocí byl nalezen první základní plán, jsou základní a ostatní x m +1, x m +2, ... x n - volný, uvolnit. Vždy by mělo existovat tolik základních proměnných, kolik je v systému rovnic. Na základě podmínky nezápornosti je nejmenší hodnota volných proměnných nula. Získané základní řešení soustavy rovnic je jejím počátečním přípustným řešením, tj. x 1 = b 1, x 2 = b 2, ... x m = b m, x m +1 = 0,…, X n = 0.

Toto řešení odpovídá hodnotě objektivní funkce

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

Počáteční řešení je testováno na optimálnost. Pokud to není optimální, pak zavedením volných proměnných do základu se najdou následující proveditelná řešení s menší hodnotou objektivní funkce. Chcete -li to provést, definujte volnou proměnnou, která musí být zadána do základu, a také proměnnou, která musí být odvozena od základu. Poté se člověk přesune z předchozího systému do dalšího ekvivalentního systému. To se provádí pomocí simplexových tabulek. Řešení problému pokračuje, dokud není získána optimální hodnota objektivní funkce.

Jednostranné tabulky se skládají následovně (viz tabulka 3.1). Všechny proměnné jsou umístěny v horní části tabulky NS 1 , NS 2 …, x n a koeficienty c j, pomocí kterého jsou do cílové funkce zahrnuty odpovídající proměnné. První sloupec c i sestává z koeficientu objektivní funkce pro proměnné zahrnuté v základu. Následuje sloupec základních proměnných a volné termíny rovnic. Prvky zbývajících sloupců tabulky představují koeficienty proměnných, s nimiž jsou tyto proměnné zahrnuty do soustavy rovnic. Každý řádek tabulky tedy odpovídá rovnici systému, řešené s ohledem na základní proměnnou. Tabulka také ukazuje variantu plánu, která odpovídá objektivní funkci pro daný základ.

Volá se spodní řádek tabulky index... Každý z jeho prvků (odhad) ∆ j definovat

∆j = z j - c j,

kde c j- koeficienty pro odpovídající proměnné v objektivní funkci; z j - součet součinů koeficientů objektivní funkce pro základní proměnné odpovídajícími proměnnými - prvky j-Th sloupec tabulky.

stůl 3.1

Jednostranná tabulka s počátečním platným

V praxi jsou omezení v problému lineárního programování často specifikována nikoli rovnicemi, ale nerovnostmi.

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

U proměnných budiž problém lineárního programování, ve kterém jsou omezení proměnných ve formě lineárních nerovností. V některých z nich může být znak nerovnosti, zatímco v jiných (druhý typ je redukován na první jednoduchou změnou znaménka obou částí). Proto nastavíme všechna omezení nerovnosti ve standardní podobě:

Je nutné najít sadu nezáporných hodnot, které by splňovaly nerovnosti (4.1) a navíc by minimalizovaly lineární funkci:

Z takto nastaveného úkolu lze snadno přejít na hlavní úkol lineárního programování. Ve skutečnosti si představme notaci:

kde jsou nějaké nové proměnné, které budeme nazývat „dodatečné“. Podle podmínek (4.1) by tyto dodatečné proměnné neměly být záporné.

Stojíme tedy před problémem lineárního programování v následující formulaci: najděte takové nezáporné hodnoty proměnných, aby vyhovovaly soustavě rovnic (4.3) a současně snížily lineární funkci těchto proměnných na minimum:

Jak vidíte, máme před sebou ve své čisté podobě hlavní úkol lineárního programování (LPP). Rovnice (4.3) jsou uvedeny ve formě již povolené pro základní proměnné, které jsou vyjádřeny jako volné proměnné. Celkový počet proměnných je stejný, z toho „počáteční“ a „doplňkový“. Funkce L je vyjádřena pouze pomocí „počátečních“ proměnných (koeficienty „doplňkových“ proměnných v ní jsou rovny nule).

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

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

a minimalizace lineární funkce

Je nutné přenést tento úkol do podoby OZLP.

Řešení. Redukujeme nerovnosti (4.4) na standardní formu;

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

Úkol je omezen na nalezení nezáporných hodnot proměnných

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

Ukázali jsme, jak můžeme přejít od problému lineárního programování s omezeními nerovností k problému s omezeními rovnosti (LPPP). Zpětný přechod je vždy možný - od LPP k problému s omezeními nerovnosti. Pokud jsme v prvním případě zvýšili počet proměnných, pak ve druhém případě jej snížíme, odstraníme základní proměnné a ponecháme pouze volné.

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

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

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

Řešení. Protože od té doby vybereme nějaké dvě proměnné jako volné. Pamatujte, že proměnné nelze vybrat jako volné proměnné, protože jsou vztaženy k 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 je nemožné vybrat proměnné jako volné (jsou spojeny druhou rovnicí). Vyberme si jako volné proměnné a vyjádřme prostřednictvím nich všechny ostatní:

Protože podmínky (4 9) mohou být nahrazeny nerovnostmi:

Pojďme předat výraz lineární funkce L volným proměnným Substituce v L místo jejich výrazů (4.9). dostaneme.

Základní pojmy modelování

V procesu lidské činnosti se rozvíjejí představy o určitých vlastnostech skutečných předmětů a jejich interakcích. Tyto reprezentace jsou tvořeny osobou ve formě popisů objektů, pro které je používán popisný jazyk. Může to být verbální popis (verbální modely), kresba, kresba, graf, rozložení atd. Vše výše uvedené je shrnuto do jednoho konceptu Modelka, a proces vytváření modelů je modelování.

Modelování Je to univerzální způsob studia procesů a jevů reálného světa. Modelování je zvláště důležité při studiu objektů, které jsou nepřístupné přímému pozorování a výzkumu. Patří sem zejména socioekonomické jevy a procesy.

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

Ekonomika- Jedná se o systém sociální výroby, který ve skutečnosti provádí produkci, distribuci, výměnu a spotřebu hmotných statků nezbytných pro společnost.

Respektive ekonomický a matematický model Je ekonomická abstrakce vyjádřená formálně matematickými termíny, jejíž logická struktura je dána jak objektivními vlastnostmi předmětu popisu, tak subjektivním cílovým faktorem studie, pro kterou se tento popis provádí.

Ekonomické a matematické problémy v zemědělství jsou řešeny pomocí matematických metod. Mezi nimi jsou nejrozvinutější 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í vztahy vyjádřeny lineárně, tj. všechny podmínky jsou vyjádřeny jako soustava 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).

Lineární programovací problém se skládá z objektivní funkce, systému omezení a podmínky pro negativitu proměnných.

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

Takto představovaný problém optimalizace se nazývá problém matematického programování. Hodně NS se nazývá soubor proveditelných rozhodnutí a funkce je objektivní funkce nebo objektivní funkce. Realizovatelné řešení, při kterém funkce nabývá největší (nebo nejmenší) hodnoty, se nazývá optimální řešení problému.

Pokud je funkce objektivu lineární a množina NS je specifikován pomocí systému lineárních rovnic a nerovnic, pak se problému říká problém lineárního programování (LPP). Obecné tvrzení o problému lineárního programování je tedy následující:

najít extrém funkce

s omezeními

za podmínek bez negativity

Pojďme si představit notaci:

Zásoby já-Th typ zdroje;

výdaje já-Th typ zdroje pro produkci j-Th typ výrobku;

jednotkový zisk j-Th typ produktu.

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

Kompaktní zápis ukazuje, že obecný model 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 proměnných v objektivní funkci, které se nazývají variabilní odhady;

Proměnný index;

Index omezení.

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

Proměnné x j označují takové druhy a metody činnosti, jejichž velikost není známa a musí být stanovena v průběhu řešení problému. V problémech v zemědělství obvykle proměnné znamenají požadované velikosti ekonomických odvětví, druhy krmiv ve stravě, značky traktorů a zemědělských strojů atd. Podle konkrétních podmínek může být stejná plodina nebo druh hospodářských zvířat vyjádřena několika proměnnými. Například obilí a krmné obilí; kukuřice na zrno, siláž, zelené krmivo; víceleté trávy na seno, senáž, zelené píce, travní moučku a semena atd.

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

Celkový počet proměnných zahrnutých v úkolu je určen povahou úkolu, konkrétními výrobními podmínkami, schopností shromažďovat informace atd.

Proměnné lze vyjádřit v různých měrných jednotkách: ha, q, kg, ks, hlavy atd. Proměnné jsou ze své podstaty rozděleny na hlavní, doplňkové a pomocné. Mezi hlavní proměnné patří vyhledávané činnosti: průmyslová odvětví, druhy krmiv, značky automobilů. Proměnné, které se tvoří v procesu transformace nerovností na rovnice, se nazývají další. Mohou znamenat nevyužitou část zdrojů, přebytek pravá strana nerovnost (jde -li o nerovnost typu „už ne“). Do úkolu jsou zahrnuty pomocné proměnné za účelem stanovení odhadovaných hodnot získaných výrobních zdrojů, odhadovaných hodnot indikátorů ekonomické efektivity 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í jsou vyjádřeny míry výrobních zdrojů nebo rychlost produkce na měrnou jednotku proměnné.

V obou případech je nutné, aby technické a ekonomické koeficienty přesně odpovídaly plánovacímu období, pro které se problém řeší. Pokud je například problém vyřešen pro ekonomickou a matematickou analýzu výroby za uplynulé období, pak se koeficienty vypočítají podle vykázaných údajů. Pokud je rozhodnuto do budoucna, pak by měly být koeficienty vypočítány pro tuto perspektivu.

Míry spotřeby zdrojů jsou nejčastěji určeny referenčními knihami, musí být přizpůsobeny odpovídajícím konkrétním podmínkám. Poměry výnosů se vypočítají 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 na střídání plodin nebo podíl některých krmiv na celkové krmné skupině atd.

Pravá strana omezení (b i) se nazývají konstanty, tj. konstantní hodnoty. Patří sem objem výrobních zdrojů - půda, práce, stroje, hnojiva, kapitálové investice atd. Výrobní zdroje by měly být stanoveny s přihlédnutím k jejich skutečnému stavu a je nutné vzít v úvahu plánovací období. Kromě toho se tyto výrobní zdroje, jejichž využití je v průběhu roku nerovnoměrné, počítají nejen za rok jako celek, ale také za jednotlivá intenzivní období nebo měsíce (pracovní zdroje).

Výrobní zdroje jsou určeny v různých jednotkách: půda - v hektarech, pracovní zdroje - v člověko -dnech nebo v hodinách, zařízení - v počtu směn stroje, směny nebo denního výkonu atd.

Určení dostupnosti produktivních zdrojů tedy není snadné. Je nutné pečlivě analyzovat výrobní aktivitu ekonomiky, využití pracovní síly, půdy, technických a dalších zdrojů a až poté zahrnout jejich objemy do omezení.

Pravá strana omezení odráží nejen množství zdrojů, ale také objem výroby na horní nebo dolní úrovni. Nižší úroveň je uvedena v případech, kdy je objem výroby znám předem, méně než by farma neměla vyrábět, a horní úroveň neumožňuje produkci produktů nad určitý objem. Tato omezení nejsou vždy požadována. Téměř žádný problém zahrnující definici kombinace průmyslových odvětví se však neobejde bez odpovídajících omezení produktů, jinak se ukáže jednostranné řešení. To je způsobeno skutečností, že účinnost průmyslových odvětví není stejná.

Ve všech ostatních omezeních jsou nuly uvedeny na správnou stranu, protože formulují podmínky pro výrobu a používání produktů nebo odrážejí omezení proporcionální komunikace.

Omezení Je matematický výraz, který váže proměnné ve formě rovností a nerovností. Formulář všech omezení systém omezeníúkoly. Systém omezení v matematické formě 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 reflektovat v úkolu pouze ty podmínky, které skutečně omezují možnosti produkce;

v příliš mnoho omezení zvětšuje velikost problému a ztěžuje jeho řešení

Existují tři typy omezení: rovnost (=), nerovnost typu menší nebo rovna (≤), nerovnost typu větší nebo rovna (≥). Například,

kde já = 1, 2, … , m... Variabilní koeficienty jsou označeny a ij kde index já- číslo omezení, index j- proměnný počet, volné členy (pravá strana vazeb) jsou označeny b i, index já- číslo omezení.

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

Z hlediska významu lze všechna omezení rozdělit na hlavní, 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 úkolu. Zpravidla se s jejich pomocí odrážejí základní podmínky problému - půda, práce, krmiva, živiny, technologie atd.

Další omezení jsou superponovány na část proměnných nebo na jednu proměnnou. Tato omezení jsou zavedena 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 nasycení stravy jednotlivými krmivy nebo jejich skupinami. Další omezení tedy odrážejí různé další podmínky, které vznikají během simulace. Každé další omezení však zužuje prostor svobody volby. Proto by měli být do úkolu zavedeni opatrně, v rozumných mezích a v případě potřeby.

Pomocná omezení, zpravidla nemají žádný nezávislý význam a jsou zavedeny do problému za účelem formalizace jednotlivých podmínek. Patří sem omezení, která vytvářejí proporcionální vztah mezi jednotlivými proměnnými nebo jejich skupinami.

Odhad proměnných v objektivní funkci (s j) jsou koeficienty, které vyjadřují výši celkových příjmů nebo nákladů na měrnou jednotku proměnné. Odhad proměnné zpravidla vyjadřuje přijaté kritérium optimality. Může být předložen v naturáliích i v hotovosti, tj. jednotkové náklady (výrobní náklady).

Podmínka pro nezápornost proměnných je zapsána ve formuláři

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

V reálném životě výroby je na základě podmínek úkolu sestaven seznam proměnných a omezení z tohoto záznamu strukturálního ekonomického a matematického modelu (EMM), jsou připraveny počáteční informace, je sestaven podrobný problém EMM, který je poté je zapsán ve formě matice (tabulky), vložen do počítače a podle odpovídajícího programu je proveden výpočet a analýza výsledků. i = 1, ..., m, (1.5)

j = 1, …, n. (1.6)

Vektor X = (X 1 , X 2 , …, X n), součásti x j které splňují omezení (1.2) a (1.3) [nebo (1.5) a (1.6) v minimálním problému] se nazývá přijatelné rozhodnutí nebo přijatelný plán LP úkoly. Sbírání všech platných plánů se nazývá mnoho platných plánů.

Kanonický forma problému lineárního programování je charakterizována skutečností, že obsahuje objektivní funkci, všechna omezení rovnost, všechny proměnné nejsou zá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 je v obecném případě třeba umět redukovat problém maximalizace na problém minimalizace; přejít od omezení nerovnosti k omezením rovnosti a nahradit proměnné, které nedodržují podmínku non-negativity.

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

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

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

3) pokud mezi omezeními existují nerovnosti, pak zavedením dalších proměnných nezáporných proměnných se transformují na rovnosti. Například další proměnné S j v omezeních typu menšího nebo rovného (£) se zadávají se znaménkem plus:

Další proměnné S j u typových omezení větších nebo rovných (≥) se zadávají se znaménkem minus:

Chcete -li odstranit 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.