Scribd
Upload
179 views14 pages

Simplex Method for Maximization Problems

The document describes solving a linear programming problem using the simplex method. It involves maximizing an objective function subject to constraints. The problem is converted to standard form by adding slack variables. An initial feasible solution is established with decision variables set to zero. Further iterations are performed by selecting an entering variable and leaving variable to arrive at an optimal solution. The process involves setting up and transforming the simplex tableau at each step until an optimal solution is reached where there is no more scope for improvement.

Uploaded by

Sanjan KS
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
179 views14 pages

Simplex Method for Maximization Problems

The document describes solving a linear programming problem using the simplex method. It involves maximizing an objective function subject to constraints. The problem is converted to standard form by adding slack variables. An initial feasible solution is established with decision variables set to zero. Further iterations are performed by selecting an entering variable and leaving variable to arrive at an optimal solution. The process involves setting up and transforming the simplex tableau at each step until an optimal solution is reached where there is no more scope for improvement.

Uploaded by

Sanjan KS
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
  • Problem Description and Standard Form Conversion
  • Initial Simplex Tableau Setup
  • Initial Feasible Solution Establishment
  • Locating Improvement Scope
  • Variable Selection and Key Row Transformation
  • Simplex Method Iterations
  • Conclusion of Simplex Solution

Operations Research Simplified

Simplex Method for Linear Programming Problem


Problem: Find solution using Simplex method
Maximize Z = 3X + 5Y
subject to
X + 2Y <= 2000
X + Y <= 1500
Y <= 600
and X,Y >= 0

Solution:
in given problem objective function is

Max Z = 3 X + 5 Y

subject to constraints

X + 2 Y ≤ 2000

X + Y ≤ 1500

Y ≤ 600

and X,Y ≥ 0;

Step 1: Convert the given objective function and constraints in to standard


form:
The problem is converted to standard form by adding slack, surplus and artificial variables as
appropriate
1. As the constraint-1 is of type '≤' we should add slack variable S1
2. As the constraint-2 is of type '≤' we should add slack variable S2
3. As the constraint-3 is of type '≤' we should add slack variable S3

After introducing slack variables problem will become

Maximize

Z= 3X + 5Y + 0.S1 + 0.S2 + 0.S3

Subject to

X + 2Y + 1.S1 + 0.S2 + 0.S3 = 2000;

Page 1 of 14
Operations Research Simplified

X + Y + 0.S1 + 1.S2 + 0.S3 = 1500;

0.X + Y + 0.S1 + 0.S2 + 1.S3 = 600;

where X,Y,S1,S2,S3≥0

Note that for objective functions coefficient of slack variable will be zero as slack variable do not
contribute in profit Z.

Step 2: Setting up the initial simplex tableau


Table 1 represents the blank Simplex tableau

The essential features of simplex tableau are

The first row of the table called as objective row (Cj row) contains the coefficient of variables in
the objective function. The elements in this row indicate the contribution per unit to the objective
function of each of the variables.

The first column headed by Cj is called as objective column. It lists the coefficient of variables
included in the solution at any stage of the problem. Only slack variables are considered in the
solution in the initial solution, their profit coefficient is zero which is listed in this column.

The second column called as product mix column contains basic variables in the current
solution. In the initial simplex table these basic variables are slack variables (S1, S2 and S3).

Then there are number of columns equal to variables in the constraints (in this example there are
five variables X, Y, S1, S2 and S3). It contains the coefficient of variables from corresponding
constraints.

Second last column is called as solution column which contains the right hand side (RSH) value
of corresponding constraints in corresponding row.

Last column is replacement ratio column which we need to calculate for deciding the leaving
variable.

Page 2 of 14
Operations Research Simplified

Table 1: Blank Simple Table

Step 3: Establishing an initial feasible solution


The simplex method starts with zero solution (point of zero production) and progresses through
series of iterations to determine the optimal quantity of each item.

To obtain the initial feasible solution, decision variables (X and Y) are set to zero, which reduces
the constraint value to

X = 0 and Y = 0 so

S1 = 2000; S2 = 1500 and S3 = 600.

This implies that at initial stage available capacity is idle or unused.

Each row in table represents one constraint.

So simplex table for initial feasible solution is shown in table 2.

Page 3 of 14
Operations Research Simplified

Table 2 : Initial feasible solution

Step 4: Locating scope for improvement


Two more rows Zj and Cj-Zj are added at the bottom in the table

Positive value of Cj-Zj indicates an opportunity for improving the current solution.

Zj values for each column are calculated by summing the products of elements in the column and
corresponding element in objective column (Cj)

Cj-Zj values are calculated by subtracting Cj value from corresponding Zj value for a column

For example for the column having variable X (third column in Table-3)

Zj = (0 x 1) + (0 x 1) + (0 x 0)

Zj = 0;

Cj = 3;

So Cj – Zj = (3 – 0) = 3

