A. Feasible Region and Points

Constraints mean that we cannot just take any x and y when looking for the x and y that optimise our objective function. If we think of the variables x and y as a point (x,y) in the xy-plane then we call the set of all points in the xy—plane that satisfy our constraints the feasible region. Any point in the feasible region is called a feasible point.
For example, the constraints

x≥0,y≥0
mean that every (x,y) we can consider must lie in the first quadrant of the my plane. The constraint
x≥y
means that every (x,y) must lie on or below the line y=x and the constraint
x≤20
means that an must lie on or to the left of the line x=20.
We can use these constraints to draw the feasible region as shown by the shaded region in Figure A.
Important: The constraints are used to create bounds of the solution.

Figure A: The feasible region corresponding to the constraints
x≥0,y≥0, x≥y and x≤20.

Important:

ax+by=c	If b≠0, feasible points must lie on the line If b=0, feasible points must lie on the line x=c/a.
ax+by≤c	If b≠0, feasible points must lie on or below the line If b=0, feasible points must lie on or to the left of the line x=c/a.

When a constraint is linear, it means that it requires that any feasible point (x,y) lies on one side of or on a line. Interpreting constraints as graphs in the xy plane is very important since it allows us to construct the feasible region such as in Figure A.

B. Linear Programming and the Feasible Region

If the objective function and all ofthe constraints are linear then we call the problem of optimising the objective function subject to these constraints a linear program. All optimisation problems we will look at will be linear programs.

The major consequence of the constraints being linear is that the feasible region is always a polygon. This is evident since the constraints that define the feasible region all contribute a line segment to its boundary (see Figure A). It is also always true that the feasible region is a convex polygon.

The objective function being linear means that the feasible point(s) that gives the solution of a linear program always lies on one of the vertices of the feasible region. This is very important since, as we will soon see, it gives us a way of solving linear programs.

We will now see why the solutions of a linear program always lie on the vertices of the feasible region. Firstly, note that if we think of f(x,y) as lying on the z axis, then the function f(x,y)=ax+by (where a and b are real numbers) is the definition of a plane. If we solve for y in the equation defining the objective function then

What this means is that if we find all the points where f(x,y)=c for any real number c (i.e. f(x,y) is constant with a value of c), then we have the equation of a line. This line we call a level line of the objective function.

Consider again the feasible region described in Figure A. Lets say that we have the objective function
f(x,y)=x-2y…(i)
with this feasible region. If we consider Equation (i) corresponding to

f(x,y)=-20
then we get the level line
y=½x+10
which has been drawn in Figure B. Level lines corresponding to
f(x,y)=-10 or y=½x+5
f(x,y)=0 or y=½x
f(x,y)=10 or y=½x-5
f(x,y)=20 or y=½x-10
have also been drawn in. It is very important to realise that these are not the only level lines; in fact, there are infinitely many of them and they are all parallel to each other. Remember that if we look at any one level line f(x,y) has the same value for every point (x,y) that lies on that line. Also, f(x,y) will always have different values on different level lines.

Figure B: The feasible region corresponding to the constraints x≥0,y≥0, x≥y and x≤20 with objective function f(x,y)=x-2y. The dashed lines represent various level lines of f(x,y).

If a ruler is placed on the level line corresponding to f(x,y)=-20 in Figure B and moved down the page parallel to this line then it is clear that the ruler will be moving over level lines which correspond to larger values of f(x,y). So if we wanted to maximise f(x,y) then we simply move the ruler down the page until we reach the ‘‘lowest’’ point in the feasible region. This point will then be the feasible point that maximises f(x,y). Similarly, if we wanted to minimise f(x,y) then the “highest” feasible point will give the minimum value of f(x,y).

Since our feasible region is a polygon, these points will always lie on vertices in the feasible region. The fact that the value of our objective function along the line of the ruler increases as we move it down and decreases as we move it up depends on this particular example. Some other examples might have that the function increases as we move the ruler up and decreases as we move it down.

