Course 2 : Primal simplex method
Author: OptimizationCity Group
Introduction
The initial simplex method is a systematic repeated procedure until it finally reaches the desired or optimal solution. The set of steps that is repeated each time in such a process is called an iteration.
Basics of the primal simplex method
In an algebraic method, working with equal equations is far simpler than inequalities. Hence, the first step of the simplex method (omit the primal for the rest of manuscript) is to convert functional constraints from an unequal form to equal one. The constraints of negativity can be left unequal because they do not enter directly into the solution process. The conversion of an inequality to equality is done by introducing slack variables. Next, we solve the following model using Simplex method in the form of an example. The model is as follows:
Now consider the functional constraint (1), x1<=4 . The slack variable of this constraint, x3 , is defined as the difference of right and left side of constraint 1. Therefore, constraint 1 can be rewritten as follows:
The above equation is equal to the limit of 1 provided that x3>=0. Hence constraint 1 is equivalent to the following set of constraints:
To clarify the subject, we give a simple example. Consider the constraint x1<=4 . If x1=1 then we have 1<4 and the value of the slack variable is equal to 3, x3=3. The relation x1<=4 becomes x1+x3=4 and in this case x1=1 and x3=3.
For other inequalities, the model (P1) can be similarly rewritten as follows:
Model (P1-1) is exactly the same as model (P1), but this new format is much simpler for algebraic operations. In model (P1-1) the number of variables is equal to 5 and the number of constraints is equal to 3, in which we are faced with a set of constriant with two degrees of freedom(number of variables-number of constriants). In this case, you can set the desired value for two additional variables in each step and solve the system equation of three constraint having three variables. In the simplex method, these two additional variables are set equal to zero. Variables that are considered zero are called Non-basic variables and others are called Basic variables. The solution that all non-basic variables are equal to zero is called the Basic solution and the basic solution in which the basic variables are non-negative is called the Basic feasible solution.
Notice that the basic variable can be read immediately in the model because each equation has just one basic variable, which has a coefficient of 1, and this basic variable does not appear in any other equation.
It is easier for solving that the objective function rewrite as the functional constraint in the list of constraint with row zero. Therefore, before presenting the simplex method, we rewrite the problem (P1-1) as follows.
In the row zero, Z is the basic variable; because it has a coefficient of 1 in row zero, and it does not appear in any other equation
The primal simplex method
In this section, we will present the formal form of simplex method. In short, at each step the simplex method seeks to find the basic feasible solution provided that this solution is not worse than the previous solution to finally find an optimal basic feasible solution. To convert from one basic feasible solution to another on, it is sufficient to convert one basic variable to a non-basic variable (leaving variable) and a non-basic variable to a basic variable (entering variable). With these changes, the current basic feasible solution moves to the adjacent basic feasible solution. If a basic feasible solution is better than all the adjacent basic solution, that solution is the optimal solution and the algorithm ends at this point. The following figure summarizes the steps of the simplex method in general.
We express each step of the simplex method in the form of an example.
Intial step:
Call the slack variables (x3,x4,x5) as the basic variables and set the (x1,x2 ) variables as non-basic variables equal to zero. For simplicity of calculation, the coefficients of the variables and the value on the right hand side are written in the table named the simplex tableau. The example simplex tableau (P1-2) is as follows.
Because each equation contains a basic variable with a coefficient of +1, so the value of each basic variable will be equal to the value of right hand side (RHS) of the equation. The basic feasible solution of the above table is equal to (x1=0,x2=0,x3=4,x4=12,x5=18), which is displayed as (0,0,4,12,18) in the rest.
Stoping step:
If and only if all coefficients of row zero are non-negative (>=0), then the current basic feasible solution is the optimal, and then stop. Otherwise, repeat the interative step to find the adjacent basic feasible solution.
Iterative step:
Substep 1: Select the variable that has the largest negative coefficient for non-basic variable in row zero as the entering variable. Increasing the value of this non-basic variable leads to the fastest growth rate of the objective function. Draw a rectangle around the column below entering variable and call pivot column. In this example, the largest negative coefficient (-5) is for the variable (x2) and therefore it is selected as the entering variable.
Substep 2: The leaving basic variable is determined as follows.
A) Consider the positive coefficients of the pivote column
B) Divide the right hand side into positive coefficients
C) Select the row for which the ratio obtained in part (B) is the smallest.
D) The basic variable of this row is the leaving basic variable.
Substep 3: Draw a rectangle around this row and call pivot row. The value in both rectangles (pivote column and pivote row) is called the pivot number.
The results of the above operations are given in the table below.
In the above table, the variable x2 is the entering variable and the variable x4 is the leaving variable..
Substep 4: Get the new basic solution with the help of a new simplex tableau. The steps to obtain a new tableau are as follows.
A) In column (0), delete the leaving variable, x4 , and replace it with the entering variable, x2
B) To convert the coefficient of entering variable to one, divide the pivote row by the pivote number.
C) In order to remove the e basic variable from the other row, each row (even row zero) except the pivote row should be changed as follows.
C1. Multiply the pivote row by a nonzero constant which lead to become zero the coefficient of pivote column except from pivote number
C2. Add a multiple of pivote row to another row.
After creating a new simplex tableau, we go to the stopping step. If the stopping condition is met, the algorithm will stop; otherwise we will go to iterative step. We will continue this process until the stopping condition is met. The complete table of samples for (P2-1) is as follows.
In the table above, the basic solution (2,6,2,0,0) with Z=36 with satisfies the stopping condition, and therefore this solution is optimal.
Note: In each iteration of the simplex algorithm, one of the corner points of the feasible region is tested. Due to the small size of the model, the movement on the corner points of the feasible region can be seen in the graphical display of the model (P1) as follows.
If we had not chosen the larger absolute negative coefficient(it means x1 is as a entering variable), we would moved counterclockwise in the feasible region, and another basic feasible solution having been considered.
Shadow price
The simplex method produces other valuable information in addition to the optimal solution. The shadow value of the source i (denoted by yi*) measures the marginal value of source i, which indicates the rate of increase of Z due to a slight increase in the right hand side of source i (bi). Note that the rate of increase must be small enough that the current set of variables remains optimal because as soon as the set of basic variables changes, the shadow price also changes. The coefficient of i-th slack variable, which is related to i-th constraint, in row zero of final simplex tabluea determines the shadow price of i-th constraint.
For example in model (P1), the shadow price of constraint 1 is equal to the coefficient of x3 in row zero (equal to zero), the shadow price of constraint 2 is equal to the coefficient of x4 in row zero (equal to 1.5) and the shadow price of constraint 3 is equal to the coefficient of x5 in row zero (equal to 1).
Note: In other words, the shadow price of source 1 is the maximum price that it is cost-effective to pay to increase one unit of this source.
Special cases in simplex method
Choosing the entering variable
Suppose two or more non-basic variables have the largest negative coefficient. Here, pick the one with the largerst index. For example, consider (P1) model with different objective function, Z=3x1+3x2. Both and had a coefficient of 3, and 3; we pick . In this problem, if is selected, we will reach the optimal answer after three iterations, while if we choose , we will reach the optimal solution after two iterations.
Degeneracy
A linear model is degenerate if in a basic feasible solution, one of the basic variables takes on a zero value. Degeneracy is a problem in practice, because it makes cycling in the basic solution and then makes the simplex algorithm slower.
Note: A simple rule to get out of the state of decay is to use Bland’s rule. In this rule, a variable is selected as an input to the base that has the lowest index and the lowest coefficient of the objective function. In the case that there is more than one choice for the output variable from the base, the variable that is closest to the target function line or the zero line is selected.
Unbounded Z
Consider a situation where none of the basic variables have leaving conditions, and the value of the basic entering variables can increase infinitely without any of the other basic variables being negative. This condition occurs when coefficients of the pivote column in the simplex table are all negative or zero (non-positive). Consider the following model to clarify the issue.
The graphical display of the above model is as follows. Clearly, the value of the objective function increases infinitly and the form of a simplex table is given below.
In the table above, we have x4=12+2x2 and x5=18+2x2-3x1 where x2 can be increased to infinity. Therefore, the value of the objective function increases to infinity and the constraints do not prevent the unboundness of objective function. If this happened, it could have been a miscalculation or missing some constraints.
Multiple optimal solutions
Whenever a problem has more than one optimal basic feasible solution, at least one of the nonbasic variables has a coefficient of zero in the final row zero, so increasing any such variable will not change the value of Z. Therefore, these other optimal basic feasible solutions can be identified (if desired) by performing additional iterations of the simplex method, each time choosing a nonbasic variable with a zero coefficient as the entering basic variable.
Consider the following model:
The graphical display of the above model is given below. In this figure, each point of the line connecting (2,6) and (4,3) is the optimal solution. Knowing the existence of multiple optimal solutions to the problem is often very important in applying the results in practice. A mathematical model cannot take into account all the economic factors in the real world. Therefore, you can choose the best solution of optimal solutions with the help of an expert.
In the table above, the two basic solution (4,3,0,6,0) and (2,6,2,0,0) are optimal and the optimal value is Z=18 in both.
Equality constriants
Any equality constraint
actually is equivalent to a pair of inequality constraints:
However, rather than making this substitution and thereby increasing the number of constraints, it is more convenient to use the artificial-variable technique. We shall illustrate this technique with the following example.
The only resulting change in the linear programming model is that the third constraint, 3x1+2x2<=18, instead becomes an equality constraint. The new model as follows:
The below figure shows the graphical display of the above model:
Unfortunately, these equations do not have an obvious initial basic feasible solution because there is no longer a slack variable to use as the initial basic variable for constriant (3). It is necessary to find an initial basic solution solution to start the simplex method.
This difficulty can be circumvented in the following way.
Obtaining an Initial BF Solution.
The procedure is to construct an artificial problem that has the same optimal solution as the real problem by making two modifications of the real problem.
- Apply the artificial variable by introducing a nonnegative artificial variable (call it x̄5) into constraint (3), then we have:
And then the model would be:
Adding an artificial variable, x̄5 , enlarges the possible area similar to the figure below.
- Assign the penalty to having x̄5=0 by changing the objective function Z-3x1-5x2+Mx̄5=0, where M symbolically represents a huge positive number. (This method of forcing x̄5=0 in the optimal solution is called the Big M method.)
Converting Equation (0) to Proper Form.
The system of constriants is not yet in proper form because a basic variable x̄5 has a nonzero coefficient in Eq. (0). Recall that all basic variables must be algebraically eliminated from Eq. (0) before the simplex method can either apply the optimality test or find the entering basic variable. To algebraically eliminate x̄5 from row zero, we need to subtract from row zero the product, M times row 3, as below.
Now find the optimal solution for the real problem by applying the simplex method to the artificial problem, starting with the following initial BF solution:
In the above table, the optimal solution is (2,6,2,0,0).
Two-phase method
As mentioned, the big M method is used to solve the linear programming model with artificial variables. But because calculations with big M are very difficult in large models, it can lead to computational error. In this cas, Two-phase method is recommended. In this method, phase 1 seeks to minimize the sum of artificial variables. If the model succeeds in making the sum of the artificial variables equal to zero, the solution is used as the initial solution of the model in phase 2. In the following example, two-phase method is applied..
Example: Using the two-phase method, work through the simplex method step by step to solve the problem.
Solution:
Write the model in the standard form:
In the two-phase method, we first solve a model that seeks to minimize the objective function w=x5+x6 with the limitations of the original model. In fact, we are looking to optimize the following model.
The solution of the above model is done simultaneously with the orginal model, in which the objective function W and Z are entered in the simplex table.
The optimal solution of original model is (0,0,50,50) and Z*=400..
Revised simplex method
Another practical method for solving linear programming problems is the revised simplex method. Although the simplex method is suitable for performing manual calculations, it does not have the necessary efficiency to solve large problems by computer. The reason can be found in the storage of information that may never be used in simplex iterations. For example, some variables never meet the necessary conditions to be selected as input variables, as a result, all calculations related to the coefficients of these variables in the objective function and constraints will remain unused. In fact, the column corresponding to that variable is calculated, but it is not actually used.
The Revised Simplex method solves the problem by using all the principles and steps of the original Simplex method, without performing redundant operations and storing useless information, which require a lot of memory to keep in the computer. The use of the matrix is an inevitable necessity in applying the revised simplex method, and this makes the definition of the matrix of the linear programming problem necessary.
Matrix representation of the linear programming
In general, the standard linear programming problem is represented as follows:
Where
Example: Display the following model as a matrix.
In the above model:
In case of adding slack variables, the problem becomes as follows:
where
where I is called the m-by-m unit matrix and
By adding the slack variable s, the model is displayed as a matrix representation:
The number of basic variables is equal to the number of constraints and is equal to m. The matrix [A,I] has m rows (m number of constraints other than non-negativity constraints) and m+n columns, which include m basic variables and n non-basic variables. In the above example, m is equal to 2 and n is equal to 3.
Matrix [A,I] is divided into two matrices, one of which consists of the coefficients of basic variables and the other of the coefficients of non-basic variables. The matrix of coefficients of basic variables is represented by B and the matrix of coefficients of non-basic variables is represented by N. In the same way, all the variables of the problem, xj, si (j=1,…,m;i=1,…,n), are also divided into two groups of basic variables (xB ) and non-basic variables (xN ).
Note: In the first step of the basic simplex algorithm, basic variables are of type si and non-basic variables are of type xj. In the next steps, this situation will change and the basic variables will be a combination of si and xj. In the following, we will explain this situation with an example.
Example: Solve the following model using the revised simplex method.
Solution:
The initial simplex table for the above problem is as follows:
In the above table, basic variables or xB are slack variables (s1,s2); and non-basic variables or xN are decision variables (x1,x2,x3). B is the matrix of coefficients of basic variables and N is the matrix of coefficients of non-basic variables in the constraints.
The table of the first iteration of the simplex method is as follows.
In the above table
The matrix B is the coefficients of the basic variables in the initial table, and B-1 is the inverse matrix of B. The coefficient of x3 is 3 in the first constraint and 3 in the second constraint, so the first column of matrix B is created in this way.
The final simplex table is as follows.
Where
The matrix B is the coefficients of the basic variables in the initial table, and B-1 is the inverse matrix of B. The coefficient of x3 is 3 in the first constraint and 3 in the second constraint, so the first column of matrix B is created in this way. The x2 coefficient is 1 in the first constraint and 2 in the second constraint, so the second column of matrix B is created in this way.
With the explanations given above, the matrix representation of the linear programming model can be expressed. The constraints of the linear programming model are written as follows.
The variables are divided into two parts according to decision and slack variables. It can also be divided into two parts according to basic and non-basic variables and written as follows:
If we multiply both sides of the equation by B-1, we will have:
Since xN represent non-basic variables and have zero value, we have as a result:
If we have B-1 for each table, the above relation gives the value of the basic variables of that table or the numbers on the right side of it.
The objective function will be as follows by separating the variables into basic and non-basic variables:
Since xN represent non-basic variables and have zero value, we have as a result:
The coefficient of the non-basic variables in the objective function, that is, the coefficient xN, which is denoted by the symbol zj-cj, will be as follows according to the above relationships:
Coefficients of non-essential variables (xN) in the constraints, according to the following equation:
Equal to
The N matrix is shown as a column vector of non-basic variables, each column corresponding to one variable.
where each column of N shows the variable coefficients xj in the constraints. In this way, the following relationship is used to calculate the pivote column numbers:
To learn more about how to apply the above relations, we give an example.
Example:
Suppose we want to obtain the numbers of the simplex table, where the variables x3 and x2 are the basic variables. Therefore, we have:
To calculate the coefficient of non-basic variables in the objective function of the simplex table, where x3 and x2 are basic variables, it is done as follows:
In this simplex table, the value of xB and Z is calculated as follows.
The calculation of the x1 variable column is done as follows:
What has been said so far has covered all the necessary prerequisites for presenting the revised simplex algorithm. Therefore, we will continue to introduce this algorithm.
Revised simplex algorithm
Step 1: Determine the input variable. At each iteration, find the non-prime coefficients in the objective function using the cBB-1N-cN. If these values are all non-negative, you have reached the optimal solution. Calculate the optimal solution using the following relations.
Otherwise, select the variable with the most negative calculated coefficient. This variable is the input variable.
Step 2: Determine the output variable. Selecting the output variable requires having the coefficients of the input variable in the constraints and numbers on the right hand side. If the variable xj is the input variable, its coefficients in the constraints are obtained from the following relationship.
The value of the current basic variables which is equal to numbers on the right hand side is:
The basic output variable is obtained as follows.
Step 3: Calculate the new B-1 and determine the new basic variable and go to step 1.
Example: Consider the following model. Obtain the optimal solution using the revised simplex algorithm.
Solution:
We rewrite the model as follows.
Iteration 1
Step 1. Determine the input variable. The basic variable of iteration 1, s1 and s2 and their coefficient in the objective function is zero (cB=(0,0)). The coefficients of non-basic variables (xN=(x1,x2,x3)T) are calculated as follows:
Because the coefficient of x3 is equal to -6 and the most negative number, this is the input variable shown in the table below.
Step 2. Determine the output variable. The x3 coefficients in the constraints are calculated as follows:
Because the smallest number of the result corresponds to the basic variable s1, this variable is selected as the output variable. The calculations of steps 1 and 2 are summarized as follows:
Step 3. Calculate the new B and xB. Since variable x3 is input and s1 is output, the basic variables of the new iteration are:
Iteration 2
Step 1. Determine the input variable. The coefficients of non-basic variables, xN=[x1,x2,s1], are calculated as follows.
x2 becomes the input variable.
Step 2. Determine the output variable.
s2 is the output variable.
Step 3. Since x2 is the input variable and s2 is the output variable, the basic variables of the next iteration are:
Iteration 3
Step 1. Determine the input variable. The coefficients of non-basic variables (xN=[x1,s1,s2]T) are calculated as follows:
Because all the obtained numbers are non-negative, you have reached the optimal solution.
Example: Solve the following problem by the revised simplex method.
Solution:
The s1 variable is considered as the basic variable of the first constraint, the s2 variable is considered to equalize the second constraint, and the R2 variable is considered as a slack and artificial variable, respectively, for the purpose of the second constraint basic variable.
Thus we have:
Iteration 1:
Step 1. We define the input variable.
Considering that the value of -2M-2 has the most negative value, therefore, the variable x2 is introduced as an input variable to the basic variable.
Step 2. Select the output variable from the base variables. For this, we must first obtain the value of variable coefficients x2 in all constraints.
The variable R2 is removed from the base.
Step 3. We calculate the new B-1.
Iteration 2
Step 1. Determine the input variable.
x1 becomes the input variable to the base.
Step 2. Determine the output variable.
The variable s1 becomes the output variable of the base.
Step 3. We calculate the new B-1.
Iteration 3
Step 1. Determine the input variable.
The variable s2 enters the base.
Step 2. Determine the output variable.
The ratio test is performed only on the positive numbers of the column corresponding to the input variable. Therefore, the x1 variable is removed from the base.
Step 3. Calculate the new B-1.
Iteration 4
Step 1. Determine the input variable.
Because there are no negative values in the above values, we reached the optimal solution. the optimal solution is as follows.
Simplex method with bounded variable
In many linear programming problems, we encounter cases where the decision variables have a specific upper or lower limit. In this case, the form of the problem will be as follows:
uj and lj are fixed numbers that show the maximum increase (upper limit) and the maximum decrease (lower limit) of variable xj, respectively.
A simple and inefficient way to solve such problems is to deal similarly with bounded variables and other functional constraints of the problem. This way of dealing with problem solving leads to increasing calculations and reducing the efficiency of solving. On the other hand the time required to perform simplex calculations is affected by various factors, the number of constraints being the most important. Experience has shown that the calculation time increases almost by the third power of the number of constraints. For example, if the number of constraints is doubled, the computation time increases 23=8 times.
The method of solving these problems is divided into two categories of variables with lower bound and variables with upper bound, which will be examined in the following.
Variables with lower bound
In this section, you will find a situation where the problem only has variables with lower bound. The general form of the problem is as follows:
The constraint of the bounded variable can be equalized by subtracting the new variable xj‘ from it:
By replacing lj+x’j with xj, the lower bound constraint for xj is removed from the list of functional constraints. The steps for solving problems with lower bound variables are as follows:
Step 1. For variables with lower bounds, change the variable xj to lj+x’j throughout the problem.
Step 2. Solve the new problem resulting from this change of variable without considering the lower bound constraint using the standard simplex method.
Step 3. Convert all x’j variables obtained in the final table to xj using the variable change relation.
Example: Consider the following problem.
Solve the above model using the lower bound method.
Solution:
x2 is a variable with a lower limit, that is, the value of x2 is not less than 1. To remove this constraint, just change the following variable.
As a result, the problem will be as follows:
Using the simplex method, the optimal solution of the above model is as follows.
Variables with upper bound
In many linear programming problems, the variables of the problem have upper bounds that represent the maximum values of that variable. The upper bound method is a method to solve such problems. The general form of this model is as follows:
The variable with upper bound method is a method that takes the upper bound constraints from functional constraints and treats them separately like non-negative constraints.
The main problem with variables with an upper bound is that changing the variable is not as true as before; because there is no guarantee that changing the variable like below, the value of xj will remain non-negative.
To clarify the above forms, we give an example. Suppose the following constraint is assumed:
For xj‘, the value of 5 can be considered because it is a non-negative value, in which case, xj becomes -2, which is against the assumption of non-negative xj.
In the simplex method, it is assumed that the values on the right hand side are non-negative, which causes the value of the basic variables to be non-negative or feasible. In the upper bound method, instead of adding the upper bound constraint, its effect can be replaced by changing the feasibility of the basic solution which is no safisfied:
(1) right hand side value is negative or
(2) right hand side value exceed its upper limit.
In the following, the algorithm of the upper bound method is described. More details will be given in solving a problem.
Step 1. Fill the simplex table as normal, but do not enter the upper bound constraints.
Step 2. Select the non-basic variable input to the base, xk (the variable with the most negative coefficient in the zero row)
Step 3. To select the output variable, calculate the following ratios (aik are the coefficients of the variable xk in functional limits).
uk is the upper limit of the input variable. Then calculate the minimum value of (θi,αi,uk). Three cases occur:
The first case: the minimum ratio is related to θr. Then xk enters the base and xr leaves the base. In this case, when xk enters a basic variable xr, its value becomes zero. This is the same situation that you encountered before in the standard simplex method.
The second case: the minimum ratio is related to uk. Then xk remains non-basic and reaches its upper bound. In this case, the input variable becomes the output variable. The variable (xk) should be changed to the variable yk=uk-xk, then the simplex method is used. With this, the new variable yk will remain non-primary and with zero value. Because it was possible to enter the base, but it reached its upper bound.
The third case: the minimum ratio is related to αr. In this case, the basic variable against the negative number of the pivot column (xr) reaches its upper limit. First a variable replacement is given for xr as yr=ur-xr and the operation continues according to the simplex method.
Note: The difference between the second and third case is that in the second case, the change of variable is done for the non-basic variable that has the conditions to enter the base, but in the third case, the change of variable is done for the current basic variable.
Step 4: Stop when all numbers in the zero line become non-negative. You have reached the optimal solution.
Example: Consider the following problem. Obtain the optimal solution using the simplex with upper bound method.
Solution:
Step 1. By adding slack variables, like the simplex method, the problem enters the following table.
Step 2. The variable x2 is chosen as the input variable.
Step 3. To determine the output variable, the following value is calculated.
The value of θ1 means that the variable x2 can increase up to 6 units so that the variable s1 does not become negative. The value of θ2 means that the variable x2 can increase by 1 unit so that the variable s2 does not become negative. This is the concept of ratio test in simplex method.
Because the numbers in the column corresponding to x2 are positive, there is no need to calculate a. The upper limit of variable x2 is equal to 3, so we have:
Since the minimum is related to (the first case of step 3), x2 is entered and s2 is removed from the base, and the operation is performed exactly the same as the simplex method.
Step 3. Since there is a negative number (-3) in the zero row, the problem is non-optimal and x1 is the input variable. To determine the output variable, the following ratios are calculated.
So,
Note: For simplicity of representation, θ1 will be the ratio value for row 1, α2 will be the ratio value for row 2, and u1 will be the upper bound for the non-basic variable of column 1.
This case represents the second case of step 3. For further explanation, we have the equation of row 2 as follows.
The variables x3 and s2 are non-basic and their value is zero. Therefore, the above equation is as follows.
The value of x1 can increase by two units (a2) so that the variable x2 reaches the upper bound which is equal to 3. In this case, x1 enters the base and x2 leaves the base and is at its upper bound. In this case, the variable x2 is changed to x2=3-y2 so that the variable x2 is in the upper bound and the variable y2 has a value of zero and is placed in its lower bound and will be non-basic.
Because the coefficient of x2 in the simplex table is zero, the change of variable has no effect on the row 0 coefficients. There is no change for row 1 in the same way. In the equation of the row 2, there is variable x2, so we have
By placing the above equation in the row 2 in the simplex table, we will have
The variable y2 in the above table does not have the basic variable condition. Also, the right side of the second line is negative. By multiplying row 2 of this table by -1, the following table is obtained.
Step 3. Since the x1 coefficient is negative in the zero row, we recalculate the following ratios to determine the output variable. Because 2 and 1 (the numbers under the x1 variable column) are positive, there is no need to calculate a.
Since the minimum ratio of the result is θ2, the operation continues as in the simplex method.
x3 is the input variable and the following ratios are calculated. Considering that one of the numbers in the x3 column is positive and the other is negative, the values of a and θ are calculated.
Again, it works like the case 1 of step 3 and the simplex table is as follows.
The above table has the optimality condition, so the optimal solution is as follows.
In the previous problem, the case 2 of step 3 did not occur. In the following example, we examine this case.
Example:
Solution:
Considering that the second constraint can be considered as an upper bound for the x2 variable with a value of 6, therefore, the model can be transferred to the simplex table only by adding a slack variable.
x2 is the input variable and θ1=9 and also:
With the entry of x2, this non-basic variable reaches its upper bound and the variable must be changed for it: x2=6-y2. The simplex table is changed based on variable y2 as follows.
x1 will be the input variable and we have:
And the optimal table is as follows.
The optimal solution will be as follows:
Example: A Company has discontinued the production of a certain unprofitable product line. This act created considerable excess production capacity. The management is considering devoting this excess capacity to one or more of three products; products 1, 2, and 3. The available capacity on the machines is summarized in the following table:
The number of machine hours required for each unit of the products is:
The sales department indicates that the sales potential for products 1 and 2 exceeds the maximum production rate and that the sales potential for product 3 is 20 units per week. The unit profit would be $50, $20, and $25, respectively, on products 1, 2, and 3. The objective is to determine how much of each product Omega should produce to maximize profit.
a) Formulate a linear programming model for this problem.
b) Solve the model using simplex method.
Solution:
a) Let xi be the number of units of product i produced for i=1,2,3. The linear programming model of this problem is as follows.
Constraint 1 is the same as milling machine capacity, constraint 2 is the same as lathe capacity, constraint 3 is the same as grinder constraint, and constraint 4 is demand constriant.
b) Solve the model using the simplex method.
Optimal solution is (x1,x2,x3)=(26.19,54.76,20) and Z*=2904.76. The shadow prices list as follows:
Example: consider the following problem:
Using the simplex method to solve the problem.
Solution:
After the slack variables needed for the inequality constraints are introduced, the original model becomes:
Now we can apply the simplex method as follows:
The optimal solution is x=(0,0,10,0,10) and Z*=60.
Example: Consider the following problem:
Work through the simplex method step by step to demonstrate that Z is unbounded.
Solution:
Now we can apply the simplex method as follows:
In the above table, the columns below the variable x7 are non-positive demonstrating that Z is unbounded. In fact, by increasing the two variables x2 and x3, the value of the objective function goes to infinity.
Example: Consider the following problem:
a) Solve this problem graphically.
b) Using the Big M method, work through the simplex method step by step to solve the problem.
Solution:
a) The model has no feasible region.
b) convert min to max, and use artificial/surplus/slack variables and the Big M method to construct the complete first simplex tableau for the simplex method.
In the final table, the optimal condition is reached, but x6=0.6 is greater than zero, which means that the original model has no solution.
