Proceso para Modelar un Problema de Programación Lineal
- Determinar y definir el **objetivo** (ya sea maximizar o minimizar).
- Elaborar lista de **decisiones**.
- Definir las **variables de decisión**. (X1, X2,…, Xn).
- Elaborar una lista de **restricciones** que afectan.
- Definir la **función objetivo**, ej.: Max Z: 40 X1+ 50X2
Limitación: ≤, requerimiento: ≥
Restricciones en la Programación Lineal
Las restricciones deben establecer las limitaciones existentes en cuanto a la disponibilidad de los recursos y la necesidad de cumplir con los compromisos contraídos para el período.
Restricciones de capacidad y/o disponibilidad de recursos: Son límites que se deben a las limitaciones del sistema en cuanto a la cantidad de equipo, de espacio, de financiamiento, de materias primas o de mano de obra disponible. Un ejemplo sería la restricción que se refiere al terreno disponible para cultivos. Estas restricciones se expresan como limitaciones, o sea inecuaciones del tipo (≤). Lo que se ocupe de un recurso no puede ser mayor que lo que se tiene disponible del mismo.
Restricciones de mercado: Son límites (inferiores, superiores o ambos) de la cantidad de producto que puede venderse o usarse. Por ejemplo, las ventas históricas máximas y mínimas respecto de un producto. La última sería un requerimiento o inecuación del tipo (≥), ya que si existen comprometidas ventas de un determinado producto, no podré decidir producir menos de esa cantidad, pues no podría cumplir mis compromisos de entrega y la primera es una limitación o inecuación del tipo (≤) ya que no me conviene producir más producto que el que históricamente he sido capaz de vender cada temporada.
Restricciones de calidad o de composición de una mezcla: Son restricciones que limitan la mezcla de ingredientes y que por lo general definen la calidad de los productos resultantes. Estas restricciones pueden ser limitaciones (≤), requerimientos (≥) o las más restrictivas requerimientos del tipo (=)
Restricciones de tecnología de producción o de equilibrio de materiales: Son restricciones que definen la salida de un proceso como una función de las entradas, muchas veces con una pérdida por desperdicios o rendimiento. Estas restricciones, al igual que las anteriores, también pueden ser limitaciones (≤), requerimientos (≥) o las más restrictivas requerimientos del tipo (=), eso dependerá del proceso que se esté modelando.
Restricciones de definición: Son restricciones que definen a una variable en función de otras. Muchas veces estas restricciones provienen de definiciones contables o balances de materiales, como por ejemplo la relación entre la cantidad producida de un producto, que debe ser igual a lo que se vendió de él más lo que se dejó en inventario. Estas restricciones son, por lo general, requerimientos del tipo (=).
Caracterización de la Solución Óptima
Tipos de Restricciones
- Restricciones Activas: Son aquellas que definen directamente la ubicación del punto óptimo.
- Restricciones No Activas: Son aquellas que no participan directamente en la determinación de la ubicación del punto óptimo.
- Restricciones Redundantes: Son aquellas restricciones no activas, que no participan directamente ni siquiera en la determinación de los límites de la zona de soluciones factibles.
Precio Sombra de una Restricción
El **precio sombra** de una restricción es una medida cuantitativa de cómo influye cada una de las restricciones de un sistema, en que el valor óptimo de la función objetivo sea el que es y no otro mejor o peor. Existen dos definiciones equivalentes para el precio sombra:
- Definición Nº1: Es la tasa de *mejoramiento* que experimenta el valor óptimo de la Función Objetivo, por cada unidad que se *aumente* el término libre de una restricción.
- Definición Nº2: Es la tasa de *empeoramiento* que experimenta el valor óptimo de la Función Objetivo, por cada unidad que se *disminuya* el término libre de una restricción.
Estas dos definiciones están hechas sobre la base de que el precio sombra es positivo.
Normalmente el precio sombra de una restricción del tipo limitación (≤), que es activa, será siempre positivo.
Cuando el precio sombra de una restricción es negativo, cosa que sucede normalmente con restricciones del tipo requerimiento (≥), el efecto sobre la función objetivo es el contrario al de la definición: Cuando se aumenta el término libre la F.O. empeora y cuando se disminuye, mejora.
Rangos de Valores para el Precio Sombra de una Restricción
- El precio sombra de una restricción activa será no negativo (≥0) si la restricción es una limitación (≤).
- El precio sombra de una restricción activa será no positivo (≤0) si la restricción es un requerimiento del tipo (≥).
- El precio sombra de una restricción activa será positivo, negativo o igual a 0 si la restricción es un requerimiento del tipo (=), ello dependerá de cada modelo.
- El Precio sombra de una restricción no activa será siempre igual a cero.
Rango de Validez del Precio Sombra de una Restricción
- El valor del precio sombra de una restricción será válido sólo para aumentos o disminuciones de su término libre, hasta valores tales que no provoquen que alguna de las restricciones activas de la solución óptima original, deje de ser activa.
- La F.O. mejorará su valor (aumentará si estoy maximizando y disminuirá si estoy minimizando) cuando se aumente el valor del término libre de una restricción activa que es una limitación.
- La F.O. empeorará su valor (disminuirá si estoy maximizando y aumentará si estoy minimizando) cuando se disminuya el valor del término libre de una restricción activa que es una limitación.
- La F.O. mejorará su valor (aumentará si estoy maximizando y disminuirá si estoy minimizando) cuando se disminuya el valor del término libre de una restricción activa que es un requerimiento del tipo “mayor o igual que”.
- La F.O. empeorará su valor (disminuirá si estoy maximizando y aumentará si estoy minimizando) cuando se aumente el valor del término libre de una restricción activa que es un requerimiento del tipo “mayor o igual que”.
- La F.O. mantendrá su valor (no variará) cuando se aumente o disminuya el valor del término libre de una restricción no activa de cualquier tipo.