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+opt@kam.mff.cuni.cz

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 (10 bodov)

Nájdite optimum: 
	min 122x + 143y
za podmienok:
         x ≥ -10
         y ≤  10
  3x +  2y ≤  10
 12x + 14y ≥ -12.5
  2x +  3y ≥   3
  5x -  6y ≥-100

Príklad 2 (15 bodov)

Vyberte si tu jednu z variánt, ktorú chcete riešiť.

Prvá varianta

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.

Druhá varianta

Nájdite riešenie lineárnej relaxácie TSP pre graf G. Vstupný súbor má na každom riadku definovanú jednu hranu: prvé dve čísla zodpovedajú vrcholom hrany a tretie jej dĺžke. Stačí spočítať relaxáciu so štandardnými podmienkami pre hrany (teda s polynomiálnym počtom nerovníc), nemusíte uvažovať podmienky pre všetky podmnožiny (viď príklad 1 z cvičenia 3).

V tomto prípade je graf trochu väčší, takže asi bude lepšie, ak váš program bude vedieť súbor s grafom sám načítať.