Tema 2 - Programación Lineal

Introducción

🔖
El objetivo es la optimización, de entre un conjuto de soluciones, elegir la mejor
💡
El término Programación Lineal se utiliza como sinónimo de Optimización Lineal.
Con el término programación nos referimos a planificación, no a la programación informática

Modelos de programación lineal

💡
El objetivo de esta sección es aprender a formular problemas de Programación Lineal (PL) también llamada Optimización Lineal
⚠️
En esta sección solo se plantearán los problemas, pero no se resolverán. La resolución se verán en la siguiente sección
📖
Tipos de modelos para resolver problemas de PL
  • Modelos de asignación de recursos → Repartimos un recurso entre diferentes actividades
  • Modelos de mezclas
  • Modelos de planificación de operaciones
  • Modelos de gestión de personal
  • Modelos temporales (multiperiodo)
💡
Soluciones óptimas
En estos ejercicios podemos encontrar que se usa es símbolo * como superíndice en las funciones y variables para indicar que el valor que estamos usando es una solución óptima
  • Ejemplo de variable con un valor de una solución óptima: x2∗=10x^*_2 = 10
  • Ejemplo de función con valores de la solución óptima: z∗=1⋅1+2⋅2+3⋅3=14z^* = 1·1 + 2·2 + 3·3 = 14(los valores utilizados son para el ejemplo)
💡
Un problema de optimización es un PL si tanto su función z(x)z(x) como sus restricciones son lineales
💡
Un PL puede tener restricciones tanto de igualdad como de desigualdad
 

Métodos para formular un PL

1️⃣
Escribir los datos en lenguaje natural
  • Escribir todos los datos a las mismas unidades
  • Escribir las condiciones que debe satisfacer la solución
2️⃣
Objetivo
  • Escribir el objetivo en lenguaje natural
  • Especificar si en un problema de minimización o maximización
3️⃣
Operaciones
  1. Definir las variables de decisión (con unidades) y el dominio de estas
  1. Familiarizarse con el problema: Buscar un vector solución (x^)(\widehat x)
  1. Escribir en leguaje matemático
    1. La función objetivo z(x)z(x) que queremos maximizar o minimizar
    2. Plasmar las restricciones como ecuaciones o inecuaciones
    3. En cada restricción, las unidades de ambos lados deben coincidir
    4. Verificar x^\widehat x cumple las restricciones y si z(x^)=z^z(\widehat x) = \widehat z
4️⃣
Solución
Resumiremos en un PL lo anterior. 💡 La mayoría de veces deberemos incluir restricciones de negatividad (x≥0)(x \geq 0)

Introducción a las técnicas de resolución

Resolucion geometrica de un problema PL.

📖
Este método consiste en dibujar la curva de nivel de la función objetivo sobre la región factible para después determinar si el punto escogido es óptimo
📚
Cómo dibujar las curvas de nivel

Problema PL en formato estandar

Teoría

⚙️
Método Simplex
El método simplex consiste en el siguiente algoritmo:
  1. Tomar un punto del conjunto de puntos factibles, y calcularlo.
  1. A Calculamos los valores de los vértices adyacentes.
    1. Si alguno de ellos mejora la solución del punto inicial, entonces repetimos el proceso empezando desde ese punto.
    2. Si ninguno lo mejora, hemos encontrado el punto óptimo
⚫
Tipos de puntos en PL
  • Infactible → Incumple alguna de las inecuaciones
  • Factible → Cumple todas las inecuaciones
    • Frontera → El punto se encuentra contenido en una de las rectas de alguna de las inecuaciones
    • Interior → El punto no se encuentra sobre ninguna de las rectas de las inecuaciones
    • Optimo → El punto que da el mejor resultado en la función objetivo
👥
Tipos de conjuntos de un PL
  • Conjunto factible
    • El interior del conjunto factible
    • Frontera del conjunto factible
      • El conjunto óptimo
🏷️
Propiedades de los puntos óptimos
  • Todo punto óptimo está en la frontera
  • Un PL puede no tener puntos óptimos, tener uno o tener infinitos
    • 00 → Cuando el problema es infactible o no acotado
    • 11 → El punto óptimo está en el punto de corte entre dos rectas (vertice)
    • ∞\infin → Los puntos óptimos son todos los puntos contenidos en una recta

¿Qué es el formato estándar?

🔖
El formato estaándar consiste principalemente en convertir todas las inecuaciones a inecuaciones de ≤\leq ó <<, esta operación de cambiar el sentido de la inecuación implica que debemos multiplicar cada lado por −1-1
Ejm.: x+y≥15→−(x+y)≤−15\small {x + y \geq 15 \rightarrow -(x+y) \leq -15}

Variables binarias

0️⃣
Las variables binarias se usan como cualquier otra variable, pero se debe especificar que estas solo puede tomar un valor 00 o 11
Ejemplo
ai={0Si no fabricamos el producto i1Si fabricamos el producto ia_i = \begin{cases} 0 && \text{Si no fabricamos el producto } i \\ 1 && \text{Si fabricamos el producto } i \end{cases}

Postoptimización

💡
La idea detrás de la postoptimización, reside en que la mayoría de datos que calculamos con un problema de PL no son más que estimaciones o predicciones. Por ello, debemos añadir en nuestras funciones un manera de poder recoger este posible error en el cálculo respecto del valor real.
⚙
Variables de holgura
Estas son variables que introduciremos en las restricciones. Estas representan el valor necesario para compensar las variaciónes desconocidas e impredecibles de los datos y permitir un cierto margen de error donde se sigue cumpliendo la restricción
  • Cuando estas tienen un valor diferente de 0, no estamos eligiendo la solución más óptima
© 2024 Notion Lovers.Made with ❤️ by Notion Lovers