Eejercicios de programación lineal con el método simplex y el método gráfico.

INTRODUCCION

En este trabajo colaborativo se desarrollan ejercicios de programación lineal con el método simplex y el método gráfico.

El método Simplex es un método analítico de solución de problemas de programación lineal capaz de resolver modelos más complejos que los resueltos mediante el método gráfico sin restricción en el número de variables, un procedimiento iterativo que permite mejorar la solución de la función objetivo en cada paso, este proceso concluye cuando no es posible continuar mejorando dicho valor, es decir, se ha alcanzado la solución óptima (el mayor o menor valor posible, según el caso, para el que se satisfacen todas las restricciones).

El método Simplex se basa en la propiedad “si la función objetivo Z no toma su valor máximo en el vértice A, entonces existe una arista que parte de A y a lo largo de la cual el valor de Z aumenta”.

El método Simplex únicamente trabaja con restricciones del problema cuyas inecuaciones sean del tipo "≤" (menor o igual) y sus coeficientes independientes sean mayores o iguales a 0. Por tanto habrá que estandarizar las restricciones para que cumplan estos requisitos antes de iniciar el algoritmo del Simplex. En caso de que después de éste proceso aparezcan restricciones del tipo "≥" (mayor o igual) o "=" (igualdad), o no se puedan cambiar, será necesario emplear otros métodos de resolución.

El método gráfico para resolver este tipo de sistemas consiste, por tanto, en representar en unos ejes cartesianos, o sistema de coordenadas, ambas rectas y comprobar si se cortan y, si es así, dónde. Esta última afirmación contiene la filosofía del proceso de discusión de un sistema por el método gráfico. Hay que tener en cuenta, que, en el plano, dos rectas sólo pueden tener tres posiciones relativas (entre sí): se cortan en un punto, son paralelas o son coincidentes (la misma recta). Si las dos rectas se cortan en un punto, las coordenadas de éste son el par (x, y) que conforman la única solución del sistema, ya que son los únicos valores de ambas incógnitas que satisfacen las dos ecuaciones del sistema, por lo tanto, el mismo es compatible determinado. Si las dos rectas son paralelas, no tienen ningún punto en común, por lo que no hay ningún par de números que representen a un punto que esté en ambas rectas, es decir, que satisfaga las dos ecuaciones del sistema a la vez, por lo que éste será incompatible, o sea sin solución. Por último, si ambas rectas son coincidentes, hay infinitos puntos que pertenecen a ambas, lo cual nos indica que hay infinitas soluciones del sistema (todos los puntos de las rectas), luego éste será compatible indeterminado.

El método algebraico y analítico Son métodos que se usan para resolver sistemas de ecuaciones con dos o más variables, de una manera muy sencilla. Como su nombre lo indica, el método usa como su principal herramienta, el álgebra, que ligada a un proceso de lógica matemática dio como resultado el método algebraico.

Usando métodos algebraicos como los métodos de resolución de problemas (sustitución, igualación y reducción) y sistemas de ecuaciones lineales 2*2 podemos solucionar los problemas.

ACTIVIDADES

FASE 1

GLORIA CAMARGO

Se desea ampliar las opciones de alimentación que permita tener una vida sana. Por lo tanto se crearon 4 dietas diferentes, desayuno, almuerzo, cena, onces. El desayuno requiere 2 frutas de 8 carbohidratos y 2 vasos de agua de 4 vitaminas.

El almuerzo requiere 1 verdura de 8 carbohidratos y 2 alimentos que contengan 4 vitaminas.

Cada cena requiere 1 verdura de 8 carbohidratos, 1 alimento que contengan 4 vitaminas, y 2 vasos de agua de 2 calcios.

Las onces deben ser suaves, entonces requieren 2 frutas de 8 carbohidratos, 2 vasos de agua de 2 calcios, opcional 4 alimentos de proteínas.

Cada desayuno cuesta $ 10000 y se requiere disminuir el valor a $ 5000

Cada almuerzo cuesta $ 15000 y se requiere disminuir el valor a $ 10000

Cada cena cuesta $ 12000 y se requiere disminuir el valor a $ 7000

Las onces cuentas $ 8000 y se requiere disminuir el valor a $ 3000

El objetivo es minimizar el costo.

8 carbohidratos 4 vitaminas 2 calcio proteínas

Desayuno 2 2 0 0

Almuerzo 1 2 0 0

Cena 1 1 2 0

Onces 2 0 2 4

Total 24 20 20 16

Definir

Las variables:

X1 = Cantidad de días a hacer dieta de desayuno

X2 = Cantidad de días a hacer dieta de Almuerzo

X3 = Cantidad de días a hacer dieta de Cena

X4 = Cantidad de días a hacer dieta de onces

Las restricciones:

2X1 + 1X2 + 1X3 + 2X4 <= 24

2X1 + 2X2 + 1X3 <= 20

2X3 + 2X4 <= 20

4X4 <= 16

La función Objetivo:

ZMIN = 5000X1 - 5000X2 - 5000X3 - 5000X4

CONVERTIR LAS INECUACIONES EN ECUACIONES

2X1 + 1X2 + 1X3 + 2X4 - 1S1 + 0S2 + 0S3 + 0S4 = 24

2X1 + 2X2 + 1X3 + 0X4 - 0S1 + 1S2 + 0S3 + 0S4 = 20

0X1 + 0X2 + 2X3 + 2X4 - 0S1 + 0S2 + 1S3 + 0S4 = 20

0X1 + 0X2 + 0X3 + 4X4 - 0S1 + 0S2 + 0S3 + 1S4 = 16

DEFINIR LA SOLUCIÓN

1S1 = 24

1S2 = 20

1S3 = 20

1S4 = 16

DEFINIR LA TABLA SIMPLEX

Cj 5000 5000 5000 5000 0 0 0 0

Cb Variable solución solución X1 X2 X3 X4 S1 S2 S3 S4

0 S1 24 2 1 1 2 1 0 0 0

0 S2 20 2 2 1 0 0 1 0 0

0 S3 20 0 0 2 2 0 0 1 0

0 S4 16 0 0 0 4 0 0 0 1

Zj 0 0 0 0 0 0 0 0 0

Cj-Zj 5000 5000 5000 5000 0 0 0 0

Cj 5000 5000 5000 5000 0 0 0 0

Cb Variable solución solución X1 X2 X3 X4 S1 S2 S3 S4 b/a

0 S1 24 2 1 1 2 1 0 0 0 24/2=12

0 S2 20 2 2 1 0 0 1 0 0 20/0=NA

0 S3 20 0 0 2 2 0 0 1 0 20/2=10

0 S4 16 0 0 0 4 0 0 0 1 16/4=4

Zj 0 0 0 0 0 0 0 0 0

Cj-Zj 5000 5000 5000 5000 0 0 0 0

Cj 5000 5000 5000 5000 0 0 0 0

Cb Variable solución solución X1 X2 X3 X4 S1 S2 S3 S4

0 S1

0 S2

0 S3

0 X4 4 0 0 0 1 0 0 0 0.25

Zj

Cj-Zj 5000 5000 5000 5000 0 0 0 0

S1 24 2 1 1 2 1 0 0 0

X4 4 0 0 0 1 0 0 0 0.25

X4 -8 0 0 0 -2 0 0 0 -0.5

Cj 5000 5000 5000 5000 0 0 0 0

Cb Variable solución solución X1 X2 X3 X4 S1 S2 S3 S4

0 S1 24 2 1 1 2 1 0 0 -0.5

0 S2 20 2 2 1 0 0 1 0 0

0 S3 20 0 0 2 2 0 0 1 -0.5

0 S4 16 0 0 0 4 0 0 0 0.25

Zj 20000 0 0 0 5000 0 0 0 1000

Cj-Zj 5000 5000 5000 0 0 0 0 -1000

Cj 5000 5000 5000 5000 0 0 0 0

Cb Variable solución solución X1 X2 X3 X4 S1 S2 S3 S4

0 S1 24 2 1 1 2 1 0 0 -0.5

0 S2 20 2 2 1 0 0 1 0 0

0 S3 20 0 0 2 2 0 0 1 -0.5

0 S4 16 0 0 0 4 0 0 0 0.25

Zj 15000 0 0 12000 4000 0 0 0 5000

Cj-Zj 5000 5000 0 0 0 -5000

Resultado: La dieta completa por dia tiene un costo 30000.

2. LILIANA RODRIGUEZ

Basado en los problemas propios y propuestos en el trabajo colaborativo 1, el grupo debe desarrollarlos por el método simplex y hacer El planteamiento como DUAL a cada uno de los problemas propuestos. Estos problemas deben ser desarrollados sin la ayuda de ningún programa, debe ser con cálculos manuales.

Maximizar

Z= 400.000*X1 + 320.000*X2

Restricciones

X1+X2 ≤800

2X1+3X2≤1200

3X1+4X2≤5000

X1, X2≥0

TABLA SIMPLEX

Columna Pivote

Valor pivote

El valor pivote se debe convertir a uno (1), en este ejercicio el 4

Se debe dejar en cero (0) los valores que están encima y debajo del valor pivote

RUDID BARRERA

En el molino de Arroz Casanare se producen dos variedades de arroz: EL Paddy Verde y el Arroz Blanco los cuales se venden a un precio de 912.800 por tonelada y 1.916.889 por tonelada respectivamente. El histórico de producción muestra que la utilidad por cada variedad es del 45% para el Paddy verde y del 56% sobre el precio de venta por tonelada.

La producción máxima en Casanare es de 396.730 toneladas al año

De acuerdo al departamento de producción se estima que la planta está diseñada para producir el doble de arroz Paddy que de arroz blanco.

Sea x1 = la cantidad en toneladas al año a producir de Arroz Paddy Verde

X2= toneladas a producir al año de Arroz Blanco.

Maximizar z = 410760 X1 + 1073457.84 X2

X1+X2 <=396730

X1 -2X2 = 0

X1, X2 >=0

Forma estándar:

Maximizar z = 410760 X1 + 1073457.84 X2

X1+X2 + S1 = 396730

X1 -2X2 + R1 = 0

X1, X2 >=0

SOLUCIÓN POR MÉTODO SIMPLEX (MÉTODO DE LAS DOS FASES)

En la Fase I SIEMPRE se minimiza la función objetivo.

Fase I

Base x1 x2 s1 r1 Solución

z(min) 1 -2 0 0 0

s1 1 1 1 0 396730

r1 1 -2 0 1 0

Base x1 x2 s1 r1 Solución

z(min) 0 0 0 -1 0

s1 0 3 1 -1 396730

x1 1 -2 0 1 0

Fase II

Base x1 x2 s1 r1 Solución

z(max) 0 -1894977.84 0

...