: Úlohy lineárne programovanie(ZLP)

1. Lineárne programovanie

2. Typy úloh lineárneho programovania

3. Formy záznamu PLP

4. Kanonická forma úloh lineárneho programovania

Lineárne programovanie

Lineárne programovanie je časť matematického programovania používaná pri vývoji metód na nájdenie extrému lineárnych funkcií viacerých premenných s lineárnou dodatočné obmedzenia uložené premenným.

Podľa typu riešených úloh sa metódy LP delia na univerzálne a špeciálne. Cez univerzálne metódy je možné vyriešiť akýkoľvek problém lineárneho programovania (LPP). Špeciálne zohľadňujú vlastnosti modelu problému, jeho objektívnu funkciu a systém obmedzení.

Hlavnou črtou problémov lineárneho programovania je, že extrém účelovej funkcie je na hranici oblasti realizovateľných riešení.

Obrázok 1 - Extrém účelovej funkcie

Matematický model ZLP je napísaný nasledujúcim spôsobom:

max (alebo min) Z=z(X),(1)

RSO môže byť reprezentované systémom lineárne rovnice alebo nerovnosti.

Vektor X=(x 1, x 2, .... x p) je riadiaci vektor alebo riadiaca akcia.

Prípustný plán X, v ktorom kritérium optimality Z=z(X) dosahuje extrémnu hodnotu, sa nazýva optimálny a označuje sa X*, extrémna hodnota účelovej funkcie - Z*=z(X*).

Typy úloh lineárneho programovania

Metódy lineárneho programovania sú široko používané v priemyselné podniky pri optimalizácii výrobný program, jeho distribúcia po dielňach a po časových intervaloch, so sortimentným nakladaním zariadení, plánovaním tokov nákladu, stanovením plánu obratu a pod.

Najbežnejší typ úlohy je problém optimálneho využívania zdrojov. Nechajte nejakú výrobnú jednotku (dielňu, podnik, združenie atď.) na základe trhových podmienok, technické možnosti a dostupné zdroje, dokáže vyprodukovať n rôzne druhy produkty známe ako j.

Pri výrobe produktov je podnik limitovaný dostupnými zdrojmi, ktorých počet bude označovaný m, a zdrojovým vektorom B = (b 1 , b 2 , ..., b t). Známe sú aj technologické koeficienty a ij, ktoré ukazujú mieru spotreby i-tého zdroja na výrobu jednotky j-tého produktu. Účinnosť uvoľnenia j jednotky produkciu charakterizuje zisk p j .

Je potrebné stanoviť plán výroby X=(x 1 , x 2 , ..., x p), ktorý maximalizuje zisk podniku s danými zdrojmi.

Cieľová funkcia vyzerá takto

pod obmedzeniami

Sortiment produktov je často stanovený vyššou organizáciou, t. j. jeho objemy musia byť uzavreté v určitých hraniciach D n j a D v j: potom je stanovené nasledujúce obmedzenie:

Základom je model problému optimálneho využívania zdrojov optimalizačné modely ročného výrobného programu podniku. Model obsahuje obmedzenia týkajúce sa fondu času prevádzky zariadenia.

Pri zachovaní predchádzajúcej notácie zapíšeme cez b j a c j predajnú cenu a jednotkové náklady j-tá produkcia. Ako kritérium optimálnosti možno považovať nasledovné:

1) maximálny zisk

2) minimálne výrobné náklady

3) maximálny výstup v hodnotovom vyjadrení (výnosy z predaja produktov)

Príklad. Podnik môže vyrábať štyri typy produktov 1, 2, 3 a 4. Zabezpečuje sa predaj akéhokoľvek objemu. V priebehu štvrťroka má podnik pracovné sily 100 pracovných zmien, polotovary s hmotnosťou 260 kg, obrábacie stroje 370 strojných zmien. Miery spotreby zdrojov a zisk na jednotku každého typu produktu sú uvedené v tabuľke 1.

Potrebné:

a) zostaviť matematický model problému stanovenia plánu výroby, pri ktorom sa dosiahne maximálny zisk;

b) vyriešte úlohu s požiadavkou vychystávania tak, aby počet jednotiek tretieho výrobku bol 3-násobný väčšie množstvo jednotky prvého;

c) zistiť optimálny rozsah pre dodatočné podmienky: vyrobiť aspoň 25 jednotiek prvého produktu, nie viac ako 30 jednotiek tretieho a pomer 1:3 druhého a štvrtého produktu.

stôl 1

Počiatočné údaje

Matematický model problému:

objektívna funkcia:

