Fundamentos de Programación Lineal y Modelado Matemático

Programación Lineal: Conceptos Fundamentales

La Programación Lineal es una representación simplificada de la realidad utilizada para optimizar un objetivo sujeto a restricciones.

Modelación en Programación Lineal

La Modelación es un proceso de abstracción que permite construir un esquema cuantitativo. Tiene como resultado un modelo matemático de un sistema real bajo estudio.

Fases de la Modelación

La modelación se divide en dos fases:

1. Subjetiva: Definición del sistema supuesto o simplificado.
2. Objetiva: Construcción del modelo a partir del sistema simplificado.

Formulación del Modelo

La Formulación es la componente objetiva de la modelación y convierte el sistema simplificado en un modelo cuantitativo que lo describe.

Conceptos Clave

Heurística

Heurística: Procedimiento de ensayo y error.

Algoritmo

Algoritmo: Conjunto de operaciones y procedimientos que se siguen para resolver un problema.

Pasos para la Resolución de un Problema

Los pasos típicos para resolver un problema mediante programación lineal son:

1. Leer y entender el problema.
2. Formular el modelo: definir variables, función objetivo y restricciones.
3. Resolver el problema.
4. Validar el resultado.
5. Implementar la solución.
6. Controlar la solución.

Tipos Principales de Restricciones

Restricción de Capacidad

Relacionada con los recursos de infraestructura del sistema.

Restricciones de Entradas

Limitan el valor de las variables debido a la disponibilidad de recursos como materia prima.

Restricciones de Mercado

Son reflejo de los valores máximo y mínimo en las ventas o en el uso del producto, o en el nivel de la actividad a realizar.

Restricción de Composición

Son expresiones de las mezclas de los ingredientes, que definen usualmente la calidad de los productos.

Restricciones de Balance de Materiales

Expresan las salidas de un proceso en función de las entradas, tomando en cuenta generalmente cierto porcentaje de merma o desperdicio en el proceso.

Restricciones Internas

Son las que se escriben para definir el valor de una variable que surge en la formulación del problema, no siendo variable de decisión, sino una variable auxiliar creada para hacer más expedita la construcción del modelo.

Restricciones por Política Administrativa

No hacen parte de la tecnología del problema, sino que obedecen a decisiones administrativas.

El Método de la "M"

Propiedades y Manejo de Restricciones

• Para restricciones del tipo >= b: Se le resta una variable de superávit (o de exceso) y se le agrega una variable artificial positiva.
• Para restricciones del tipo = b: Se le agrega una variable artificial positiva.

Tratamiento de Variables Artificiales en la Función Objetivo

• En maximizar Z: Se agrega una variable -MRi a la función objetivo (donde Ri es la variable artificial y M es un número grande positivo), y luego se iguala a cero para llevarla a la forma estándar.
• En minimizar Z: Se agrega una variable +MRi a la función objetivo, y luego se iguala a cero.

Criterios de Entrada y Salida de Variables (Método Simplex)

• En maximizar: La variable que entra a la base es aquella con el coeficiente más negativo en la fila Z (ej: -1, -4; la más negativa es -4). La variable que sale es la que restringe más a la que entra, lo cual se comprueba dividiendo el valor de la solución (columna RHS) por los valores correspondientes en la columna de la variable que entra (siempre que el divisor sea positivo).
• En minimizar: La variable que entra a la base es aquella con el coeficiente más positivo en la fila Z (o menos negativo, si se usa la convención de minimizar Z directamente). La variable que sale se determina de la misma manera que en maximización (dividiendo RHS por los valores positivos de la columna entrante).

Tipos de Variables Auxiliares

Variable de Holgura

Son variables que se introducen en cada una de las restricciones dadas como inecuaciones (<=), y nos permiten convertirlas en igualdades. Esta variable adicionada cuantifica la cantidad sobrante del recurso (cantidad no utilizada) al poner en ejecución la solución óptima. Siendo esta una variable positiva.

Variable de Exceso

Son variables que se introducen en cada una de las restricciones dadas como inecuaciones (>=), y nos permiten convertirlas en igualdades. Siendo esta una variable negativa, nos indica cuánto ingrediente en exceso, sobre el mínimo exigido, contendrá la mezcla.

Variable de Superávit

Para las restricciones del tipo (>=), el lado derecho representa requerimientos mínimos de disponibilidad del recurso. Entonces, se define como variable de superávit el excedente del recurso por encima del requerimiento mínimo.