solve the following linear programming problem using two phase simplex method

Two Phase Method: Linear Programming

In Two Phase Method , the whole procedure of solving a linear programming problem (LPP) involving artificial variables is divided into two phases.

In phase I, we form a new objective function by assigning zero to every original variable (including slack and surplus variables) and -1 to each of the artificial variables. Then we try to eliminate the artificial varibles from the basis. The solution at the end of phase I serves as a basic feasible solution for phase II. In phase II, the original objective function is introduced and the usual simplex algorithm is used to find an optimal solution. The following are examples of Two Phase Method .

Example 1, Two Phase Method: Example 2

Two Phase Method: Minimization Example 1

Minimize z = -3x 1 + x 2 - 2x 3

x 1 + 3x 2 + x 3 ≤ 5 2x 1 – x 2 + x 3 ≥ 2 4x 1 + 3x 2 - 2x 3 = 5

x 1 , x 2 , x 3 ≥ 0

If the objective function is in minimization form, then convert it into maximization form.

Changing the sense of the optimization

Any linear minimization problem can be viewed as an equivalent linear maximization problem, and vice versa. Specifically:

If z is the optimal value of the left-hand expression, then -z is the optimal value of the right-hand expression.

Maximize z = 3x 1 – x 2 + 2x 3

Converting inequalities to equalities

x 1 + 3x 2 + x 3 + x 4 = 5 2x 1 – x 2 + x 3 – x 5 = 2 4x 1 + 3x 2 - 2x 3 = 5

x 1 , x 2 , x 3 , x 4 , x 5 ≥ 0

Where: x 4 is a slack variable x 5 is a surplus variable

The surplus variable x 5 represents the extra units.

Now, if we let x 1 , x 2 and x 3 equal to zero in the initial solution, we will have x 4 = 5 and x 5 = -2, which is not possible because a surplus variable cannot be negative. Therefore, we need artificial variables .

x 1 + 3x 2 + x 3 + x 4 = 5 2x 1 – x 2 + x 3 – x 5 + A 1 = 2 4x 1 + 3x 2 - 2x 3 + A 2 = 5

x 1 , x 2 , x 3 , x 4 , x 5 , A 1 , A 2 ≥ 0

Where A 1 and A 2 are artificial variables.

Phase 1 of Two Phase Method

In this phase, we remove the artificial variables and find an initial feasible solution of the original problem. Now the objective function can be expressed as

Maximize 0x 1 + 0x 2 + 0x 3 + 0x 4 + 0x 5 + (–A 1 ) + (–A 2 )

Initial basic feasible solution

The intial basic feasible solution is obtained by setting x 1 = x 2 = x 3 = x 5 = 0

Then we shall have A 1 = 2 , A 2 = 5, x 4 = 5

Two Phase Method: Table 1

On small screens, scroll horizontally to view full calculation

Key column = x 1 column Minimum (5/1, 2/2, 5/4) = 1 Key row = A 1 row Pivot element = 2 A1 departs and x 1 enters.

A2 departs and x 2 enters. Here, Phase 1 terminates because both the artificial variables have been removed from the basis.

Phase 2 of Two Phase Method

The basic feasible solution at the end of Phase 1 computation is used as the initial basic feasible solution of the problem. The original objective function is introduced in Phase 2 computation and the usual simplex procedure is used to solve the problem.

Use horizontal scrollbar to view full calculation

"The most useful virtue is patience" - John Dewey

Two Phase Method: Final Optimal Table

An optimal policy is x 1 = 5/2, x 2 = 0, x 3 = 5/2. The associated optimal value of the objective function is z = 3 X (5/2) – 0 + 2 X (5/2) = 25/2.

Share This Article

Operations Research Simplified Back Next

Goal programming Linear programming Transportation Problem Assignment Problem

Wolfram Demonstrations Project

Two-phase simplex method.

• Open in Cloud
• Download to Desktop
• Copy Resource Object

Requires a Wolfram Notebook System

