Question

Minimize z = 6x + 21y, subject to x + 2y ≥ 3, x + 4y ≥ 4, 3x + y ≥ 3, x ≥ 0, y ≥ 0.

Answer 1

First we draw the lines AB, CD and EF whose equations are x + 2y = 3, x + 4y = 4 and 3x + y = 3 respectively.

Line	Equation	Points on the X-axis	Points on the Y-axis	Sign	Region
AB	x + 2y = 3	A(3, 0)	B`(0, 3/2)`	≥	non-origin side of line AB
CD	x + 4y = 4	C(4, 0)	D(0, 1)	≥	non-origin side of line CD
EF	3x + y = 3	E(1, 0)	F(0, 3)	≥	non-origin side of line EF

The feasible region is XCPQFY which is shaded in the graph.

The vertices of the feasible region are C(4, 0), P, Q and F (0, 3).

P is the point of intersection of the lines x + 4y = 4 and x + 2y = 3

On subtracting, we get

2y = 1 

∴ y = `1/2`

Substituting y = `1/2` in x + 2y = 3, we get

x + 2`(1/2)` = 3

∴ x = 2

∴ P ≡ `(2, 1/2)`

Q is the point of intersection of the lines

x + 2y = 3     ....(1)

and 3x + y = 3      ...(2)

Multiplying equation (1) by 3, we get

3x + 6y = 9

Subtracting equation (2) from this equation, we get

5y = 6

∴ y =`6/5`

∴ from (1), x + 2`(6/5) = 3`

∴ x = `3 - 12/5 = 3/5` 

∴ Q ≡ `(3/5,6/5)`

The values of the objective function z = 6x + 21y at these vertices are

z(C) = 6(4) + 21(0) = 24

z(P) = 6(2) + 21`(1/2)`

= 12 + 10.5 = 22.5

z (Q) = `6(3/5) + 21(6/5)`

`= 18/5 + 126/5 = 144/5 = 28.8`

z(F) = 6(0) + 21(3) = 63

∴ z has minimum value 22.5, when x = 2 and y = `1/2`.