Notice: Undefined index: mode in /home/misc/mst/public_html/common.php on line 63 Notice: Undefined index: mode in /home/misc/mst/public_html/common.php on line 65 Notice: Undefined index: mode in /home/misc/mst/public_html/common.php on line 67 Notice: Undefined index: mode in /home/misc/mst/public_html/common.php on line 69 Notice: Undefined variable: base in /home/misc/mst/public_html/lecture.php on line 36 Optymalizacja I – 12. Metoda podziału i ograniczeń – MIM UW

Zagadnienia

12. Metoda podziału i ograniczeń

12.1. Metoda podziału i ograniczeń

Badamy problem optymalizacji

P: Max\ \{\, f(x)\ |\  x\in Q(P)\}

W przypadku gdy obszar dopuszczalny Q(P) niewygodnie opisany, np. wymagamy by niektóre współrzędne punktów były liczbami całkowitymi, jedną z głównych metod rozwiązywania jest metoda podziału i ograniczeń zwana też metodą rozgałęzień i zamykania. Używać będziemy też skróconej nazwy angielskiej ”B\& B” ( Branch and Bound ). Nawet tak proste programy jak Solver w arkuszu kalkulacyjnym Excel są reklamowane jako używające tej metody. Podstawowymi pojęciami są:

Definicja 12.1

Podziałem problemu P nazywamy ciąg podproblemów P_{1},P_{2},...,P_{t}, postaci P_{i}:\  Max\ \{\, f(x)\ |\  x\in Q(P_{i})\}, gdzie obszar dopuszczalny Q(P) jest rozłączną sumą obszarów Q(P_{i}).

Podsumowując, zamiast problemu P:\  Max\ \{\, f(x)\ |\  x\in Q\} rozwiązujemy ciąg problemów P_{1},P_{2},...,P_{t}, postaci P_{i}:\  Max\ \{\, f(x)\ |\  x\in Q(P_{i})\}, gdzie obszar dopuszczalny

Q(P)\subset\bigcup _{{\, i=1}}^{{\, t}}\  Q(P_{i}).

Rozwiązanie problemu polega na rozwiązaniu wszystkich podproblemów. Operacje te nazywamy zamykaniem podproblemu. Posługujemy się następującymi kryteriami:

Kryteria zamykania podproblemów.

KZ1 Jeżeli pewna relaksacja RP_{i} problemu P_{i} jest sprzeczna, Q(RP_{i})=\emptyset, to problem P_{i} uznajemy za zamknięty.

KZ2 Jeżeli pewna relaksacja RP_{i} problemu P_{i} ma rozwiązanie dopuszczalne p, p\in Q(P), to problem P_{i} uznajemy za zamknięty.

KZ3 Jeżeli znamy oszacowanie dolne w* zadania P, np. jest wartością funkcji celu w pewnym punkcie dopuszczalnym i pewna relaksacja RP_{i} problemu P_{i} ma rozwiązanie o mniejszej wartości funkcji celu, to problem P_{i} uznajemy za zamknięty.

Algorytm metody B&B.
Dana jest lista kandydacka L zawierająca wszystkie niezamknięte
problemy. (L może np. zawierać tylko jeden problem początkowy).
Lista L będzie się rozszerzać przy dokonywaniu podziału i skracać
przy zamykaniu problemu. Celem jest osiągniecie L=\emptyset .
Dodatkowo mamy sukcesor \widehat{x}. Jest nim zbiór zawierający element ze zbioru
dopuszczalnego i wartość funkcji na tym elemencie. W chwili
początkowej sukcesor może być pusty.
\widehat{x}=\left\{\left(w,f(w)\right)\right\} lub
\widehat{x}=\emptyset
1)Test stopu:
 Jeżeli L=\emptyset to stop,
 jeśli \widehat{x}=\left\{\left(w,f(w)\right)\right\}\neq\emptyset to w jest punktem optymalnym, a f(w) jest rozwiązaniem,
jeśli \widehat{x}=\emptyset to zadanie jest sprzeczne.
2)  Wybór kandydata z listy:
 Wybieramy i usuwamy z listy L podproblem P_{{k}}.
