GLPK (GNU Linear Programming Kit)

Este un pachet de programe dedicat rezolvarii problemelor de programare liniara (LP), programare liniara in numere intregi (MIP) si alte probleme conexe.

Este cel mai performant pachet de programe gratuit pentru acest scop. Este scris in C dar pachete de interconectare au fost scrise pentru majoritatea limbajelor de programare.

Pentru descrierea problemelor foloseste un limbaj specializat GMPL.

Iata cum este descrisa o problema simpla in tutorialul lui Rodrigo Ceron de la IBM:

 
 # Giapetto's problem
 #
 # This finds the optimal solution f
 # or maximizing Giapetto's profit
 #

  /* Decision variables */
  var x1 >=0;  /* soldier */
  var x2 >=0;  /* train */

 /* Objective function */
 maximize z: 3*x1 + 2*x2;

 /* Constraints */
s.t. Finishing : 2*x1 + x2 <= 100;
s.t. Carpentry : x1 + x2 <= 80;
s.t. Demand    : x1 <= 40;

end;

Foarte simplu nu-i asa? Daca ai scrie simplex-ul singur probabil ca ar lua mult mai mult timp…

Exista si un IDE de lucru (destul de primitiv): GUSEK (GLPK Under Scite Extended Kit), o aplicatie gata compilata pentru Windows precum si o interfata cu Java.

Articole de la IBM’s developerWorks:

• Introduction to linear optimization
• Intermediate problems in linear programming
• Advanced problems and elegant solutions