sábado, 7 de mayo de 2011

Temario Unidad 1

·         La Investigación de Operaciones usa el método científico para investigar el problema en cuestión. En particular, el proceso comienza por la observación cuidadosa y la formulación del problema incluyendo la recolección de datos pertinentes.
·         La Investigación de Operaciones adopta un punto de vista organizacional. De esta manera intenta resolver los conflictos de interés entre los componentes de la organización de forma que el resultado sea el mejor para la organización completa.
·         La Investigación de Operaciones intenta encontrar una mejor solución (llamada solución óptima), para el problema bajo consideración. En lugar de contentarse con mejorar el estado de las cosas, la meta es identificar el mejor curso de acción posible.
·         En la Investigación de Operaciones es necesario emplear el enfoque de equipo. Este equipo debe incluir personal con antecedentes firmes en matemáticas, estadísticas y teoría de probabilidades, economía, administración de empresas ciencias de la computación, ingeniería, etc. El equipo también necesita tener la experiencia y las habilidades para permitir la consideración adecuada de todas las ramificaciones del problema.
·         La Investigación de Operaciones ha desarrollado una serie de técnicas y modelos muy útiles a la Ingeniería de Sistemas. Entre ellos tenemos: la Programación No Lineal, Teoría de Colas, Programación Entera, Programación Dinámica, entre otras.
·         La Investigación de Operaciones tiende a representar el problema cuantitativamente para poder analizarlo y evaluar un criterio común.
·         Un modelo de decisión debe considerarse como un vehículo para resumir un problema de decisión en forma tal que haga posible la identificación y evaluación sistemática de todas las alternativas de decisión del problema. Después se llega a una decisión seleccionando la alternativa que se juzgue sea la mejor entre todas las opciones disponibles.
·         Un modelo es una abstracción selectiva de la realidad.
·         El modelo se define como una función objetivo y restricciones que se expresan en términos de las variables (alternativas) de decisión del problema.
·         Una solución a un modelo, no obstante, de ser exacta, no será útil a menos que el modelo mismo ofrezca una representación adecuada de la situación de decisión verdadera.
·         El modelo de decisión debe contener tres elementos:
Alternativas de decisión, de las cuales se hace una selección.
Restricciones, para excluir alternativas infactibles.
 Criterios para evaluar y clasificar alternativas factibles.