Ustalamy jego relaksację RPk.
3)  Rozwiązujemy RPk i testujemy kryteria zamykania:
a) Jeżeli jest spełnione kryterium KZ2 i nie jest spełnione
KZ3 to zmieniamy sukcesor w:w_{{k}}f:f_{{k}} GO TO 1)
 b) Jeżeli spełnione kryteria KZ1 lub KZ3 GO TO 1)
4) Jeżeli żadne kryterium zamykania nie jest spełnione to decydujemy, czy zacieśniamy relaksację
czy dokonujemy podziału:
Jeżeli zacieśniamy relaksację to GO TO 3)
Jeżeli dokonujemy podziału to powstałe podproblemy dodajemy do listy kandydackiej L i GO TO 2).

Zobaczmy to na następującym przykładzie. Stosować w nim będziemy tak zwane podziały Dakina [5]. W sytuacji gdy otrzymaliśmy niedopuszczalne rozwiązanie p relaksacji RP, w którym i-ta współrzędna p równa p_{i} nie jest liczbą całkowitą to problem dzielimy na dwa. Tak zwany ”lewy” przez dodanie ograniczenia x_{i}\leq\lfloor p_{i}\rfloor i tak zwany ”prawy” przez dodanie ograniczenia x_{i}\geq\lceil p_{i}\rceil=\lfloor p_{i}\rfloor+1.

Przykład 12.1

Rozwiązujemy zadanie P.

Max\quad\qquad x_{{0}}=-9x_{1}-6x_{2}-2x_{3}

\qquad-\frac{5}{2}x_{1}-\frac{3}{2}x_{2}+\frac{1}{2}x_{3}+x_{4}=\frac{5}{2}

\qquad\qquad 4x_{1}+3x_{2}+2x_{3}+x_{5}=3

\qquad\qquad\qquad-2x_{3}+x_{6}=4

\qquad\qquad\forall _{i}\  x_{{i}}\geq 0,\  x_{{i}}\in Z

Jest to zadanie typu:

P:\qquad Max\quad x_{0}=c\bullet x

x\in Q(P).

1) Lista L zawiera tylko problem początkowy P. Sukcesor jest pusty.

2) Budujemy pierwszą relaksację RP opuszczając warunki \forall _{i}\  x_{{i}}\in Z.

Teraz zbiór dopuszczalny pierwszej relaksacji jest wielościanem.

3) Rozwiązujemy RP metodą sympleks.

\qquad\left[\begin{array}[]{c|rrrrrr|c}x_{{0}}&x_{{1}}&x_{{2}}&x_{{3}}&x_{{4}}&x_{{5}}&x_{{6}}&ww\\
1&9&6&2&0&0&0&0\\
\hline 0&-\frac{5}{2}&-\frac{3}{2}&\frac{1}{2}&1&0&0&\frac{5}{2}\\
0&4&3&2&0&1&0&3\\
0&0&0&-2&0&0&1&4\end{array}\right]

Otrzymana macierz jest tablicą sympleks pierwotnie i dualnie dopuszczalną więc opisuje wierzchołek optymalny relaksacji w_{1}=(0,0,0,\frac{5}{2},3,4). Nie jest on dopuszczalny dla zadania P zatem dokonujemy podziału względem zmiennej x_{4}.

4) Wydzielamy ze zbioru Q(RP) 2 podzbiory, tak zwany ”lewy” i ”prawy” przez dodanie ograniczeń:

\qquad x_{{4}}\leq\left\lfloor\frac{5}{2}\right\rfloor=2\quad lub \qquad x_{4}\geq\left\lfloor\frac{5}{2}\right\rfloor+1=3 odpowiednio

Oczywiście Q(P)\subset Q(RP_{L})\cup Q(RP_{P}) gdyż wyrzuciliśmy tylko punkty u o współrzędnej x_{3} z przedziału otwartego (2,3). Idziemy do 1).

1) Lista L zawiera podproblemy ”lewy” i ”prawy”. Sukcesor jest pusty.

2) Wybieramy problem ”lewy” i ustalamy relaksację przez odrzucenie warunków \forall _{i}\  x_{{i}}\in Z.

3) Rozwiązujemy relaksację problemu ”lewego”.

RP_{L} Dodajemy ograniczenie x_{4}\leq 2\Leftrightarrow x_{4}+x_{7}=2

Warunek x_{4}+x_{7}=2 zastępujemy \frac{5}{2}x_{1}+\frac{3}{2}x_{2}-\frac{5}{2}x_{3}+x_{7}=-\frac{1}{2}, który powstaje przez odjęcie pierwszego równania. Zatem ”lewa” relaksacja ma postać:

