Service for Solving Linear Programming Problems Русский

and other interesting typical problems

Home Graphical Method Simplex Method Transportation Problem Other

Simplex Method Calculator

The simplex method is universal. It allows you to solve any linear programming problems.
Тhe solution by the simplex method is not as difficult as it might seem at first glance.
This calculator only finds a general solution when the solution is a straight line segment.
You can solve your problem or see examples of solutions that this calculator has made.

Clear ► ▼ ▲

Enter integers or ordinary fractions. For example: 12, -3/4.

Find the   minimum     value of the function

F =  100 x1 + 340 x2

subject to the constraints:

1 x1 + 2 x2  ≥  3

3 x1 + 3 x2  ≥  5

2 x1 + 5 x2  ≥  6

x1 ≥ 0   x 2 ≥ 0  

Solve

Problem:

Find the minimum value of the function

F = 100 x1 + 340 x2
subject to the constraints:

x1 + 2 x2 ≥ 3

3 x1 + 3 x2 ≥ 5

2 x1 + 5 x2 ≥ 6

x1 ≥ 0    x2 ≥ 0    

Solution:

1.This is a necessary condition for solving the problem:

the numbers on the right parts of the constraint system must be non-negative.
This condition is done.

2. This is a necessary condition for solving the problem:

all constraints must be equations.

x1 + 2 x2 ≥ 3

3 x1 + 3 x2 ≥ 5

2 x1 + 5 x2 ≥ 6

x1 + 2 x2 - S1 = 3

3 x1 + 3 x2 - S2 = 5

2 x1 + 5 x2 - S3 = 6

S1 ≥ 0, S2 ≥ 0, S3 ≥ 0.   The entered variables S1, S2, S3, are called slack variables.

3. Finding the initial basis and the value of the function F which corresponds to the found initial basis.

What is a basis?
A variable is called a basic variable for an equation if it enters into this equation with a coefficient of one and does not enter into other
equations system (provided that there is a non-negative number on the right side of the equation).
If each equation has a basic variable, then they say that the system has a basis.
Variables that are not basic are called non-basic.

What is the idea of the simplex method?

Each basis is corresponded to one function value. One of them is the minimum value of the function F.
We will move from one basis to another.
The next basis will be chosen in such a way that the value of the function F will be no more than we have now.
Obviously, the number of possible bases for any problem is not very large.
So sooner or later the answer will be received.

How will we move from one basis to another?

It is more convenient to record the solution in the form of tables. Each row of the table is equivalent to a system equation. The highlighted
row consists of the coefficients of the function (see the table below). This allows us not to rewrite variables every time. It saves time.
In the highlighted row, select a maximum negative coefficient (we can select any negative coefficient).
This is necessary in order to get a value of the function F no more than we have.
Column is selected.
For the positive coefficients of the selected column, we count the coefficient Θ and select the minimum value.
This is necessary in order to get non-negative numbers in the right part of the equations after moving to another basis.
Row is selected.
An element is found that will be basic. Next, we will need to calculate.

Does our system have a basis?

x1 + 2 x2 - S1 = 3

3 x1 + 3 x2 - S2 = 5

2 x1 + 5 x2 - S3 = 6
There is not a basis in our system. We cannot begin to solve our problem.
We need to find it. To do this, we will solve an auxiliary problem.
If there is not a basic variable in the equation, add an artificial variable to it.

x1 + 2 x2 - S1 + R1 = 3

3 x1 + 3 x2 - S2 + R2 = 5

2 x1 + 5 x2 - S3 + R3 = 6

R1 ≥ 0, R2 ≥ 0, R3 ≥ 0.   The entered variables R1, R2, R3 are called artificial variables.

Let's consider a function W and we will find its minimum value.

W = R1 + R2 + R3

W = ( 3 - x1 - 2 x2 + S1 ) + R2 + R3 = 3 - x1 -2 x2 + S1 + R2 + R3

W = 3 - x1 -2 x2 + S1 + ( 5 - 3 x1 - 3 x2 + S2 ) + R3 = 8 -4 x1 -5 x2 + S1 + S2 + R3

