investigación de operaciones unidad 3

Investigacion de operaciones I 

Unidad 3

INDICE

3.1. Teoría primal-dual

3.2. Formulación del problema dual.

3.3. Relación primal-dual.

3.4. Dual-Simplex

3.5. Análisis de sensibilidad: cambio en el vector recursos (boj) y sus límites, cambio en el vector (Ci) y sus límites, adición de una variable (Xi), cambio en coeficientes tecnológicos (aj), Adición de una nueva restricción

3.6. Interpretación del análisis de sensibilidad

3.7. Uso de software

INTRODUCCION

Encontrar el óptimo de un problema de optimización, es solo una parte del proceso

De solución. Muchas veces nos interesara saber cómo varia la solución si varıa

Alguno de los parámetros del problema que frecuentemente se asumen como determinísticos, pero que tienen un carácter intrínsecamente aleatorio. Más especialmente nos interesara saber paraqué rango de los parámetros que determinan el problema sigue siendo válida la solución encontrada.

UNIDAD 3 DUALIDAD Y ANÁLISIS DE SENSIBILIDAD

La asignación de probabilidades a los eventos es una tarea difícil que muchos gerentes pueden mostrarse difícil a hacer, por lo menos con cierto grado de

Exactitud. En algunos casos prefieren decir “creo que la probabilidad de que este evento ocurra está entre 0.5 y 0.7”. Bajo estas circunstancias, como en cualquier aspecto de decisión gerencial, es útil realizar un análisis de sensibilidad para determinar cómo afecta a la decisión la asignación de probabilidades. El análisis de sensibilidad concierne el estudio de posibles cambios en la solución óptima disponible como resultado de hacer cambios en el modelo original.

Definiciones generales del Análisis de sensibilidad Efecto neto.- Es la ganancia o pérdida por unidad adicional de una variable que entra a la base. El efecto neto de una variable básica siempre será cero.

Cambios en los coeficientes de la función objetivo.

El cambio de una variable se interpretaría, por ejemplo, como en incremento en el precio de un producto para un objetivo de maximización, o como la disminución en el costo de una materia prima para un objetivo de minimización. Finalmente, se estudiara por separado si la modificación es para una variable no-básica o para una básica, ya que las consecuencias en cada caso son muy diferentes.

Cambios en el coeficiente Objetivo de una variable No-básica.

Es importante mencionar que una variación en el coeficiente de una variable no-básica, no necesariamente conlleva a una infracción no mejorada a la solución óptima actual, aunque en ciertas ocasiones si lo haga.

3.1. TEORÍA PRIMA-DUAL.

El problema dual se define sistemáticamente a partir del modelo de PL primal (u original). Los dos problemas están estrechamente relacionados en el sentido de que la solución óptima de uno proporciona automáticamente la solución óptima al otro. En la mayoría de los tratamientos de PL, el dual se define para varias formas del primal según el sentido de la optimización (maximización o minimización), los tipos

De restricciones, y el signo de las variables (no negativas o restrictivas).Requiere expresar el problema primal en la forma de ecuación (todas las restricciones son ecuaciones con lado derecho no negativo, y todas las variables son negativas). Este requerimiento es consistente, de ahí que cual es quiere resultados obtenidos a partir de la solución óptima primales se aplica diferente al problema dual asociado. Las ideas clave para construir el dual a partir del primal se resumen como sigue: 1. Asigne un variable dual por cada restricción primal.2. Construya una restricción dual por cada variable primal.3. Los coeficientes de restricción y el coeficiente objetivo de la variable primala j-pésima definen respectivamente los lados izquierdos y derecho de la restricción dual j-ésima.4. Los coeficientes objetivo duales son iguales a los lados derechos delas ecuaciones de restricción primales.5. Las reglas rigen el sentido de la optimización de las desigualdades y los signos de las variables en el dual.

3.2. FORMULACIÓN DEL PROBLEMA DUAL.

Hemos visto como la programación lineal puede ser usada para resolver una extensa variedad de problemas propios de los negocios, ya sea para maximizar utilidades o minimizar costos. Las variables de decisión en tales problemas fueron, por ejemplo, el número de productos a producir, la cantidad de pesos a emplear, etc. En cada caso la solución óptima no explicó cómo podrían ser asignados los recursos (ejemplo: materia prima, capacidad de las máquinas, el dinero, etc.) para obtener un objetivo establecido. En este capítulo veremos que a cada problema de programación lineal se le asocia otro problema de programación lineal, llamado el problema de programación dual. La solución óptima del problema de programación dual, proporciona la siguiente información respecto del problema de programación original:

1. La solución óptima del problema dual proporciona los precios en elmercado o los beneficios de los recursos escasos asignados en el problemaoriginal.2. La solución óptima del problema dual aporta la solución óptima del problema original y viceversa

3.3 DUALIDAD EN PROGRAMACION LINEAL (Relaciones primal-dual)

Asociado a cada problema lineal existe otro problema de programación linealdenominado

Problema dual (PD)

, que posee importantes propiedades y relaciones notables con respecto al problema lineal original, problema que para diferencia del dual se denomina entonces como

