Linear programmingIB MYP Maths Extended: Revision notes

Linear programming starts by choosing variables, such as $x$ tables and $y$ chairs, and turning each limit in the problem into a constraint (a linear inequality).

• at most, no more than: $\le$
• at least, no fewer than: $\ge$
• fewer than: $<$; more than: $>$ Examples: 'at most 14 people' is $x+y\le14$; 'at least 2 adults' is $x\ge2$; 'children at most three times the adults' is $y\le3x$. Resource limits add up each item's use: 4 kg of rice per Type A parcel and 2 kg per Type B with 40 kg available gives $4x+2y\le40$. Counts cannot be negative, so also write $x\ge0$ and $y\ge0$.

1. Draw the boundary line by changing the inequality to an equals sign. Find two points, such as the axis intercepts: $2x+y=16$ passes through $(8,0)$ and $(0,16)$.
2. Use a solid line for $\le$ or $\ge$ (points on the line are allowed) and a dashed line for $<$ or $>$.
3. Test a point, usually $(0,0)$. For $2x+y\le16$: $0\le16$ is true, so shade the side containing the origin. For $x+y\ge5$: $0\ge5$ is false, so shade the other side. Technology (graphing software) can draw and shade each inequality for you.

The feasible region is where all the shaded regions overlap: every point inside satisfies every constraint. Its corners are vertices. Find a vertex by solving the two boundary equations that meet there. For $2x+y=16$ and $x+2y=14$: from the first, $y=16-2x$. Substitute: $x+2(16-2x)=14$, so $-3x=-18$, $x=6$ and $y=4$. The vertex is $(6,4)$. The other vertices come from the axes: $(0,0)$, $(8,0)$, $(0,7)$. Check a point is feasible by substituting it into every inequality. $(8,7)$ fails because $2(8)+7=23>16$.

The objective function is the quantity to maximise (profit, people fed) or minimise (cost, time), such as $P=30x+20y$. The best value always occurs at a vertex of the feasible region. Evaluate the objective function at every vertex and choose the largest (to maximise) or smallest (to minimise). For vertices $(0,0),(8,0),(0,7),(6,4)$ and $P=30x+20y$: $0,240,140,260$. The maximum profit is \260$at$(6,4)$. Minimising works the same way. For$C=2x+3y$with$x+y\ge6$,$x\ge1$,$y\ge1$, the vertices are$(1,5)$and$(5,1)$, giving$17$and$13$, so the minimum cost is$13$at$(5,1)$. If an objective line is parallel to an edge, two vertices tie and every point on that edge is optimal.

1. Define the variables. 2. Write the constraints and the objective function. 3. Draw the feasible region (or find its vertices by solving pairs of equations). 4. Evaluate the objective function at each vertex. 5. Write the answer in context. Example: a charity with 40 kg of rice and 36 kg of lentils packs $x$ Type A and $y$ Type B parcels. The constraints are $4x+2y\le40$ and $2x+3y\le36$, and people fed is $5x+4y$. The vertices are $(0,0)$, $(10,0)$, $(0,12)$, $(6,8)$, giving $0,50,48,62$. The best plan is 6 Type A and 8 Type B parcels, feeding 62 people. If the variables must be whole numbers, check that the optimal vertex is a whole-number point. If not, test nearby whole-number points inside the region.