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

Introducción

Estructura del modelo matemático

Componentes

• Variables de decisión ${\underline {x}}$.
• Función objetivo$f({\underline {x}})$.
• Restricciones $g({\underline {x}})$.

La forma típica es

$[Max|Min]f({\underline {x}})$

Sujeto a:

$g({\underline {x}})\leq {\underline {b}}$ ;restricciones de desigualdad

$h({\underline {x}})={\underline {d}}$ ;restricciones de igualdad

${\underline {L}}=\leq {\underline {x}}\leq {\underline {U}}$ ;restricciones de cota

Definiciones

Punto factible

Es todo punto ${\underline {x}}$ que verifica todas las restricciones del modelo.

Punto no factible

Es todo punto ${\underline {x}}$ que no verifica alguna de las restricciones del modelo.

Solución óptima del modelo

Es todo punto factible ${\underline {x}}^{*}$ que brinda el mejor valor de función objetivo $f({\underline {x}}^{*})$.

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

${\frac {1}{x}}\leq 2\rightarrow 1\leq 2x$

Un problema lineal viene de la forma

$[Max|Min]c_{1}x_{1}+c_{2}x_{2}+\cdots +c_{n}x_{n}$

Sujeto a:

$a_{11}x_{1}+a_{12}x_{2}+\cdots +a_{1n}x_{n}[\leq |=|\geq ]b_{1}$

$a_{21}x_{1}+a_{22}x_{2}+\cdots +a_{2n}x_{n}[\leq |=|\geq ]b_{2}$

$\ldots$

$a_{m1}x_{1}+a_{m2}x_{2}+\cdots +a_{mn}x_{n}[\leq |=|\geq ]b_{m}$

Donde:

• ${\underline {x}}$ es el vector de variables de decisión.
• ${\underline {c}}$ es el vector de costos o coeficientes de la función objetivo.
• ${\underline {\underline {A}}}$ es la matriz de recursos o coeficientes tecnológicos, es decir, las unidades requeridas para realizar una actividad.
• ${\underline {b}}$ es el vector de disponibilidades.

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 ($b_{i}$) son no negativos.

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

Caso	Solución
Una variable $x_{j}$ es SRS[1]	Utilizar $x_{j}=x_{j}^{+}-x_{j}^{-}$, y escribir en modelo en función de estas dos variables no negativas
Restricciones de $\geq$	Restar una variable de holgura al lado izquierdo, que asume el valor de la diferencia entre ambos lados.
Restricciones de $\leq$	Sumar una variable de holgura al lado izquierdo, que asume el valor de la diferencia entre ambos lados.
$b_{i}<0$	Multiplicar miembro a miembro por -1
Restricciones de valor absoluto	Deben reemplazarse por dos restricciones, una de $\leq$ y una de $\geq$, y a cada una agregarle la variable de holgura correspondiente.
F.O. con término constante	$Opt(A+f({\underline {x}}))=A+Opt(f({\underline {x}}))$

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.

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

Caso	Solución
Una variable $x_{j}$ es SRS[3]	Utilizar $x_{j}=x_{j}^{+}-x_{j}^{-}$, y escribir en modelo en función de estas dos variables no negativas
Restricciones de $\geq$	Multiplicar miembro a miembro por -1.
Restricciones de = o de valor absoluto	Deben reemplazarse por dos restricciones, una de $\leq$ y una de $\geq$, y multiplicar miembro a miembro por -1 la de $\geq$.
F.O. con término constante	$Opt(A+f({\underline {x}}))=A+Opt(f({\underline {x}}))$
Problema de minimización	Minimizar $f$ es equivalente a maximizar $-f$.

Determinación algebraica de puntos extremos

Archivo:Ejemplo region simplex1.svg

Para un punto $p_{1}$ que está bajo la restricción 1, la variable de holgura s1 correspondiente a esa restricción, será mayor que cero. Para un punto $p_{2}$ 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$:

${\frac {n!}{(n-g)!g!}}={\frac {n!}{m!g!}}$

---

^  Sin restricción de signo.

^  Utilizada para análisis de sensibilidad.