Linear programming

Constraint and linear programming are useful paradigms for formulating and solving problems that can be naturally defined in terms of constraints among a set of variables. Solving such problems consists of finding such combinations of values of the variables that satisfy the constraints. This is called constraint satisfaction. The origins of LP (linear programming) date back to the late 1940s when G. B Dantiz developed a very efficient and general algebraic method known as the "Simplex method" that could solve LP problems. about a decade later, Dantig published a major survey covering the theoretical developments and applications of linear programming up to the early 1960. Since the publication of Datzig's original paper, pratically hundreds of books and thousands of research articles on LP have appeared in dozens of different languages. Any text book on operations research published since 1950s has at least one chapter describing LP. Linear programming is now a very important and established branch of operations research that has found wide applicability. Despite the mathematical nature of the simplex method, wich requires a good understanding of linear algebra, LP has become one of the most useful operations research techniques and is frequently used by practitioners. In the following examples i will brifely describe how to model some the problems such as Shortest path problem etc. using the Object Pascal language and the Freepascal or Delphi compilers and the FastCLP and LPSolve softwares.

1. Linear programming formulation of the Shortest-Route problem

Consider the shortest-route network in the following figure. Suppose that we want to determine the shortest route from node 1 to node 2. The figure shows how the unit of flow enters at node 1 and leaves at node 2.

We can see from the network that the flow-conservation equation yields:

Node 1: 1 = x12 + x13

Node 2: x12 + x42 = x23 + 1

Node 3: x13 + x23 = x34 + x35

Node 4 : x34 = x42 + x45

Node 5: x35 + x45 = 0

And the function to minimize is:

Z = 100*x12 + 30*x13 + 20*x23 + 10*x34 + 60*x35 + 15*x42 + 50*x45

And the formulation in Object pascal using FastCLP and LPSolve is:

program demo; {$APPTYPE CONSOLE} uses windows,SysUtils,lpsolve,fastclp1; var majorversion, minorversion, release, build: integer; lp: THandle; variables: array[0..7] of real; constraints: array[0..7] of real; row :array[0..7] of real; name1,name2:pchar; a,i:integer; procedure press_ret; begin writeln('[return]'); readln; end; procedure error; begin writeln('error'); if (lp <> 0) then delete_lp(lp); readln; halt(1); end; begin a:=7; lp := make_lp(0, a); if (lp = 0) then error; set_debug(lp,false); set_outputfile(lp,'log.txt'); set_add_rowmode(lp, TRUE); for i:=1 to a do row[i]:=0; row[1]:= 1.0; row[2]:= 1.0; if (not add_constraint(lp, @row, EQ, 1.0)) then error; for i:=1 to a do row[i]:=0; row[1] := 1.0; row[3]:= -1.0; row[6]:= 1.0; if (not add_constraint(lp, @row, EQ, 1.0)) then error; for i:=1 to a do row[i]:=0; row[2]:= 1.0; row[3]:= 1.0;row[4]:= -1.0; row[5]:= -1.0; if (not add_constraint(lp, @row, EQ, 0.0)) then error; for i:=1 to a do row[i]:=0; row[4]:= 1.0; row[6]:= -1.0;row[7]:= -1.0; if (not add_constraint(lp, @row, EQ, 0.0)) then error; for i:=1 to a do row[i]:=0; row[5]:= 1.0; row[7]:= 1.0; if (not add_constraint(lp, @row, EQ, 0.0)) then error; for i:=0 to a-1 do row[i]:=0; row[1]:= 100.0; row[2]:= 30.0;row[3]:= 20.0; row[4]:= 10.0; row[5]:= 60.0; row[6]:= 15.0;row[7]:= 50.0; if (not set_obj_fn(lp, @row)) then error; set_add_rowmode(lp, FALSE); //set_binary(lp,1,true); //set_binary(lp,2,true); //set_binary(lp,3,true); //set_binary(lp,4,true); //set_binary(lp,5,true); //set_binary(lp,6,true); //set_binary(lp,7,true); set_minim(lp); writeln('after solving this gives us:'); solve(lp); writeln('Value of objective function: ',Format('%.2f',[get_objective(lp)])); get_variables(lp,@variables); writeln('Actual values of the variables: '); writeln('X1: ',Format('%.2f',[variables[0]])); writeln('X2: ',Format('%.2f',[variables[1]])); writeln('X3: ',Format('%.2f',[variables[2]])); writeln('X4: ',Format('%.2f',[variables[3]])); writeln('X5: ',Format('%.2f',[variables[4]])); writeln('X6: ',Format('%.2f',[variables[5]])); writeln('X7: ',Format('%.2f',[variables[6]])); write_mps(lp, '1.mps'); name1:='1.mps'; name2:='solfile1'; fastclp(name1,name2); delete_lp(lp); end.

both FastCLP and LPSolve gives the optimal solution of: z = 55 , x13 = 1 , x34 = 1 , x42 = 1

You can download the source code here:

http://pages.videotron.com/aminer/zip/lp.zip

Please click here to return to my homepage: homepage.

Regards,
Amine Moulay Ramdane.