Interact on desktop, mobile and cloud with the free Wolfram Player or other Wolfram Language products .

Do not show again

This Demonstration computes the solution of a randomly generated linear programming problem using the two-phase simplex algorithm. It displays the table generated while stepping through the simplex algorithm and then compares the solution so obtained with Mathematica 's built-in function LinearProgramming .

Contributed by: Sourav Mukherjee   (June 2011) Open content licensed under CC BY-NC-SA

If the value in the right-hand side (r.h.s.) column of the top row is negative at the end of phase 1, it means that the constraints are infeasible.

An equality constraint is replaced by the corresponding greater-than-equal-to constraint and the lesser-than-equal-to constraint.

In this Demonstration, in the tables the values attained by the original variables that happen to be basic variables are highlighted in light green. The pivot element is highlighted in light red. The value attained by the objective function at the end of phase 2 is highlighted in light blue.

For details of the algorithm used, please refer to Chapter 3 of [1].

[1] S. S. Rao, Engineering Optimization : Theory and Practice , 3rd ed., New Delhi: New Age International, 2006.

Related Links

• Linear Programming  ( Wolfram MathWorld )
• Simplex Method  ( Wolfram MathWorld )

Permanent Citation

Sourav Mukherjee "Two-Phase Simplex Method" http://demonstrations.wolfram.com/TwoPhaseSimplexMethod/ Wolfram Demonstrations Project Published: June 13 2011

Share Demonstration

Take advantage of the Wolfram Notebook Emebedder for the recommended user experience.

Related Topics

• College Mathematics
• Linear Programming
• Optimization

Two-Phase Method

There are two standard methods for handling artificial variables within the simplex method: The Big M method The 2-Phase Method Although they seem to be different, they are essentially identical. However, methodologically the 2-Phase method is much superior. We shall therefore focus on it. The 2-Phase method is based on the following simple observation: Suppose that you have a linear programming problem in canonical form and you wish to generate a feasible solution (not necessarily optimal) such that a given variable, say x 3 , is equal to zero. Then, all you have to do is solve the linear programming problem obtained from the original problem by replacing the original objective function by x 3 and setting opt=min. If more than one variable is required to be equal to zero, then replace the original objective function by the sum of all the variables you want to set to zero. Observe that because of the non-negativity constraint, the sum of any collection of variables cannot be negative. Hence the smallest possible feasible value of such a sum is zero. If the smallest feasible sum is strictly positive, then the implication is that it is impossible to set all the designated variables to zero. Applying this simple idea to artificial variables we obtain the following recipe: To set all the artificial variables to zero, solve a linear programming problem derived from the canonical form of the original problem by replacing the original objective function by the sum of all the artificial valriables and setting opt=min. If the optimal value of the modified objective function is not equal to zero, then the problem (system of constraints) is not feasible. To illustrate the modelling aspects of this approach let us re-examine the following little example: x 1 + 3x 2 + 7x 3 > = 25 -3x 1 - 2x 2 + 7x 3 = - 5 2x 1 + x 2 + 4x 3 < = 10     x 2 ,x 3 >= 0

Taking case of its violations of the standard form we obtain the following canonical form:

 x 1 -  x 2 + 3x 3 + 7x 4 - x 5 + x 6 = 25 3x 1 - 3x 2 + 2x 3 - 7x 4 + x 7 =  5 2x 1 - 2x 2 +  x 3 + 4x 4 + x 8 = 10 x j >= 0 , j=1,...,8

There are two artificial variables, namey x 6 and x 7 . Thus, Phase 1 of the 2-Phase method involves the following linear programming problem:

w* := min w := x 6 + x 7  x 1 -  x 2 + 3x 3 + 7x 4 - x 5 + x 6 = 25 3x 1 - 3x 2 + 2x 3 - 7x 4 + x 7 =  5 2x 1 - 2x 2 +  x 3 + 4x 4 + x 8 = 10 x j >= 0 , j=1,...,8

