Given the following LP:

$mamizeZ={\displaystyle \underset{j=1}{\overset{n}{}}}{c}_j{x}_j$

subject $to{\displaystyle \underset{j=1}{\overset{n}{}}}{a}_j{x}_{j}b$

$x_{j}0$

a$)$ Write the dual of this problem $(20$ points$)$:

b$)$ Design an algorithm to find the optimal solution to this problem with minimum computational effort $(80$ points$).$

Hint: The primal problem contains single constraint and $n$ variables while the dual problem has $n$ constraints and one variable. This observation would be helpful in designing an algorithm.