ejercicio 3.2-3 Gams

GAMS Rev 233  WIN-VIS 23.3.2 x86/MS Windows             09/29/10 16:12:06 Page 1
giovanni
C o m p i l a t i o n


   2  
   3  
   4  Sets
   5           i variables /dineroe, horae/
   6           j productos /empresa1, empresa2/
   7           k ganancias /ganancia1, ganancia2/;
   8  
   9  Parameters
  10  
  11           b(i) capacidad de la planta i en los casos
  12           /       dineroe 6000
  13                   horae 600/
  14  
  15           c(k)  ganancia por fabricar un elemento en miles de dólares
  16           / ganancia1 4500
  17             ganancia2 4500 /;
  18  
  19  Table m(j,k)
  20           ganancia1       ganancia2
  21  empresa1  4500           0
  22  empresa2  0              4500         ;
  23  
  24  Table h(i,j) horas de producción por producto
  25  
  26               empresa1    empresa2
  27  dineroe          5000       4000
  28  horae            400        500 ;
  29  
  30  
  31  
  32  Variables
  33           x(j,k)  lo que se debe pedir de cada producto
  34           z      ganancia total de producción          ;
  35  
  36  Positive variable x;
  37  
  38  Equations
  39           ganancia
  40           produccion(i) ;
  41  
  42           ganancia ..        z =e= sum((j,k), m(j,k)*x(j,k));
  43  
  44           produccion(i) .. sum((j,k), h(i,j)*x(j,k)) =l= b(i) ;
  45  model giovanni / all/
  46  
  47  solve giovanni using lp maximizing z
  48  
  49  
  50  
  51  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             09/29/10 16:12:06 Page 2
giovanni
Equation Listing    SOLVE giovanni Using LP From line 51


---- ganancia  =E=

ganancia..  - 4500*x(empresa1,ganancia1) - 4500*x(empresa2,ganancia2) + z =E= 0
      ; (LHS = 0)
    

---- produccion  =L=

produccion(dineroe)..  5000*x(empresa1,ganancia1) + 5000*x(empresa1,ganancia2)
    
      + 4000*x(empresa2,ganancia1) + 4000*x(empresa2,ganancia2) =L= 6000 ;
    
      (LHS = 0)
    
produccion(horae)..  400*x(empresa1,ganancia1) + 400*x(empresa1,ganancia2)
    
      + 500*x(empresa2,ganancia1) + 500*x(empresa2,ganancia2) =L= 600 ;
    
      (LHS = 0)
    
GAMS Rev 233  WIN-VIS 23.3.2 x86/MS Windows             09/29/10 16:12:06 Page 3
giovanni
Column Listing      SOLVE giovanni Using LP From line 51


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

x(empresa1,ganancia1)
                (.LO, .L, .UP, .M = 0, 0, +INF, 0)
    -4500       ganancia
     5000       produccion(dineroe)
      400       produccion(horae)

x(empresa1,ganancia2)
                (.LO, .L, .UP, .M = 0, 0, +INF, 0)
     5000       produccion(dineroe)
      400       produccion(horae)

x(empresa2,ganancia1)
                (.LO, .L, .UP, .M = 0, 0, +INF, 0)
     4000       produccion(dineroe)
      500       produccion(horae)

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             09/29/10 16:12:06 Page 4
giovanni
Model Statistics    SOLVE giovanni Using LP From line 51


MODEL STATISTICS

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


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


EXECUTION TIME       =        0.016 SECONDS      4 Mb  WIN233-233 Nov 17, 2009
GAMS Rev 233  WIN-VIS 23.3.2 x86/MS Windows             09/29/10 16:12:06 Page 5
giovanni
Solution Report     SOLVE giovanni Using LP From line 51


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

     MODEL   giovanni            OBJECTIVE  z
     TYPE    LP                  DIRECTION  MAXIMIZE
     SOLVER  CPLEX               FROM LINE  51

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

 RESOURCE USAGE, LIMIT          0.023      1000.000
 ITERATION COUNT, LIMIT         2    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 :        6000.000000


                       LOWER     LEVEL     UPPER    MARGINAL

---- EQU ganancia        .         .         .        1.000    

---- EQU produccion

           LOWER     LEVEL     UPPER    MARGINAL

dineroe     -INF   6000.000  6000.000     0.500    
horae       -INF    600.000   600.000     5.000    

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

                      LOWER     LEVEL     UPPER    MARGINAL

empresa1.ganancia1      .        0.667     +INF       .        
empresa1.ganancia2      .         .        +INF  -4500.000    
empresa2.ganancia1      .         .        +INF  -4500.000    
empresa2.ganancia2      .        0.667     +INF       .        

                       LOWER     LEVEL     UPPER    MARGINAL