max: Z=40x 1 +50x 2 +100x 3 +80x 4

s obmedzeniami:

a) pre pracovné zdroje:

2,5x 1 +2,5x 2 +2x 3 +1,5x 4 ? 100;

pre polotovary:

4x 1 +10x 2 +4x 3 +6x 4 ? 260;

pre obrábacie stroje:

8x 1 +7x 2 +4x 3 +10x 4 ? 370;

stav nezápornosti:

b) dodatočná požiadavka konfigurácia bude vyjadrená podmienkou

3x 1 \u003d x 3, t.j. 3x 1 x 3 \u003d 0;

c) okrajové podmienky a podmienka konfigurácie budú reprezentované nasledovne: x 1? 25,

x 3? 30, 3 * x 2 \u003d x 4.

Problém zadávania objednávok alebo nakladania vymeniteľných skupín zariadení. Je to o o rozdelení zákaziek medzi m (i=1,…, m) podnikov (dielne, stroje, výkonní umelci) s rôznymi výrobnými a technologickými charakteristikami, ale zameniteľnými v zmysle plnenia zákaziek. Je potrebné vypracovať taký plán zadávania zákaziek, v ktorom by bola úloha splnená a ukazovateľ efektívnosti by dosiahol extrémnu hodnotu.

Sformulujme problém matematicky. Nech sa na výrobu n druhov výrobkov používa m homogénnych skupín zariadení. Plán pre uvoľnenie každého typu produktu pre určité obdobie nastaviť x j (j=1,2, …n). Výkon každého typu zariadenia je obmedzený a rovná sa b i. Známa technologická matica A=||a ij ||, kde a ij je počet jednotiek j-tého produktu vyrobeného za jednotku času za i-té vybavenie. Matica C je matica nákladov, kde c ij sú náklady spojené s uvoľnením jednotky j-tého produktu na i-tom zariadení. X je vektor výstupu.

Model úlohy bude mať nasledujúcu formu:

účelová funkcia -- minimalizácia nákladov na realizáciu všetkých zákaziek

s obmedzeniami:

a) výkonom zariadenia

b) na výrobu

c) podmienka nezápornosti

Tento problém sa nazýva distribučný alebo distribučný problém.

Ak je pre niektoré typy produktov povolené prekročiť plán, potom bude mať formu obmedzenie (b).

Ako cieľový zisk si môžete vziať aj:

a) maximálny zisk

b) minimálne náklady na strojový čas

Pretože každý model obsahuje zjednodušujúce predpoklady, pre správnu aplikáciu získaných výsledkov je nevyhnutné jasné pochopenie podstaty týchto zjednodušení, čo nám v konečnom dôsledku umožňuje vyvodiť záver o ich prípustnosti či neprípustnosti. Najvýraznejším zjednodušením v uvažovaných modeloch je predpoklad priamoúmerného (lineárneho) vzťahu medzi objemami spotreby zdrojov a objemami výroby, ktorý je stanovený pomocou nákladových sadzieb a ij . Je zrejmé, že tento predpoklad nie je vždy splnený. Objemy spotreby mnohých zdrojov (napríklad investičného majetku) sa teda menia náhle - v závislosti od zmeny výrobného programu X. Medzi ďalšie zjednodušujúce predpoklady patrí predpoklad, že ceny j sú nezávislé od objemov x j , čo platí len pre určité hranice ich zmeny. Tieto „slabosti“ je tiež dôležité poznať, pretože naznačujú základné smery na zlepšenie modelu.

Záznamové formuláre PLP

Existujú 3 formy záznamu PLP:

1) vo forme funkcií

max(alebo min)Z=,max(alebo min)Z=,

2) vektorový tvar

(skalárny súčin vektorov)

pod obmedzeniami

A 1 x 1 + A 2 x 2 +.. + A n x n = B

Kde sú vektory

C\u003d (C1, C2..Cn), X\u003d (X1, X2..Xn) a.

3) matričný formulár

pod obmedzeniami

kde С = (с 1, с 2,…с n),

Kanonická forma úloh lineárneho programovania

Ak sú všetky obmedzenia v úlohe lineárneho programovania rovnicami a na všetky premenné x j sú kladené podmienky nezápornosti, potom sa to nazýva problém lineárneho programovania v kanonickej forme alebo problém kanonického lineárneho programovania (KZLP).

pod obmedzeniami

Aby sme mohli prejsť od LLP k CLZP, je potrebné prejsť od obmedzení nerovnosti k obmedzeniam rovnosti a nahradiť premenné, ktoré nespĺňajú podmienky nezápornosti.

