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

23
MA37A Sesi´ on #6 Software para Programaci´ on Lineal Oscar Peredo 29 de Octubre del 2008

Upload: others

Post on 18-Aug-2020

1 views

Category:

Documents


0 download

TRANSCRIPT

Page 1: MA37A Sesión #6 Software para Programación Lineal · Para ramos futuros y mundo laboral, puede ser u´til saber utilizar un software para PL (aplicaciones en practicamente todas

MA37ASesion #6

Software para Programacion Lineal

Oscar Peredo

29 de Octubre del 2008

Page 2: MA37A Sesión #6 Software para Programación Lineal · Para ramos futuros y mundo laboral, puede ser u´til saber utilizar un software para PL (aplicaciones en practicamente todas

Esquema

1 Programacion Lineal

2 Lenguajes de alto nivelMATLAB/OCTAVEAMPLGAMS

3 SolversCPLEXGLPK

4 Otras alternativasMicrosoft Excel Solver

5 Conclusiones

Page 3: MA37A Sesión #6 Software para Programación Lineal · Para ramos futuros y mundo laboral, puede ser u´til saber utilizar un software para PL (aplicaciones en practicamente todas

Esquema

1 Programacion Lineal

2 Lenguajes de alto nivelMATLAB/OCTAVEAMPLGAMS

3 SolversCPLEXGLPK

4 Otras alternativasMicrosoft Excel Solver

5 Conclusiones

Page 4: MA37A Sesión #6 Software para Programación Lineal · Para ramos futuros y mundo laboral, puede ser u´til saber utilizar un software para PL (aplicaciones en practicamente todas

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.

Page 5: MA37A Sesión #6 Software para Programación Lineal · Para ramos futuros y mundo laboral, puede ser u´til saber utilizar un software para PL (aplicaciones en practicamente todas

Problema

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

(PL)

minx∈Rn cT x

s.a Ax = bx ≥ 0

Page 6: MA37A Sesión #6 Software para Programación Lineal · Para ramos futuros y mundo laboral, puede ser u´til saber utilizar un software para PL (aplicaciones en practicamente todas

Diagrama de Software para PL

Page 7: MA37A Sesión #6 Software para Programación Lineal · Para ramos futuros y mundo laboral, puede ser u´til saber utilizar un software para PL (aplicaciones en practicamente todas

Esquema

1 Programacion Lineal

2 Lenguajes de alto nivelMATLAB/OCTAVEAMPLGAMS

3 SolversCPLEXGLPK

4 Otras alternativasMicrosoft Excel Solver

5 Conclusiones

Page 8: MA37A Sesión #6 Software para Programación Lineal · Para ramos futuros y mundo laboral, puede ser u´til saber utilizar un software para PL (aplicaciones en practicamente todas

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.

Page 9: MA37A Sesión #6 Software para Programación Lineal · Para ramos futuros y mundo laboral, puede ser u´til saber utilizar un software para PL (aplicaciones en practicamente todas

AMPL

A Mathematical ProgrammingLanguage

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

Page 10: MA37A Sesión #6 Software para Programación Lineal · Para ramos futuros y mundo laboral, puede ser u´til saber utilizar un software para PL (aplicaciones en practicamente todas

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];

Page 11: MA37A Sesión #6 Software para Programación Lineal · Para ramos futuros y mundo laboral, puede ser u´til saber utilizar un software para PL (aplicaciones en practicamente todas

GAMS

General Algebraic ModelingSystem

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

Page 12: MA37A Sesión #6 Software para Programación Lineal · Para ramos futuros y mundo laboral, puede ser u´til saber utilizar un software para PL (aplicaciones en practicamente todas

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 ;

Page 13: MA37A Sesión #6 Software para Programación Lineal · Para ramos futuros y mundo laboral, puede ser u´til saber utilizar un software para PL (aplicaciones en practicamente todas

Esquema

1 Programacion Lineal

2 Lenguajes de alto nivelMATLAB/OCTAVEAMPLGAMS

3 SolversCPLEXGLPK

4 Otras alternativasMicrosoft Excel Solver

5 Conclusiones

Page 14: MA37A Sesión #6 Software para Programación Lineal · Para ramos futuros y mundo laboral, puede ser u´til saber utilizar un software para PL (aplicaciones en practicamente todas

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.

Page 15: MA37A Sesión #6 Software para Programación Lineal · Para ramos futuros y mundo laboral, puede ser u´til saber utilizar un software para PL (aplicaciones en practicamente todas

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);

...

}

Page 16: MA37A Sesión #6 Software para Programación Lineal · Para ramos futuros y mundo laboral, puede ser u´til saber utilizar un software para PL (aplicaciones en practicamente todas

GLPK

GNU Linear Programming Kit

Desarrollado como proyectoGNU por Andrew Makhorindesde el ano 2000.

Librerıa llamable desde ellenguaje C.

Page 17: MA37A Sesión #6 Software para Programación Lineal · Para ramos futuros y mundo laboral, puede ser u´til saber utilizar un software para PL (aplicaciones en practicamente todas

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;

}

Page 18: MA37A Sesión #6 Software para Programación Lineal · Para ramos futuros y mundo laboral, puede ser u´til saber utilizar un software para PL (aplicaciones en practicamente todas

Esquema

1 Programacion Lineal

2 Lenguajes de alto nivelMATLAB/OCTAVEAMPLGAMS

3 SolversCPLEXGLPK

4 Otras alternativasMicrosoft Excel Solver

5 Conclusiones

Page 19: MA37A Sesión #6 Software para Programación Lineal · Para ramos futuros y mundo laboral, puede ser u´til saber utilizar un software para PL (aplicaciones en practicamente todas

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)

Page 20: MA37A Sesión #6 Software para Programación Lineal · Para ramos futuros y mundo laboral, puede ser u´til saber utilizar un software para PL (aplicaciones en practicamente todas

Excel

Sub SolverMacro()’ Example Solver VBA Macro

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

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

SolverSolve userFinish:=TrueEnd Sub

Page 21: MA37A Sesión #6 Software para Programación Lineal · Para ramos futuros y mundo laboral, puede ser u´til saber utilizar un software para PL (aplicaciones en practicamente todas

Esquema

1 Programacion Lineal

2 Lenguajes de alto nivelMATLAB/OCTAVEAMPLGAMS

3 SolversCPLEXGLPK

4 Otras alternativasMicrosoft Excel Solver

5 Conclusiones

Page 22: MA37A Sesión #6 Software para Programación Lineal · Para ramos futuros y mundo laboral, puede ser u´til saber utilizar un software para PL (aplicaciones en practicamente todas

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).

Page 23: MA37A Sesión #6 Software para Programación Lineal · Para ramos futuros y mundo laboral, puede ser u´til saber utilizar un software para PL (aplicaciones en practicamente todas

FIN