PROBLÉM S LINEÁRNYM PROGRAMOVANÍM (PPL)
Matematika
ĎALŠIE DOKUMENTY
PROBLÉM S LINEÁRNYM PROGRAMOVANÍM (PPL)
Základné formy PPL, riešenia, klasifikácia; ekonomická interpretácia PPL.
Problém matematické programovanie predstavuje stanovenie optima (maxima alebo minima) funkcie vektorovej premennej, ktorá spĺňa podmienky (obmedzenia, spojenia) typu nerovností alebo rovníc, ako aj podmienky nezápornosti funkčných premenných. Ak sú všetky funkcie, ktoré zasahujú do formulácie úlohy matematického programovania, lineárne, potom sa problém nazýva problém lineárneho programovania (PPL); inak sa to volá nelineárny problém programovania.
Štandardná forma - je ten, ktorý obsahuje obmedzenia typu rovnice.
- optimum z =
-obmedzenia rovnosti:
- podmienky negativity:
Štandardnú maticovú formu možno vyjadriť takto:
kde
- sa volá objektívna funkcia ( funkcie ekonomický)
sa volá priestor R n vektora X, respektíve C - priestor činnosti
vektor sa volá vektor zdrojov
sa volá priestor R m zdrojový priestor.
Kanonické formy
ktorý kontroluje systém obmedzení sa volá riešenie problému (možné riešenie);
- nazýva sa riešenie obmedzení, ktoré overuje podmienky negativity časový harmonogram alebo prípustné riešenie;
- volá sa program, pre ktorý sa vykonáva požadovaný koniec funkcie optimálny program.
Nech je problém lineárneho programovania v štandardnej podobe.
Je možné, že obmedzenia nerovnosti sa prinesú vo forme obmedzení rovnosti tak, že sa do jedného z pojmov pripočíta (alebo odčíta) nerovnosť, ktorej pojem sa nazýva variabilný vozík alebo variabilná kompenzácia.
Označíme stĺpcové vektory matice A,; potom sa dá napísať systém obmedzení:
Nech B je základňa v priestore. Poznámka pre jeden z vektorov bázy B. Buď je bázické riešenie zodpovedajúce báze B. Báza B, ktorá vedie k programu, sa nazýva prípustný základ; ak nejde o program, hovoríme, že B. je potenciál.
Modely lineárneho programovania, s ktorými sa stretávame v hospodárskej praxi
Medzi najbežnejšie ekonomické problémy modelované pomocou lineárneho programovania uvádzame nasledujúce:
a) problém plánovania výroby
Podnik vyrába v sortimentoch a má m zdrojov. Je potrebné organizovať výrobu, ak je známe množstvo dostupných zdrojov, konkrétna spotreba a jednotkové výhody.
Organizáciu výroby identifikujeme pri tvorbe modelu PPL s plánom výroby.
Buď: množstvo dostupných zdrojov Ri
aij - množstvo zdrojov Ri potrebné na spotrebu pre sortiment Sj
cj - výhoda, ktorú priniesol sortiment Sj.
Označíme xj - počet sortimentov typu Sj. Potom je výrobný plán predstavovaný vektorom stĺpca
PPL teda možno konštatovať nasledovne:
Ak chcete určiť jeho súradnice za podmienok:
získanie maximálneho prínosu
b) problém výživy
Strava musí obsahovať výživné látky v množstvách, ktoré sa nachádzajú v potravinách
Nech aij - množstvo látky obsiahnutej v potravine Aj,
cij-jednotkové náklady na jedlo Aj.
Určte množstvo xj potravy potrebné na zabezpečenie požadovanej úrovne látok tak, aby celkové náklady na stravu boli minimálne.
Matematický model úlohy: tak
c) Problém s prepravou
Rovnaký produkt musí byť prerozdelený z m -výrobných centier (dodávateľ) do n-predajných centier (príjemca), dostupnosť dodávateľa je, potreba príjemcu Bj je bj, jednotkové náklady od dodávateľa k príjemcovi Bj sú cij. Organizácia prepravy spočíva v určení množstva produktu, ktoré sa má prepraviť od každého dodávateľa ku každému príjemcovi, aby celkové náklady na prepravu boli minimálne.
Poznamenávame xij - množstvo, ktoré sa prepraví od dodávateľa k príjemcovi Bj.
Ak sa vezme do úvahy, že celková suma, ktorá je k dispozícii dodávateľom, sa rovná celkovej sume potrebnej pre príjemcov, stáva sa problém vyváženým a model lineárneho programovania je:
min
d) Problém miešania
Produkt sa získava zo zmesi n-surovín Mj, jednotka surovín Mj obsahuje aij jednotiek látky. Výrobok musí obsahovať najmenej dh, jednotky látky a najviac dk, jednotky látky, jednotkové náklady na suroviny Mj je cj .
Určte xj množstvá surovín Mj, ktoré musia byť súčasťou produktu, aby jeho náklady boli minimálne. Matematický model úlohy formulovaný ako PPL je:
,
,