Praktická domáca úloha 1

Vyriešte nasledujúce úlohy pomocou niektorého software na riešenie úloh lineárneho programovania. Zoznam software nájdete na tejto stránke: ./sw.html. Riešenia posielajte na adresu elias@kam.mff.cuni.cz ideálne ako odpoveď na email so zadaním zo SISu.

Zdrojáky posielajte s krátkym popisom, ako sa to kompiluje. V prípade riešení v programoch Mathematica, Matlab a Maple posielajte worksheety.

Príklad 1 (5 bodov)

Nájdite optimum: 
	max 2x - y
za podmienok:
	x ≥  2
	x ≤  9
   x + 2y ≤  10
x - 1/3 y ≥  10
	y ≥ -10
    x + y ≥  2

Príklad 2 (5 bodov)

Sformulujte lineárnu relaxáciu pre vrcholové pokrytie grafu G a nájdite optimum (tejto relaxácie) pomocou vybraného software. Sú 4 varianty zadania. Úlohu budete riešiť pre graf Gi, kde 
i := UKČO mod 4
UKČO je vaše číslo osoby na UK, ktoré máte napísané na ISICu/univerzitnom preukaze pod fotografiou. Grafy sú zadané vo forme zoznamu hrán. Každé číslo je vrchol a na každom riadku v súbore sú dva vrcholy, ktoré tvoria hranu. Grafy nájdete v týchto súboroch:

G0 G1 G2 G3

Program stačí vytvoriť pre zadaný graf. Teda ten graf/LP tam môže byť "zadrôtovaný", nemusí si ho vedieť brať zo vstupu. Ale možno bude jednoduchšie, ak ho bude vedieť zo súboru rovno načítať. Závisí to od toho, aký software si vyberiete.