Ingeniería Industrial

(Academia de IO de la
UPIICSA)

1. Exprese el modelo
   matemático en la forma
   estándar.
2. Elabore la tabla inicial del
   simplex
3. Determine la variable no
   básica que entra
4. Determine la variable que
   sale:
5. Aplicación del
   método Gauss-Jordan (o de operaciones sobre
   renglones).
6. Criterio para terminar el
   proceso.
7. Algoritmo del Método
   de la Gran M

1.-Exprese el
modelo
matemático en la forma estándar.

Todas las restricciones del modelo matemático
deben convertirse en igualdades.

• No debe haber ningún lado derecho
  negativo.
• Si es "<=" entonces se agrega una
  Hi
• Si es ">=" entonces se agregan Ai –
  Si
• Si es " =" entonces se agrega una
  Ai

2.      Elabore la tabla
inicial del simplex:
  Note que en la fila
superior de la matriz se
enlistan todas las variables del
problema ( las de decisión y las agregadas). Además
observe que en la columna izquierda, es decir en la base, no se
colocan las variables de decisión ni las sobrantes. Esto
es en la tabla inicial, pero no implica que dichas variables no
puedan entrar a la base en tablas posteriores.

3.      Determine la
variable no básica que entra:

Se elige como la variable que entra en
maximización (minimización) como la variable no
básica que tiene el indicador más negativo
(positivo), en la fila de coeficientes de la Función
Objetivo (Z).
Los empates se rompen arbitrariamente.

4.      Determine la
variable que sale:

Se determina tomando el cociente de los valores en
la columna del lado derecho (LD) de cada restricción entre
los coeficientes positivos de la columna de la variable que
entra. Si el coeficiente es "cero o negativo" entonces el
cociente se considera infinito. La variable básica
asociada al cociente más pequeño (en ambos casos,
maximización y minimización) es la variable que
sale. Los empates se rompen arbitrariamente. Sin embargo, en caso
de haber empate y que una de las variables involucradas sea una
variable artificial, se elige a ésta como la variable
saliente.

 5.     
Aplicación del método
Gauss-Jordan (o de operaciones sobre
renglones).

Mediante este procedimiento se
elimina (en realidad se sustituye) la variable que entra, en
todas las filas de la tabla. Es decir, se tiene que convertir la
columna de la variable que entra en un vector columna unitario
(un 1 y puros ceros). Esto se logra de la siguiente manera:
5.1. El primer paso en la eliminación de Gauss-Jordan es
multiplicar la fila pivote por el inverso multiplicativo del
elemento pivote (para formar la unidad) y reemplazar el nombre de
la variable que sale por el nombre de la variable que entra.
5.2. La eliminación (o sustitución) se logra
sumando un múltiplo adecuado de la fila pivote ( elemento
pivote = 1) a cada una de las demás filas.

Es decir, se multiplica la fila pivote por el negativo
del número que deseamos que se convierta en cero y el
resultado de esta multiplicación se suma a la fila donde
queremos que aparezca el cero. 

1. Criterio para
   terminar el proceso.

Los pasos 2, 3, 4 y 5 se repiten hasta que todos los
indicadores
de la función objetivo sean no negativos (si es de
maximización) o sean no positivos (si es de
minimización).

Cuando esto ocurre se dice que se ha llegado a la
solución óptima del

problema. 

Variables artificiales

En los problemas
anteriores del método simplex hemos utilizado las
variables de holgura como una solución inicial factible.
Sin embargo, si la restricción original es una
ecuación ("=") o es del tipo  "" , ya no
tenemos una solución factible inicial
preparada. 

Por lo que es necesario generar una solución
inicial. La idea de utilizar Variables Artificiales es muy
simple. Es necesario sumar una variable no negativa
a todas la ecuaciones que
no tengan variables básicas iniciales. Las variables
agregadas desempeñarán la misma función que
una variable de holgura. Sin embargo, como estas variables no
tienen un significado físico desde el punto de vista del
problema original ( de aquí el nombre de "artificial"), el
procedimiento será valido sólo si hacemos que estas
variables sean cero cuando se llegue a la tabla
óptima. 

