Determine the optimal assignment of jobs to machines for the following data.

በእያንዳንዱ ረድፍ ውስጥ ትንሹን ቁጥር ከረድፉ ውስጥ ካሉ ሁሉም ቁጥሮች እንቀንሳለን።

• ረድፍ 1: ትንሹ ቁጥር 2.
• ረድፍ 2: ትንሹ ቁጥር 6.
• ረድፍ 3: ትንሹ ቁጥር 3.
• ረድፍ 4: ትንሹ ቁጥር 5.

$$\begin{bmatrix} 8-2 & 6-2 & 2-2 & 4-2 \\ 6-6 & 7-6 & 11-6 & 10-6 \\ 3-3 & 5-3 & 7-3 & 6-3 \\ 5-5 & 10-5 & 12-5 & 9-5 \end{bmatrix} = \begin{bmatrix} 6 & 4 & 0 & 2 \\ 0 & 1 & 5 & 4 \\ 0 & 2 & 4 & 3 \\ 0 & 5 & 7 & 4 \end{bmatrix}$$

በእያንዳንዱ አምድ ውስጥ ትንሹን ቁጥር ከአምዱ ውስጥ ካሉ ሁሉም ቁጥሮች እንቀንሳለን።

• አምድ A: ትንሹ ቁጥር 0.
• አምድ B: ትንሹ ቁጥር 1.
• አምድ C: ትንሹ ቁጥር 0.
• አምድ D: ትንሹ ቁጥር 2.

$$\begin{bmatrix} 6-0 & 4-1 & 0-0 & 2-2 \\ 0-0 & 1-1 & 5-0 & 4-2 \\ 0-0 & 2-1 & 4-0 & 3-2 \\ 0-0 & 5-1 & 7-0 & 4-2 \end{bmatrix} = \begin{bmatrix} 6 & 3 & 0 & 0 \\ 0 & 0 & 5 & 2 \\ 0 & 1 & 4 & 1 \\ 0 & 4 & 7 & 2 \end{bmatrix}$$

ሁሉንም ዜሮዎች ለመሸፈን አነስተኛውን አግድም እና ቀጥ ያለ መስመሮችን እንሳል።

$$\begin{bmatrix} 6 & 3 & \mathbf{0} & \mathbf{0} \\ \mathbf{0} & \mathbf{0} & 5 & 2 \\ \mathbf{0} & 1 & 4 & 1 \\ \mathbf{0} & 4 & 7 & 2 \end{bmatrix}$$

ሶስት መስመሮችን በመጠቀም ሁሉንም ዜሮዎች መሸፈን እንችላለን (ለምሳሌ: ረድፍ 1፣ ረድፍ 2 እና አምድ A)። የመስመሮች ብዛት (3) ከረድፎች/አምዶች ብዛት (4) ያነሰ ስለሆነ ወደ ቀጣዩ ደረጃ እንሄዳለን።

ያልተሸፈኑት ቁጥሮች ውስጥ ትንሹን ቁጥር እንፈልጋለን። ይህንን ቁጥር ከሁሉም ያልተሸፈኑ ቁጥሮች እንቀንሳለን እና ሁለት መስመሮች በሚገናኙበት ቦታ ላይ እንጨምራለን። በአንድ መስመር የተሸፈኑ ቁጥሮች ሳይለወጡ ይቀራሉ።

• ትንሹ ያልተሸፈነ ቁጥር 1 ነው።
• መስመሮች የሚገናኙባቸው ቦታዎች: (1,A) እና (2,A)።

$$\begin{bmatrix} 6+1 & 3 & 0 & 0 \\ 0+1 & 0 & 5-1 & 2-1 \\ 0 & 1-1 & 4-1 & 1-1 \\ 0 & 4-1 & 7-1 & 2-1 \end{bmatrix} = \begin{bmatrix} 7 & 3 & 0 & 0 \\ 1 & 0 & 4 & 1 \\ 0 & 0 & 3 & 0 \\ 0 & 3 & 6 & 1 \end{bmatrix}$$

ሁሉንም ዜሮዎች ለመሸፈን አነስተኛውን አግድም እና ቀጥ ያለ መስመሮችን እንሳል።

$$\begin{bmatrix} 7 & 3 & \mathbf{0} & \mathbf{0} \\ 1 & \mathbf{0} & 4 & 1 \\ \mathbf{0} & \mathbf{0} & 3 & \mathbf{0} \\ \mathbf{0} & 3 & 6 & 1 \end{bmatrix}$$

አሁን አራት መስመሮችን በመጠቀም ሁሉንም ዜሮዎች መሸፈን እንችላለን (ለምሳሌ: ረድፍ 1፣ ረድፍ 2፣ ረድፍ 3 እና አምድ A)። የመስመሮች ብዛት (4) ከረድፎች/አምዶች ብዛት (4) ጋር እኩል ስለሆነ፣ ምርጥ ምደባ ማድረግ ይቻላል።

በእያንዳንዱ ረድፍ እና አምድ ውስጥ አንድ ዜሮ ብቻ እንዲኖር ምደባዎችን እናደርጋለን።

• ሥራ 2 ወደ ማሽን B ይመደባል (በረድፍ 2 ውስጥ ብቸኛው ዜሮ)።
• ሥራ 4 ወደ ማሽን A ይመደባል (በረድፍ 4 ውስጥ ብቸኛው ዜሮ)።
• ሥራ 3 ወደ ማሽን D ይመደባል (በአምድ D ውስጥ ብቸኛው ዜሮ)።
• ሥራ 1 ወደ ማሽን C ይመደባል (በአምድ C ውስጥ ብቸኛው ዜሮ)።

ምደባዎቹ የሚከተሉት ናቸው:

• ሥራ 1 $\to$ ማሽን C
• ሥራ 2 $\to$ ማሽን B
• ሥራ 3 $\to$ ማሽን D
• ሥራ 4 $\to$ ማሽን A

ወደ መጀመሪያው ማትሪክስ በመመለስ ለእያንዳንዱ ምደባ ወጪውን እንፈልጋለን።

• ሥራ 1 ወደ ማሽን C: 2
• ሥራ 2 ወደ ማሽን B: 7
• ሥራ 3 ወደ ማሽን D: 6
• ሥራ 4 ወደ ማሽን A: 5

አጠቃላይ ዝቅተኛው ወጪ:

$$2 + 7 + 6 + 5 = 20$$

የምርጥ ምደባው እና አጠቃላይ ወጪው:

• ሥራ 1 $\to$ ማሽን C
• ሥራ 2 $\to$ ማሽን B
• ሥራ 3 $\to$ ማሽን D
• ሥራ 4 $\to$ ማሽን A
• አጠቃላይ ወጪ: $\text{20}$