pravidlá prinášanie ZLP na kánonickú formu:

1) v prípade obmedzení pravá časť je záporný, potom by sa tento limit mal vynásobiť -1;

2) ak existujú nerovnosti medzi obmedzeniami, potom sa zavedením ďalších nezáporných premenných premenia na rovnosti;

3) ak niektorá premenná xk nemá žiadne znamienkové obmedzenia, potom je v účelovej funkcii a vo všetkých obmedzeniach nahradená rozdielom dvoch nových nezáporných premenných: xk=x * k - xl, kde l je súhrnný index, x * k>=, xl >=0.

Zvážte príklad. Prinášame kánonickú formu:

Zaveďme vyrovnávacie premenné x 4 , x 5 , x 6 do každej rovnice systému obmedzení. Systém bude napísaný vo forme rovnosti a v prvej a tretej rovnici systému obmedzení sa premenné x 4, x 6 zavedú do ľavá strana so znamienkom „+“ a x 5 so znamienkom „-“ sa zadáva do druhej rovnice.

Voľné členy v kanonickom tvare musia byť kladné, preto posledné dve rovnice vynásobíme -1:

V kanonickej forme písania úloh lineárneho programovania musia byť všetky premenné zahrnuté v systéme obmedzení nezáporné. Predpokladajme, že

Nahrádzanie daný výraz v systéme obmedzení a objektívna funkcia a zapísaním premenných vo vzostupnom poradí indexu dostaneme problém lineárneho programovania prezentovaný v kanonickej forme:

optimalizácia simplexné lineárne programovanie

kanonická forma, ak sa vyžaduje maximalizácia objektívnej funkcie, všetky systémové obmedzenia sú rovnice a všetky premenné podliehajú podmienke nezápornosti.

Problém lineárneho programovania je uvedený v symetrický tvar, ak sa vyžaduje maximalizácia objektívnej funkcie, všetky systémové obmedzenia sú nerovnice "" (alebo aby sa minimalizovala objektívna funkcia, všetky systémové obmedzenia sú nerovnosti "") a všetky premenné podliehajú podmienke nezápornosti.

Volá sa množina čísel prijateľné riešenie (plán) ak spĺňa systém obmedzení LLP.

Množina všetkých realizovateľných riešení je tzv oblasť realizovateľných riešení(RSO).

Volá sa realizovateľné riešenie, pri ktorom sa dosiahne maximálna (minimálna) hodnota funkcie optimálny plán PLP.

Pojmy „plán“ a „optimálny plán“ vznikli z ekonomických aplikácií.

Všetky tri formy písania LLP sú ekvivalentné v tom zmysle, že existujú algoritmy na prechod z jednej formy do druhej. Ak teda existuje spôsob riešenia problému v niektorej z foriem, potom je vždy možné určiť optimálny plán pre problém zadaný v akejkoľvek inej forme. Problém je riešený v symetrickej forme grafická metóda a v kanonickej forme simplexovou metódou.

Zvážte algoritmy na prechod z jednej formy do druhej.

• 
  Symetrický  kanonický. Prechod sa vykonáva pridaním ďalšej nezápornej premennej na ľavú stranu každej nerovnosti. Ak bola nerovnosť "≤", potom sa premenná rovnováhy pridá na ľavú stranu nerovnosti so znamienkom "+". Ak bola nerovnosť „“, potom sa premenná zostatku pridá na ľavú stranu nerovnosti so znamienkom „-“. Zavedené nové premenné sa nazývajú súvahy. Úloha minimalizácie funkcie Z je nahradená úlohou maximalizácie funkcie (–Z) a používa sa, že min Z = –max (–Z).
• 
  Kanonický  symetrický. Na implementáciu takéhoto prechodu sa nájde všeobecné riešenie systému rovníc - obmedzenia, účelová funkcia je vyjadrená pomocou voľných premenných. Ďalej pomocou nezápornosti základných premenných ich môžeme z problému vylúčiť. Symetrická forma úlohy bude obsahovať nerovnosti, ktoré sa týkajú iba voľných premenných a objektívnej funkcie, ktorá závisí len od voľných premenných. Hodnoty základných premenných sa nachádzajú zo všeobecného riešenia pôvodného systému rovníc.
• 
  Všeobecný  kanonický. Každá premenná, na ktorú nebola vložená podmienka nezápornosti, je reprezentovaná ako rozdiel dvoch nových nezáporných premenných. Nerovnosti sa prevedú na rovnice zavedením premennej rovnováhy na ľavej strane každej nerovnosti rovnakým spôsobom, ako to bolo opísané pri prechode zo symetrickej na kanonickú formu. Problém minimalizácie funkcie Z je nahradený problémom maximalizácie funkcie (–Z) rovnakým spôsobom, ako bol popísaný pri prechode zo symetrickej na kanonickú formu.

