SGT Sheet

Question 1

(i)

Begin by introducing slack variables:

$$\begin{array}{rl}3y-x+s_0& =9\\ 4x+6y+s_1& =27\\ 5x-6y+s_2& =1\end{array}$$

Maximise $x+3y\to C=x+3y$. (re-arranged to $-x-3y+C=0$) Construct a Tableau:

$$\left[\begin{array}{ccccccc}x& y& s_0& s_1& s_2& C& \\ -1& 3& 1& 0& 0& 0& 9\\ 4& 6& 0& 1& 0& 0& 27\\ 5& -6& 0& 0& 1& 0& 1\\ -1& -3& 0& 0& 0& 1& 0\end{array}\right]$$

Pivot column is $y$. Calculate row quotients by dividing each entry in final column by entries in the selected pivot column: $3,4.5,\cancel{-0.16}$. Pivot row is the 1st row. Pivot value is $5$. Apply row transformations:

$$\left[\begin{array}{ccccccc}x& y& s_0& s_1& s_2& C& \\ -\frac{1}{3}& 1& \frac{1}{3}& 0& 0& 0& 3\\ 6& 0& -2& 1& 0& 0& 9\\ 3& 0& 2& 0& 1& 0& 19\\ -2& 0& 1& 0& 0& 1& 9\end{array}\right]$$

Pivot column is $x$. Pivot row is 2nd row. Pivot value is $6$. Apply row transformations:

$$\left[\begin{array}{ccccccc}x& y& s_0& s_1& s_2& C& \\ 0& 1& \frac{2}{9}& \frac{1}{18}& 0& 0& \frac{7}{2}\\ 1& 0& -\frac{1}{3}& \frac{1}{6}& 0& 0& \frac{3}{2}\\ 0& 0& 3& -\frac{1}{2}& 1& 0& \frac{29}{2}\\ 0& 0& \frac{1}{3}& \frac{1}{3}& 0& 1& 12\end{array}\right]$$

We no longer have negative values in the bottom row. We can now form the optimal solution by reading off the matrix. And then do simultaneous solving if needed.

Complete this.

(ii)

Try this.

Question 2

Simplified Example

Take $x+y\le 5$ and $2x\ge 6$. If we want to maximise $3x+2y$, the Simplex algorithm tries to look at the extreme points where the region is overlapped. Since we are doing integer programming, we are operating on a grid of points on the $x$ and $y$ axis.

(i)

The feasible region can just be plotted from the lines. It is plotted in part. 2 below.

(ii)

When putting all the values into a calculator, we get the values: $x=1.5485,y=2.7652,C=1.0768$

And from here we start branching on $x$:

• $x\ge 2$ We add this as an extra constraint on which we calculate the next value. $x=2,y=2.5,C=68$ Branch on $y$:
  • $y\le 2$: $x=2.5,y=2,C=6.5$ Branch on $x$:
    • $x\le 2$: $x=2,y=2,C=6$
    • $x\ge 3$: $x=3,y=1.6,C=6.2$ Branch on $y$:
      • $y\le 1$: $C=5.75$, we can just stop here as $C$ degrades
      • $y\ge 2$: No solutions.
  • $y\ge 3$ No solutions.
• $x\le 1$: $x=1,y=2.5,C=6$ We already have an integer solution for $C=6$ so we abandon search.

Hence our final answer is $x=2,y=2$ with $C=6$.

Question 3

(i)

Minimise ${\sum }_{i,j}{x}_{i,j}\times d_{i,j}$.

(ii)

$$\sum _{i,j}{x}_{i,j}=10$$

(iii)

Try this.

(iv)

Try this.