La programación lineal es un conjunto de técnicas racionales de análisis y de resolución de problemas que tiene por objeto ayudar a los responsables en las decisiones sobre asuntos en los que interviene un gran número de variables.

El nombre de programación lineal no procede de la creación de programas de ordenador, sino de un término militar, programar, que significa 'realizar planes o propuestas de tiempo para el entrenamiento, la logística o el despliegue de las unidades de combate'.

El procedimiento es iterativo, pues mejora los resultados de la función objetivo en cada etapa hasta alcanzar la solución buscada. Ésta se encuentra en un vértice del que no parta ninguna arista a lo largo de la cual la función objetivo aumente.

viernes, 20 de agosto de 2010

EJERCICIO 5.2-3


Publicado por en No hay comentarios:

sábado, 14 de agosto de 2010

TALLER EN GAMS

1.GAMS Rev 233  WIN-VIS 23.3.2 x86/MS Windows             08/14/10 11:34:25 Page 1
weenies buns
C o m p i l a t i o n


   2
   3  Sets
   4           i costos /costo1, costo2, costo3/
   5           j productos /producto1, producto2/
   6           k ganancias /ganancia1, ganancia2/;
   7
   8  Parameters
   9
  10           b(i) consumo del costo i en los casos
  11           /       costo1 200
  12                   costo2 800
  13                   costo3 12000/
  14
  15           c(k)  ganancia por producir un elemento en pesos
  16           / ganancia1 0.2
  17             ganancia2 0.1 /;
  18
  19  Table m(j,k)
  20            ganancia1         ganancia2
  21  Producto1    0.2                0
  22  Producto2     0                0.1           ;
  23
  24  Table h(i,j) cantidad de costo por producto
  25
  26               producto1    producto2
  27  costo1          0           0.1
  28  costo2         0.25          0
  29  costo3          3            2 ;
  30
  31
  32
  33  Variables
  34           x(j,k)  lo que se debe pedir de cada producto
  35           z      ganancia total de producción          ;
  36
  37  Positive variable x;
  38
  39  Equations
  40           ganancia
  41           costos(i) ;
  42
  43           ganancia ..        z =e= sum((j,k), m(j,k)*x(j,k));
  44
  45           costos(i) .. sum((j,k), h(i,j)*x(j,k)) =l= b(i) ;
  46  model weeniesbuns / all/
  47
  48  solve weeniesbuns  using lp maximizing z
  49
  50
  51
  52  Display x.l, x.m ;


COMPILATION TIME     =        0.016 SECONDS      3 Mb  WIN233-233 Nov 17, 2009
GAMS Rev 233  WIN-VIS 23.3.2 x86/MS Windows             08/14/10 11:34:25 Page 2
weenies buns
Equation Listing    SOLVE weeniesbuns Using LP From line 52


---- ganancia  =E=

ganancia..  - 0.2*x(producto1,ganancia1) - 0.1*x(producto2,ganancia2) + z =E= 0
      ; (LHS = 0)
  

---- costos  =L=

costos(costo1)..  0.1*x(producto2,ganancia1) + 0.1*x(producto2,ganancia2) =L=
     200 ; (LHS = 0)
  
costos(costo2)..  0.25*x(producto1,ganancia1) + 0.25*x(producto1,ganancia2) =L=
     800 ; (LHS = 0)
  
costos(costo3)..  3*x(producto1,ganancia1) + 3*x(producto1,ganancia2)
  
      + 2*x(producto2,ganancia1) + 2*x(producto2,ganancia2) =L= 12000 ;
  
      (LHS = 0)
  
GAMS Rev 233  WIN-VIS 23.3.2 x86/MS Windows             08/14/10 11:34:25 Page 3
weenies buns
Column Listing      SOLVE weeniesbuns Using LP From line 52


---- x  lo que se debe pedir de cada producto

x(producto1,ganancia1)
                (.LO, .L, .UP, .M = 0, 0, +INF, 0)
       -0.2     ganancia
        0.25    costos(costo2)
        3       costos(costo3)

