0
$\begingroup$

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?

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.