Soustavy lineárních rovnic

11. listopadu 2007 v 12:31 |  MATEMATIKA I-IV

2 Soustavy lineárních NErovnic

2. 1 Konvexní množiny
Definice. Lineární kombinací vektorů nazýváme
vektor
.
Jestliže navíc 1. ki ≥ 0
2.
hovoříme o konvexní (lineární) kombinaci.
Poznámka.
u2 U
P u1
U = [u1,u2]
Vektor a bod U jsou
vyjádřeny toutéž uspořádanou
dvojicí (u1, u2).
Obě interpretace bod ↔ vektor uspořádané dvojice (u1, u2) jsou ekvivalentní.
Věta. Libovolný bod X úsečky AB je konvexní kombinací
bodů A, B.
Platí totiž, že , kde …
Např. , nebo , ……
Definice. Množina bodů se nazývá konvexní, jestliže s libovolný
mi body A, B obsahuje také všechny body úsečky AB.
ANO
NE
Věta. Je-li M konvexní množina, pak každá konvexní kombi-
nace libovolných bodů z M se nachází v M.
Definice. Bod U konvexní množiny M se nazývá vrchol (krajní
bod), když neleží uvnitř žádné úsečky patřící do M.
Vrchol tedy nejde vyjádřit jako konvexní kombinace nějakých jiných bodů U1, U2 є M,
tj. U ≠ k1U1 + k2U2 , kde U, U1, U2 є M,
k1 + k2 = 1
k1, k2 > 0 ↔ (U ≠ U1, U ≠ U2)
Př. Krajními body trojúhelníka jsou jeho vrcholy.
Krajními body kruhu jsou všechny body hraniční kružnice.
Konvexní množina je ohraničená, jestliže neobsahuje žádnou polopřímku. Je neohraničená, když alespoň jednu polopřímku obsahuje.
Definice. Ohraničená konvexní množina s konečným počtem
vrcholů se nazývá konvexní polyedr.
Je-li neohraničená mluvíme o konvexní mnohohranné neomezené množině.
2. 2 Soustava lineárních nerovnic
Soustavou m lineárních rovnic o 2 neznámých rozumíme soustavu
a11x1 + a12x2 ≤ b1
a21x1 + a22x2 ≤ b2
. ai1x1 + ai2x2 ≤ bi
. i = 1, 2, …, r
.
ar1 x1 + ar2 x2 ≤ br
ar+1,1 x1 + ar+1,2 x2 ≥ br+1
ar+2,1 x1 + ar+2,2 x2 ≥ br+2
.
. ak1x1 + ak2x2 ≥ bk
.
. k = r+1, r+2, …, m
.
am1 x1 + am2 x2 ≥ bm
x1, x2 ³ 0 ….. tzv. podmínky nezápornosti
(v ekonomických interpretacích)
2. 3 Grafické řešení soustavy lineárních nerovnic
Přímka a1x1 + a2x2 = b rozdělí rovinu na dvě poloroviny. Souřadnice bodů ležících v jedné z nich ( včetně přímky) vyhovují vztahu a1x1 + a2x2 ≤ b. Souřadnice bodů druhé poloroviny ( bez přímky) vyhovují vztahu a1x1 + a2x2 > b.
Řešení každé nerovnice ai1x1 + ai2x2 ≤ bi tedy odpovídá jedna polorovina.
Analogicky pro nerovnice ak1x1 + ak2x2 ≥ bk.
Společným řešením všech nerovnic je průnik příslušných polorovin. Ta jeho část, která splňuje podmínky nezápornosti (x1, x2 ³ 0) se nazývá množina přípustných řešení.
Poznámka. Pro kreslení obrázku je vhodné přímku
a1x1 + a2x2 = b upravit na tzv. úsekový tvar ,
kde p je "úsek" na ose x1 a q "úsek" na ose x2.
x2
q
x1
p
2. 4 Numerické řešení soustavy lineárních nerovnic
Nerovnice převedeme pomocí tzv. doplňkových proměnných
xi ≥ 0 na rovnice
a1x1 + a2x2 ba1x1 + a2x2+ x3 = b
Vzniklou soustavu rovnic řešíme vzhledem ke všem bázím, které obsahují x1, x2. Každé z nich odpovídá jeden vrchol množiny řešení dané soustavy nerovnic. Jeho souřadnice dostaneme dosazením 0 za doplňkové proměnné. Vzhledem k podmínkám nezápornosti (x1, x2 ³ 0) a vzhledem k podmínkám pro doplňkové proměnné (xi ≥ 0) vyhovují pouze nezáporná řešení.
Př. 2x1 + x2 ≥ 600
2x1 + 4 x2 ≥ 1200
4 x2 ≥ 400
x1, x2 ≥ 0
Př. Podnik vyrábí dva výrobky A, B, které se zpracovávají ve
třech dílnách D1, D2, D3.
Dílny
Pracnost výroby v hodinách
Požadavek na minimální využití dílny
v hodinách
A
B
D1
2
1
600
D2
2
4
1200
D3
0
4
400
Náklady v Kč
50
60
Stanovte výrobní program tak, aby náklady byly minimální.
Označme x1 počet výrobků A, x2 počet výrobků B.
Nejdříve sestrojíme množinu přípustných řešení.
Optimální řešení najdeme pomocí grafického vyjádření tzv. účelové funkce z = 50 x1 + 60 x2 .
Přímku 50 x1 + 60 x2 = k, kde k je libovolná konstanta, posuneme rovnoběžně tak, aby procházela alespoň jedním bodem množiny přípustných řešení a aby zároveň její vzdálenost od počátku byla co nejmenší (při minimalizační úloze) nebo co největší (při maximalizační úloze).
 

Buď první, kdo ohodnotí tento článek.

Nový komentář

Přihlásit se
  Ještě nemáte vlastní web? Můžete si jej zdarma založit na Blog.cz.
 

Aktuální články

Reklama