Programación Lineal: Conceptos Clave y Formulación Estándar

Programación Lineal (PLC): Planteamiento y Formulación

Elementos Clave de un Problema de Programación Lineal

• Variables de Decisión: Representan las incógnitas o decisiones que se buscan en el problema. ¿Qué estamos buscando determinar?
• Función Objetivo: Define lo que se quiere optimizar (maximizar o minimizar). ¿Cuál es el propósito de la optimización?
• Restricciones: Son las limitaciones o condiciones que deben cumplirse, como la demanda, la disponibilidad de recursos, etc. Se expresan como desigualdades o igualdades. En problemas de minimización, las restricciones suelen ser del tipo '≥', mientras que en problemas de maximización son del tipo '≤'. Además, se incluyen las restricciones de no negatividad (Xj ≥ 0, para todas las variables j) y, en algunos casos, de integralidad (Xj ∈ Z, donde Z representa el conjunto de los números enteros).

Formulación de un PLC

Un PLC puede presentarse en tres formas principales:

1. Forma Estándar
2. Forma Estandarizada
3. Forma Canónica

1. PLC en Forma Estándar

Un PLC está en forma estándar cuando:

• Tiene una función objetivo a optimizar (maximizar o minimizar).
• Todas las restricciones son igualdades (Ax = h).
• Todas las variables son no negativas (x ≥ 0).

Un PLC en forma estándar *aún no está listo* para ser resuelto directamente. Para resolverlo, debe transformarse a la forma estandarizada o canónica.

Conversión a Igualdades: Para convertir las desigualdades en igualdades, se introducen variables de holgura. Si la restricción es del tipo '≤', la variable de holgura se suma al lado izquierdo de la ecuación. Si es del tipo '≥', se resta.

Ejemplos:

• 4x1 + 3x2 ≤ 12 se convierte en 4x1 + 3x2 + x3 = 12 (x3 es la variable de holgura)
• x1 + 2x2 + 4x3 ≥ 20 se convierte en x1 + 2x2 + 4x3 - x4 = 20 (x4 es la variable de holgura)
• En ambos ejemplos, x1, x2, x3, x4 ≥ 0

2. PLC en Forma Estandarizada

Un PLC está en forma estandarizada si cumple con las condiciones de la forma estándar *y además*:

• Todos los términos independientes (los valores 'b' en Ax = b) son no negativos. Si algún término independiente es negativo, se multiplica toda la restricción correspondiente por -1.
• La matriz de restricciones (A) contiene una base canónica (una submatriz identidad). Si no la contiene, se deben añadir variables artificiales.

Ejemplo:

Dadas las restricciones:

4x1 + 3x2 ≤ 12

2x1 + 5x2 ≤ 10

x1, x2 ≥ 0

Paso 1: Introducir variables de holgura:

4x1 + 3x2 + x3 = 12

2x1 + 5x2 + x4 = 10

x1, x2, x3, x4 ≥ 0

Paso 2: Verificar que los términos independientes sean positivos (ya lo son en este caso).

Paso 3: Verificar la matriz A:

A = [[4, 3, 1, 0], [2, 5, 0, 1]]

La matriz A ya contiene una matriz identidad (las columnas de x3 y x4), por lo tanto, el PLC ya está en forma estandarizada.

Caso Especial (Variables Artificiales): Si, después de introducir las variables de holgura, la matriz A *no* contiene una matriz identidad, se deben añadir variables artificiales. Estas variables se añaden *sumándolas* a las restricciones correspondientes. El objetivo es obtener la matriz identidad. Si se necesita más de una variable artificial, se añaden tantas como sea necesario para formar la matriz identidad.

Ejemplo de como se vería la matriz si se necesitaran dos variables artificiales (x6 y x7):

[[1, 0, ... , 0, 0], [0, 1, ..., 0, 0], [..., ..., ..., 1, 0], [..., ..., ..., 0, 1]]

Importante: Al añadir variables artificiales, el problema *deja de estar estandarizado*. Estas variables introducen una penalización en la función objetivo. Si se está minimizando, las variables artificiales se *suman* a la función objetivo (con un coeficiente 'M' muy grande). Si se está maximizando, se *restan* (también con un coeficiente 'M'). Por ejemplo: Min f(x) ... + Mx6 + Mx7

Tipos de Soluciones

• Solución: Cualquier vector de variables que satisface las restricciones (Ax ≤ b).
• Solución Factible (Posible): Cualquier vector de variables que satisface las restricciones y la condición de no negatividad (Ax ≤ b, x ≥ 0).
• Solución Factible Básica: Dado un PLC en forma estándar, es una solución factible que tiene al menos 'n - m' ceros, donde 'n' es el número de variables y 'm' es el número de restricciones. Puede ser:
  • Degenerada: Tiene más de 'n - m' ceros.
  • No Degenerada: Tiene exactamente 'n - m' ceros.
• Solución Óptima: Una solución factible básica no degenerada que optimiza (maximiza o minimiza) la función objetivo.