In similar way Cj-Zj values are calculated for all the columns as shown in table-3

Page 4 of 14
Operations Research Simplified

Table 3: Initial Simplex table with Cj – Zj values

For maximization problem if there are any positive values (>0) in the Cj-Zj row, then we have to
perform step-5. If there are all zero or negative values in the Cj-Zj row then solution is optimum
and we can stop at that point?

As maximum positive value of Cj-Zj is 5 in table 3 there is a scope for improvement so we will
move to step-5

Step 5: Selection of the entering variable


Now in this problem there are positive values (>0) in the Cj-Zj row, so select highest value in Cj-
Zj row.

Maximum positive value of Cj-Zj is 5 and its column index is 2, which is associated to variable
Y. So, the entering variable is Y.

And key column is column containing variable Y

Step 6: Selection of the leaving/departing variable


Now calculate the replacement ratio

Page 5 of 14
Operations Research Simplified

Now select minimum positive value of replacement ratio, corresponding row will become key
row and corresponding variable will be leaving variable.

Minimum ratio is 600 and its row index is 3. So, the leaving basis variable is S3.

Table 4 : Simplex table with key element

∴ the key element is 1.

Entering variable =Y,

Departing variable =S3,

Key Element =1

Now we need to prepare revised simplex table

Iteration-I

Step 7: Transformation of key row to reduced row in revised simplex table


Elements in third row (Reduced row) for revised simplex table are given by
Page 6 of 14
Operations Research Simplified

Reduced row is sown in Table - 5

Table 5: Reduced row in revised simplex table ( Iteration –I )

Step 8: Transformation of non-key row to replaced row in revised simplex


table
Elements in first and second row (Replaced row) for revised simplex table are given by

So complete revised Simplex table for iteration-I is shown in Table-6

Page 7 of 14
Operations Research Simplified

Table 6: Replaced row in the revised Simplex table ( Iteration –II )

Now calculate the Zj and Cj-Zj values as mentioned step-4

Table 7 : Cj - Zj values for revised Simplex table ( iteration I )

Page 8 of 14
Operations Research Simplified

Maximum positive value of Cj-Zj is 3 and its column index is 1. So, the entering variable is X.

Table 8: Revised Simplex table with key element ( iteration I )

Minimum positive ratio is 800 and its row index is 1. So, the leaving basis variable is S1.
∴ the key element is 1.
Entering variable =X, Departing variable =S1, Key Element =1

As Cj-Zj value is positive, there is a still scope for improvement we will perform next iteration

Iteration II
Repeat the steps 7, reduced row for second iteration is shown in table-9

Page 9 of 14
Operations Research Simplified

Table 9: Reduced row in revised simplex table (Iteration -II)

Repeat the steps 8, Replaced rows for second iteration is shown in table-10

Table 10: Replaced row in revised simplex table ( iteration II )

Page 10 of 14
Operations Research Simplified

Now calculate the Zj and Cj-Zj values as mentioned step-4

Table 11: Cj - Zj values for revised Simplex table ( Iteration II )

Maximum positive value of Cj-Zj is 1 and its column index is 3. So, the entering variable is S3.

Table 12 : Revised Simplex table with key element ( Iteration II )

Page 11 of 14
Operations Research Simplified

Minimum positive replacement ratio is 100 and its row index is 2. So, the leaving basis variable
is S2.
∴ the key element is 1.
Entering variable =S3, Departing variable =S2, Key Element =1

As there is a still scope for improvement we will perform next iteration

Iteration III
Repeat the steps 7, reduced row for second iteration is shown in table-13

Table 13: Reduced row in revised simplex table ( Iteration –III )

Repeat the steps 8, Replaced rows for second iteration is shown in table-14

Page 12 of 14
Operations Research Simplified

Table 14: Replaced row in revised simplex table ( Iteration –III )

Now calculate the Zj and Cj-Zj values as mentioned step-4

Table 15: Cj - Zj values for revised Simplex table ( Iteration III )

As all the values of Cj-Zj are either negative or zero it represents an optimal solution at

Page 13 of 14
Operations Research Simplified

X = 1000,

Y = 500,

Maximum possible profit Z = 5500

Value of slack variable S3 = 100 indicates the remaining unused capacity.

Page 14 of 14

Common questions

Powered by AI

The improved Cj-Zj value calculation is significant because it provides a clear criterion for determining whether additional iterations are necessary. A positive Cj-Zj value signals that increasing the corresponding variable in the solution can further improve the objective function, indicating that the current solution is not yet optimal. Conversely, if all Cj-Zj values are non-positive, it confirms that the solution cannot be improved further, allowing the process to stop at the optimal solution. Thus, Cj-Zj values guide the continuation or termination of the iterative process .

Iterations in the simplex method systematically improve the objective function by transitioning from one basic feasible solution to another through pivot operations. Each iteration involves selecting entering and leaving variables, computing pivot elements, and updating the simplex tableau to move the solution closer to optimality. This process continues until no further improvement is possible, indicated by non-positive Cj-Zj values, at which point the solution is deemed optimal. Iterations ensure that the exploration of feasible solutions is efficient, accurately converging towards maximum or minimum values of the objective function .