Algoritmo del
Método de la Gran M

1. Pasar a la forma estándar el modelo
   matemático.
3. Agregar variables artificiales en las ecuaciones
   que no tienen variables de holgura.
4. Se deben penalizar a las variables artificiales en
   la función objetivo asignándoles coeficientes
   positivos muy grandes. Sea M un número muy grande. (
   En los modelos de
   Minimización la penalización para cada variable
   artificial se suma y en los de Maximización se
   restan).
5. En la función objetivo no deben aparecer
   variables básicas por lo que se hace necesario
   eliminar las variables artificiales de la F.O.(Quitar las "M"
   de las columnas de las artificiales).
6. Con la solución inicial artificial se aplica
   el método simplex de la forma acostumbrada generando
   las tablas necesarias para llegar a una
   solución.

• Notas:
• Cuando una solución contiene variables
  artificiales básicas igual a cero entonces la
  solución sí es factible con respecto al problema
  original.
• Si el problema no tiene solución factible,
  cuando menos una variable artificial será positiva en la
  solución óptima. 

Cuando tenemos restricciones de igualdad, de
mayor o igual;  cuando algunas de las bi son
negativas o queremos minimizar, para usar el simplex, debemos
identificar una solución básica inicial.

Se revisa el problema añadiendo variables
artificiales, sólo con el propósito de que sea la
variable básica inicial para esa ecuación. Son
variables no-negativas y se altera la función objetivo
para que imponer una penalidad exhorbitante en que estas
variables artificiales tengan valores
mayores de cero. El método del simplex entonces hace
desaparecer estas variables hasta que el problema real es
resuelto.

Utilizando el método simplex resuelva el
siguiente problema de programación
lineal.

Max Z = 40X1 + 60X2 +
50X3

s.a. 10 X1 + 4 X2 + 2
X3  950

2 X1 + 2 X2 + 
410

X1 + + 2 X3 
610

X1 , X2 , X3
 0

Max Z -40X1 – 60X2 –
50X3

s.a. 10 X1 + 4 X2 + 2
X3 + X4 = 950

2 X1 + 2 X2 + + X5 =
410

X1 + + 2 X3 + X6 =
610

X1 , X2 , X3 ,
X4 , X5 , X6 ³ 0

• Solución básica actual:

X4 = 950 min í 950/4 , 410/2 ,
-ý

X5 = 410 min í 237.5 , 205 , -ý

X6 = 610

• Solución básica actual:

X4 = 130 min í 130/2 , – ,
610/2ý

X2 = 205 min í 65 , – , 305ý

X6 = 610

• Solución básica actual:

X3 = 65 min í – , 205/0.5 ,
480/2ý

X2 = 205 min í – , 410 , 240ý

X6 = 480

• Por lo tanto la solución óptima
  es:

Z* = 20350

X2* = 85

X3* = 305

X5* = 240

X1* = X4* = X6* =
0

• Comprobación en la función
  objetivo:

Max Z = 40X1 + 60X2 +
50X3

Z = 4 (0) + 3 (85) + 50(305)

Z = 20350

• Comprobación en las restricciones:

10 X1 + 4 X2 + 2 X3 +
X4

10(0) + 4( 85) + 2(305) + 0 = 950

2 X1 + 2 X2 +
X5

2(0) + 2(85) + 240 = 410

X1 + 2 X3 +
X6

0. + 2(305) + 0 = 610

Utilizando el método simplex resuelva el
siguiente problema de programación lineal.

Max Z = 5X1 + X2 +
3X3

s.a. 2 X1 – X2 + 2
X3 £ 4

X1 + X2 + 4 X3
£ 4

X1 , X2 , X3 ³
0