ma37a sesión #6 software para programación lineal · para ramos futuros y mundo laboral, puede...

MA37ASesion #6

Software para Programacion Lineal

Oscar Peredo

29 de Octubre del 2008

Esquema

1 Programacion Lineal

2 Lenguajes de alto nivelMATLAB/OCTAVEAMPLGAMS

3 SolversCPLEXGLPK

4 Otras alternativasMicrosoft Excel Solver

5 Conclusiones

Esquema

1 Programacion Lineal

2 Lenguajes de alto nivelMATLAB/OCTAVEAMPLGAMS

3 SolversCPLEXGLPK

4 Otras alternativasMicrosoft Excel Solver

5 Conclusiones

Objetivos

Para ramos futuros y mundo laboral, puede ser util saberutilizar un software para PL (aplicaciones en practicamentetodas las ramas de la ingenierıa).

PL es la rama de la Optimizacion mas entendible (y por lotanto mas personas e instituciones la utilizan).

Matematicas, Computacion e Industrias.

Problema

Para c ∈ Rn, A ∈ Rm×n y b ∈ Rm, nos interesa resolver

(PL)

minx∈Rn cT x

s.a Ax = bx ≥ 0

Diagrama de Software para PL

Esquema

1 Programacion Lineal

2 Lenguajes de alto nivelMATLAB/OCTAVEAMPLGAMS

3 SolversCPLEXGLPK

4 Otras alternativasMicrosoft Excel Solver

5 Conclusiones

MATLAB/OCTAVE

Software orientado al calculonumerico (matrices).

Desarrollados desde 1984(MATLAB) y 1992 (OCTAVE),software comercial (MATLAB) ylibre (OCTAVE).

Soportan lenguaje M,desarrollado a partir de 1970.

Diversas herramientas paraOptimizacion: OptimizationToolbox, funciones propias, etc.

AMPL

A Mathematical ProgrammingLanguage

Desarrollado en Bell Labs.posterior al 2000 por Fourer,Gay & Kernighan.

AMPL

minx∈R|P|

|P|∑j=1

cjxj

s.a|P|∑j=1

1

ajxj ≤ b

xj ∈ [0, uj ], j = 1, . . . , |P|set P;

param a {j in P};

param b;

param c {j in P};

param u {j in P};

var X {j in P};

maximize Total_Profit: sum {j in P} c[j] * X[j];

subject to Time: sum {j in P} (1/a[j]) * X[j] <= b;

subject to Limit {j in P}: 0 <= X[j] <= u[j];

GAMS

General Algebraic ModelingSystem

Desarrollado por el BancoMundial desde 1975 y porGAMS DevelopmentCorporation desde 1987, con laparticipacion de diversoseconomistas y matematicos(premios Nobel).

GAMS

minx∈R|P|

|P|∑j=1

cjxj

s.a|P|∑j=1

1

ajxj ≤ b

xj ∈ [0, uj ], j = 1, . . . , |P|Sets

j indice /1,2,3,4/;

Parameters

a(j) coeficientes

/ 1 23

2 12

3 5

4 1.4 /

u(j) cota superior

/ 1 100

2 100

3 100

4 100 / ;

Scalar b lado derecho /90/;

Variables

x(j) variables;

Positive Variable x ;

Equations

objetivo define funcion objectivo

restr(j) restriccion j ;

objetivo .. z =e= sum(j, c(j)*x(j)) ;

restr(j) .. sum(j, (1/a(j))*x(j)) =l= b ;

Model ejemplo /all/ ;

Solve ejemplo using lp minimizing z ;

Display x.l, x.m ;

Esquema

1 Programacion Lineal

2 Lenguajes de alto nivelMATLAB/OCTAVEAMPLGAMS

3 SolversCPLEXGLPK

4 Otras alternativasMicrosoft Excel Solver

5 Conclusiones

CPLEX

CPLEX=C+Simplex (hoycontiene diversos metodos,ademas de Simplex)

Desarrollado por Robert E.Bixby y vendido vıa CPLEXOptimization Inc., adquirida porILOG in 1997.

Diversas empresas yuniversidades utilizan este solvercomercial.

Librerıa llamable desde ellenguaje C.

CPLEX

#include <ilcplex/cplex.h>

#include <stdlib.h>

...

int

main (int argc, char **argv)

{

...

env = CPXopenCPLEX (&status);

...

status = CPXsetintparam (env, CPX_PARAM_SCRIND, CPX_ON);

...

status = CPXsetintparam (env, CPX_PARAM_DATACHECK, CPX_ON);

...

lp = CPXcreateprob (env, &status, "lpex1");

...

status = CPXlpopt (env, lp);

...

status = CPXsolution (env, lp, &solstat, &objval, x, pi, slack, dj);

...

status = CPXwriteprob (env, lp, "lpex1.lp", NULL);

...

}

GLPK

GNU Linear Programming Kit

Desarrollado como proyectoGNU por Andrew Makhorindesde el ano 2000.

Librerıa llamable desde ellenguaje C.

GLPK

#include <stdio.h>

#include <stdlib.h>

#include "glpk.h"

int main(void)

{

LPX *lp;

int ia[1+1000], ja[1+1000];

double ar[1+1000], Z, x1, x2, x3;

lp = lpx_create_prob();

lpx_set_prob_name(lp, "sample");

lpx_set_obj_dir(lp, LPX_MAX);

lpx_add_rows(lp, 3);

lpx_set_row_name(lp, 1, "p");

lpx_set_row_bnds(lp, 1, LPX_UP, 0.0, 100.0);

...

lpx_add_cols(lp, 3);

lpx_set_col_name(lp, 1, "x1");

lpx_set_col_bnds(lp, 1, LPX_LO, 0.0, 0.0);

...

lpx_load_matrix(lp, 9, ia, ja, ar);

lpx_simplex(lp);

Z = lpx_get_obj_val(lp);

x1 = lpx_get_col_prim(lp, 1);

...

lpx_delete_prob(lp);

return 0;

}

Esquema

1 Programacion Lineal

2 Lenguajes de alto nivelMATLAB/OCTAVEAMPLGAMS

3 SolversCPLEXGLPK

4 Otras alternativasMicrosoft Excel Solver

5 Conclusiones

Microsoft Excel Solver

Orientado a la planilla de calculo (worksheet).

Sirve para problemas pequenos.

Posee poca escalabilidad (cuando el problema crece) y suinteraccion con otros sistemas es pobre (no es un sistemadedicado a la Optimizacion, esta dedicado a la Gestion).

Se puede complementar con Macros (VBA: Visual Basic forApplications)

Excel

Sub SolverMacro()’ Example Solver VBA Macro

SolverResetSolverOk SetCell:="$B$24", _

MaxMinVal:=2, _ValueOf:="0", _ByChange:="$B$16:$B$17"

SolverSolve userFinish:=TrueEnd Sub

Esquema

1 Programacion Lineal

2 Lenguajes de alto nivelMATLAB/OCTAVEAMPLGAMS

3 SolversCPLEXGLPK

4 Otras alternativasMicrosoft Excel Solver

5 Conclusiones

Conclusiones

Existen muchas alternativas de software para Optimizacion enPL.

¿Como se utiliza la Optimizacion en las empresas?

Cada empresa modela e implementa de acuerdo a susnecesidades.

Se debe utilizar la mejor alternativa de la que se disponga($,tiempo,recurso humano).

FIN