1. Grafická metóda na riešenie problému lineárneho programovania

Grafická metóda sa používa na riešenie CŽV v symetrickej forme. Táto metóda sa najefektívnejšie využíva pri riešení problémov s dvomi premennými, pretože vyžaduje grafiku. V prípade troch premenných, konštrukcie v R 3 , v prípade štyroch premenných konštrukcie v R 4 atď.

Súbor bodov sa nazýva konvexné, ak pre ľubovoľné dva body množiny obsahuje segment, ktorý ich spája.

Príklad 1

Nasledujúce množiny bodov v rovine sú konvexné:

Nasledujúce množiny bodov v rovine nie sú konvexné:

Veta 1 Priesečník ľubovoľného počtu konvexných množín je konvexná množina.

Veta 2 Nech sú dva ľubovoľné body a v priestore R n. Potom pre ľubovoľný bod segmentu [ PQ] by malo byť: .kde .

Hyperplane vo vesmíre R n je množina bodov, ktorá spĺňa rovnicu . Všimnite si, že v dvojrozmernom prípade je nadrovina priamka.

polovičný priestor je množina bodov, ktorá vyhovuje jednej z nerovností alebo . Nadrovina rozdeľuje body priestoru do dvoch polpriestorov. V dvojrozmernom prípade je nadrovina polrovina.

Veta 3 Polpriestor je konvexná zostava.

Dôsledok Priesečník ľubovoľného počtu polpriestorov je konvexná množina.

mnohosten sa nazýva priesečník jedného alebo viacerých polpriestorov. Mnohosten v dvojrozmernom prípade sa nazýva mnohouholník.

Príklad 2

Nasledujúce množiny sú polygóny.

limitovaná sada

Neobmedzená sada

jediný bod

Prázdna súprava

Bod konvexnej množiny sa nazýva hranatý, ak neleží vo vnútri žiadneho segmentu spájajúceho dva ďalšie body z množiny.

Príklad 3

Rohové body trojuholníka sú jeho vrcholy (sú tri). Rohové body kruhu sú body kruhu, ktorý ho ohraničuje (je ich nekonečne veľa).

Rohový bod mnohostenu sa nazýva jeho summit.

Uvažujme LLP v symetrickej forme.

Veta 4 Optimálny plán LLP zodpovedá vrcholu rozhodovacieho mnohostenu definovaného jeho systémom obmedzení.

MP úlohy

Celková PLP volal <,=,>=)bi (i=l,n) (2) za predpokladu, že xj>

Symetrický < либо = и не отрицательных переменных и задача минимизации функции (1) при линейных ограничениях в неравенствах со знаком > Kanonický zmiešané.

min f(x) = -max(-f(x))

<=b (5)соответствует вполне определенное решение х1…хn, xn+1 уравненияa1x1+…+anxn+xn+1=b (6) при условии что хn+1>

Geometrická interpretácia objektívnej funkcie a obmedzenia celoživotného vzdelávania. Geometrická formulácia LLP.

Nech je daná úloha f=c1x1+c2x2-max (1).

a11x1+a12x2<=b1 }

am1x1+am2x2<=bm}

x1>=0, x2>=0 (3)

Plán úloh (х1,х2) je bod na rovine. Každá nerovnosť s-my 2 rep. je polovičná rovina. Polrovina je konvexná množina. konvexné nazývaná množina, do ktorej patria aj body spojovacieho segmentu (x1 a x2) patriace do tejto množiny. S-ma 2 je priesečník polrovín. Pri prechode môžete získať:

1) konvexná polygonálna uzavretá oblasť.

2) konvexná otvorená polygonálna oblasť

3) jeden bod

4) prázdna sada

5) lúč a rez

Geometrická interpretácia účelovej funkcie: f-tion 1 je rodina rovnobežných čiar, ktoré sa nazývajú úrovňové čiary (čiary konštantnej hodnoty účelovej funkcie). Parciálne derivácie funkcie vzhľadom na x1 a x2 ukazujú rýchlosť nárastu cieľovej funkcie pozdĺž súradníc osí. gradientový vektor ukazuje smer najrýchlejšieho nárastu cieľovej funkcie Pre úlohu 1-3 gradientový vektor = (с1;с2) Opúšťa bod (0,0) a smeruje do bodu so súradnicami (с1;с2). Vektor gradientu je kolmý na čiary úrovne. Priesečník polrovín je tzv oblasť prijateľných riešení (ODR).

