Search

Define maximum value of the objective function F(X) =  x1  + x2   the following conditions-restrictions.
 1.01 x1   + 9.45 x2 <=110.0
 0.18 x1   + 3.25 x2 <=21.4
 2000.0 x1   + 5000.0 x2 <=15000.0
To build support program is the first system of inequalities give the system of equations by introducing additional variables.
 1.01x1 + 9.45x2 + 1x3 + 0x4 + 0x5 = 110.0
 0.18x1 + 3.25x2 + 0x3 + 1x4 + 0x5 = 21.4
 2000.0x1 + 5000.0x2 + 0x3 + 0x4 + 1x5 = 15000.0
The matrix of coefficients A = a(ij) of this system of equations has the form:

Basic variables are variables that are only in one equation system of restrictions and, moreover, with a single coefficient.
We solve the system of equations for the basic variables:
  x3  , x4  , x5  
Assuming that the free variables are equal to 0, we obtain the first support program:
  X1 = (0,0,110,21.4,15000)
Since the problem is solved at a maximum, then the leading column is selected by the maximum negative number and the index line. All transformations were carried out as long as they are not in the index line positive elements.
Turn to the basic algorithm, the simplex method.

Plan
Basis
Â
x 1
x 2
x 3
x 4
x 5
min

1
x3
110
1.01
9.45
1
0
0
11.64

 
x4
21.4
0.18
3.25
0
1
0
6.58

 
x5
15000
2000
5000
0
0
1
3

The indexline
F(X1)
0
-1
-1
0
0
0
0

Iteration ¹0
Current support program is suboptimal, as in the index line are the coefficients of negative
As the leading select the column corresponding to variable x2 , as the largest coefficient in absolute.
Calculate the values D i the rows as the quotient of division
and from them choose the smallest:

Therefore, 3-th row is the leading Allow the element is 5000 and is located at the intersection of the lead column and the lead line
 Forming part of the next simplex table.
 Instead variable x the plan 1 will include the variable x2
String corresponding to the variable x2  in the plan 1, obtained by dividing all the elements of row x5 plan's 0 allowing for an element ÐÝ=5000 In place of allowing an element in terms of 1 obtain 1.
In the remaining cells of column x2  plan's 1 write zeros.Thus, the new plan 1 filled row x2 and column x2. All other elements of the new plan, 1, including elements of the index line, defined by the rule of the rectangle.
To do this, choose from the old plan, four of which are located at the vertices of the rectangle, and always include an element permitting AE.
 ÍÝ = OE - (À*Â)/AE
 OE - element of the old plan, AE - allowing element (5000), À è Â - elements of the old plan, forming a rectangle with the elements of the OE and AE.
Represent the calculation of each element in a table:

 B
 x 1
 x 2
 x 3
 x 4
 x 5













 15000 / 5000 = 3
 2000 / 5000 = 0.4
 5000 / 5000 = 1
 0 / 5000 = 0
 0 / 5000 = 0
 1 / 5000 = 0







 

  Plan
 Basis
 Â
 x 1
 x 2
 x 3
 x 4
 x 5
 min

 2
 x3
 81.65
 -2.77
 0
 1
 0
 -0
 0

 
 x4
 11.65
 -1.12
 0
 0
 1
 -0
 0

 
 x2
 3
  0.4
 1
 0
 0
 0
  7.5

 The indexline
 F(X2)
 3
  -0.6
 0
 0
 0
 0
 0

Iteration ¹1
Current support program is suboptimal, as in the index line are the coefficients of negative
As the leading select the column corresponding to variable x1 , as the largest coefficient in absolute.
Calculate the values D i the rows as the quotient of division
and from them choose the smallest:

Therefore, 3-th row is the leading Allow the element is 0.4 and is located at the intersection of the lead column and the lead line
Forming part of the next simplex table.
Instead variable x the plan 2 will include the variable x1
String corresponding to the variable x1  in the plan 2, obtained by dividing all the elements of row x2 plan's 1 allowing for an element ÐÝ=0.4 In place of allowing an element in terms of 2 obtain 1.
In the remaining cells of column x1  plan's 2 write zeros.Thus, the new plan 2 filled row x1 and column x1 . All other elements of the new plan, 2, including elements of the index line, defined by the rule of the rectangle.
To do this, choose from the old plan, four of which are located at the vertices of the rectangle, and always include an element permitting AE.
 ÍÝ = OE - (À*Â)/AE
 OE - element of the old plan, AE - allowing element (0.4), À è Â - elements of the old plan, forming a rectangle with the elements of the OE and AE.
Represent the calculation of each element in a table:

 B
 x 1
 x 2
 x 3
 x 4
 x 5













 3 / 0.4 = 7.5
 0.4 / 0.4 = 1
 1 / 0.4 = 2.5
 0 / 0.4 = 0
 0 / 0.4 = 0
 0 / 0.4 = 0







 
End of iterations: an optimal plan
The final version of the simplex table:

 Plan
 Basis
 Â
 x 1
 x 2
 x 3
 x 4
 x 5
 min

 3
 x3
 102.43
 0
 6.93
 1
 0
 -0
 0

 
 x4
 20.05
 0
 2.8
 0
 1
 -0
 0

 
 x1
 7.5
 1
 2.5
 0
 0
 0
 7.5

 The indexline
 F(X3)
 7.5
 0
 1.5
 0
 0
 0
 0

The optimal plan can be written as:
x 3 = 102.43
x 4 = 20.05
x 1 = 7.5
F(X) = 1*7.5 = 7.5