The Cj-Zj row in a simplex tableau indicates the potential for improving the current solution. Each entry in this row is computed by subtracting the Zj value, which represents the total contribution to the objective from the current basis, from the Cj value, which is the coefficient of the non-basic variable in the objective function. A positive value in the Cj-Zj row suggests that introducing more of the associated variable into the solution could improve the objective function value, indicating an opportunity for optimization. When all Cj-Zj values are less than or equal to zero, it suggests that the solution is optimal and no further improvements can be made by adding other non-basic variables to the basis .

The introduction of slack variables transforms inequalities that are less-than-or-equal-to (≤) in the constraints of a linear programming problem into equalities by adding non-negative slack variables to the constraints. For instance, if a constraint is X + 2Y ≤ 2000, the slack variable S1 is added to transform it into X + 2Y + S1 = 2000. This process allows the constraints to be written in a form that is suitable for the simplex tableau, where each inequality is converted into an equality by adding a slack variable to account for unused resources .

The simplex method terminates with an optimal solution when all the values in the Cj-Zj row of the tableau are less than or equal to zero. This scenario indicates that there are no more positive Cj-Zj values, reflecting that no further improvement can be achieved by increasing any of the current variables in the solution. Hence, the current solution is considered optimal .

The initial feasible solution in the simplex method is determined by setting the decision variables, such as X and Y, to zero, which simplifies the constraints to the values of the slack variables. This results in zero production and shows the available, unused capacity, such as S1 = 2000, S2 = 1500, and S3 = 600 in the given problem. This initial point serves as a baseline from which the simplex algorithm iteratively progresses by adjusting the values of the decision variables to explore feasible solutions that improve the objective function, thus playing a critical role in initiating the optimization process .

Calculating the Zj values in each simplex tableau iteration is necessary to assess the contribution of the current basis to the objective function. Zj values are computed by summing the products of each column's elements and the corresponding coefficients of the basic variables in the objective column (Cj). These values allow for the evaluation of the current solution's effectiveness and determine if further optimization is possible by computing Cj-Zj for each column, which helps in identifying potential new entering variables .

During the pivot operation in the simplex method, the entering variable is selected based on the highest positive value in the Cj-Zj row, as it represents the variable that can most effectively improve the objective function when added to the basis. Once the entering variable is identified, the leaving variable is determined by calculating the replacement ratio, which is the ratio of the current right-hand side values to the coefficients of the entering variable in the constraint. The leaving variable is associated with the row having the minimum positive replacement ratio, ensuring that the solution remains feasible when the entering variable is increased. This process is repeated iteratively to move towards the optimal solution .

The simplex method ensures the solution remains feasible during each iteration by selecting the entering and leaving variables such that the solution remains within the feasible region defined by the constraints. The leaving variable is determined based on the minimum positive replacement ratio, which prevents any constraint from being violated as the entering variable is increased. This careful selection process, combined with maintaining non-negativity of the variables, ensures that the solution remains valid and feasible throughout the iterative optimization process .

Slack variables provide insights into resource utilization by quantifying the unused portion of resources in linear programming constraints. When a slack variable is zero, it indicates full utilization of the corresponding constraint's resources; a positive slack variable value reflects unused or surplus capacity. For instance, in the final solution, a slack variable value such as S3 = 100 indicates that 100 units of that constraint's capacity remain unused, helping to understand which resources are still available or fully expended, thereby guiding resource allocation and decision-making .

Operations Research Simplified Page 1 of 14 Simplex Method for Linear Programming Problem Problem: Find solution usin
Operations Research Simplified Page 2 of 14 X + Y + 0.S1 + 1.S2 + 0.S3 = 1500; 0.X + Y + 0.S1 + 0.S2 + 1.S3 = 600;
Operations Research Simplified Page 3 of 14 Table 1: Blank Simple Table Step 3: Establishing an initial feasible so
Operations Research Simplified Page 4 of 14 Table 2 : Initial feasible solution Step 4: Locating scope for improvem
Operations Research Simplified Page 5 of 14 Table 3: Initial Simplex table with Cj – Zj values For maximization pro
Operations Research Simplified Page 6 of 14 Now select minimum positive value of replacement ratio, corresponding ro
Operations Research Simplified Page 7 of 14 Reduced row is sown in Table - 5 Table 5: Reduced row in revised simp
Operations Research Simplified Page 8 of 14 Table 6: Replaced row in the revised Simplex table ( Iteration –II ) No
Operations Research Simplified Page 9 of 14 Maximum positive value of Cj-Zj is 3 and its column index is 1. So, the
Operations Research Simplified Page 10 of 14 Table 9: Reduced row in revised simplex table (Iteration -II) Repeat t

You might also like