sesión 04 2015 ii

INVESTIGACIÓN DE OPERACIONES

Mg. Paul Linares OrtegaIngeniero Industrial

Semana 04

MÉTODO SIMPLEX SOLUCIÓN DE LOS PROBLEMAS DE PROGRAMACIÓN LINEAL

MÉTODOS DE PROGRAMACION LINEAL

Existen tres métodos para resolver problemas de programación lineal:

Método geométrico o gráfico:Tiene un valor práctico limitado pero es de gran utilidad para visualizar los conceptos de la programación lineal.

Método algebraico:Muchos califican al método algebraico, como uno de los métodos más importantes en el campo de la programación lineal

Método simplex: Es utilizado para resolver cualquier problema de programación lineal.

Para resolver en la práctica problemas de más de dos dimensiones, se emplea el llamado Método Simplex, basada en el álgebra matricial y en el empleo de espacios de “n” dimensiones.

El Método Simplex es un procedimiento o conjunto de restricciones con el cual se examinan los puntos en las esquinas de una manera metódica hasta conseguir la mejor solución: la mayor utilidad ó el menor costo.

En teoría, el método Simplex puede resolver un problema que consiste en cualquier número de variable y restricciones; aunque en el caso de problemas que tienen más de tres variables o restricciones, es mejor que los cálculos sean hechos en el computador a través de un software (WINQSB, TORA, SOLVER, LINDO, etc.).

Sin embargo, para poder comprender totalmente la programación lineal, construir las ecuaciones para desarrollar el programa y poder integrar sus resultados, es necesario seguir manualmente el Método Simplex.

Los pasos que comprende el Método simplex son:

• Formular el problema, planteado la función objetiva, las restricciones y las condiciones de no negatividad.

• Introducir variables de holgura (S) ó variables artificiales (A) en las restricciones:

- Si una restricción tiene signo ( ≤ ) “menor o igual que”, genera la inclusión de una variable de holgura (S) al lado izquierdo, para convertirla en una igualdad. - Si una restricción tiene signo ( = ) “igual que”, genera la inclusión de una variable artificial (A) al lado izquierdo.

- Si una restricción tiene signo ( ≥ ) “mayor o igual que”, se debe restar una variable de holgura (S) y sumar una variable artificial (A) al lado izquierdo de la desigualdad, para convertirla en una igualdad.

CjVariableSolución

Cantidad

X1 X2 S1 S2

S1

S2

Zj

Zj - Cj

Variables Reales Variables de Holgura

En esta fila se consigna la contribución total, es decir la suma de los productos entre término.

Diferencia entre la fila Zj y la fila Cj, su significado es un “shadow price” (precio sombra) , es decir, la utilidad que se deja de recibir por cada unidad de la variable correspondiente que no forme parte de la solución.

• Elaborar la tabla inicial simplex donde todos los coeficientes numéricos de la función objetivo y de las restricciones son ubicados en la tabla.

En esta fila se hace referencia al coeficiente que tiene cada una de las variables de la fila “solución”en la función objetivo.

En esta columna se consigna la solución básica, y a partir de esta en cada iteración se van incluyendo las variables que formarán parte dela solución final.

• Se ingresan los coeficientes y las cantidades de las función objetivo y de las restricciones a la tabla inicial simplex y se calcula el costo de introducir la variable (Zj) y la contribución neta de la variable (Zj-Cj).

• Partiendo del calculo de (Zj-Cj) se escoge entre las restricciones un punto de apoyo (Pivote) para lo cual se determina una columna pivote, eligiendo entre la columna de variables a aquella que tenga el menor valor si se trata de maximización y el mayor valor si se trata de minimización.

• Posteriormente se determina una fila pivote, dividiendo la columna cantidad entre la columna pivote, tomando como referencia el menor valor positivo; la intercepción de ambas es el punto pivote.

• El punto Pivote por su ubicación indica que variable de holgura sale y que variable real entra. El Pivote, debe ser 1; si no es así tendrá que operarse ya sea multiplicando o dividiendo con la finalidad de obtener 1. Una vez que el punto Pivote es la unidad, se convierte en ceros todos los elementos de su columna.

