INV DE OPERACIONES

UNIDAD 1

EL MÉTODO SIMPLEX

2.1 SOLUCIÓN GRÁFICA DE UN PROBLEMA LINEAL.

Este método es muy sencillo de aplicar y es de gran ayuda para ver gráficamente el procedimiento que se sigue para llegar a la solución óptima del problema en el método simplex. Obviamente, éste método sólo se puede aplicar a problemas que tienen dos o tres variables de decisión, aquí nos vamos a concretar a resolver problemas de dos variables. Los pasos a seguir para aplicar el método gráfico son:

1. En una gráfica bidimensional poner las restricciones de no negatividad usando las variables de decisión X1 y X2 como los ejes de coordenadas. Las restricciones de no negatividad (X1 0, X2 0) nos limitan a utilizar sólo la parte positiva de los ejes (cuadrante 1).

2. Enseguida se grafica cada una de las restricciones, tomando en cuenta el tipo de restricción de que se trate (, =, ).

3. Una vez que se grafican las restricciones, al conjunto de puntos que satisfagan todas, se denomina REGION FACTIBLE. En uno de sus puntos extremos está la solución óptima del problema.

4. Enseguida se grafica la función objetivo, lo cual se hace igualándola a un valor arbitrario. La recta que representa la función objetivo se desplaza paralelamente en dirección requerida (dependiendo de si un problema es de maximización o de minimización) hasta encontrar el valor (solución única) o los valores (solución múltiple) de las variables de decisión X1 y X2 que hagan que la función objetivo sea óptima.

EJEMPLO 2.1-1 Hallar la solución gráfica del siguiente problema:

Maximizar X0 =3X1 +5X2

Sujeta a: X1  4

2X2  12

3X1 +2X2  18

X1, X2 0

Para trazar las restricciones, se despejan las restricciones para obtener la intersección con los ejes de coordenadas.

1a. Restricción 2a. Restricción 3a. Restricción

X1  4 2X2  12 3X1 +2X2  18

X1 = 4 X2 = 6 si X1=0 entonces X2=9

si X2=0 entonces X1=6

Para la función objetivo, ésta se iguala a un valor arbitrario, como por ejemplo el producto de sus coeficientes.

3X1 +5X2 =15

si X1=0 entonces X2=3

si X2=0 entonces X1=5

Se dibuja la gráfica, obteniendo los puntos extremos y sus valores.

FIGURA 2.1-A

Obtenemos los valores de cada punto sustituyendo sus coordenadas en la función objetivo. Desplazando la recta de la función objetivo dentro del área de soluciones, se obtiene que el punto óptimo es B (punto máximo).

O (X1=0, X2=0) —————— X0 = 0

A (X1=0, X2=6) —————— X0 =30

B (X1=2, X2=6) —————— X0 =36

C (X1=4, X2=3) —————— X0 =27

D (X1=4, X2=0) —————— X0 =12

2.2 SOLUCIÓN GRÁFICA DE UN PROBLEMA LINEAL: PUNTOS EXTREMOS Y OPTIMALIDAD, TIPOS DE SOLUCIÓN.

2.2.1 PUNTOS EXTREMOS Y OPTIMALIDAD. En programación lineal, a las esquinas de una región factible de soluciones se les llama puntos extremos. Si observamos la figura 2.1-A, veremos que los puntos extremos o vértices son los puntos 0, A, B, C y D. En un problema de programación lineal, si existe una solución óptima, ésta siempre se encuentra en un vértice, a excepción de los casos donde hay solución múltiple, que veremos más adelante. Existen tres propiedades para los vértices de los problemas que cuentan con soluciones factibles y una región factible acotada, éstas son:

PROPIEDAD 1:

a). Si el problema tiene exactamente una solución óptima, entonces ésta debe ser una solución factible en un vértice.

b). Si el problema tiene soluciones múltiples, entonces al menos dos deben ser soluciones factibles en vértices adyacentes.

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

PROPIEDAD 3: Si una solución factible en un vértice no tiene soluciones factibles en vértices adyacentes que sean mejores (en cuanto al valor de la función objetivo), entonces no existen soluciones factibles mejores, por lo que ésta es la solución óptima.

2.2.2 TIPOS DE SOLUCIÓN.

Los casos especiales de solución que se pueden presentar al aplicar el método simplex son: degeneración, alternativas óptimas, soluciones no acotadas y soluciones no factibles.

