Sunday, April 27, 2008

Half-planes in linear programming

A half-plane is a region on a co-ordinated plane for which an inequality in x, y or both is true.

The idea of graphing a half-plane (such as 2x + 3y ≤ 6) is similar to graphing a line.
First change the inequality to an equation - graph 2x+3y = 6.
Remember how to do this?
Find two points on the line
  • set x=0, see what y is - giving you (0,2)
  • set y=0, see what x is - giving you (3,0).
Now you can graph the line.























But how do you find the half-plane 2x + 3y ≤ 6
In other words, on which side of this line will every single point obey the rule 2x + 3y ≤ 6 ?
To find out, you use a test point.
The easiest test point to use is (0,0) - remember you can't use this if the line goes through the origin and you will know if goes through the origin if there is no constant (e.g. the line 2x + 3y = 0 goes through the origin).
Substitute the test point (0,0) into 2x + 3y ≤ 6 and we get
2(0) + 3(0) ≤ 6
0≤6
This last line is true, (0 is less than 6) so if 2x + 3y ≤ 6 is true for (0,0), it is also true for all other points on the same side of the line as (0,0).
So, draw arrows pointing towards the (0,0) side like this.


If your test point had produced result that wasn't true such as 8 ≤ 6, then the arrows would point towards the side of the line that did not contain the test point.














A typical exam part (a) type question would be:
Shade in the region of a plane which simultaneously satisfies the following inequalities:
  • 2x + 3y ≤ 6
  • x ≥ 1
  • y ≥ 0
The first one is already done.
The second one works like this:
Turn it into an equation x = 1 and graph this. Any point where x = 1 is on the line ((1,0), (1,1), (1,2) etc) so this line is the line that cuts the x-axis at 1 and is parallel to the y-axis.
Work out which way the arrow goes ... take a test point like (0,0) and see does it fit the inequality x ≥ 1.
Substituting into the inequality gives 0 ≥ 1 which is not true, so the half-plane we are looking for is on the other side, arrows pointing to the right.

Use the same logic to work out that y=0 is the equation for the x-axis. You can't use (0,0) as a test-point as it is on the line, so use another convenient point instead - e.g. (0,1).
Substituting into the inequality gives 1 ≥ 0 which is true, so this means that the test point is in the half-plane and that the arrows point upwards.
Last part of the question is to draw shade in the region which is in all 3 half-planes.



















Note that there are other ways this question could be asked. You could be given the diagram and be asked for the 3 inequalities that define a region.

This was the example we started looking at in class on Monday.

The vertical and horizontal lines should be easy now.
"Above the x-azis" means the inequality is y ≥ 0
"To the right of the y-axis" means the inequality is x ≥ 0

The diagonal line is more difficult.
You know that two points on the line are (4,0) and (0,3) so how can you get the equation of the line?

You have to resurrect your co-ordinate geometry.
First find the slope of the line
m = 3-0/0-4 = -3/4

Now put one of your points into the formula y-y1 = m(x-x1)
I'll choose (4,0)
This gives you:
y - 0 = -3/4(x - 4)
4y = -3x + 12
Rearranging this gives us the equation
3x + 4y = 12 ( which is the rule for being a point on the diagonal line).
But you want rule for being on the half-plane which is below and to the left of this line.
So you have to use a test-point. (0,0) is a good candidate here.

3x + 4y = 12
Left-hand-side works out as 3(0) + 4(0) which is 0.
Right hand side is 12.

Now you have to work out the direction of the inequality:
0 ? 12
Answer is that 0 < 12 so in this case the inequality that defines the half-plane in question is
3x + 4y ≤ 12

A few closing points:
  • If you are doing this question in your exam, make sure that you write out all three inequalities clearly.
  • On our course the half-planes are always defined using ≤ or ≥, not < or >.
  • Also, note that part (b) of this question will be concerned with positive x and y values (since they refer to real-world problems) , but in part (a) you could have lines that intercept the x and/or y-axes at negative numbers.

No comments: