Service for Solving Linear Programming Problems

and other interesting typical problems
Ðóññêèé

Example ¹4. Solving a Linear Programming Problem Using a Graphical Method.
Function has a Minimum Value on the Line Segment

This solution was made using the calculator presented on the site.
Problem:
Find the minimum value of the function

F = 2 x1 + 2 x2

subject to the constraints:

Çíàê ñèñòåìû x1 + x2 6
3 x1 - x2 3
x1 - x2 2
x2 6
x1 5

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 5)

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

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.

See the plan for solving this problem in pictures

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 + x2  ≥  6

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

Let x1 =0 => x2 = 6

Let x2 =0 => x1 = 6

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

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

Let's go back to the inequality.

x1 + x2  ≥  6

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

x2  ≥  - x1 + 6

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

3 x1 - x2  ≥  3

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

Let x1 =0 => - x2 = 3 => 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 (2) 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

x2  ≤  3 x1 - 3

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.

Step ¹3

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

x1 - x2  ≤  2

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

Let x1 =0 => - x2 = 2 => x2 = -2

Let x2 =0 => x1 = 2

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

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

Let's go back to the inequality.

x1 - x2  ≤  2

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

- x2  ≤  - x1 + 2

x2  ≥  x1 - 2

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.

Step ¹4

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

x2  ≤  6

We need to plot a straight line: x2 = 6

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

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

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

x1  ≤  5

We need to plot a straight line: x1 = 5

Now we can plot the straight line (5) through point (5,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.

Step ¹6

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

Step ¹7

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

The "red" straight line is called the level line. At each point of the level line, the value of the function F is a constant value.

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 minimum value at points A and B at the same time (see picture). Let's check it.

Let's find the coordinates of point A.

Point A is on the straight line (1) and on the straight line (2) at the same time.

Çíàê ñèñòåìû x1 + x2 = 6   =>   x1 = 9/4
3 x1 - x2 = 3 x2 = 15/4

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

F (A) = 2 * 9/4 + 2 * 15/4 = 12

Let's find the coordinates of point B.

Point B is on the straight line (1) and on the straight line (3) at the same time.

Çíàê ñèñòåìû x1 + x2 = 6   =>   x1 = 4
x1 - x2 = 2 x2 = 2

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

F (B) = 2 * 4 + 2 * 2 = 12

F(A) = F(B).

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

Result:

x1 = 9/4 * t + 4 * ( 1 - t )

x2 = 15/4 * t + 2 * ( 1 - t )

0 ≤ t ≤ 1

F min = 12

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








© 2010-2024

If you have any comments, please write to siteReshmat@yandex.ru