Rozdíly

Zde můžete vidět rozdíly mezi vybranou verzí a aktuální verzí dané stránky.

--- courses:a4b35ko:test3 [2012/03/06 11:20]
navara
+++ courses:a4b35ko:test3 [2025/01/03 18:28] (aktuální)
@@ Řádek 1: / Řádek 1: @@
 ====== Test 3 ======
-=== Test 2011 ===
+===== Test 2015 =====
+==== Varianta 1 ====
+Jednalo se o podobné zadání jako varianta B z roku 2012. Navíc byla zadána matice
 <code>
-A
+M = 1 0 1 0
-n(5) dam na sachovnici. (n queens problem)
+1 0 0
-zjednodusena uloha n vezi, z te pak dodelat uhlopricky pro damy.
+0 1 0
-vychazelo se z ukolu na sudoku
+0 0 1
 </code>
+Kde 1 značí: Úloha i musí být vykonávána na stejném procesoru jako úloha j, i je řádkový a j je sloupcový index.
+Řešení:
+Test vstupních podmínek. Matice M musí být symetrická, např. pokud úloha 1 musí být vykonávána na stejném procesoru jako úloha 3, tak úloha 3 musí být vykonávána na stejném procesoru jako úloha 1. Na diagonále musí být 1, samostatná úloha se vykonává na stejném (jednom) procesoru. Preempce nebyla povolena.
+Vektor proměnných obsahuje xij - x11 x21 x31 x41 x12 x22 x32 x42 Cmax, kdy i je číslo úlohy, j je procesor, více viz popis úlohy níže.
+Matice M nám říká, že úloha 1 má běžet na stejném procesoru jako úloha 3. Tedy nemůže se stát, že pokud je úloha 1 rozvržena na procesor 1 (x11), tak bude úloha 3 rozvržena na procesor 2 (x32). Součet těchto proměnných musí být 1. Analogicky, nemůže se stát, že pokud je úloha 1 rozvržena na procesor 2 (x12), tak bude úloha 3 rozvržena na procesor 1 (x31). Součet těchto proměnných musí být opět 1.
+Matici A tedy rozšíříme o řádky pro omezení z matice M:
 <code>