Problema primal (PP)

.Las relaciones las podemos enumerar como siguen: a) El problema dual tiene tantas variables como restricciones tiene el programaprimal.b) El problema dual tiene tantas restricciones como variables tiene el programaprimalc) Los coeficientes de la función objetivo del problema dual son los términos independientes de las restricciones o RHS del programa primad) Los términos independientes de las restricciones o RHS del dual son los coeficientes de la función objetivo del problema primal. E) La matriz de coeficientes técnicos del problema dual es la traspuesta de la matriz técnica del problema primal.

f) El sentido de las desigualdades de las restricciones del problema dual y el signo de las variables del mismo problema, dependen de la forma de que tenga el signo de las variables del problema primal y del sentido de las restricciones del mismo problema .g) Si el programa primal es un problema de maximización, el programa dual es un problema de minimización .h) El problema dual de un problema dual es el programa primal original. Los problemas duales simétricos son los que se obtienen de un problema primal

En forma canónica y „normalizada‟, es decir, cuando

Llevan asociadas desigualdades de la forma mayor o igual en los problemas de minimización, y desigualdades menores o iguales para los problemas de maximización .Por qué se plantea el programa dual? ¿Qué significado tiene su solución? ¿La solución del dual se puede obtener desde el primal? Por una parte permite resolver problemas lineales donde el número de restricciones es mayor que el número de variables. Gracias a los teoremas que expondremos a continuación la solución de unos delos problemas (primal o dual) nos proporciona de forma automática la solución del otro programa

La dualidad permite realizar importantes interpretaciones económicas de los problemas de programación lineal. La dualidad permite generar métodos como el método dual del simplex de gran importancia en el análisis de pos optimización y en la programación lineal para métrica.

Teoría del método simplex

Para poder aplicar el método simplex a un modelo de programación lineal es necesario que este se encuentre en su forma estándar.

La forma estándar.

Las características de la forma estándar son:

1.-Todas las restricciones son ecuaciones excepto para las restricciones de no negatividad que permanecen como desigualdades

.2.-Los elementos del lado derecho de cada ecuación son no negativos.

3.-Todas las variables son no negativas.

4.-la función objetivo es del tipo de Maximización o minimización.

Transformaciones elementales.

Transformaciones elementales.