Tipos de Modelos de Investigación de Operaciones.
(a) Modelo Matemático: Se emplea cuando la función objetivo y las restricciones del modelo se pueden expresar en forma cuantitativa o matemática como funciones de las variables de decisión.
(b) Modelo de Simulación: Los modelos de simulación difieren de los matemáticos en que las relaciones entre la entrada y la salida no se indican en forma explícita. En cambio, un modelo de simulación divide el sistema representado en módulos básicos o elementales que después se enlazan entre si vía relaciones lógicas bien definidas. Por lo tanto, las operaciones de cálculos pasaran de un módulo a otro hasta que se obtenga un resultado de salida.
Los modelos de simulación cuando se comparan con modelos matemáticos; ofrecen mayor flexibilidad al representar sistemas complejos, pero esta flexibilidad no esta libre de inconvenientes. La elaboración de este modelo suele ser costoso en tiempo y recursos. Por otra parte, los modelos matemáticos óptimos suelen poder manejarse en términos de cálculos.
Modelos de Investigación de Operaciones de la ciencia de la administración: Los científicos de la administración trabajan con modelos cuantitativos de decisiones.
Modelos Formales: Se usan para resolver problemas cuantitativos de decisión en el mundo real. Algunos modelos en la ciencia de la administración son llamados modelos determinísticos. Esto significa que todos los datos relevantes (es decir, los datos que los modelos utilizarán o evaluarán) se dan por conocidos. En los modelos probabilísticos (o estocásticos), alguno de los datos importantes se consideran inciertos, aunque debe especificarse la probabilidad de tales datos.
En la siguiente tabla se muestran los modelos de decisión según su clase de incertidumbre y su uso en las corporaciones. (D, determinista; P, probabilista; A, alto; B, bajo)
Tipo de Modelo
Clase de Incertidumbre
Frecuencia de uso en corporaciones
Programación Lineal
D
A
Redes (Incluye PERT/CPM)
D,P
A
Inventarios, producción y programación
D,P
A
Econometría, pronóstico y simulación
D,P
A
Programación Entera
D
B
Programación Dinámica
D,P
B
Programación Estocástica
P
B
Programación No Lineal
D
B
Teoría de Juegos
P
B
Control Optimo
D,P
B
Líneas de Espera
P
B
Ecuaciones Diferenciales
D
B
Modelo de Hoja de Cálculo Electrónica: La hoja de cálculo electrónica facilita hacer y contestar preguntas de "que si" en un problema real. Hasta ese grado la hoja de cálculo electrónica tiene una representación selectiva del problema y desde este punto de vista la hoja de cálculo electrónica es un modelo.
En realidad es una herramienta más que un procedimiento de solución.
Etapas de la Investigación de Operaciones.
Las etapas de un estudio de Investigación de Operaciones son las siguientes:
Definición del problema de interés y recolección de los datos relevantes.
Formulación de un modelo matemático que represente el problema.
Desarrollo de un procedimiento basado en computadora para derivar una solución al problema a partir del modelo.
Prueba del modelo y mejoramiento según sea necesario.
Preparación para la aplicación del modelo prescrito por la administración.
Puesta en marcha.
1.2 Formulación del Modelo
Una vez que nos aseguramos que la definición del problema ha sido construida de manera específica y correcta, continuamos con la formulación del modelo. El modelo, usualmente matemático, debe ser formulado de tal manera que exprese la esencia del problema:
El modelo matemático está basado en ecuaciones y desigualdades establecidas en términos de variables, las cuales expresan la esencia del problema a resolver; las cuales son definidas en función del modelo del problema.
Después de localizar las variables en función del problema, se procede a determinar matemáticamente las dos partes que constituyen el modelo:
·         La medida de efectividad que permite conocer el nivel de logro de los objetivos y generalmente es una función llamada función objetivo.
·         Las limitantes del problema, llamadas restricciones, que son un conjunto de igualdades o desigualdades que constituyen las barreras y obstáculos para la consecución del objetivo.
  • Un modelo matemático es una idealización abstracta de un problema, lo cual mayormente nos lleva a aproximaciones y suposiciones. Por lo que debemos cuidar que el modelo siempre sea una representación valida del problema.
La valides de un modelo requiere que exista una alta correlación entre las predicciones del modelo y la realidad; para lograr esto es importante hacer un número considerable de pruebas al modelo y caso de ser necesario, las pertinentes modificaciones. Aun cuando la validación del modelo se incluyera al final de este documento, la mayor parte de la validación del modelo se hace durante la etapa de la construcción del modelo.
  • Validación del Modelo
  • Solución Optima

1.3 METODO GRAFICO
La PL es una técnica mediante la cual se toman decisiones, reduciendo el problema bajo estudio a un modelo matemático general, el cual debe ser resuelto por métodos cuantitativos.
En desarrollo de este capítulo se aplicarán la solución de dichos modelos aplicando diversas técnicas como: el método gráfico, método simplex, método matricial, técnica de la gran M.
Además se desarrollara la aplicación de variables artificiales y obtención de soluciones para identificar a qué tipo de clasificación pertenecen. Por medio de dichos modelos de solución se podrá obtener la solución adecuada para cada problema y facilitar la toma de decisiones.
Método gráfico.
El método gráfico se utiliza para la solución de problemas de PL, representando geométricamente a las restricciones, condiciones técnicas y el objetivo.
El modelo se puede resolver en forma gráfica si sólo tiene dos variables. Para modelos con tres o más variables, el método gráfico es impráctico o imposible.
Cuando los ejes son relacionados con las variables del problema, el método es llamado método gráfico en actividad. Cuando se relacionan las restricciones tecnológicas se denomina método gráfico en recursos.
Los pasos necesarios para realizar el método son nueve:
1. graficar las soluciones factibles, o el espacio de soluciones (factible), que satisfagan todas las restricciones en forma simultánea.
2. Las restricciones de no negatividad Xi>= 0 confían todos los valores posibles.
3. El espacio encerrado por las restricciones restantes se determinan sustituyendo en primer término <= por (=) para cada restricción, con lo cual se produce la ecuación de una línea recta.
4. trazar cada línea recta en el plano y la región en cual se encuentra cada restricción cuando se considera la desigualdad lo indica la dirección de la flecha situada sobre la línea recta asociada.
5. Cada punto contenido o situado en la frontera del espacio de soluciones satisfacen todas las restricciones y por consiguiente, representa un punto factible.
6. Aunque hay un número infinito de puntos factibles en el espacio de soluciones, la solución óptima puede determinarse al observar la dirección en la cual aumenta la función objetivo.
7. Las líneas paralelas que representan la función objetivo se trazan mediante la asignación de valores arbitrarios a fin de determinar la pendiente y la dirección en la cual crece o decrece el valor de la función objetivo.
Ejemplo.
Maximizar Z = 3X1 + 2X2
restricciones: X1 + 2X2 <=6 (1)
2X1 + X2 <=8 (2)
-X1 + X2 <=1 (3)
X2 <= 2 (4)
X1 >= 0 (5)
X2 >= 0 (6)