x(producto1,ganancia2)
                (.LO, .L, .UP, .M = 0, 0, +INF, 0)
        0.25    costos(costo2)
        3       costos(costo3)

x(producto2,ganancia1)
                (.LO, .L, .UP, .M = 0, 0, +INF, 0)
        0.1     costos(costo1)
        2       costos(costo3)

REMAINING ENTRY SKIPPED

---- z  ganancia total de producción

z
                (.LO, .L, .UP, .M = -INF, 0, +INF, 0)
        1       ganancia

GAMS Rev 233  WIN-VIS 23.3.2 x86/MS Windows             08/14/10 11:34:25 Page 4
weenies buns
Model Statistics    SOLVE weeniesbuns Using LP From line 52


MODEL STATISTICS

BLOCKS OF EQUATIONS           2     SINGLE EQUATIONS            4
BLOCKS OF VARIABLES           2     SINGLE VARIABLES            5
NON ZERO ELEMENTS            11


GENERATION TIME      =        0.031 SECONDS      4 Mb  WIN233-233 Nov 17, 2009


EXECUTION TIME       =        0.031 SECONDS      4 Mb  WIN233-233 Nov 17, 2009
GAMS Rev 233  WIN-VIS 23.3.2 x86/MS Windows             08/14/10 11:34:25 Page 5
weenies buns
Solution Report     SOLVE weeniesbuns Using LP From line 52


               S O L V E      S U M M A R Y

     MODEL   weeniesbuns         OBJECTIVE  z
     TYPE    LP                  DIRECTION  MAXIMIZE
     SOLVER  CPLEX               FROM LINE  52

**** SOLVER STATUS     1 Normal Completion      
**** MODEL STATUS      1 Optimal                
**** OBJECTIVE VALUE              760.0000

 RESOURCE USAGE, LIMIT          0.015      1000.000
 ITERATION COUNT, LIMIT         1    2000000000

ILOG CPLEX       Nov  1, 2009 23.3.2 WIN 13908.14598 VIS x86/MS Windows
Cplex 12.1.0, GAMS Link 34

LP status(1): optimal
Optimal solution found.
Objective :         760.000000


                       LOWER     LEVEL     UPPER    MARGINAL

---- EQU ganancia        .         .         .        1.000    

---- EQU costos

          LOWER     LEVEL     UPPER    MARGINAL

costo1     -INF    120.000   200.000      .      
costo2     -INF    800.000   800.000     0.200    
costo3     -INF  12000.000 12000.000     0.050    

---- VAR x  lo que se debe pedir de cada producto

                       LOWER     LEVEL     UPPER    MARGINAL

producto1.ganancia1      .     3200.000     +INF       .      
producto1.ganancia2      .         .        +INF     -0.200    
producto2.ganancia1      .         .        +INF     -0.100    
producto2.ganancia2      .     1200.000     +INF       .      

                       LOWER     LEVEL     UPPER    MARGINAL

---- VAR z              -INF    760.000     +INF       .      

  z  ganancia total de producción


**** REPORT SUMMARY :        0     NONOPT
                             0 INFEASIBLE
                             0  UNBOUNDED
GAMS Rev 233  WIN-VIS 23.3.2 x86/MS Windows             08/14/10 11:34:25 Page 6
weenies buns
E x e c u t i o n


----     52 VARIABLE x.L  lo que se debe pedir de cada producto

            ganancia1   ganancia2

producto1    3200.000
producto2                1200.000


----     52 VARIABLE x.M  lo que se debe pedir de cada producto

            ganancia1   ganancia2

producto1                  -0.200
producto2      -0.100



EXECUTION TIME       =        0.000 SECONDS      3 Mb  WIN233-233 Nov 17, 2009


USER: Departmento de Ingeniería Industrial           G091203:1120AP-WIN
      Universidad de Antioquia                                   DC8064
      License for teaching and research at degree granting institutions


**** FILE SUMMARY