-B
+ A = [p , 0 0 0 0, -1;
-problem batohu pomoci ILP
+0 0 0, p , -1;
-nejaka omezeni, ktere veci nejdou vzit spolu (prosim doplnte)
+0 0 0, 1 0 0 0,0;
-</code>
+1 0 0, 0 1 0 0,0;
+0 1 0, 0 0 1 0,0;
+0 0 1, 0 0 0 1,0;
+     %pridané řádky pro matici M
+0 0 0, 0 0 1 0,0;
+0 1 0, 1 0 0 0,0];
+</code>
+Je třeba i upravit vektor b, rozšířit ho o dvě jedničky
+<code>b = [0; 0; ones(n,1); 1;1];</code>
+a porovnávací podmínky
+<code>ctype = ['L'; 'L'; repmat('E',n,1);'E';'E'];</code>
-=== Test 2010 ===
+Pokud bych něco opomenul, pište do diskuze, případně upravte s poznámkou.
-{{:courses:a4b35ko:a4m35ko-test3-2010.jpg|}}
-~~DISCUSSION~~
+P.S. Proč mne řešení napadnou vždy až v klidu při kávičce a příjemné hudbě, místo při psaní testu :-).
+===== Test 2014 =====
+{{:courses:a4b35ko:img_20150504_200112.jpg?200|}}
+===== Test 2013 =====
+{{:courses:a4b35ko:a4m35ko_test_2013.jpg?200|}}
+===== Test 2012 =====
+==== A ====
+== zadani ==
+{{:courses:a4b35ko:wp_000161.jpg?200|}}
+== reseni ==
+Par hintu na prvni pokuk:
+  * matice A bude obsahovat tenhle vzor: ''Apartial = [ 1 0 0 0 0 0 0 1; 1 1 0 0 0 0 0 0; 0 1 1 0 0 0 0 0; ... ];'' kazde cislo v radku je jedna 3hodinovka, vyznam je stejny jako v domacim ukolu s telefonim operatorem
+  * take se nam tam vyskytne ''-[bmin, bmax]'; ''
+  * tipuju to na neco jako minimalizace pres vsechna ''x'' (tedy: ''c=ones(length(A),1)'') pro matici ''A = [ Apartial -bmin'; -Apartial bmax'];''
+  * vektor x obsahuje pocet sluzeb zacinajicich v te ktere hodine
+Tim konci myslenkove pochody a prichazi vecerni odpocinek =D Je to jen tip reseni na prvni pohled. Melo by se stacit podivat na domacak s Telefonnim operatorem a brat jednu 3hodinovku jako 1h.
+==== B ====
+== zadani ==
+Jednalo se o planovaci ulohu ctyr uloh na dvou procesorech.
+  n = 4;          % pocet ulon (delka nasledujiciho vektoru)
+  p = [11 7 4 8]; % doba trvani jednotlivych uloh na procesorech
+  m = 2;          % pocet procesoru
+Meli jsme vytvorit plan pomoci ILP (prakticky 3. domaci uloha). Jednotlive parametry pro funkci ''ilinprog'' bylo mozne zapsat primo a nebylo potreba je generovat dynamicky podle velikosti vstupnich parametru.
+Promenne ILP jsou
+  * <latex>x_{i,j} \in \{0,1\}, \quad i \in \left<1,n\right> , j \in \left<1,m\right></latex> - tedy mame m*n booleovskych promennych, ktere znaci, ze **uloha i se vykonava na procesoru j**
+  * <latex>Cmax</latex> - doba trvani cele prace (soucet dob trvani uloh na nejvytizenejsim procesoru), tuto promennou minimalizujeme.
+Omezujici podminky linearniho programu jsou:
+<latex> min \quad Cmax </latex>
+<latex> z.p.: </latex>
+<latex>\sum_{i=1}^{n} \left( p_{i} * x_{i,j} \right) \le Cmax \quad \forall j \in \left<1,m\right></latex>
+<latex>\sum_{j=1}^{m} \left( x_{i,j} \right) = 1 \quad \forall i \in \left<1,n\right></latex>
+Prvni podminka rika, ze Cmax je vetsi nez soucet trvani uloh na kteremkoli procesoru. Druha podminka rika, ze se kazda uloha vykonava prave na jednom procesoru.
+Soucasti reseni je vypis jake ulohy se kde maji provadet, jaky je vysledny vektor a hodnota kriteria a popis toho co je ve vektory ''vartype'' jako soucast komentare v kodu.
+== reseni ==
+Posilam sem komplet reseni i s vysvetlivkami. Uz je po testu, tak verim, ze nikdo nebude mit moznost ho zneuzit. **Pokud budete chtit tenhle kod dale sirit, tak prosim jedine pres link na tuhle dokuwiki**.
+  clear all;
+  n = 4;          % pocet uloh
+  p = [11 5 3 8]; % doby trvani uloh
+  m = 2;          % pocet procesoru
+  cmax = 0;       % vysledna delka rozvrhu (tu minimalizujeme)
+  % snese = minimalisation (see help ilinprog)
+  sense = 1;
+  % Prvni dva radky jsou soucet uloh na prvnim a druhem procesoru
+  % Lower-or-equal CMAX
+  % Nasledujicich n radku udava, ze kazda uloha se ma vykonat prave jednou na
+  % jednom z procesoru. Soucet jednicek pro kazdou ulohu bude Equal jedne.
+  ctype = ['L'; 'L'; repmat('E',n,1)];
+  % creation of A-matrix
+  A = [   p   , 0 0 0 0, -1; ...
+0 0 0,    p   , -1; ...
+0 0 0, 1 0 0 0,  0; ...
+1 0 0, 0 1 0 0,  0; ...
+0 1 0, 0 0 1 0,  0; ...
+0 0 1, 0 0 0 1,  0];
+  % rozdil na prvnich dvou radcich musi byt nula
+  % soucet na zbylych radcich se rovna jedne
+  b = [0; 0; ones(n,1)];
+  % Prvnich M*N cisel vektoru b jsou boolean hodnoty pro tasky x(1:n) na
+  % procesorech 1:m. Proto jsou celociselne. Matice A se na prvni pohled
+  % nejevi totalne unimodularni, proto zde nelze pouzit realne promenne.
+  %vartype = [repmat('I', m*n+1, 1)];
+  %
+  % Predpokladam, ze aby se dala pouzit simplexova metoda, nebo jiny
+  % algoritmus pro necelociselne LP, je potreba aby vsechny promenne byly
+  % realne, ne celociselne. Nasledujici radek proto parvdepodobne nicemu
+  % nepomuze. Nicmene, kdybychom povolili necelociselne doby trvani
+  % jednotlivych uloh, bylo by potreba nastavit typy prave takhle:
+  vartype = [repmat('I', m*n, 1); 'C'];
+  % minimalizujeme pouze cmax
+  c = [zeros(m*n,1); 1];
+  % cmax bude maximalne soucet vsech casu, ostatni promenne budou maximalne
+  % jedna
+  lb = [zeros(m*n, 1);   0   ]; % dolni meze
+  ub = [ones(m*n, 1) ; sum(p)]; % horni meze
+  %Parametry optimalizace
+  schoptions=schoptionsset('ilpSolver','glpk','solverVerbosity',2);
+  %spusteni optimalizace z TORSCHE
+  [xmin,fmin,status,extra] = ...
+      ilinprog(schoptions,sense,c,A,b,ctype,lb,ub,vartype);
+  fprintf('vektor kriteria: ');
+  xmin'
+  fprintf('hodnota kriteria (doba trvani): %d\n', fmin);
+  i=(1:n);
+  fprintf(strcat('# na prvnim procesoru pobezi ulohy: ',repmat(' %d',1,sum(xmin(1:n))), '\n'),  i(boolean(xmin(1:n)')));
+  fprintf(strcat('# na druhem procesoru pobezi ulohy: ',repmat(' %d',1,sum(xmin(n+1:n+n))), '\n'),  i(boolean(xmin(n+1:n+n)')));
+===== Test 2011 =====
+==== A ====
+  n(5) dam na sachovnici. (n queens problem)
+  zjednodusena uloha n vezi, z te pak dodelat uhlopricky pro damy.
+  vychazelo se z ukolu na sudoku
+==== B ====
+  problem batohu pomoci ILP
+  nejaka omezeni, ktere veci nejdou vzit spolu (prosim doplnte)
+===== Test 2010 =====
+{{:courses:a4b35ko:a4m35ko-test3-2010.jpg?500|}}
+~~DISCUSSION~~

courses/a4b35ko/test3.1331029236.txt.gz · Poslední úprava: 2025/01/03 18:24 (upraveno mimo DokuWiki)

Nahoru