• El método simplex es un método iterativo (repetitivo), han de repetirse los pasos hasta encontrar la solución óptima, es decir cuando se cumpla la condición:

Zj-Cj sea ceros o positivos para la maximización Zj-Cj sea ceros o negativos para la minimización.

Caso Aplicativo

1.- Para el siguiente caso: Zmax = 40X1 + 60X2 + 50X3

s.a. 10X1 + 4X2 + 2X3 ≤ 950 2X1 + 2X2 ≤ 410

X1 + 2X3 ≤ 610

X1, X2, X3 ≥ 0

Encontrar la solución óptima.

Función Objetivo:

Zmax= 40X1 + 60X2 + 50X3

Restricciones:

10X1 + 4X2 + 2X3 = 950 2X1 + 2X2 + 0X3 = 410 X1 + 0X2 + 2X3 = 610

Condición de no negatividad:

X1, X2, X3, ≥ 0

+ 0S1 + 0S2 + 0S3

+ S1 + S2

S1, S2, S3

+ S3

Cj Variable solución

40 60 50 0 0 0CantidadX1 X2 X3 S1 S2 S3

0 S1 10 4 2 1 0 0 9500 S2 2 2 0 0 1 0 4100 S3 1 0 2 0 0 1 610

Zj Zj - Cj

Tabla inicial simplex

X1=0(10)+0(2)+0(1)=0X2=0(4)+0(2)+0(0) =0X3=0(2)+0(0)+0(2) =0S1=0(1)+0(0)+0(0)=0S2=0(0)+0(1)+0(0)=0S3=0(0)+0(0)+0(1)=0Utilidad= 0(950)+0(410)+0(610)=0

Calculo Zj: Calculo Zj-Cj: X1=0-40=-40X2=0-60=-60X3=0-50=-50S1=0-0=0 S2=0-0=0S3=0-0=0

0 0 0 0 0 0 0 -40 -60 -50 0 0 0

Cj Variable Solución

40 60 50 0 0 0CantidadX1 X2 X3 S1 S2 S3

0 S1 10 4 2 1 0 0 9500 S2 2 2 0 0 1 0 4100 S3 1 0 2 0 0 1 610

Zj Zj - Cj

0 0 0 0 0 0 0

- 40 -60 -50 0 0 0

1.- Columna PIVOTE Menor valor

237.5

205

Error

3.- PIVOTEEl pivote debe ser siempre la unidad

El PIVOTE indica la variable que sale y la variable que ingresa.

2.- Fila PIVOTEMenor valor positivo

Cj VariableSolución

40 60 50 0 0 0CantidadX1 X2 X3 S1 S2 S3

Zj

Zj - Cj

60 60 0 0 30 0 12300 20 0 -50 0 30 0

60 X2 1 1 0 0 1/2 0 205 0 S1 6 0 2 1 -2 0 130

0 S3 1 0 2 0 0 1 610

Menor valor

65

Error

305

Menor valor positivo

PIVOTE

¿Son todos los Zj-Cj ceros o positivos? Una vez que el punto Pivote es la unidad, se convierte en ceros todos los elementos de su columna.

No se cumple la condición, se debe repetir el proceso.

Cj VariableSolución

40 60 50 0 0 0CantidadX1 X2 X3 S1 S2 S3

Zj

Zj - Cj

60 X2 1 1 0 0 1/2 0 205

50 X3 3 0 1 1/2 -1 0 65

0 S3 - 5 0 0 -1 2 1 480

Menor valor

-65

410

240

210 60 50 25 -20 0 15550 170 0 0 25 -20 0

Menor valor positivoPIVOTE

El PIVOTE debe ser la unidad y todos los elementos de su columna ceros

¿Son todos los Zj-Cj ceros o positivos?

Una vez que el punto Pivote es la unidad, se convierte en ceros todos los elementos de su columna.

No se cumple la condición, se debe repetir el proceso.

Cj VariableSolución

40 60 50 0 0 0CantidadX1 X2 X3 S1 S2 S3

Zj

Zj - Cj

0 S2 -5/2 0 0 -1/2 1 1/2 240 60 X2 9/4 1 0 1/4 0 -1/4 85

