Manual del estudiante de Ingeniería en Sistemas de UTN/Investigación Operativa/Introducción
De Wikilibros, la colección de libros de texto de contenido libre.
Contenido |
[editar] Introducción
[editar] Estructura del modelo matemático
[editar] Componentes
- Variables de decisión
. - Función objetivo
. - Restricciones
.
La forma típica es
![[Max|Min] f(\underline{x})](http://upload.wikimedia.org/math/4/5/b/45bacf32c04df584dabd11d441674f65.png)
Sujeto a:
;restricciones de desigualdad
;restricciones de igualdad
;restricciones de cota
[editar] Definiciones
[editar] Punto factible
Es todo punto que verifica todas las restricciones del modelo.
[editar] Punto no factible
Es todo punto que no verifica alguna de las restricciones del modelo.
[editar] Solución óptima del modelo
Es todo punto factible 
que brinda el mejor valor de función objetivo 
.
[editar] Programación lineal
Un modelo es lineal si todas las funciones involucradas son lineales (sumatorias de múltiplos de variables de decisión). Algunas restricciones no lineales tienen una restricción lineal equivalente, como
Un problema lineal viene de la forma
![[Max|Min] c_1x_1+ c_2x_2 + \cdots + c_nx_n](http://upload.wikimedia.org/math/3/c/5/3c57ea97b4ef5cb3f41815987a596515.png)
Sujeto a:
![a_{11}x_1 + a_{12}x_2 + \cdots + a_{1n}x_n [\leq|=|\geq] b_1](http://upload.wikimedia.org/math/5/0/3/50360838a5b2debdce4adfdd694bda4c.png)
![a_{21}x_1 + a_{22}x_2 + \cdots + a_{2n}x_n [\leq|=|\geq] b_2](http://upload.wikimedia.org/math/5/6/2/5622cfeb52ba133edcdc9031be07ad6d.png)
![a_{m1}x_1 + a_{m2}x_2 + \cdots + a_{mn}x_n [\leq|=|\geq] b_m](http://upload.wikimedia.org/math/b/b/d/bbd3173ec547df878ae0c0bd6a56b557.png)
Donde:
- es el vector de variables de decisión.
es el vector de costos o coeficientes de la función objetivo.
es la matriz de recursos o coeficientes tecnológicos, es decir, las unidades requeridas para realizar una actividad.
es el vector de disponibilidades.
[editar] Forma estándar de un problema lineal
En la forma estándar:
- Todas las variables son no-negativas.
- Todas las restricciones son de igualdad.
- Los términos independientes (bi) son no negativos.
[editar] Reglas para convertir un problema lineal a la forma estándar
| Caso | Solución |
|---|---|
| Una variable xj es SRS[1] | Utilizar  , y escribir en modelo en función de estas dos variables no negativas |
Restricciones de  |
Restar una variable de holgura al lado izquierdo, que asume el valor de la diferencia entre ambos lados. |
Restricciones de  |
Sumar una variable de holgura al lado izquierdo, que asume el valor de la diferencia entre ambos lados. |
| bi < 0 | Multiplicar miembro a miembro por -1 |
| Restricciones de valor absoluto | Deben reemplazarse por dos restricciones, una de y una de , y a cada una agregarle la variable de holgura correspondiente. |
| F.O. con término constante |  |
[editar] Forma canónica de un problema lineal[2]
En la forma canónica:
- El problema debe ser de máximo.
- Todas las variables son no-negativas.
- Todas las restricciones son de menor o igual.
[editar] Reglas para convertir un problema lineal a la forma canónica
| Caso | Solución |
|---|---|
| Una variable xj es SRS[3] | Utilizar , y escribir en modelo en función de estas dos variables no negativas |
| Restricciones de |
Multiplicar miembro a miembro por -1. |
| Restricciones de = o de valor absoluto | Deben reemplazarse por dos restricciones, una de y una de , y multiplicar miembro a miembro por -1 la de . |
| F.O. con término constante | |
| Problema de minimización | Minimizar f es equivalente a maximizar − f. |
[editar] Determinación algebraica de puntos extremos
Para un punto p1 que está bajo la restricción 1, la variable de holgura s1 correspondiente a esa restricción, será mayor que cero. Para un punto p2 que está sobre la restricción 1, la variable de holgura s1 correspondiente a esa restricción, será menor que cero. Para un punto en la recta de la restricción 1, la variable de holgura s1 correspondiente a esa restricción, será igual a cero. Cada restricción tendrá una variable asociada, que al hacerse cero, indique que esa restricción se cumple en el límite. En una intersección, las restricciones que se intersecan se cumplen en el límite. Un sistema con m ecuaciones y n variables tiene g grados de libertad, g = n − m, lo que indica que si se fija el valor de g variables, podría encontrarse una solución al sistema. Fijando todas las g-uplas de valores en cero, se pueden encontrar las soluciones básicas del sistema en todas las intersecciones. El número total de soluciones básicas (factibles y no factibles), es decir, puntos extremos, está dado por las combinaciones de n elementos tomados de a g:
^ Sin restricción de signo.
^ Utilizada para análisis de sensibilidad.
