Linear Programming

How to solve the linear programming problem: 1 example and its solution.

Example

Example

Solution

To graph the linear inequalities,
change the linear inequalities to slope-intercept form.

Change 3x + y ≤ 9 to slope-intercept form.
Then y ≤ -3x + 9.

Change x + 2y ≤ 8 to slope-intercept form.
Then y ≤ (-1/2)x + 4.

Set x + y = k.

To graph this linear equation,
change this to slope-intercept form.

Then y = -x + k.

The goal is to find the maximum value of the y-intercept k.

So the given linear inequalities are like this.
x ≥ 0
y ≥ 0
y ≤ -3x + 9
y ≤ (-1/2)x + 4

Graph the system of linear inequalities.

x ≥ 0, y ≥ 0 means the first quadrant.

So graph y ≤ -3x + 9 on the first quadrant.

Graph y ≤ (-1/2)x + 4 on the first quadrant.

Color the intersecting region.
This colored region is the solution of the system.

See y = -x + k.

The y-intercept is +k.

The slope is -1.
The slope is easier than the slope of y = -3x + 9, 3.
The slope is steeper than the slope of y = (-1/2)x + 4, (-1/2).

So, to make the y-intercept, k, maximum,
y = -x + k should pass through
the intersecting point of y = -3x + 9 and y = (-1/2)x + 4.

So find the coordinates of the intersecting point
of y = -3x + 9 and y = (-1/2)x + 4.

Set -3x + 9 = (-1/2)x + 4.

Solve -3x + 9 = (-1/2)x + 4.
Then x = 2.

Put x = 2 into y = -3x + 9.
Then y = -3⋅2 + 9.

-3⋅2 + 9 = -6 + 9 = 3

x = 2
y = 3

So the intersecting point is (2, 3).

x + y = k passes through (2, 3).
So put (2, 3) into x + y = k.
Then k = 2 + 3.

2 + 3 = 5

So k = 5 is the maximum value of x + y.