Input      C:\Users\NESTOR\Documents\UdeA\PROLINEAL\sesión 2\EJERCICIO1.gms
Output     C:\Users\NESTOR\Documents\gamsdir\projdir\EJERCICIO1.lst


2. GAMS Rev 233  WIN-VIS 23.3.2 x86/MS Windows             08/14/10 12:04:29 Page 1
fred cerdos
C o m p i l a t i o n


   2
   3  Sets
   4           i nutritivos /nutritivo1, nutritivo2, nutritivo3/
   5           j productos /producto1, producto2, producto3/
   6           k costos /costo1, costo2, costo3/;
   7
   8  Parameters
   9
  10           b(i) porcentaje del nutritivo i en los casos
  11           /       nutritivo1 200
  12                   nutritivo2 180
  13                   nutritivo3 150/
  14
  15           c(k)  costo por producir un producto en pesos
  16           / costo1 84
  17             costo2 72
  18             costo3 60 /;
  19
  20  Table m(j,k)
  21              costo1       costo2          costo3
  22  Producto1    84             0               0
  23  Producto2     0            72               0
  24  Producto3     0             0              60 ;
  25
  26  Table h(i,j) cantidad de nutritivo por producto
  27
  28               producto1    producto2    producto3
  29  nutritivo1      90           20           40
  30  nutritivo2      30           80           60
  31  nutritivo3      10           20           60 ;
  32
  33
  34
  35  Variables
  36           x(j,k)  lo que se requiere de cada producto
  37           z       costo nimimo de producción          ;
  38
  39  Positive variable x;
  40
  41  Equations
  42           costos
  43           nutritivos(i) ;
  44
  45           costos ..        z =e= sum((j,k), m(j,k)*x(j,k));
  46
  47           nutritivos(i) .. sum((j,k), h(i,j)*x(j,k)) =g= b(i) ;
  48  model fredcerdos / all/
  49
  50  solve fredcerdos  using lp minimizing z
  51
  52
  53
  54  Display x.l, x.m ;


COMPILATION TIME     =        0.000 SECONDS      3 Mb  WIN233-233 Nov 17, 2009
GAMS Rev 233  WIN-VIS 23.3.2 x86/MS Windows             08/14/10 12:04:29 Page 2
fred cerdos
Equation Listing    SOLVE fredcerdos Using LP From line 54


---- costos  =E=

costos..  - 84*x(producto1,costo1) - 72*x(producto2,costo2)
  
      - 60*x(producto3,costo3) + z =E= 0 ; (LHS = 0)
  

---- nutritivos  =G=

nutritivos(nutritivo1)..  90*x(producto1,costo1) + 90*x(producto1,costo2)
  
      + 90*x(producto1,costo3) + 20*x(producto2,costo1) + 20*x(producto2,costo2)
  
      + 20*x(producto2,costo3) + 40*x(producto3,costo1) + 40*x(producto3,costo2)
  
      + 40*x(producto3,costo3) =G= 200 ; (LHS = 0, INFES = 200 ****)
  
nutritivos(nutritivo2)..  30*x(producto1,costo1) + 30*x(producto1,costo2)
  
      + 30*x(producto1,costo3) + 80*x(producto2,costo1) + 80*x(producto2,costo2)
  
      + 80*x(producto2,costo3) + 60*x(producto3,costo1) + 60*x(producto3,costo2)
  
      + 60*x(producto3,costo3) =G= 180 ; (LHS = 0, INFES = 180 ****)
  
nutritivos(nutritivo3)..  10*x(producto1,costo1) + 10*x(producto1,costo2)
  
      + 10*x(producto1,costo3) + 20*x(producto2,costo1) + 20*x(producto2,costo2)
  
      + 20*x(producto2,costo3) + 60*x(producto3,costo1) + 60*x(producto3,costo2)
  
      + 60*x(producto3,costo3) =G= 150 ; (LHS = 0, INFES = 150 ****)
  
GAMS Rev 233  WIN-VIS 23.3.2 x86/MS Windows             08/14/10 12:04:29 Page 3
fred cerdos
Column Listing      SOLVE fredcerdos Using LP From line 54


