Portal para Investigadores y Profesionales

Encuentra más Cursos o Publica tu Contenido en ElPrisma.com





Método Simplex



Enlaces Patrocinados






Navigation bar
  Start Previous page
 1 of 2 
Next page End 1 2  

Método Simplex
1. Introducción
Mucha gente sitúa el desarrollo de la programación lineal entre los avances científicos más importantes de
la mitad del siglo XX, y debemos estar de acuerdo con esta afirmación  si tenemos en cuenta que su
impacto desde 1950 ha sido extraordinario. Se han escrito decenas de libros de texto sobre la materia y
los artículos publicados que describen aplicaciones importantes se cuentan ahora por cientos. De hecho,
una proporción importante  de todo el cálculo científico que se lleva a cabo en computadoras se dedica al
uso de la programación lineal y a técnicas íntimamente relacionadas. (Esta proporción se estimó en un
25%, en un estudio de la IBM).
Un modelo de programación lineal proporciona un método eficiente para determinar una decisión óptima, (o
una estrategia óptima o un plan óptimo) escogida de un gran número de decisiones posibles.
En todos los problemas de Programación Lineal, el objetivo es la maximación o minimización de alguna
cantidad.
2. Desarrollo
Contrucción de los Modelos de Programación Lineal
De forma obligatoria se deben cumplir los siguientes requerimientos para construir un modelo de
Programación Lineal.
Requerimiento 1. Función objetivo. (F.O).
Debe haber un objetivo (o meta o blanco) que la optimización desea alcanzar.
Requerimiento 2. Restricciones y decisiones.
Debe haber cursos o alternativas de acción o decisiones, uno de los cuáles permite alcanzar el objetivo. 
Requerimiento 3. La F.O y las restricciones son lineales.
Deben utilizarse solamente ecuaciones lineales o desigualdades lineales. 
Modelo standard de Programación Lineal
Optimizar Z = C1X1+ C1X2 +….+ C
X
n
). 
Función objetivo. 
Sujeta a a
11
X1+ a
11
X2 +…..+ a
1n
X
n
  b1
     
   
a
21
X1+ a
21
X2 +…..+ a
2n
X
n
  b1
Restricciones
              .
    
             a
m1
X1+ a
m1
X2 +…..+ a
mn
X
n
  b
m
Debiendo ser
      X1
0, X2
0, ….. X
n
0
Donde :
X
: variables de decisión, j = 1,2.., n.
n 
: número de variables.
m 
: número de restricciones.
a
ij 
, b
i
, c
constantes, i = 1,2.., m.
Pasos para la construcción del modelo
1)
Definir las variables de decisión.
2)
Definir el objetivo o meta en términos de las variables de decisión.
3)
Definir las restricciones.
4)
Restringir todas las variables para que sean no negativas.
Ejemplo: Taller de mantenimiento.
Un taller de mantenimiento fabrica dos tipos de piezas para la reparación de equipos fundamentales del
proceso productivo. Estas piezas requieren un cierto tiempo de trabajo en cada una de las tres máquinas
que las procesan. Este tiempo, así como la capacidad disponible (h) y la ganancia por cada pieza se
muestran en el cuadro siguiente:
Tiempo por Pieza
Máquina
A
B
Fondo de Tiempo(h)
I
2
2
160
II
1
2
120
III
4
2
280
Ganancia ($/Pieza)
6
4
Se logra vender todo lo producido y se desea determinar la cantidad de piezas a fabricar que optimice la
ganancia.
Formulando el modelo
X1 : Número de piezas del tipo A.
X2 : Número de piezas del tipo B.
Optimizando la ganancia (Z).
Max Z = 6X1 + 4X2
Sujeto a las restricciones:
2X1 + 2X2
160  Fondo de tiempo de la máquina 1.
  X1 + 2X2 
120  Fondo de tiempo de la máquina 2.
4X1 + 2X2 
280  Fondo de tiempo de la máquina 3.
Como ninguna variable implicada puede ser negativa.
X1
0; X2
0
3. Métodos de solución
El método simplex es un procedimiento iterativo que permite tender progresivamente hacia la solución
óptima. Es un procedimiento sistemático y eficiente para encontrar y probar soluciones situadas en los
vértices de optimalidad.
El método requiere que las restricciones sean ecuaciones en lugar de inecuaciones, lo cual se logra
añadiendo variables de holgura a cada inecuación del modelo, variables que nunca pueden ser negativas y
tienen coeficiente 0 en la función objetivo. Para el modelo formulado anteriormente tenemos:
Z – 6X1 – 4X2   = 0
2X1 + 2X2 + s1 = 160
  X1 + 2X2 +  s2 = 120 
