V lineárnom programovaní sa používa grafická metóda, ktorá je určená konvexnými množinami (polyhedra roztoky). Ak je hlavnou úlohou lineárne programovanie Má optimálny plánCieľová funkcia má hodnotu v jednom z vrcholov polyhedrónových roztokov (pozri obrázok).

Menovanie služby. Cez táto služba Môže byť online režim Riešiť úlohu lineárneho programovania s geometrickou metódou, rovnako ako získať riešenie duálnej úlohy (vyhodnotiť optimalifikátu využívania zdrojov). Okrem toho vytvára šablónu riešenia v programe Excel.

Inštrukcie. Vyberte počet riadkov (počet obmedzení).

Počet obmedzení 1 2 3 4 5 6 7 8 9 10

Ak je počet premenných viac ako dva, systém musí byť uvedený na SLP (pozri príklad a príklad č. 2). Ak je reštrikčné dvojité, napríklad 1 ≤ x 1 ≤ 4, potom sa rozdelí na dva: x 1 ≥ 1, x 1 ≤ 4 (to znamená, že počet riadkov sa zvyšuje o 1).
Túto službu môže používať aj oblasť prípustného riešenia (ADR).

Spolu s touto kalkulačkou tiež použite nasledovné:
Metóda rozhodnutia Simplex ZLP

Riešenie úlohy dopravy
Riešenie hry Matrix
Pomocou služby v online režime môžete určiť cenu hry Matrix (dno a horné hranice), skontrolujte prítomnosť sedlového bodu, nájdite riešenie pre zmiešané metódy stratégie: Minimax, simplex-metóda, grafika (Geometric) Metóda, Hnedná metóda.
Extrémna funkcia dvoch premenných
Výpočet limitov

Riešenie lineárneho programovania Problém Grafická metóda zahŕňa nasledujúce kroky:

1. Na X 1 0x 2 rovine stavať rovno.
2. Polovina sa stanoví.
3. Definujte roztoky mnohouholníkov;
4. Vektor N (C1, C2) je postavený, ktorý označuje smer cieľovej funkcie;
5. Presunúť priamu cieľovú funkciu c 1 x 2 + C 2 x 2 \u003d 0 v smere vektora n do extrémneho bodu polygónových roztokov.
6. Vypočítajte súradnice bodu a hodnotu cieľovej funkcie v tomto bode.

Zároveň môžu vzniknúť tieto situácie:

Príklad. Spoločnosť vyrába dva typy výrobkov - P1 a P2. Na výrobu výrobkov sa používajú dva typy surovín - C1 a C2. Hromadné ceny Jednotky výrobkov: 5 D.E. Pre P1 a 4, D.E. Pre p2. Spotreba surovín na jednotku produktov formulára P1 a typu P2 je uvedený v tabuľke.
Tabuľka - Spotreba surovín na výrobu

Obmedzenia týkajúce sa dopytu výrobkov sú stanovené: denná výroba produktov P2 by nemala presiahnuť dennú výrobu výroby P1 nie viac ako 1 tonu; Maximálna denná produkcia P2 by nemala prekročiť 2 tony.
Je potrebné určiť:
Koľko produktov každého typu by malo priniesť podnik tak, že príjmy z predaja výrobkov je maximálne?

1. Formulovať matematický model Lineárne programovacie úlohy.
2. Vyriešiť úlohu lineárneho programovania graficky (pre dve premenné).

Rozhodnutie.
Vyvolávame matematický model problému lineárneho programovania.
x 1 - Výroba výrobkov P1, jednotky.
x 2 - Výroba produktov P2, jednotiek.
x 1, x 2 ≥ 0

Obmedzenia zdrojov
6x 1 + 4x 2 ≤ 24
x 1 + 2x 2 ≤ 6

Obmedzenia dopytu
x 1 +1 ≥ x 2
x 2 ≤ 2

Cieľová funkcia
5x 1 + 4x 2 → Max

Potom dostaneme nasledujúci ZLP:
6x 1 + 4x 2 ≤ 24
x 1 + 2x 2 ≤ 6
x 2 - x 1 ≤ 1
x 2 ≤ 2
x 1, x 2 ≥ 0
5x 1 + 4x 2 → Max

Úloha. Riešiť graficky, úlohu lineárneho programovania, určovanie extrémnej hodnoty cieľovej funkcie:

s obmedzeniami