---- x  lo que se requiere de cada producto

x(producto1,costo1)
                (.LO, .L, .UP, .M = 0, 0, +INF, 0)
      -84       costos
       90       nutritivos(nutritivo1)
       30       nutritivos(nutritivo2)
       10       nutritivos(nutritivo3)

x(producto1,costo2)
                (.LO, .L, .UP, .M = 0, 0, +INF, 0)
       90       nutritivos(nutritivo1)
       30       nutritivos(nutritivo2)
       10       nutritivos(nutritivo3)

x(producto1,costo3)
                (.LO, .L, .UP, .M = 0, 0, +INF, 0)
       90       nutritivos(nutritivo1)
       30       nutritivos(nutritivo2)
       10       nutritivos(nutritivo3)

REMAINING 6 ENTRIES SKIPPED

---- z  costo nimimo de producción

z
                (.LO, .L, .UP, .M = -INF, 0, +INF, 0)
        1       costos

GAMS Rev 233  WIN-VIS 23.3.2 x86/MS Windows             08/14/10 12:04:29 Page 4
fred cerdos
Model Statistics    SOLVE fredcerdos Using LP From line 54


MODEL STATISTICS

BLOCKS OF EQUATIONS           2     SINGLE EQUATIONS            4
BLOCKS OF VARIABLES           2     SINGLE VARIABLES           10
NON ZERO ELEMENTS            31


GENERATION TIME      =        0.000 SECONDS      4 Mb  WIN233-233 Nov 17, 2009


EXECUTION TIME       =        0.000 SECONDS      4 Mb  WIN233-233 Nov 17, 2009
GAMS Rev 233  WIN-VIS 23.3.2 x86/MS Windows             08/14/10 12:04:29 Page 5
fred cerdos
Solution Report     SOLVE fredcerdos Using LP From line 54


               S O L V E      S U M M A R Y

     MODEL   fredcerdos          OBJECTIVE  z
     TYPE    LP                  DIRECTION  MINIMIZE
     SOLVER  CPLEX               FROM LINE  54

**** SOLVER STATUS     1 Normal Completion      
**** MODEL STATUS      1 Optimal                
**** OBJECTIVE VALUE                0.0000

 RESOURCE USAGE, LIMIT          0.013      1000.000
 ITERATION COUNT, LIMIT         0    2000000000

ILOG CPLEX       Nov  1, 2009 23.3.2 WIN 13908.14598 VIS x86/MS Windows
Cplex 12.1.0, GAMS Link 34

LP status(1): optimal
Optimal solution found.
Objective :           0.000000


                       LOWER     LEVEL     UPPER    MARGINAL

---- EQU costos          .         .         .        1.000    

---- EQU nutritivos

              LOWER     LEVEL     UPPER    MARGINAL

nutritivo1   200.000  1350.000     +INF       .      
nutritivo2   180.000   450.000     +INF       .      
nutritivo3   150.000   150.000     +INF       EPS    

---- VAR x  lo que se requiere de cada producto

                    LOWER     LEVEL     UPPER    MARGINAL

producto1.costo1      .         .        +INF     84.000    
producto1.costo2      .       15.000     +INF       .      
producto1.costo3      .         .        +INF       EPS    
producto2.costo1      .         .        +INF       EPS    
producto2.costo2      .         .        +INF     72.000    
producto2.costo3      .         .        +INF       EPS    
producto3.costo1      .         .        +INF       EPS    
producto3.costo2      .         .        +INF       EPS    
producto3.costo3      .         .        +INF     60.000    

                       LOWER     LEVEL     UPPER    MARGINAL

---- VAR z              -INF       .        +INF       .      

  z  costo nimimo de producción


**** REPORT SUMMARY :        0     NONOPT
                             0 INFEASIBLE
                             0  UNBOUNDED
GAMS Rev 233  WIN-VIS 23.3.2 x86/MS Windows             08/14/10 12:04:29 Page 6
fred cerdos
E x e c u t i o n


