Primer Parcial

Elementos básicos de la Programación Lineal

Lo más importante de la solución es poder abstraernos del problema y determinar los componentes principales

• Variable de decisión que tratamos de determinar
  • Es todo aquello que yo puedo modificar para así afectar el resultado final y optimizarlo.
  • Ej: $x_1,x_2$
• Función objetivo (meta) que tratamos de optimizar
  • Es el output, lo que yo quiero lograr optimizar.
  • $z=a_1{x}_1+a_2{x}_2$
• Restricciones que necesitamos satisfacer
  • Son reglas que yo le pongo a mis variables de decisión, que limitan mi espacio de posibilidades.

Enlace al original

Diferencia con la PLE con la PLNE

• Se pueden usar variables de decisión enteras y no enteras

  • Es PLE cuando tiene al menos una variable entera. También se la llama Programación Lineal Entera

• Los números de las variables de decisión siempre van a aumentar al próximo entero, nunca van a bajar.

• Redondear no siempre está bien, por eso es un análisis distinto a la Programación Lineal

Enlace al original

Tipos de restricciones

Una vez resuelto el problema, se pueden definir dos tipos de restricciones

• Binding (vinculante)
  • Restricciones que se cumplen de manera exacta en la solución óptima. Es decir la solución óptima satisface la igualdad de la restricción.
  • Cambiar cualquier valor dentro de la restricción alterará la solución óptima del problema.
  • Tiene un papel activo en la determinación de la solución óptima.
• Non binding (no vinculante)
  • Restricciones que no afectan la solución óptima del problema. La solución óptima puede encontrarse dentro de los límites impuestos por estar restricciones, sin satisfacer exactamente la igualdad.
  • Hay cierto margen para moverse dentro de estas restricciones sin cambiar la solución óptima.
  • No tienen un papel activo en la determinación de la solución óptima.

Enlace al original

Precio sombra

• El precio sombra de una restricción indica cuánto aumentaría o disminuiría el valor óptimo de la función objetivo si se relajara o se modificara ligeramente esa restricción en particular, mientras se mantienen las demás condiciones constantes.

restriccion.dual_value()

Enlace al original

Problemas de Asignación

Problemas de Asignación

Problema

• Tipos de problemas que se resuelven con programación lineal entera.
• Asignar un conjunto de personas o agentes, a un conjunto de ateas de la manera más eficiente posible, según algún criterio.

Modelo matemático

• **Variables dicotómicas o dummies **
  • Toman valores 0 o 1. Está activa o no?
  • $x_{ij}$ tomará el valor de 1 si el agente i es asignado a la tarea j
• Función objetivo
  • $\text{Maximizar o Minimizar }{\sum }_{i=1}^n{\sum }_{j=1}^m{c}_{ij}\cdot x_{ij}$
• Restricciones
  • Cada agente debe ser asignado a exactamente una tarea. ${\sum }_{i=1}^n{x}_{ij}=1$
  • Cada tarea debe ser realizada por exactamente un agente.${\sum }_{j=1}^m{x}_{ij}=1$

Enlace al original

Problema del Viajero

Problema del viajero

Se busca minimizar las distancias. El viajero debe salir de un origen, pasar por todos los nodos solo una vez y volver a su origen. Tiene aplicaciones en logística, la industria automotriz, para medidas de seguridad, entre otros usos. Las variables de decisión son las aristas del grafo. $x_{ij}$ donde x es 1 si hago el viaje de i a j y 0 en caso contrario la función objetivo será

${\sum }_{i,j}{x}_{ij}\cdot d_{ij}$ donde d es la distancia entre cada lugar las restricciones son que solo se puede llegar a un lugar una sola vez:

${\sum }_i{x}_{ij}=1\forall j\ne i$ y solo se puede salir de un lugar una sola vez ${\sum }_j{x}_{ji}=1\forall i\ne i$ Para eliminar el problema de subtours se resuelve creando variables de decisión adicionales $u_j$ que valdrá un numero entero correspondiente al orden de lugares a los que llego, es decir, el primer destino j al que llegue tendrá la variable $u_j=1$ Se arma la restricción $u_i-uj+n\cdot x_{ij}\le n-1$ donde n es la cantidad de nodos o destinos.

Enlace al original

Método de Montecarlo

Método de Montecarlo

El método de Montecarlo es una técnica matemática que permite obtener aproximaciones numéricas a problemas complejos mediante el uso de números aleatorios o datos aleatorios. Es útil para obtener simulaciones de la vida real y es aplicable para gestión de inventario, modelos de mercado financiero, epidemiología, simulación de circuitos, análisis de riesgo, etc.

Números Aleatorios

Son números generados de tal manera que no muestran ningún tipo de patrón o regularidad predecible, al menos en un rango limitado. Existen dos tipos:

• Números aleatorios verdaderos. Son generados de manera completamente aleatoria.
• Números aleatorios pseudoaleatorios. Son generados mediante algoritmos o fórmulas matemáticas.

La librería en python que se utilizará en el curso es random. Sus funciones básicas son:

random.random()
random.randint(a,b)
random.uniform(a,b)
random.choice(['a','b','c'])

Ejemplo - Estimación de Pi

Teniendo un plano cuadrado con un circulo dentro, si tengo el area del cuadrado y el area del circulo,

$\frac{Acirc}{Acuad}\approx \frac{CDCirc}{CDCuad}$

$\pi \approx \frac{CDCirc}{CDCuad}\cdot 4$

Así podremos llegar a estimar pi

Enlace al original