## Example ¹4. Solving a Linear Programming Problem Using a Graphical Method. |

x_{1} | + | x_{2} | ≥ | 6 | ||

3 x_{1} | - | x_{2} | ≥ | 3 | ||

x_{1} | - | x_{2} | ≤ | 2 | ||

x_{2} | ≤ | 6 | ||||

x_{1} | ≤ | 5 |

x

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: x_{1} ≥ 0 x_{2} ≥ 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.

x_{1} + x_{2} ≥ 6

We need to plot a straight line: x_{1} + x_{2} = 6

Let x_{1} =0 => x_{2} = 6

Let x_{2} =0 => x_{1} = 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.

x_{1} + x_{2} ≥ 6

We need to transform the inequality so that only x_{2} is on the left side.

x_{2} ≥ - x_{1} + 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 x_{1} - x_{2} ≥ 3

We need to plot a straight line: 3 x_{1} - x_{2} = 3

Let x_{1} =0 => - x_{2} = 3 => x_{2} = -3

Let x_{2} =0 => 3 x_{1} = 3 => x_{1} = 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 x_{1} - x_{2} ≥ 3

We need to transform the inequality so that only x_{2} is on the left side.

- x_{2} ≥ - 3 x_{1} + 3

x_{2} ≤ 3 x_{1} - 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.

x_{1} - x_{2} ≤ 2

We need to plot a straight line: x_{1} - x_{2} = 2

Let x_{1} =0 => - x_{2} = 2 => x_{2} = -2

Let x_{2} =0 => x_{1} = 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.

x_{1} - x_{2} ≤ 2

We need to transform the inequality so that only x_{2} is on the left side.

- x_{2} ≤ - x_{1} + 2

x_{2} ≥ x_{1} - 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.

x_{2} ≤ 6

We need to plot a straight line: x_{2} = 6

Now we can plot the straight line (4) through point (0,6) parallel to the OX_{1} axis

The inequality sign is ≤

Therefore, we must consider points below the straight line (4).

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

Step ¹5

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

x_{1} ≤ 5

We need to plot a straight line: x_{1} = 5

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

The inequality sign is ≤

Therefore, we must consider points to the left of the straight line (5).

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 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.

x_{1} | + | x_{2} | = | 6 | => | x_{1} = 9/4 | ||

3 x_{1} | - | x_{2} | = | 3 | x_{2} = 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.

x_{1} | + | x_{2} | = | 6 | => | x_{1} = 4 | ||

x_{1} | - | x_{2} | = | 2 | x_{2} = 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.

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

© 2010-2021

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