----     54 VARIABLE x.L  lo que se requiere de cada producto

               costo2

producto1      15.000


----     54 VARIABLE x.M  lo que se requiere de cada producto

               costo1      costo2      costo3

producto1      84.000                     EPS
producto2         EPS      72.000         EPS
producto3         EPS         EPS      60.000



EXECUTION TIME       =        0.000 SECONDS      3 Mb  WIN233-233 Nov 17, 2009


USER: Departmento de Ingeniería Industrial           G091203:1120AP-WIN
      Universidad de Antioquia                                   DC8064
      License for teaching and research at degree granting institutions


**** FILE SUMMARY

Input      C:\Users\NESTOR\Documents\UdeA\PROLINEAL\sesión 2\EJERCICIO2.gms
Output     C:\Users\NESTOR\Documents\gamsdir\projdir\EJERCICIO2.lst



Publicado por en No hay comentarios:

viernes, 13 de agosto de 2010

CUESTIONAMIENTOS DEL CAPITULO 4

  • De que se trata el metodo simplex?
Es un algoritmo eficiente y confiable para resolver problemas de programación lineal.

  • Cual es el objetivo de la prueba del cociente minimo?
Su funcion es determinar que variable basica llega se cero primero cuando crece la variable entrante.


  • De que se trata el metodo de eliminación gaussiana?
Se trata de utilizar las operaciones algebraicas elementales para reducir el sistema de ecuaciones original a la forma aporopiada de eliminación gaussiana, en donde cada variable basica se elimina de todas las ecuaciones menos una (su ecuación) y en esa ecuación tiene coeficiente +1.

  • Si se tiene un empate de coeficientes en la funcion objetivo, como se podría elegir cual usar?
Se puede usar cualquiera de los dos de manera arbitraria.


  • Que es un analisis posoptimo?
Es el analisis que se hace despues de obtener una solucion optima para la versión inicial del modelo, constituye una parte muy importante de casi todos los estudios de investigación de operaciones.

  • Cual es el proposito principal del analisis de sensibilidad?
Su proposito general es identificar los parametros sensibles (aquellos que no pueden cambiar sin cambiar la solución optima).


  • Como se identifican los parametros sensibles?
En el caso de la bi, esta información esta dada por los valores sombra que proporciona el metodo simplex.
Publicado por en No hay comentarios:

EJERCICIOS DE PROGRAMACIÓN LINEAL

3.1-10 Weenies and Buns es una planta procesadora de alimentos que fabrica hotdogs y pan para hotdogs. Muelen su propia harina para el pan a una tasa máxima de 200 libras por semana. Cada pan requiere 0.1 libras. Tiene un contrato con Pigland Inc, que especifica la entrega de 800 libras de producto de puerco cada lunes. Cada hotdog requiere 0.25 libras de producto de puerco. Se cuenta con suficiente cantidad del resto de los ingredientes de ambos productos. Por último, la mano de obra consiste en 5 empleados de tiempo completo (40 horas por semana). Cada hotdog requiere 3 minutos de mano de obra y cada pan requiere 2 minutos de mano de obra. Cada hotdog proporciona una ganancia de $0.20 y cada pan de $0.10. Weenies and Buns desea saber cuántos hotdogs y cuantos panes deben producir cada semana para lograr la ganancia más alta posible.


a) Formule un modelo de programación lineal.
Analizando cada uno de los datos podemos construir la siguiente tabla:

Costos
Hotdogs
Pan
Unidades disponibles
Harina
0
0.1
200
Puerco
0.25
0
800
Mano de obra
3
2
200h = 12000min
Ganancia
0.2
0.1
















Ahora podemos construir el modelo de programación lineal, así:
Hotdogs: X1                       Pan: X2
Función objetivo:            Z = 0.2X1 + 0.1X2
Sujeto a:                             0.1X2 ≤ 200
                                         0.25X1 ≤ 800
                                    3 X1 + 2X2 ≤ 12000
                                         X1 ≥ 0  y  X2 ≥ 0

b)Use el método grafico para resolver el modelo.