Hlavná veta LP. schému zapojenia riešenie LLP, ktoré vyplýva z tejto vety.

Ak má LLP riešenie, potom cieľová funkcia dosiahne extrémnu hodnotu aspoň v jednom z krajných bodov pôdorysného mnohostenu. Ak cieľová funkcia dosiahne extrémnu hodnotu vo viac ako jednom extrémnom bode, potom dosiahne jeden a druhý, čo je ich konvexná lineárna kombinácia.V ktoromkoľvek bode rovnaká hodnota. o PLP rozhodnutie je vhodné použiť záznam v tabuľke manuálne.

BP		SP-Xm+1-Xm+2-Xn
x1	b1o	b11 b12 b1n-m
x2	b2o	b21 b22 b2n-m
xm	bm	bm1 bm2 bmn-m
f	boo	bo1 bo2 bon-m

Algoritmus simplexovej metódy.

1. priviesť model problému do kánonickej podoby;

2. nájsť počiatočný referenčný plán;

3. napíšte úlohu jednoducho. stôl;

5. prejsť do nového referenčného plánu, do nového symp. tabuľky. Na prechod na nový základný plán stačí nahradiť jednu základnú premennú voľnou. Premenná zahrnutá v základe a jej zodpovedajúci stĺpec rozlíšenia sú určené najväčším záporným prvkom f-riadku. Premenná, ktorá vylučuje zo základu a zodpovedajúci povoľovací reťazec, je určená najmenším simplexným pomerom, t.j. pomer prvkov jedného stĺpca k zodpovedajúcemu prvku povoleného stĺpca. Simplexný pomer je nezáporná veličina. Na priesečníku povoľovacej čiary a povoľovacieho stĺpca sa nachádza povoľovací prvok, vzhľadom na ktorý sa simplexná transformácia po stope pravidlo: 1. prvky permisívnej línie sa delia permisívnym prvkom; 2. prvky rozlišovacieho stĺpca sú rozdelené rozlišovacím prvkom a menia znamienko na opačné; 3. Zvyšné prvky tabuľky sa prekreslia podľa pravidla obdĺžnika.:

bij bis bkj=(bkj*bis-bij*bks)/bi

Athova veta o dualite.

ak má jeden z duálnych problémov optimálny dizajn, potom je druhý riešiteľný, t.j. má voliteľný plán. V tomto prípade sa extrémne hodnoty účelových funkcií zhodujú (j=od 1 do n) Σcjxj*= (i=od 1 do m)Σbiyi*, ak sú v origináli. problém, účelová funkcia je neohraničená na množine plánov, potom v duálny problém systém obmedzení je nekonzistentný.

Veta o hodnosti matice TK.

Hodnosť matice A transp.problému je o jednu menšia ako počet rovníc: r(A)=m+n-1.

39. Algoritmus na zostavenie počiatočného základného plánu ZLP.

Ak chcete nájsť počiatočnú základnú líniu, môžete navrhnúť nasledujúce algoritmus:

1. zapíšte úlohu vo forme Jordanovej tabuľky tak, aby všetky prvky stĺpca voľných členov boli nezáporné, t.j. bola splnená nerovnosť aio>=0 (i=1,m). Tie rovnice s-we, v ktorých sú voľné členy záporné, sa predbežne vynásobia -1.

		-x1 ….. -xn
0=	a1o	a11.... a1n
…..	…..	………………………..
0=	amo	am1....amn
f=		-c1.... -cn

Transformujte tabuľku v Jordanových eliminačných krokoch a nahraďte nuly v ľavom stĺpci zodpovedajúcimi x. Avšak pri každom kroku možno zvoliť permisívny akýkoľvek stĺpec obsahujúci aspoň jeden kladný prvok. Rozlišovací reťazec je určený najmenším z pomerov voľných členov k zodpovedajúcim kladným prvkom rozlišovacieho stĺpca. Ak je v procese eliminácie riadok 0, ktorého všetky prvky sú nulové a voľný člen je nenulový, potom rovnice obmedzenia c-ma nemajú žiadne riešenia. Ak však existuje nulový riadok, v ktorom okrem voľného člena nie sú žiadne ďalšie kladné prvky, potom obmedzujúce rovnice c-ma nemajú nezáporné riešenia. kĺb, potom po určitom počte krokov budú všetky nuly v ľavom stĺpci nahradené x a tým sa získa určitý základ a následne jemu zodpovedajúci nosný plán.

