Consider the following linear program:
max $z = 4x_1+x_2+5x_3+3x_4$
subject to
$x_1-x_2-x_3+3x_4 \le 1$
$5x_1+x_2+3x_3+8x_4\le55$
$-x_1+2x_2+3x_3-5x_4\le3$
It is claimed that the solution $x^*=(0, 14, 0, 5)$ is an optimal solution to the problem. Give a proof of the claim.
I have to proof the problem without using the simplex method to solve this problem. How can it be possible?
Your objectiva value is $29$. Hence if we can exhibit a feasible solution with the same objective value in the dual problem then we are done.
Let's write down the dual:
$$\min p_1+55p_2+3p_3$$
subject to
$$p_1 + 5p_2-p_3 = 4 $$ $$-p_1+p_2+2p_3=1$$
$$-p_1+3p_2+3p_3=5$$
$$3p_1+8p_2-5p_3=3$$
$$p \ge 0$$
Also, from complementary slackness condition we know that $p_2=0$.
We can easily check that the linear system has no feasible solution. Hence the claimed solution can't be optimal.
View the original problem as
$$\max c^Tx$$
subject to $$Ax \le b$$
$A$ is of full row rank and the nullity is $1$, that is there is this vector $d \ne 0$ such that $Ad=0$.
If we compute $c^Td\ne 0$, then we have found a direction that can increase the objective value indefinitely.