Max\quad\qquad x_{{0}}=-9x_{1}-6x_{2}-2x_{3}

\qquad-\frac{5}{2}x_{1}-\frac{3}{2}x_{2}+\frac{1}{2}x_{3}+x_{4}=\frac{5}{2}

\qquad\qquad 4x_{1}+3x_{2}+2x_{3}+x_{5}=3

\qquad\qquad\qquad-2x_{3}+x_{6}=4

\qquad\qquad\frac{5}{2}x_{1}+\frac{3}{2}x_{2}-\frac{5}{2}x_{3}+x_{7}=-\frac{1}{2}

\qquad\forall _{i}x_{{i}}\geq 0

Budujemy tablicę sympleks. Jest ona dualnie dopuszczalna więc stosujemy dualną metodę sympleks.

\left[\begin{array}[]{crrrrrr|r}9&6&2&0&0&0&0&0\\
\hline-\frac{5}{2}&-\frac{3}{2}&\frac{1}{2}&1&0&0&0&\frac{5}{2}\\
4&3&2&0&1&0&0&3\\
0&0&-2&0&0&1&0&4\\
\frac{5}{2}&\frac{3}{2}&(-\frac{1}{2})&0&0&0&1&-\frac{1}{2}\end{array}\right]

Jedynym elementem nadającym się na centralny jest -\frac{1}{2}.

Po przekształceniach Gaussa - Jordana otrzymujemy:

\left[\begin{array}[]{crrrrrr|r}19&12&0&0&0&0&4&-2\\
\hline 0&0&0&1&0&0&1&2\\
14&9&0&0&1&0&4&1\\
-10&-6&0&0&0&1&-4&6\\
-5&-3&1&0&0&0&-2&1\end{array}\right]

RP_{L} ma rozwiązanie dopuszczalne p_{1}=(0,0,1,2,1,6,0) x_{{0}}=-2. Zapamiętujemy to rozwiązanie w sukcesorze.

Zamknęliśmy problem ”lewy” stosując kryterium KZ2.

1) Nasza lista kandydacka zawiera tylko problem ”prawy”. Sukcesor zawiera punkt p_{1} i wartość x_{{0}}=-2.

2) wybieramy problem ”prawy” RP_{P} i ustalamy relaksację przez odrzucenie warunków \forall _{i}\  x_{{i}}\in Z.

3) Rozwiązujemy relaksację problemu ”prawego”. .

Dodajemy ograniczenie   x_{4}\geq\left\lfloor\frac{5}{2}\right\rfloor+1=3

x_{4}-x_{7}=3\Leftrightarrow-x_{4}+x_{7}=-3

Teraz po dodaniu do pierwszego równania dodanego ograniczenia otrzymujemy nowe:

-\frac{5}{2}x_{1}-\frac{3}{2}x_{2}+\frac{5}{2}x_{3}+x_{7}=-\frac{1}{2}

Zadanie ”prawe” zapisujemy w postaci tablicy sympleks:

\left[\begin{array}[]{rrrrrrr|r}9&6&2&0&0&0&0&0\\
\hline-\frac{5}{2}&-\frac{3}{2}&\frac{1}{2}&1&0&0&0&\frac{5}{2}\\
4&3&2&0&1&0&0&3\\
0&0&-2&0&0&1&0&4\\
(-\frac{5}{2})&-\frac{3}{2}&\frac{1}{2}&0&0&0&1&-\frac{1}{2}\end{array}\right]

i rozwiązujemy dualną metodą sympleks. Liczymy Min\left\{ 9/\frac{5}{2};5/\frac{3}{2}\right\}=\frac{18}{5} więc elementem centralnym jest -\frac{5}{2}.

Po przekształceniach Gaussa - Jordana otrzymujemy:

\left[\begin{array}[]{rrrrrrr|r}0&\frac{3}{5}&\frac{19}{5}&0&0&0&\frac{18}{5}&-\frac{9}{5}\\
\hline 0&0&0&1&0&0&-1&3\\
0&\frac{3}{5}&\frac{14}{5}&0&1&0&\frac{8}{5}&\frac{11}{5}\\
0&0&-2&0&0&1&0&4\\
1&\frac{3}{5}&-\frac{1}{5}&0&0&0&-\frac{2}{5}&\frac{1}{5}\end{array}\right]

