9887

Two-Phase Simplex Method

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.

SNAPSHOTS

  • [Snapshot]
  • [Snapshot]
  • [Snapshot]
  • [Snapshot]

DETAILS

Phase 1 of the two-phase simplex algorithm tries to find a basic feasible solution. Artificial variables are introduced in phase 1 and dropped at the beginning of phase 2. If the constraints are feasible, then the basic feasible solution obtained at the end of phase 1 is used in phase 2 to begin a search for the optimal solution (which lies at one of the corners of the convex polytope defined by the constraint equations). The denote slack variables.
In phase 1, the top row of the table represents the objective equation that we try to minimize to zero in our search for a basic feasible solution. The second row from the top represents our actual objective function in phase 1.
At the beginning of phase 2, the top row is dropped and the new top row represents the actual objective function .
If the linear programming problem immediately offers a basic feasible solution, phase 1 is bypassed. No artificial variables are introduced.
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.
In two-dimensional cases, the value attained by the original variables as inferred from the table is indicated by a red dot in the corresponding graphic.
For details of the algorithm used, please refer to Chapter 3 of [1].
Reference
[1] S. S. Rao, Engineering Optimization:Theory and Practice, 3rd ed., New Delhi: New Age International, 2006.
    • Share:

Embed Interactive Demonstration New!

Just copy and paste this snippet of JavaScript code into your website or blog to put the live Demonstration on your site. More details »

Files require Wolfram CDF Player or Mathematica.









 
RELATED RESOURCES
Mathematica »
The #1 tool for creating Demonstrations
and anything technical.
Wolfram|Alpha »
Explore anything with the first
computational knowledge engine.
MathWorld »
The web's most extensive
mathematics resource.
Course Assistant Apps »
An app for every course—
right in the palm of your hand.
Wolfram Blog »
Read our views on math,
science, and technology.
Computable Document Format »
The format that makes Demonstrations
(and any information) easy to share and
interact with.
STEM Initiative »
Programs & resources for
educators, schools & students.
Computerbasedmath.org »
Join the initiative for modernizing
math education.
Step-by-step Solutions »
Walk through homework problems one step at a time, with hints to help along the way.
Wolfram Problem Generator »
Unlimited random practice problems and answers with built-in Step-by-step solutions. Practice online or make a printable study sheet.
Wolfram Language »
Knowledge-based programming for everyone.
Powered by Wolfram Mathematica © 2014 Wolfram Demonstrations Project & Contributors  |  Terms of Use  |  Privacy Policy  |  RSS Give us your feedback
Note: To run this Demonstration you need Mathematica 7+ or the free Mathematica Player 7EX
Download or upgrade to Mathematica Player 7EX
I already have Mathematica Player or Mathematica 7+