2° parte parcial- 2 de octubre...punto 8.3-4

$title  transporte

Sets

         i nado /dorso, pecho, mariposa, libre/

         j nadador /carlos, cristina, david, antonio, jose/;

Parameters

         A(i) tipo de nado

         /       dorso 1

                 pecho 1

                 mariposa 1

                 libre 1

                                  /

         B(j) demanda de nadador

         /       carlos 1

                 cristina 1

                 david 1

                 antonio 1

                 jose 1

                                     /

Table G(i,j) ganancia por unidad distribuida entre i y j

         carlos  cristina david   antonio jose

dorso    37.7    32.9     33.8    37      35.4

pecho    43.3    33.1     42.2    34.7    46.8

mariposa 33.3    28.5     38.9    30.4    33.6

libre    29.2    26.4     24.6    28.5    31.1

                                                          ;

Variables

         x(i,j)  unidades transportadas entre i y j

         GT      ganancia por unidad distribuida          ;

positive variable x;

Equations

         ganancia     ganancia total del transporte

         capacidad(i) capacidad maxima de cada planta (i)

         demanda(j)   demanda maxima de cada cliente (j)  ;

         ganancia ..        GT =e= sum((i,j), G(i,j)*x(i,j));

         capacidad (i) .. sum(j, x(i,j)) =L= A(i);

         demanda (j) .. sum(i, x(i,j)*1) =G= B(j) ;

model transporte / ganancia, capacidad, demanda/

solve transporte  using lp maximizing GT

Display x.l, x.m ;

MAPAS CONCEPTUALES

Ejercicio 8.2-23

Una contratista tiene que acarrear grava a tres construcciones. Puede comprar hasta 18 toneladas en un foso de grava al norte de la cuidad y 14 toneladas en una al sur. Necesita 10, 5 y 10 toneladas en las respectivas contriciones 1,2, y 3. El precio de compra por tonelada en cada foso y los costos de acarreo son los siguientes.

Costo por tonelada acarreada

Foso	1	2	3	Precio por tonelada
Norte	$ 30	$ 60	$ 50	$ 100
Sur	$ 60	$ 30	$ 40	$ 120

La contratista desea determinar cuanto acarrear de cada foso a cada construcción de manera que se minimice el costo total de compra y acarreo de la grava.

a.) formular el modelo de programación lineal. Use el método de la M para construir la tabla simplex inicial lista para aplicar el método simplex (pero no lo resuelva)

b.) ahora formula este como uno de transporte construyendo la tabla de parámetros adecuada. Compare el tamaño de esta tabla (y de la tabla simplex de trasporte correspondiente) use el método simples de transporte, con el tamaño de la tabla simplex inicio a necesaria para aplicar el método simplex.

c.) la contratista ha observado que puede abastecer por completo las construcciones 1 y 2 del foso norte y la construcción 3 del foso sur. Utilice la prueba de optimalidad (pero no realizar iteraciones) del método simplex de transporte para verificar si la solución BF correspondiente es optima

d.) con la regla de la esquina noroeste, use la rutina interactiva del método simples de transporte para resolver el problema formulado en el inicio b.

Solución:

b) tabla de parámetros para método de transporte

foso	1	3	2	4	recursos
norte	130	150	160	0	18
sur	180	150	160	0	14
demanda	10	5	10	7	0

Ahora

Minimizar:   Z= 130x1.1 +160x1.2 + 150x1.3 + 180x2.1 + 150x2.2 + 160x2.3

 S.a

X1.1 +X1.2 + X1.3 <=18

X2.1 + X2.2 + X2.3 <=14

X1.1 + X2.1 =10

X1.2 + X2.2 = 5

X1.3 + X2.3 = 10

c) tabla simplex de transporte

foso	1	3	2	4	recursos
norte	130	150	160	0	18
	(10)	(5)	(-10)	(3)
sur	180	150	160	0	14
	50	-10	(10)	(4)
demanda	10	5	10	7	0

La solución no es optima, ya que

Δ22 = 150-0-160= -10

Δ13= 150-0-160 = -10

Ejercicio 8.3-4

$title  transporte


Sets
         i productor /inglaterra, francia, espana/
         j cultivo /trigo, cebada, avena/;

Parameters

         A(i) capacidad de tierra del productor
         /       inglaterra      70
                 francia         110
                 espana          80
                                 /
         B(j) demanda del mercado
         /       trigo    125
                 cebada   60
                 avena    75
                                 /
Table G(i,j) ganancia por unidad distribuida entre i y j
                 trigo   cebada  avena
inglaterra       162     121.5   82.8
francia          93.6    108     75
espana           158.4   100.8   100.8    ;


Variables
         x(i,j)  unidades transportadas entre i y j
         GT      ganancia por unidad distribuida          ;


positive variable x;
Equations
         ganancia     ganancia total del transporte
         capacidad(i) capacidad maxima de cada planta (i)
         demanda(j)   demanda maxima de cada cliente (j)  ;

         ganancia ..        GT =e= sum((i,j), G(i,j)*x(i,j));
         capacidad (i) .. sum(j, x(i,j)) =L= A(i);
         demanda (j) .. sum(i, x(i,j)*1) =G= B(j) ;

model transporte / ganancia, capacidad, demanda/
solve transporte  using lp minimizing GT
Display x.l, x.m ;

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