metodo simplex
Páginas: 6 (1428 palabras)
Publicado: 18 de octubre de 2013
ING. SERGIO H. CASTRO INVESTIGACION OPERATIVA: METODO SIMPLEX
INVESTIGACIÓN OPERATIVA: PROGRAMACIÓN LINEAL
En el modelo general de programación lineal se encuentra definidas una función
objetivo o funcional la cual puede ser planteada como un problema de maximización o uno de minimización. Esta función esta sujeta a un conjunto de restricciones que pueden ser descriptas
como ecuaciones (restricciones de igualdad) o inecuaciones (restricciones del tipo mayor o igual y
del tipo menor o igual) además de las restricciones de no negatividad.
La función objetivo estará formada por una suma lineal de valores, estos valores se
obtienen de multiplicar un coeficiente (de beneficio o de costo según el caso) por cada una de las variables que se representarán en el modelo o problema.
En estos problemas, cuando las restricciones son inecuaciones, podemos
transformarlas a ecuaciones agregando variables de holgura que también serán no negativas.
En las restricciones de menor o igual ( = ) bastará con restar al primer
miembro de la inecuación una cantidad no negativa que será igual a la diferencia entre el primer miembro y el segundo, representada por la variable de holgura, de tal manera que se transforme la
desigualdad en igualdad.
Estas variables de holgura serán agregadas en la función objetivo y les
corresponderán un coeficiente nulo (cero).
Estos problemas se caracterizan por el gran número de soluciones posibles que satisfacen las condiciones fundamentales de cada problema. La selección de una solución dada
como la mejor solución dependerá del objetivo planteado y se denominará SOLUCION OPTIMA.
Estas soluciones óptimas pueden ser obtenidas a través de resoluciones gráficas de
los problemas cuando se plantean situaciones con no más de dos variables. Cuando los problemas
tienen mas de dos variables deberán ser resueltos analíticamente.
EL MÉTODO SIMPLEXSirve para resolver analíticamente los problemas lineales.
El método Simplex consiste en explorar las soluciones posibles básicas del modelo,
comparándolas entre sí en sucesivos pasos hasta encontrar la óptima.
PROCEDIMIENTO DEL MÉTODO SIMPLEX
1)
En primer lugar observamos si existen valores negativos en el vector de
términos independientes de las restricciones. Si esto ocurriese, se los lleva a una valoración
positiva multiplicando por (1) ambos miembros de las restricciones en las cuales aparecen dichos
valores. Recuérdese que si la restricción donde existiera dicho problema fuese una inecuación, al
multiplicar ambos miembros por (1) se tendrá que cambiar el sentido de la desigualdad.
2)
Analizamos luego el tipo de restricciones (ecuaciones o inecuaciones). Si
son inecuaciones (=) se deberá convertirlas en ecuaciones sumando o restando en los
primeros miembros de las mismas según corresponda, nuevas variables no negativas (variables de
holgura).
3)
En la Función Objetivo (sea de máximo o de mínimo) las variables de
holgura deben estar precedidas por un coeficiente nulo.
4)
Llamaremos m al número de ecuaciones linealmente independientes.
Debemos determinar si existen m vectores unitarios, los cuales deberán corresponder cada uno de
estos vectores unitarios a una restricción diferente.
ING. SERGIO H. CASTRO INVESTIGACION OPERATIVA: METODO SIMPLEX
PROCESO DE CÓMPUTO
5)
La información disponible se transcribe en una tabla. Toda solución tendrá m variables en la base (igual a la cantidad de ecuaciones lineales). Partimos de una solución posible
básica o sea que existirán m valores positivos para las variables, eligiendo como base inicial la
formada por los m vectores unitarios identificados en el paso anterior.
Cj
0
0
0
Ci >
18
BASE SOLUCION X1
X4
400
4
X5
800
7
X6
1000
8
Zj
0
0
Cj Zj
18
10...
INVESTIGACIÓN OPERATIVA: PROGRAMACIÓN LINEAL
En el modelo general de programación lineal se encuentra definidas una función
objetivo o funcional la cual puede ser planteada como un problema de maximización o uno de minimización. Esta función esta sujeta a un conjunto de restricciones que pueden ser descriptas
como ecuaciones (restricciones de igualdad) o inecuaciones (restricciones del tipo mayor o igual y
del tipo menor o igual) además de las restricciones de no negatividad.
La función objetivo estará formada por una suma lineal de valores, estos valores se
obtienen de multiplicar un coeficiente (de beneficio o de costo según el caso) por cada una de las variables que se representarán en el modelo o problema.
En estos problemas, cuando las restricciones son inecuaciones, podemos
transformarlas a ecuaciones agregando variables de holgura que también serán no negativas.
En las restricciones de menor o igual ( = ) bastará con restar al primer
miembro de la inecuación una cantidad no negativa que será igual a la diferencia entre el primer miembro y el segundo, representada por la variable de holgura, de tal manera que se transforme la
desigualdad en igualdad.
Estas variables de holgura serán agregadas en la función objetivo y les
corresponderán un coeficiente nulo (cero).
Estos problemas se caracterizan por el gran número de soluciones posibles que satisfacen las condiciones fundamentales de cada problema. La selección de una solución dada
como la mejor solución dependerá del objetivo planteado y se denominará SOLUCION OPTIMA.
Estas soluciones óptimas pueden ser obtenidas a través de resoluciones gráficas de
los problemas cuando se plantean situaciones con no más de dos variables. Cuando los problemas
tienen mas de dos variables deberán ser resueltos analíticamente.
EL MÉTODO SIMPLEXSirve para resolver analíticamente los problemas lineales.
El método Simplex consiste en explorar las soluciones posibles básicas del modelo,
comparándolas entre sí en sucesivos pasos hasta encontrar la óptima.
PROCEDIMIENTO DEL MÉTODO SIMPLEX
1)
En primer lugar observamos si existen valores negativos en el vector de
términos independientes de las restricciones. Si esto ocurriese, se los lleva a una valoración
positiva multiplicando por (1) ambos miembros de las restricciones en las cuales aparecen dichos
valores. Recuérdese que si la restricción donde existiera dicho problema fuese una inecuación, al
multiplicar ambos miembros por (1) se tendrá que cambiar el sentido de la desigualdad.
2)
Analizamos luego el tipo de restricciones (ecuaciones o inecuaciones). Si
son inecuaciones (=) se deberá convertirlas en ecuaciones sumando o restando en los
primeros miembros de las mismas según corresponda, nuevas variables no negativas (variables de
holgura).
3)
En la Función Objetivo (sea de máximo o de mínimo) las variables de
holgura deben estar precedidas por un coeficiente nulo.
4)
Llamaremos m al número de ecuaciones linealmente independientes.
Debemos determinar si existen m vectores unitarios, los cuales deberán corresponder cada uno de
estos vectores unitarios a una restricción diferente.
ING. SERGIO H. CASTRO INVESTIGACION OPERATIVA: METODO SIMPLEX
PROCESO DE CÓMPUTO
5)
La información disponible se transcribe en una tabla. Toda solución tendrá m variables en la base (igual a la cantidad de ecuaciones lineales). Partimos de una solución posible
básica o sea que existirán m valores positivos para las variables, eligiendo como base inicial la
formada por los m vectores unitarios identificados en el paso anterior.
Cj
0
0
0
Ci >
18
BASE SOLUCION X1
X4
400
4
X5
800
7
X6
1000
8
Zj
0
0
Cj Zj
18
10...
Leer documento completo
Regístrate para leer el documento completo.