It is a general property, though, of linear objective functions that they will consistently increase or decrease as we move the ruler up or down. Knowing which direction to move the ruler in order to maximise/minimise f(x,y)=ax+by is as simple as looking at the sign of b (i.e. “is b negative, positive or zero?”). If b is positive, then f(x,y) increases as we move the ruler up and f(x,y) decreases as we move the ruler down. The opposite happens for the case when b is negative: f(x,y) decreases as we move the ruler up and f(x,y) increases as we move the ruler down. If b=0 then we need to look at the sign of a.

If a is positive then f(x,y) increases as we move the ruler to the right and decreases if we move the ruler to the left. Once again, the opposite happens for a negative. If we look again at the objective function mentioned earlier,

f(x,y)=x-2y
with a=1 and b=-2, then we should find that f(x,y) increases as we move the ruler down the page since b=-2<0. This is exactly what we found happening in Figure B.

The main points about linear programming we have encountered so far are
● The feasible region is always a polygon.
● Solutions occur at vertices of the feasible region.
● Moving a ruler parallel to the level lines of the objective function up/down to the top/bottom of the feasible region shows us which of the vertices is the solution.
● The direction in which to move the ruler is determined by the sign of b and also possibly by the sign of a.

These points are sufficient to determine a method for solving any linear program.

Method: Linear Programming

If we wish to maximise the objective function f(x,y) then:
1. Find the gradient of the level lines of f(x,y) (this is always going to be -a/b as we saw in Equation

)
2. Place your ruler on the xy plane, making a line with gradient -a/b (i.e. b units on the x-axis and –a units on the y-axis)
3. The solution of the linear program is given by appropriately moving the ruler. Firstly we need to check whether b is negative, positive or zero.

A) If (b>0, move the ruler up the page, keeping the ruler parallel to the level lines all the time, until it touches the “highest” point in the feasible region. This point is then the solution.

B) If b<0, move the ruler in the opposite direction to get the solution at the “lowest” point in the feasible region.

C) If b=0, check the sign of a

i. If a<0 move the ruler to the "leftmost" feasible point. This point is then the solution.

ii. If a>0 move the ruler to the “rightmost” feasible point. This point is then the solution.

📌 Worked Example: Search Line Method
Question: As a production planner at a factory manufacturing lawn cutters yourjob will be to advise the management on how many of each model should be produced per week in order to maximise the profit on the local production. The factory is producing two types of lawn cutters: Quadrant and Pentagon. Two of the production processes that the lawn cutters must go through are: bodywork and engine work.
● The factory cannot operate for less than 360 hours on engine work for the lawn cutters.
● The factory has a maximum capacity of 480 hours for bodywork for the lawn cutters.
● Half an hour of engine work and half an hour of bodywork is required to produce one Quadrant.
● One third of an hour of engine work andone fifth of an hour of bodywork is required to produce one Pentagon.
● The ratio of Pentagon lawn cutters to Quadrant lawn cutters produced per week must be at least 3:2.
● A minimum of 200 Quadrant lawn cutters must be produced per week.

Let the number of Quadrant lawn cutters manufactured in a week be x.
Let the number of Pentagon lawn cutters manufactured in a week be y.
Two of the constraints are:

x≥200
3x+2y≥2,160
1. Write down the remaining constraints in terms of x and y to represent the abovementioned information.
2. Use graph paper to represent the constraints graphically.
3. Clearly indicate the feasible region by shading it.
4. If the profit on one Quadrant lawn cutter is $1,200 and the profit on one Pentagon lawn cutter is $400, write down an equation that will represent the profit on the lawn cutters.
5. Using a search line and your graph, determine the number of Quadrant and Pentagon lawn cutters that will yield a maximum profit.
6. Determine the maximum profit per week.
Answer
Step 1: Remaining constraints:
½x+⅕≤480
y/x≥3/2
Step 2: Graphical representation

Step 3: Profit equation
P=1,200x+400y
Step 4: Maximum profit
P=1,200(600)+400(900)
P=$1,080,000
💎 Iso-Profit Line Method — Corner-Point Method — Sensitivity Analysis 👈