Service for Solving Linear Programming Problems

Let good people see good solutions

Example 6. Solving a Linear Programming Problem Using a Graphical Method.
Function has a Minimum Value on the Ray

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

F = 3 x1 - x2

subject to the constraints:

 x1 - x2 8
3 x1 - x2 3
2 x1 + x2 4

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

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

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  ≤  8

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

Let x1 =0 => - x2 = 8 => x2 = -8

Let x2 =0 => x1 = 8

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

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

Let's go back to the inequality.

x1 - x2  ≤  8

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

- x2  ≤  - x1 + 8

x2  ≥  x1 - 8

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.

2 x1 + x2  ≥  4

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

Let x1 =0 => x2 = 4

Let x2 =0 => 2 x1 = 4 => x1 = 2

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

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

Let's go back to the inequality.

2 x1 + x2  ≥  4

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

x2  ≥  - 2 x1 + 4

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

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

Step 5

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.

There is an assumption that the function F has a minimum value on the ray, which has its start at point A. (see picture)

Let's find the coordinates of point A.

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

 3 x1 - x2 = 3   =>   x1 = 7/5
2 x1 + x2 = 4 x2 = 6/5

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

F (A) = 3 * 7/5 - 1 * 6/5 = 3

The coordinates of any point of the ray can be written as follows:

x1 = 7/5 + 1 * t

x2 = 6/5 + 3 * t

t ≥ 0

Suppose that if t = 1 then we have a point B.
Let's find the coordinates of point B.

x1 = 7/5 + 1 * 1 = 12/5

x2 = 6/5 + 3 * 1 = 21/5

Let's calculate the value of the function F at point B (12/5,21/5).

F (B) = 3 * 12/5 - 1 * 21/5 = 3

F(A) = F(B).

Then we can conclude that the function F has a miniimum value at any point on the ray which has its start at point A.

Result:

x1 = 7/5 + 1 * t

x2 = 6/5 + 3 * t

t ≥ 0

Fmin = 3









2010-2020 If you have any comments, please write to matematika1974@yandex.ru