1. UNIDAD 1: PROGRAMACIÓN LINEAL
1.1. 1.1 Definición, desarrollo y tipos de modelos de investigación de operaciones.
1.1.1. Actualmente la administración está funcionando en un ambiente de negocios que está sometido a muchos más cambios, los ciclos de vida de los productos se hacen más cortos, además de la nueva tecnología y la internacionalización creciente.
1.1.1.1. Las raíces de la investigación de operaciones se remonta a cuando se hicieron los primeros intentos para emplear el método científico en la administración de una empresa. Sin embargo, el inicio de esta disciplina se atribuye a los servicios militares prestados a principios de la segunda guerra mundial.
1.1.2. Tipos de Modelos de Investigación de Operaciones.
1.1.2.1. 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.
1.1.2.2. Modelo de Simulación: Los modelos de simulación difieren de los matemáticos en que las relación 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.
1.1.2.3. 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.
1.1.2.4. 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 deterministicos. 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 probabilistas (o estocásticos), alguno de los datos importantes se consideran inciertos, aunque debe especificarse la probabilidad de tales datos.
1.2. 1.2 Formulación de modelos.
1.2.1. Una vez definido el problema del tomador de decisiones, la siguiente etapa consiste en reformularlo de manera conveniente para su análisis. La forma convencional en que la investigación de operaciones realiza esto es construyendo un modelo matemático que represente la esencia del problema. El modelo matemático puede expresarse entonces como el problema de elegir los valores de las variables de decisión de manera que se maximice la función objetivo, sujeta a las restricciones dadas. Un modelo de este tipo, y algunas variaciones menores sobre él, tipifican los modelos analizados en investigación de operaciones.
1.2.2. Aplicación: La Oficina responsable del control del agua y los servicios públicos del Gobierno de Holanda, el Rijkswaterstatt, concesionó un importante estudio de Investigación de Operaciones para guiarlo en el desarrollo de una importante política de administración del agua. La nueva política ahorro cientos de millones de dólares en gastos de inversión y redujo el daño agrícola en alrededor de 15 millones de dólares anuales, al mismo tiempo que disminuyo la contaminación térmica y debida a las algas. En lugar de formular un modelo matemático, este estudio de Investigación de Operaciones desarrolló un sistema integrado y comprensible de ¡50 modelos! Mas aún, para alguno de los modelos, se desarrollan versiones sencillas y complejas. La versión sencilla se usó para adquirir una visión básica incluyendo el análisis de trueques. La versión compleja se usó después en las corridas finales del análisis o cuando se deseaba mayor exactitud o más detalles en los resultados. El estudio completo de Investigación de Operaciones involucró directamente a mas de 125 personas – año de esfuerzo (mas de un tercio de ellas en la recolección de datos), creó varias docenas de programas de computación y estructuró una enorme cantidad de datos
1.3. 1.3 Método gráfico.
1.3.1. 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.
1.3.1.1. El método Simplex se basa en la siguiente propiedad: si la función objetivo, f, no toma su valor máximo en el vértice A, entonces hay una arista que parte de A, a lo largo de la cual f aumenta. Deberá tenerse en cuenta que este método sólo trabaja para restricciones que tengan un tipo de desigualdad “≤” y coeficientes independientes mayores o iguales a 0, y habrá que estandarizar las mismas para el algoritmo. En caso de que después de éste proceso, aparezcan (o no varíen) restricciones del tipo “≥” o “=” habrá que emplear otros métodos, siendo el más común el método de las Dos Fases.
1.3.1.1.1. Construcción de la primera tabla: En la primera columna de la tabla aparecerá lo que llamaremos base, en la segunda el coeficiente que tiene en la función objetivo cada variable que aparece en la base (llamaremos a esta columna Cb), en la tercera el término independiente de cada restricción (P0), y a partir de ésta columna aparecerán cada una de las variables de la función objetivo (Pi). Para tener una visión más clara de la tabla, incluiremos una fila en la que pondremos cada uno de los nombres de las columnas. Sobre ésta tabla que tenemos incluiremos dos nuevas filas: una que será la que liderará la tabla donde aparecerán las constantes de los coeficientes de la función objetivo, y otra que será la última fila, donde tomará valor la función objetivo. Nuestra tabla final tendrá tantas filas como restricciones.
1.3.1.1.2. Los valores de la fila Z se obtienen de la siguiente forma: El valor Z0 será el de sustituir Cim en la función objetivo (y cero si no aparece en la base). El resto de columnas se obtiene restando a este valor el del coeficiente que aparece en la primera fila de la tabla.
1.3.1.1.3. Se observará al realizar el método Simplex, que en esta primera tabla, en la base estarán las variables de holgura.
1.3.1.1.4. – Condición de parada: Comprobaremos si debemos de dar una nueva iteración o no, que lo sabremos si en la fila Z aparece algún valor negativo. Si no aparece ninguno, es que hemos llegado a la solución óptima del problema.
1.3.1.1.5. – Elección de la variable que entra: Si no se ha dado la condición de parada, debemos seleccionar una variable para que entre en la base en la siguiente tabla. Para ello nos fijamos en los valores estrictamente negativos de la fila Z, y el menor de ellos será el que nos de la variable entrante.
1.3.1.1.6. – Elección de la variable que sale: Una vez obtenida la variable entrante, obtendremos la variable que sale, sin más que seleccionar aquella fila cuyo cociente P0/Pj sea el menor de los estrictamente positivos (teniendo en cuenta que sólo se hará cuando Pj sea mayor de 0). La intersección entre la columna entrante y la fila saliente nos determinará el elemento pivote.
1.3.1.1.7. – Actualización de la tabla: Las filas correspondientes a la función objetivo y a los títulos permanecerán inalterados en la nueva tabla. El resto deberá calcularse de dos formas diferentes:Construcción de la primera tabla: En la primera columna de la tabla aparecerá lo que llamaremos base, en la segunda el coeficiente que tiene en la función objetivo cada variable que aparece en la base (llamaremos a esta columna Cb), en la tercera el término independiente de cada restricción (P0), y a partir de ésta columna aparecerán cada una de las variables de la función objetivo (Pi). Para tener una visión más clara de la tabla, incluiremos una fila en la que pondremos cada uno de los nombres de las columnas. Sobre ésta tabla que tenemos incluiremos dos nuevas filas: una que será la que liderará la tabla donde aparecerán las constantes de los coeficientes de la función objetivo, y otra que será la última fila, donde tomará valor la función objetivo. Nuestra tabla final tendrá tantas filas como restricciones.Los valores de la fila Z se obtienen de la siguiente forma: El valor Z0 será el de sustituir Cim en la función objetivo (y cero si no aparece en la base). El resto de columnas se obtiene restando a este valor el del coeficiente que aparece en la primera fila de la tabla.Se observará al realizar el método Simplex, que en esta primera tabla, en la base estarán las variables de holgura.– Condición de parada: Comprobaremos si debemos de dar una nueva iteración o no, que lo sabremos si en la fila Z aparece algún valor negativo. Si no aparece ninguno, es que hemos llegado a la solución óptima del problema.– Elección de la variable que entra: Si no se ha dado la condición de parada, debemos seleccionar una variable para que entre en la base en la siguiente tabla. Para ello nos fijamos en los valores estrictamente negativos de la fila Z, y el menor de ellos será el que nos de la variable entrante.– Elección de la variable que sale: Una vez obtenida la variable entrante, obtendremos la variable que sale, sin más que seleccionar aquella fila cuyo cociente P0/Pj sea el menor de los estrictamente positivos (teniendo en cuenta que sólo se hará cuando Pj sea mayor de 0). La intersección entre la columna entrante y la fila saliente nos determinará el elemento pivote.– Actualización de la tabla: Las filas correspondientes a la función objetivo y a los títulos permanecerán inalterados en la nueva tabla. El resto deberá calcularse de dos formas diferentes:
1.3.2. Los pasos necesarios para realizar el método son siete:
1.3.2.1. 1. graficar las soluciones factibles, o el espacio de soluciones (factible), que satisfagan todas las restricciones en forma simultánea.
1.3.2.2. 2. Las restricciones de no negatividad Xi>= 0 confían todos los valores posibles.
1.3.2.3. 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.
1.3.2.4. 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.
1.3.2.5. 5. Cada punto contenido o situado en la frontera del espacio de soluciones satisfacen todas las restricciones y por consiguiente, representa un punto factible.
1.3.2.6. 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.
1.3.2.7. 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.
1.4. 1.4 Fundamentos del método simplex.
1.4.1. El Método Simplex, esta diseñado para ser aplicado únicamente hasta que el problema se encuentre en la forma Estándar. La forma Canónica es también de bastante utilidad, especialmente en explorar la relación de Dualidad. Un problema de P.L. está en la forma canónica si para un problema de: Maximización, las variables son no-negativas y las restricciones son del tipo ≤ Minimización, las variables son no-negativas y las restricciones son del tipo ≥ Considere el siguiente problema de P.L. en forma canónica
1.4.1.1. Donde : A= Matriz de coeficientes de las variables en el sistema de ecuaciones de (mxn) aij= coeficiente de la variable j en la restricción i x=Vector solución (nx1) xj= Variable j bi= Lado derecho de la restricción i ( Limitación i ) C=Vector de costos o utilidades (1xn) cj= Coeficiente de la variable j en la función objetivo
1.4.1.2. Los motivos para que un problema no este en la forma estándar son: 1. Algunas restricciones son desigualdades 2. Algunas bi son negativas 3. Algunas variables de decisión xj pueden ser negativas
1.4.2. El método Simplex es un procedimiento iterativo que permite ir mejorando la solución a cada paso. El proceso concluye cuando no es posible seguir mejorando más dicha solución. Partiendo del valor de la función objetivo en un vértice cualquiera, el método consiste en buscar sucesivamente otro vértice que mejore al anterior. La búsqueda se hace siempre a través de los lados del polígono (o de las aristas del poliedro, si el número de variables es mayor). Cómo el número de vértices (y de aristas) es finito, siempre se podrá encontrar la solución.
1.4.2.1. El método Simplex se basa en la siguiente propiedad: si la función objetivo, f, no toma su valor máximo en el vértice A, entonces hay una arista que parte de A, a lo largo de la cual f aumenta. Deberá tenerse en cuenta que este método sólo trabaja para restricciones que tengan un tipo de desigualdad “≤” y coeficientes independientes mayores o iguales a 0, y habrá que estandarizar las mismas para el algoritmo. En caso de que después de éste proceso, aparezcan (o no varíen) restricciones del tipo “≥” o “=” habrá que emplear otros métodos, siendo el más común el método de las Dos Fases.
1.5. 1.5 Aplicaciones diversas de programación lineal.
1.5.1. Un problema de programación lineal puede ser establecido en diferentes formas equivalentes a través de manipulaciones apropiadas. Dos formas en particular serán de bastante utilidad. Estas son las formas Estándar y Canónica. Un problema lineal se dice que esta en la forma estándar si ;
1.5.1.1. a) Todas las restricciones son igualdades
1.5.1.2. b) Todas las variables son no-negativas
1.5.1.3. c) Las limitaciones ( lado derecho de la restricción) son positivas