50 X3 1/2 0 1 0 0 1/2 305

160 60 50 15 0 10 20350 120 0 0 15 0 10

X1 = 0 X2 = 85 X3= 305Zmax = 20350

¿Son todos los Zj-Cj ceros o positivos?

Una vez que el punto Pivote es la unidad, se convierte en ceros todos los elementos de su columna.

Si, se cumple la condición, se ha llegado a la solución óptima.

2. Para el siguiente problema:

Zmax = 100X1 + 200X2 + 50X3

s.a. 5X1 + 5X2 + 10X3 ≤ 1000 10X1 + 8X2 + 5X3 ≤ 2000

10X1 + 5X2 ≤ 500

X1, X2, X3 ≥ 0

Encontrar la solución óptima.

X1= 0X2= 100X3= 50Zmax = 22,500

Investigar sobre los dos métodos de solución del Algoritmo Simplex, cuando se tiene en un problema de programación lineal restricciones con ≥ y/o =:

- Método de la Gran MEl método de la Gran M, penaliza la inclusión de las variables artificiales en la función objetivo con un coeficiente “M” muy grande.

- Método de las Dos fasesEste método es sumamente sencillo. Se usa ante la presencia de variables artificiales en el modelo a solucionar y su objetivo es eludir el uso de la Gran M.

Resolver un caso empleando cualquiera de los dos métodos

de solución investigados

1. Resolver:

Zmax = 100X1 + 200X2 + 50X3

s.a. 5X1 + 5X2 + 10X3 ≤ 1000 10X1 + 8X2 + 5X3 = 2000

10X1 + 5X2 ≥ 500

X1, X2, X3 ≥ 0

X1= 200X2= 0X3= 0Zmax = 20,000

2.- Resolver: Zmax = 100X1 + 90X2

s.a. 6X1 + 4X2 ≥ 24 20X1 + 8X2 ≤ 160 3X1 + 5X2 ≥ 15

X2 ≤ 5

X1, X2 ≥ 0

X1= 6 X2= 5 Zmax = 1,050

3.- Resolver: Zmin = 0.4X1 + 0.5X2

s.a. 0.3X1 + 0.1X2 ≤ 2.7 0.5X1 + 0.5X2 = 6 0.6X1 + 0.4X2 ≥ 6

X1, X2 ≥ 0

X1= 15/2 X2= 9/2 Zmin = 21/4

4.- Resolver: Zmin = 4X1 + X2

s.a. 3X1 + X2 = 3 4X1 + 3X2 ≥ 6 X1 + 2X2 ≤ 4

X1, X2 ≥ 0

X1= 2/5 X2= 9/5 Zmin = 17/5

5.- Resolver: Zmin = X1 + 2X2

s.a. 8X1 + 2X2 ≥ 16 X1 + X2 ≥ 5 2X1 + 7X2 ≥ 20

X1, X2 ≥ 0

X1= 3 X2= 2 Zmin = 7000

6.- Resolver: Zmin = X1 + 2X2

s.a. 3X1 + X2 ≥ 3 4X1 + 3X2 ≥ 6 X1 + X2 ≤ 3

X1, X2 ≥ 0

X1= 3/2 X2= 0 Zmin = 3/2

5ta semana 1ra Practica Calificada

Variables de Holgura (S): Se introducen las variables de holgura necesaria en cada restricción; ya que estas convierten dichas restricciones en igualdades.Una variable de holgura representa la cantidad no utilizando u ociosa de cada recurso.La función objetivo también refleja la suma de las variables de holgura; pero como esta no genera utilidad su coeficiente es “0”.

Variables Artificiales (A): Una variable artificial es una variable que no tiene significado físico en términos de un problema de programación lineal, permitiendo crear una solución factible básica para iniciar el algoritmo simplex.Cada variable artificial tiene asignado un costo que se representa por M y sirve para fines de cálculo en la tabla inicial simplex. Cuando se adiciona una variables artificial y la función objetivo se maximiza se agrega un valor M bastante pequeño (-M) y si se minimiza se agrega un valor M bastante grande (+M).Una variable artificial no aparece en la solución final del problema