Manual del estudiante de Ingeniería en Sistemas de UTN/Investigación Operativa/Introducción

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.