# hw5-1
R09521608 土木系電輔組 蔡瑋倫

| |J1|J2|J3|J4|
|-|-|-|-|-|
|S1|3|9|3|2|
|S2|9|4|10|3|
|S3|8|6|4|5|

---

#### solution

$max\sum_{i=1}^{n}\sum_{j=1}^n c_{ij}x_{ij}$

s.t.

$\sum_{i=1}^{n}x_{ij} = 1, ∀i$

$\sum_{j=1}^{n}x_{ij} = 1, ∀j$

$x_{ij} = (1, 0), ∀i, j$

---

#### standard form
$\begin{split}&\\&max(
3 \times x_{11} + 9 \times x_{12} + 3 \times x_{13} + 2 \times x_{14}\\
&+ 9 \times x_{21} + 4 \times x_{22} + 10 \times x_{23} + 3 \times x_{24}\\
&+ 8 \times x_{31} + 6 \times x_{32} + 4 \times x_{33} + 5 \times x_{34})
\end{split}$

one employeecan only take one job and each job can only have one employee working on it.
There are only three employees but there are four jobs. According to the question, there will be one job left after assign three jobs to three employees. So there will be one summation of $\sum_{i=1}^{n}x_{ij}$ not equal 1.

$\begin{split}
&x_{11} + x_{21} + x_{31} \le 1\\
&x_{12} + x_{22} + x_{32} \le 1\\
&x_{13} + x_{23} + x_{33} \le 1\\
&x_{14} + x_{24} + x_{34} \le 1\\
&x_{11} + x_{12} + x_{13} + x_{14} = 1\\
&x_{21} + x_{22} + x_{23} + x_{24} = 1\\
&x_{31} + x_{32} + x_{33} + x_{34} = 1\\
\end{split}$

$x_{11}, x_{12}, x_{13}, x_{14}, x_{21}, x_{22}, x_{23}, x_{24}, x_{31}, x_{32}, x_{33}, x_{34} \ge 0$

---

#### slack form, and pivot $x_{23}$
$\begin{split}&\\&max(
3 \times x_{11} + 9 \times x_{12} + 3 \times x_{13} + 2 \times x_{14}\\
&+ 9 \times x_{21} + 4 \times x_{22} + 10 \times x_{23} + 3 \times x_{24}\\
&+ 8 \times x_{31} + 6 \times x_{32} + 4 \times x_{33} + 5 \times x_{34}) \leftarrow pivot~x_{23}
\end{split}$

$\begin{split}
&w_1 = 1 - x_{11} - x_{21} - x_{31}\\
&w_2 = 1 - x_{12} - x_{22} - x_{32}\\
&w_3 = 1 - x_{13} - x_{23} - x_{33} \to x_{23}\le \frac{1}{1} = 1\\
&w_4 = 1 - x_{14} - x_{24} - x_{34}\\
&w_5 = 1 - x_{11} - x_{12} - x_{13} - x_{14}\\
&w_6 = 1 - x_{21} - x_{22} - x_{23} - x_{24} \to x_{23}\le \frac{1}{1} = 1\\
&w_7 = 1 - x_{31} - x_{32} - x_{33} - x_{34}\\
\end{split}$

$x_{11}, x_{12}, x_{13}, x_{14}, x_{21}, x_{22}, x_{23}, x_{24}, x_{31}, x_{32}, x_{33}, x_{34}, w_1, w_2, w_3, w_4, w_5, w_6, w_7 \ge 0$

$x_{23} = 1 - x_{21} - x_{22} - x_{24} - w_6$

---

#### pivot $x_{12}$
$\begin{split}&\\&max(10+
3 \times x_{11} + 9 \times x_{12} + 3 \times x_{13} + 2 \times x_{14}\\
&-x_{21}-6\times x_{22}-7\times x_{24}\\
&+ 8 \times x_{31} + 6 \times x_{32} + 4 \times x_{33} + 5 \times x_{34}) \leftarrow pivot~x_{12}
\end{split}$