Otrzymany wierzchołek optymalny p_{2}=(\frac{1}{5},0,0,3,\frac{11}{5},4,0) nie jest dopuszczalny więc problem dzielimy na nowe podproblemy względem zmiennej x_{5} i idziemy do 1).

1) Lista L zawiera podproblemy ”prawy,lewy”- P_{{PL}} i ”prawy,prawy”'- P_{{PP}}. Sukcesor zawiera punkt p_{1} i wartość x_{{0}}=-2.

2) Wybieramy problem P_{{PL}} i ustalamy relaksację przez odrzucenie warunków \forall _{i}\  x_{{i}}\in Z.

3) Rozwiązujemy relaksację problemu P_{{PL}}.

RP_{L} Dodajemy ograniczenie x_{5}\leq\left\lfloor\frac{11}{5}\right\rfloor=2\Leftrightarrow x_{4}+x_{8}=2.

Otrzymujemy zadanie opisane tablicą:

\left[\begin{array}[]{rrrrrrrr|r}0&\frac{3}{5}&\frac{19}{5}&0&0&0&\frac{18}{5}&0&-\frac{9}{5}\\
\hline 0&0&0&1&0&0&-1&0&3\\
0&\frac{3}{5}&\frac{14}{5}&0&1&0&\frac{8}{5}&0&\frac{11}{5}\\
0&0&-2&0&0&1&0&0&4\\
1&\frac{3}{5}&-\frac{1}{5}&0&0&0&-\frac{2}{5}&0&\frac{1}{5}\\
0&(-\frac{3}{5})&-\frac{14}{5}&0&0&0&-\frac{8}{5}&1&-\frac{1}{5}\end{array}\right]

i rozwiązujemy dualną metodą sympleks. Liczymy Min\left\{\frac{3}{5}/\frac{3}{5};\frac{19}{5}/\frac{14}{5};\frac{18}{5}/\frac{8}{5}\right\}=\frac{3}{5}/\frac{3}{5}=1 więc elementem centralnym jest -\frac{3}{5}.

Po przekształceniach Gaussa - Jordana otrzymujemy:

\left[\begin{array}[]{rrrrrrrr|r}0&0&1&0&0&0&2&1&-2\\
\hline 0&0&0&1&0&0&-1&0&3\\
0&0&0&0&1&0&0&1&2\\
0&0&-2&0&0&1&0&0&4\\
1&0&-3&0&0&0&-2&1&0\\
0&1&\frac{14}{3}&0&0&0&\frac{8}{3}&-\frac{5}{3}&\frac{1}{3}\end{array}\right]

Otrzymany wierzchołek optymalny p_{3}=(0,\frac{1}{3},0,3,2,4,0,0) nie jest dopuszczalny. Wartość funkcji celu w tym punkcie jest taka sama jak w sukcesorze. Ponadto nad kreską nie ma ”niebazowych” zer więc jest to jedyny punkt optymalny relaksacji. Oznacza to, że każdy punkt zadania P_{{PL}} ma wartość mniejszą niż sukcesor. Stosując kryterium KZ3 zamykamy problem. Idziemy do 1).

1) Lista L zawiera podproblem ”prawy,prawy”'- P_{{PP}}. Sukcesor zawiera punkt p_{1} i wartość x_{{0}}=-2.

2) Wybieramy problem P_{{PP}} i ustalamy relaksację przez odrzucenie warunków \forall _{i}\  x_{{i}}\in Z.

3) Rozwiązujemy relaksację problemu P_{{PP}}.

RP_{L} Dodajemy ograniczenie x_{5}\geq\left\lfloor\frac{11}{5}\right\rfloor+1=3\Leftrightarrow x_{4}-x_{8}=3.

Otrzymujemy zadanie opisane tablicą:

\left[\begin{array}[]{rrrrrrrr|r}0&\frac{3}{5}&\frac{19}{5}&0&0&0&\frac{18}{5}&0&-\frac{9}{5}\\
\hline 0&0&0&1&0&0&-1&0&3\\
0&\frac{3}{5}&\frac{14}{5}&0&1&0&\frac{8}{5}&0&\frac{11}{5}\\
0&0&-2&0&0&1&0&0&4\\
1&\frac{3}{5}&-\frac{1}{5}&0&0&0&-\frac{2}{5}&0&\frac{1}{5}\\
0&\frac{3}{5}&\frac{14}{5}&0&0&0&\frac{8}{5}&1&-\frac{4}{5}\end{array}\right]

