IP3

Dakin's Algorithm for Mixed Integer LPs

Dakin's algorithm is a version of branch and bound especially for linear programs that have at least one integer or binary variable (these are called mixed integer linear programs) . We will use Dakin's Algorithm to solve the following mixed integer linear programming problem:

  • Maximize : Z = 8x₁ + 5x₂

Subject to:

  • x₁ + x₂ ≤ 6
  • 9 x₁ + 5 x₂ ≤ 45
  • x₁ , x₂ are integer and non-negative

 

Popular posts from this blog

Contents

Chapter 1: Introduction.  An introduction to the process of optimization and an overview of the major topics covered in the course.  Last revision: December 2020 . Chapter 2: Introduction to Linear Programming.  The basic notions of linear programming and the simplex method. The simplex method is the easiest way to provide a beginner with a solid understanding of linear programming.  Last revision: December 2020. See animation  LP1 . A good  article on formulating LPs  by Gerry Brown and Rob Dell. Example questions with solutions . March 4, 2021. Chapter 3: Towards the Simplex Method for Efficient Solution of Linear Programs.  Cornerpoints and bases. Moving to improved solutions.  Last revision: December 2020 . See animation  LP2 . Chapter 4: The Mechanics of the Simplex Method.  The tableau representation as a way of illustrating the process of the simplex method. Special cases such as degeneracy and unboundedness.  Last revis...
Read more