Antología de Investigación de Operaciones
Ingeniería en Sistemas Computacionales
óptimo, esto es, el resultado que mejor alcance la meta especificada( según el modelo matemático) entre todas las alternativas de solución.
Aunque la asignación de recursos a las actividades es la aplicación más frecuente, la programación lineal tiene muchas otras posibilidades. de hecho, cualquier problema cuyo modelo matemático se ajuste al formato general del modelo de programación lineal es un problema de programación lineal. Aún más, se dispone de un procedimiento de solución extraordinariamente eficiente llamado método símplex, para resolver estos problemas, incluso los de gran tamaño. Estas son algunas causas del tremendo auge de la programación lineal en las últimas décadas.
MODELO DE PROGRAMACIÓN LINEAL
Los términos clave son recursos y actividades, en donde m denota el número de distintos tipos de recursos que se pueden usar y n denota el número de actividades bajo consideración. Algunos ejemplos de recursos son dinero y tipos especiales de maquinaria, equipo, vehículos y personal. Los ejemplos de actividades incluyen inversión en proyectos específicos, publicidad en un medio determinado y el envío de bienes de cierta fuente a cierto destino. En cualquier aplicación de programación lineal, puede ser que todas las actividades sean de un tipo general( como cualquiera de los ejemplos), y entonces cada una correspondería en forma individual a las alternativas específicas dentro de esta categoría general.
El tipo más usual de aplicación de programación lineal involucra la asignación de recursos a ciertas actividades. La cantidad disponible de cada recurso está limitada, de forma que deben asignarse con todo cuidado. La determinación de esta asignación incluye elegir los niveles de las actividades que lograrán el mejor valor posible de la medida global de efectividad.
Ciertos símbolos se usan de manera convencional para denotar las distintas componentes de un modelo de programación lineal. Estos símbolos se enumeran a continuación, junto con su interpretación para el problema general de asignación de recursos a actividades.
Z = valor de la medida global de efectividad
x j = |
nivel de la actividad j( para j = 1,2,..., n) |
c j = |
incremento en Z que resulta al aumentar una unidad en el nivel de la actividad j |
b i = |
cantidad de recurso i disponible para asignar a las actividades( para i = 1,2,..., m) |
a ij = cantidad del recurso i consumido por cada unidad de la actividad j |
El modelo establece el problema en términos de tomar decisiones sobre los niveles de las actividades, por lo que x1, x2,...., xn se llaman variables de decisión. Los valores de cj, bi y aij( para i = 1,2,...., m y j = 1,2,...., n) son las constantes de entrada al modelo. Las cj, bi y aij también se conocen como parámetros del modelo.
Forma Canónica
La forma canónica de un problema de programación lineal es:
22