$\begin{split}
&w_1 = 1 - x_{11} - x_{21} - x_{31}\\
&w_2 = 1 - x_{12} - x_{22} - x_{32} \to x_{12}\le \frac{1}{1} = 1\\
&w_3 = - x_{13} - x_{33} + x_{21} + x_{22} + x_{24} + w_6\\
&w_4 = 1 - x_{14} - x_{24} - x_{34}\\
&w_5 = 1 - x_{11} - x_{12} - x_{13} - x_{14} \to x_{12}\le \frac{1}{1} = 1\\
&x_{23} = 1 - x_{21} - x_{22} - x_{24} - w_6\\
&w_7 = 1 - x_{31} - x_{32} - x_{33} - x_{34}\\
\end{split}$

$x_{11}, x_{12}, x_{13}, x_{14}, x_{21}, x_{22}, x_{23}, x_{24}, x_{31}, x_{32}, x_{33}, x_{34}, w_1, w_2, w_3, w_4, w_5, w_6, w_7 \ge 0$

$x_{12} = 1 - x_{11} - x_{13} - x_{14} - w_5$

---

#### pivot $x_{31}$
$\begin{split}&\\&max(19
-6\times x_{11}-6\times x_{13}-7\times x_{14}-x_{21}-6\times x_{22}-7\times x_{24}\\
&+ 8 \times x_{31} + 6 \times x_{32} + 4 \times x_{33} + 5 \times x_{34}) \leftarrow pivot~x_{31}
\end{split}$

$\begin{split}
&w_1 = 1 - x_{11} - x_{21} - x_{31} \to x_{31}\le \frac{1}{1} = 1\\
&w_2 = - x_{22} - x_{32} + x_{11} + x_{13} + x_{14} + w_5\\
&w_3 = - x_{13} - x_{33} + x_{21} + x_{22} + x_{24} + w_6\\
&w_4 = 1 - x_{14} - x_{24} - x_{34}\\
&x_{12} = 1 - x_{11} - x_{13} - x_{14} - w_5\\
&x_{23} = 1 - x_{21} - x_{22} - x_{24} - w_6\\
&w_7 = 1 - x_{31} - x_{32} - x_{33} - x_{34} \to x_{31}\le \frac{1}{1} = 1\\
\end{split}$

$x_{11}, x_{12}, x_{13}, x_{14}, x_{21}, x_{22}, x_{23}, x_{24}, x_{31}, x_{32}, x_{33}, x_{34}, w_1, w_2, w_3, w_4, w_5, w_6, w_7 \ge 0$

$x_{31} = 1 - x_{32} - x_{33} - x_{34} - w_7$

---

$\begin{split}&\\&max(27
-6\times x_{11}-6\times x_{13}-7\times x_{14}-x_{21}-6\times x_{22}-7\times x_{24}-2\times x_{32}-4\times x_{33}-3\times x_{34})
\end{split}$

$\begin{split}
&w_1 = - x_{11} - x_{21} + x_{32} + x_{33} + x_{34} + w_7\\
&w_2 = - x_{22} - x_{32} + x_{11} + x_{13} + x_{14} + w_5\\
&w_3 = - x_{13} - x_{33} + x_{21} + x_{22} + x_{24} + w_6\\
&w_4 = 1 - x_{14} - x_{24} - x_{34}\\
&x_{12} = 1 - x_{11} - x_{13} - x_{14} - w_5\\
&x_{23} = 1 - x_{21} - x_{22} - x_{24} - w_6\\
&x_{31} = 1 - x_{32} - x_{33} - x_{34} - w_7\\
\end{split}$

$x_{11}, x_{12}, x_{13}, x_{14}, x_{21}, x_{22}, x_{23}, x_{24}, x_{31}, x_{32}, x_{33}, x_{34}, w_1, w_2, w_3, w_4, w_5, w_6, w_7 \ge 0$

---

$\begin{split}&\\
&max(27-6\times x_{11}-6\times x_{13}-7\times x_{14}
-x_{21}-6\times x_{22}-7\times x_{24}
-2\times x_{32}-4\times x_{33}-3\times x_{34})= 27\\
&x_{12} = x_{23} = x_{31} = 1\end{split}$

We can get employee 1 will be assigned to job 2, employee 2 will be assigned to job 3, and employee 3 will be assigned to job 1. Maximum of the employee-job matching index will be 27.