1. **Stating the problem:** We have two types of bus services: Ekspres (x) and Reguler (y). We want to maximize profit given constraints on Terminal A, Depo BBM, and pool/bengkel capacity. 2. **Define variables:** Let $x$ = number of Ekspres departures per day Let $y$ = number of Reguler departures per day 3. **Formulate the primal problem:** Maximize profit: $$\max Z = 3x + 4y$$ Subject to constraints: - Terminal A slots: $$x + y \leq 6$$ - Depo BBM capacity (Ekspres uses 2 units, Reguler 1 unit): $$2x + y \leq 8$$ - Pool/bengkel capacity (Ekspres 2 units, Reguler 1 unit): $$2x + y \leq 8$$ - Non-negativity: $$x \geq 0, y \geq 0$$ 4. **Formulate the dual problem:** Let $u, v, w$ be dual variables for the three constraints respectively. Dual: $$\min W = 6u + 8v + 8w$$ Subject to: $$u + 2v + 2w \geq 3$$ $$u + v + w \geq 4$$ $$u, v, w \geq 0$$ 5. **Solve primal graphically:** Plot constraints: - $x + y \leq 6$ - $2x + y \leq 8$ - $x, y \geq 0$ Find intersection points: - Intersection of $x + y = 6$ and $2x + y = 8$: Subtracting: $(2x + y) - (x + y) = 8 - 6 \Rightarrow x = 2$ Then $y = 6 - 2 = 4$ Check vertices: - $(0,0)$: $Z=0$ - $(0,6)$: Check constraints: $2(0)+6=6 \leq 8$ valid, $Z=4*6=24$ - $(2,4)$: $2(2)+4=8$ valid, $Z=3*2+4*4=6+16=22$ - $(4,0)$: $2(4)+0=8$ valid, $Z=3*4=12$ Maximum profit at $(0,6)$ with $Z=24$ 6. **Solve primal by simplex:** Set up tableau with slack variables $s_1, s_2$: Maximize $Z=3x+4y$ Subject to: $x + y + s_1 = 6$ $2x + y + s_2 = 8$ Initial basic variables: $s_1=6, s_2=8$ Pivot to increase $y$ (higher profit coefficient): From first constraint: $y = 6 - x - s_1$ From second: $y = 8 - 2x - s_2$ At $x=0$, $y$ max is 6 (from first constraint), $Z=24$ Simplex confirms optimal solution $x=0, y=6, Z=24$ 7. **Dual optimal value:** From complementary slackness and dual constraints, solve: Try $u=0, v=1, w=0$: $u+2v+2w=2 \geq 3$ no Try $u=1, v=1, w=0$: $1+2*1+0=3 \geq 3$ ok $1+1+0=2 \geq 4$ no Try $u=0, v=0, w=1$: $0+0+2=2 \geq 3$ no Try $u=1, v=0, w=1$: $1+0+2=3 \geq 3$ ok $1+0+1=2 \geq 4$ no Try $u=2, v=0, w=1$: $2+0+2=4 \geq 3$ ok $2+0+1=3 \geq 4$ no Try $u=2, v=1, w=0$: $2+2+0=4 \geq 3$ ok $2+1+0=3 \geq 4$ no Try $u=1, v=1, w=1$: $1+2+2=5 \geq 3$ ok $1+1+1=3 \geq 4$ no Try $u=0, v=2, w=1$: $0+4+2=6 \geq 3$ ok $0+2+1=3 \geq 4$ no Try $u=0, v=1, w=2$: $0+2+4=6 \geq 3$ ok $0+1+2=3 \geq 4$ no Try $u=1, v=2, w=1$: $1+4+2=7 \geq 3$ ok $1+2+1=4 \geq 4$ ok Calculate dual objective: $6u + 8v + 8w = 6*1 + 8*2 + 8*1 = 6 + 16 + 8 = 30$ Since dual objective is 30 but primal max is 24, check if constraints are tight or if there is a mistake. Note: The pool/bengkel and Depo BBM constraints are identical ($2x + y \leq 8$), so effectively one is redundant. Reconsider primal constraints: - Terminal A: $x + y \leq 6$ - Depo BBM and Pool/Bengkel combined: $2x + y \leq 8$ So only two constraints effectively. Dual variables reduce to $u$ and $v$: Minimize $6u + 8v$ Subject to: $u + 2v \geq 3$ $u + v \geq 4$ $u,v \geq 0$ Try $u=0, v=2$: $0 + 4 = 4 \geq 3$ ok $0 + 2 = 2 \geq 4$ no Try $u=2, v=1$: $2 + 2 = 4 \geq 3$ ok $2 + 1 = 3 \geq 4$ no Try $u=3, v=0$: $3 + 0 = 3 \geq 3$ ok $3 + 0 = 3 \geq 4$ no Try $u=4, v=0$: $4 + 0 = 4 \geq 3$ ok $4 + 0 = 4 \geq 4$ ok Dual objective: $6*4 + 8*0 = 24$ This matches primal optimum $Z=24$. **Final answers:** - Primal optimum: $x=0, y=6, Z=24$ - Dual optimum: $u=4, v=0, W=24$ They are equal, confirming strong duality.