Entonces hallamos los puntos de cruce en las X:
 0.1X2 ≤ 200 → X2 ≤ 2000
0.25X1 ≤ 800 → X1 ≤ 3200
3 X1 + 2X2 ≤ 12000 → X1 = 0 → X2 ≤ 12000/2 = 6000
                                → X2 = 0 → X1 ≤ 12000/3 = 4000

Luego por reducción:
(¼ X1 = 800)*-12 = -3 X1 = -9600
(3 X1 + 2X2 = 12000) –(3 X1 = -9600)  → X2 = 1200
Hallamos X1 reemplazando X2 en la tercera ecuación:
3 X1 + 2*1200 = 12000  → X2 = (12000 – 2400)/2 = 3200

Ahora tenemos reemplazamos en la función objetivo:
0.2*(3200) + 0.1*(1200) = 760

La línea que representa la función objetivo es:
X1 = 0 → X2 = 7600
X2 = 0 → X1 = 3800



Finalmente podemos decir que se requieren 3200 hotdogs y 1200 panes para ganar un máximo de $760, que sería la ganancia más alta posible.



3.6-4 Fred Jonasson administra la granja de su familia. Para complementar varios alimentos que se cultivan en la granja, Fred también cría cerdos para venta y desea determinar las cantidades de los diferentes tipos de alimentos disponibles (maíz, grasas y alfalfa) que debe dar a cada cerdo. Como los cerdos se comerán cualquier mezcal de estos tipos de alimento, el objetivo es determinar que mezcla cumple ciertos requisitos nutritivos a un costo mínimo. En la siguiente tabla se dan las unidades de cada tipo de ingrediente nutritivo básico contenido en 1 kilogramo de cada tipo de alimento, junto con los requisitos de nutrición diarios y los costos de los alimentos:









Ingrediente nutritivo
Kilogramo de maíz
Kilogramo de grasas
Kilogramo de alfalfa
Requisito mínimo diario
Carbohidratos
90
20
40
200
Proteínas
30
80
60
180
Vitaminas
10
20
60
150
Costo ($)
84
72
60


a) Formule el modelo de programación lineal.
Ahora podemos construir el modelo de programación lineal, así:
Función objetivo: Minimizar Z = 84X1 + 72X2 + 60X3
Sujeto a:           90X1 + 20X2 + 40X3 ≥ 200
                        30X1 + 80X2 +60X3 ≥ 180
                        10X1 + 20X2 + 60X3 ≥ 150





 X1 ᶺ X2 ᶺ X3 ≥ 0

Para ser resuelto por el método simplex, se debe pasar a un caso de maximización, así:
Maximizar  -Z = - 84X1 - 72X2 - 60X3 - MX5 - MX7 - MX9
Sujeto a:              90X1 + 20X2 + 40X3 - X4 + X5 = 200
                       30X1 + 80X2 +60X3 - X6 + X7 = 180
                       10X1 + 20X2 + 60X3 - X8 + X9 = 150
X1 ᶺ X2 ᶺ X3 ≥ 0

Los grados de libertad = # de variables - # de ecuaciones
                                               = 9 -3 = 6

Ahora hacemos la tabla con los coeficientes de las variables:

V.b
Z
X1
X2
X3
X4
X5
X6
X7
X8
X9
L.D
Z
-1
84
72
60
0
M
0
M
0
M
0
X5
0
90
20
40
-1
1
0
0
0
0
200
X7
0
30
80
60
0
0
-1
1
0
0
180
X9
0
10
20
60
0
0
0
0
-1
1
150
Resolviendo con excel solver:
Kilogramo de
requerimiento mín diario
Total
Ingrediente Nutritivo
Maíz
Grasas
Alfalfa
Carbohidratos
90
20
40
200
200
Proteínas
30
80
60
180
180
Vitaminas
10
20
60
150
157,14
costo unidad
84
72
60


solución
1,14285714
0
2,42857143


241,7142857

Publicado por en 4 comentarios:
Suscribirse a: Entradas (Atom)