La programación lineal es una técnica de optimización matemática que se utiliza para encontrar el mejor resultado (como el máximo beneficio o el mínimo costo) en un modelo que está representado por relaciones lineales. Es ampliamente utilizada en diversas áreas como la economía, la ingeniería, la logística y la investigación operativa.

1. Función Objetivo: Es la función que queremos maximizar o minimizar.
2. Variables de Decisión: Son las variables que afectan el valor de la función objetivo.
3. Restricciones: Son las limitaciones o condiciones que deben cumplirse.
4. Región Factible: Es el conjunto de todas las soluciones posibles que satisfacen las restricciones.

Supongamos que una empresa fabrica dos productos, A y B. La empresa desea maximizar sus beneficios. La función objetivo y las restricciones pueden ser las siguientes:

• Función Objetivo: Max Z = 3A + 5B
• Restricciones:
  • 2A + 3B ≤ 12
  • A + B ≤ 5
  • A, B ≥ 0

Aquí, Z es el beneficio total, y A y B son las cantidades de los productos A y B, respectivamente.

1. Identificar las Variables de Decisión: Determinar las variables que afectan el resultado.
2. Establecer la Función Objetivo: Definir la función que se desea maximizar o minimizar.
3. Definir las Restricciones: Especificar las limitaciones que deben cumplirse.
4. Escribir el Modelo Matemático: Combinar la función objetivo y las restricciones en un modelo matemático.

Supongamos que una empresa produce dos tipos de productos, X e Y. La empresa desea maximizar su beneficio. La función objetivo y las restricciones son las siguientes:

• Función Objetivo: Max Z = 4X + 3Y
• Restricciones:
  • 2X + Y ≤ 20 (Restricción de recursos)
  • X + 2Y ≤ 16 (Restricción de tiempo)
  • X, Y ≥ 0 (No negatividad)

\[ \begin{align*} \text{Maximizar } & Z = 4X + 3Y
\text{Sujeto a: } & 2X + Y \leq 20
& X + 2Y \leq 16
& X, Y \geq 0 \end{align*} \]

El método gráfico es útil para problemas con dos variables de decisión. Consiste en:

1. Dibujar las Restricciones: Graficar las restricciones en un plano cartesiano.
2. Identificar la Región Factible: Determinar el área donde todas las restricciones se superponen.
3. Evaluar la Función Objetivo: Encontrar el valor máximo o mínimo de la función objetivo en los vértices de la región factible.

Para el modelo anterior:

1. Dibujar las Restricciones:

   • 2X + Y ≤ 20
   • X + 2Y ≤ 16
   • X, Y ≥ 0

2. Identificar la Región Factible:

   • La región factible es el área donde todas las restricciones se superponen.

3. Evaluar la Función Objetivo:

   • Evaluar Z en los vértices de la región factible.

El método Simplex es un algoritmo iterativo que se utiliza para resolver problemas de programación lineal con más de dos variables de decisión. Es más eficiente que el método gráfico para problemas grandes.

Pasos del Método Simplex

1. Convertir el Modelo a Forma Estándar: Asegurarse de que todas las restricciones sean igualdades.
2. Construir la Tabla Simplex Inicial: Crear una tabla que incluya la función objetivo y las restricciones.
3. Iterar para Mejorar la Solución: Utilizar operaciones de fila para mejorar la solución iterativamente.
4. Determinar la Solución Óptima: Continuar iterando hasta que no se pueda mejorar más la función objetivo.

Para el modelo anterior, el método Simplex seguiría estos pasos:

1. Convertir a Forma Estándar:

   • Introducir variables de holgura \( S_1 \) y \( S_2 \): \[ \begin{align*} 2X + Y + S_1 &= 20
     X + 2Y + S_2 &= 16
     X, Y, S_1, S_2 &\geq 0 \end{align*} \]

2. Construir la Tabla Simplex Inicial:

   • Crear una tabla con las variables y las restricciones.

3. Iterar para Mejorar la Solución:

   • Utilizar operaciones de fila para mejorar la solución iterativamente.

4. Determinar la Solución Óptima:

   • Continuar iterando hasta que no se pueda mejorar más la función objetivo.

Formule y resuelva el siguiente problema de programación lineal utilizando el método gráfico:

• Función Objetivo: Max Z = 5X + 4Y
• Restricciones:
  • 3X + 2Y ≤ 18
  • X + Y ≤ 8
  • X, Y ≥ 0

1. Dibujar las Restricciones:

   • 3X + 2Y ≤ 18
   • X + Y ≤ 8
   • X, Y ≥ 0

2. Identificar la Región Factible:

   • La región factible es el área donde todas las restricciones se superponen.

3. Evaluar la Función Objetivo:

   • Evaluar Z en los vértices de la región factible.

Formule y resuelva el siguiente problema de programación lineal utilizando el método Simplex:

• Función Objetivo: Max Z = 6X + 5Y
• Restricciones:
  • 4X + 3Y ≤ 24
  • 2X + Y ≤ 10
  • X, Y ≥ 0

1. Convertir a Forma Estándar:

   • Introducir variables de holgura \( S_1 \) y \( S_2 \): \[ \begin{align*} 4X + 3Y + S_1 &= 24
     2X + Y + S_2 &= 10
     X, Y, S_1, S_2 &\geq 0 \end{align*} \]

2. Construir la Tabla Simplex Inicial:

   • Crear una tabla con las variables y las restricciones.

3. Iterar para Mejorar la Solución:

   • Utilizar operaciones de fila para mejorar la solución iterativamente.

4. Determinar la Solución Óptima:

   • Continuar iterando hasta que no se pueda mejorar más la función objetivo.

La programación lineal es una herramienta poderosa para resolver problemas de optimización en diversas áreas. Comprender cómo formular y resolver estos problemas utilizando métodos gráficos y el método Simplex es esencial para abordar problemas complejos de manera eficiente. En el próximo tema, exploraremos los algoritmos de optimización combinatoria, que amplían aún más nuestras capacidades para resolver problemas de optimización.