Programación Lineal Método Simplex

PRESENTADO POR:

ADRIAN ORTEGA DE LA CRUZ

YELIANY MARTINEZ CERVANTES

PRESENTADO AL PROFESOR:

JOSE DE LA HOZ

UNIVERSIDAD DEL ATLANTICO

FACULTAD DE QUIMICA Y FARMACIA

MATERIA: BIOESTADISTICA

ATLANTICO/BARRANQUILLA

31/05/2013

PROBLEMA: UN PROCESO INDUSTRIAL ESTA GENERANDO 1.4% DE MATERIAL DEFECTUSO, EN ESTAS CONDICIONES UN LOTE DE 250 UNIDADES. SE DESPACHA A UN CLIENTE EL CUAL DECIDE ACERCARLO SI AL TOMAR UNA MUESTRA REPRESENTATIVA DE 25 Und. ENCUENTRA COMO MAXIMO UNA DEFECTUOSA.

a) Probabilidad de aceptar un lote.

b) Probabilidad de rechazar un lote.

c) Probabilidad de que al examinar la muestra no se encuentre ningún artículo defectuoso.

d) Probabilidad de que al examinar la muestra se encuentre exactamente un artículo defectuoso.

e) Probabilidad de que al examinar la muestra se encuentre entre 1 y 2 articulo defectuoso.

f) Probabilidad de que al examinar la muestra se encuentre mas de uno y menos de dos articulo defectuoso.

g) Probabilidad de que al examinar la muestra se encuentre mas de uno y menos de 3 artículos defectuoso.

h) Probabilidad de que al examinar la muestra se encuentre más de un artículo defectuoso.

i) Si es aplicable resuelva el ejercicio utilizando la distribución binomial.

j) Si es aplicable resuelva el ejercicio utilizando la ecuación Poisson.

k) Construya un cuadro comparativo con los resultados arrojados.

Parte 6 Programación Lineal Método Simplex

El método símplex es un algoritmo. De hecho, cualquier procedimiento iterativo de solución es un algoritmo. Entonces, un algoritmo es simplemente un proceso en el que se repite (se itera) un procedimiento sistemático una y otra vez hasta obtener el resultado deseado. Cada vez que se lleva a cabo el procedimiento sistemático se realiza una iteración. En consecuencia, un algoritmo sustituye un problema difícil por una serie de problemas fáciles.

Además de las iteraciones, los algoritmos incluyen un procedimiento para iniciar y un criterio para determinar cuándo detenerse, como se resume enseguida:

Paso inicial Preparación para iniciar iteraciones

Paso iterativo Realización de iteraciones

Regla de detención ¿Es óptima la solución actual?

Si no Si sí

Fin

El método símplex es un procedimiento algebraico en el que cada iteración contiene la solución de un sistema de ecuaciones para obtener una nueva solución a la que se le aplica la prueba de optimalidad. No obstante, también tiene una interpretación geométrica muy útil. Para ilustrar los conceptos geométricos generales se empleará la solución gráfica del siguiente problema:

Max Z = 3x1 + 5x2

s.a.

x1  4

2x2  12

3x1 + 2x2  18

x1  0 x2  0

Solución por el método gráfico:

En la figura anterior pueden observarse los puntos de intersección que son las soluciones en los vértices del problema. Los cinco puntos que se encuentran en los vértices de la región factible,  (0,0), (0,6), (2,6), (4,3), (4,0) son las soluciones factibles en los vértices. Algunas de estas soluciones factibles en un vértice son adyacentes, en el sentido de que están conectadas por una sola orilla (segmento de línea) de la frontera de la región factible; esto es, tanto (0,6) como (4,3) son adyacentes a (2,6). Las tres propiedades clave de las soluciones factibles en los vértices y que forman el fundamento del método símplex se resumen como sigue:

Propiedades de las soluciones factibles en un vértice:

1a. Si existe exactamente una solución óptima, entonces debe ser una solución factible en un vértice.

1b. Si existen soluciones óptimas múltiples, entonces al menos dos de ellas deben ser soluciones factibles en vértices adyacentes.

2. Existe sólo un número finito de soluciones factibles en los vértices adyacentes.

3. Si una solución en un vértice es igual o menor (según el valor de Z) que todas las soluciones factibles en los vértices adyacentes a ella, entonces es igual o mejor que todas las demás soluciones en los vértices; es decir, es óptima.

