Question

Use Branch and Bound technique to solve the following problem
Maximise z = 3x1 + 3x2 + 13 x3
Subject to
– 3x1 + 6x2 + 7x3 ≤ 8
6x1 – 3x2 + 7x3 ≤ 8
0 ≤ xj ≤ 5
And xj are integer j = 1, 2, 3

Answer 1

$$\begin{array}{l} z = 3 x _ {1} + 3 x _ {2} + 13 x _ {3} \rightarrow \max \\ -3 x _ {1} + 6 x _ {2} + 7 x _ {3} \leq 8 \\ 6 x _ {1} - 3 x _ {2} + 7 x _ {3} \leq 8 \\ x _ {i} \in \{0, 1, 2, 3, 4, 5 \} \\ \left[ \begin{array}{l} -3 x _ {1} + 6 x _ {2} + 7 x _ {3} \leq 8 \\ 6 x _ {1} - 3 x _ {2} + 7 x _ {3} \leq 8 \end{array} \right. \quad \text{"-"} \Rightarrow 9 x _ {1} - 9 x _ {2} \leq 0 \Rightarrow 0 \leq x _ {1} \leq x _ {2} \\ " +": 3 x _ {1} + 3 x _ {2} + 14 x _ {3} \leq 16 \Rightarrow 0 \leq 3 x _ {1} + 3 x _ {2} \leq 16 - 14 x _ {3} \Rightarrow 14 x _ {3} \leq 16 \Rightarrow 0 \leq x _ {3} \in Z \Rightarrow x _ {3} \in \{0, 1 \} \\ \end{array}$$ $$a) x _ {3} = 0$$ $$\left\{ \begin{array}{l} z = 3 x _ {1} + 3 x _ {2} \rightarrow \max \\ -3 x _ {1} + 6 x _ {2} \leq 8 \\ 6 x _ {1} - 3 x _ {2} \leq 8 \\ x _ {i} \in \{0, 1, 2, 3, 4, 5 \} \\ 0 \leq 3 x _ {1} + 3 x _ {2} \leq 16, 0 \leq x _ {1} \leq x _ {2} \leq 5 \end{array} \right.$$ $$\max : x _ {1} + x _ {2} = 5$$ $$x _ {1} = 0, x _ {2} = 5, x _ {3} = 0 \Rightarrow z = 15$$ $$x _ {1} = 1, x _ {2} = 4, x _ {3} = 0 \Rightarrow z = 15$$ $$x _ {1} = 2, x _ {2} = 3, x _ {3} = 0 \Rightarrow z = 15$$ $$b) x _ {3} = 1$$ $$\left\{ \begin{array}{l} z = 3 x _ {1} + 3 x _ {2} + 13 \rightarrow \max \\ -3 x _ {1} + 6 x _ {2} \leq 1 \\ 6 x _ {1} - 3 x _ {2} \leq 1 \\ x _ {i} \in \{0, 1, 2, 3, 4, 5 \} \\ 0 \leq 3 x _ {1} + 3 x _ {2} \leq 2, 0 \leq x _ {1} \leq x _ {2} \leq 5 \end{array} \right.$$ $$x _ {1} + x _ {2} = 0 \Rightarrow x _ {1} = x _ {2} = 0, x _ {3} = 1 \Rightarrow z = 13$$ $$\text{So, solutions are:}$$ $$(0, 5, 0), (1, 4, 0), (2, 3, 0), z _ {\max } = 15$$