od Istien » 18. 2. 2009 08:46
1) V rovině je dán bod K=(6,4) a polyedr s krajními body (0,1), (1,0), (5,0), (8,2), (6,0). Najděte nějakou nadrovinu, která ostře odděluje bod K od polyedru P, a vyjádřete ji analyticky.
2)b_i >= 0, A_ij >= 0 pro všechna i = 1,...,m, j= 1,...,n. Dále víme, že matice A nemá žádný sloupec nulový. Dokažte, že pak úloha max {cx: Ax <= b, x >= 0) má optimální řešení pro všechna c z R^n.
3) Napište duální úlohu k úloze:
min Suma (j = 1,...,n) c_j * x_j
podm. Suma (j = 1,...,n) a_ij * x_j = b_i pro všechna i = 1,...,m
alfa_j <= x_j <= beta_j pro všechna j = 1,...,n
kde a_ij, b_i, alfa_j, beta_j jsou z R a alfa_j < beta_j pro všecha i,j
4) Pomocí LPO najděte optimální řešení úlohy
min x + y
podm. x^(-2) + y^(-2) <= a^(-2)
x >= epsilon, y >= epsilon
pro parametry platí a > 0, epsilon > 0
Poznámky:
1) Tohle si stačí nakreslit a pak analyticky vyjádřit tu přímku, která odděluje K od P.
2) Je potřeba si uvědomit, že úloha má alespoň jedno přípustné řešení (x = 0). A pak nějak ukázat, že množina {Ax <= b, x >= 0) je uzavřená a omezená. Nevím přesně jak, ale to že A má všechny sloupce nenulové je důležité k té omezenosti. Jiný možný způsob řešení by měl být přes duální úlohu.
3) Běžný postup. Stačí si uvědomit, že "alfa_j <= x_j <= beta_j pro všechna j = 1,...,n" je 2n nerovností, které je třeba zapsat do tabulky a x_j se položí normálně elementem R.
4) Běžný postup. Vyjde tuším [x,y] = [max(a*2^(1/2), epsilon), max(a*2^(1/2), epsilon)].
1) V rovině je dán bod K=(6,4) a polyedr s krajními body (0,1), (1,0), (5,0), (8,2), (6,0). Najděte nějakou nadrovinu, která ostře odděluje bod K od polyedru P, a vyjádřete ji analyticky.
2)b_i >= 0, A_ij >= 0 pro všechna i = 1,...,m, j= 1,...,n. Dále víme, že matice A nemá žádný sloupec nulový. Dokažte, že pak úloha max {cx: Ax <= b, x >= 0) má optimální řešení pro všechna c z R^n.
3) Napište duální úlohu k úloze:
min Suma (j = 1,...,n) c_j * x_j
podm. Suma (j = 1,...,n) a_ij * x_j = b_i pro všechna i = 1,...,m
alfa_j <= x_j <= beta_j pro všechna j = 1,...,n
kde a_ij, b_i, alfa_j, beta_j jsou z R a alfa_j < beta_j pro všecha i,j
4) Pomocí LPO najděte optimální řešení úlohy
min x + y
podm. x^(-2) + y^(-2) <= a^(-2)
x >= epsilon, y >= epsilon
pro parametry platí a > 0, epsilon > 0
Poznámky:
1) Tohle si stačí nakreslit a pak analyticky vyjádřit tu přímku, která odděluje K od P.
2) Je potřeba si uvědomit, že úloha má alespoň jedno přípustné řešení (x = 0). A pak nějak ukázat, že množina {Ax <= b, x >= 0) je uzavřená a omezená. Nevím přesně jak, ale to že A má všechny sloupce nenulové je důležité k té omezenosti. Jiný možný způsob řešení by měl být přes duální úlohu.
3) Běžný postup. Stačí si uvědomit, že "alfa_j <= x_j <= beta_j pro všechna j = 1,...,n" je 2n nerovností, které je třeba zapsat do tabulky a x_j se položí normálně elementem R.
4) Běžný postup. Vyjde tuším [x,y] = [max(a*2^(1/2), epsilon), max(a*2^(1/2), epsilon)].