# Maximization using dual simplex method - problem

My teacher gave us on a test following problem:

Following ILP(Integer linear programming) problem:

$$2x_1 +5x_2+4x_3 ->max$$

$$3x_1 +3x_2 + x_3 \leq 20$$

$$2x_1+ 3x_2 + 4x_3 \leq 30$$

$$x_1,x_2,x_3\ge 0 , x_1,x_2,x_3 - int$$

is being solved using branch and bound method. One of paths in tree for this exercise is

$$x_1\le5........ x_2\le3$$

S0------->S1-------->S2

Using dual simplex method solve relaxed problem related to node S2 of this tree.

## My attempt to solve:

Standarization:

$$-x_1-5x_2-4x_3->min$$

$$3x_1+3x_2+x_3+x_4=20$$

$$2x_1+3x_2+4x_3+x_5=30$$

$$x_2 +x_6 = 5$$

$$x_3 +x_7 = 3$$

$$x_1,x_2,x_3,x_4,x_5,x_6,x_7\ge0$$

So i get this dual simplex tableau:

$$\begin{bmatrix} & & & -1 & -5 & -4 & 0 & 0 & 0 & 0 \\ & & Z_0 & Z_1 & Z_2 & Z_3 & Z_4 & Z_5 & Z_6 & Z_7 \\ N_B & C_B & 0 & 1 & 5 & 4 & 0 & 0 & 0 & 0 \\ 4 & 0 & 20 & 3 & 3 & 1 & 1 & 0 & 0 & 0 \\ 5 & 0 & 30 & 2 & 3 & 4 & 0 & 1 & 0 & 0 \\ 6 & 0 & 5 & 0 & 1 & 0 & 0 & 0 & 1 & 0 \\ 7 & 0 & 3 & 0 & 0 & 1 & 0 & 0 & 0 & 1 \end{bmatrix}$$

......................../\ And in this following column all values are positive so i don't have any vector to remove from the base so I guess this problem doesn't have any solution or am I doing something wrong or maybe our teacher Is not educated and gave us problem that's unsolvable using dual simplex?