Los modelos de programación lineal son herramientas matemáticas utilizadas para maximizar o minimizar una función objetivo lineal, sujeta a un conjunto de restricciones lineales. Estos modelos son extremadamente útiles en diversas áreas como economía, ingeniería, administración de operaciones, y más, donde se requiere la optimización de recursos limitados.

Componentes de un Modelo de Programación Lineal

Función Objetivo

Es la función que se desea optimizar, ya sea maximizar (por ejemplo, beneficios, eficiencia) o minimizar (por ejemplo, costos, tiempo).

\text{Maximizar o Minimizar: } z = c_1·x_1 + c_2·x_2 ...

Restricciones

Son las condiciones que las variables de decisión deben satisfacer. Pueden ser igualdades o desigualdades lineales que representan limitaciones físicas, financieras, o de otro tipo.

\max \text{ o } \min \quad z = \mathbf{c}^T \mathbf{x}

Variables de Decisión

Son las variables que el modelo ajustará para satisfacer las restricciones y optimizar la función objetivo. Estas variables deben ser no negativas en muchos contextos.

Uso de Modelos de Programación Lineal

Los modelos de programación lineal se usan para resolver problemas complejos mediante técnicas de solución eficientes como el método simplex. Estos modelos permiten tomar decisiones racionales y bien fundamentadas en situaciones donde los recursos son limitados.

Ejemplo de Problema de Examen

Una empresa produce dos tipos de productos, A y B. Cada unidad de A requiere dos horas de trabajo y una unidad de materia prima, y cada unidad de B requiere una hora de trabajo y dos unidades de materia prima. La empresa dispone de 100 horas de trabajo y 80 unidades de materia prima. Si el beneficio por cada unidad de A es de $40 y por cada unidad de B es de $30, ¿cuántas unidades de cada producto debe producir para maximizar su beneficio?

Modelo:

• Función objetivo

\text{Maximizar: } z = 40x + 30y

• $x$: Producto A

• $y$: Producto B

• Restricciones

\begin{align*}
2x + y & \leq 100 \quad \text{(horas de trabajo)} \\
x + 2y & \leq 80 \quad \text{(unidades de materia prima)} \\
x, y & \geq 0
\end{align*}

Método Simplex

1. Formulación del Problema:

• El problema se formula en forma estándar, donde todas las restricciones son desigualdades de "menor o igual" ($≤$), y todas las variables son no negativas.

\begin{align*}
2x + y & \leq 100 \quad \text{(horas de trabajo)} \\
x + 2y & \leq 80 \quad \text{(unidades de materia prima)} \\
x, y & \geq 0
\end{align*}

• Se introduce una variable de holgura para cada restricción para convertir las desigualdades en igualdades. Esto permite aplicar técnicas de álgebra lineal.

\begin{align*}

\text{Maximizar: } z = 40x + 30y \\

2x + y + s &= 100 \\
x + 2y + t &= 80 \\
x, y, s, t &\geq 0
\end{align*}

2. Tabla Simplex Inicial

• Se construye la tabla simplex inicial, que incluye la función objetivo y las restricciones ajustadas.

\begin{array}{c|cccc|c}
\text{} & x & y & s & t & \text{RHS} \\
z & -40 & -30 & 0 & 0 & 0 \\
s & 2 & 1 & 1 & 0 & 100 \\
t & 1 & 2 & 0 & 1 & 80 \\
\end{array}

3. Pivote: Búsqueda de la Solución Óptima

• Selección de la variable entrante: Se elige la variable no básica con el coeficiente más negativo en la función objetivo (en caso de maximización) como la variable entrante.

El coeficiente más negativo en la fila $z$ es ($−40$) para la variable $x$, por lo que $x$ será nuestra variable entrante.

• Selección de la variable saliente: Se determina cuál de las variables básicas debe dejar de serlo para permitir el ingreso de la variable entrante, utilizando el criterio del mínimo cociente.

Calculamos el ratio mínimo para determinar la variable saliente. Solo consideramos ratios positivos:

• Para $s$: $100/2 = 50$
• Para $t$: $80/1 = 80$ El mínimo ratio es $50$ para la fila $s$, por lo que $s$ será la variable saliente.

Iteraciones

• Se realizan operaciones de fila para convertir la columna de la variable entrante en una columna de unidad en la tabla simplex.

Realizaremos operaciones de fila para convertir la columna de $x$ en una columna de identidad con un $1$ bajo $s$ y $0$ en las demás filas.

\begin{array}{c|cccc|c}
 & x & y & s & t & \text{RHS} \\
z & 0 & -10 & 20 & 0 & 2000 \\
s & 1 & 0.5 & 0.5 & 0 & 50 \\
t & 0 & 1.5 & -0.5 & 1 & 30 \\
\end{array}

• Este proceso se repite, actualizando la tabla en cada paso, hasta que todos los coeficientes de la función objetivo son no negativos (en maximización), lo que indica que se ha alcanzado la solución óptima.

1. Selección de la Variable Entrante