1.-Las restricciones de desigualdad pueden cambiarse por ecuaciones introduciendo en el lado izquierdo de cada una de tales restricciones una variable no negativa. (Estas nuevas variables se conocen como variables de holgura o supera bit las cuales se sumaran si la2.-El signo del lado derecho (-) puede eliminarse multiplicando la ecuación por (-1) en caso de que sea necesario.

3.-Una restricción de desigualdad con su lado izquierdo en forma de valor absoluto puede cambiarse a dos desigualdades, la desigualdad contraria a la original se le antepone el signo negativo a su lado derecho.4.-Una variable que es irrestricta en signo (esto es positiva, negativa o cero) es equivalente a la diferencia entre dos variables no negativas por consiguiente si X es irrestricta en signo puede remplazarse por (X+-X-) donde Y X-  ambos lados por (-1)

.6.-Una ecuación puede ser remplazada por dos desigualdades en direcciones opuestas.

7.-La minimización de una función f(x), es

Matemáticamente equivalente a la maximización de la expresión negativa de esta función f(x), y viceversa.

El método simplex.

Podemos decir que es la determinación algebraica de los puntos extremos del espacio de soluciones factibles (método gráfico), partiendo de la forma estándar. En la cual tenemos un sistema con m ecuaciones y n incógnitas .La diferencia entre el número de ecuaciones y las incógnitas nos dan el número de variables que son iguales a cero en un punto extremo, las cuales son llamadas

Variables no básicas, y las variables restantes son llamadas básicas.

El método simplex inicia con un punto extremo o solución factible básica.

1.-La función objetivo se presenta como una ecuación y al pasarla a la tabla simplex cambian de signo los coeficientes de la función objetivo.

2.-Se coloca toda la información en una tabla.

3.-El siguiente paso es determinar una solución básica factible (punto extremo). El método simplex hace esto eligiendo una variable

No básica a la cual se le conoce como la variable que entra (se convertirá en básica) y una variable básica que se le conoce como la variable que sale (se convertirá en no básica). La que entra está determinada por la condición de optimizad y la que sale por la condición de factibilidad

4.-Condición de optimizad.- Dada la ecuación X

0 (función objetivo) expresada en función de las variables no básicas solamente, se elige la variable que entra en maximización como la variable no básica que tiene el mayor coeficiente negativo y en minimización como la variable no básica que tiene el mayor coeficiente positivo, en la ecuación X0. Un empate entre dos variable no básicas o más se rompe arbitrariamente. Cuando los coeficientes del lado izquierdo de la ecuación X

0 (Función objetivo) son no negativos (maximización) o no positivos (minimización) se ha llegado al punto óptimo.5.-Condición de factibilidad.-La variable que sale es la variable básica correspondiente al cociente más pequeño de los valores actuales de las variables básicas entre los coeficientes positivos de las restricciones de la variable que entra. Un empate puede romperse arbitrariamente.

3.5 ANALISIS DE SENSIBILIDAD

El análisis de sensibilidad busca determinar los efectos que se producen enla solución óptima al realizar cambios en cualquiera de los parámetros del modelode programación lineal planteado inicialmente. Entre los cambios que seinvestigan están: los cambios en los coeficientes de las variables enla función objetivo tanto para variables básicas como para las variablesno básicas, cambios en los recursos disponibles de las restricciones, variación delos coeficientes de utilización en las restricciones e introducción de unanueva restricción.

El objetivo principal del análisis de sensibilidad: es identificar el intervalo permisible de variación en los cuales las variables o parámetros pueden fluctuarsin que cambie la solución óptima. Sin embargo, así mismo se identificaaquellos parámetros sensibles, es decir, los parámetros cuyos valores no pueden cambiar sin que cambie la solución óptima. Los investigadores de operaciones tienden a prestar bastante atención a aquellos parámetros con holguras reducidas en cuanto a los cambios que pueden presentar, de forma que se vigile su comportamiento para realizar los ajustes adecuados según corresponda y evitar que estas fluctuaciones puedan desembocar en una solución no factible.

A modo general, cuando se realiza un análisis de sensibilidad auna solución óptima se debe verificar cada parámetro de formaindividual, dígase los coeficientes de la función objetivo y los límites de cada una de las restricciones. En ese sentido se plantea el siguiente procedimiento:

1.    Revisión del modelo: se realizan los cambios que se desean investigar en el modelo

2.    .2. Revisión de la tabla final Simplex: se aplica el criterio adecuado para determinar los cambios que resultan en la tabla final Simplex.

3.    3. Conversión a la forma apropiada de eliminación Gauss: se convierta la tabla en la forma apropiada para identificar y evaluar la solución básica actual, para lo cual se aplica la metodología de eliminación Gauss si es necesario.

4.    4. Prueba de factibilidad: se prueba la factibilidad de esta solución mediantela verificación de que todas las variables básicas de la columna del lado derecho aun tengan valores no negativos.

5.    . Prueba de optimalizad: se verifica si esta solución es óptima y factible, mediante la comprobación de que todos los coeficientes de las variables no básicas del reglón Z permanecen no negativos.6. Re-optimización: si esta solución no pasa una de las pruebas indicadas ellos puntos 4 y 5 anteriores, se procede a buscar la nueva solución óptima a partir de la tabla actual como tabla Simplex inicial, luego de aplicadas las conversiones de lugar, ya sea con el método Simplex o el Simplex Dual.

Aplicación del análisis de sensibilidad

Este análisis casi siempre comienza con la investigación de los cambios en los valores de las vi, la cantidad del recurso i (i = 1, 2,. . ., m) que se encuentra disponible para las actividades bajo consideración. La razón es que en general existe mayor flexibilidad al establecer y ajustar estos valores que los otros parámetros del modelo. La interpretación económica de las variables duales (las ya) como precios sombra es extremadamente útil para decidir cuáles son los cambios que se deben estudiar.

Primer caso:

Cambios en la bi (columna lado derecho)

Supongamos que los únicos cambios al modelo actual consisten en el cambio de uno o más de los parámetros vi

(i= 1, 2,. . ., m).

En este caso, los únicos cambios que resultan en la tabla simplex final se encuentran en la columna del lado derecho, por lo cual, se pueden omitir del procedimiento general tanto la conversión a la forma apropiada de eliminación de Gauss como la prueba optimalizad.

Segundo caso:

Cambio en los coeficientes de una variable no básica

Considere una variable específica

Dj (j Fija) que sea no básica en la solución óptima dada en la tabla simplex final. El caso 2a es aquel en el que los únicos cambios al modelo actual ocurren en uno o más de los coeficientes de esta variable, dj, a1j, a2j........, aj. Entonces, si dj y aj, denotan los nuevos valores de estos parámetros con Aj, (columna j de la matriz A) como el vector que contiene a aj, se tiene para el modelo revisado.

Tercer caso cambio en los coeficientes de una variable

Ahora suponga que la variable xj (con j fija) que se está estudiando es unavariable básica en la solución óptima que se muestra en la tabla simplex final. El caso 3 supone que los únicos cambios al modelo actual se hacen en los coeficientes de esta variable. El caso 3 difiere del 2a debido al requisito de que la tabla simplex debe estar en la forma apropiada de eliminación de Gauss. Esta forma permite que los elementos en la columna de una variable no básica tengan cualquier valor, así que no afecta en el caso 2a. Sin embargo, para el caso 3 la variable básica dj debe tener coeficiente 1 en su renglón de la tabla simplex y coeficiente 0 en todos los demás renglones (incluyendo el renglón 0). Por lo tanto, una vez que se han calculado los cambios en la columna dj de la tabla simplex final, es probable que sea necesario aplicar la eliminación de Gauss para restaurar la forma apropiada. Este paso, a su vez, quizá cambie los valores de la solución básica actual, y puede hacerla no factible o no óptima (con lo que puede ser necesario re optimizar).