Linear Programming

Simplex Algorithm

I have coded recently the simplex algorithm. It is an algorithm that solves the optimizations of a problem of linear programming. It gives a function to minimize and constrains the variables with an inequality form.

It can be proven that the simplex algorithm solves this problem in Non-Polynomial time.

Simplex Algorithm

The simplex algorithm iterates over feasible solutions and minimizes the value of the function z

The image below shows an example of the code that solves a linear programming problem

As it shows, it creates a table with the variables used by the algorithm.

Two-phase Method

Sometimes can not find a feasible solution, we can reinterpret the problem of finding a feasible solution with a linear programming one. It executes the simplex algorithm two times, the first to find a feasible solution and the second to optimize.

It can be proven that the optimization of the first problem is equivalent that there exists an optimum solution.

Dual Algorithm

It can be defined the dual problem of ours. It has special properties, whether our problem is not feasible then the dual is not too.

We can use the dual version of the simplex algorithm to find feasible solutions to our problem. It will be used to add new restrictions to the problem

post-Optimization

This is an important part of the problem, we can use an optimized problem to accelerate the optimization of a new version of ours.

  • Add restriction
  • New Costs
  • New independent variables
  • New variable

Integer Linear Programming

We can use the simplex algorithm in order to get an optimized solution to a solution that is integer-only or integer-mixed. We can use two algorithms that I have implemented: Hyper-planes cutting and Ramiction and Bounding.

 

Leave a Reply

Your email address will not be published. Required fields are marked *