40. Algoritmus na zostavenie optimálneho základného plánu celoživotného vzdelávania.

Počiatočný referenčný návrh Ho sa skúma z hľadiska optimálnosti.

Ak sa v f-rade (okrem voľného termínu) nevyskytujú žiadne negatívne prvky, je -plán optimálny. Ak v rade f nie sú žiadne nulové prvky, potom je optimálny plán jedinečný; ak je medzi prvkami aspoň jedna nula, potom existuje nekonečný počet optimálnych plánov. Ak je v riadku f aspoň jeden záporný prvok a v príslušnom stĺpci nie sú žiadne kladné prvky, potom účelová funkcia nie je obmedzená v prípustnej oblasti. Úloha je neriešiteľná. Ak je v riadku f aspoň jeden negatívny prvok a v každom stĺpci s takýmto prvkom aspoň jeden pozitívny prvok, potom môžeme prejsť na nový základný plán, ktorý je bližšie k optimálnemu. Na tento účel sa stĺpec so záporným prvkom v riadku f berie ako povoľný; určte rozlišovací reťazec z minimálneho simplexného pomeru a urobte krok Jordanovej eliminácie. Výsledný základný plán sa opäť skúma na optimálnosť. Toto sa opakuje, kým sa nenájde optimálny základný plán alebo kým sa problém nepotvrdí ako neriešiteľný.

Algoritmus Gomoriho metódy.

1. Na nájdenie optimálneho plánu úloh sa používa simplexná metóda. Ak sú všetky zložky optimálneho plánu celočíselné, potom je optimálny. V opačnom prípade prejdite na krok 2

2. Spomedzi neceločíselných komponentov by ste si mali vybrať ten s zlomok je najväčší a pomocou zodpovedajúceho riadku simplexnej tabuľky sformulujte podľa vzorca správnu hranicu

(n-m,s=1)∑ (αkm+1)Xm+1≥(βk)

3. Sformulovaná nerovnosť sa transformuje na ekvivalentnú nulovú rovnosť a zahrnie sa do simplexný stôl s neceločíselným optimálnym plánom

4. Výsledný rozšírený problém sa rieši simplexnou metódou. Ak výsledný plán nie je celé číslo, prejdite znova na krok 2.

Ak sa v procese riešenia objaví riadok s neceločíselným voľným členom a inými celočíselnými koeficientmi, potom zodpovedajúca rovnica nemá riešenie v celých číslach. V tomto prípade je pôvodný problém neriešiteľný aj v celých číslach Gomoryho metóda má obmedzené uplatnenie. S jeho pomocou je vhodné riešiť malé problémy, pretože. počet iterácií môže byť veľmi veľký.

Rôzne formy Záznamy LLP (všeobecné, kanonické, symetrické)

MP úlohy: stanovenie optimálneho plánu, stanovenie optimálneho objemu výkonu, stanovenie optimálnej kombinácie plodín poľnohospodárskych plodín, vytvorenie optimálneho balíka aktív, maximalizácia zisku banky a pod.

Spoločná PLP sa nazýva maximalizačný (minimalizačný) problém lineárna funkcia f=Σcj*xj-max(min) (1) pri lineárnych obmedzeniach ∑aij *xj(=<,=,>=)bi (i=1,n) (2) za predpokladu, že xj>=0(j=1,n1), xj-ľubovoľné (j=n1+1,n)(3) kde cj,aij, bikonštantné čísla .

Symetrický forma zápisu ZLP je problém maximalizácie funkcie (1) pri lineárnych obmedzeniach v znamienkových nerovnostiach< либо = и не отрицательных переменных и задача минимизации функции (1) при линейных ограничениях в неравенствах со знаком >alebo = a nezáporné premenné. Kanonický forma zápisu ZLP je problém maximálnej funkcie (1) pri lineárnych obmedzeniach rovnosti a nezáporných premenných. Akákoľvek iná forma sa nazýva zmiešané.

min f(x) = -max(-f(x))

Transformácia nerovnosti na rovnicu a naopak sa vykonáva na základe lemmy: pre akékoľvek riešenie x1 ... xn nerovnosti a1x1 + ... + anxn<=b (5)соответствует вполне определенное решение х1…хn, xn+1 уравненияa1x1+…+anxn+xn+1=b (6) при условии что хn+1>=0(7) a naopak. Akékoľvek riešenie x1…xn,xn+1 rovnice 6 a nerovnosti 7 zodpovedá riešeniu x1…xn nerovnosti 5.