La propiedad 1 significa que la búsqueda de la solución óptima se puede reducir a la consideración de sólo las soluciones factibles en los vértices, de manera que sólo existe un número finito de soluciones que es necesario tomar en cuenta (propiedad 2). La propiedad 3 proporciona una prueba de optimalidad muy conveniente.

El método símplex explota estas tres propiedades al examinar nada más unas cuantas soluciones factibles en vértices prometedores y al detenerse en cuanto una de ellas pasa la prueba de optimalidad. En particular, se traslada repetidamente (en forma iterativa) de una solución factible en un vértice a otra, adyacente y mejor. Esto se puede realizar en forma muy eficiente hasta que la solución actual no tiene soluciones factibles en vértices adyacentes que sean mejores. Este procedimiento se resume como sigue:

Bosquejo del método símplex:

1. Paso inicial: inicio en una solución factible en un vértice.

2. Paso iterativo: traslado a una mejor solución factible en un vértice adyacente. (Repítase este paso las veces que sea necesario).

3. Prueba de optimalidad: la solución factible en un vértice es óptima cuando ninguna de las soluciones en vértices adyacentes a ella sean mejores.

Este bosquejo muestra la esencia del método símplex,. En el caso del ejemplo, al utilizar estas reglas de selección el método símplex procede como sigue:

1. Paso inicial: comienza en (0,0).

2a. Iteración 1: se mueve de (0,0) a (0,6)

2b. Iteración 2: se mueve de (0,6) a (2,6).

3. Prueba de optimalidad: ni (0,6) ni (4,3) son mejores que (2,6), entonces se detiene, (2,6) es óptima.

Preparación para el método símplex.

En el procedimiento algebraico es mucho más conveniente manejar ecuaciones que desigualdades. Así, el primer paso para preparar el método símplex es convertir las restricciones funcionales de desigualdad en restricciones equivalentes. (Las restricciones de no negatividad se pueden dejar como desigualdades porque el algoritmo las usa sólo indirectamente). Esta conversión se hace mediante la introducción de variables de holgura. Considérese la primera restricción funcional del ejemplo:

x1  4

La variable de holgura para esta restricción es x3, que no es otra cosa que la holgura entre los dos lados de la desigualdad. Entonces:

x1 + x3 = 4

La restricción original x1  4 se cumple siempre que x3  0. Por tanto, x1  4 es totalmente equivalente al conjunto de restricciones

x1 + x3 = 4 y

x3  0,

de manera que se usará este conjunto por resultar más conveniente.

Al introducir variables de holgura en las otras restricciones en forma parecida, el modelo de programación lineal original para este ejemplo se puede sustituir por el modelo equivalente:

Maximizar Z = 3x1 + 5x2,

sujeta a

x1 + x3 = 4

2x2 + x4 = 12

3x1 + 2x2 + x5 = 18

xj  0 para j = 1, 2, …, 5

Aun cuando este problema es idéntico al anterior, esta forma es mucho más conveniente para la manipulación algebraica y la identificación de las soluciones factibles en los vértices. Ésta se llama la forma de igualdades del problema, para diferenciarla de la forma de desigualdades original y poder introducir la siguiente definición:

Una solución aumentada es una solución para un problema que originalmente se encontraba en forma de desigualdades y que se ha aumentado con los valores correspondientes de las variables de holgura para cambiar el problema a la forma de igualdades.

Por ejemplo, al aumentar la solución (3,2) en el ejemplo, se obtiene la solución aumentada (3,2,1,8,5), puesto que los valores correspondientes de las variables de holgura son x3 = 1, x4 = 8, x5 = 5.

Una solución básica es una solución en un vértice aumentada.

Para ilustrar esto, considérese la solución no factible en el vértice (4,6) del ejemplo. Al aumentar con los valores obtenidos para las variables de holgura x3 = 0, x4 = 0 y x5 = –6, se llega a la solución básica correspondiente (4,6,0,0,–6). Se permite que las soluciones básicas sean factibles o no factibles, lo que lleva a la siguiente definición:

Una solución básica factible es una solución factible en un vértice aumentada.

Así, la solución factible en el vértice (0,6) del ejemplo es equivalente a la solución básica factible (0,6,4,0,6) para la forma de igualdades del problema.

Como los términos solución básica y solución básica factible constituyen partes muy importantes del vocabulario normal de programación lineal, es necesario aclarar sus propiedades algebraicas.

...