Very important insights on the quality of the solutions of an optimization problem may be obtained by considering a related problem, called the dual problem. For a linear programming problem written in standard form the dual problem is a minimization problem with as many variables as the number of constraints in P and as many constraints as the number of variables in P.
Note that the constraint matrix of the dual is simply the transposed matrix of A and the cost and the vectors of the primal problem change their roles in the dual.
If all the primal constraints are defined by inequalities then the dual variables are subjected to be non negative.
Problem P and D are strongly linked. For instance it is easy to verify that if x' and u' are two feasible solutions of P and D respectively, then cx' is not greater than u'b. This property is called weak duality. As a consequence we have that if one problem is unbounded then the other one is infeasible and viceversa. Moreover, if both problem are feasible, then the optimalue value of the primal problem is not greater than the optimal value of the dual one.