Stavujeme oblasť prípustných riešení, t.j. Graficky systém nerovností. Na tento účel budeme konštruovať každú priamu a definovať polovičné lietadlo dané nerovnosť (pol dosiek sú označené zdvihom).

Stanovujeme rovnicu 3x 1 + x 2 \u003d 9 dva body.
Ak chcete nájsť prvý bod rovnocenné X 1 \u003d 0. Nájdeme x 2 \u003d 9. Ak chcete nájsť druhý bod, ktorý zodpovedá X 2 \u003d 0. Nájsť x 1 \u003d 3. Pripojte bod (0, 9) s (3; 0) priama linka. Definujeme polovičnú rovinu definovanú nerovnosť. Výberom bodu (0, 0) definujeme znamenie nerovnosti v polosahline: 3. 0 + 1. 0 - 9 ≤ 0, t.j. 3x 1 + x 2 - 9 ≥ 0 v polovici roviny nad rovno.
Stavujeme rovnicu x 1 + 2x 2 \u003d 8 dva body.
Ak chcete nájsť prvý bod rovnocenné X 1 \u003d 0. Nájdeme x 2 \u003d 4. Ak chcete nájsť druhý bod, sme zodpovedať x 2 \u003d 0. Nájdeme x 1 \u003d 8. Spojíme bod (0; 4) s (8; 0) Priama čiara. Definujeme polovičnú rovinu definovanú nerovnosť. Výberom bodu (0, 0) definujeme znamenie nerovnosti v polosahline: 1. 0 + 2. 0 - 8 ≤ 0, t.j. x 1 + 2x 2 - 8≥ 0 v polovici roviny nad rovno.
Stavujeme rovnicu x 1 + x 2 \u003d 8 dva body.
Ak chcete nájsť prvý bod, ktorý zodpovedá X 1 \u003d 0. Nájdeme x 2 \u003d 8. Ak chcete nájsť druhý bod, ktorý zodpovedá X 2 \u003d 0. Nájdeme X 1 \u003d 8. Spojíme bod (0; 8) C (8) 0) Priama čiara. Definujeme polovičnú rovinu definovanú nerovnosť. Výberom bodu (0, 0) definujeme znamenie nerovnosti v polosahline: 1. 0 + 1. 0 - 8 ≤ 0, t.j. x 1 + x 2 - 8 \u003c0 v pol-rovine pod priamkou.

Priesečník polôh bude oblasť, ktorej súradnice, z ktorých body spĺňajú podmienku nerovností problémov obmedzení.
Označujú hranice oblasti polygónu riešení.

Skontrolujte správnosť výstavby grafov funkcií môže používať kalkulačku

Zvážte cieľovú funkciu úlohy F \u003d 4x 1 + 6x 2 → min.
Vytvárame priamu zodpovedajúcu funkciu funkcie F \u003d 0: F \u003d 4x 1 + 6x 2 \u003d 0 Gradientový vektor zostavený z koeficientov cieľovej funkcie indikuje odkaz na minimalizáciu F (X). Štart Vektor - bod (0; 0), koncový bod (4; 6). Tento rovný paralelne posúvame. Vzhľadom k tomu, že máme záujem o minimálne riešenie, takže sme presmerovaní na prvý nádych určenej oblasti. Na grafe táto priama je označená bodkovanou čiarou.

Priamy F (x) \u003d4x 1 + 6x 2 prechádza oblasťou v bode B. Pretože bod B sa získa v dôsledku priesečníka priameho (1) a (2) , jeho súradnice spĺňajú rovnice týchto priamych:
3x 1 + x 2 \u003d 9
x 1 + 2x 2 \u003d 8

Rozhodovanie systému rovníc, získavame: X 1 \u003d 2, X 2 \u003d 3
Odkiaľ nájdete minimálnu hodnotu cieľovej funkcie:
F (x) \u003d 4 * 2 + 6 * 3 \u003d 26

Najjednoduchšia a vizuálna metóda riešenia problému lineárneho programovania (ZLP) je grafická metóda. Je založený na geometrickom výklade lineárneho programovacieho problému a používa sa pri riešení ZLP s dvoma neznámymi:

Budeme zvážiť riešenie tejto úlohy v lietadle. Každá nerovnosť systému funkčných obmedzení geometricky určuje polročnú rovinu s ohraničením priamym p. x, + + a j2 x 2 \u003d b n i \u003d 1, t. Podmienky trvania určujú polovičnú rovinu s hranicou rovno x (= 0, x 2= 0. Ak je systém koordinovaný, pollenina, pretínanie, tvorí spoločnú časť, ktorá je konvexná súprava a predstavuje súbor bodov; Súradnicou každého z týchto bodov sú riešením tohto systému. Súbor týchto bodov sa volá polygonové roztoky. Môže to byť bod, segment, lúč, obmedzený a neobmedzený polygón.

Geometricky ZLP je zavedenie takéhoto uhlového bodu roztokov polygónu, ktorých súradnice sa dodávajú do maximálnej (minimálnej) hodnoty lineárnej cieľovej funkcie, \\ t Okrem toho sú všetky body polygónových roztokov prípustné riešenia.

Lineárna rovnica opisuje množstvo bodov ležiacich na jednej priamke. Lineárna nerovnosť opisuje určitú oblasť v rovine.

Definujeme, akú časť lietadla popisuje nerovnosť 2x (+ ZH 2 12.

Po prvé, budeme postaviť rovno 2x, + ZH2 \u003d 12. Prejde body (6; 0) a (0; 4). Po druhé, definujeme, čo polovica roviny uspokojí nerovnosť. Ak to chcete urobiť, vyberte ľubovoľný bod na grafe, ktorý nepatrí do linky a nahradí svoje súradnice nerovnosti. Ak sa vykoná nerovnosť, potom tento bod Je to prípustné riešenie a pol-rovina obsahujúca bod, uspokojuje nerovnosť. Na nahradenie nerovnosti je vhodné použiť pôvod súradníc. Náhradník x (\u003d x 2 \u003d 0 v nerovnosti 2x, + Zh 2 12. Dostaneme 2 0 + 3 0

Podobne môžete graficky znázorniť všetky obmedzenia lineárnej programovacej úlohy.

Rozhodnutím každej nerovnosti Limitom Limitom ZLP je polovičná rovina obsahujúca hranicu priamky a nachádza sa z neho jedným z nich. Nazýva sa priesečník polosviecích miest, z ktorých každý je určený zodpovedajúcou nerovnosťou systému, sa nazýva plocha prípustných riešení (ORD) alebo oblasti definície.

Treba pripomenúť, že oblasť prípustných riešení spĺňa podmienky negativity (Xj. > 0, j \u003d. 1, p). Súradnice akéhokoľvek bodu, ktorý vlastnil oblasť definície, sú prípustným riešením problému.

Ak chcete nájsť extrémnu hodnotu cieľovej funkcie, s grafickým rozhodnutím VLP, použitie gradient vektora, Súradnice, z ktorých sú čiastočné deriváty cieľovej funkcie:

Tento vektor zobrazuje smer definície cieľovej funkcie. Priamy c [x L + C 2 x 2 \u003d F (x 0), kolmé na gradientový vektor je Úroveň riadkov Cieľová funkcia (Obr. 2.2.2). V ľubovoľnom bode riadiacej čiary je cieľová funkcia rovnakú hodnotu. Vyrovnávame cieľovú funkciu konštantnej hodnoty ale. Zmena hodnoty ale, Dostaneme rodinu paralelných rovných línií, z ktorých každá je riadok cieľovej funkcie.

Obr. 2.2.2.

Dôležitá vlastnosť lineárna funkcia Je to, že s rovnobežnou čiarou posunu v jednom smere zväčšiť A keď sa posunujú v d r y y, bočná znižuje.

Grafická metóda Rozhodnutie ZLP pozostáva zo štyroch etáp:

• 1. Oblasť prípustných riešení (ORD) ZLP je postavený.
• 2. Gradientový vektor cieľovej funkcie (CF) je postavený so začiatkom v bode x 0 (0; 0): v \u003d (s, c 2).
• 3. CJXJ + LINE c 2 x 2 \u003d A (A - Trvalá hodnota) - DIRECT, kolmé na gradient V, - pohybuje sa v smere gradientového vektora v prípade maximalizácie cieľovej funkcie f (x v x 2) až necháva limity ODR. Pri minimalizácii / (*, x 2) Úroveň riadkov sa pohybuje v smere oproti gradientu vektora. Extrémny bod (alebo bod) ADR s týmto pohybom a je maximálny bod (minimum) f (X. p jc 2).

Ak je priame zodpovedajúce riadiacemu riadku, pri jeho pohybe neopúšťa ADR, potom minimálna (maximálna) funkcia f (X.p x 2) neexistuje.

Ak je riadok úrovne cieľovej funkcie paralelný s funkčným obmedzením úlohy, na ktorej sa dosiahne optimálna hodnota CF, optimálna hodnota CF sa dosiahne v ktoromkoľvek bode tohto obmedzenia ležiaceho medzi dvoma optimálnymi uhlovými bodkami, a podľa toho niektorý z týchto bodov je optimálnym roztokom ZLP.

4. Súradnice maximálneho bodu (minimum) sú definované. Aby to urobilo, stačí vyriešiť systém rovníc priameho, čo dáva maximálny bod v priesečníku (minimum). Hodnota f (x (, x 2),v výslednom bode je maximálna (minimálna) cieľová funkcia.

Možné situácie grafické riešenie ZLP sú uvedené v tabuľke. 2.2.1.

Tabuľka 2.2.1

Typ ODR	vyhliadka optimálne riešenie
Obmedzený	ROZHODNUTIE
	Nekonečný súbor riešení
Neobmedzený	CF nie je obmedzený na nižšie
	Cf nie je obmedzený na vrchol
	ROZHODNUTIE
	Nekonečný súbor riešení
	ROZHODNUTIE
	Nekonečný súbor riešení

Príklad 2.2.1. Plánovanie výroby šijacieho podniku (úloha kostýmov).

Plánuje sa uvoľniť dva typy kostýmov - muž a žena. Žena kostým vyžaduje 1 m vlnu, 2 M Lavsana a 1 osobu modelovaciu prácu; Na mužskom - 3,5 m vlne, 0,5 m Lavsana a 1 osoba modelovacia práca. Existuje 350 m vlna, 240 m Lavsana a 150 ľudí.

Je potrebné určiť, koľko oblekov každého typu je potrebné šiť, aby sa zabezpečil maximálny zisk, ak je zisk z predaja ženského kostýmu 10 denník. a od mužského - 20 denníka. Jednotky. Treba mať na pamäti, že je potrebné šiť najmenej 60 mužských kostýmov.

Ekonomický a matematický model problému

Premenné: X, - počet ženských kostýmov; x 2 - Počet pánskych oblekov.

Cieľová funkcia:

Obmedzenia:

Prvé obmedzenie (na vlnu) má formulár x (+. 3,5x 2 x (+ 3,5x 2 \u003d 350 prechádza bodmi (350; 0) a (0; 100). Druhé obmedzenie (podľa Lavsany) má vzhľad 2x ( + 0,5x 2 2x x + 0,5x 2 \u003d 240 prechádza bodmi (120; 0) a (0; 480). Tretie obmedzenie (podľa práce) má formulár x + x 2 150. Priamo x (+ x 2 \u003d 150 prechádza bodmi (150; 0) a (0; 150). Štvrté obmedzenie (podľa počtu pánskych oblekov) má x 2 \u003e 60. Rozhodnutím tejto nerovnosti, polovičného lietadla x 2 \u003d. 60.

V dôsledku križovatky vybudovaných štyroch poloskupiek získame mnohouholník, ktorý je oblasťou prípustných riešení našej úlohy. Akýkoľvek bod tohto polygónu spĺňa všetky štyri funkčné nerovnosti a pre akýkoľvek bod mimo tohto polygónu bude prerušená aspoň jedna nerovnosť.

Na obr. 2.2.3 Oblasť prípustných riešení (ORD) je oholená. Na určenie smeru pohybu na optimum konštruujeme gradient vektora V, ktorého súradnice sú čiastkové deriváty cieľovej funkcie:

Ak chcete vytvoriť takýto vektor, musíte pripojiť bod (10; 20) so začiatkom súradníc. Pre pohodlie môžete vytvoriť vektor úmerný vektoru V. Takže na obr. 2.2.3 ukazuje vektor (30; 60).

Potom konštruujte čiaru úrovne 10xj + 20x 2 \u003d ale. Vyrovnávame cieľovú funkciu konštantnej hodnoty ale. Zmena hodnoty ale, Získame rodinu paralelných rovných línií, z ktorých každý je riadok úrovne cieľovej funkcie.

Grafický spôsob riešenia ZLP je založený na obvineniach uvedených v odseku 2.1. Podľa teorem 2 je optimálne riešenie v hornej časti oblasti prípustných riešení, a preto vyrieši ZLP, aby vyhľadal vrchol platných riešení, ktorých súradnice poskytujú optimálnu hodnotu cieľovej funkcie.

Grafická metóda sa používa na riešenie obmedzenej triedy úloh s dvoma premennými, niekedy s tromi premennými. Treba poznamenať, že pre tri premenné táto oblasť nestačí.

Algoritmus grafickej metódy rozhodnutia ZLP

Implementácia grafického spôsobu rozhodnutia ZLP zváži príklady.

Príklad 2.2.1. Solve ZLP Grafická metóda:

(2.2.1)

max z.=x. 1 + 4x. 2 (2.2.2)

Rozhodnutie.Vytvorenie plochy prípustných riešení, ktorá sa skladá z prechodu poloskupín zodpovedajúcich každej nerovnosti obmedzujúceho systému (2.2.1), ktorý napíše hraničné priame rovnice:

l. 1: x. 1 + 5x. 2 = 5; l. 2: x. 1 + x. 2 = 6; l. 3: 7x. 1 + x. 2 = 7.

l. 1 na myseľ (2.2.3.) Rozdeľujeme obe časti 5:
. Teda l. 1 odreže na osi Ohovárať 1 5 jednotiek, na osi Ohovárať 2 1 jednotka. Podobne máme l. 2:
a l. 3:
.

Na určenie poloskupín, ktoré spĺňajú obmedzenia systému (2.2.1), obmedzenia potrebujú nahradiť súradnice akéhokoľvek bodu, ktorý nie je ležiaci na hraničnej priamej. Ak dostaneme vernú nerovnosť, potom všetky body z tohto poloviny sú rozhodnutiami tejto nerovnosti. V inak Vyberte inú polovicu.

Prvé a druhé požadované polovice sú teda umiestnené v opačnom smere od pôvodu súradníc (0 - 5 · 0 - päť; 7 · 0 + 0 7) a druhý - v smere začiatku súradníc (0 + 0 6). Oblasť prípustných riešení na obrázku 2.2.1 je tieňovaná.

Obrázok 2.2.1 - oblasť prípustných riešení

Ak chcete nájsť optimálny plán, ktorý bude v hornej časti polygónových riešení, musíte stavať vektorové smery
=(z 1 ,z 2), ktorý označuje smer najväčšieho zvýšenia cieľovej funkcie z.=z 1 h. 1 +z 2 h. 2 .

V tejto úlohe vektorové smery
\u003d (1, 4): Začína v bode O(0,0) a končí v bode N.(1, 4).

Ďalej postavíme rovno, ktorá prechádza oblasť prípustných riešení kolmých na vektor, a je nazývaný cieľ úrovne riadkov funkcie. Presunúť riadok úrovne v smere vektorového smeru maximalizácie cieľovej funkcie z.a v smere opaku, v prípade minimalizácie z., Až na poslednú križovatku s oblasťou prípustných riešení. V dôsledku toho sa určuje bod alebo bod, kde cieľová funkcia dosiahne extrémnu hodnotu, alebo je nastavená neobmedzená cieľová funkcia. z.na nastavených riešeniach problému.

Maximálny bod cieľovej funkcie teda z.je bod ALEkrižovatky l. 2 I. l. 3 .

Vypočítajte optimálnu hodnotu cieľovej funkciez. Nájsť súradnice boduALE . Od boduALE - Toto je priesečnícky bod priamehol. 2 I.l. 3, jeho súradnice spĺňajú systém rovníc zložených z rovníc zodpovedajúcich hraničných rovných čiar:

Takže bodALE Má koordinátyx. 1 =1/6, x. 2 = 35/6.

Ak chcete vypočítať optimálnu hodnotu cieľovej funkcie, musíte nahradiť súradnice boduALE .

Nahradenie súradníc boduALE V cieľovej funkcii (2.4) sa dostaneme

maxz. \u003d 1/6 + 4 · (35/6) \u003d 47/2.

Príklad 2.2.2. Vytvorte oblasť platných riešení lineárnych nerovností (2.2.4) v lietadle (2.2.4) a nájsť najväčšie a najmenšie hodnoty cieľovej funkcie (2.2.5):

(2.2.4)

z.= –2x. 1 –x. 2 (2.2.5)

Rozhodnutie.Vytvárať plochu prípustných riešení, ktoré pozostávajú z križovatky poloskupín zodpovedajúcich každej nerovnosti limitného systému (2.2.4), ktorý bude písať rovnice hraničných rovných čiar:

l. 1: 4x. 1 – x. 2 = 0; l. 2: x. 1 + 3x. 2 = 6; l. 3: x. 1 – 3x. 2 = 6; l. 4: x. 2 = 1.

Priamy l. 1 prechádza bodom s súradnicami (0; 0). Zostavte ho x. 2 cez x. 1: x. 2 = 4x. jeden. Nájdeme ďalší bod, cez ktorý prechádza priamka l. 1, napríklad (1; 4). Prostredníctvom bodu so súradnicami (0, 0) a bod so súradnicami (1; 4) budú stráviť priame l. 1 .

Priniesť rovnicu priamo l. 2 Kees v segmentoch na osiach (2.2.3) Rozdeľujeme obe časti 6:
. Teda l. 2 odreže na osi Ohovárať 1 6 jednotiek, na osi Ohovárať 2 - 2 jednotky. Podobne máme l. 3:
a rovno l. 4 paralelné s osou Ohovárať 1 a prechádza bodom so súradnicami (0; 1).

Na určenie polohy, ktoré spĺňajú obmedzenia systému (2.2.4) v obmedzeniach, je potrebné nahradiť súradnice akéhokoľvek bodu, ktorý neleží na hraničnej priamej. Na základe obmedzeníh. 1 0, h. 2 0, prípustná plocha riešenia ZLP Leží v prvom štvrťroku koordinačného lietadla.

O
blast prípustných riešení na obrázku 2.2.2 je tieňovaný.

Obrázok 2.2.2 - oblasť prípustných riešení

Stavujeme vektorové smery
\u003d (-2, -1). Ďalej vybudujeme rovnú čiaru, kolmú na vektor .

Ak chcete nájsť najvyššiu hodnotu cieľovej funkcie, presuňte riadok úrovne v smere vektora do posledného priesečníka s oblasťou prípustných riešení. Maximálny bod cieľovej funkcie teda z.je bod ALE(Križovatka l. 1 I. l. 2).

Vypočítajte optimálnu hodnotu cieľovej funkcie z.nájsť súradnice bodu ALE. Od bodu ALE- Toto je priesečnícky bod priameho l. 1 I. l. 2, jeho súradnice spĺňajú systém rovníc zložených z rovníc zodpovedajúcich hraniciach rovných čiar:

Takže bodALE Má koordinátyx. 1 =6/13, x. 2 = 24/13.

Nahradenie súradníc boduALE V cieľovej funkcii (2.2.5) získame optimálnu hodnotu cieľovej funkcie

max z.\u003d - 2 · (6/13) - (24/13) \u003d - 36/13.

Ak chcete nájsť najmenšiu hodnotu cieľovej funkcie, presuňte riadok úrovne v smere oproti vektoru až do poslednej križovatky s oblasťou prípustných riešení. V tomto prípade je cieľová funkcia neobmedzená v oblasti prípustných riešení, t.j. ZLP nemá minimum.

V dôsledku rozhodnutia ZLP sú možné tieto prípady možné: \\ t

Cieľová funkcia dosiahne optimálnu hodnotu v jedinom vrchole z polygónových roztokov;

Cieľová funkcia dosiahne optimálnu hodnotu v ľubovoľnom bode rebro z polygónových roztokov (ZLP má alternatívne referenčné plány s rovnakými hodnotamiz. );

ZLP nemá optimálne plány;

ZLP má optimálny plán v prípade neobmedzenej oblasti prípustných riešení.

Grafická metóda je celkom jednoduchý a vizuálny na riešenie lineárnych problémov s programovaním s dvoma premennými. Je založený na geometrický Zastupujúce prípustné riešenia a úlohy TSC.

Každá z nerovností Lineárneho programovacieho problému (1.2) určuje určitú polovičnú rovinu na rovine koordinácie (obr. 2.1) a systém nerovností všeobecne je priesečník zodpovedajúcich rovín. Mnohé body priesečníka týchto polosviecích pozícií sa nazýva plocha prípustných riešení (ORD). ADR je vždy konvexný Obrázok, t.j. Držanie nasledujúcej vlastnosti: Ak sú dva body A a B patria k tomuto číslu, potom k nemu patrí celý segment AV. ADR graficky môže byť reprezentovaný konvexným polygónom, neobmedzenom konvexnej polygonálnej oblasti, segment, lúč, jeden bod. V prípade neúplnosti systému obmedzení problému (1.2) je ADR prázdny súbor.

Všetky vyššie uvedené sa vzťahuje na prípad, keď obmedzovací systém (1.2) obsahuje rovnosť, pretože akúkoľvek rovnosť

môže byť reprezentovaný ako systém dvoch nerovností (pozri obr.2.1)

CC na pevnej hodnote určuje priamku v rovine. Zmena hodnôt L, dostaneme rodinu paralelných priamych, nazvaných Úroveň riadkov.

Je to spôsobené tým, že zmena hodnoty L bude mať len zmenu len dĺžku segmentu odrezaného na úrovni čiary na osi (počiatočná ordinácia), a rohový koeficient rovného bude zostať trvalý (pozri CRIS.2.1 ). Preto bude stačiť, že bude stačiť na vytvorenie jednej z úrovne riadkov, svojvoľne výberom hodnoty L.

Vektor so súradnicami z koeficientov CF s a kolmé na každú z riadkov na úrovni (pozri obr.2.1). Smer vektora sa zhoduje so smerom vzostupný Cf, čo je dôležitým bodom Riešiť problémy. Smer zostupný CF je oproti smeru vektora.

Podstata grafickej metódy je nasledovná. V smere (proti smeru) vektora v ODR, optimálny bod hľadá. Optimálna je bod, cez ktorý prechádza úroveň úrovne zodpovedajúcej najväčšej (najmenšej) funkcii funkcie. Optimálne riešenie je vždy na hranici ADR, napríklad v poslednom vrchole z polygónu ADR, cez ktorý cieľová rovná čiara prejde, alebo na celej svojej strane.

Pri hľadaní optimálnych riešení lineárnych problémov programovania sú možné nasledujúce situácie: Existuje jediné riešenie problému; Existuje nekonečná sada riešení (alternatívny optim); Cf nie je obmedzený; Plocha prípustných riešení je jediným bodom; Úloha nemá žiadne riešenia.

Obrázok 2.1 Geometrická interpretácia obmedzení a problémov s CF.

Metódy riešenia problémov s grafickou metódou LP.

I. V obmedzeniach problému (1.2) nahradia príznaky nerovnosti známkami presných rovností a budujú vhodné priame.

II. Hľadanie a trasúci polovičné dosky umožnené každej z problémov obmedzení nerovnosti (1.2). Na to je potrebné nahradiť osobitnú nerovnosť koordinácie akéhokoľvek bodu [napríklad (0; 0)] a skontrolovať pravdu získanej nerovnosti.

Aknerovnosť je pravdivá

to Je potrebné oholiť polovičnú rovinu obsahujúcu tento bod;

inak (Falošná nerovnováha) je potrebné otrasiť polovičnú rovinu, ktorá neobsahuje tento bod.

Odvtedy a musia byť negatívne, potom ich platné hodnoty Vždy byť nad osou a vpravo od osi, t.j. V kvadrante I-M.

Obmedzenia rovnosti sú povolené len týmito bodmi, ktoré ležia na príslušnom riadku. Preto je potrebné vyčleniť takéto priame.

III. Určite ADR ako súčasť roviny patriaceho do všetkých povolených oblastí súčasne a zvýraznite ho. V neprítomnosti ADR má úloha žiadne riešenia.

IV. Ak ADR nie je prázdny súbor, potom musíte vybudovať cieľovú priamu, t.j. Ktorýkoľvek z úrovňových riadkov (kde L je ľubovoľné číslo, napríklad viacnásobné a, t.j. pohodlné pre osady). Metóda výstavby je podobná konštrukcii priamych obmedzení.

V. Zostavte vektor, ktorý začína v bode (0, 0) a končí v bode. Ak je cieľ priamy a vektor postavený správne, budú kolmý.

Vi. Pri vyhľadávaní maxima by sa mal CF presunúť do cieľového priameho v smere Vektor, pri hľadaní minimálneho CF - proti smerom Vektor. Ten v priebehu pohybu bude horná časť ODR bod maximálneho alebo minimálneho porovce. Ak takýto bod (body) neexistuje, potom môžeme uzavrieť neobmedzený TSC v súbore plánov zhora (pri hľadaní maxima) alebo nižšie (pri hľadaní minima).

VII. Určite súradnice MAX (MIN) CC BODU a vypočítajte hodnotu CF. Na výpočet súradníc optimálneho bodu je potrebné vyriešiť systém rovníc priamych, na priesečníku, ktorého sa nachádza.