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.

Introducción[editar]

Estructura del modelo matemático[editar]

Componentes[editar]

  • Variables de decisión .
  • Función objetivo.
  • Restricciones .

La forma típica es

Sujeto a:

;restricciones de desigualdad

;restricciones de igualdad

;restricciones de cota

Definiciones[editar]

Punto factible[editar]

Es todo punto que verifica todas las restricciones del modelo.

Punto no factible[editar]

Es todo punto que no verifica alguna de las restricciones del modelo.

Solución óptima del modelo[editar]

Es todo punto factible que brinda el mejor valor de función objetivo .

Programación lineal[editar]

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

Sujeto a:

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.

Forma estándar de un problema lineal[editar]

En la forma estándar:

  • Todas las variables son no-negativas.
  • Todas las restricciones son de igualdad.
  • Los términos independientes () son no negativos.

Reglas para convertir un problema lineal a la forma estándar[editar]

Caso Solución
Una variable 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.
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

Forma canónica de un problema lineal[2][editar]

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.

Reglas para convertir un problema lineal a la forma canónica[editar]

Caso Solución
Una variable 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 es equivalente a maximizar .

Determinación algebraica de puntos extremos[editar]

Archivo:Ejemplo region simplex1.svg

Para un punto que está bajo la restricción 1, la variable de holgura s1 correspondiente a esa restricción, será mayor que cero. Para un punto 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 ecuaciones y variables tiene grados de libertad, , lo que indica que si se fija el valor de 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 elementos tomados de a :



^  Sin restricción de signo.

^  Utilizada para análisis de sensibilidad.