Aby ste mohli prejsť z daného sim formulára na zadok kanonickú formu, je potrebné zadať bilančných (nivelačných) premenných. Toto je založené na vete o nerovnosti: akákoľvek nerovnosť môže byť reprezentovaná ako rovnica alebo jednoduchá nerovnosť.

Zaznamenávanie cieľovej funkcie a systému obmedzení rôzne úlohy lineárne programovanie nie je rovnaké: v niektorých problémoch je potrebné nájsť minimum cieľovej funkcie av iných - maximum; v niektorých prípadoch požadované premenné závisia od jedného indexu av iných od dvoch; v niektorých problémoch sú obmedzenia dané vo forme systému lineárne nerovnosti a v iných - vo forme systému lineárnych rovníc. V praxi sú možné aj problémy, v ktorých majú niektoré obmedzenia tvar lineárnych nerovností a niektoré majú tvar lineárnych rovníc. Tiež nie všetky problémy môžu vyžadovať nezápornosť premenných.

Účtovanie takejto rozmanitosti problémov lineárneho programovania si vyžaduje vývoj špeciálnych metód na riešenie ich jednotlivých tried. Svoju pozornosť zameriame na štúdium všeobecných vlastností a metód lineárneho programovania, písaných v takzvanej kanonickej forme.

Ak v úlohe lineárneho programovania má systém počiatočných obmedzení formu rovníc typu

a musíte nájsť maximum funkcie lineárneho cieľa

potom sa predpokladá, že problém lineárneho programovania je napísaný v kanonickej forme.

Akýkoľvek problém lineárneho programovania možno ľahko zredukovať na kanonickú formu. AT všeobecný prípad na to stačí byť schopný po prvé zredukovať problém minimalizácie objektívnej funkcie na problém jej maximalizácie, po druhé prejsť od obmedzení nerovnosti k obmedzeniam rovnosti a po tretie zmeniť tie premenné, ktoré nie sú podlieha podmienke nezápornosti.

Keď potrebujete nájsť minimum funkcie , môžeme pristúpiť k hľadaniu maxima funkcie , keďže tvrdenie je pravdivé:
.

Obmedzenie nerovnosti pôvodný problém, ktorý vyzerá ako " " , možno zmeniť na obmedzenie rovnice pridaním ďalšej nezápornej premennej na jej ľavú stranu a obmedzenia nerovnosti tvaru " » – odčítaním ďalšej nezápornej premennej od jej ľavej strany.

Všimnite si, že počet zavedených dodatočných nezáporných premenných sa vždy rovná počtu nerovností v pôvodnom systéme obmedzení.

Zavedené dodatočné premenné majú veľmi špecifický ekonomický význam. Ak teda obmedzenia pôvodného problému lineárneho programovania odrážajú náklady a dostupnosť výrobných zdrojov, potom číselná hodnota dodatočná premenná zobrazuje množstvo zodpovedajúceho nevyužitého zdroja.

Všimnite si tiež, že ak nejaká premenná nespĺňa podmienku nezápornosti, potom ju treba nahradiť dvomi nezápornými premennými a , prijímanie
.

Príklad. Napíšte nasledujúci lineárny optimalizačný problém v kanonickom tvare: nájdite minimum funkcie
pod obmedzeniami

rozhodnutie

V tomto probléme musíte nájsť minimum cieľovej funkcie a systém obmedzení obsahuje štyri nerovnosti. Aby sme to mohli napísať v kanonickom tvare, je potrebné prejsť od obmedzení nerovností k obmedzeniam rovnice a tiež transformovať účelovú funkciu.

Keďže počet nerovností zahrnutých v systéme obmedzení problému je štyri, tento prechod sa musí uskutočniť so zavedením ďalších štyroch nezáporných premenných. Navyše v druhej a štvrtej nerovnosti je znak " » , takže na ich ľavú stranu pridáme ďalšie premenné. V prvej a tretej nerovnosti znak „ “, čo znamená, že ďalšie premenné sa odčítajú od ich ľavej strany.

Objektívnu funkciu transformujeme aj zmenou všetkých znamienok na opačné a nájdeme jej maximum.

Preto bude tento problém lineárneho programovania napísaný v nasledujúcom texte kanonická forma:

nájsť maximum funkcie

pod obmedzeniami

Vo všeobecnom prípade je problém lineárneho programovania napísaný tak, že rovnice aj nerovnice sú obmedzeniami a premenné môžu byť nezáporné alebo sa môžu ľubovoľne meniť. V prípade, že všetky obmedzenia sú rovnice a všetky premenné spĺňajú podmienku nezápornosti, problém lineárneho programovania sa nazýva kanonický. Môže byť reprezentovaný súradnicovým, vektorovým alebo maticovým zápisom.