4X1 + 2X2 + s3  = 280
Todas las variables son no negativas.                                                                                                            
La solución básica inicial se obtiene seleccionando las variables de holgura como variables básicas,
resultando conveniente disponer los valores como se muestran en la tabla siguiente:
i
VB
Z
X1
X2
S1
S2
S3
Bi
1
Z
1
- 6
-4
0
0
0
0
2
S1
0
2
2
1
0
0
160
3
S2
0
1
2
0
1
0
120
4
S3
0
4
2
0
0
1
280
Cada ecuación debe tener una única variable básica(VB), con el coeficiente unidad en la fila
correspondiente.
Esta solución básica debe ser examinada para observar si puede ser mejorada. La presencia de
coeficientes negativos en la FO indica que la solución básica puede ser mejorada, pues el valor de Z se
incrementará.
Cuando no hay coeficientes negativos, significa que la solución es óptima.
Para encontrar una solución mejorada es necesario:
Elegir la variable que entra como la de mayor coeficiente negativo (X1)
Elegir la variable que sale como aquella que al ser removida permita que la variable que entra a la base
pueda tener un valor tan grande como sea posible, sin violar alguna de las restricciones en el modelo.
En este caso la variable S3 deja la base y a su vez X1 se introduce como la nueva variable básica.
El elemento pivote es el coeficiente que está en la intersección de la columna de la variable que entra y
la fila de la variable que sale.
Los valores correspondientes a la nueva fila pivote se obtienen dividiendo los coeficientes de la fila
pivote en la tabla inicial por el elemento pivote.
Las otras filas de la solución mejorada se calculan por la expresión:
Nueva fila = Fila anterior – elemento de la columna pivote(nueva fila pivote)
Así, se obtiene la siguiente tabla:
i
VB 
Z
X1
X2
S1
S2
S3
Bi
0
Z
1
0
- 1
0
0
1.5
420
1
S1
0
0
1
1
0
-0.5
20
2
S2
0
0
1.5
0
1
- 0.25
50
3
X1
0
1
0.5
0
0
0.25
70
Como se puede apreciar esta no es aún la solución óptima ¿Por qué?
Iterando nuevamente se obtiene la tabla correspondiente que se muestra a continuación:
i
VB
Z
X1
X1
S1
S2
S3
Bi
0
Z
1
0
0
1
0
1
440
1
X2
0
0
1
1
0
- 0.5
20
2
S2
0
0
0
- 1.5
1
0.5
20
3
X1
0
1
0
- 0.5
0
0.5
60
¿Es esta la solución óptima? Si lo es determine entonces los valores de las variables para el óptimo.
Se ha aplicado el algoritmo para el caso del modelo estándard, cuando se presentan problemas con
restricciones
o = y el criterio de optimización es mínimo, entonces hay que introducir variables artificiales
y se sugiere convertir el problema en un problema de maximizar.
4. Aspectos Fundamentales Del Método Simplex
1.
Encuentra una solución óptima
2.
Es un método de cambio de bases
3.
Requiere que la función objetivo sea expresada de tal forma que cada variable básica tenga como
coeficiente 0
4.
Requiere que cada variable básica aparezca en una y solamente una ecuación de restricción.
Dualidad
Asociado a cada problema de Programación Lineal existe un llamado dual, de hecho al de Programación
Lineal se le llama primal. La forma general del problema dual es la siguiente:
Optimizar Z = b1Y1+ b1Y2 +….+ b
Y
n
). 
Función objetivo. 
Sujeta a a
11
Y1+ a
11
Y2 +…..+ a
m1
Y1
  C1
     
   
a
21
Y1+ a
22
Y2 +…..+ a
m2
Y2
  C1
              .
Restricciones
              .
    
             a
1m
Y1+ a
2m
Y2 +…..+ a
mn
Y
m
  C
n
Para facilitar la comprensión de lo anterior considérese el diagrama siguiente:
Primal
Dual
                   C
1…….
C
n                      (1)
a
11                      
b1
                                       (2)                              (3)
a
m1                        
b
m
                       b
1…….
b
m                          (3)
(2)                             
a
11…….
a
m1             
C1   
                                                                                   (1)
                                                  C2                           