W = 8 -4 x1 -5 x2 + S1 + S2 + ( 6 - 2 x1 - 5 x2 + S3 ) = 14 -6 x1 -10 x2 + S1 + S2 + S3

Non-basic variables are zero. In the mind, we can find the values of the basic variables. (see system)
Function W contains only non-basic variables. Therefore, the value of the function W for this basis can be found in the mind.
x1 = 0   x2 = 0   S1 = 0   S2 = 0   S3 = 0  
=> W = 14
R1 = 3   R 2 = 5   R 3 = 6  

Step №1
x1 x2 S1 S2 S3 R1 R2 R3 const. Θ

1 2 -1 0 0 1 0 0 3 3 : 2 = 1,5

3 3 0 -1 0 0 1 0 5 5 : 3 ≈ 1,667

2 5 0 0 -1 0 0 1 6 6 : 5 = 1,2

-6 -10 1 1 1 0 0 0 W - 14

1 2 -1 0 0 1 0 0 3

3 3 0 -1 0 0 1 0 5

2/5 1 0 0 -1/5 0 0 1/5 6/5

-6 -10 1 1 1 0 0 0 W - 14

1/5 0 -1 0 2/5 1 0 -2/5 3/5

9/5 0 0 -1 3/5 0 1 -3/5 7/5

2/5 1 0 0 -1/5 0 0 1/5 6/5

-2 0 1 1 -1 0 0 2 W-2

Non-basic variables are zero. In the mind, we can find the values of the basic variables. (see table)
Function W contains only non-basic variables. Therefore, the value of the function W for this basis can be found in the mind. (see the
highlighted row in the table)
x1 = 0   S1 = 0   S2 = 0   S3 = 0   R3 = 0  
=> W - 2 = 0   => W = 2
x2 = 6/5   R1 = 3/5   R2 = 7/5  

Step №2
x1 x2 S1 S2 S3 R1 R2 R3 const. Θ
 1/5 0 -1 0 2/5 1 0 -2/5 3/5 3/5 : 1/5 = 3

9/5 0 0 -1 3/5 0 1 -3/5 7/5 7/5 : 9/5 ≈ 0,778

2/5 1 0 0 -1/5 0 0 1/5 6/5 6/5 : 2/5 = 3

-2 0 1 1 -1 0 0 2 W-2

1/5 0 -1 0 2/5 1 0 -2/5 3/5

1 0 0 -5/9 1/3 0 5/9 -1/3 7/9

2/5 1 0 0 -1/5 0 0 1/5 6/5

-2 0 1 1 -1 0 0 2 W-2

0 0 -1 1/9 1/3 1 -1/9 -1/3 4/9

1 0 0 -5/9 1/3 0 5/9 -1/3 7/9

0 1 0 2/9 -1/3 0 -2/9 1/3 8/9

0 0 1 -1/9 -1/3 0 10/9 4/3 W - 4/9

Non-basic variables are zero. In the mind, we can find the values of the basic variables. (see table)
Function W contains only non-basic variables. Therefore, the value of the function W for this basis can be found in the mind. (see the
highlighted row in the table)
S1 = 0   S 2 = 0   S 3 = 0   R 2 = 0   R 3 = 0  
=> W - 4/9 = 0   => W = 4/9
x1 = 7/9   x2 = 8/9   R1 = 4/9  

Step №3
x1 x2 S1 S2 S3 R1 R2 R3 const. Θ

0 0 -1 1/9 1/3 1 -1/9 -1/3 4/9 4/9 : 1/3 ≈ 1,333

1 0 0 -5/9 1/3 0 5/9 -1/3 7/9 7/9 : 1/3 ≈ 2,333

0 1 0 2/9 -1/3 0 -2/9 1/3 8/9

0 0 1 -1/9 -1/3 0 10/9 4/3 W - 4/9

0 0 -3 1/3 1 3 -1/3 -1 4/3

1 0 0 -5/9 1/3 0 5/9 -1/3 7/9

