Service for Solving Linear Programming Problems

Let good people see good solutions

Example 10. Solving a Linear Programming Problem Using a Graphical Method.
Region of Feasible Solutions is an Empty Set

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

F = x1 + x2

subject to the constraints:

 3 x1 + 5 x2 30
4 x1 - 3 x2 12
x1 - 3 x2 6

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.

3 x1 + 5 x2  ≤  30

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

Let x1 =0 => 5 x2 = 30 => x2 = 6

Let x2 =0 => 3 x1 = 30 => x1 = 10

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

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

Let's go back to the inequality.

3 x1 + 5 x2  ≤  30

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

5 x2  ≤  - 3 x1 + 30

x2  ≤  - 3/5 x1 + 6

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.

4 x1 - 3 x2  ≤  12

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

Let x1 =0 => - 3 x2 = 12 => x2 = -4

Let x2 =0 => 4 x1 = 12 => x1 = 3

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

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

Let's go back to the inequality.

4 x1 - 3 x2  ≤  12

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

- 3 x2  ≤  - 4 x1 + 12

x2  ≥  4/3 x1 - 4

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.

x1 - 3 x2  ≥  6

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

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

Let x2 =0 => x1 = 6

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

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

Let's go back to the inequality.

x1 - 3 x2  ≥  6

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

- 3 x2  ≥  - x1 + 6

x2  ≤  1/3 x1 - 2

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

This result does not have common points with the region of possible solutions of the previous step (see picture).

Result:

The region of feasible solutions is an empty set.









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