Otrzymaliśmy sprzeczność bo ostanie równanie nie ma dodatnich rozwiązań. Zamykamy problem stosując kryterium KZ1. Idziemy do 1).

1) Lista L pusta. Sukcesor zawiera punkt p_{1} i wartość x_{{0}}=-2. Rozwiązanie jest zawarte w sukcesorze.

Uwaga 12.1

Metoda podziału Dakina w przypadku gdy po usunięciu warunków całkowitoliczbowych otrzymujemy ograniczony obszar dopuszczalny.

Uwaga 12.2

Metoda podziału Dakina jest skuteczna gdy tylko część zmiennych jest całkowitoliczbowa.

Metodą B\& B można rozwiązywać zadanie programowania liniowego z parametrem (pewne współczynniki nie są określone), na przykład zadania w których obszar dopuszczalny jest wielościanem ale funkcja celu jest wymierna.

np. Max\quad x_{{0}}=\frac{a_{{1}}x_{{1}}+a_{{2}}x_{{2}}+...+a_{{n}}x_{{n}}}{b_{{1}}x_{{1}}+b_{{2}}x_{{2}}+...+b_{{n}}x_{{n}}}

x\in Q

TS=\left[\begin{array}[]{c|c|c}-c_{{N}}&0&b_{{0}}\\
\hline N&I&b\end{array}\right]

Niech t=\sum _{{i=1}}^{n}\, b_{i}x_{i}\ i rozwiązujemy zadanie dopisując równanie t do tablicy.

\circ\qquad TS=\left[\begin{array}[]{c|c}\begin{array}[]{c|c}-c_{{N}}&0\\
\hline N&I\end{array}&\begin{array}[]{c}b_{{0}}\\
\hline b\end{array}\\
b_{{1}}x_{{1}}+b_{{2}}x_{{2}}+...+b_{{n}}x_{{n}}&t\end{array}\right]

przekształcenia polegają na wyborze elementu centralnego \underset{i,\alpha _{{ij}}>0}{Min}\left\{\frac{t_{{i}}}{\alpha _{{ij}}},\frac{t}{b_{{j}}}\right\}=min

i dzielimy na dwa podproblemy

1) \frac{t}{b_{{j}}}<min\rightarrow b_{{j}} - element centralny

2) \frac{t}{b_{{j}}}\geq min\rightarrow element centralny - jakiś z kolumny j

\qquad\widehat{x}=\left\{\left(\frac{f\left(w\right)}{t},w\right)\right\}

Przykład 12.2

Rozwiązujemy zadanie P.

Max\  M=\frac{-2x_{1}+x_{2}+3}{2x_{1}+3x_{2}+x_{3}+2}

\qquad 3x_{1}+x_{2}+x_{4}=4

\qquad\qquad x_{1}+2x_{2}+x_{5}=3

\qquad\qquad\forall _{i}\  x_{{i}}\geq 0

Ustalmy parametr t=2x_{1}+3x_{2}+x_{3}+2 i rozwiązujmy zadanie

Max\  x_{0}=-2x_{1}+x_{2}+3

\qquad 3x_{1}+x_{2}+x_{4}=4

\qquad\qquad x_{1}+2x_{2}+x_{5}=3

\qquad\qquad 2x_{1}+3x_{2}+x_{3}=t-2

\qquad\qquad\forall _{i}\  x_{{i}}\geq 0

Wtedy maksymalna wartość M jest równa maksymalnej wartości \frac{x_{0}}{t} i punkty optymalne obu zadań pokrywają się.

Budujemy więc tablicę sympleks i zadanie dzielimy na podproblemy w zależności od parametru t.

\left[\begin{array}[]{ccccc|c}2&-1&0&0&0&3\\
\hline 3&1&0&1&0&4\\
1&2&0&0&1&3\\
2&3&1&0&0&t-2\end{array}\right]

P_{1} Jeżeli t<2 to zadanie jest sprzeczne.

P_{2} Jeżeli 2\leq t\leq\frac{13}{2} to element centralny leży w ostatnim wierszu.

