## Example ¹5. Solving a Linear Programming Problem Using the Simplex Method. |

F | = | x_{1} | + | 2 | x_{2} |

subject to the constraints:

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

2 | x_{1} | + | x_{2} | ≤ | 8 | |||

x_{2} | ≤ | 2 |

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.

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.

all constraints must be equations.

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

2 | x_{1} | + | x_{2} | ≤ | 8 | |||

x_{2} | ≤ | 2 |

x_{1} | + | 2 | x_{2} | + | S_{1} | = | 6 | ||||||||||

2 | x_{1} | + | x_{2} | + | S_{2} | = | 8 | ||||||||||

x_{2} | + | S_{3} | = | 2 |

S_{1} ≥ 0, S_{2} ≥ 0, S_{3} ≥ 0. The entered variables S_{1}, S_{2}, S_{3}, are called slack variables.

3. Finding the initial basis and the value of the function F which corresponds to the found initial 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.

Each basis is corresponded to one function value. One of them is the maximum 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 less 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.

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 positive coefficient (we can select any positive coefficient).

This is necessary in order to get a value of the function F no less 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.

x_{1} | + | 2 | x_{2} | + | S_{1} | = | 6 | ||||||||||

2 | x_{1} | + | x_{2} | + | S_{2} | = | 8 | ||||||||||

x_{2} | + | S_{3} | = | 2 |

There is a basis in our system. We can begin to solve our problem.

F | = | x_{1} | + | 2 | x_{2} |

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.

Function F contains only non-basic variables. Therefore, the value of the function F for this basis can be found in the mind.

x_{1} = 0 x_{2} = 0 S _{1} = 6 S_{2} = 8 S_{3} = 2 |
=> F = 0 |

The initial basis was found. The value of the function F corresponding to the initial basis was found.

4. Finding a maximum value of the function F.

Step ¹1

x_{1} | x_{2} | S_{1} | S_{2} | S_{3} | const. | Θ |

1 | 2 | 1 | 0 | 0 | 6 | 6 : 2 = 3 |

2 | 1 | 0 | 1 | 0 | 8 | 8 : 1 = 8 |

0 | 1 | 0 | 0 | 1 | 2 | 2 : 1 = 2 |

1 | 2 | 0 | 0 | 0 | F - 0 | |

1 | 0 | 1 | 0 | -2 | 2 | |

2 | 0 | 0 | 1 | -1 | 6 | |

0 | 1 | 0 | 0 | 1 | 2 | |

1 | 0 | 0 | 0 | -2 | F - 4 |

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)

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)

x_{1} = 0 S_{3} = 0 x _{2} = 2 S_{1} = 2 S_{2} = 6 |
=> F - 4 = 0 => F = 4 |

Step ¹2

x_{1} | x_{2} | S_{1} | S_{2} | S_{3} | const. | Θ |

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

2 | 0 | 0 | 1 | -1 | 6 | 6 : 2 = 3 |

0 | 1 | 0 | 0 | 1 | 2 | |

1 | 0 | 0 | 0 | -2 | F - 4 | |

1 | 0 | 1 | 0 | -2 | 2 | |

0 | 0 | -2 | 1 | 3 | 2 | |

0 | 1 | 0 | 0 | 1 | 2 | |

0 | 0 | -1 | 0 | 0 | F - 6 |

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)

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)

S_{1} = 0 S_{3} = 0 x _{1} = 2 x_{2} = 2 S_{2} = 2 |
=> F - 6 = 0 => F = 6 |

There are not any positive coefficients in the highlighted row. Therefore, the maximum value of the function F was found.

The coefficient is zero at position 5 in the highlighted row. There is not a basic variable in the column 5.

This allows us to find another solution in which F = 6.

This allows us to find another solution in which F = 6.

Step ¹3

x_{1} | x_{2} | S_{1} | S_{2} | S_{3} | const. | Θ |

1 | 0 | 1 | 0 | -2 | 2 | |

0 | 0 | -2 | 1 | 3 | 2 | 2 : 3 ≈ 0,67 |

0 | 1 | 0 | 0 | 1 | 2 | 2 : 1 = 2 |

0 | 0 | -1 | 0 | 0 | F - 6 | |

1 | 0 | 1 | 0 | -2 | 2 | |

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

0 | 1 | 0 | 0 | 1 | 2 | |

0 | 0 | -1 | 0 | 0 | F - 6 | |

1 | 0 | -1/3 | 2/3 | 0 | 10/3 | |

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

0 | 1 | 2/3 | -1/3 | 0 | 4/3 | |

0 | 0 | -1 | 0 | 0 | F - 6 |

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)

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)

S_{1} = 0 S_{2} = 0 x _{1} = 10/3 x_{2} = 4/3 S_{3} = 2/3 |
=> F - 6 = 0 => F = 6 |

From a geometric point of view, both solutions are points of space, i.e. form a line segment.

Any point (any solution) on this line segment will also be a solution.

© 2010-2024

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