1. Kanonický problém lineárneho programovania v súradnicovom zápise má tvar

.

V kompaktnejšej forme túto úlohu možno napísať pomocou súčtu,

(1.7)

2. Kanonický problém lineárneho programovania vo vektorovom zápise má tvar

(1.8)

kde ,

.

3. Kanonický problém lineárneho programovania v maticovom zápise má tvar

(1.9)

, .

Tu ALE je matica koeficientov sústavy rovníc, X– stĺpcová matica premenné úlohy, je stĺpcová matica pravých častí systému obmedzení.

Často používané úlohy lineárneho programovania, tzv symetrické, ktoré v matričnom zápise majú tvar

(1.10)

(1.11)

1.4. Casting spoločná úloha lineárne programovanie
do kánonickej podoby

Vo väčšine metód riešenia problémov lineárneho programovania sa predpokladá, že systém obmedzení pozostáva z rovníc a prirodzených podmienok pre nezápornosť premenných. Pri zostavovaní matematických modelov ekonomických problémov sa však obmedzenia formujú najmä do sústav nerovníc, preto je potrebné vedieť prejsť od sústavy nerovníc k sústave rovníc. Za týmto účelom dokážeme nasledujúcu vetu.

Veta 1.1. O nahradení nerovnosti rovnicou. Každé rozhodnutie nerovnosti

zodpovedá jedinečnému riešeniu rovnice

a nerovnosti

, (1.14)

a naopak, každé riešenie rovnice (1.13) a nerovnosti (1.14) zodpovedá jedinečnému riešeniu nerovnosti (1.12).

Dôkaz. Nechať byť je riešením nerovnosti (1.12), potom . Rozdiel medzi pravou a ľavou časťou tejto nerovnosti označme , t.j.

Samozrejme . Dosadíme do rovnice (1.13) namiesto premenné hodnoty , dostaneme

Teda spĺňa rovnicu (1.13) a nerovnosť (1.14). Takže prvá časť vety je dokázaná.

Splňme teraz rovnicu (1.13) a nerovnosť (1.14), t.j. máme

A

Vynechaním nezápornej hodnoty na ľavej strane poslednej rovnosti dostaneme

t.j. spĺňa nerovnosť (1,12). Veta bola dokázaná.

Ak je nerovnosť , potom je potrebné na jej ľavej strane zadať ďalšiu nezápornú premennú so znamienkom mínus, t.j.

Negatívne premenné zavedené do obmedzení nerovností, aby sa zmenili na rovnice, sa nazývajú dodatočné premenné. Ďalšie premenné sú zavedené do účelovej funkcie s nulovými koeficientmi, a preto neovplyvňujú jej hodnotu.

V prípade, že problém má ľubovoľne sa meniace premenné, potom je každá takáto premenná nahradená rozdielom dvoch nezáporných premenných, t.j. , kde a .

Niekedy je potrebné posunúť sa v probléme od hľadania minima k hľadaniu maxima alebo naopak. Na to stačí zmeniť znamienka všetkých koeficientov účelovej funkcie na opačné a zvyšok problému ponechať nezmenený. Optimálne riešenia maximálnych a minimálnych problémov získaných týmto spôsobom sa zhodujú a hodnoty cieľových funkcií optimálne riešenia líšia sa len znakom.

Príklad 1.1. Redukujte problém lineárneho programovania na kanonickú formu.

D

rozhodnutie. Prejdime k problému hľadania maxima účelovej funkcie. Aby sme to dosiahli, zmeníme znamienka koeficientov účelovej funkcie. Na transformáciu druhej a tretej nerovnosti systému obmedzení do rovníc zavádzame nezáporné dodatočné premenné (na matematický model táto operácia je označená písmenom D). Premenná sa zadáva na ľavej strane druhej nerovnosti so znamienkom „+“, keďže nerovnosť má tvar . Premenná sa zadáva naľavo od tretej nerovnosti so znamienkom „-“, keďže nerovnosť má tvar . Premenné sa zavádzajú do účelovej funkcie s koeficientom rovným nule. Premenná , na ktorú nie je uložená podmienka nezápornosti, je nahradená rozdielom , . Úlohu zapisujeme v kanonickom tvare

V niektorých prípadoch je potrebné priniesť kanonický problém k symetrickému problému. Zvážte príklad.

Príklad 1.2. Redukujte problém lineárneho programovania na symetrickú formu