\left[\begin{array}[]{ccccc|c}2&-1&0&0&0&3\\
\hline 3&1&0&1&0&4\\
1&2&0&0&1&3\\
2&(3)&1&0&0&t-2\end{array}\right]

i po przekształceniach Gaussa - Jordana otrzymujemy:

\left[\begin{array}[]{ccccc|c}\frac{8}{3}&0&\frac{1}{3}&0&0&\frac{7}{3}+\frac{1}{3}t\\
\hline\frac{7}{3}&0&-\frac{1}{3}&1&0&\frac{14}{3}-\frac{1}{3}t\\
-\frac{1}{3}&0&-\frac{2}{3}&0&1&\frac{13}{3}-\frac{2}{3}t\\
\frac{2}{3}&1&\frac{1}{3}&0&0&\frac{1}{3}t-\frac{2}{3}\end{array}\right]

Punktem optymalnym jest p=(0,\frac{1}{3}t-\frac{2}{3},0,\frac{14}{3}-\frac{1}{3}t,\frac{13}{3}-\frac{2}{3}t), maksymalną wartością x_{0} jest \frac{7}{3}+\frac{1}{3}t. Zatem M przyjmuje wartość M=\frac{x_{0}}{t}=\frac{7}{3t}+\frac{1}{3}. Wartość M rośnie ze wzrostem T i przyjmuje maksymalną wartość dla t=\frac{13}{2} wynoszącą M_{m}=\frac{7}{3}+\frac{1}{3}\frac{13}{2}=\frac{9}{2}

P_{3}

t>\frac{13}{2} Tym razem elementem centralnym jest 2.

\left[\begin{array}[]{ccccc|c}2&-1&0&0&0&3\\
\hline 3&1&0&1&0&4\\
1&(2)&0&0&1&3\\
2&3&1&0&0&t-2\end{array}\right]

i po przekształceniach Gaussa - Jordana otrzymujemy:

\left[\begin{array}[]{ccccc|c}\frac{5}{2}&0&0&0&\frac{1}{2}&\frac{9}{2}\\
\hline\frac{5}{2}&0&0&1&-\frac{1}{2}&\frac{5}{2}\\
\frac{1}{2}&1&0&0&\frac{1}{2}&\frac{3}{2}\\
\frac{1}{2}&0&1&0&-\frac{3}{2}&-\frac{13}{2}+t\end{array}\right]

Punktem optymalnym jest p=(0,\frac{3}{2},-\frac{13}{2}+t,\frac{5}{2},0), maksymalną wartością x_{0} jest \frac{9}{2}. Zatem M przyjmuje wartość M=\frac{x_{0}}{t}=\frac{9}{2t}. Wartość M maleje ze wzrostem T i zawsze jest mniejsza niż \frac{9}{2}.

Rozwiązanie zadania p=(0,\frac{3}{2},0,\frac{5}{2},0), M=\frac{9}{2} otrzymaliśmy w podproblemie P_{2}.

Jako literaturę uzupełniającą do tego tematu polecamy książki [13] i [12]

Ćwiczenie 12.1

Stosując podział Dekina rozwiąż w liczbach całkowitych zadanie:

Min x_{0}=x_{3}+x_{4}+3x_{5} , gdy

x_{1}+\frac{1}{2}x_{3}+2x_{4}+\frac{3}{2}x_{5}=\frac{7}{2}

x_{2}+\frac{1}{2}x_{3}+\frac{1}{2}x_{4}+3x_{5}=\frac{9}{2}

\forall _{i}x_{i}\geq 0, x_{i}\in Z.

Ćwiczenie 12.2

Stosując podział Dekina rozwiąż w liczbach całkowitych zadanie:

Max\  x_{{0}}=x_{{1}}-2x_{{2}}

-x_{{1}}+x_{{2}}\leq 0

4x_{{1}}-2x_{{2}}\leq 9

x_{{1}}\leq 3

\forall _{i}x_{{i}}\geq 0\qquad x_{{i}}\in Z

Treść automatycznie generowana z plików źródłowych LaTeXa za pomocą oprogramowania wykorzystującego LaTeXML.

Projekt współfinansowany przez Unię Europejską w ramach Europejskiego Funduszu Społecznego.

Projekt współfinansowany przez Ministerstwo Nauki i Szkolnictwa Wyższego i przez Uniwersytet Warszawski.