Do2

Тука сложи заглавие

---

страницата се нуждае от дописване/преглеждане

---

Задача за назначенията

• $n$ работника
• $n$ работи

Всеки работник трябва да свърши точно една работа, и всяка работа трябва да бъде свършена от точно един работинк.

• $c_{ij}$ цена за назначаване на i^тия работник на j^тата работа.

Целта е да се минимиза сумата от цените за назначаване на всеки работник.

Математически модел

$x_{ij} \in \{0, 1 \}$ - тази променлива ще показва дали i^тия работник е назначен на j^тата работа.
Ограничението всеки работник да взима точно една работа:

(1)

\begin{align} \sum_{j} x_{ij} = 1 \quad i = \overline{1, n} \end{align}

Т.е искаме за всеки конкретен работник ($i = \overline{1, n}$) да сумираме всички $x_{ij}$, който се отнасят до него - т.е този работник със всички възможни работи. Тази сума трябва да е 1 (и тъй като всички променливи са 0/1 то точно една от променливите трябва да бъде 1 за да е изпълнено равенството).

Ограничението всяка работа да бъде свършена от точно един работник (доста подобно на горното):

(2)

\begin{align} \sum_{i} x_{ij} = 1 \quad j = \overline{1, n} \end{align}

Целевата функция - искаме да минимизираме сумата от цените за назначенията. Само тези произведения, при които $x_{ij}$ не е 0 са съществени - т.е ще прибавим само цените, за работа/работник ако съответния работник извършва съответната работа.

(3)

\begin{align} \sum_{i}\sum_{j} c_{ij}x_{ij} \to \min \end{align}

0/1 knapsack problem (задача за раницата)

• $n$ обекта които трябва да натъпчем в раница. Всеки обект има стойност (печалба) и тегло
• $w_j$ тежест на j^тия обект
• $p_j$ печалба на j^тия обект
• $C$ капацитет на раницата (максимална тежест, която може да вкараме вътре без да се скъса)

Математически модел

• $x_{j} = \{ 0, 1 \}$ - дали взимаме j^тия обект
• ограничение за капацитета на раницата (да не го препълним):

(4)

\begin{align} \sum_j w_j x_j \le C \end{align}

• целева функция - трябва да максимизираме печалбата

(5)

\begin{align} \sum_j p_j x_j \to \max \end{align}

Разновидности

• Целочислена раница. Ако позволим взимането на произволен брой предмети от всеки вид (т.е $x_j \in \mathbb Z^+_0$) получаваме друга задача, не по-лесна от основната. Тази задача е известна още като целочислена раница или просто раница (естествено има и дробна раница при която е позволено да се взима произволно количество от всеки предмен - не непременно целочислено - но това е по-скоро задача на линейното оптимиране).
• Раница със нетривиална функция на печалбаа. Възможно е функцията на печалбата да не бъде линейна ($px$) а да прилича на нещо такова:

[[ image knapsack_price_function ]]
При това ако означим функцията за печалба за всеки предмет със $t_j$, то целевата функция става $\sum t_j(x_j)$.

Set covering (задача за покритието)

• $n$ пожарни
• $m$ къщи (места, където могат да възникнат пожари)
• $c_j$ цена за построяване на j^тата пожарна.
• $R_j \subseteq 2^m$ множество от къщи, който покрива всяка пожарна (подмножество на всички къщи) - т.е ако бъде построена j^тата пожарна кои къщи ще могат да бъдат достигнати от нея (ако са много далеч няма да има смисъл, защото ще бъдат изгорели докато пристигне :)). Разбира се трябва да си стегнем малко модела, тъй като тези множества трудно ще ги трансформираме до линейни неравенства.

$R_{ij} = \{ 0 , 1 \}$ ако j^тата пожарна покрива i^тата къща

Целта е да построим пожарни, който покриват всички къщи (някой къщи могат да се окажат покрити от повече от 1 пожарна), така че общата цена за построяването на всички пожарни да е минимална.

• ограничението да бъдат покрити всички къщи

(6)

\begin{align} \ \end{align}