If we now incorporate the objective function in the constraint in the usual manner and place the new variable, namely w last, we obtain the following system:

 x 1 -  x 2 + 3x 3 + 7x 4 - x 5 + x 6 = 25 3x 1 - 3x 2 + 2x 3 - 7x 4 + x 7 =  5 2x 1 - 2x 2 +  x 3 + 4x 4 + x 8 = 10                   - x 6 - x 7   + w =  0 x j >= 0 , j=1,...,8, w>= 0

Note that this system is not in a canonical form because the columns of the artificial variables are not elementary columns. To obtain a canonical form we have to add the rows of the artificial variables to the last row. This yields:

 x 1 -  x 2 + 3x 3 + 7x 4 - x 5 + x 6 = 25 3x 1 - 3x 2 + 2x 3 - 7x 4 + x 7 =  5 2x 1 - 2x 2 +  x 3 + 4x 4 + x 8 = 10 4x 1 - 4x 2 + 5x 3 +   - x 5 +           w = 30 x j >= 0 , j=1,...,8, w>= 0

This is then the system that will be used to initialise the simplex algorithm for Phase 1 of the 2-Phase method. Of course, the column of w will not appear in the tableau.

We can ditinguish between two cases as far as the end of Phase 1 is concerned, namely:

Case 1: w* > 0 : The optimal value of w is greater than zero.

Case 2: w* = 0 : The optimal value of w is equal to zero.

In Case 1 we conclude that the LP problem under consideration does not have a feasible solution whereas Case 2 implies that the constraints are feasible, hence the problem under consideration possesses a feasible solution.

The following final simplex tableau is an example of Case 1:

One artificial variable ( x 6 ) is in the basis and is not equal to zero. The problem does not have a feasible solution.

It should be noted that although Case 2 implies that all the artificial variables are equal to zero, this does not mean that they are all out of the basis.

So it is necessary to consider Case 1 in more detail, namey:

Case 2.1: All the artificial variables are non-basic.

Case 2.2: some of the artificial variables are in the basis

In Case 2.1 we proceed to Phase 2 of the 2-Phase method replacing the objecitve function of Phase 1 with the original objecitve function. This will typically violate the canonical form of the problem and thus pivot operations may have to be used to restore the canonical form.

The following is a typical example of Case 2.1

The two artificial variables are not in the basis, hence w is equal to zero.

Case 2.2 represents a degenerate basis, namely a situation where one or more of the basic variables are equal to zero. Here is an example:

To take a degenerate artificial variable out of the basis we pivot on any non-artificial variable whose coefficient in the row of the artificial is not equal to zero and enter it into the basis.

Fore example, in the table above, we can replace x 6 by either x 2 or x 3 or x 4 .

If the coefficients of all the non-artificial variables in that row are zeros, then the conclusion is that the constraint is redundant and thus can be ignored.

More to come soon .......

• 3D-Functions Plotter
• Runge Kutta Methods
• The Simplex Algorithm
• Matrix calculator
• 2D-Functions Plotter
• Complex functions
• Functions Analyzer
• Fourier Series
• Prime numbers calculator
• Latex Editor
• Linear Programming
• Simplex Pivot Element
• The 2-Phase Method
• The online Simplex method
• Differential Equations
• Runge-Kutta Methods
• Fehlberg Methods
• Runge-Kutta On line
• The Complex plane
• Complex variable functions
• The complex derivate
• Complex integration
• Cauchy's integral formula
• Hilbert Spaces
• Fourier Series Convergence
• Discontinuities Behavour
• The Online Fourier Series
• Linear programing Basics
• Differentiable Functions
• Convex Functions
• Lagrange Multipliers
• Eigenvalues
• Matrix Diagonalizations
• Jordan canonical form
• Online Systems
• Simplex method example
• Finite Solution Example
• Unbounded Solution Sample
• Infinite Solutions Sample
• Uncompatible Constraints
• Jordan Cannonical form 3x3
• Jordan 3x3(2)
• Ejemplo Serie de Fourier
• The Euler's method
• Three eighths rule in Matlab
• Dormand/Prince 4 and 5
• Modelling the Brusselator

