Service for Solving Linear Programming Problems

Let good people look good solutions

Example 1. Solving the Linear Programming Problem Using the Graphical Method.
Function has a Maximum Value at the Point

This solution is done by the program presented on the site.
Problem:
Find the maximum value of the function

F = x1 - x2

subject to the constraints:

 x1 + x2 7
x2 5
x1 + x2 3
x2 2
x1 4

x1 ≥ 0     x2 ≥ 0
Solution:

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

To find the region of feasible solutions to this problem, it is necessary to solve each inequality of the constraint system. (see step 1 - step 5)

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

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.

Picture 0. Graphical Method of Solving LPP.

Step 1

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

x1 + x2  ≤  7

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

Let x1 =0 => x2 = 7

Let x2 =0 => x1 = 7

Two points were found: (0, 7) and (7 ,0)

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

Let's go back to the inequality.

x1 + x2  ≤  7

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

x2  ≤  - x1 + 7

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.

Picture 1. Graphical Method of Solving LPP.

Step 2

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

x2  ≤  5

We need to plot a straight line: x2 = 5

Now we can plot the straight line (2) through point (0,5) parallel to the OX1 axis

The inequality sign is  ≤
Therefore, we must consider points below 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.

Picture 2. Graphical Method of Solving LPP.

Step 3

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

x1 + x2  ≥  3

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

Let x1 =0 => x2 = 3

Let x2 =0 => x1 = 3

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

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

Let's go back to the inequality.

x1 + x2  ≥  3

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

x2  ≥  - x1 + 3

The inequality sign is  ≥
Therefore, we must consider points above 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.

Picture 3. Graphical Method of Solving LPP.

Step 4

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

x2  ≥  2

We need to plot a straight line: x2 = 2

Now we can plot the straight line (4) through point (0,2) parallel to the OX1 axis

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.

Picture 4. Graphical Method of Solving LPP.

Step 5

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

x1  ≤  4

We need to plot the straight line: x1 = 4

Now we can plot the straight line (5) through point (4,0) parallel to the OX2 axis

The inequality sign is  ≤
Therefore, we must consider points to the left of the straight line (5).

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

Picture 5. Graphical Method of Solving LPP.

Step 6

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

Vector C is not shown at scale because it is too long.

Picture 6. Graphical Method of Solving LPP.

Step 7

We will move a "red" straight line perpendicular to vector C from the upper left corner to the lower 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.

Function F has a maximum value at point A. (see picture)

Let's find the coordinates of point A.

Point A is on the straight line (4) and the straight line (5) at the same time.

 x2 = 2   =>   x1 = 4
x1 = 4 x2 = 2

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

F (A) = 1 * 4 - 1 * 2 = 2

Picture 7. Graphical Method of Solving LPP.

Result:

x1 = 4

x2 = 2

F max = 2

Comment: if there is any doubt that the function F has a maximum at point A, you should find the value of the function F at the point of interest and compare it to F (A).









2010-2020, for all questions please write to matematika1974@yandex.ru