---- VAR z              -INF   6000.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             09/29/10 16:12:06 Page 6
giovanni
E x e c u t i o n


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

           ganancia1   ganancia2

empresa1       0.667
empresa2                   0.667


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

           ganancia1   ganancia2

empresa1               -4500.000
empresa2   -4500.000



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


USER: GAMS Development Corporation, Washington, DC   G871201/0000CA-ANY
      Free Demo,  202-342-0180,  sales@gams.com,  www.gams.com   DC0000


**** FILE SUMMARY

Input      C:\Users\Gio\Desktop\Programacion lineal\Gams\ejemplo.gms
Output     C:\Users\Gio\Documents\gamsdir\projdir\ejemplo.lst

Proyecto

Link Borrador proyecto
http://www.megaupload.com/?d=0UP47N5P

Resumen capitulo 4

PROGRAMACIÓN LINEAL

"Se llama programación lineal al conjunto de técnicas matemáticas que pretenden resolver la situación siguiente: Optimizar (maximizar o minimizar) una función objetivo, función lineal de varias variables, sujeta a: una serie de restricciones, expresadas por inecuaciones lineales."

Muchas personas clasifican el desarrollo de la programación lineal entre los avances científicos más importantes de mediados del siglo XX, su impacto desde 1950 ha sido extraordinario. En la actualidad es una herramienta de uso normal que ha ahorrado miles o millones de pesos a muchas compañías o negocios, incluyendo empresas medianas en los distintos países industrializados del mundo; su aplicación a otros sectores de la sociedad se está ampliando con rapidez. Una proporción muy grande de los cálculos científicos en computadoras está dedicada al uso de la programación lineal.

¿Cuál es la naturaleza de esta notable herramienta y qué tipos de problemas puede manejar. Expresado brevemente, el tipo más común de aplicación abarca el problema general de asignar recursos limitados entre actividades competitivas de la mejor manera posible (es decir, en forma óptima). Con más precisión, este problema incluye elegir el nivel de ciertas actividades que compiten por recursos escasos necesarios para realizarlas. Después, los niveles de actividad elegidos dictan la cantidad de cada recurso que consumirá cada una de ellas. La variedad de situaciones a las que se puede aplicar esta descripción es sin duda muy grande, y va desde la asignación de instalaciones de producción a los productos, hasta la asignación de los recursos nacionales a las necesidades de un país; desde la selección de una cartera de inversiones, hasta la selección de los patrones de envío; desde la planeación agrícola, hasta el diseño de una terapia de radiación, etc. No obstante, el ingrediente común de todas estas situaciones es la necesidad de asignar recursos a las actividades eligiendo los niveles de las mismas.

La programación lineal utiliza un modelo matemático para describir el problema. El adjetivo lineal significa que todas las funciones matemáticas del modelo deber ser funciones lineales. En este caso, las palabra programación no se refiere a programación en computadoras; en esencia es un sinónimo de planeación. Así, la programación lineal trata laplaneación de las actividades para obtener un resultado óptimo, esto es, el resultado que mejor alcance la meta especificada (según el modelo matemático) entre todas las alternativas de solución.

MODELO DE PROGRAMACIÓN LINEAL

Z  =      valor de la medida global de efectividad

x_j =       nivel de la actividad j (para j = 1,2,...,n)

c_j =       incremento en Z que resulta al aumentar una unidad en el nivel de la actividad j

b_i =       cantidad de recurso i disponible para asignar a las actividades (para i = 1,2,...,m)

a_ij =      cantidad del recurso i consumido por cada unidad de la actividad j

FORMA ESTÁNDAR DEL MODELO

Optimizar (maximizar o minimizar) Z = c₁x₁ + c₂x₂ +....+ c_nx_n,

Sujeta a las restricciones:

            a₁₁x₁ + a₁₂x₂ +....+ a_1nx_n < b₁

            a₂₁x₁ + a₂₂x₂ +....+ a_2nx_n < b₂

                                       .

                                       .

                                       .

            a_m1x₁ + a_m2x₂ +....+ a_mnx_n < b_m

X₁  ³ 0,           X₂ ³0,     ...,      Xn ³0.

Método grafico

Los problemas de programación lineal en dos variables tienen interpretaciones geométricas relativamente sencillas; por ejemplo, el sistema de restricciones lineales asociado con un problema de programación lineal bidimensional- si no es inconsistente- define una región plana cuya frontera está formada por segmentos de recta o semirrectas, por lo tanto es posible analizar tales problemas en forma gráfica.

El modelo se puede resolver en forma gráfica si sólo tiene dos variables. Para modelos con tres o más variables, el método gráfico es impráctico o imposible.

