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}
Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-NonCommercial-ShareAlike 3.0 License