Given a Linear Programming problems of the form:

minimize,$c^{TT}x$

subject $toAx=b$

$x0,$

where

$x$ is the decision variable.

c is the coefficient for the objective function.

A is the matrix of coefficients for the constraints.

$b$ is the right$-$hand side values for the constraints.

Implement a Linear Programming Problem solver using the Simplex or Interior Point method. You are to code the solver from scratch, relying only on basic libraries such as numpy for mathematical operations. No specialized linear programming libraries are allowed.

Below is given a template according to which you have to design your code:

def $,$ epsilon $)$:

$,"$

$,$Parameters:

$,-$ A : Coefficient matrix for constraints.

$,-b$ : RHS vector for constraints.

$,-c$ : Coefficient vector for the objective function.

$,-$ epsilon : Tolerance for optimality.

$,$Returns:

$,-$ opt : The optimal value of the objective function.

$,-$ x$\_$star : The optimal solution vector.

$,"$

The function should return an optimal value $($opt$)$ and an optimal solution $($x$\_$star$)$ such that

$|$ opt $-tru{e}_{o}pt|$ epsilon.