PLC1

1. INTRODUCCIÓN A LA PROGRAMACIÓN LINEAL

1.1 UN POCO DE HISTORIA
La Programación Lineal fue conceptualmente desarrollada antes de la segunda guerra mundial.
Sin embargo, el mayor progreso en este campo se ubica en 1947 cuando George Dantzig,
matemático estadounidense, plantea en términos muy precisos el modelo estándar al cual se
ajusta todo problema de programación lineal. PosteriormenteDantzig también formula el
procedimiento de solución conocido como Método Simplex.
Como trabajos de valor anteriores a 1947, que tuvieron influencia sobre la programación
lineal, cabe citar la Teoría de Juegos publicada en 1928 por el matemático norteamericano de
origen húngaro John Von Neumann y la extensa monografía presentada en 1939 por Leonid
Kantorovich, titulada Métodos Matemáticos en laOrganización y Planificación de la
Producción. Kantorovich, economista, ingeniero y matemático ruso, obtiene en 1975 el Premio
Nobel de Economía por sus aportaciones a la Teoría de la Asignación Óptima de Recursos.
1.2 ¿QUÉ ES UN PROGRAMA LINEAL?
La Programación (u Optimización) Matemática aborda el diseño de metodologías para resolver,
desde un punto de vista práctico, situaciones reales en las cuales,en general, se pretende
determinar la asignación de recursos escasos para cumplir un objetivo dado.1 Tales situaciones
presentan además, como aspecto común, la necesidad de identificar el mejor curso de acción (en
lo posible, el óptimo), frente a múltiples alternativas de solución.
Una de las herramientas más importantes de la optimiza ción matemática es la programación
lineal, siendo habitual suuso en diversas áreas de toma de decisiones de empresas y
organizaciones de todo el mundo.
Un problema (o programa) lineal está compuesto por una función objetivo a optimizar y un
conjunto de restricciones que limitan o condicionan dicho objetivo. Como característica
distintiva, tanto la función objetivo como las restricciones, son funciones lineales. El siguiente
ejemplo nos permitirá introducirel tema de manera sencilla.
Ejemplo 1-1
Un pequeño taller de alfarería produce vasijas y cántaros de alta calidad, con diseños y colores
autóctonos. Los principales recursos utilizados en el taller son la mano de obra calificada de
artesanos locales y cierto tipo de arcilla. Actualmente se dispone de 40 h oras de mano de obra y
75kg de arcilla, por día.
Cada vasija tiene una contribución marginalde $ 20 y requiere 1 hora de mano de obra y 3kg
de arcilla, mientras que, cada cántaro tiene una contribución marginal de $45 e insume 2 horas
de mano de obra y 1,5kg de arcilla. Se sabe además, que la demanda diaria de cántaros nunca
excede las 15 unidades.
Bajo el supuesto que todas las unidades producidas pueden venderse, se desea programar la
producción diaria de manera de maximizar lacontribución marginal total .
1

El término programación tiene el sentido de formulación de un plan o programa que ha de realizarse de manera
óptima.
1

Capítulo 1

La formulación de un programa lineal requiere la construcción de un modelo matemático en
términos de:




Variables de decisión, también denominadas variables concretas o actividades del
sistema.
Una función económica (función objetivo ofuncional) a maximizar o minimizar,
siendo ésta una función lineal de las variables de decisión.
Un conjunto de restricciones que limitan los valores de las variables de decisión,
siendo cada restricción una ecuación o inecuación lineal de las variables de decisión.

De esta forma, para el Ejemplo 1-1 tendremos,
Variables de decisión
x 1 : producción diaria de vasijas (en unidades)
x 2 : produccióndiaria de cántaros (en unidades)
Función objetivo

Maximizar z  20 x 1  45x 2
Restricciones
Disponibilidad de mano de obra (en horas diarias): x 1  2x 2  40
Disponibilidad de arcilla (en kg/día): 3x 1  1,5x 2  75
Demanda máxima (en unidades diarias): x 2  15
Como restricciones implícitas, las variables de decisión deben ser no negativas.
x1 ; x 2  0
La condición de no negatividad dota a...