2.2.2.1 DEGENERACIÓN. Esta condición revela que el modelo tiene cuando menos una restricción redundante. Lo cual se refleja en el valor de una o más de las variables básicas, las cuales tendrán valor de cero en la solución óptima. Esto se ilustra en el siguiente problema:

EJEMPLO 2.2.2-1 Hallar la solución gráfica del siguiente problema:

Maximizar X0 =3X1 +9X2

Sujeta a: X1 +2X2  4

X1 +4X2  8

X1, X2 0

Si se resuelve el problema mediante el método gráfico, tenemos la siguiente figura con la solución optima, la cual es degenerada:

FIGURA 2.1-B

Observando la figura 2.1-B, vemos que la segunda restricción (X1 +4X2  8) es redundante. Esto es debido a que, siendo el punto A el óptimo, pasan por él tres rectas (restricciones), una de las cuales sobra, ya que para determinar un punto en un espacio bidimensional basta que se crucen dos rectas. Esta es una solución óptima degenerada.

2.2.2.2 ALTERNATIVAS ÓPTIMAS. Cuando la función objetivo es paralela a una restricción, la función objetivo tomará el mismo valor óptimo en más de un punto de solución. Por esto, se generan alternativas óptimas a la solución.

EJEMPLO 2.2.2-2 Hallar la solución gráfica del siguiente problema:

Maximizar Z =2X1 +4X2

Sujeta a: X1 +2X2  5

X1 + X2  4

X1, X2 0

Si se resuelve el problema mediante el método gráfico, tenemos la siguiente figura con la solución optima, la cual tiene alternativas óptimas entre los puntos A y B de la región factible:

2.2.2.3 SOLUCIÓN NO FACTIBLE. Si las restricciones no se pueden satisfacer en forma simultánea, se dice que el modelo no tiene solución factible. Esta situación nunca ocurre cuando todas las restricciones del tipo  con coeficientes no negativos. Un espacio no factible indica la posibilidad de una mala formulación del modelo de programación lineal.

EJEMPLO 2.2.2-3 Hallar la solución gráfica del siguiente problema:

Maximizar Z =3X1 +2X2

Sujeta a: 2X1 + X2  2

3X1 +4X2  12

X1, X2 0

En el diagrama de la solución por el método gráfico, se puede ver que las restricciones no se satisfacen de manera simultánea.

2.2.2.4 SOLUCIÓN NO ACOTADA. En algunos modelos de programación lineal los valores de las variables se pueden aumentar en forma indefinida sin violar ninguna de las restricciones, lo que significa que el espacio de soluciones es no acotado. Como resultado, el valor puede crecer (en caso de maximización) o decrecer (en caso de minimización) en forma indefinida. Una solución no acotada, indica que el modelo está mal formulado.

EJEMPLO 2.2.2-4 Hallar la solución gráfica del siguiente problema:

Maximizar Z =2X1 +X2

Sujeta a: X1 - X2  10

2X1  40

X1, X2 0

En el diagrama de la solución por el método gráfico, se puede ver que las dos restricciones si se satisfacen de manera simultánea, sin embargo, la región factible se extiende indefinidamente hacia arriba.

2.3 TEORÍA DEL MÉTODO SIMPLEX.

Los métodos algebraicos para solucionar un problema de Programación Lineal suelen ser muy laboriosos, debido a que trabaja con todos los datos de las ecuaciones, para mejorar éste aspecto se creó el método simplex cuya gran virtud es su sencillez, método muy práctico, ya que solo trabaja con los coeficientes de la función objetivo y de las restricciones.

El método simplex un algoritmo que se emplea para solucionar problemas de Programación Lineal. Consiste en transportar el problema a una tabla en la cual hay una columna para cada variable y un renglón para cada restricción.

Para poder desarrollar el método simplex se sugiere los siguientes pasos:

1. El problema lineal se expresa en su forma estándar.

2. Se elige una solución básica de inicio:

a. Si todas las restricciones son del tipo , las variables de holgura se emplean como solución de inicio.

b. Si se tienen restricciones del tipo  o = se emplea la técnica de doble fase o la de penalización (método de la gran M).

3. Generar nuevas soluciones básicas factibles empleando los criterios de optimalidad y de factibilidad tantas veces como sea necesario hasta llegar a una solución óptima.

A continuación, se muestran las reglas de decisión para determinar la variable que entra, la que sale, y cómo determinar que estamos en el óptimo. Todas éstas reglas de decisión fueron deducidas del método

...