Variables
X
1…….
X
n
Variables
Y
1…….
Y
m
El problema dual tiene las siguientes características:
El el objetivo de la optimización es contrario al del primal.
Las inecuaciones de restricción son inversas.
La solución del dual es la misma que la del primal.
Desde el punto de vista económico, el significado de las variables duales es de gran interés para los
gerentes, ya que representan el valor por unidad de recurso adicional, lo cuál permite tomar decisiones
sobre donde invertir para incrementar las utilidades.
Análisis de Sensibilidad
El objetivo del análisis de sensibilidad es determinar la influencia de ciertos valores en la solución óptima,
que nos permite la interpretación razonable de los resultados obtenidos. En muchos casos la información
lograda por la aplicación del análisis de sensibilidad puede ser más importante y más informativa que
simple resultado obtenido en la solución óptima.
El análisis deviene del resultado de los cambios en:
Los coeficientes en la función objetivo.
Los términos independientes en las restricciones.
5. Bibliografía
1.
Arbonas, M.E. Optimización Industrial (I): Distribución de los recursos. Colección Productica No. 26.
Marcombo S.A, 1989.
2.
Arbonas, M.E. Optimización Industrial (II): Programación de recursos. Colección Productica No. 29.
Marcombo S.A, 1989.
3.
Anderson, D.R., Sweeney.J. , Williams,T.A. , Introducción a los Modelos Cuantitativos para
Administración. Grupo Editorial Iberoamérica. 1993.
4.
Moskowitz,H. y Wright G.P. Investigación de Operaciones. Prentice_Hall Hispanoamericana S.A.
1991.
5.
Trujillo,J;Batista,A: Métodos Económicos-Matemáticos I.Editorial ISPJAE, Habana,1986.
6.
Taha,H: Investigación de Operaciones.Alfaomega,México,1995.
7.
Buffa,E: Operations Management: Problems and Models. Edición Revolucionaria,La Habana, 1968.
6. Problemas
1- Una empresa se dedica a la producción de pinturas para interiores y exteriores para su distribución al
mayoreo. Se utilizan dos materiales básicos, A y B, para producir las pinturas. La disponibilidad máxima
de A es de 6 toneladas diarias; la de B es de 8 toneladas por día. La necesidad diaria de materia prima por
tonelada de pintura para interiores y exteriores se resumen en la tabla que sigue:
                          Toneladas de MP por              Disponibilidad
                          tonelada de pintura            máxima en toneladas
                          Exterior         Interior
Materia prima A     1                  2                                6
Materia prima B     2                  1                                8
El estudio de mercado ha establecido que la demanda diaria de pintura para interiores no puede ser mayor
que la pintura para exteriores en más de una tonelada. Así mismo, el estudio señala que la demanda
máxima de pintura para interiores está limitada a dos toneladas diarias.
La ganancia por tonelada es de $3000 para la pintura de exteriores y $2000 para la pintura de interiores.
Cuánta pintura para exteriores e interiores debe producir la empresa todos los días para maximizar el
ingreso bruto?
2- A una empresa se le ha planteado la tarea de cumplir un contrato de explotación de dos productos A y
B para el próximo semestre. El contrato estipula que deben ser entregados como mínimo 2000 unidades
de ambos productos, siendo al menos 800 de B. Los precios de venta son de 50 y 80 pesos por unidad
para A y B respectivamente. La empresa cuenta con 3 establecimientos que pueden acometer esa tarea
disponiendo los mismos de 550, 800 y 930 horas de tiempo productivo en el semestre respectivamente.
El tiempo de producción que toma cada producto, en horas, para cada establecimiento, así como el costo
por hora de producción de cada uno, se dan en la tabla siguiente:
                                         Productos
Establecimientos              A              B                  Costo/hora(pesos/h)
          1                          0,9            1,3                      25
          2                          1,2             -                        20
          3                          1,0            1,5                      22
Para balancear el uso de la fuerza laboral, se desea por la empresa que el % de capacidad productiva
utilizada en los tres establecimientos sea la misma.
Por otra parte para el terminado de los productos se utiliza una materia prima de importación de las que
disponen 3000 unidades, siendo la norma unitaria de consumo de una unidad para A y 2 para B.
Plantee el modelo matemático que permita conocer la forma más provechosa de cumplir el contrato.
Previous page Top Next page
Comparte ElPrisma.com en:   Tweet     Mister Wong 


Es política de El Prisma.com cumplir con las leyes nacionales y tratados internacionales que protegen la propiedad intelectual y los Derechos de Autor (Copyright). Los textos mostrados en esta página han sido enviados por nuestros usuarios que han declarado ser los autores de los mismos y han permitido su uso por parte de www.elprisma.com, si usted considera que la información contenida en esta página viola sus derechos de autor, por favor envíenos su notificación de infracción a sugerencias1[en]elprisma.com y removeremos los textos de nuestros servidores. Condiciones de Uso.

Administración de Empresas y Negocios, Economía y Finanzas, Mercadeo y Publicidad, Arquitectura, Diseño Gráfico, Diseño Industrial, Teología, Pedagogía, Ciencias Políticas, Derecho, Historia, Bellas Artes, Comunicación y Periodismo, Español y Literatura, Filosofía, Ingeniería Civil, Ingeniería de Minas y Petróleos, Ingeniería de Sistemas e Informática, Ingeniería Eléctrica y Electrónica, Ingeniería Industrial, Ingeniería Mecánica, Ingeniería Química, Biología, Física, Geografía, Matemáticas, Química, Medicina, Odontología, Psicología, Agronomía, Veterinaria, Zootecnia.