Linear programming examples

Complex example of two phase method.

Next iteration

So, we have reached the end of the first phase with the solution x 7 =0 and the best value obtained is the trivial one. Thus, we can forward to second phase.

We go on the second phase, we eliminate the artificial variables and we reestablish the original function, that is, we reconstruct the table as follows.

Next iteration 2.

Thus, we have reached the end of phase 2 because the optimality criterion holds. We have finite optimum solution at the extreme point of coordinates

with the optimal value (remember to change the original objective function again)

Was useful? want add anything?

Post from other users, livis liquoro:.

• school Campus Bookshelves
• menu_book Bookshelves
• perm_media Learning Objects
• login Login
• how_to_reg Request Instructor Account
• hub Instructor Commons
• Download Page (PDF)
• Download Full Book (PDF)
• Periodic Table
• Physics Constants
• Scientific Calculator
• Reference & Cite
• Tools expand_more
• Readability

selected template will load here

This action is not available.

4.2.1: Maximization By The Simplex Method (Exercises)

• Last updated
• Save as PDF
• Page ID 37871

• Rupinder Sekhon and Roberta Bloom
• De Anza College

SECTION 4.2 PROBLEM SET: MAXIMIZATION BY THE SIMPLEX METHOD

Solve the following linear programming problems using the simplex method.

1) \[\begin{array}{ll} \text { Maximize } & \mathrm{z}=\mathrm{x}_{1}+2 \mathrm{x}_{2}+3 \mathrm{x}_{3} \\ \text { subject to } & \mathrm{x}_{1}+\mathrm{x}_{2}+\mathrm{x}_3 \leq 12 \\ & 2 \mathrm{x}_{1}+\mathrm{x}_{2}+3 \mathrm{x}_{3} \leq 18 \\ & \mathrm{x}_{1}, \mathrm{x}_{2}, \mathrm{x}_{3} \geq 0 \end{array} \nonumber \]

2) \[\begin{array}{ll} \text { Maximize } \quad z= & x_{1}+2 x_{2}+x_{3} \\ \text { subject to } & x_{1}+x_{2} \leq 3 \\ & x_{2}+x_{3} \leq 4 \\ & x_{1}+x_{3} \leq 5 \\ & x_{1}, x_{2}, x_{3} \geq 0 \end{array} \nonumber \]

3) A farmer has 100 acres of land on which she plans to grow wheat and corn. Each acre of wheat requires 4 hours of labor and $20 of capital, and each acre of corn requires 16 hours of labor and $40 of capital. The farmer has at most 800 hours of labor and $2400 of capital available. If the profit from an acre of wheat is $80 and from an acre of corn is $100, how many acres of each crop should she plant to maximize her profit?

4) A factory manufactures chairs, tables and bookcases each requiring the use of three operations: Cutting, Assembly, and Finishing. The first operation can be used at most 600 hours; the second at most 500 hours; and the third at most 300 hours. A chair requires 1 hour of cutting, 1 hour of assembly, and 1 hour of finishing; a table needs 1 hour of cutting, 2 hours of assembly, and 1 hour of finishing; and a bookcase requires 3 hours of cutting, 1 hour of assembly, and 1 hour of finishing. If the profit is $20 per unit for a chair, $30 for a table, and $25 for a bookcase, how many units of each should be manufactured to maximize profit?

5). The Acme Apple company sells its Pippin, Macintosh, and Fuji apples in mixes. Box I contains 4 apples of each kind; Box II contains 6 Pippin, 3 Macintosh, and 3 Fuji; and Box III contains no Pippin, 8 Macintosh and 4 Fuji apples. At the end of the season, the company has altogether 2800 Pippin, 2200 Macintosh, and 2300 Fuji apples left. Determine the maximum number of boxes that the company can make.