0 1 0 2/9 -1/3 0 -2/9 1/3 8/9

0 0 1 -1/9 -1/3 0 10/9 4/3 W - 4/9

0 0 -3 1/3 1 3 -1/3 -1 4/3

1 0 1 -2/3 0 -1 2/3 0 1/3

0 1 -1 1/3 0 1 -1/3 0 4/3

0 0 0 0 0 1 1 1 W-0

Non-basic variables are zero. In the mind, we can find the values of the basic variables. (see table)
Function W contains only non-basic variables. Therefore, the value of the function W for this basis can be found in the mind. (see the
highlighted row in the table)
S1 = 0   S 2 = 0   R 1 = 0   R 2 = 0   R 3 = 0  
=> W - 0 = 0   => W = 0
x1 = 1/3   x2 = 4/3   S3 = 4/3  
There are not any negative coefficients in the highlighted row. Therefore, the minimum value of the function W was found.
The basis was found without artificial variables.
The columns corresponding to artificial variables can be deleted.
As a result, our system has the form:

- 3 S1 + 1/3 S2 + S3 = 4/3

x1 + S1 - 2/3 S2 = 1/3

x2 - S1 + 1/3 S2 = 4/3

F = 100 x1 + 340 x2

F = 100 * ( 1/3 - S1 + 2/3 S2 ) + 340 x2 = 100/3 + 340 x2 -100 S1 + 200/3 S2

F = 100/3 + 340 * ( 4/3 + S1 - 1/3 S2 ) -100 S1 + 200/3 S2 = 1460/3 + 240 S1 -140/3 S2

Non-basic variables are zero. In the mind, we can find the values of the basic variables. (see system)
Function F contains only non-basic variables. Therefore, the value of the function F for this basis can be found in the mind.
S1 = 0   S 2 = 0  
=> F = 1460/3
x1 = 1/3   x2 = 4/3   S3 = 4/3  
The initial basis was found. The value of the function F corresponding to the initial basis was found.

4. Finding a minimum value of the function F.

Step №1
x1 x2 S1 S2 S3 const. Θ

0 0 -3 1/3 1 4/3 4/3 : 1/3 = 4

1 0 1 -2/3 0 1/3

0 1 -1 1/3 0 4/3 4/3 : 1/3 = 4

0 0 240 -140/3 0 F - 1460/3

0 0 -9 1 3 4

1 0 1 -2/3 0 1/3

0 1 -1 1/3 0 4/3

0 0 240 -140/3 0 F - 1460/3

0 0 -9 1 3 4

1 0 -5 0 2 3

0 1 2 0 -1 0

0 0 -180 0 140 F - 300

Non-basic variables are zero. In the mind, we can find the values of the basic variables. (see table)
Function F contains only non-basic variables. Therefore, the value of the function F for this basis can be found in the mind. (see the
highlighted row in the table)
S1 = 0   S 3 = 0  
=> F - 300 = 0   => F = 300
x1 = 3   x2 = 0   S2 = 4  

Step №2
x1 x2 S1 S2 S3 const. Θ

0 0 -9 1 3 4
 1 0 -5 0 2 3

0 1 2 0 -1 0 0:2=0

0 0 -180 0 140 F - 300

0 0 -9 1 3 4

1 0 -5 0 2 3

0 1/2 1 0 -1/2 0

0 0 -180 0 140 F - 300

0 9/2 0 1 -3/2 4

1 5/2 0 0 -1/2 3

0 1/2 1 0 -1/2 0

0 90 0 0 50 F - 300

Non-basic variables are zero. In the mind, we can find the values of the basic variables. (see table)
Function F contains only non-basic variables. Therefore, the value of the function F for this basis can be found in the mind. (see the
highlighted row in the table)
x2 = 0   S3 = 0  
=> F - 300 = 0   => F = 300
x1 = 3   S1 = 0   S2 = 4  
There are not any negative coefficients in the highlighted row. Therefore, the minimum value of the function F was found.
Result:
x1 = 3   x2 = 0  
Fmin = 300

Back to top What do you think about this?

© 2010-2022

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