• La variable $y$ tiene el coeficiente más negativo en la fila $z(−10)$, por lo que será nuestra variable entrante.

2. Selección de la Variable Saliente

• s: $50/0.5 = 100$
• t: $30/1.5 = 20$ 👈🏽

3. Pivoteo

• Dividir la fila $t$ por $1.5$ para normalizar la variable entrante $y$.
• Ajustar la fila $s$ y $z$ para eliminar $y$ de esas filas.

\begin{array}{c|cccc|c}
  & x & y &     s &     t & \text{RHS} \\
z & 0 & 0 &    10 &  6.67 & 2667 \\
s & 1 & 0 &  0.67 & -0.17 & 35 \\
t & 0 & 1 & -0.33 &  0.67 & 20 \\
\end{array}

Interpretación de la Solución

• La solución óptima se lee directamente de la fila de la función objetivo y las columnas correspondientes a las variables básicas en la tabla simplex final.

Revisamos los coeficientes de la fila $z$. En este caso, todos los coeficientes son no negativos ($0,0,10,6.67$), lo que indica que hemos alcanzado la solución óptima.

Solución Óptima:

• $x = 35$
• $y = 20$
• Benefício máximo: $z = 2667$

Esta solución significa que para maximizar el beneficio, la empresa debe producir $35$ unidades de producto A y $20$ unidades de producto B, resultando en un beneficio máximo de $2667$.

Las variables de holgura

¿Qué son las variables de holgura ($s$ y $t$)?

En la programación lineal, las variables de holgura son introducidas para transformar las desigualdades en ecuaciones. Esto es fundamental porque los métodos algebraicos estándar, como el método simplex, requieren un sistema de ecuaciones lineales (igualdades) para funcionar correctamente.

Si tienes una restricción como $2x+y≤100$, agregar una variable de holgura $s$ convierte esta desigualdad en la ecuación $2x+y+s=100$.

El método simplex se basa en una sólida base matemática derivada del álgebra lineal y la teoría de optimización:

Solución Básica Factible

Al convertir todas las restricciones a ecuaciones lineales (utilizando variables de holgura), establecemos un sistema de ecuaciones que puede tener múltiples soluciones. Una solución básica factible es una solución al sistema de ecuaciones que también satisface la condición de no negatividad ($x≥0,y≥0,s≥0,t≥0$).

Movimiento entre Soluciones Básicas

El método simplex explora soluciones básicas factibles moviéndose a lo largo de los bordes del poliedro definido por las restricciones. Cada paso del simplex ajusta una variable de decisión (entrada) aumentando su valor mientras ajusta otra (saliente) para mantener la factibilidad de todas las restricciones. Este proceso se repite, buscando siempre mejorar (maximizar o minimizar) el valor de la función objetivo.

Condiciones de Optimalidad

El algoritmo se detiene cuando todos los coeficientes de la función objetivo en la tabla simplex son no negativos en un problema de maximización (o no positivos en minimización). Esto se basa en la dualidad en programación lineal, que indica que si todas estas condiciones son satisfechas, no se pueden obtener mejoras adicionales en la función objetivo y la solución actual es óptima.

¿Se pueden determinar los valores de $s$ y $t$?

¡Sí, definitivamente se pueden determinar los valores de las variables de holgura ss y tt en el problema de los productos A y B! Estos valores son importantes porque indican cuánta capacidad restante hay en cada restricción después de que se han tomado las decisiones de producción optimizadas. En el contexto de nuestro ejemplo, $s$ y $t$ pueden proporcionar información sobre cuántas horas de trabajo y cuántas unidades de materia prima quedan sin usar, respectivamente.

En la solución final, podemos ver:

• $x = 35$ unidades de A
• $y = 20$ unidades de B
• $z = 2667$ es el beneficio máximo.

Valores de las Variables de Holgura $s$ y $t$:

• La variable $s$ se relaciona con la restricción original $2x+y≤100$, representando las horas de trabajo.
• La variable $t$ se relaciona con la restricción original $x+2y≤80$, representando las unidades de materia prima.

\begin{align*}
2(35) + (20) + s & = 100 \\
(35) + 2(20) + t & = 80  \\
\\
s & = 10 & \text{horas de trabajo no utilizadas}\\
t & = 5  & \text{unidades de materia prima no utilizadas}\\
\end{align*}

Estos valores de holgura indican que, en la solución óptima donde el beneficio es maximizado, todavía hay capacidad no utilizada en términos de horas de trabajo y materia prima, lo que podría permitir ajustes adicionales o indicar cierta ineficiencia en el uso completo de los recursos disponibles.

Osea que si tenemos mucha holgura podemos intentar aumentar nuestros recursos o directamente contar con menos. Si la holgura de un factor es menor deberíamos adquirir más de este recurso. Es decir, si la holgura de $s$ es pequeña deberemos contratar más trabajadores, y si lo es $t$ debemos adquirir más materia prima. Por el contrario deberiamos reducir la plantilla si la holgura de $s$ es grande, o vender materia prima que es sobrante si $t$ es grande.