Convirtiendo las restricciones a igualdad y representándolas gráficamente se tiene:
X1 + 2X2 = 6 (1)
2X1 + X2 = 8 (2)
-X1 + X2 = 1 (3)
X2 = 2 (4)
X1 = 0 (5)
X2 = 0 (6)

Figura 1 Espacio de solución presentada con WinQsb


Figura 2 Determinación de solución

1.4 Método simplex
En la solución gráfica observamos que la solución óptima está asociada siempre con un punto extremo del espacio de soluciones. El método simplex está basado fundamentalmente en este concepto.
Careciendo de la ventaja visual asociada con la representación gráfica del espacio de soluciones, el método simplex emplea un proceso iterativo que principia en un punto extremo factible, normalmente el origen, y se desplaza sistemáticamente de un punto extremo factible a otro, hasta que se llega por último al punto óptimo.
Existen reglas que rigen la selección del siguiente punto extremo del método simplex:
1. El siguiente punto extremo debe ser adyacente al actual.
2. La solución no puede regresar nunca a un punto extremo considerado con la anterioridad.
El algoritmo simplex da inicio en el origen, que suele llamarse solución inicial. Después se desplaza a un punto extremo adyacente. La elección específica de uno a otro punto depende de los coeficientes de la función objetivo hasta encontrar el punto óptimo.
Al aplicar la condición de optimidad a la tabla inicial seleccionamos a Xi como la variable que entra. En este punto la variable que sale debe ser una de las variables artificiales.
Los pasos del algoritmo simplex son (10):
1. Determinar una solución básica factible inicial.
2. Prueba de optimidad: determinar si la solución básica factible inicial es óptima y sólo si todos los coeficientes de la ecuación son no negativos ( >= 0 ). Si es así, el proceso termina; de otra manera se lleva a cabo otra interacción para obtener la nueva solución básica factible inicial.
3. Condición de factibilidad.- Para todos los problemas de maximización y minimización, variable que sale es la variable básica que tiene la razón más pequeña (positiva). Una coincidencia se anula arbitrariamente.
4. Seleccionar las variables de holgura como las variables básicas de inicio.
5. Selecciona una variable que entra de entre las variables no básicas actuales que, cuando se incrementan arriba de cero, pueden mejorar el valor de la función objetivo. Si no existe la solución básica es la óptima, si existe pasar al paso siguiente.
6. Realizar el paso iterativo.
a) Se determina la variable básica entrante mediante la elección de la variable con el coeficiente negativo que tiene el valor mayor valor absoluto en la ecuación. Se enmarca la columna correspondiente a este coeficiente y se le da el nombre de columna pivote.
b) Se determina la variable básica que sale; para esta, se toma cada coeficiente positivo (>0) de la columna enmarcada, se divide el lado derecho de cada renglón entre estos coeficientes, se identifica la ecuación con el menor cociente y se selecciona la variable básica para esta ecuación.
c) Se determina la nueva solución básica factible construyendo una nueva tabla en la forma apropiada de eliminación de Gauss, abajo de la que se tiene. Para cambiar el coeficiente de la nueva variable básica en el renglón pivote a 1, se divide todo el renglón entre el número pivote, entonces
Renglón pivote nuevo = renglón pivote antiguo
número pivote
Para completar la primera iteración es necesario seguir usando la eliminación de Gauss para obtener coeficientes de 0 para la nueva variable básica Xj en los otros renglones, para realizar este cambio se utiliza la siguiente fórmula:
Renglón nuevo = renglón antiguo - ( coeficiente de la columna pivote X renglón pivote nuevo)
Cuando el coeficiente es negativo se utiliza la fórmula:
Renglón nuevo = renglón antiguo + (coeficiente de la columna pivote X renglón pivote nuevo)
TABLA SIMPLEX
como se capturaría la solución básica factible inicial en el siguiente ejemplo:
Sea:
Maximizar Z = 2X1+4X2
sujeto a:
2X1+ X2<= 230
X1+ 2X2<= 250
X2<= 120
todas las X1,X2>=0
BASE
Z
X1
X2
S1
S2
S3
SOLUCIÓN
RAZÓN
Z
0
-2
-4
0
0
0
0
0
S1
0
2
1
1
0
0
230
230/1
S2
0
1
2
0
1
0
250
250/2
S3
0
0
1
0
0
1
120
120/1
Seleccione la variable que entra y la variable que sale de la base:
Entra X2 y sale S3, se desarrolla la nueva tabla solución y se continua el proceso iterativo hasta encontrar la solución optima si es que está existe.
Tabla Óptima:
BASE
Z
X1
X2
S1
S2
S3
SOLUCIÓN
RAZÓN
Z
0
0
0
0
2
0
500
S1
0
0
0
1
-2
3
90
X1
0
1
0
0
1
-2
10
X2
0
0
1
0
0
1
120
Solución: Z = $500
fabricando
X1=10
X2=120
Sobrante de
S1 = 90
Tipo de solución: Optima Múltiple


