Agregar a favoritos      Ayuda      Português      Ingles     

Ingeniería Industrial

Enviado por ivan_escalona



Partes: 1, 2

(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.

Base

X1

X2

H1

H2

H3

H4

Z

LD

H1

a11

a12

1

0

0

0

0

b1

H2

a21

a22

0

1

0

0

0

b2

H3

a31

a32

0

0

1

0

0

b3

H4

a41

a42

0

0

0

1

0

b4

Z

-c1

-c2

0

0

0

0

1

0

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.
  2. Agregar variables artificiales en las ecuaciones que no tienen variables de holgura.
  3. 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).
  4. 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).
  5. 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

V B

Z

X1

X2

X3

X4

X5

X6

SOLUCION

Z

1

-40

-60

-50

0

0

0

0

X4

0

10

4

2

1

0

0

950

X5

0

2

2

0

0

1

0

410

X6

1

1

0

2

0

0

1

610

Z

1

20

0

-50

0

30

0

12300

60RP + FO

X4

0

6

0

2

1

-2

0

130

-4RP + R1

X2

0

1

1

0

0

1/2

0

205

1/2RP

X6

0

1

0

2

0

0

1

610

Z

1

170

0

0

25

-20

0

15550

50RP + FO

X3

0

3

0

1

1/2

-1

0

65

1/2 RP

X2

0

1

1

0

0

1/2

0

205

X6

0

-5

0

0

-1

2

1

480

-2RP + 3

Z

1

120

0

0

15

0

20

20350

20RP + FO

X3

0

1/2

0

1

0

0

0

305

RP + R1

X2

0

9/4

1

0

1/4

0

-1/2

85

1/2RP + R2

X5

0

-5/2

0

0

-1/2

1

1

240

1/2RP

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

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

  1. + 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

VB

Z

X1

X2

X3

X4

X5

SOLUCION

Z

1

-5

-1

-3

0

0

0

X4

0

2

-1

2

1

0

4

X5

0

1

1

4

0

1

4

Z

1

0

-7/2

2

5/2

0

10

5RP + FO

X1

0

1

-1/2

1

1/2

0

2

1/2RP

X5

0

0

3/2

3

-1/2

1

2

-RP + R2

Z

1

0

0

9

4/3

7/3

44/3

7/2RP + FO

X1

0

1

0

2

1/3

1/3

8/3

1/2RP + R1

X2

0

0

1

2

-1/3

2/3

4/3

2/3RP

 

 

 

 

 

 

 

 

 

 

 

Partes: 1, 2

Página siguiente 

Comentarios


Trabajos relacionados

  • Distribución Normal

    Distribución Normal. Función de densidad. La distribución binomial. Esta distribución es frecuentemente utilizada en l...

  • Estructura y funcionamiento del Programa Raíces

    Carlos alberto PérezEl programa esta compuesto por la función principal raices y 9 subfunciones: Raices (principal; Cuad...

  • El poder del Solver

    Ejemplo de cómo usar "SOLVER". En estos tiempos donde se habla de la tecnología, información, sociedad del conocimient...

Ver mas trabajos de Matematicas

 

Nota al lector: es posible que esta página no contenga todos los componentes del trabajo original (pies de página, avanzadas formulas matemáticas, esquemas o tablas complejas, etc.). Recuerde que para ver el trabajo en su versión original completa, puede descargarlo desde el menú superior.


Todos los documentos disponibles en este sitio expresan los puntos de vista de sus respectivos autores y no de Monografias.com. El objetivo de Monografias.com es poner el conocimiento a disposición de toda su comunidad. Queda bajo la responsabilidad de cada lector el eventual uso que se le de a esta información. Asimismo, es obligatoria la cita del autor del contenido y de Monografias.com como fuentes de información.

Iniciar sesión

Ingrese el e-mail y contraseña con el que está registrado en Monografias.com

   
 

Regístrese gratis

¿Olvidó su contraseña?

Ayuda