# Service for Solving Linear Programming Problems

Let good people see good solutions
Русский

## Example №3. Solving the Linear Programming Problem Using the Graphical Method. Function has a Maximum Value on the Line Segment

This solution has been done by the calculator presented on the site.
Problem:
Find the maximum value of the function

F = x1 + 2 x2

subject to the constraints: x1 + 2 x2 ≤ 10 x1 + 2 x2 ≥ 2 2 x1 + x2 ≤ 10 3 x1 + x2 ≥ 3

x1 ≥ 0     x2 ≥ 0
Solution:

Points whose coordinates satisfy all the inequalities of the constraint system are called a region of feasible solutions.

It is necessary to solve each inequality of the constraint system to find the region of feasible solutions to this problem. (see step 1 - step 4)

The last two steps are necessary to get an answer. (see step 5 - step 6)

This is a standard solution plan. If the region of feasible solutions is a point or an empty set then the solution will be shorter.

By the condition of the problem: x1 ≥ 0     x2 ≥ 0.

Now we have the region of feasible solutions shown in the picture. Step №1

Let's solve 1 inequality of the system of constraints.

x1 + 2 x2  ≤  10

We need to plot a straight line: x1 + 2 x2 = 10

Let x1 =0 => 2 x2 = 10 => x2 = 5

Let x2 =0 => x1 = 10

Two points were found: (0, 5) and (10 ,0)

Now we can plot the straight line (1) through the found two points.

Let's go back to the inequality.

x1 + 2 x2  ≤  10

We need to transform the inequality so that only x2 is on the left side.

2 x2  ≤  - x1 + 10

x2  ≤  - 1/2 x1 + 5

The inequality sign is  ≤
Therefore, we must consider points below the straight line (1).

Let's combine this result with the previous picture.
Now we have the region of feasible solutions shown in the picture. Step №2

Let's solve 2 inequality of the system of constraints.

x1 + 2 x2  ≥  2

We need to plot a straight line: x1 + 2 x2 = 2

Let x1 =0 => 2 x2 = 2 => x2 = 1

Let x2 =0 => x1 = 2

Two points were found: (0, 1) and (2 ,0)

Now we can plot the straight line (2) through the found two points.

Let's go back to the inequality.

x1 + 2 x2  ≥  2

We need to transform the inequality so that only x2 is on the left side.

2 x2  ≥  - x1 + 2

x2  ≥  - 1/2 x1 + 1

The inequality sign is  ≥
Therefore, we must consider points above the straight line (2).

Let's combine this result with the previous picture.
Now we have the region of feasible solutions shown in the picture. Step №3

Let's solve 3 inequality of the system of constraints.

2 x1 + x2  ≤  10

We need to plot a straight line: 2 x1 + x2 = 10

Let x1 =0 => x2 = 10

Let x2 =0 => 2 x1 = 10 => x1 = 5

Two points were found: (0, 10) and (5 ,0)

Now we can plot the straight line (3) through the found two points.

Let's go back to the inequality.

2 x1 + x2  ≤  10

We need to transform the inequality so that only x2 is on the left side.

x2  ≤  - 2 x1 + 10

The inequality sign is  ≤
Therefore, we must consider points below the straight line (3).

Let's combine this result with the previous picture.
Now we have the region of feasible solutions shown in the picture. Step №4

Let's solve 4 inequality of the system of constraints.

3 x1 + x2  ≥  3

We need to plot a straight line: 3 x1 + x2 = 3

Let x1 =0 => x2 = 3

Let x2 =0 => 3 x1 = 3 => x1 = 1

Two points were found: (0, 3) and (1 ,0)

Now we can plot the straight line (4) through the found two points.

Let's go back to the inequality.

3 x1 + x2  ≥  3

We need to transform the inequality so that only x2 is on the left side.

x2  ≥  - 3 x1 + 3

The inequality sign is  ≥
Therefore, we must consider points above the straight line (4).

Let's combine this result with the previous picture.
Now we have the region of feasible solutions shown in the picture. Step №5

We need to plot the vector C = (1, 2), whose coordinates are the coefficients of the function F. Step №6

We will move a "red" straight line perpendicular to vector C from the lower left corner to the upper right corner.

The function F has a minimum value at the point where the "red" straight line crosses the region of feasible solutions for the first time.

The function F has a maximum value at the point where the "red" straight line crosses the region of feasible solutions for the last time.

There is an assumption that the function F has a maximum value at points A and B at the same time (see picture). Let's check it.

The coordinates of point A (0,5) are known. (see step 1)

Let's calculate the value of the function F at point A (0,5).

F (A) = 1 * 0 + 2 * 5 = 10

Let's find the coordinates of point B.

Point B is on the straight line (1) and the straight line (3) at the same time. x1 + 2 x2 = 10 => x1 = 10/3 2 x1 + x2 = 10 x2 = 10/3

Let's calculate the value of the function F at point B (10/3,10/3).

F (B) = 1 * 10/3 + 2 * 10/3 = 10

F(A) = F(B).

Then we can conclude that the function F has a maximum value at any point on the line segment AB. Result:

## F max = 10

Comment: changing the parameter t we can get the coordinates of any point of the line segment AB.