Universidad Mariano Gálvez de Guatemala
Facultad de Ciencias de la Administración
Centro Universitario Santa Lucia Cotz.
CARRERA
Licenciatura en Administración de Empresas
Curso
Investigación de Operaciones
Catedrático:
Ing. Selvyn Archeita
“METODO SIMPLE”
Fredy Alexander Marroquín Vásquez
Carne: 2922-14-11229
Santa Lucia Cotz. 29 de julio de 2017
1
Introducción
El método algebraico es muy dispendioso, en razón a que trabaja con todos los
datos de las ecuaciones, para mejorar éste aspecto se creó el método simplex
cuya gran virtud es su sencillez, método muy práctico, ya que solo trabaja con
los coeficientes de la función objetivo y de las restricciones. Las reglas de
decisión para determinar la variable que entra, la que sale, la gran M, y cómo
determinar que estamos en el óptimo; Todas éstas reglas de decisión fueron
deducidas del método algebraico, solamente que aquí se han acomodado para
ser usadas en el tipo de tablero simplex que se usará.
2
PROGRAMACION LINEAL: METODO SIMPLEX
Los problemas reales de programación lineal generalmente tienen variables de
decisión y muchas restricciones. Tales problemas no pueden ser resueltos
gráficamente. Se usan algoritmos tales como el simplex. El método simplex es
un procedimiento iterativo que progresivamente permite obtener una solución
óptima para los problemas de programación lineal. Existen numerosos
programas tanto para computadoras centrales como para personales. Aunque
el método simples es especialmente útil en problemas de gran escala
(resueltos con una computadora), en seguida se practicará en el caso del
mismo problema que fue resuelto gráficamente en el ejemplo sobre la empresa
química “Chemical”.
Procedimiento general del simplex
1. Establézcase la tabla inicial de simples. Formular la función objetivo y
las restricciones e introducir las variables de decisión, variable en la
solución, valor en solución (LD), C (contribución de la variable), Z (costo
de introducir la variable), C – Z (contribución neta de la variable).
2. Selecciónese la columna pivote. Ésta es la columna con el número
positivo más grande en el renglón inferior (C - Z). Esta se convierte en la
nueva variable de la solución.
3. Selecciónese el renglón pivote. Éste es el renglón con la razón más
pequeña del valor LD dividido por el valor de la columna pivote. Úsense
sólo números positivos. Esto identifica la variable que deja la solución.
4. Enciérrese en un círculo el elemento pivote. Ésta es la intersección del
renglón y la columna pivotes.
5. Conviértase al elemento pivote en un 1. Hágase esto dividiendo cada
valor del renglón pivote entre el valor pivote. Métase este renglón en una
tabla nueva.
6. Genérense los demás renglones de la nueva tabla con ceros en la
columna pivote. Esto se hace multiplicando el nuevo renglón (del paso 5)
por el negativo del elemento en la columna pivote. El resultado será
sumado al antiguo renglón. Introdúzcase este renglón revisado en la
nueva tabla, y continúese este procedimiento en cada renglón de la
sección central de la tabla.
7. Prueba de optimización. Calcúlense los valores de Z y C – Z. Los
valores de Z de cada columna son (elementos de la columna) ( C ). Si
todos los valores de C – Z son ≤ 0, la solución es óptima. Léanse los
valores de las variables en la solución de la columna de LD y el valor de
la función objetivo del renglón de Z en la columna de LD. Si la solución
no es óptima, regrese al paso 2.
Variables de holgura- El método simples empieza con el planteamiento de
una función objetivo y ecuaciones de restricción. Las rutinas computarizadas de
programación lineal (PL) automáticamente arreglarán esos datos iniciales,
pero tratándose de soluciones manuales, debe construirse en cada paso la
tabla de simples. Esto requiere que las restricciones sean establecidas como
igualdades. En los problemas de maximización se logra esto añadiendo
variables de holgura (s) a cada restricción. La holgura representa una cantidad
3
no utilizada, o la diferencia entre lo que es usado y el límite de lo que puede
usarse.
Por ejemplo añadiendo variables de holgura a las desigualdades del
ejemplo de la industria “Chemical”; se tienen las nuevas ecuaciones que se
muestran en la siguiente tabla. Nótese que S1 está relacionada con la
restricción de la máquina A y S2 lo está con la máquina B.
Restricción Desigualdad Ecuación con holgura
Máquina A h 4x + 6y ≤ 12 4x + 6y + S1 = 12
Máquina B h 8x + 4y ≤ 16 8x + 4y + S2 = 16
La restricción de la máquina A ahora indica cuatro horas por el número de
unidades de X producidas más seis horas por el número de unidades de Y
producidas, más las horas de holgura = 12. Así, pues, si una unidad de X y una
Y son producidas, se tienen dos horas de tiempo de holgura S en la máquina A,
dado que 4(1) + 6(1) + 2 = 12. Si ni X ni Y son producidas, “se produce” una
holgura total, y S1 = 12.
El método simplex siempre comienza con una solución factible dentro de la
cual sólo se produce holgura. Esto corresponde al origen en la solución gráfica,
dónde X y Y son iguales a cero. Se empieza con una solución inexacta, pero
factible, que corresponde a una esquina de la región factible. Se empieza con
una solución inexacta, pero factible, que corresponde al origen, donde sólo se
produce holgura, es decir, cero utilidad. Por tanto, las variables de holgura (por
ejemplo S1 y S2 están en la solución, y las otras variables de decisión (X y Y) no
están en la solución (así, tienen valores de cero).
Preséntense la función objetivo y las restricciones del siguiente ejemplo en una
tabla inicial de simplex
Una empresa química “Chemical” produce limpiadores para automóviles X y
pulidores Y y gana $10 en cada lote de X, y $30 en Y. Ambos productos
requieren procesarse en las mismas máquinas, A y B, pero X requiere cuatro
horas en A y ocho en B, mientras que Y requiere seis horas en A y cuatro en B.
Durante la semana entrante las máquinas A y B tienen 12 y 16 horas de
capacidad disponible, respectivamente. Suponiendo que existe demanda de
ambos productos, cuántos lotes de cada uno deben producirse para alcanzar la
unidad óptima Z?.
La función objetivo es:
Max Z = $10X + $30Y
Las restricciones son:
h maquina A : 4X + 6Y = 12
h máquina B : 8X + 4Y =16
X,Y ≥ 0
4
Formato simplex
C 10 30 0 0 Valores de solución
Variables de la Variables de decisión
solución X Y S1 S2 (LD)
0 S1 4 6 1 0 12
0 S2 8 4 0 1 16
Z 0 0 0 0 0
C-Z 10 30 0 0 0
Elementos de la tabla simplex.
La parte central de la tabla simplex consta de los coeficientes de las
restricciones de:
4X + 6Y + 1S1 + 0S2 = 12
8X + 4Y + 0S1 + 1S2 =16
Nótese que se ha asignado un uno (1) a la variable de holgura asociada con su
propia restricción, y un cero (0) a la otra variable de holgura
La columna de variables en la solución indica cuáles variables están en la
solución (en este caso, sólo las de hoguera) y la columna de valores solución
indica las cantidades de solución. Los números vienen del lado derecho LD de
las restricciones (en este caso, 12 horas de holgura para la máquina A y 16
horas para la B)
La C en la esquina superior izquierda encabeza a la vez un renglón y una
columna. Especifican la cantidad de contribución a la función objetivo de cada
unidad de las variables a que se refiere. Esto es, cada unidad de X (limpiador)
contribuye con $10 a las utilidades y cada unidad de Y (pulidor) lo hace con
$30. El tiempo de holgura de la maquina A y B proporciona $0 de contribución
tanto de S1 como de S2.
El renglón de Z en la tabla muestra el costo de oportunidad, o la cantidad de
contribución que debe ser introducida o (producida) por unidad (o por unidad
extra) de la variable en cada columna. Esto se calcula para cada columna
multiplicando los elementos de la columna por la contribución en la columna C
y sumándolos después
Esto es, el valor de Z para la columna X es (4 x 0) + (8 x 0) = 0.
Esto significa que para introducir una unidad de X (limpiador) en la
solución, deben darse cuatro horas de tiempo de holgura en la máquina
A, con un costo de $0, y ocho horas de holgura en la máquina B,
también con un costo de $0.
El valor de Z para la columna LD representa la contribución total de las
variables en la solución, debido a que esta solución (inicial) es “producir” 12
5
horas de holgura en la máquina A (con $0 de contribución) y 16 horas de
holgura en la máquina B con ($0 de contribución), la utilidad total de esta
solución inicial es cero. El renglón de Z en la solución inicial siempre tiene
ceros, pero cambia al progresar la solución.
Los valores del renglón inferior (C-Z) representan la contribución neta de
introducir una unidad de la columna variable en la solución. En la tabla inicial
aparecen simplemente los coeficientes de la función objetivo seguidos por
ceros en las columnas de las variables de holgura. Es decir, se puede
incrementar el valor de la función objetivo en un total de $10 por cada unidad
de X producida y en $30 por cada unidad de Y producida, y debido a que la
holgura no tiene ningún valor deben introducirse X o Y en esta etapa.
Produciendo más holgura obviamente no se incrementan las utilidades.
Metodología de cálculo
La metodología de solución de los problemas de maximización hace necesario
seleccionar una columna y un renglón pivotes y revisar los valores de la tabla
hasta que en el renglón inferior sean menores o iguales que cero.
- Úsense los pasos del procedimiento simplex –
C 10 30 0 0 Valores
Variables Variables de decisión de
de la solución
solución X Y S1 S2 (LD)
0 S1 4 6 1 0 12
0 S2 8 4 0 1 16
Z 0 0 0 0 0
C-Z 10 30 0 0 0
1. Seleccionar una columna y un renglón pivotes
a) La columna pivote es la que tiene el número positivo más grande en el
renglón inferior
C-Z 10 30 0 0 0
En este ejercicio es 30.
b) El renglón pivote es el que tiene la razón más pequeña, del renglón
pivote
6
12 16
2 (mínimo) 4
6 4
C 10 30 0 0 Valores
Variables Variables de decisión de
de la solución
solución X Y S1 S2 (LD)
0 S1 4 6 1 0 12
0 S2 8 4 0 1 16
Z 0 0 0 0 0
C-Z 10 30 0 0 0
Por lo tanto el renglón 1 es el renglón pivote.
c) El elemento pivote es encerrado en un círculo 6
C 10 30 0 0 Valores
Variables Variables de decisión de
de la solución
solución X Y S1 S2 (LD)
0 S1 4 6 1 0 12
0 S2 8 4 0 1 16
Z 0 0 0 0 0
C-Z 10 30 0 0 0
2. Divídase cada valor del renglón pivote 1 entre el elemento pivote (6) y
colóquense los valores en una nueva tabla.
C 10 30 0 0 Valores
Variables Variables de decisión de
de la solución
solución X Y S1 S2 (LD)
0 Y 2/3 1 1/6 0 2
a) Genérense los otros renglones para la siguiente tabla, de tal manera que
los elementos de la columna pivote sean iguales a cero.
Se empieza con el renglón S2, el cual tiene 4 en la columna de Y. Se
multiplica el nuevo renglón (del paso 2) por el negativo del valor que se
desea convertir (-4), y se suma al anterior renglón de S2. Se multiplica el
nuevo renglón por -4. el resultado se muestra en la siguiente tabla.
7
X Y S1 S2 (LD)
El renglón del paso 2 se -4(2/3) -4(1) - -4(0) -4(2)
multiplica por -4 4(1/6)
Obtener el resultado -8/3 -4 -2/3 0 -8
Sumarlo al renglón de S2 8 4 0 1 16
Para obtener el nuevo 16/3 0 .2/3 1 8
renglón
El renglón obtenido se introduce a la nueva tabla del paso 2.
C 10 30 0 0 Valores
Variables Variables de decisión de
de la solución
solución X Y S1 S2 (LD)
30 Y 2/3 1 1/6 0 2
0 S2 16/3 0 .2/3 1 8
Z
Si hay más renglones que convertir, debe repetirse este paso en el
siguiente renglón. Dado que ahí no hay más, puede procederse a
calcular el renglón Z y C-Z.
Los valores en el renglón Z son ∑ (elementos de la columna) (C)
Elementos del renglón Z
Para X: Z = 2/3(30) + 16/3(0) = 20
Para Y: Z = 1(30) + 0(0) = 30
Para S1: Z = 1/6(30) – 2/3(30) = 5
Para S2: Z = 0(30) + 1(0) = 0
Para LD: 2(30) + 8(0) = 60
Después de que se introducen éste y los valores de C-Z en la siguiente
matriz, se tiene:
C 10 30 0 0 Valores
Variables Variables de decisión de
de la solución
solución X Y S1 S2 (LD)
30 Y 2/3 1 1/6 0 2
0 S2 16/3 0 .2/3 1 8
Z 20 30 5 0 60
C-Z -10 0 -5 0
Repetir los pasos anteriores hasta que todos los valores del renglón
inferior sean ≤ 0. Dado que todos los valores son ≤ 0, ha sido alcanzada
la solución óptima. Las variables en la solución son identificadas por las
columnas en la parte central de la tabla que tienen un 1, y el resto de los
valores son cero. Los valores solución son datos en la columna del lado
derecho, como se ve en la siguiente tabla.
8
X Y S1 S2 (LD)
- 1 - 0 2
- 0 - 1 8
Z - - - - 60
Por tanto,
X = no está en la solución
Y = 2 unidades
Z = $60
Nótese que la variable de holgura asociada con la restricción 2 también tiene
un 1 y ceros, lo cual significa que tiene holgura en la solución y que la
restricción no se agotó. Entonces hay sólo una variable de decisión (no
holgura) en la solución (Y) y una restricción agotada (número 1). Esto
concuerda con el teorema fundamental de programación lineal, que establece
que el número de variables de decisión (no holgura) de la solución siempre
será igual a número de restricciones que son agotadas.
Esta solución es la misma que la dada en el ejemplo resuelto por el método
gráfico.
9
Conclusión
El método simplex es más práctico que el método algebraico, pero para
problemas de un gran número de variables y restricciones, fácilmente se vuelve
dispendioso por el número de iteraciones y por supuesto demorado para
obtener la solución óptima,.
10
Bibliografía
Monks Joseph G. ADMINISTRACIÓN DE OPERACIONES, SERIE SCHAUM.,
Primera edición, México D.F., Mc. Graw Hill., p.p. 103 – 104.
Taha Hamdy. INVESTIGACIÓN DE OPERACIONES. Séptima edición, México
D.F., Prentice Hall. p.p 71 - 90
11