Ejemplo “ejercicio 3.4-7”

Método del Simplex

Es un procedimiento repetitivo (iterar) que permite ir mejorando la solución a cada paso. El proceso concluye cuando no es posible seguir mejorando más dicha solución.

El método del simplex fue creado en 1947 por el matemático George Dantzig. Este método se utiliza, sobre todo, para resolver problemas de programación lineal en los que intervienen tres o más variables.

El álgebra matricial y el proceso de eliminación de Gauss-Jordan para resolver un sistema de ecuaciones lineales constituyen la base del método simplex.

Ejemplo “ejercicio 3.2-3”

USO DE LA COMPUTADORA

            EXCEL 2007/SOLVER

Primero que todo hay que disponer del solver en Excel, para ello vamos a inicio - opciones de Excel – complementos - seleccionar solver – ir… - chulear solver- aceptar.

Luego de seguir los pasos de la grafica: Datos – solver

Es importante definir el modelo como un problema de programación lineal.

Podemos concluir que el costo mínimo para la dieta de solo res y papas basándose en una buena nutrición es de 1.27 porciones diarias de res y 2.91 porciones diarias de papas, a un costo de $10.91.

Ejemplo “ejercicio 3.4-7”

3.4-7

3.4-7 carne con papas es el plato favorito de Ralph Edmund. Por eso decidió hacer una dieta continua de solo estos dos alimentos (más algunos líquidos y suplementos de vitaminas) en todas sus comidas. Ralph sabe que no es la dieta más sana y quiere asegurarse de que toma las cantidades adecuadas de los dos alimentos para satisfacer los requerimientos nutricionales. Cuenta con la siguiente información nutricional de costo.

gramos de ingredientes por porción
ingredientes	res	papas	requerimiento diario
carbohidratos	5	15	Mayor o igual 50
proteínas	20	5	Mayor o igual 40
grasa	15	2	Menor o igual 60
costo/porción	$4	$2

Ralph quiere determinar el número de porciones diarias (pueden ser fraccionales) de res y papas que cumplirían con estos requerimientos a un costo mínimo.

a.       Formule un modelo de programación lineal

b.      Use el modelo grafico para resolver el modelo

c.       Utilice una computadora para resolver este modelo por el método simplex.

Solución

a.      

b.

c.

gramos de ingredientes por porción
ingredientes	res	papas	requerimiento diario
carbohidratos	5	15	50
proteínas	20	5	40
grasa	15	2	60
costo/porción	4	2
Solución	1,27272727	2,90909091
Z	10,9090909
x1	1,27272727
x2	2,90909091

3.2-3

3.2-3 Hoy es su día de suerte. Acaba de ganar un premio de $10000. Dedicara$ 4000 a impuestos y diversiones, pero ha decidido invertir los otros $6000. Al oír ésta noticia, dos amigos distintos le ofrecen la oportunidad de participar como socio en dos negocios, cada negocio planteado por cada amigo. En ambos casos, la inversión significa dedicar un poco de tiempo el siguiente verano, al igual que invertir efectivo. Con el primer amigo, al convertirse en socio completo, tendría que invertir $5.000 y 400 horas, y la ganancia estimada (ignorando el valor del tiempo) sería de $4.500. Las cifras correspondientes a la proposición del segundo amigo son $4.000 y 500 horas, con una ganancia estimada de $4.500. Sin embargo, ambos amigos son flexibles y le permitirían entrar en el negocio con cualquier fracción de la sociedad; la participación en las utilidades sería proporcional a esa fracción. Como de todas maneras, ésta persona está buscando un trabajo interesante para el verano (600 horas a lo sumo), ha decidido participar en una ó ambas propuestas, con la combinación que maximice la ganancia total estimada. Formule y resuelva el problema.

	compañía 1	compañía 2
Inversión	5000	4000	6000
Horas	400	600	600
utilidad	4500	4500

Maximizar

Solución:

It	Ec	Vb	Z	X1	X2	X3	X4	LD
	0	Z	1	-4500	-4500	0	0	0
0	1	X3	0	5000	4000	1	0	6000
	2	X4	0	400	500	0	1	600
It	Ec	Vb	Z	X1	X2	X3	X4	LD
	0	Z	1	0	-900	0,9	0	5400
1	1	X1	0	1	0,8	0,0002	0	1,2
	2	X4	0	0	180	-0,08	1	120
It	Ec	Vb	Z	X1	X2	X3	X4	LD
	0	Z	1	0	0	0,5	5	6000
2	1	X1	0	1	0	0,000556	-0,00444	0,66666667
	2	X2	0	0	1	-0,00044	0,005556	0,66666667