Conceptos fundamentales
Programación lineal y método simplex:

Una vez se tiene un concepto general de lo que es la programación lineal, es importante conocer la forma de actuación particular de los algoritmos que resuelven programas lineales. De entre todos los algoritmos destaca por su importancia histórica y práctica el método simplex. Dicho método fue desarrollado por Dantzig en 1947, alcanzando un éxito inusitado en las décadas posteriores con el desarrollo de los computadores. El conocimiento básico de dicho método ayuda a la comprensión de las diferentes formas de resolución de programas lineales. Dicho método puede ser estudiado en alguno de los manuales que se presentan a continuación: Hillier y Liebermann (2001) (Capítulos 4 y 5) o bien Winston (1994) (Capítulos 3 y 4). Por otra parte, el estudio de aplicaciones de la Programación Lineal es exhaustivo en los textos de Hillier, Hillier y Liebermann (2000); Eppen et al.(1998); o bien de Anderson, Sweeney y Williams (2001).


Clasificación de las aplicaciones de PL:

La Programación Lineal presenta un gran número de aplicaciones en multitud de ámbitos empresariales, industriales, de gestión y en general, de toma de decisiones. En este mathblock tan sólo se hace una exposición sucinta de las aplicaciones más clásicas. Sin embargo, se aconseja al lector la consulta de los documentos de Internet siguientes:



En el primero se describen los problemas clásicos de mezclas y de la dieta, mientras en el segundo se desarrolla un elenco de aplicaciones que sirven muy bien para completar los casos aquí descritos. En otro orden de cosas, en el presente mathblock se van a desarrollar campos de aplicación de la programación lineal en los ámbitos siguientes: Marketing, Producción, Asignación de Tareas, Finanzas, Logística y Mezclas. Esta clasificación no es exhaustiva: existen otros muchos campos de aplicación de la Programación Lineal que aquí no aparecen citados, todos ellos relacionados con tomas de decisiones operativas y tácticas en la gestión empresarial. En algún caso, también aparecen aplicaciones en tomas de decisiones estratégicas.

1 comentario: