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

...