Sunday, October 04, 2009

Linear Programming problem solver in ubuntu

Did your teacher give you a hard linear programming(LP) problem as home assignment? Then ubuntu is ready to help you..It's very easy to solve LP problems in ubuntu.You can use the command lp_solve for that.

Format of the command:

lp_solve [options] inputfilename

The input file can be of different formats like lp , mps etc. I will use lp here.A lp file look like this( open your favorite editor- i prefer geany and start writing)

max: 143 x + 60 y;

120 x + 210 y <= 15000; 110 x + 30 y <= 4000; x + y <= 75; x >= 0;
y >= 0;

and save as "anyname.lp" // give whatever name you wanna giv ..names doesn't matter for anything.

and use the command " lp_solve -lp anyname.lp " .
This will give you the optimal solution of the objective function.This software is using the
simplex algorithm to solve the problem .

For any help use this command " lp_solve -h "

//Remaining is for newbies who dont know what a LP problem is
Intro:

A linear programming problem may be defined as the problem of maximizing or minimizing a linear function subject to linear constraints. The constraints may be equalities
or inequalities. Here is a simple example.

Find numbers x1 and x2 that maximize the sum x1 + x2 subject to the constraints
x1 ≥ 0, x2 ≥ 0, and
x1 + 2x2 ≤ 4
4x1 + 2x2 ≤ 12
−x1 + x2 ≤ 1

In this problem there are two unknowns, and five constraints. All the constraints are
inequalities and they are all linear in the sense that each involves an inequality in some
linear function of the variables. The first two constraints, x1 ≥ 0 and x2 ≥ 0, are special.
These are called non-negativity constraints and are often found in linear programming
problems. The other constraints are then called the main constraints. The function to be
maximized (or minimized) is called the objective function. Here, the objective function is
x1 + x2