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

...